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

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

但我认为应该有更方便的方法来做到这一点？如果没有，有人可以解释为什么吗？我知道有 set_intersection，但它似乎只对 vector 起作用？

谢谢

Answer 1

事实上，基于循环的解决方案是您可以与 std::unordered_set 一起使用的最佳解决方案.

有一种算法叫做std::set_intersection这允许找到两个已排序范围的交集:

Constructs a sorted range beginning at d_first consisting of elements that are found in both sorted ranges [first1, last1) and [first2, last2).

当你处理std::unordered_set ，您不能应用这个算法，因为 std::unordered_set 中的元素没有保证顺序.

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