Re: vector::insert performance tip.

From:

James Kanze <james.kanze@gmail.com>

Newsgroups:

comp.lang.c++

Date:

29 Apr 2007 11:22:36 -0700

Message-ID:

<1177870956.204966.68570@y5g2000hsa.googlegroups.com>

On Apr 29, 11:09 am, rpbg...@yahoo.com (Roland Pibinger) wrote:

On 28 Apr 2007 14:32:55 -0700, 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 probably the 'normal' implementation which is faster for
random-access iterators but slower in some cases of bidirectional
iterators. I guess your number of elements is very small. Otherwise
the vector relocations in the copy(...,back_inserter(v)) variant would
be more time-consuming that the double traversal once.

I just did the test with 10 million members in the set. I get
similar results. I suspect that the lack of locality in node
based containers is the reason.

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