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?

Answer 1

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.

Answer 2

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)