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

[Victor Bazarov]

Re: STL container question

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.

Store first, then sort, then search (using 'std::binary_se arch'), you
could just use 'std::vector'. If you expect both searching and updating
the container, 'std::set' is probably better, its insertions are quite
fast. What book on the Standard Library are you reading that does not
have comparison of different standard containers in terms of performance?

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]

Re: STL container question

Boltar schrieb:

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

std::set

Lars

[Jeff Schwab]

Re: STL container question

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

[Ioannis Vranos]

Re: STL container question

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,

[Victor Bazarov]

Re: STL container question

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?

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

[Ioannis Vranos]

Re: STL container question

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.

[Juha Nieminen]

Re: STL container question

Ioannis Vranos wrote:

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.

The original poster talked about storing integer values. I highly
doubt sorting a list of integers will be faster than sorting an array of
integers. In fact, I'm pretty sure of the contrary.

[Juha Nieminen]

Re: STL container question

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.

If memory usage is not an issue, std::set is by far the easiest solution.

(OTOH if the amount of integers can be counted in the millions, then
it may be better to use a sorted vector or whatever.)

[Rolf Magnus]

Re: STL container question

Ioannis Vranos wrote:

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.

And you really think that doing two pointer exchanges is faster than one
integer exchange?

[Rolf Magnus]

Re: STL container question

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=?=]

Re: STL container question

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]

Re: STL container question

On 2008-10-01 10:23:13 -0400, Ioannis Vranos
<ivranos@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]

Re: STL container question

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]

Re: STL container question

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