Как удалить одинаковые элементы из списка?

Question

[Clean Coder]

Допустим дан class T и список объектов класса list<T>. Как убрать из него одинаковые элементы? (Например, список {a, b, a, c, b} превратить в {a, b, c})

Answer 1

[res2001]

В общем случае сортируете, проходите по списку и удаляете рядом стоящие одинаковые элементы.

Но может надо решать проблему более кардинальным образом - вместо list использовать более подходящий контейнер - set? В set элементы уже отсортированы и уникальны.

Comments

[Clean Coder]

В программе используется именно list. Про сортировку не совсем понял. У нас же не числа, а абстрактные объекты. Допустим, полигоны. Как их сортировать и зачем?

[res2001]

У вас же есть критерий "одинаковости" для полигона, вот по нему и сортируйте. Вам нужно только переопределить оператор < для класса полигона. https://en.cppreference.com/w/cpp/algorithm/sort
На счет set - если просто вставлять по порядку в set елементы из list, то в результате в set вы получите то что вам нужно. Для сравнения используется тот же оператор <, что и в sort.

[Roman]

Evgeny, https://ru.cppreference.com/w/cpp/algorithm/unique

у std::list есть свои
https://ru.cppreference.com/w/cpp/container/list/sort
https://en.cppreference.com/w/cpp/container/list/unique
осталось написать свой "компаратор". или operator==

Как убрать из него одинаковые элементы?

У нас же не числа, а абстрактные объекты. Допустим, полигоны. Как их сортировать и зачем?

А как вы собираетесь определять уникальность? !=?

а да еще https://en.cppreference.com/w/cpp/algorithm/stable_sort

[res2001]

Думаю, что в некоторых случаях вариант с unique будет работать быстрее, а в некоторых случаях медленнее, чем вариант с sort. Надо смотреть на сортируемый класс и размер списка.

Answer 2

[Павел]

Создаешь коллекцию гарантирующую уникальность и добавляешь в нее все значения из списка. Получаем коллекцию уникальных элементов. Если тебе на выходе нужен список - очищаешь старый или создаешь новый, после чего в него добавляешь все уникальные элементы из созданной тобой коллекции.

По времени работы выйдет O(n * (n - a)), где N - количество элементов в списке, а - количество дубликатов. Ну если уж очень грубо, то O(n^2).