比较两个无序集合的相等性有多昂贵？ [英] How expensive is comparing two unordered sets for equality?

问题描述

给出两个 std :: set s，一个人可以简单地同时遍历两个集合并比较元素，从而导致线性复杂度。这对于 std :: unordered_set 无效，因为元素可以任何顺序存储。那么 a == b 对于 std :: unordered_set 有多昂贵？

Given two std::sets, one can simply iterate through both sets simultaneously and compare the elements, resulting in linear complexity. This doesn't work for std::unordered_sets, because the elements may be stored in any order. So how expensive is a == b for std::unordered_set?

推荐答案

operator == 和 operator！= 的复杂度：

平均情况下的线性复杂度。 N ² 在最坏的情况下，其中N是容器的大小。

Linear complexity in the average case. N² in the worst case, where N is the size of the container.

更多详细信息，请参见标准§23.2.5，第11点：

More details in the standard §23.2.5, point 11:

对于 unordered_set 和 unordered_map ， operator == （即，调用 value_type的 == 运算符的次数，
key_equal（）返回的谓词以及 hash_function（）返回的哈希器）在平均情况下与 N 成正比，在最坏的情况下与N 2 成正比，其中 N 是 a.size（）。

For unordered_set and unordered_map, the complexity of operator== (i.e., the number of calls to the == operator of the value_type, to the predicate returned by key_equal(), and to the hasher returned by hash_function()) is proportional to N in the average case and to N² in the worst case, where N is a.size().

这篇关于比较两个无序集合的相等性有多昂贵？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！