Menu
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.
651
Iterator Invalidation in C++When the container to which an Iterator points changes shape internally, i.e. when elements are moved from one position to another, and the initial iterator still points to the old invalid location, then it is called Iterator invalidation.
To avoid invalidation of references to elements you can use a std::deque if you do not insert or erase in the middle. To avoid invalidation of iterators you can use a std::list.
References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated. This means that once the item is erased, the iterators that pointed to it are no longer valid.
For std::vector , all iterators are invalidated after calling insert if it causes the vector's size() to exceed its capacity() (i.e. it must reallocate).
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)
----------------- --------------------
+----------+ +----------+
| -+-------------->| |
+----------+ +----------+
| -+---------+ | |
+----------+ | +----------+
| -+---+ | | |
+----------+ | | +----------+
| |
| |
| |
| | +----------+
| +---->| |
| +----------+
| | |
| +----------+
| | |
| +----------+
|
| +----------+
+---------->| |
+----------+
| |
+----------+
| |
+----------+
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
