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