Topic: several newbiew questions about stl


Author: goodbyeera@gmail.com
Date: Sun, 8 Feb 2009 19:28:18 CST
Raw View
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?


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?


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;


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.


4. Why the first two arguments of std::find_first_of() requires
forward iterator, but not just input iterator?


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&>
{...};


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?


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?
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.


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()?


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?



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]





Author: wasti.redl@gmx.net
Date: Mon, 9 Feb 2009 16:54:11 CST
Raw View
On Feb 9, 2:28 am, goodbye...@gmail.com wrote:
> 1. Does std::vector has any chance to shrink its capacity?

No.

> 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?
>

It is pure constant time in the only sane implementation.

> 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.

Because the standards committee is made up of people who care about
the practical use of the components, not about nitpicking.

> 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&>
> {...};
>
> 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?

istream_iterator parses an element from the stream using >> and stores
it in a temporary location. It doesn't make sense to modify it.
istreambuf_iterator acts directly on the buffer, which might be
provided by the caller, thus modification can be observed and makes
sense.

>
> 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()?

Oversight? I've never used bsearch myself - binary_search is far
better.

>
> 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?

I'm pretty sure the char variant is a member, and only the char*
variant a non-member. There was the design decision to make primitive
inserters/extractors members, and the others not. I don't know the
reasoning behind this.

Sebastian


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]





Author: goodbyeera@gmail.com
Date: Tue, 10 Feb 2009 16:14:33 CST
Raw View
> > 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?
>
> I'm pretty sure the char variant is a member, and only the char*
> variant a non-member. There was the design decision to make primitive
> inserters/extractors members, and the others not. I don't know the
> reasoning behind this.

I just checked the standard and it is said that input/output of char
type is defined as non-member functions.

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]





Author: Rick Wheeler <rwheeler@oyogeospace.com>
Date: Wed, 11 Feb 2009 12:28:02 CST
Raw View
On Feb 9, 4:54 pm, wasti.r...@gmx.net wrote:
> On Feb 9, 2:28 am, goodbye...@gmail.com wrote:
>
> Because the standards committee is made up of people who care about
> the practical use of the components, not about nitpicking.
>

This statement cannot be subscribed to and is is unacceptable in the
context wherein it was given. It is the responsibility of the
Committee to indeed be concerned with the details purported in the
Standard. Afterall, details provide the underpinning of the "practical
use of the components". Perhaps a different statment is in order.


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]