使用对的"std::vector"上的"std::count"出现意外行为

Question

我的目标是完全删除std::vector<std::pair<int, int>>中多次出现的所有元素。

其思想是将std::remove与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 = [&](i_pair& 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(auto& 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)元素。

为什么会发生这种行为？如何删除多次出现的所有元素？

Answer 1

最大的问题是std::remove_if在运行时对向量的内容几乎没有保证。

它在最后保证，返回迭代器的begin()包含未删除的元素，并且从那里直到end()还有一些其他元素。

同时，您正在这个操作的中间对容器进行迭代。

std::partition更有可能起作用，因为它保证(当完成时(元素"是"；删除"；实际上存储在最后。

一个更安全的方法是生成std::unordered_map<std::pair<int,int>, std::size_t>并在一次传递中计数，然后在第二次传递中删除计数至少为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 (auto&& elem:vec) {
++counts[elem];
}
vec.erase(std::remove_if(begin(vec), end(vec), [&](auto&&elem){return counts[elem]>1;}), end(vec));

你必须自己写pair_hasher。如果你愿意接受nlgn性能，你可以做

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