9

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

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

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

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

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

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

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

4

1 回答 1

10

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

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

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

 +----------+               +----------+
 |         -+-------------->|          |
 +----------+               +----------+
 |         -+---------+     |          |
 +----------+         |     +----------+
 |         -+---+     |     |          |
 +----------+   |     |     +----------+ 
                |     |
                |     |
                |     |
                |     |     +----------+
                |     +---->|          |
                |           +----------+
                |           |          |
                |           +----------+
                |           |          |
                |           +----------+ 
                |           
                |           +----------+
                +---------->|          |
                            +----------+
                            |          |
                            +----------+
                            |          |
                            +----------+
于 2009-11-02T06:18:52.923 回答