removing duplicate entries in a list.

[Amit]

Hi,
I have a list of integers. At each iteration, I remove some element
from it and then insert new elements in it. The order of elements is
not important. So I guess I could use a vector also for this purpose.
However, I am also interested in having no duplicacy in elements of
the vector. So I do not want to have any integer repeated more than
once in the list.
One very naive approach could be to compare the new integer being
added to every element of the list already present. Can I do any
better, by using sort() and unique() methods(in conjunction) in the
list? I am not aware of any such methods for a vector.. Any suggestions
which one might be better in terms of efficiency?

thanks,
--a.

 

[Filip Dreger]

Hi,
I have a list of integers. At each iteration, I remove some element
from it and then insert new elements in it. The order of elements is
not important. So I guess I could use a vector also for this
purpose.
However, I am also interested in having no duplicacy in elements of
the vector. So I do not want to have any integer repeated more than
once in the list.
One very naive approach could be to compare the new integer being
added to every element of the list already present. Can I do any
better, by using sort() and unique() methods(in conjunction) in the
list? I am not aware of any such methods for a vector.. Any
suggestions
which one might be better in terms of efficiency?

If the range of integers in question is limited and you want really
efficient 'sort' and 'unique' functions, you might be better off using
a bitfield with number of fields equal to the biggest integer you wish
to store. It takes quite a lot of memory (max. range of integers / 8
bytes) but gives you zero time 'sort' and zero time 'unique' functions


regards,
Filip Dreger

 

[Cy Edmunds]

Hi,
I have a list of integers. At each iteration, I remove some element
from it and then insert new elements in it. The order of elements is
not important. So I guess I could use a vector also for this purpose.
However, I am also interested in having no duplicacy in elements of
the vector. So I do not want to have any integer repeated more than
once in the list.
One very naive approach could be to compare the new integer being
added to every element of the list already present. Can I do any
better, by using sort() and unique() methods(in conjunction) in the
list? I am not aware of any such methods for a vector.. Any suggestions
which one might be better in terms of efficiency?

thanks,
--a.

Have a look at std::set<int>.

 

[Richard Herring]

Hi,
I have a list of integers. At each iteration, I remove some element
from it and then insert new elements in it. The order of elements is
not important. So I guess I could use a vector also for this purpose.
However, I am also interested in having no duplicacy in elements of
the vector. So I do not want to have any integer repeated more than
once in the list.
One very naive approach could be to compare the new integer being
added to every element of the list already present. Can I do any
better, by using sort() and unique() methods(in conjunction) in the
list? I am not aware of any such methods for a vector..

That doesn't mean you can't do it: the reason there are no
vector-specific member functions for this is merely that the generic
(non-member) std:: algorithms will work on std::vector (unlike
std::list), so there's no point in having class-specific equivalents.

Any suggestions
which one might be better in terms of efficiency?

Since you're adding and removing all the time (which would entail
repeatedly re-sorting a vector) you might do better to use std::set,
which is intrinsically sorted already.