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

问题描述 投票:0回答:3

我有两个 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
,但这似乎只对向量起作用。

c++ stl unordered-set
3个回答
26
投票

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

std::unordered_set
一起使用的最佳选择。

有一种名为

std::set_intersection
的算法,它允许找到两个 sorted 范围的交集:

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

当您处理

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

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


0
投票

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

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

-5
投票

std
有一个函数称为
set_intersection
。但是,使用
std::set
作为输入参数会具有非常高的复杂性。更好的解决方案是,从这些集合中创建两个向量,并使用
set_intersection
和向量作为输入参数。

© www.soinside.com 2019 - 2024. All rights reserved.