Adding unique data to a vector

[Abhishek Pandey]

Hi,
I have a vector of strings. I want to hold it only unique strings.
That is, before adding any new string, I want to check if it is already
present, and if yes, then I will not add the new item.
Is there a simpler and efficient way of doing it (instead of traversing
linearly through the whole list and comparing strings everytime I want to
add new item).

Thanks in advance,
Abhishek

 

[Gianni Mariani]

Hi,
I have a vector of strings. I want to hold it only unique strings.
That is, before adding any new string, I want to check if it is already
present, and if yes, then I will not add the new item.
Is there a simpler and efficient way of doing it (instead of traversing
linearly through the whole list and comparing strings everytime I want to
add new item).

std::map should be an obvious alternative to vector.

Perhaps the best alternative would be a hash container, but that's not
part of the standard stl, although many stl implementations have one.

So, *must* it be a vector, or can you change the container ?

 

[Abhishek Pandey]

std::map should be an obvious alternative to vector.

Perhaps the best alternative would be a hash container, but that's not
part of the standard stl, although many stl implementations have one.

So, *must* it be a vector, or can you change the container ?

Thanks for the reply,
Changing the container will require more code changes, which I was trying to
avoid if possible.

-Abhishek

 

[Karl Heinz Buchegger]

Thanks for the reply,
Changing the container will require more code changes, which I was trying to
avoid if possible.

How do you build up the vector?
Is it built in one rush or are things added as needed?

If the former then a possible solution is:
Just add all of the strings (you will have duplicates now).
Then sort the vector. In this way all the duplicates will be
at consecutive vector positions. Walk through the vector and
remove the duplicates.

Look up: std::sort std::unique

 

[Abhishek Pandey]

How do you build up the vector?
Is it built in one rush or are things added as needed?

If the former then a possible solution is:
Just add all of the strings (you will have duplicates now).
Then sort the vector. In this way all the duplicates will be
at consecutive vector positions. Walk through the vector and
remove the duplicates.

I add the things as and when needed and not in one go. :-(
Thanks

 

[shez]

make sure the vector is sorted at all times, then before you insert, do
a binary search.

or just use std::set.

If you cannot change the order of elements in the vector, then maintain
a separate std::set using the minimal data needed to define uniqueness.
-shez-