在push_front()之后C++ deque的迭代器失效

Question

刚才,我正在读Josuttis的STL书.

据我所知 - c ++ vector是一个可以重新分配的c-array.所以,据我所知,为什么在push_back()之后所有迭代器和引用都会变得无效.

但我的问题是关于std :: deque.据我所知,它是大块的数组(c-array的c-array).因此push_front()在开头插入元素,如果没有空格,则deque分配新块,并将元素放在已分配块的末尾.

在中间插入()后,所有引用和迭代器都变得无效,我理解为什么 - 所有元素都被移动.但我真的误解了这句话"...在push_back()和push_front()之后所有引用都保持有效,但迭代器没有"(同样的短语可以在@ standard:23.2.2.3找到)

这是什么意思？!如果引用有效,则deque无法重新分配(==移动)其元素.那么为什么迭代器变得无效呢？为什么我不能在非移动元素插入后使用它们？或者这句话意味着,我不能确定迭代器相等于begin()或end()和溢出？

另外,我想提一下,在erase()之后,所有迭代器和引用都保持有效(除了擦除的:-)).

PS:请不要以"标准"形式回答:"它不能被使用,因为标准是这样说的".我想明白为什么,会发生什么.

Answer 1

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

在一端或另一端将一个新元素插入双端队列将永远不需要重新分配和移动exsting数据页,但它可能需要添加(因此重新分配和复制)页面指针数组,使依赖于前一个数组的任何迭代器无效页面指​​针.

Array of pointers           
(if this grows                 Data Pages
 and gets copied,           (these never move
 iterators are invalid)      due to insert at ends)
-----------------          --------------------

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