C ++ 11标准是否要求通过一个常量unordered_container访问元素的两次迭代以相同的顺序访问元素？

for (auto&& i : unordered_container) { /* ... */ } for (auto&& i : unordered_container) { /* .. */ } 

标准是否要求这两个循环访问相同顺序的元素（假定容器是未修改的）？

---

我对这个问题的分析

我读的标准和最好的我可以告诉答案是“不”

因为容器的迭代器是向前的，所以有一种语言要求a==b暗示++a==++b用于前向迭代器。 这意味着两个迭代将通过相同的path，如果他们都在同一个地方开始。 这将问题简化为标准是否需要container.begin() == container.begin() 。 我找不到任何需要的语言。

Answer 1

容器需要实现operator==() 。 那是我们可以做的：

 container c; c == c; 

这种关系需要像下面一样工作：

 std::distance(a.begin(), a.end()) == std::distance(b.begin(), b.end()) && std::equal(a.begin(), a.end(), b.begin()); 

这里的重要部分是对std::equal()的调用。 这个调用要求对container.begin()两个独立调用将产生相同的值序列。 如果没有，那么c == c将是错误的，这是没有任何意义的，因为==是一个等价关系。

因此，我的答案是，我们可以声称标准要求任何容器的两次通过必须导致相同的顺序。 显然，如果你做了任何改变容器或者使迭代器失效的情况，这个需求就会中断。

引文：

• C ++ 2011表96 – 容器要求

Answer 2

我认为@Sharth的结论是正确的，但是（对于任何关心较新标准的人）已经过时了（可能从未反映现实 – 见下文）。

最近的标准草案（例如n3797）已经改变了这些要求，显然是故意排除了订购要求。 它具体说（§23.2.5/ 12）：

如果a.size() == b.size()对两个无序容器a和b进行比较，并且对于从a.equal_range(Ea1)获得的每个等价键组[ Ea1 ， a.equal_range(Ea1) ，存在一个等价键组distance(Ea1, Ea2) == distance(Eb1, Eb2)和is_permutation(Ea1, Ea2, Eb1)返回true is_permutation(Ea1, Ea2, Eb1)从b.equal_range(Ea1) ）得到的[ Eb1 ， Eb2 ]

我也有相对较低的信心，实现实际上也符合2011年标准的要求。 特别地，无序容器通常被实现为具有用于冲突解决的链表的散列表。 由于这些链表要求较短，因此不必sorting（特别是因为存储在无序容器中的项不需要定义用于sorting的操作，如operator< ）。 在这种情况下，链接列表保持相同的项目是相当常规的，但是依次取决于插入顺序。

在这种情况下，对于包含相同项目的两个哈希表来说是相当常规的，这些项目已经以不同顺序插入，以不同顺序迭代这些项目。

理论上这样的实现不符合C ++ 11标准 – 但是我想上面提到的改变很大程度上是因为实际上不能满足这个要求（因为如上所述，容器有没有办法强制sorting）。

所以，只要你处理的是同一个容器，不变，依靠同一顺序的迭代可能是安全的。 两个具有相同内容的容器虽然（甚至在声称是C ++ 11实现的东西中，可能不会指望它比新的草稿包含更严格的要求）可能无法很好地工作。

Answer 3

我读的标准是这不能保证。 第23.2.5段第6段指出：

因此，尽pipe未指定无序容器中的元素的绝对顺序，但是其元素被分组为等价键组，使得每个组的所有元素都具有相同的键。 除非另有规定，无序容器上的变异操作应保留每个等价键组中元素的相对顺序。

让我们从表格中清楚地保证，散列到同一个密钥的元素将保留其相对顺序，而不pipe它们是什么。 这似乎相当清楚。 另外，让我们排除对容器的任何修改。 在其余范围内：

虽然这实际上并没有明确地定义迭代次序，如果没有对容器进行更改，它是不稳定的，因此我解释了在其文字面值上的语句“无序容器中元素的绝对顺序未指定”。 如果迭代次序是未定义的，那么它是未定义的，并且不能保证每次都是相同的。

我想这一切都归结为在引用的“没有指定”的摘录中是否应该被解释为“它可以是任何东西”或“在任何时候它可以是任何东西”。

我认为可以采取任何方式。 我会用最严格的字面解释来解释“没有指定”，但是如果有人会赞成前者，我不会反对。

Answer 4

无序容器会返回前向迭代器（在第24.2.5节中定义），并且它们具有以下属性： a == b implies ++a == ++b 。 这似乎意味着这么长时间unordered_container.begin() == unordered_container.begin()是真实的，遍历顺序将是相同的。

我无法find任何需要unordered_container.begin() == unordered_container.begin()语言，这导致我对“否”的试探性答案，遍历顺序不需要是相同的。