c++ 双端队列的迭代器在 push_front() 之后失效

C++ deque#39;s iterator invalidated after push_front()(c++ 双端队列的迭代器在 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-array of c-arrays).所以 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.

推荐答案

我认为迭代器无效但引用无效的原因可能是由于可能的双端队列实现了指向存储元素的双端队列页面的指针数组.对双端队列中元素的引用将直接引用页面"中的元素.但是，进入双端队列的迭代器可能依赖于指向各个页面的指针向量.

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)
-----------------          --------------------

 +----------+               +----------+
 |         -+-------------->|          |
 +----------+               +----------+
 |         -+---------+     |          |
 +----------+         |     +----------+
 |         -+---+     |     |          |
 +----------+   |     |     +----------+ 
                |     |
                |     |
                |     |
                |     |     +----------+
                |     +---->|          |
                |           +----------+
                |           |          |
                |           +----------+
                |           |          |
                |           +----------+ 
                |           
                |           +----------+
                +---------->|          |
                            +----------+
                            |          |
                            +----------+
                            |          |
                            +----------+ 

这篇关于c++ 双端队列的迭代器在 push_front() 之后失效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！