C++ deque 的迭代器在 push_front() 后失效
刚才，我正在阅读 Josuttis 的 STL 书.
Just now, I'm reading Josuttis' STL book.
据我所知――c++ 向量是一个可以重新分配的 c 数组.所以，我明白了，为什么在 push_back() 之后所有的迭代器和引用都会变得无效.
As far as I know -- c++ vector is a c-array that can be reallocated. So, I understand, why after push_back() all iterators and references can become invalid.
但我的问题是关于 std::deque.据我所知，它是大块数组(c 数组的 c 数组).因此 push_front() 在开头插入元素，如果没有空间，则 deque 分配新块，并将元素放置在已分配块的末尾.
But my question is about std::deque. As I know it is array of large blocks (c-array of c-arrays). So push_front() inserts element at the beginning and if there is no space, deque allocates new block, and places the element at allocated block's end.
在中间的 insert() 之后，所有引用和迭代器都变得无效，我明白为什么――所有元素都被移动了.但我真的误解了这句话......在 push_back() 和 push_front() 之后，所有引用都保持有效，但迭代器没有"(同样的短语可以在@standard:23.2.2.3 中找到)
After insert() in the middle all references and iterators become invalid and I understand why -- all elements are moved. But I really misunderstand the phrase "...after push_back() and push_front() all references stays valid, but iterators don't" (same phrase can be found @ standard:23.2.2.3)
什么意思?！如果引用有效，则 deque 无法重新分配(== 移动)其元素.那么为什么迭代器变得无效呢?为什么在插入非移动元素后不能使用它们?或者这句话的意思是，我不能确定与 begin() 或 end() 和溢出的迭代器相等吗?
What does it mean?! If references are valid, than deque couldn't reallocate (== move) its elements. So why iterators become invalid? Why can't I use them after non-moving-elements insertion? Or does the phrase mean, that I can't be sure about iterators equality to begin() or end() and overflow?
另外，我想提一下，在 erase() 之后，所有迭代器和引用都保持有效(除了被擦除的 :-) ).
Also, I wanna mention, that after erase() all iterators and references stay valid (except the erased one :-) ).
PS:请不要以标准"形式回答:不能使用，因为标准是这样说的".我想了解为什么会发生什么.
PS: please don't answer in "standard" form: "it can't be used because THE STANDARD says so". I wanna understand why, what can happen.
推荐答案
我认为迭代器失效但引用没有失效的原因可能是因为 deque 实现了指向存储元素的 deque 页面的指针数组.对双端队列中元素的引用将直接引用页面"中的元素.然而，进入双端队列的迭代器可能依赖于指向各个页面的指针向量.
I think that the reason iterators get invalidated but references not might be because of the possible deque implementation of an array of pointers to the deque's pages that store the elements. A reference to an element in a deque will refer directly to the element in a 'page'. However, an iterator into the deque might be dependant on the vector of pointers that point to the various pages.
在一端或另一端将新元素插入双端队列永远不需要重新分配和移动现有数据页，但它可能需要添加(并因此重新分配和复制)页面指针数组，使任何依赖的迭代器无效在前一个页面指针数组上.
Inserting a new element into a deque at one or another end will never require reallocating and moving exsting data pages, but it might require adding to (and therefore reallocating & copying) the array of page pointers, invalidating any iterators that depended on the previous array of page pointers.
Array of pointers
(if this grows Data Pages
and gets copied, (these never move
iterators are invalid) due to insert at ends)
----------------- --------------------
+----------+ +----------+
| -+-------------->| |
+----------+ +----------+
| -+---------+ | |
+----------+ | +----------+
| -+---+ | | |
+----------+ | | +----------+
| |
| |
| |
| | +----------+
| +---->| |
| +----------+
| | |
| +----------+
| | |
| +----------+
|
| +----------+
+---------->| |
+----------+
| |
+----------+
| |
+----------+
相关文章