STL container question

[Boltar]

Hi

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.

Thanks for any help

B2003

[Rolf Magnus]

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.

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

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.

--
Erik Wikström

[Pete Becker]

On 2008-10-01 10:23:13 -0400, Ioannis Vranos
<iv*****@no.spa m.nospamfreemai l.grsaid:

Victor Bazarov wrote:

>Ioannis Vranos wrote:

>>Victor Bazarov wrote:

Store first, then sort, then search (using 'std::binary_se arch'), you
could just use 'std::vector'.
For that case, I think std::list is a better option, since the sorting
will be faster,

Do you have any proof of that?

Lists are implemented using pointers to point to the previous and to
the next elements, so list::sort(), is more efficient by changing
pointer values, while sorting a vector involves copying objects.

In other words, no. <gOne could also point out that quicksort can be
used to sort a vector but can't be used on a list, so obviously sorting
a vector is faster. The problem with both arguments is exactly what
Victor implied: they're handwaving. Proof requires much more detailed
analysis, or if you're making a decision for a particular platform,
measurement.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[Lars Tetzlaff]

Jeff Schwab schrieb:

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

How do you get O(1) from a sorted vector<int>? A binary search costs
O(log N).

Lars

[Victor Bazarov]

Lars Tetzlaff wrote:

Jeff Schwab schrieb:

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

How do you get O(1) from a sorted vector<int>? A binary search costs
O(log N).

Jeff meant one would get O(1) from looking up in the full array of bits.
Every integer would mean a shift to form the index and a mask to get
to the bit value, one shift, one pointer addition, one dereference, one
bitwise AND per lookup, O(1).

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

[Lars Tetzlaff]

Victor Bazarov schrieb:

Lars Tetzlaff wrote:

>Jeff Schwab schrieb:

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

How do you get O(1) from a sorted vector<int>? A binary search costs
O(log N).

Jeff meant one would get O(1) from looking up in the full array of bits.
Every integer would mean a shift to form the index and a mask to get to
the bit value, one shift, one pointer addition, one dereference, one
bitwise AND per lookup, O(1).

V

I see, something like vector<bool>. Ok, that would be fast.

Lars

[Rolf Magnus]

Erik Wikström 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.

If you only do a single look-up, yes. But in that case, building up an array
of 500 Megabytes will take a quite significant amount of time. ;-)

[James Kanze]

On Oct 1, 3:40 pm, Jeff Schwab <j...@schwabcen ter.comwrote:

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

Some systems won't allow you to allocate that much as a local
variable, so you might as well use std::vector. If the
reallocations are an issue, one call up front to capacity should
solve that.

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Oct 1, 7:31 pm, Erik Wikström <Erik-wikst...@telia. comwrote:

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:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Oct 1, 7:40 pm, Pete Becker <p...@versatile coding.comwrote :

On 2008-10-01 10:23:13 -0400, Ioannis Vranos
<[e-mail] m.nospamfreemai l.grsaid:

Victor Bazarov wrote:

Ioannis Vranos wrote:
Victor Bazarov wrote:

>>Store first, then sort, then search (using
'std::binary_ search'), you could just use 'std::vector'.

>For that case, I think std::list is a better option, since
the sorting will be faster,

Do you have any proof of that?

Lists are implemented using pointers to point to the
previous and to the next elements, so list::sort(), is more
efficient by changing pointer values, while sorting a vector
involves copying objects.

In other words, no. <gOne could also point out that
quicksort can be used to sort a vector but can't be used on a
list, so obviously sorting a vector is faster. The problem
with both arguments is exactly what Victor implied: they're
handwaving. Proof requires much more detailed analysis, or if
you're making a decision for a particular platform,
measurement.

To other considerations: you can't use binary_search on
std::list---with any sort of size, that's going to make a
significant difference in favor of vector. And of course, an
std::list has horrible locality, which will translate into a lot
of cache misses (or even virtual page faults). So even if
sorting it were faster (which I somehow doubt)...

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]