Will std::deque preserve pointer validity of it's contained objects?

Question

I'm looking for a container that preserves it's contained objects' positions in memory (it's pointers remain valid)

The container will grow and shrink constantly. Elements in the middle may be erased, but there's no insertions in the middle; all elements are pushed onto the back of the container. Iterator validity isn't important in this case, my only concern is that the pointers remain valid.

Is std::deque a safe and efficient option in this situation? I was previously using list, but it is allocating far too many times to be useful in this instance.

Answer 1

NO ! As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays. The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location

Answer 2

No. std::deque is necessarily implemented using chunks. Erasing in the middle of a chunk would at the very least invalidate the addresses of all subsequent elements in that chunk.

Note that iterator invalidation and pointer invalidation are generally closely connected. An iterator often is a pointer to the (node holding the) element, with proper iteration semantics added. Such iterators get invalidated because the pointer they contain is invalidated.

Answer 3

Inserting or removing elements in the middle invalidates all iterators and references.

Inserting elements at the beginning/end invalidates iterators, but does not affect references.

Removing elements at the beginning/end does not affect iterators or references, except ones pointing to the removed element, and possibly the past-the-end iterator.

http://en.cppreference.com/w/cpp/container/deque/erase

All iterators and references are invalidated, unless the erased elements are at the end or the beginning of the container, in which case only the iterators and references to the erased elements are invalidated.

http://en.cppreference.com/w/cpp/container/deque/push_back

All iterators, including the past-the-end iterator, are invalidated. No references are invalidated.

(other methods that operate on front or back elements have similar notes).