Deque, List, forward_list, and basic_string

Deque

Sometimes, we'll find ourselves in a situation where we need to frequently add elements to both the beginning and end of a sequence. If we are using a std::vector and need to speed up the inserts at the front, we can instead use std::deque, which is short for a 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 we can see in the following figure, all of the elements are not stored contiguously in memory, which is the case with std::vector and std::array.