在deque中对迭代器失效的困惑

Question

关于deque中的迭代器失效,我有点困惑.(在这个问题的背景下)

以下是摘自 - The C++标准库:教程和参考,作者:Nicolai M. Josuttis

除开头或结尾之外的任何元素的插入或删除都会 使引用双端队列元素的所有指针,引用和迭代器无效.

以下是SGI网站的摘录:

deque的迭代器失效的语义如下.Insert(包括push_front和push_back)使引用deque的所有迭代器无效.在双端队列中间擦除使所有引用双端队列的迭代器无效.只有当它指向已擦除的元素时,在双端队列的开头或结尾处擦除(包括 pop_front和pop_back)才会使迭代器无效.

恕我直言,deque是块的集合,第一个块在一个方向上生长,最后一个块在相反方向上生长.

  -   -  -  
  -   -  -
  |   -  -  ^
  |   -  -  |
  V   -  -  |
      -  -  -
      -  -  -

push_back, push_front 不应该对deque迭代器产生任何影响(我同意Josuttis).

什么是正确的解释？标准对此有何看法？

Answer 1

从标准的工作草案

template <class InputIterator> void insert(iterator position,InputIterator first,InputIterator last);

1效果:deque中间的插入使所有迭代器和对deque元素的引用无效.在deque两端的插入使deque的所有迭代器无效,但对deque元素的引用的有效性没有影响."

所以两者都是正确的.正如Josuttis指出的那样,在前面或后面插入并不会使对deque元素的引用无效,只会对deque本身进行迭代.

编辑:更新的草案基本上是相同的(第23.2.2.3节)

Answer 2

恕我直言,deque是块的集合,第一个块在一个方向上生长,最后一个块在相反方向上生长.

你的意见是你的特权,但这是错的.:)

deque在语义上是这样的容器,但就实现而言,它被设计为由一个或多个内存块实现.C++的迭代器失效规则来自实现,所以这就是原因.可以说这是一个小的抽象泄漏,但是,无论如何.

SGI STL文档不是正确的文档,因为SGI STL不是C++标准库.不幸的是,Josuttis是那些称之为"STL"的人之一,这导致了你的困惑.

以下是摘自 - The C++标准库:教程和参考,作者:Nicolai M. Josuttis

除开头或结尾之外的任何元素的插入或删除都会使引用双端队列元素的所有指针,引用和迭代器无效.

简单地说,从这个约祖蒂斯通道被误导的暗示该元素的插入或缺失是在开头或结尾都没有无效指针,引用或迭代器......虽然这是值得注意的是,他从来没有出来,并声称这种顾左右而言他.

以下是真实,适当的官方规则std::deque:

C++ 03

• 插入:所有迭代器和引用都是无效的,除非插入的成员位于双端队列的末尾(前面或后面)(在这种情况下,所有迭代器都无效,但对元素的引用不受影响)[23.2.1.3/1]

• 擦除:所有迭代器和引用都是无效的,除非擦除的成员位于双端队列的末端(前面或后面)(在这种情况下,只有迭代器和对擦除成员的引用无效)[23.2.1.3/4]

• 调整大小:按插入/删除[23.2.1.2/1]

C++ 11

• 插入:所有迭代器和引用都是无效的,除非插入的成员位于双端队列的末尾(前面或后面)(在这种情况下,所有迭代器都无效,但对元素的引用不受影响)[23.3.3.4/1]

• 擦除:擦除最后一个元素只会使迭代器和对擦除元素的引用以及过去的迭代器无效; 擦除第一个元素只会使迭代器和对擦除元素的引用无效; 擦除任何其他元素会使所有迭代器和引用无效(包括过去的迭代器)[23.3.3.4/4]

• 调整大小:按插入/删除[23.3.3.4/1]

进一步阅读

• 迭代器失效规则
• "STL"和"C++标准库"之间有什么区别？

_{我不确定你还在寻找可靠来源的进一步参考 - 相关的标准段落已被引用和引用.}

Answer 3

SGI 实现可能使用可增长数组，因此如果插入导致数组增长，则指向旧数组的迭代器将无效。

编辑：

查看《C++ 编程语言第三版》的 17.2.3 节，我在 deque 的描述中没有看到任何指示哪些操作保留或使迭代器无效的内容。我可能看错了地方，或者行为可能未定义。