Удалить дубликаты из списка <int>

Question

Использование алгоритмов STL (как можно больше), такие как remove_if() и list::erase, есть хороший способ, чтобы удалить дубликаты из списка, определенного следующим образом:

list<int> l;

Обратите внимание что list::unique() работает только в том случае, если дублирование происходит в последовательных элементах. В моем случае все дубликаты должны быть исключены независимо от их позиции в списке. Более того, удаление дубликатов означает сохранение только одного экземпляра каждого элемента в конечном результате.

EDIT: Невозможно использовать опцию l.sort(), за которой следует l.unique(), так как это разрушит порядок в списке.

Answer 1

Использование функции list::remove_if члена, временный набор хэшированного и лямбда-выражение.

Answer 2

Если сохраняющая порядок списка не имеет значения, вы можете просто сделать list.sort(); list.unique();

Если порядок важен, используйте предложение Rup в:

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

Он сказал, что он хотел использовать erase- удалить идиомы, так вот возможный способ, с помощью функции объекта:

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," ")); 

} 

---

Обновление: Приведенный выше код имеет тонкую ошибку. Согласно C++ 11 [algorithms.general]/10:

[Примечание: если не указано иное, алгоритмы, которые принимают функциональные объекты в качестве аргументов, могут свободно копировать эти функциональные объекты. Программисты, для которых важна идентичность объекта, должны рассмотреть возможность использования класса-оболочки, который указывает на объект неготовности реализации, такой как reference_wrapper<T> (20.8.3) или какое-то эквивалентное решение. -end примечание]

Там нет, как представляется, нет «не указано иное» для std::list::remove_if, так что этот код может не удалить все дубликаты, так как он может создавать копии предиката в начале, а затем использовать различные копии одного предикат для разных частей списка. Example of this actually happening for std::remove_if.

Простое исправление для C++ 11 должен заменить v.remove_if(u) с:

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

В C++ 03 Я не уверен, если выше цитата присутствовал; но если бы это было тогда, исправление заключалось бы в том, чтобы сделать foundElements статическим или для рефакторирования Unifier, чтобы все его копии ссылались на один экземпляр foundElements.

Link to related question