Re: vector::insert performance tip.
On Apr 28, 11:32 pm, kostas <skola...@gmail.com> wrote:
On Apr 28, 10:49 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
I don't see why it would need to traverse the set twice. Any hint
to why it was happening?
The implementation of STL i use it needs first to calculate
the distance s.end() - s.begin() in order to reserve the
appropriate space. Is this not the standard (or the usual)
implementation of vector::insert ?
It's the required implementation: "Complexity: The constructor
template <class InputIterator> vector(InputIterator first,
Input- Iterator last) makes only N calls to the copy constructor
of T (where N is the distance between first and last) and no
reallocations if iterators first and last are of forward,
bidirectional, or random access categories." The apparent
assumption in the standard is that copies and allocations are
expensive, and iteration is cheap. Copying basic types,
however, is very, very cheap; modern allocators aren't that
expensive, and iterating over node based containers can be
extremely expensive due to their poor locality.
--
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