两个具有相同内容的 unordered_set-s 的迭代顺序是否保证相同

Question

如果我有两个unordered_set具有相同内容的变量（如果已排序），但创建方式不同（例如，第一个变量仅插入了项目，第二个变量以不同的顺序插入、删除了项目等，但两个变量最终都具有相同的内容），迭代这两个变量会产生相同顺序的值吗？

附言。这个问题与迭代相同的无序集合两次的类似问题不同。

Answer 1

本标准不做这样的保证。排序必然是特定于实现的。

考虑这个例子，看看为什么即使内容相同，顺序也可能不同：让我们从两个无序的集合开始，A这两个集合B已经创建并填充了相同顺序的值，直到添加一个对象将触发重新哈希。

B现在考虑将一个对象添加到，然后将其删除，而不向 中添加任何对象时会发生什么A。显然，这两个集合是相同的，但由于B经过重新哈希，这些集合中对象的顺序会发生变化。

C++11 标准的第 23.2.5.12 节讨论了无序容器的相等性。它指出计算等式的最坏情况时间复杂度为 O(n^2)。这意味着不能保证相同的顺序，因为否则我们将能够在 O(n) 中检查相等性。