9

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.

1 Answer 1

10

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)
-----------------          --------------------

 +----------+               +----------+
 |         -+-------------->|          |
 +----------+               +----------+
 |         -+---------+     |          |
 +----------+         |     +----------+
 |         -+---+     |     |          |
 +----------+   |     |     +----------+ 
                |     |
                |     |
                |     |
                |     |     +----------+
                |     +---->|          |
                |           +----------+
                |           |          |
                |           +----------+
                |           |          |
                |           +----------+ 
                |           
                |           +----------+
                +---------->|          |
                            +----------+
                            |          |
                            +----------+
                            |          |
                            +----------+ 
2
  • may be you right. but how iterators should be implemented, to become invalid after insertion new page. or they can have field "num of pages" which become incorrect?
    – f0b0s
    Nov 2, 2009 at 10:10
  • 2
    I imagine that the iterator would have two fields: one of them a pointer into the "array of pointers" on the left, and the other a pointer or offset into the corresponding "data page" on the right. So increment would be implemented as (1) increment the position in the data page, (2) if that reached the end of the page, increment the position in the master index and reset the the data page position to the start of the next page. Hence if the master index is reallocated, the iterator becomes invalid. Nov 2, 2009 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.