Search code examples
c++c++11c++-faq

How can I efficiently select a Standard Library container in C++11?

There's a well known image (cheat sheet) called "C++ Container choice". It's a flow chart to choose the best container for the wanted usage.

Does anybody know if there's already a C++11 version of it?

This is the previous one: eC++ Container choice

Solution

  • Not that I know of, however it can be done textually I guess. Also, the chart is slightly off, because list is not such a good container in general, and neither is forward_list. Both lists are very specialized containers for niche applications.

    To build such a chart, you just need two simple guidelines:

    • Choose for semantics first
    • When several choices are available, go for the simplest

    Worrying about performance is usually useless at first. The big O considerations only really kick in when you start handling a few thousands (or more) of items.

    There are two big categories of containers:

    • Associative containers: they have a find operation
    • Simple Sequence containers

    and then you can build several adapters on top of them: stack, queue, priority_queue. I will leave the adapters out here, they are sufficiently specialized to be recognizable.

    Question 1: Associative ?

    • If you need to easily search by one key, then you need an associative container
    • If you need to have the elements sorted, then you need an ordered associative container
    • Otherwise, jump to the question 2.

    Question 1.1: Ordered ?

    • If you do not need a specific order, use an unordered_ container, otherwise use its traditional ordered counterpart.

    Question 1.2: Separate Key ?

    • If the key is separate from the value, use a map, otherwise use a set

    Question 1.3: Duplicates ?

    • If you want to keep duplicates, use a multi, otherwise do not.

    Example:

    Suppose that I have several persons with a unique ID associated to them, and I would like to retrieve a person data from its ID as simply as possible.

    1. I want a find function, thus an associative container

    1.1. I couldn't care less about order, thus an unordered_ container

    1.2. My key (ID) is separate from the value it is associated with, thus a map

    1.3. The ID is unique, thus no duplicate should creep in.

    The final answer is: std::unordered_map<ID, PersonData>.

    Question 2: Memory stable ?

    • If the elements should be stable in memory (ie, they should not move around when the container itself is modified), then use some list
    • Otherwise, jump to question 3.

    Question 2.1: Which ?

    • Settle for a list; a forward_list is only useful for lesser memory footprint.

    Question 3: Dynamically sized ?

    • If the container has a known size (at compilation time), and this size will not be altered during the course of the program, and the elements are default constructible or you can provide a full initialization list (using the { ... } syntax), then use an array. It replaces the traditional C-array, but with convenient functions.
    • Otherwise, jump to question 4.

    Question 4: Double-ended ?

    • If you wish to be able to remove items from both the front and back, then use a deque, otherwise use a vector.

    You will note that, by default, unless you need an associative container, your choice will be a vector. It turns out it is also Sutter and Stroustrup's recommendation.