Remove duplicates from <int>

Question

Using STL algorithms (as much as possible) such as remove_if() and list::erase , there is a good way to remove duplicates from a list defined as follows:

list<int> l;

Note that list::unique() only works if duplication occurs in sequential elements. In my case, all duplicates should be excluded regardless of their position in the list. Moreover, removing duplicates means saving only one instance of each element in the final result.

EDIT: The l.sort() option, followed by l.unique() , cannot be used, as this will destroy the list order.

Answer 1

Using the member function list::remove_if , a temporary hashed set and lambda expression.

 std::list<int> l; std::unordered_set<int> s; l.remove_if([&](int n) { return (s.find(n) == s.end()) ? (s.insert(n), false) : true; }); 

Answer 2

If maintaining the order of the list is not important, you can simply do list.sort(); list.unique(); list.sort(); list.unique();

If order is important, use the Rup clause:

 list<int>::iterator iter = l.begin(); set<int> elements; while (iter != l.end()) { if (elements.find(*iter) != elements.end()) iter = l.erase(iter); else { elements.insert(*iter); ++iter; } } 

Answer 3

He said he wants to use erase-delete idiom, so here you can use a functional object:

 struct Unifier{ set<int> foundElements; bool operator()(int & a){ if(foundElements.find(a) != foundElements.end()){ return true; }else{ foundElements.insert(a); return false; } } }; int main(){ list<int> v; v.push_back(5); v.push_back(4); v.push_back(5); v.push_back(3); v.push_back(5); v.push_back(3); copy (v.begin(), v.end(), ostream_iterator<int>(cout," ")); Unifier u; v.remove_if(u); cout << endl << "After:" << endl; copy (v.begin(), v.end(), ostream_iterator<int>(cout," ")); } 

---

Update : The code above has a subtle error. According to C ++ 11 [algorithms.general]/10 :

[Note. Unless otherwise specified, algorithms that take function objects as arguments can freely copy these function objects. Programmers who are interested in identifying an object should consider using a wrapper class that points to an object that cannot be processed, such as reference_wrapper<T> (20.8.3), or some equivalent solution. -end note]

Apparently, for std::list::remove_if not indicated “otherwise indicated”, therefore this code may not delete all duplicates, since it can create copies of the predicate at the beginning, and then use different copies of the predicate for different parts of the list. An example of this actually happens for std :: remove_if .

A simple fix for C ++ 11 is to replace v.remove_if(u) with:

 v.remove_if( reference_wrapper<decltype(u)>(u) ); 

In C ++ 03, I'm not sure if the above quote was present; but if that were then, the fix would be to make foundElements static or to refactor Unifier so that all copies of it refer to the same instance of foundElements .

Link to a related question