提问人：NoSenseEtAl 提问时间：11/3/2023 更新时间：11/3/2023 访问量：61
为什么 std：：ranges：：set_difference、std：：ranges：：set_intersection 不适用于 std：：unordered_set？
Why do std::ranges::set_difference, std::ranges::set_intersection do not work on std::unordered_set?
问：
我知道原因是这些算法被指定为需要排序范围作为输入，因此不起作用，但我想知道为什么没有指定这些算法来理解无序集合容器。unordered_set
换句话说，我明白，如果我只是给这些算法一个范围（2 个迭代器），它们就不知道如何有效地查找该未排序范围内的元素，但是当我为它提供一个具有成员的容器时，他们似乎可以做到这一点（具有可怕的最坏情况复杂性，但与快乐情况下的常规集合操作具有相同的复杂性）。.contains()
我的猜测是，这些算法已经有了大量的需求列表，并且对于这种很少使用的算法来说，处理这种情况的工作（例如确保它们不适用于多集容器）被认为不值得付出努力。
但是我可能错过了其他一些原因，为什么这是不可能的。
答：
1赞
Marshall Clow
12/17/2023
#1
你在“可怕的最坏情况复杂性”中提到了答案。
使用排序范围，您可以计算线性复杂度（）的差值/交集，但是对于无序集合，您具有二次复杂度，因为即使无序容器中的查找是恒定时间（不是给定的），那么您必须将第一个容器的每个元素与第二个容器的每个元素进行比较，因此您可以进行比较。M+NM*N
其中和“N”是容器的大小。M
评论
0赞
NoSenseEtAl
12/18/2023
这是真的，但如果你对哈希如此不走运，它仍然是最好的情况，换句话说，手动解决方案将具有相同的复杂性。因此，我看到的唯一缺点是使算法的最坏情况复杂性取决于输入类型。
0赞
Jan Schultke
12/17/2023
#2
我的猜测是，这些算法已经有了大量的需求清单
事实并非如此。问题恰恰相反：算法被设计为与迭代器一起工作，而对容器没有感知。要求非常低，尽管迭代器需要指向一个有序范围才能使算法高效。<algorithm>
但是当我为它提供一个有成员的容器时，他们似乎可以做到
.contains()
他们无法做到这一点，因为迭代器无法访问容器。迭代器根本无法使用。
您需要一个全新的重载，该重载直接与 std：：erase_if（std：：unordered_set） 一起使用.contains()std::set_differencestd::unordered_set
或者，可以将成员函数（如）添加到 中。同时，您可以轻松地制作您的功能。.difference(...)std::unordered_set
std::unordered_set<int> a, b;
// ...
// a can be turned into the intersection of a and b via:
std::erase_if(a, [&b](int e) {
return !b.contains(e);
});
评论