What effect does "insert" have on references to deques?

Question

I'm using a deque in one of my C++ programs, and was reading the documentation for insert on cppreference.com. Most of it made sense except this bit:

All iterators, including the past-the-end iterator, are invalidated. References are invalidated too, unless pos == begin() or pos == end(), in which case they are not invalidated.

What does this mean? Is this saying that references to the deque itself are invalidated, or references to its elements, or references to the iterators? Or something else entirely?

Here's a link the doc in question: http://en.cppreference.com/w/cpp/container/deque/insert

Answer 1

A deque is an object. It is a container, therefore it contains other objects within it's internal storage. Those are elements stored in a deque.

You can access those elements. Accessing an element is basically getting a reference back from the container. If you check it, all of the methods under element access section return a reference type.

You can make a copy of accessed element, but you can store the reference itself. T foo = d.front(); vs T& bar = d.front();. (Let d be some std::deque<T>)

A reference to a deque would be auto& ref_d = &d;. This is something else.

So:

1. What effect does “insert” have on references to deques?

None. references to d are fine.

2. What does this mean?

A deque is designed in such a way that inserting at the beginning or at the end of it does not invalidate the references to the elements which you might have already stored. Though if you insert in the middle, the elements might move in memory. Note that the bar is not touched. Precisely because it cannot be, it gets invalidated. Previously obtained reference (or iterator) doesn't point to anything meaningful anymore, thus dereferencing it is illegal.

3. Is this saying that references to the deque itself are invalidated?

Nope, as in 1.

4. or references to its elements [are invalidated]?

Yes, as in 2.

5. or references to the iterators [are invalidated]?

You again seem to confuse what is what. A reference to an iterator would be std::deque<T>::iterator& iter_ref;, if you obtain an iterator from a deque. E.g. auto iter = d.begin(); and make a reference to it iter_ref = &iter;, an insert doesn't make *iter_ref illegal, it invalidates the iterator, so *iter is illegal (or **ref_iter).

Note: I am not saying that something like std::deque<T>& ref_d or std::deque<T>::iterator& iter_ref make sense, but this is semantical meaning of "reference to a deque" and "reference to an interator".