An Overview of C++ STL Containers

Updated: 2018-11-05

Previously we've looked at the C++ array and vector containers and saw why those containers are better than standard C-style arrays. We also learned that containers can take advantage of idioms such as the SBRM design pattern and range-based for loops.

Now that we've looked at two containers in depth (as well as the pseudo-container std::string, I'd like to provide an overview of the remaining C++ containers.

The Standard Containers

The containers library is a collection of templates and algorithms that implement the common data structures that we work with as programmers. A container is an object that stores a collection of elements (i.e. other objects). Each of these containers manages the storage space for their elements and provides access to each element through iterators and/or member functions.

The standard containers implement structures that are commonly used in our programs, such as:

  • dynamic arrays
  • queues
  • stacks
  • linked lists
  • trees
  • associative sets

I love the STL containers, as they eliminate an entire set of boilerplate code that I re-implement on every project I work on. The container library also benefits from having a standardized interface for member functions. These standardized interfaces reduce your memory burden and allow containers to be used with STL algorithms.

The C++ container library categorizes containers into four types:

  • Sequence containers
  • Sequence container adapters
  • Associative containers
  • Unordered associative containers

Let's dive into each of these categories.

Sequence Containers

Sequence containers are used for data structures that store objects of the same type in a linear manner.

The STL SequenceContainer types are:

  • array represents a static contiguous array
  • vector represents a dynamic contiguous array
  • forward_list represents a singly-linked list
  • list represents a doubly-linked list
  • deque represents a double-ended queue, where elements can be added to the front or back of the queue.

While std::string is not included in most container lists, it does in fact meet the requirements of a SequenceContainer.

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). These container adapters encapsulate the underlying container type and limit the user interfaces accordingly.

Let's consider std::stack. std::stack is a container that enforces a LIFO-type data structure. Here's the declaration of std::stack:

    class T,
    class Container = std::deque<T>
> class stack;

Notice that Container defaults to wrapping a std::deque<T>. You can actually change the type of underlying container to another STL SequenceContainer or your own custom container. The container you specify has to meet the following requirements:

The STL containers std::vector, std::deque, and std::list all meet these requirements and can be used for underlying storage.

The standard container adapters are:

  • stack provides an LIFO data structure
  • queue provides a FIFO data structure
  • priority_queue provides a priority queue, which allows for constant-time lookup of the largest element (by default)

Associative Containers

Associative containers provide sorted data structures that provide a fast lookup (O(log n) time) using keys.

The STL AssociativeContainer types are can be divided in two ways: containers which require unique keys, and those which allow multiple entries using the same key.

  • Keys are unique
    • set is a collection of unique keys, sorted by keys
    • map is a collection of key-value pairs, sorted by keys
    • set and map are typically implemented using red-black trees
  • Multiple entries for the same key are permitted
    • multiset is a collection of keys, sorted by keys
    • multimap is a collection of key-value pairs, sorted by keys

Each of the associative containers can specify a comparison function during declaration. Let's take a look at the definition of std::set:

    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

The default comparison function for associative containers is std::less. This comparison function is used to sort keys. If you prefer a different sorting or allocation scheme, you should override these functions during declaration.

Unordered Associative Containers

Unordered associative containers provide unsorted data structures that can be accessed using a hash. Access times are O(n) in the worst-case, but much faster than linear time for most operations.

For all STL UnorderedAssociativeContainer types, a hashed key is used to access the data. Similar to the AssociativeContainer, the standard types are split between those that require unique keys, and those that do not:

  • Keys are unique
  • Multiple entires for the same key are permitted

Like with the other container types, UnorderedAssociativeContainer types can have details overridden. Let's look at std::unordered_set:

    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

You can override the hashing function, the key comparison function, and the allocator. I don't care to improve up on the STL hashing functionality, so I usually leave these details alone. However, if you want to override any of the default functions, you must do it during declaration.

Reasons to Use Standard Containers

Standard containers eliminate much of the boilerplate code that I am required to write when bringing up a new system for a new client. They simplify development and should be utilized instead of custom implementations for four simple reasons:

  1. STL containers are implemented correctly, and I will not need to spend time debugging the containers
  2. STL containers are fast, and likely more efficient than anything I'm going to implement on my own
  3. STL containers share common interfaces, making it quite simple to utilize different containers without looking up member function definitions
  4. STL containers are well-documented and easily understood by other developers, improving the understandability and maintainability of our projects

By utilizing STL containers, I can become a more productive developer. I'm much more confident in the reliability of my code, and I can trust that other developers will have an easier time maintaining my code in the future.

Standard Container Thread Safety

I want to share with you some relevant points regarding container thread safety, as many embedded systems will likely require sharing objects across threads. The following general thread-safety rules apply:

  • All container functions are safe to be called concurrently on different objects of the same container type (i.e. it is safe to use two different std::vector instances on two different threads
  • All const member functions can be called concurrently by different threads
  • Containers can be safely read from multiple threads if no thread is making asynchronous writes
  • Different elements in the same container can be modified concurrently, except for the elements of std::vector<bool>.
  • If an object is written to by one thread and read by other threads, the object must be protected
  • In general, iterator operations read from a container, but do not modify it, so they are thread-safe
    • Container operations that invalidate iterators are NOT thread-safe, as they modify the container

The most important detail to keep in mind: if you are modifying the container in multiple threads, you will need to protect that container to prevent concurrent access. For more information using containers in a thread-safe way, see Implementing a Thread-Safe Queue using Condition Variable

Also, Boost provides a selection of lock-free container alternatives which you can consider for multi-threaded use cases.

Further Reading

I've aimed to provide a summary of the containers available in C++. In later articles, we will be using these containers to build up our embedded system. I recommend reading the documentation for any containers that immediately interest you.

Change Log

  • 20181026:
    • Updated notes on thread-safety for unordered associative containers. Operator [] and at() are not thread safe due to the possibility for re-indexing to invalidate all iterators.
  • 20181105:
    • Further improved notes on thread-safety of containers
    • Updated cppreference links: "concept" URLs were updated to "named_req"