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

Question

刚才，我正在读 Josuttis 的 STL 书。

据我所知——c++向量是一个可以重新分配的c数组。所以，我明白为什么在 push_back() 之后所有迭代器和引用都会变得无效。

但我的问题是关于 std::deque 的。据我所知，它是大块数组（c 数组的 c 数组）。因此，push_front() 在开头插入元素，如果没有空间，双端队列分配新块，并将元素放置在分配块的末尾。

在中间的 insert() 之后，所有引用和迭代器都变得无效，我明白为什么——所有元素都被移动。 但我真的误解了这句话“...在push_back（）和push_front（）之后所有引用保持有效，但迭代器不”（相同的短语可以在@ standard：23.2.2.3找到）

这是什么意思？！如果引用有效，则双端队列无法重新分配（==移动）其元素。那么为什么迭代器会失效呢？为什么我在插入非移动元素后无法使用它们？或者这句话的意思是，我无法确定迭代器是否等于 begin() 或 end() 以及溢出？

另外，我想提一下，在擦除（）之后，所有迭代器和引用都保持有效（除了被擦除的:-)）。

PS：请不要以“标准”形式回答：“它不能使用，因为标准是这么说的”。 我想了解为什么，会发生什么。

Answer 1

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

将新元素插入双端队列的一端或另一端永远不需要重新分配和移动现有数据页，但可能需要添加（因此重新分配和复制）页指针数组，从而使依赖于前一个数据页的任何迭代器无效页指针数组。

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

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