The speedy hybrid: std::deque<T>

Like std::vector, std::deque presents the interface of a contiguous array--it is random-access, and its elements are stored in contiguous blocks for cache-friendliness. But unlike vector, its elements are only "chunkwise" contiguous. A single deque is made up of an arbitrary number of "chunks," each containing a fixed number of elements. To insert more elements on either end of the container is cheap; to insert elements in the middle is still expensive. In memory it looks something like this:

std::deque<T> exposes all the same member functions as std::vector<T>, including an overloaded operator[]. In addition to vector's push_back and pop_back methods, deque exposes an efficient push_front and pop_front.

Notice that, when you repeatedly push_back into a vector, you eventually trigger a reallocation of the underlying array and invalidate all your iterators and all your pointers and references to elements within the container. With deque, iterator...