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

Question

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

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

标准是否要求这两个循环以相同的顺序访问元素(假设容器未经修改)？

---

我对这个问题的分析......

我读了标准,最好的我可以说答案是"不"......

由于容器的迭代器是向前的,因此有一种语言需要a==b暗示++a==++b前向迭代器.这意味着如果它们都在同一个地方开始,则两次迭代将经历相同的路径.这将问题简化为标准是否需要的另一个问题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并b比较等于if a.size() == b.size()和,对于从中获得的每个等效键组[ Ea1,Ea2] a.equal_range(Ea1),存在从中获得的等效键组[ Eb1,Eb2] b.equal_range(Ea1),distance(Ea1, Ea2) == distance(Eb1, Eb2)并is_permutation(Ea1, Ea2, Eb1)返回true.

我对实现实际上也符合2011标准要求的信心也相对较低.特别是,无序容器通常实现为具有用于冲突解决的链表的哈希表.由于预期这些链接列表很短,因此它们不一定排序(特别是因为存储在无序容器中的项目不需要定义用于排序的操作,例如operator<).在这种情况下,链表保持相同的项目是相当常规的,但顺序取决于它们的插入顺序.

在这种情况下,对于包含以不同顺序插入的相同项目来迭代不同顺序的那些项目的两个哈希表将是相当常规的.

理论上这样的实现不符合C++ 11标准 - 但我猜测上面引用的变化主要是因为在实践中无法满足这一要求(因为,如上所述,容器有无法强制执行订购).

所以,只要你处理相同的容器,不变,取决于相同顺序的迭代可能是安全的.具有相同内容的两个容器可能无法很好地工作(甚至在声称是C++ 11实现的情况下,您可能不能指望它满足比新草稿包含更严格的要求).