Re: STL container question
On Oct 1, 7:31 pm, Erik Wikstr=F6m <Erik-wikst...@telia.com> wrote:
On 2008-10-01 18:57, Rolf Magnus wrote:
Jeff Schwab wrote:
Boltar wrote:
I need to store a number of integer values which I will
then search on later to see if they exist in my container.
Can someone tell me which container would be quickest for
finding these values? I can't use a plain C array (unless
I make it 2^32 in size!) since I don't know the max
integer value.
Sorted vector. See Effective STL, Item 23.
For the record, you wouldn't 2^32 integers, just 2^32 bits
= 500 MiB. It's actually not that much RAM, depending on
your target system, and would let you check for integers
with O(1) complexity (rather than O(log N)).
However, it can still be slower, since it's more or less the
worst thing you can do to the cache.
Still, you should only get one cache-miss when looking for a
value, if you use a set or vector you will probably get more.
One thing I don't understand here: both a C style array and
std::vector use a single block of contiguous memory. How could
cache performance be any different for them?
(An earlier suggestion to use std::list does suffer from this,
of course.)
--
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