In a previous article, I provided an overview of the C++ standard container types. We’ve also taken a look at general rules of thumb for selecting a container, as well as a more detailed look at rules of thumb for associative containers. Let’s take a look at guidelines we can use to select the right sequential container.
Sequential Container Review
SequenceContainers
should be used if you care about your memory being stored sequentially (use std::vector
or `std::array) or when you want to access data sequentially (all containers).
Here’s a quick summary of the sequential containers:
std::array
– static contiguous array, providing fast access but with a fixed number of elementsstd::vector
– dynamic contiguous array, providing fast access but costly insertions/deletionsstd::deque
– double-ended queue providing efficient insertion/deletion at the front and back of a sequencestd::list
andstd::forward_list
– linked list data structures, allowing for efficient insertion/deletion into the middle of a sequence
I want to re-iterate this point: while std::deque
, std::list
, and std::forward_list
are SequenceContainers
, their memory is not allocated in a contiguous manner.
Container Adapters
Container adapters are a special type of container class. They are not full container classes on their own, but wrappers around other container types (such as a vector
, deque
, or list
). The container adapters encapsulate the underlying container type and limit the user interfaces accordingly.
The standard container adapters are:
stack
– adapter providing an LIFO data structurequeue
– adapter providing a FIFO data structurepriority_queue
– adapter providing a priority queue, which allows for constant-time lookup of the largest element (by default)
General Rules of Thumb
There are some general rules of thumb that will guide you through most situations:
- Use sequential containers when you need to access elements by position
- Use
std:vector
as your default sequential container, especially as an alternative to built-in arrays - If you add or remove elements frequently at both the front and back of a container, use
std::deque
- Use a
std::list
(notstd::deque
) if you need to insert/remove elements in the middle of the sequence - Do not use
std::list
if you need random access to objects - Prefer
std::vector
overstd::list
if your system uses a cache std::string
is almost always better than a C-string- If you need to limit the interfaces, use a container adapter
Memory allocation may also be a factor in your decision. Here are the general rules of thumb for how the different sequential containers are storing memory:
std:vector
,std::array
, andstd::string
store memory contiguously and are compatible with C-style APIsstd::deque
allocates memory in chunksstd::list
allocates memory by node
If you are worried about cache performance, it is best to stick to std::vector
or std::array
since memory is allocated in a contiguous manner.
Container Adapters
Container adapters take a container type and limit the interfaces to provide a specific data type. These containers will exhibit the characteristics of their underlying data structures, so you may not always want to utilize the default underlying container.
Generally you will want to:
- Use
std::stack
when you need a LIFO data structure - Use
std::queue
when you need a FIFO data structure
std::priority
queue is a bit more complex. The container utilizes a Compare
function (std::less
by default) and provides constant-time lookup of the largest (by default) element in the container. This structure is useful for implementing things like an ISR handler queue, where you always want to be working through the highest priority interrupt in the queue. This feature comes with an increased cost in element insertion.
Container Analysis
Let’s take a look at the various sequential containers. Since the container adapters are simply add-ons to the primary sequential containers, we will not be evaluating those below. Select the underlying container appropriately for your use case, and use the adapter to implement the specific interface you need.
std::vector
Your default sequential containers should be a std::vector
. Generally, std::vector
will provide you with the right balance of performance and speed. The std::vector
container is similar to a C-style array that can grow or shrink during runtime. The underlying buffer is stored contiguously and is guaranteed to be compatible with C-style arrays.
Consider using a std::vector
if:
- You need your data to be stored contiguously in memory
- Especially useful for C-style API compatibility
- You do not know the size at compile time
- You need efficient random access to your elements (
O(1)
) - You will be adding and removing elements from the end
- You want to iterate over the elements in any order
Avoid using a std::vector
if:
- You will frequently add or remove elements to the front or middle of the sequence
- The size of your buffer is constant and known in advance (prefer
std::array
)
Be aware of the specialization of std::vector<bool>
: Since C++98, std::vector<bool>
has been specialized such that each element only occupies one bit. When accessing individual boolean elements, the operators return a copy of a bool that is constructed with the value of that bit.
std::array
The std::array
container is the most like a built-in array, but offering extra features such as bounds checking and automatic memory management. Unlike std::vector
, the size of std::array
is fixed and cannot change during runtime.
Consider using a std::array
if:
- You need your data to be stored contiguously in memory
- Especially useful for C-style API compatibility
- The size of your array is known in advance
- You need efficient random access to your elements (
O(1)
) - You want to iterate over the elements in any order
Avoid using a std::array
if:
- You need to insert or remove elements
- You don’t know the size of your array at compile time
- You need to be able to resize your array dynamically
std::deque
The std::deque
container gets its name from a shortening of “double ended queue”. The std::deque
container is most efficient when appending items to the front or back of a queue. Unlike std::vector
, std::deque
does not provide a mechanism to reserve a buffer. The underlying buffer is also not guaranteed to be compatible with C-style array APIs.
Consider using std::deque
if:
- You need to insert new elements at both the front and back of a sequence (e.g. in a scheduler)
- You need efficient random access to your elements (
O(1)
) - You want the internal buffer to automatically shrink when elements are removed
- You want to iterate over the elements in any order
Avoid using std::deque
if:
- You need to maintain compatibility with C-style APIs
- You need to reserve memory ahead of time
- You need to frequently insert or remove elements from the middle of the sequence
- Calling
insert
in the middle of astd::deque
invalidates all iterators and references to its elements
- Calling
std::list
The std::list
and std::forward_list
containers implement linked list data structures. Where std::list
provides a doubly-linked list, the std::forward_list
only contains a pointer to the next object. Unlike the other sequential containers, the list types do not provide efficient random access to elements. Each element must be traversed in order.
Consider using std::list
if:
- You need to store many items but the number is unknown
- You need to insert or remove new elements from any position in the sequence
- You do not need efficient access to random elements
- You want the ability to move elements or sets of elements within the container or between different containers
- You want to implement a node-wise memory allocation scheme
Avoid using std::list
if:
- You need to maintain compatibility with C-style APIs
- You need efficient access to random elements
- Your system utilizes a cache (prefer
std::vector
for reduced cache misses) - The size of your data is known in advance and can be managed by a
std::vector
Up Next
That wraps up my general overview of C++ STL containers. In future articles, I will be using these STL containers to implement embedded systems programming constructs.
Further Reading
- Embedded Artistry Container Series
- C++ References
- Other References:
Using C++ Without the Heap
Want to use C++, but worried about how much it relies on dynamic memory allocations? Our course provides a hands-on approach for learning a diverse set of patterns, tools, and techniques for writing C++ code that never uses the heap.
Learn More on the Course Page
really stellar article! It would be useful to add under the intro to sequential containers that memory allocation is not contiguous for list and deque, but is cont. for vectors / arrays. Newcomers may confuse / gloss-over the detail that sequential containers only refer to data being accessed sequentially typically for these containers, but for performance reasons (cache miss etc.), it is crucial to understand that the memory is not contiguous for lists and deques.
Great point, I will get this article updated.