Sometimes you need to add elements to the end and the beginning of a sequence. If you are using a vector and need to speed up the inserts at the front, you can instead use std::deque, short for double-ended queue. std::deque is usually implemented as a collection of fixed-size arrays, which makes it possible to access elements by their index in constant time. However, as can be seen in the following image, all elements are not stored contiguously in memory, which is the case with vector and array:
