两个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，但这似乎只对向量起作用？

谢谢

Answer 1

实际上，基于循环的解决方案是您最好的选择std::unordered_set。

有一种称为的算法std::set_intersection，可以找到两个排序范围的交集：

构造一个从d_first开始的排序范围，该范围由在两个排序范围 [first1，last1）和[first2，last2）中都找到的元素组成。

在处理时std::unordered_set，您无法应用此算法，因为中的元素没有保证的顺序std::unordered_set。

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