1

Possible Duplicate:
How to make elements of vector unique? (remove non adjacent duplicates)
Remove duplicates from a list<int>

I have list of pointers like 

std::list<Person*> persons;

and there is duplicates in this list during filling. How to remove duplicates and stay only unique pointers in list ?

Community
  • 1
  • 1
Damir
  • 54,277
  • 94
  • 246
  • 365

3 Answers3

8

If you can change the order of the elements, then first sort the list with list::sort, then remove the duplicates with list::unique.

std::less<Person*> cmp;
persons.sort(cmp);
persons.unique(cmp);

On the other hand, you could use an std::set. It's elements are unique, ordered, and the insert method fails if an element is already present in the set.

Bear in mind that the time complexity of insertion of single elements is logarithmic, whereas adding elements to the front or back of a list is constant time. On the other hand, std::list::sort is N*log(N), and std::unique is linear. So if you intent to perform these duplicate removals frequently, you are better off with using an std::set in the first place. Also note that in C++11 there is std::unordered_set, which has element uniqueness and average constant complexity for insertions and removals.

juanchopanza
  • 223,364
  • 34
  • 402
  • 480
  • 1
    A shame `sort` is not returning `list&`... – pmr Aug 20 '12 at 13:30
  • The insert time doesn't make much of a difference once you do an `O(N log N)` sort anyway. – Christian Rau Aug 20 '12 at 13:41
  • If you're going to call `sort()` and `unique()` after every `insert`, a `set` `insert` would be faster. Possibly _much_ faster. – David Aug 20 '12 at 13:50
  • 1
    @Dave calling `sort()` and `unique()` after every insert would be pretty crazy. But I will add a few words on the time complexity of those methods. – juanchopanza Aug 20 '12 at 13:53
  • I guess you meant *constant* complexity instead of *linear* in your sentence about `std::unordered_set`. – Christian Rau Aug 20 '12 at 17:32
  • @ChristianRau yes, of course. Thanks for paying attention to the details! – juanchopanza Aug 20 '12 at 18:18
  • 1
    How does sorting a list of pointers work? You can't use < or > to compare arbitrary pointers: http://stackoverflow.com/questions/4909766/is-it-unspecified-behavior-to-compare-pointers-to-different-arrays-for-equality – Rag Sep 11 '13 at 20:29
  • @BrianGordon very good point. I have modified the code in my answer to use `std::less`, which should yield an adequate ordering. – juanchopanza Sep 12 '13 at 11:23
2

If you don't care about insertion order use a set instead of a list. There can only be unique elements in it and it will do the sorting others are recommending automatically.

If you do care about insertion order do something like this:

auto i = std::find(persons.begin(), persons.end(), pPerson);
if(i != persons.end())
    persons.erase(i);

persons.insert(pPerson);

(I didn't compile that)

David
  • 27,652
  • 18
  • 89
  • 138
1

sort the list according to the address they are pointing at. the remove duplicates with a simple loop.

elyashiv
  • 3,623
  • 2
  • 29
  • 52