Vector et al default initialized
Joshua...@gmail.com
>23.2.4.1 vector constructors, copy, and assignment [lib.vector.cons]
...
>explicit vector(size_type n, const T& value = T(), const Allocator& = Allocator());
Is there a specific reason they did not instead choose the following
(or something similar) instead?
explicit vector(size_type n);
explicit vector(size_type n, const T& value, const Allocator& =
Allocator());
explicit vector(size_type n, const Allocator& );
Specifically, I like to view std::vector as a better (built in) array.
However, because of this interface (and the semantics implied by it,
and formally spelled out in the standard), vectors incur an
unnecessary performance cost during construction. (A similar situation
probably exist for destruction.) A local array
int some_array[10];
does not initialize its elements. The equivalent local vector
std::vector<int> some_vector(10);
does initialize its elements. The signature of the function takes a
default argument for "value" of the default constructor for the
contained type, and then copy constructs each contained element from
the object returned by the default constructor.
This seems like a curious design decision when a main design goal of C+
+ is to be as fast as possible (while weighed against its other design
goals, like usability and platform independence).
Note that if the contained type is a class type, in the array case,
each element will be default constructed, and in the vector case, each
element will be copy constructed from a default construct object. It
differs in the case of PODs, where "default constructed" means
uninitialized, so the array is unitialized, and the vector is
initialized.
Is the reason to be consistent in style in the interface of
containers? (The iterator constructors copy construct from their
arguments. The current "explicit vector(size_type n)" constructor also
copy constructs each element. My proposed change would have the
"explicit vector(size_type n)" constructor default construct each
element. Is this especially bad for some reason?)
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pavel Minaev
> Specifically, I like to view std::vector as a better (built in) array.
> However, because of this interface (and the semantics implied by it,
> and formally spelled out in the standard), vectors incur an
> unnecessary performance cost during construction. (A similar situation
> probably exist for destruction.)
It doesn't. Destructing a vector is really not anymore costly then
destructing an array - either element destructors are trivial, in
which case the compiler will likely optimize away the entire loop, or
they are not, in which case both array and vector will have to call
destructor on each.
> A local array
> int some_array[10];
> does not initialize its elements. The equivalent local vector
> std::vector<int> some_vector(10);
> does initialize its elements. The signature of the function takes a
> default argument for "value" of the default constructor for the
> contained type, and then copy constructs each contained element from
> the object returned by the default constructor.
>
> This seems like a curious design decision when a main design goal of C+
> + is to be as fast as possible (while weighed against its other design
> goals, like usability and platform independence).
All STL containers initialize their elements, even valarray (which is
arguably even more performance-oriented than vector). It was deemed
that safety is of more importance here. Besides, you might find that
initialization penalties are rather insignificant for vectors of built-
in types - I've used vector<char> as general-purpose output buffers
many times (a typical case where initialization is not needed), and
not once it lead to a performance problem. Typically, initialization
only happens once; even if you use the buffer in a loop, you're likely
to create it outside the loop anyway.
Alberto Ganesh Barbati
The problem here is that vector is allowed to copy elements on certain
occasions (for example when reallocation occurs) and so you must ensure
that all elements in the vector are in "copyable" state. There are,
unfortunately, exotic architectures that have "trap representations" of
objects that cannot be copied. The typical example is with pointers:
there are computers that actually check if a pointer is valid even
during a copy operation and not only when it's dereferenced (this is not
done explicitly in the code, but by storing pointers in specific CPU
registers). So in order to guarantee that every object is "copyable" the
only way is to initialize everything.
>
> Note that if the contained type is a class type, in the array case,
> each element will be default constructed, and in the vector case, each
> element will be copy constructed from a default construct object. It
> differs in the case of PODs, where "default constructed" means
> uninitialized, so the array is unitialized, and the vector is
> initialized.
This is a common misconception... What you said is wrong. According to
8.5/8: "An object whose initializer is an empty set of parentheses,
i.e., (), shall be value-initialized." Value-initialization for arrays
of built-in types means that the array shall be zero-initialized (see
8.5/5). However, one reason behind this misconception is that the are a
few compilers that do not implement this rule correctly. That is a bug.
HTH,
Ganesh
Maxim Yegorushkin
> On Jul 18, 8:37 am, JoshuaMaur...@gmail.com wrote:
>
> > Specifically, I like to view std::vector as a better (built in) array.
> > However, because of this interface (and the semantics implied by it,
> > and formally spelled out in the standard), vectors incur an
> > unnecessary performance cost during construction. (A similar situation
> > probably exist for destruction.)
[]
> All STL containers initialize their elements, even valarray (which is
> arguably even more performance-oriented than vector). It was deemed
> that safety is of more importance here. Besides, you might find that
> initialization penalties are rather insignificant for vectors of built-
> in types - I've used vector<char> as general-purpose output buffers
> many times (a typical case where initialization is not needed), and
> not once it lead to a performance problem.
I was once working on a custom protocol proxy server and used
std::vector<char> as a buffer for reading messages from TCP sockets.
The TCP messages started with a 4-byte message length followed by the
message body. It would read the message length from the socket, resize
the vector to that length and read the rest of the message into the
vector. Profiling revealed that the server spent ~30% of its run-time
zeroing out the vector when resizing. Obviously, zeroing out the
buffer which was going to be read() into was unnecessary. The solution
was a custom pod_vector<> container, which did not do initialisation
and could only be used with POD types. This also allowed using
realloc() for resizing, thus making it even more efficient.
Max
Joshua...@gmail.com
isn't, at least not with a tolerable optimizer. It was late at night
and that's my excuse.
Thanks for reminding me of the hardware pointer traps. I recall
reading about them at some point, but have since forgotten.
>>>>2003 Standard 8.5.9
If no initializer is specified for an object, and the object is of
(possibly cv-qualified) non-POD class type (or array thereof), the
object shall be default-initialized; if the object is of const-
qualified type, the underlying class type shall have a user-declared
default constructor. Otherwise, if no initializer is specified for a
nonstatic object, the object and its subobjects, if any, have an
indeterminate initial value90); if the object or any of its subobjects
are of const-qualified type, the program is ill-formed.
<<<<
I read this as saying that a local POD object without an initializer
shall have an indeterminate initial value. So, a local array
int x[10];
has indeterminate initial value, whereas
std::vector<int> y(10);
has initial value 0, as the default initializor (I'm sorry I don't
speak correct standardeze) for int is 0, and the 10 elements of y are
copy constructed from this default initializor object.
Ok, I guess with the existence of these hardware traps and insert()
and erase(), it has to be "default initialized". Thank you for
enlightening me.
Niels Dekker - no return address
> Taken from the standard
>> 23.2.4.1 vector constructors, copy, and assignment [lib.vector.cons]
>> = Allocator());
>
> Is there a specific reason they did not instead choose the following
> (or something similar) instead?
> explicit vector(size_type n);
> explicit vector(size_type n, const T& value, const Allocator& =
> Allocator());
They did, actually! Did you take a look at the latest Working Draft of the
next C++ Standard? It looks like *your* vector constructors are in there!
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2691.pdf
You added:
> explicit vector(size_type n, const Allocator& );
That one not included with the Working Draft. But I guess that one would
cause trouble when having a vector of allocators... don't you think?
> My proposed change would have the "explicit vector(size_type n)"
> constructor default construct each element.
Coincidentally that's very much like the Working Draft says right now! N2691,
[vector.cons] says:
explicit vector(size_type n);
Effects: Constructs a vector with n default constructed elements.
I've been asking around recently about what it means for an element to be
"default constructed". Including here at the newsgroup: "Questions about
default constructed STL container elements."
http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/637186b5ef718412
(Thanks again for your replies, Greg!) Eventually I got an e-mail from Bjarne
Stroustrup. :-) He told me that the intention is to have those vector
elements "value-initialized", not just "default constructed". He has raised
the issue in the C++ committee, so it will be resolved. Personally I'm glad
to have those elements initialized by default. :-)
> I read this as saying that a local POD object without an initializer
> shall have an indeterminate initial value. So, a local array
> int x[10];
> has indeterminate initial value, whereas
> std::vector<int> y(10);
> has initial value 0, as the default initializor (I'm sorry I don't
> speak correct standardeze) for int is 0, and the 10 elements of y are
> copy constructed from this default initializor object.
>
> Ok, I guess with the existence of these hardware traps and insert()
> and erase(), it has to be "default initialized".
No problem about your "standardeze". But please note that within the Standard,
there's a subtle difference between the terms "default-initialized" and
"value-initialized". The expression T() gets you a /value-initialized/ object
of type T.
BTW, a compiler is free to skip the initialization of those vector elements in
cases where it doesn't have any effect on the rest of the program. For
example:
std::vector<int> v(1);
v[0] = 1; // Original value of v[0] unused.
Kind regards,
--
Niels Dekker
http://www.xs4all.nl/~nd/dekkerware
Scientific programmer at LKEB, Leiden University Medical Center
Greg Herlihy
wrote:
> JoshuaMaur...@gmail.com ha scritto:
>
> > Note that if the contained type is a class type, in the array case,
> > each element will be default constructed, and in the vector case, each
> > element will be copy constructed from a default construct object. It
> > differs in the case of PODs, where "default constructed" means
> > uninitialized, so the array is unitialized, and the vector is
> > initialized.
>
> This is a common misconception... What you said is wrong. According to
> 8.5/8: "An object whose initializer is an empty set of parentheses,
> i.e., (), shall be value-initialized." Value-initialization for arrays
> of built-in types means that the array shall be zero-initialized (see
> 8.5/5).
There are no parentheses in an array declaration - and therefore no
value-initialization of the array. For example:
int array[10];
declares an array of ten ints with no initializer. Therefore the ten
"int" array elements (being POD types) will have uninitialized (that
is, indeterminate) starting values. Whereas a std::vector of ten ints
would have to be zero-initialized (because parentheses would be
present)..
For this reason, declaring a std::vector of ints does have more
(sometimes a great deal more) overhead than declaring a comparable
array of ints (the exact amount would depend on its size).
Fortunately, additions to the Standard Library Container classes in
the next version of the C++ Standard - do provide ways to reduce this
initialization overhead: via emplace() methods and by other means.
Greg