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 (
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
std:vectoras your default sequential container, especially as an alternative to built-in arrays
- If size is known in advance, use
std::arrayinstead of a built-in array
- If you add or remove elements frequently at both the front and back of a container, use
- Use a
std::deque) if you need to insert/remove elements in the middle of the sequence
- Do not use
std::listif you need random access to objects
std::listif your system uses a cache
std::stringis 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,
- If you need multiple entries for the same key, use
std::unordered_multimap, or if element order matters,
- 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::stringstore memory contiguously and are compatible with C-style APIs
std::dequeallocates memory in chunks
std::listallocates memory by node
A Note on
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
Next week we will take a detailed look at some of the tradeoffs for each sequential and associative container.