Re: STL set question

From:

"Victor Bazarov" <v.Abazarov@comAcast.net>

Newsgroups:

comp.lang.c++

Date:

Wed, 20 Feb 2008 11:01:03 -0500

Message-ID:

<fphirv$9no$1@news.datemas.de>

Joe Greer wrote:

"Victor Bazarov" <v.Abazarov@comAcast.net> wrote in
news:fphe98$iqu$1@news.datemas.de:

One of the ways we combined the two in our practice is to form
the collection in a set and then copy it into a vector. The
copying is O(N). Of course this means huge savings iff the
"formation" (insertions) happens before the "use" (lookups).
Not all algorithms can be massaged into that scheme, but those
that can gain significantly.

V

Does that turn out faster than just pushing them onto the vector and
doing one sort at the end or when lookup is needed?

Not sure. Perhaps this is even better. The only reason I think I
would need to have them in the set to begin with is to perform some
/rare/ lookups during the process of inserting the new ones. This
is better than re-sorting the vector after every insertion or having
to insert in the middle.

I hadn't really
thought of bringing two collections into play like this before. My
gut instinct thinks that the allocations involved in the set would out
weight the benefits if you delayed the sort until a lookup was
requested. I haven't done any tests though.

Yes, I think your gut instinct is spot on, except when some lookups
are still needed during the formation process.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask