Deque, List, forward_list, and basic_string
Explore the characteristics and performance implications of key C++ standard library data structures including std::deque for double-ended queues, std::list and std::forward_list for linked lists, and std::basic_string for string handling. Understand their memory layouts, iteration costs, and when to choose each container type for high-performance code.
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.
list and forward_list
The std::list is a doubly linked ...