Re: Need to understand tradeoff between array and vector
On Nov 22, 11:19 pm, Juha Nieminen <nos...@thanks.invalid> wrote:
duli wrote:
So I am confused: I remember Stroustrup saying that one
should always use vectors instead of arrays.
I think there's a confusion of terminology here.
There are, in fact, two types of arrays: Static arrays and dynamic
arrays (or, more precisely, dynamically allocated arrays). A static
array looks like this:
int array[3];
A dynamic array looks like this:
int* array = new int[3];
These are two drastically different things. std::vector is by
all intents and purposes completely equivalent to the latter
(except that it's safer because it doesn't leak memory so
easily),
And that a good implementation will have bounds checking. And
that it is a vector, and not just a pointer, and that you
haven't lost the size.
and completely non-equivalent to the former.
And just how is
std::vector< int > array( 3 ) ;
different from the former? Except that it doesn't convert into
a pointer (and thus loose the size), and that it is correctly
initialized. (Both fundamental advantages.)
In general: use a C style array if you need static
initialization (in an object with static lifetime), or possible,
for very small arrays in frequently used objects, if you expect
to see lots and lots of short lived instances of those objects.
Otherwise, use std::vector.
What I believe Stroustrup was talking about was that in
situations where you would need the second type of array, you
should definitely use std::vector instead, because it's much
safer.
I suspect that Stroustrup was talking about all use. And
somehow, I doubt that he said "always"; more likely usually, or
almost always. (I'm sure, for example, that he understands the
issues of static initialization.) Or perhaps he was just saying
it in the context of a learner; someone who's just beginning to
learn C++ won't encounter the cases where a C style array makes
sense.
However, if you have such a small, fixed-size array as the
member of a class, then using a static array is definitely
more efficient than using a dynamic array (which includes
using std::vector).
I think you meant C style array, and not "static array".
(Static has a very definite meaning with regards to class
members.) As for more efficient, it depends on how the class is
used. Your scenario is one where an experienced programmer
might consider using a C style array, but it's far from
guaranteed (and is only applicable to an experienced
programmer).
There are at least two reasons why using a dynamic array (or
std::vector) instead of a static array in this situation is a
lot less efficient. In approximate order of importance:
1) 'new' and 'delete' are very heavy operations, and each time
you are instantiating your class with the std::vector as
member, and you are resizing it to have 3 elements, you are
indirectly causing a 'new' operation. When your class is
destroyed, you are indirectly causing a 'delete' operation.
These operations are not performed if you have a static array
of size 3 as a member of your class.
That, of course, depends on the implementation (and how you
define "heavy"). For this to be relevant, the arrays must also
be short-lived; who cares if it takes, say, 10 microseconds to
create one if you do a couple of million operations on it
afterwards.
2) A dynamically allocated array (of 3 elements, as in this
case) consumes significantly more memory than a static array
of 3 elements. The static array will consume only
3*sizeof(int) bytes as a member of the class, while the
std::vector will most probably consume the size of a pointer,
plus 3*sizeof(int), plus any overhead the default allocator
needs for a dynamically allocated block of memory (usually at
least 4 bytes).
This can be an important point (and I'd forgotten it). You're
right: if you expect to have literally millions of instances of
the object, you probably should go with the C style array.
There may also be an rather insignificant (at least compared
to #1 above) slowdown each time you access the dynamic array
(eg. through the std::vector) because you are doing it through
one extra level of indirection compared to the static array
(with the std::vector each time you access the array, the
compiler takes the pointer to the class instance, reads the
dynamic array pointer from a specific offset from there, and
then indexes the array through this second pointer, while with
the static array it's enough for the compiler to simply access
an offset using the first pointer).
Hmmm. The measurements I've seen seem to show the opposite,
although I'll admit that I don't know why. At any rate, it
depends on the implementation, and the underlying architecture
(available addressing modes, etc., and how efficient they
are---the only measurements I've made were on a Sparc, which is
a RISC architecture, and requires the address to be in a
register in order to access memory anyway).
--
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