Как удалить дубликаты из std::list? [дубликат]

24 декабря 2021, 06:50

На этот вопрос уже даны ответы здесь:

Удаление элемента контейнера map через итератор (1 ответ)

Проблема с обработкой вектора C++ STL (3 ответа)

Удаление элементов вектора (4 ответа)

Закрыт 2 года назад.

Есть такая структура:

struct Vec { double x, y, z; };

и такой двусвязный список:

std::list<Vec> points;

Нужно удалить дубликаты из него. Вот мой код, но он по какой-то причине не работает:

for (auto it = points.begin(); it != --points.end(); it++)
{
    for (auto it2 = ++it; it2 != points.end(); )
    {    
        if (it->x == it2->x && it->y == it2->y && it->z == it2->z)
        {
            it2 = points.erase(it2);
        }
        else{
            ++it2;
        }
    }
}

Хотелось бы узнать: 1) Как правильно удалять дубликаты ? 2) Почему мой код не работает?

Answer 1

Ну тут лично Я вижу 2 варианта (для примитивных типов данных и для Вашей ситуации)

1) Отсоритроватья (методом list.sort()) и дернуть std::unique (после уникальные элементы останутся отсортированными.

2) Пришить unordered_set и лямбду (после Все останется на своих местах) и все это отдать в remove_if но в list-овый ибо std::remove_if не сработает.

*3) в 20 стандарте list научится uniq) прим:

lst.unique();

Т.к. У вас структура, то придется немного пописать. Вам надо завести 2 доп объекта для сравнения и подсчета Hash и указать их в unordered_set в место дефолтных.

Под свои структуры напишите Сами. Тут будет пример

#include <iostream>
#include <algorithm>
#include <list>
#include <iterator>
#include <unordered_set>
struct s
{
    s() : val(0), val2(0) {}
    s(int val, int val2) : val(val), val2(val2) {}
    int val;
    int val2;
    bool operator<(const s& other) {
        if (val <= other.val) {
            return true;
        }
        if (val2 <= other.val2) {
            return true;
        }
        return false;
    }
    bool operator>(const s& other) {
        return (val > other.val && val2 > other.val2);
    }
    bool operator==(const s& other) {
        return (val == other.val && val2 == other.val2);
    }
    s& operator=(const s& other) {
        val = other.val;
        val2 = other.val2;
        return *this;
    }
};
std::ostream& operator<< (std::ostream &out, const s &obj)
{
    out << obj.val << " " << obj.val2 << " ";
    return out;
}
struct CustumHash
{
    size_t operator()(const s& obj) const
    { 
        return std::hash<int>{}(obj.val) ^ (std::hash<int>{}(obj.val2) << 4); 
    } 
}; 

struct CustumEqual
{
    bool operator()(const s& obj1, const s& obj2) const
    { 
        return obj1.val == obj2.val && obj1.val2 == obj2.val2;
    } 
}; 
int main()
{
    // вариант с сортировкой
    std::list<s> lst{{1, 3}, {1, 2}, {1, 4}, {1,2}};
    std::copy(std::begin(lst), std::end(lst), std::ostream_iterator<s>{std::cout, " "});
    std::cout << std::endl;
    auto cmp{[](const s& a, const s& b){if (a.val == b.val && a.val2 == b.val2 ){return false;} return true;}};
    lst.sort(cmp);
    auto last{std::unique(std::begin(lst), std::end(lst))};
    lst.erase(last, std::end(lst)); 
    std::copy(std::begin(lst), std::end(lst), std::ostream_iterator<s>{std::cout, " "});
    std::cout << std::endl << std::endl;

    // вариант без сортировки
    std::list<s> lst2{{1, 2}, {1, 3}, {1, 4}, {1,2}};
    std::unordered_set<s, CustumHash, CustumEqual> us{};
    std::copy(std::begin(lst2), std::end(lst2), std::ostream_iterator<s>{std::cout, " "});
    std::cout << std::endl;
    auto pred{[&](s n) {return (us.find(n) == us.end()) ? (us.insert(n), false) : true;}};
    lst2.remove_if(pred);
    us.clear();
    std::copy(std::begin(lst2), std::end(lst2), std::ostream_iterator<s>{std::cout, " "});
    std::cout << std::endl << std::endl;

    return 0;
}

Пример для примитивных данных:

#include <iostream>
#include <algorithm>
#include <list>
#include <iterator>
#include <unordered_set>
int main()
{
    // вариант с сортировкой
    std::list<int> lst{1, 2, 3, 5, 1, 3, 5, 1, 4, 2};
    std::copy(std::begin(lst), std::end(lst), std::ostream_iterator<int>{std::cout, " "});
    std::cout << std::endl;
    lst.sort();
    auto last = std::unique(std::begin(lst), std::end(lst));
    lst.erase(last, std::end(lst)); 
    std::copy(std::begin(lst), std::end(lst), std::ostream_iterator<int>{std::cout, " "});
    std::cout << std::endl;
    // вариант без сортировки
    std::list<int> lst2{1, 2, 3, 5, 1, 3, 5, 1, 4, 2};
    std::unordered_set<int> s;
    auto pred{[&](int n) {return (s.find(n) == s.end()) ? (s.insert(n), false) : true;}};
    lst2.remove_if(pred);
    s.clear();
    std::copy(std::begin(lst2), std::end(lst2), std::ostream_iterator<int>{std::cout, " "});
    std::cout << std::endl;
    return 0;
}