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

Question

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

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

但我的问题是关于 std::deque。据我所知，它是大块数组(c 数组的 c 数组)。所以 push_front() 在开头插入元素，如果没有空间，deque 分配新 block ，并将元素放在已分配 block 的末尾。

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

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

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

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

Answer 1

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

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

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

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