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

Question

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

Answer 1

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

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1, Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1, Eb2) obtained from b.equal_range(Ea1), such that is_permutation(Ea1, Ea2, Eb1, Eb2) returns true.

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

Answer 2

来自[unord.red]/12

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1, Ea2) obtained from a.equal_­range(Ea1), there exists an equivalent-key group [Eb1, Eb2) obtained from b.equal_­range(Ea1), such that is_­permutation(Ea1, Ea2, Eb1, Eb2) returns true. [...]

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

Answer 3

下面引用了 cppreference.com 关于 std:unordered_map、operator==,!=(std::unordered_map):

The contents of two unordered containers lhs and rhs are equal if the following conditions hold:

• lhs.size() == rhs.size()
• each group of equivalent elements [lhs_eq1, lhs_eq2) obtained from lhs.equal_range(lhs_eq1) has a corresponding group of equivalent elements in the other container [rhs_eq1, rhs_eq2) obtained from rhs.equal_range(rhs_eq1), that has the following properties:
  • std::distance(lhs_eq1, lhs_eq2) == std::distance(rhs_eq1, rhs_eq2).
  • std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true.

注意：

The behavior is undefined if Key or T are not 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)

最后要考虑的是复杂度：

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.

因此，如果两个无序映射具有相同的大小，并且在另一个容器中查找其中一个容器中的每个键，如果恰好找到，则比较它们的值，然后将它们视为相同.