Why does push_back or push_front invalidate a dequ

Question

As the title asks.

My understanding of a deque was that it allocated "blocks". I don't see how allocating more space invalidates iterators, and if anything, one would think that a deque's iterators would have more guarantees than a vector's, not less.

Answer 1

An iterator is not just a reference to the data. It must know how to increment, etc.

In order to support random access, implementations will have a dynamic array of pointers to the chunks. The deque iterator will point into this dynamic array. When the deque grows, a new chunk might need to be allocated. The dynamic array will grow, invalidating its iterators and, consequently, the deque's iterators.

So it is not that chunks are reallocated, but the array of pointers to these chunks can be. Indeed, as Johannes Schaub noted, references are not invalidated.

Also note that the deque's iterator guarantees are not less than the vector's, which are also invalidated when the container grows.