std :: unordered_map相等是否依赖于插入顺序

Question

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

Answer 1

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

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

因此，只要一个中的键（和相关值）与另一个相同（但可能以不同的置换顺序），它将比较相等。

Answer 2

来自[unord.red]/12

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

因此，只要密钥相同且大小相同，无论密钥的顺序如何，容器都将相等。

Answer 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 :: distance（lhs_eq1，lhs_eq2）== std :: distance（rhs_eq1，rhs_eq2）。 std :: is_permutation（lhs_eq1，lhs_eq2，rhs_eq1）== true。

注意：

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

如果Hash和KeyEqual做（直到C ++ 20）KeyEqual（因为C ++ 20）在lhs和rhs上没有相同的行为，或者如果operator == for Key不是对分区的细化，那么行为也是未定义的KeyEqual引入的等效键组（即，如果使用operator ==将两个元素进行比较等于不同的分区）

最后，要考虑的是复杂性：

比例N调用operator == on value_type，调用key_eq返回的谓词，并调用hash_function返回的hasher，在平均情况下，在最坏的情况下与N2成比例，其中N是容器的大小。

因此，如果两个无序映射具有相同的大小，并且其中一个容器中的每个键都在另一个容器中查找，如果恰好找到它们，那么它们的值将被比较，那么它们被认为是相同的。