[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

STL container question

boltar2003

10/1/2008 1:32:00 PM

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
84 Answers

Victor Bazarov

10/1/2008 1:37:00 PM

0

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_search'), 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

10/1/2008 1:37:00 PM

0

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

10/1/2008 1:40:00 PM

0

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

10/1/2008 2:10:00 PM

0

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,

Victor Bazarov

10/1/2008 2:12:00 PM

0

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?

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

10/1/2008 2:23:00 PM

0

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.

Juha Nieminen

10/1/2008 2:44:00 PM

0

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

10/1/2008 2:45:00 PM

0

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

10/1/2008 4:53:00 PM

0

Ioannis Vranos wrote:

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

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

Rolf Magnus

10/1/2008 4:57:00 PM

0

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.