std：：unordered_map 是否相等取决于插入顺序

Does std::unordered_map equality depend on insertion order

提问人：Raedwald 提问时间：8/6/2018 最后编辑：Shadow Wizard Is Sad And AngryRaedwald 更新时间：3/26/2019 访问量：5963

问：

如果使用同一组（不相等的）键值对创建两个容器，但以不同的顺序插入（因此容器包含相等的元素，但可能以不同的顺序），则根据相等运算符 （operator==） 保证容器是相等的。我假设容器元素的哈希代码和相等运算符满足其实现所需的所有约束。std::unordered_map

C++ 无序映射

评论

0赞 Ulrich Eckhardt 8/6/2018
你试过吗？此外，该保证将遵循相应的 ISO 标准，因此间接包含答案。
1赞 Raedwald 8/6/2018
@UlrichEckhardt我试过了，答案似乎是“是的，这取决于插入顺序”，但我不确定这是否是因为我犯了一个错误。
0赞 n. m. could be an AI 8/6/2018
不。（此空格故意留空）
0赞 KarlM 8/7/2018
示例代码显示 4 对<char、string>的映射的插入序列的所有排列相等
4赞 Martin Bonner supports Monica 8/7/2018
@UlrichEckhardt“您是否尝试过”无法告诉您“它不依赖于广告订单”是此实现的一项功能，还是对所有C++实现都具有保证。（我想它可以告诉你“它确实取决于插入顺序”——但下面的所有答案都表明这将是实现中的一个错误。

答：

33赞 Jerry Coffin 8/6/2018 #1

是的，在这种情况下，它们保证返回相等。具体措辞（来自N4659，§[unord.req]/12）是：

两个无序容器 和 比较相等 if 和 ，对于从 获取的每个等价键组，存在一个从 获取的等价键组，使得返回 。aba.size() == b.size()[Ea1, Ea2)a.equal_range(Ea1)[Eb1, Eb2)b.equal_range(Ea1)is_permutation(Ea1, Ea2, Eb1, Eb2)true

因此，只要一个键（和相关值）与另一个键相同（但可能以不同的排列顺序），它就会相等。

评论

2赞 David Hammen 8/7/2018
@hgm -- 红黑树？这个问题涉及无序地图，而不是（有序）地图。
3赞 Jerry Coffin 8/7/2018
@Ant：无序容器是哈希表，因此它们从哈希到同一存储桶中相同值的所有键开始。我希望他们实际上会用来检查同一存储桶中的键。这可以是 O（n）。std::is_permutation
1赞 David Hammen 8/7/2018
@Ant - 该标准的报价适用于所有未订购的容器。如果每个键最多有一个条目，这将大大简化，就像unordered_map一样。遍历第一个映射中的键值对是 O（N）。在第二个映射中找到等效的键值对平均为 O（1），O（N） 最坏情况。因此，对于无序映射，平均为 O（N），O（N^2） 最坏情况。operator==
1赞 David Hammen 8/7/2018
@JerryCoffin - 对于两个无序映射，gcc 和 llvm 实现都没有使用 .对于无序地图来说，这是极端的矫枉过正。两者都遍历第一个参数中的键值对，并在第二个参数中使用而不是获取等效的键值对（如果存在）。operator==std::is_permutationfindequal_range
1赞 Jerry Coffin 8/18/2018
@André：对不起，我可能应该修改措辞 - 但它也要求键具有相同的关联值。
14赞 NathanOliver 8/6/2018 #2

来自 [unord.red]/12

两个无序容器 和 比较相等 if 和 ，对于从 获取的每个等价键组，存在一个从 获取的等价键组，使得返回 。[...]aba.size() == b.size()[Ea1, Ea2)a.equal_­range(Ea1)[Eb1, Eb2)b.equal_­range(Ea1)is_­permutation(Ea1, Ea2, Eb1, Eb2)true

因此，只要键相同且大小相同，无论键的顺序如何，容器的比较都是相等的。

3赞 acarlstein 8/6/2018 #3

以下是 cppreference.com 关于 std：unordered_map， operator==，！=（std：：unordered_map） 的引述：

如果满足以下条件，则两个无序容器 lhs 和 rhs 的内容相等：

  • lhs.size（） == rhs.size（）
  • 从lhs.equal_range（lhs_eq1）获得的每一组等效元素[lhs_eq1，lhs_eq2）在从rhs.equal_range（rhs_eq1）获得的另一个容器[rhs_eq1，rhs_eq2）中都有一组相应的等效元素，该容器具有以下性质：
    • std：:d istance（lhs_eq1， lhs_eq2） == std：:d istance（rhs_eq1， rhs_eq2）.
    • std：：is_permutation（lhs_eq1， lhs_eq2， rhs_eq1） == true。

请注意：

如果 Key 或 T 不是 EqualityComparable，则行为未定义。

The behavior is also undefined if Hash and KeyEqual do (until C++20)KeyEqual does (since C++20) not have the same behavior on lhs and rhs or if operator== for Key is not a refinement of the partition into equivalent-key groups introduced by KeyEqual (that is, if two elements that compare equal using operator== fall into different partitions)

Finally, to consider is the complexity:

Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.

Therefore, if both unordered maps have the same size, and each key in one of the containers is looked for in the other plus, if it happens to be found then their values are compared then they are the considered the same.

上一个：Spring 组件类必须是线程安全的

下一个：EJB 有什么用