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

Question

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

list<int> l;

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

РЕДАКТИРОВАТЬ: нельзя выбрать опцию l.sort(), за которой следует l.unique(), так как это разрушит порядок списка.1013 *

Answer 1

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

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

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

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

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

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

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), или какое-либо эквивалентное решение.—Конец примечания]

Похоже, что для «1015 *« не указано иное », поэтому этот код может не удалить все дубликаты, поскольку он может создать копии предиката в начале, а затемиспользуйте разные копии предиката для разных частей списка. Пример этого на самом деле происходит для std :: remove_if .

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

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

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

Ссылка на связанныйвопрос