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]

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]

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]

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]

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]

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]

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]

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]

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]

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?