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
(notstd::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
overstd::list
if your system uses a cache std::string
is almost always better than a C-string
- Use
- 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
- For key/value pair, default to
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
, andstd::string
store memory contiguously and are compatible with C-style APIsstd::deque
allocates memory in chunksstd::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
- Overview of C++ Containers
- ISO C++ FAQ: Containers
- C++ STL’s: When to use which STL
- Expert’s Exchange: Which STL Container to Use
- SlideShare: How to choose best containers in STL (C++)
- StackOverflow: In Which Scenario Do I Use a Particular STL Container?
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
Bjarne give a talk about using list vs vector: https://www.youtube.com/watch?v=YQs6IC-vgmo
It looks like… We don’t need a list at all.
That was a great talk, and I did not expect such a great difference in performance. Thanks again for sharing Wojciech!
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.
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.
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)
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:
For a list, “No iterators or references are invalidated.”