Choosing the Right Container: Sequential Containers

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 when you care that your memory is stored sequentially or when you want to access the data sequentially. Here's a quick summary of the sequential containers:

  • std::array - static contiguous array, providing fast access but with a fixed number of elements
  • std::vector - dynamic contiguous array, providing fast access but costly insertions/deletions
  • std::deque - double-ended queue providing efficient insertion/deletion at the front and back of a sequence
  • std::list and std::forward_list - linked list data structures, allowing for efficient insertion/deletion into the middle of a sequence.

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 structure
  • queue - adapter providing a FIFO data structure
  • priority_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 (not std::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 over std::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, and std::string store memory contiguously and are compatible with C-style APIs
  • std::deque allocates memory in chunks
  • std::list allocates memory by node

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 a std::deque invalidates all iterators and references to its elements

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