Как удалить дубликаты и сохранить только уникальные указатели в списке?

Question

Можно создать дубликат:
How to make elements of vector unique? (remove non adjacent duplicates)
Remove duplicates from a list<int>

У меня есть список указателей, как

std::list<Person*> persons; 

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

Answer 1

Если вы можете изменить порядок элементов, сначала отсортируйте список с помощью list::sort, а затем удалите дубликаты с помощью list::unique.

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

С другой стороны, вы могли бы использовать std::set. Элементы уникальны, упорядочены, а метод insert терпит неудачу, если элемент уже присутствует в наборе.

Помните, что временная сложность вставки отдельных элементов логарифмическая, тогда как добавление элементов в переднюю или заднюю часть списка является постоянным временем. С другой стороны, std::list::sort - N*log(N), а std::unique - линейный. Поэтому, если вы намерены часто выполнять эти повторяющиеся удаления, вам лучше всего использовать std::set. Также обратите внимание, что в C++ 11 есть std::unordered_set, который имеет уникальность элемента и среднюю постоянную сложность для вставки и удаления.

Answer 2

сортировать список в соответствии с адресом, на который они указывают. удалить дубликаты с помощью простого цикла.

Answer 3

Если вам не нужен порядок вставки, используйте set вместо list. В нем могут быть только уникальные элементы, и он будет выполнять сортировку, которую другие рекомендуют автоматически.

Если вы заботитесь о порядке вставки сделать что-то вроде этого:

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

persons.insert(pPerson); 

(я не компилировать что)