为什么 std::ranges::set_difference、std::ranges::set_intersection 不适用于 std::unordered_set？

Question

我知道原因是这些算法被指定为需要排序范围作为输入，因此

unordered_set

将不起作用，但我想知道为什么没有指定这些算法来理解无序集容器。

换句话说，我明白，如果我只是给这些算法一个范围（2个迭代器），它们就无法知道如何有效地查找该未排序范围中的元素，但是当我向它提供一个包含成员

.contains()

的容器时，它似乎就像他们可以做到的那样（最坏情况的复杂性非常可怕，但在快乐的情况下与常规集合操作具有相同的复杂性）。

我的猜测是，这些算法已经有大量的要求，并且对于这种很少使用的算法来说，处理这种情况的工作（例如确保它们不适用于多集容器）被认为不值得付出努力。

但我可能错过了一些其他原因，为什么这是不可能的。

Answer 1

您在“可怕的最坏情况复杂性”中提到了答案。

使用排序范围，您可以计算线性复杂度的差/交集（

M+N

），但是对于无序集合，您具有二次复杂度，因为即使无序容器中的查找是恒定时间（这不是给定的），那么您必须将第一个容器的每个元素与第二个容器的每个元素进行比较，因此您可以进行

M*N

比较。

其中

M

和“N”是容器的尺寸。