在对的 std::vector 上使用 std::count 的意外行为
Unexpected behavior using `std::count` on `std::vector` of pairs
我的目标是完全删除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)
元素。
为什么会出现这种情况,如何删除 所有 个多次出现的元素?
你最大的问题是 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));
我的目标是完全删除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)
元素。
为什么会出现这种情况,如何删除 所有 个多次出现的元素?
你最大的问题是 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));