给定两个 std::set，可以简单地同时遍历两个集合并比较元素，从而导致线性复杂度。这不适用于 std::unordered_set，因为元素可以按任何顺序存储。那么 a == b 对于 std::unordered_set 有多贵？
最佳答案
最坏的情况是 O(n²)。
但无序集合实际上是按哈希排序的。 因此，可以比较哈希值(如果失败，则集合不能相等)，然后验证相同的哈希值(线性)是否具有真正相同的值(对于具有相同哈希值的不同值，O(n²))。
在最好的情况下，这是 O(n)。
如果散列函数“好”(不同的对象 -> 总是不同的散列)，通常复杂度趋向于 O(n)，如果散列函数“坏”(所有东西总是具有相同的散列)，则复杂度趋向于 O(n²)值)
关于c++ - 比较两个无序集合的相等性有多昂贵？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10118551/