C++11中越过末尾迭代器的失效问题

26

stackoverflow.com上最受欢迎的C++帖子《迭代器失效规则》称,不清楚past-the-end迭代器(即通过end()cend()rend()crend()返回的迭代器)是否按照指向容器元素的普通迭代器相同的规则失效。这些声明适用于2003年和2011年的C++,它们推迟到一个讨论《末位迭代器失效规则》的帖子,在该帖子中,被采纳的答案表明2003标准在此问题上存在歧义。这个结论是基于23.1/10的一条评论(在swap()的上下文中),似乎暗示当规范没有明确提到past-the-end迭代器的失效时,它们可能会失效。

该帖子的一个问题评论(由mike-seymour发表)表明,在deque的情况下,C++11对此事是明确的。我的问题是关于所有容器的:

  • 在C++11中,是否有任何容器操作可能使past-the-end迭代器失效,并且该行为在语言规范中存在歧义?

换句话说,

  • 在执行不会说明可能使past-the-end迭代器失效的容器操作之后,我可以信任past-the-end迭代器的有效性吗?

8
如果执行不会使任何迭代器失效的操作,那么您可以相信超出末尾迭代器的有效性。对于其他所有情况,我不确定,也不关心:重新获取迭代器(这是一个常数时间操作),就不需要担心该特定迭代器是否已失效了... - David Rodríguez - dribeas
8
有些操作可能会使一个尾迭代器失效。例如,vector::erase会“使在删除点或之后位置的迭代器和引用失效”。尾迭代器必然“位于删除点之后”。 - James McNellis
@dribeas:感谢您的解决方法;我相信在几乎所有情况下,特别是考虑到编译器内联等因素,这是最优的。有一些轶闻证据(https://dev59.com/y3A75IYBdhLWcg3w0sp-)表明,缓存过去的末尾指针可能会带来性能上的好处;事实上,这也是我提出问题的动机。 - nknight
1
@JamesMcNellis:同意。这里标准是明确的,因为结束迭代器在删除点之后[被定义在某个地方]。那么vector::reserve()怎么样呢?23.3.6.3/5(我有修订版n3337):“重新分配使指向序列中的元素的所有迭代器失效”,而此列表不包括过去的结束迭代器,根据定义,它们不指向序列中的元素。然而,SGI实现使所有迭代器无效,可能也包括过去的结束迭代器 [http://www.sgi.com/tech/stl/Vector.html#5]。更多信息:https://dev59.com/lXI-5IYBdhLWcg3w483k#1624961 - nknight
这确实是C++11规范中的一个缺陷。 - James McNellis
4个回答

12
我的问题涉及所有容器:
在C++11中,是否存在任何可能使过期的迭代器无效的容器操作,并且该行为在语言规范中存在歧义?
我不确定您所说的“该行为在语言规范中存在歧义”是什么意思,但肯定存在会使过期迭代器失效的操作(例如向std :: vectorstd :: string 插入数据)。
换句话说,
我可以信任在执行不建议使过期的迭代器失效的容器操作后,过期的迭代器的有效性吗?
您可以像其他迭代器一样信任过期的迭代器:不会(潜在地)使迭代器失效的任何操作都不会使它们失效。除了标准存在错误的可能性外,在没有明确表示可能会使其失效的操作中,它们将保持有效。

1
评论中的“重新分配使指向序列中元素的所有迭代器都无效”引用的reserve代码,你认为这明显是标准中的缺陷吗? - Mark B
1
@Mark:很可能是这样。常识告诉我们,对于许多容器而言,使序列中的迭代器失效也必然会使末尾迭代器失效。(然而,我离语言律师还有很远的距离,只是一个高声望的C++标签用户,所以请谨慎对待我的观点。) - sbi
实际上,cppreference.com确实谈到了end()迭代器的失效。请参见https://dev59.com/h2gu5IYBdhLWcg3wZmQm#72624474(下方)。 - Shriram V
"past-the-end operators" - 错误? - Кое Кто

2
如果标准规定操作不会使迭代器失效,那么您应该信任它。否则,应将其视为标准库实现中的错误。

1
就个人而言,我同意对于我的(第二个)问题的否定回答应该意味着标准中存在错误。我同意你的回答,但我真的希望你能证明你所说的相反情况是错误的。也就是说,“如果标准没有说明,你应该相信容器操作不会使任何迭代器失效,包括超过尾部的迭代器。” - nknight

1
关于迭代器失效规则,cppreference.com#Iterator_invalidation中有提到。
相关行如下:

特别需要提到的是指向尾后元素的迭代器。一般来说,这个迭代器在失效时会像指向未删除元素的普通迭代器一样失效。因此 std::set::end 从不失效,std::unordered_set::end 仅在重新哈希时失效,std::vector::end 总是失效(因为它总是在修改后的元素之后),等等。

有一个例外情况:删除 std::deque 的最后一个元素的删除操作会使得指向尾后元素的迭代器失效,即使它不是容器的已删除元素(或根本不是元素)。结合 std::deque 迭代器的一般规则,其净结果是,唯一不会使 std::deque::end 失效的修改操作是删除第一个元素而不是最后一个元素。

另外还可以查看使用 std::set 的 end() 的测试 - https://godbolt.org/z/5ecdqYod3

0

至少在GCC中,std::map的末尾迭代器会失效:

#include <set>
#include <stdlib.h>
#include <assert.h>
int main() {
  std::set<int> a;
  a.insert(1);
  std::set<int>::reverse_iterator rit(a.rbegin());
  ++rit;
  assert(rit==a.rend());
  a.erase(a.begin());
  assert(a.rend()==rit); // FAIL
}

2
有趣但有缺陷。.rend()返回一个迭代器适配器,具体来说是适配a.begin()而不是a.end(),因此没有矛盾。根据定义,rend()适配begin(),而该迭代器已被明确地erase使其无效。 - sehe
演示该观点的计数器示例:http://coliru.stacked-crooked.com/a/8a195ac32db336f2。对于常规迭代器也是如此http://coliru.stacked-crooked.com/a/6e80855c3b88422a,即使在删除单个元素的情况下也是如此:http://coliru.stacked-crooked.com/a/e06c5188e46d52b6,就像您的原始示例一样。 - sehe

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接