Re: iterator and index
Mirek Fidler wrote:
James Kanze wrote:
Mirek Fidler wrote:
All I wanted to point out that there are two mutually exclusive
optimal
vector implementations: One favors fast end(), other favors fast
size(). Obviously, one that favors fast end() is used in all STL
implementations.
There are more than two. An implementation could maintain both
the size and the end pointer, optimizing both end() and size()
(but pessimizing push_back, since it would then have to update
two variables).
I was speaking about "optimal" implementation. Maintaining both is not
optimal (by pessimizing push_back and sizeof(vector)).
Which is only pessimization if I suppose that the users make
more use of push_back than of indexing and iteration, and that
they have lots and lots of vectors.
In fact, I think that all implementations derive ultimately from
the same original code base. That code base implemented size
using "end - begin" (which requires a division by sizeof(T),
given the way pointer arithmetic works), and so do all I know of
today.
Yes, but the reason is prevalence of iterators, not deriving from the
same original base.
I doubt it. The reason why the original base was written this
way probably has more to do with the general philosophy of the
author than with concrete performance considerations, althouth
performance considerations may have played a role. The reason
why all current implementations do this, however, is certainly
simply because that's the way it was originally, and there's
been no reason to change it.
BTW, it is interesting that opposite approach (store counts of elements
instead of pointer to end and pointer to capacity limit) is a little
bit more optimal on 64-bit CPU, where you can store both capacity and
size as 32-bit numbers, so your sizeof(vector) is 16, which is much
nicer number than 24.... Working with less data is always faster.
I don't think so. Both the size and the capacity must be
size_t, which is 64 bits on my 64 bit machines. And in theory,
at least, I can create vectors with more than 2^32 elements.
(In practice, I don't have that much virtual memory configured,
at least on my machines here, so I'd run out of memory a lot
sooner.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]