如何判断两个LARGE unordered_map是否相等？

Question

给定两个大的unordered_map,比如map_a,map_b.如何有效地决定map_a与map_b具有相同的信息？例如,如果map_a是{'a':3, 'b':2}和map_b {'a':3,'b':2}那么它们是相同的.也就是说,对于map_a中的每个密钥k,map_a [k] = map_b [k].

我的问题是如何有效地决定这个问题.我知道最糟糕的时间是O( max{map_a.size(), map_b.size()} ).但有一些观察结果可以很快决定map_a不等同于map_b.例如,map_a.size()!= map_b.size().

还有其他观察结果吗？我们可以使用bucket_count()和bucket_size()吗？

Wlog,我们假设map_a和map_b具有相同的散列函数和(键,值)类型.

Answer 1

问题比看起来更难,可能是O(log(load_factor)*size),因为元素在每个映射中不需要处于相同的顺序.(因此unordered_map.)在比较之前,需要对每对相应的桶进行排序(通过哈希值).

根据23.2.5/12,

对于unordered_set和unordered_map,operator ==的复杂性(即,对value_type的==运算符,对key_equal()返回的谓词以及hash_function()返回的hasher的调用次数)与N成正比.在一般情况下,在最坏的情况下为N2,其中N是a.size().对于unordered_multiset和unordered_multimap,operator ==的复杂度在平均情况下与ΣEi2成比例,在最坏的情况下与N2成比例,其中N是a.size(),Ei是第i个等价键组的大小.一个.然而,如果每对相应的等效键组Eai和Ebi的各个元件以相同的顺序排列(通常情况下,例如,如果a和b是同一容器的未修改的副本),

这个网站的格式正确,但要注意"N2"应该是N ².

我的log(load_factor)分析可能过于简单化了:我认为算法实际上不需要分配内存.我的建议不是在家尝试这个.您应该依赖标准库的实现operator ==,因为它可以依赖于标准可能无法保证的内部不变量.