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

Question

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

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

标签： c++c++11language-lawyerunordered-mapunordered-set

Answer 1

本标准不作此类保证。排序必然是特定于实现的。

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

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

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