Re: several newbie questions about stl
On Feb 8, 4:53 pm, goodbye...@gmail.com wrote:
1. Does std::vector has any chance to shrink its capacity?
My understanding of the member functions relating to capacity:
reserve(): will only reallocate when the passed in argument is larger
than current capacity
insert(): will only reallocate when size is about to exceed current
capacity
erase(): will only invalidate iterators pointing to elements after the
erased one, so it cannot reallocate, quotes from standard:
resize(): simply call insert() or erase(), so won't reallocate
So, if we don't take operator=() and swap() into account, it seems
that during the lifetime of a vector, its capacity won't shrink
forever?
Correct.
But the standard declares:
A vector is a kind of sequence that supports random access
iterators. In addition, it supports (amortized) constant time
insert and erase operations at the end; insert and erase in
the middle take linear time.
If its capacity won't shrink, then erase at the end operation
should be pure constant time, not just amortized constant
time. Could anyone tell me where my understanding goes wrong?
Nowhere, really. It's just that the standard uses the
expression amortized constant time a lot elsewhere, so the
amortized ends up attached to constant even in places where it's
not necessary.
2. Why std::partition() requires its arguments to be
bi-directional iterator? Why isn't forward iterator enough?
partition(l, u, p)
m = l;
for i = [l, u]
if (p(*i))
swap(m++, i);
return m;
Because the Hoare's original algorithm (1961) requires
bi-directional iterators. (It may also result in a few less
swaps.)
3. The standard says std::binary_search() only requires
forward iterator, and claims its complexity as below:
Complexity: At most log(last - first) + 2 comparisons. So it
seems that it only counts comparison as complexity, but
ignores the cost of advance operation when the iterator is
just forward iterator, but not random access iterator. Based
on the same assumption, why not
std::reverse()/std::reverse_copy () just requires forward
iterator instead of bi-directional iterator, after all,
advance operation doesn't count? See below what standard says
about their complexity, respectively.
Complexity: Exactly (last - first)/2 swaps.
Complexity: Exactly last - first assignments.
History, probably. There are a lot of seemingly random choices
in the STL.
4. Why the first two arguments of std::find_first_of()
requires forward iterator, but not just input iterator?
Good question. (Typically, it's not very useful over an input
iterator, but there's no reason to forbid it.)
5. Difference between std::istream_iterator and
std::istreambuf_iterator?
template <class T, class charT = char, class traits =
char_traits<charT>, class Distance = ptrdiff_t>
class istream_iterator: public iterator<input_iterator_tag, T,
Distance, const T*, const T&>
{...};
The difference between reading through a streambuf, and reading
through an istream. In particular, with the streambuf_iterator:
-- you can only read characters (char, wchar_t),
-- there are no format flags (note that in istream, skipws is
on by default, so an istream_iterator<char> will not copy
any white space),
-- and the error flags aren't set when you use an
istreambuf_iterator.
In practice, the stream iterators aren't that useful, and the
input stream iterators even less so.
template<class charT, class traits = char_traits<charT>>
class istreambuf_iterator: public iterator<input_iterator_tag, charT,
typename traits::off_type, charT*, charT&>
{...};
Why the former has const modifier for the pointer and
reference type, while the latter doesn't?
Good question. You'd probably have to ask in comp.std.c++.
6. Difference of argument type of std::generate() and
std::random_shuffle()?
Why the functor argument of the former is passed by value,
while the equivalent of latter is passed by reference? What's
the rationale for such difference?
In general, in the standard library, functional objects are
passed by value. (Why, I don't know, but I suspect that it has
to do with const: if passed by const reference, they have to be
immutable, but if passed by non const reference, you can't pass
a temporary.) In the case of a random number generator, of
course, the object needs state, so pass by value doesn't work
unless an additional level of indirection is introduced.
My understanding is that pass-by-value functor cannot retain
its usage information (e.g. internal state change in the RNG),
thus calling std::generate() again with the same functor will
generate the same sequence of numbers. Pass-by-reference
functor doesn't have this problem, but on the other hand, it
prevents user from passing a temporary object. It seems that
it will be better to use a pass-by-value functor argument and
return the used functor as the function's return value, just
as what std::for_each() does.
Many solutions are possible. The standard pretty much assumes
that functional objects don't have mutable state, since how
often and when they are copied isn't specified; in practice, if
you need mutable state, you need an additional level of
indirection (formally, even for for_each, although in practice,
probably not). Random generators obviously need mutable state,
and for a lot of them, significant mutable state (making copying
expensive). So different rules apply.
7. The prototype of bsearch() is:
void *bsearch(const void *key, const void *base, size_t nmemb, size_t
size, int (*compar)(const void *, const void *));
The base argument is of type (void*) and the return value is of type
(void*). This seems to be of C-like style, which is for the sake of
ease of usage of the return value, such as the strchr() in C:
char *strchr(const char *s, int c);
But in C++, most of such functions have been changed to a pair of
overloaded functions:
const char* strchr(const char* s, int c);
char* strchr(char* s, int c);
So, why the same change is not done to bsearch()?
Probably oversight.
8. As for std::basic_ostream and std::basic_istream, why the
<< and >> operation of bool, short, int, long are all defined
as member function, but only the equivalent of char is defined
as non-member function?
To confuse people.
Seriously, they were all members in the classical iostream. And
changing this broke a lot of code.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34