C++库求两个unordered_set的交集方法

Question

我有两个 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

，但这似乎只对向量起作用。

Answer 1

事实上，基于循环的解决方案是您可以与

std::unordered_set

一起使用的最佳选择。

有一种名为

std::set_intersection

的算法，它允许找到两个 sorted 范围的交集：

构造一个从 d_first 开始的由元素组成的排序范围 在两个排序范围 [first1, last1) 和 [first2, 最后2).

当您处理

std::unordered_set

时，您无法应用此算法，因为

std::unordered_set

中的元素没有保证顺序。

我的建议是坚持使用循环，因为它明确说明了您想要实现的目标，并且具有线性复杂度（O(N)，其中 N 是您使用 for 循环遍历的无序集合中的元素数量）这是您可能实现的最佳复杂性。

Answer 2

正如已接受的答案所解释的那样，直接不能做你想要的事情，并且

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); }
}

Answer 3

std

有一个函数称为

set_intersection

。但是，使用

std::set

作为输入参数会具有非常高的复杂性。更好的解决方案是，从这些集合中创建两个向量，并使用

set_intersection

和向量作为输入参数。