An Overview of C++ STL Containers

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.

Table of Contents:

  1. The Standard Containers
    1. Sequence Containers
    2. Container Adapters
    3. Associative Containers
    4. Unordered Associative Containers
  2. Reasons to Use Standard Containers
  3. Standard Container Thread Safety
  4. Further Reading

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:

template<
    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:

template<
    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:

template<
    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.

Major Revisions

  • 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”

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

Migrating from C to C++ Articles

11 Replies to “An Overview of C++ STL Containers”

  1. Would you please comment on whether "operator []" on an unordered associative container is thread-safe (may be executed concurrently) with other container operations?

    Your list indicates:
    Operator [] is thread-safe for sequence containers, unordered associative containers, and container adapters.
    and
    Container operations that invalidate iterators are NOT thread-safe, as they modify the container

    but this reference:
    https://en.cppreference.com/w/cpp/container/unordered_map/operator_at
    says that:
    If an insertion occurs and results in a rehashing of the container, all iterators are invalidated.
    That is, operator [] on std::unordered_map may invalidate iterators, and thus would seem not to be thread safe.

    1. Hi Bill,

      You are correct in your assessment, and as such the possibility of rehashing would make unordered_map not thread safe.

      Whether that is a practical concern or not I can’t say – perhaps for specific use cases with known maximum sizes this would be "safe" to use. I cannot advise it in general though if there is a rehashing possibility.

      Thanks for pointing this out, I will get this article updated.

    1. Thanks for the feedback Nachiket. I’ve clarified the section; let me know what you think.

      My original logic for calling those functions out is that they do not modify the container and thus are in fact generally safe to use from multiple threads. The exception is that they are not safe against data races. As such, I agree with you calling it misleading.

  2. In my application PerfectTIN, I use map<int,foo> as if it were vector (i.e. the keys are contiguous integers; the reason is that three foo types point to each other, and the pointers would be invalidated when the vectors are moved when resized). I found it necessary to lock the elements (I used spatial contiguity to use many fewer locks than the possibly millions of elements in the container) and additionally define a readers-writer lock (shared mutex) for the map itself. Inserting or deleting an element in the map counts as writing to it; accessing any element (including writing to it) and counting the elements count as reading from it. Something similar should apply to other container classes.

  3. “map is a collection of key-value pairs, sorted by keys”

    Was this supposed to say UNIQUE key-value pairs? This definition is identical to the one for multimap just below it.

  4. I’m surprised about the 100kB increase, but that might also be because it pulls in a lot of functionality that is otherwise excluded (e.g, Malloc). We have successfully used the STL in embedded systems without this problem, but we used a custom libc in that situation.

    For embedded projects, we typically recommend the Embedded Template Library, which provides static memory equivalents for the STL containers (and many other useful features).

Share Your Thoughts

This site uses Akismet to reduce spam. Learn how your comment data is processed.