Deque, List, forward_list, and basic_string
Learn about different data structures and their visual representations.
We'll cover the following...
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.
Press + to interact
A possible layout of the double-ended queue
list and forward_list
The std::list is a doubly linked ...