Блог

Моя цель — полностью удалить все элементы в a std::vector<std::pair<int, int>> , которые встречаются более одного раза.

Идея состояла в том, чтобы использовать std::remove with std::count как часть предиката. Мой подход выглядит примерно так:

 #include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using i_pair = std::pair<int, int>;

int main()
{
    std::vector<i_pair> vec;
    vec.push_back(i_pair(0,0)); // Expected to stay
    vec.push_back(i_pair(0,1)); // Expected to go
    vec.push_back(i_pair(1,1)); // Expected to stay
    vec.push_back(i_pair(0,1)); // Expected to go

    auto predicate = [amp;](i_pairamp; p)
    {
        return std::count(vec.begin(), vec.end(), p) > 1;
    };
    auto it = std::remove_if(vec.begin(), vec.end(), predicate);

    cout << "Reordered vector:" << endl;
    for(autoamp; e : vec)
    {
        cout << e.first << " " << e.second << endl;;
    }
    cout << endl;
    
    cout << "Number of elements that would be erased: " << (vec.end() - it) << endl;

    return 0;
}
 

Массив переупорядочивается с обоими (0,1) элементами, помещенными в конец, однако итератор, возвращаемый std::remove точками на последнем элементе. Это означает, что последующая erase операция приведет к удалению только одного (0,1) элемента.

Почему происходит такое поведение и как я могу удалить все элементы, которые встречаются более одного раза?

Ваша самая большая проблема заключается std::remove_if в том, что дает очень мало гарантий относительно содержимого вектора во время его выполнения.

Это гарантирует, что в конце begin() возвращаемый итератор содержит элементы, которые не были удалены, и оттуда до end() тех пор, пока не появятся какие-то другие элементы.

Тем временем вы выполняете итерацию по контейнеру в середине этой операции.

Более вероятно, что std::partition это сработает, поскольку это гарантирует (когда сделано), что элементы, которые вы «удаляете», фактически сохраняются в конце.

Еще более безопасным было бы сделать a std::unordered_map<std::pair<int,int>, std::size_t> и count за один проход, а затем за второй проход удалить все, количество которых не менее 2. Это также O (n) вместо ваших алгоритмов O (n ^ 2), поэтому должно быть быстрее.

 std::unordered_map<i_pair,std::size_t, pair_hasher> counts;
counts.reserve(vec.size()); // no more than this
for (autoamp;amp; elem:vec) {
    counts[elem];
}
vec.erase(std::remove_if(begin(vec), end(vec), [amp;](autoamp;amp;elem){return counts[elem]>1;}), end(vec));
 

вы должны написать свой собственный pair_hasher . Если вы готовы принять производительность nlgn, вы могли бы сделать

 std::map<i_pair,std::size_t> counts;
for (autoamp;amp; elem:vec) {
    counts[elem];
}
vec.erase(std::remove_if(begin(vec), end(vec), [amp;](autoamp;amp;elem){return counts[elem]>1;}), end(vec));