我有两个 unordered_set 并且想要它们的交集。我找不到库函数来做到这一点。
本质上,我想要的是这样的:
unordered_set<int> a = {1, 2, 3};
unordered_set<int> b = {2, 4, 1};
unordered_set<int> c = a.intersect(b); // Should be {1, 2}
我可以做类似的事情
unordered_set<int> c;
for (int element : a) {
if (b.count(element) > 0) {
c.insert(element);
}
}
但是,我认为应该有一种更方便的方法来做到这一点。如果没有,有人可以解释一下为什么吗?我知道有
std::set_intersection
,但这似乎只对向量起作用。
std::unordered_set
一起使用的最佳选择。
std::set_intersection
的算法,它允许找到两个 sorted 范围的交集:
构造一个从 d_first 开始的由元素组成的排序范围 在两个排序范围 [first1, last1) 和 [first2, 最后2).
std::unordered_set
时,您无法应用此算法,因为std::unordered_set
中的元素没有保证顺序。
我的建议是坚持使用循环,因为它明确说明了您想要实现的目标,并且具有线性复杂度(O(N),其中 N 是您使用 for 循环遍历的无序集合中的元素数量)这是您可能实现的最佳复杂性。
正如已接受的答案所解释的那样,直接不能做你想要的事情,并且
std::set_intersection
不适合交叉std::unordered_set
,尽管听起来像这样。理想的解决方案取决于您使用的 C++ 标准。
给定两套
std::unordered_set<T> a, b;
...
...将
a
转入路口a & b
的最佳方法如下:
// C++20 (needs <unordered_set>)
std::erase_if(a, [&b](int e) {
return !b.contains(e);
});
// C++11 (needs <unordered_set>)
for (auto it = a.begin(); it != a.end();) {
if (!b.count(*it))
it = a.erase(it);
else
++it;
}
或者,计算一个新集合
c
,其中包含 a
和 b
的交集:
// C++23 (needs <unordered_set>, <ranges>)
std::unordered_set<int> c(std::from_range, a | std::views::filter([&b](int e) {
return b.contains(e);
});
// C++20 (needs <unordered_set>, <ranges>)
auto view = a | std::views::filter([&b](int e) {
return b.contains(e);
};
std::unordered_set<int> c(view.begin(), view.end());
// C++11 (needs <unordered_set>)
std::unordered_set<int> c;
// TODO: consider reserving a size (optimistically |a| + |b|)
for (int e : a) {
if (b.count(e)) { c.insert(e); }
}
std
有一个函数称为 set_intersection
。但是,使用 std::set
作为输入参数会具有非常高的复杂性。更好的解决方案是,从这些集合中创建两个向量,并使用 set_intersection
和向量作为输入参数。