Choosing the Right STL Container: General Rules of Thumb

In a previous article, I provided an overview of the C++ standard container types. The variety of containers and the subtle differences between them can be overwhelming, especially to new developers. Let’s take a look at some quick guidelines we can use to select the right container.

Think About Your Intentions

The most important aspect to consider when selecting a container type is what you intend to do with your object. You can learn a lot about the optimal usage of a container by reviewing which operations it supports and which operations are disabled.

Consider the interfaces you intend to utilize. Do you need a last-in-first-out (LIFO) data structure? Using a std::stack restricts the interfaces that you can use and clearly communicates your intentions to other developers and to future maintainers of your code. Utilizing a bare std::deque instead of a std::stack introduces the chance that future maintainers think operating on the front of the deque is acceptable.

However, the decision for which container to use does not only depend on the functionality offered by the container. You will also need to be aware of the efficiency of each type of container and member functions. This is especially true for sequence containers (vector, list, deque), which have various complexity tradeoffs with regards to element insertion, removal, and access.

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 size is known in advance, use std::array instead of a built-in array
    • 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
  • Use associative containers when you need to access elements by key
    • For key/value pair, default to std::unordered_map, or if element order matters, std::map
    • If you need multiple entries for the same key, use std::unordered_multimap, or if element order matters, std::multimap

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

A Note on std::list

After watching this talk by Bjarne Stroustrup (recommended in the comments), I was quite surprised to learn how inefficient linked lists are when compared to a std::vector on systems with caching. Since the memory is not stored contiguously, using a std::list increases the likelihood of cache misses significantly. Cache misses will cause poorer performance when compared to std::vector and its contiguous memory storage.

Many embedded systems do not utilize the cache, so in those situations std::list is still an acceptable choice. If you are relying on caching, consider std::vector instead of std::list.

Up Next

Next week we will take a detailed look at some of the tradeoffs for each sequential and associative container.

Further Reading

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

6 Replies to “Choosing the Right STL Container: General Rules of Thumb”

  1. There is one caveat about that: The reason that the performance drops is because of cache misses.
    Since many embedded systems doesn’t have a cache as such you will not have an extra penalty for chasing the pointer.
    You will of course have the added cost of loading the pointer and some architectures do have optimisations for accessing contiguous memory, but it will not be as bad as on a PC.

    1. I would not say that every embedded system has no cache – e.g. A53 has cache and MMU:) Modern embedded systems rapidly became more and more complicated.

  2. Use a std::list (not std::deque) if you need to insert/remove elements in the middle of the sequence

    Why not? I heard that deque also allows that in the middle. Right now I am in the middle of choosing between lists and deques for my needs (FIFO insertion removal and some removal in the middle, search of elements)

    1. Hi Kansai,

      The reason is iterator invalidation, in the event that you are iterating over a list/deque or holding a handle to a single element’s iterator. When you insert/remove on a deque, the iterators are invalidated:

      All iterators, including the past-the-end iterator, are invalidated. References are invalidated too, unless pos == begin() or pos == end(), in which case they are not invalidate

      For a list, “No iterators or references are invalidated.”

Share Your Thoughts

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