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

Question

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

附言。这个问题不同于similar questions上迭代相同的无序集两次。

Answer 1

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

考虑这个例子，看看为什么顺序可能不同，即使内容相同:让我们从两个已创建和填充的无序集合 A 和 B 开始以相同的顺序使用值，直到添加一个对象会触发重新散列。

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

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