双端队列中迭代器失效的混乱
我对双端队列中的迭代器失效有点困惑。 （在这个问题的背景下）
以下是摘录自 -- C++ 标准库：教程和参考， 尼古拉·M·约苏蒂斯 (Nicolai M. Josuttis)
任何元素的插入或删除 除了开头或结尾处 使所有指针、引用无效， 和引用元素的迭代器 双端队列的。
以下是 SGI 网站的摘录：
迭代器失效的语义 双端队列如下。 插入 （包括
push_front和push_back） 使所有引用的迭代器无效 到双端队列。 擦除a的中间 deque 使所有迭代器无效 参考双端队列。 擦除在 双端队列的开始或结束（包括pop_front和pop_back）使 仅当迭代器指向 已删除的元素。
恕我直言，双端队列是块的集合，第一个块沿一个方向生长，最后一个块沿相反方向生长。
- - -
- - -
| - - ^
| - - |
V - - |
- - -
- - -
push_back、push_front 不应该对双端队列迭代器产生任何影响（我同意 Josuttis 的观点）。
正确的解释是什么？ 标准对此有何规定？
I'm bit confused regarding iterator invalidation in deque.
(In the context of this question)
Following is the excerpts from -- The C++ Standard Library: A Tutorial and Reference,
By Nicolai M. Josuttis
Any insertion or deletion of elements
other than at the beginning or end
invalidates all pointers, references,
and iterators that refer to elements
of the deque.
Following is the excerpts from SGI site:
The semantics of iterator invalidation
for deque is as follows. Insert
(includingpush_frontandpush_back)
invalidates all iterators that refer
to a deque. Erase in the middle of a
deque invalidates all iterators that
refer to the deque. Erase at the
beginning or end of a deque (includingpop_frontandpop_back) invalidates an
iterator only if it points to the
erased element.
IMHO, deque is collection of blocks with first block growing in one direction and the last block in opposite direction.
- - -
- - -
| - - ^
| - - |
V - - |
- - -
- - -
push_back, push_front should not have any impact on deque iterators ( I agree with Josuttis).
What is the correct explanation? what the standard say on this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你的意见是你的特权，但这是错误的。 :)
deque从语义上来说就是这样一种容器，但在实现方面，它被设计为由一个或多个内存块来实现。 C++ 的迭代器失效规则 来自实现，所以这就是原因。 可以说这是一个小的抽象泄漏，但是，无论如何。SGI STL 文档不是适合阅读的文档，因为SGI STL 不是 C++ 标准库。 不幸的是，Josuttis 是那些称之为“STL”的人之一，这导致了您的困惑。
简而言之，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]
进一步阅读
我不确定您正在寻找哪些进一步参考可靠来源的内容 - 相关标准段落已被引用和引用。
Your opinion is your prerogative, but it's wrong. :)
dequeis such a container semantically, but in terms of implementation it's designed to be implemented by one or more blocks of memory. C++'s iterator invalidation rules come from implementation, so this is why. Arguably this is a small abstraction leak but, well, whatever.The SGI STL documentation is not the proper documentation to read, because the SGI STL is not the C++ Standard Library. Unfortunately, Josuttis is one of those people who calls it "the STL", and this has led to your confusion.
Put simply, this passage from Josuttis is misleading in implying that the insertion or deletion of elements that are at the beginning or end do not invalidate pointers, references or iterators … though it's worth noting that he never comes out and asserts this outright.
Here are the real, proper, official rules for
std::deque:C++03
Insertion: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.2.1.3/1]
Erasure: all iterators and references are invalidated, unless the erased members are at an end (front or back) of the deque (in which case only iterators and references to the erased members are invalidated) [23.2.1.3/4]
Resizing: as per insert/erase [23.2.1.2/1]
C++11
Insertion: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.3.3.4/1]
Erasure: erasing the last element invalidates only iterators and references to the erased elements and the past-the-end iterator; erasing the first element invalidates only iterators and references to the erased elements; erasing any other elements invalidates all iterators and references (including the past-the-end iterator) [23.3.3.4/4]
Resizing: as per insert/erase [23.3.3.4/1]
Further reading
I'm not sure what further reference to credible sources you're looking for — the relevant standard passage has already been cited and quoted.
SGI 实现可能使用可增长数组，因此如果插入导致数组增长，则指向旧数组的迭代器将无效。
编辑：
查看《C++ 编程语言第三版》的第 17.2.3 节，我在 deque 的描述中没有看到任何指示哪些操作保留或使迭代器无效的内容。 我可能看错了地方，或者行为可能未定义。
The SGI implementation probably uses a growable array, so if an insert causes the array to grow, the iterators pointing to the old array are invalid.
EDIT:
Looking in section 17.2.3 of The C++ Programming Language Third Edition, I don't see anything in the description of deque that indicates what operations preserve or invalidate iterators. I may be looking in the wrong spot or the behavior may be undefined.
来自标准工作草案
正如 Josuttis 所指出的，在前面或后面插入不会使对双端队列元素的引用无效，只会使对双端队列本身的迭代器无效。
编辑：A 更多最新草案本质上说的是同一件事（第 23.2.2.3 节）
From the standard working draft
So both are correct. As Josuttis indicates, insertion at the front or back doesn't invalidate references to elements of the deque, only iterators to the deque itself.
EDIT: A more up-to-date draft says essentially the same thing (section 23.2.2.3)