14

我对双端队列中的迭代器失效感到有点困惑。（在这个问题的背景下）

以下是摘自 -- The C++ Standard Library: A Tutorial and Reference，作者 Nicolai M. Josuttis

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

以下是SGI网站的摘录：

deque 的迭代器失效语义如下。Insert（包括push_frontand push_back）使所有引用双端队列的迭代器无效。在双端队列中间进行擦除会使所有引用该双端队列的迭代器无效。仅当迭代器指向被擦除的元素时，在双端队列（包括pop_frontand ）的开头或结尾进行 擦除才会使迭代器无效。pop_back

恕我直言，双端队列是块的集合，第一个块在一个方向上增长，最后一个块在相反方向上增长。

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

push_back, push_front不应该对双端队列迭代器产生任何影响（我同意 Josuttis 的观点）。

正确的解释是什么？标准对此有何评论？

4

3 回答 3

13

来自标准工作草案

模板<class InputIterator> void insert(迭代器位置, InputIterator first, InputIterator last);

1 效果：双端队列中间的插入使所有迭代器和对双端队列元素的引用无效。在双端队列的任何一端插入都会使双端队列的所有迭代器无效，但对双端队列元素引用的有效性没有影响。”

所以两者都是正确的。正如 Josuttis 所指出的，在前面或后面的插入不会使对双端队列元素的引用无效，只会使双端队列本身的迭代器无效。

编辑：更新的草案基本上说同样的话（第 23.2.2.3 节）

于 2009-05-27T05:06:22.653 回答
12

恕我直言，双端队列是块的集合，第一个块在一个方向上增长，最后一个块在相反方向上增长。

你的意见是你的特权，但这是错误的。:)

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

SGI STL 文档不是适合阅读的文档，因为SGI STL 不是 C++ 标准库。不幸的是，Josuttis 是那些称其为“STL”的人之一，这导致了您的困惑。

以下是摘自 -- The C++ Standard Library: A Tutorial and Reference，作者 Nicolai M. Josuttis

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

简而言之，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]

  • Erasure：擦除最后一个元素只会使迭代器和对被擦除元素的引用和过去的迭代器无效；擦除第一个元素只会使迭代器和对被擦除元素的引用无效；擦除任何其他元素会使所有迭代器和引用无效（包括过去的迭代器）[23.3.3.4/4]

  • 调整大小：根据插入/擦除 [23.3.3.4/1]

进一步阅读

我不确定你在寻找什么对可靠来源的进一步参考——相关的标准段落已经被引用和引用。

于 2013-01-05T14:31:23.027 回答
0

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

编辑：

查看 The C++ Programming Language Third Edition 的第 17.2.3 节，我在 deque 的描述中看不到任何指示哪些操作保留或使迭代器无效的内容。我可能看错了地方，或者行为可能未定义。

于 2009-05-27T05:05:29.970 回答