Confusion on iterators invalidation in deque

Question

I'm bit confused regarding iterator invalidation in deque. (In the context of this question)

Following is the excerpts from -- The C++ Standard Library: A Tutorial and Reference, By Nicolai M. Josuttis

Any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque.

Following is the excerpts from SGI site:

The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back) invalidates all iterators that refer to a deque. Erase in the middle of a deque invalidates all iterators that refer to the deque. Erase at the beginning or end of a deque (including pop_front and pop_back) invalidates an iterator only if it points to the erased element.

IMHO, deque is collection of blocks with first block growing in one direction and the last block in opposite direction.

  -   -  -  
  -   -  -
  |   -  -  ^
  |   -  -  |
  V   -  -  |
      -  -  -
      -  -  -

push_back, push_front should not have any impact on deque iterators ( I agree with Josuttis).

What is the correct explanation? what the standard say on this?

score 13 · Answer 1 · edited Jun 20 '20 at 09:12

13

IMHO, deque is collection of blocks with first block growing in one direction and the last block in opposite direction.

Your opinion is your prerogative, but it's wrong. :)

deque is such a container semantically, but in terms of implementation it's designed to be implemented by one or more blocks of memory. C++'s iterator invalidation rules come from implementation, so this is why. Arguably this is a small abstraction leak but, well, whatever.

The SGI STL documentation is not the proper documentation to read, because the SGI STL is not the C++ Standard Library. Unfortunately, Josuttis is one of those people who calls it "the STL", and this has led to your confusion.

Following is the excerpts from -- The C++ Standard Library: A Tutorial and Reference, By Nicolai M. Josuttis

Any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque.

Put simply, this passage from Josuttis is misleading in implying that the insertion or deletion of elements that are at the beginning or end do not invalidate pointers, references or iterators … though it's worth noting that he never comes out and asserts this outright.

Here are the real, proper, official rules for std::deque:

C++03

Insertion: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.2.1.3/1]
Erasure: all iterators and references are invalidated, unless the erased members are at an end (front or back) of the deque (in which case only iterators and references to the erased members are invalidated) [23.2.1.3/4]
Resizing: as per insert/erase [23.2.1.2/1]

C++11

Insertion: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.3.3.4/1]
Erasure: erasing the last element invalidates only iterators and references to the erased elements and the past-the-end iterator; erasing the first element invalidates only iterators and references to the erased elements; erasing any other elements invalidates all iterators and references (including the past-the-end iterator) [23.3.3.4/4]
Resizing: as per insert/erase [23.3.3.4/1]

Ah yeah, this is exactly what I was hoping for, thanks. The existing answers were really confusing (e.g. "iterators to the deque *itself*" really threw me off), this cleared it up. :) – user541686 Jan 05 '13 at 18:22
@Mehrdad: Basically `it.begin()` vs `*it.begin()` ;) – Lightness Races in Orbit Jan 05 '13 at 18:26
You mean `deque.begin()` vs. `*deque.begin()`? :P – user541686 Jan 05 '13 at 18:28
Btw so is it correct to say that deque sacrifices iterator integrity (after prepending/appending) in exchange for providing reference integrity? – user541686 Jan 05 '13 at 18:29
@Mehrdad: Yes, I do. :D As for your second comment, I'm not sure that we can infer any sort of causality between the two, but certainly there is _more_ "reference integrity" than "iterator integrity". I'm not sure I fully understand why they didn't just say that both iterators and references would be invalidated; who the heck stores refs/pointers to elements in non-contiguous containers?! – Lightness Races in Orbit Jan 05 '13 at 18:34
Ah okay. As for your question: it makes plenty of sense! You store pointers/references whenever you need access to the objects... it's not like you *have* to do pointer arithmetic with every pointer you see! :) – user541686 Jan 05 '13 at 18:41
Also, worth noting: it seems like std::deque is rather similar to [`stable_vector`](http://www.boost.org/doc/libs/1_52_0/doc/html/boost/container/stable_vector.html) in terms of its intended iterator invalidation rules... and as a bonus, that one also offers iterator stability too. Not sure why they use linked blocks for `deque` instead of just using `stable_vector`. – user541686 Jan 05 '13 at 18:42
Storing pointers or references to a container element seems like a fool's errand in the general case. – Lightness Races in Orbit Jan 05 '13 at 18:43
1

Why though? `Object &obj = deque[5]; obj.foo(); deque.push_back(Object()); obj.bar();` seems perfectly reasonable to me. – user541686 Jan 05 '13 at 18:44
@Mehrdad: I wouldn't call that "storage". It's so short-term. :) But yes okay fine... – Lightness Races in Orbit Jan 05 '13 at 18:47
It might be relevant to note that the invalidation rules are a natural implication of implementing `deque` just as the OP described. See this [answer](http://stackoverflow.com/a/39420347/3903076) to a similar question. – filipos Sep 10 '16 at 15:12
1

@Mehrdad, in comparison to `stable_vector`, `deque` sacrifices iterator integrity in exchange for not adding one more indirection. A `stable_vector` implementation has to maintain back-references into the control array along with the data, and its iterator needs to look at this back-reference to discover where the array is, instead of storing a pointer into the array directly. – filipos Sep 10 '16 at 15:22
But your citation does not answer why insertion on either end of a `deque` would invalidate all the iterators... I want to know why. ;( Can you give me a clue? Btw, [this](https://stackoverflow.com/a/47320471/5983841) is what I think how `deque` looks like. – Rick Dec 10 '19 at 03:21
@Rick You can ask a fresh question for that – Lightness Races in Orbit Dec 10 '19 at 11:12

Matthew Flaschen · Answer 2 · 2009-05-27T05:22:18.730

From the standard working draft

template < class InputIterator > void insert ( iterator position , InputIterator first , InputIterator last );

1 Effects: An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque."

So both are correct. As Josuttis indicates, insertion at the front or back doesn't invalidate references to elements of the deque, only iterators to the deque itself.

EDIT: A more up-to-date draft says essentially the same thing (section 23.2.2.3)

Jherico · Answer 3 · 2009-05-27T05:18:00.480

The SGI implementation probably uses a growable array, so if an insert causes the array to grow, the iterators pointing to the old array are invalid.

EDIT:

Looking in section 17.2.3 of The C++ Programming Language Third Edition, I don't see anything in the description of deque that indicates what operations preserve or invalidate iterators. I may be looking in the wrong spot or the behavior may be undefined.

Confusion on iterators invalidation in deque

3 Answers3

C++03

C++11

Further reading

Linked