C ++ deque的迭代器在push_front（） [英] C++ deque's iterator invalidated after push_front()
问题描述
刚才，我正在阅读Josuttis的STL书。
据我所知 - c ++ vector是一个可重新分配的c数组。所以，我明白，为什么后push_back（）所有的迭代器和引用可能会变得无效。
但我的问题是关于std :: deque。我知道它是大块（c阵列的c阵列）的阵列。因此，push_front（）在开始处插入元素，如果没有空格，deque会分配新的块，并将元素放置在分配块的末尾。
中间的所有引用和迭代器变得无效，我明白为什么 - 所有元素都被移动。
但我真的误解了短语... after push_back（）和push_front（）所有引用保持有效，但迭代器不（可以找到相同的短语@ standard：23.2.2.3）
这是什么意思？如果引用有效，则deque不能重新分配（== move）其元素。那么为什么迭代器变得无效呢？为什么我不能在非移动元素插入后使用它们？或者这个短语是什么意思，我不能确定迭代器等于begin（）或end（）和overflow？
erase（）所有迭代器和引用保持有效（除了一个:-)）。
PS：请不要回答标准不能使用，因为标准所说的。
我想知道为什么，会发生什么。
我认为迭代器无效的原因，是因为可能的deque实现指向存储元素的deque页面的指针数组。对deque中的元素的引用将直接引用page中的元素。但是，到deque的迭代器可能取决于指向各个页面的指针的向量。
在一个或另一端将新的元素插入到deque中从不需要重新分配和移动扩展数据页，但是它可能需要添加（并因此重新分配和复制）页指针数组，使依赖于先前的页指针数组的任何迭代器无效。
指针数组
（如果这增加了数据页
并被复制，（这些永远不会移动
迭代器无效）插入到末尾）
----------------- --------------------
+ ---------- + + ---------- +
| - + --------------> | |
+ ---------- + + ---------- +
| - + --------- + | |
+ ---------- + | + ---------- +
| - + --- + | | |
+ ---------- + | | + ---------- +
| |
| |
| |
| | + ---------- +
| + ----> | |
| + ------ +
| | |
| + ---------- +
| | |
| + ---------- +
|
| + ---------- +
+ ----------> | |
+ ---------- +
| |
+ ---------- +
| |
+ ---------- +
Just now, I'm reading Josuttis' STL book.
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.
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.
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)
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?
Also, I wanna mention, that after erase() all iterators and references stay valid (except the erased one :-) ).
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 ++ deque的迭代器在push_front（）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
