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

by

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.

More Related Contents:

  1. What is a smart pointer and when should I use one?
  2. What is move semantics?
  3. What is a lambda expression in C++11?
  4. What are rvalues, lvalues, xvalues, glvalues, and prvalues?
  5. What are the main purposes of using std::forward and which problems it solves?
  6. Why should I use a pointer rather than the object itself?
  7. What is “rvalue reference for *this”?
  8. What does T&& (double ampersand) mean in C++11?
  9. C++11 rvalues and move semantics confusion (return statement)
  10. Which kind of pointer do I use when?
  11. What is std::move(), and when should it be used?
  12. Does const mean thread-safe in C++11?
  13. Is the safe-bool idiom obsolete in C++11?
  14. Why is `std::move` named `std::move`?
  15. What are the advantages of using nullptr?
  16. Is the ‘override’ keyword just a check for a overridden virtual method?
  17. Passing shared pointers as arguments
  18. What are the main purposes of std::forward and which problems does it solve?
  19. When do extra parentheses have an effect, other than on operator precedence?
  20. When to make a type non-movable in C++11?
  21. What is std::move(), and when should it be used and does it actually move anything?
  22. Converting std::__cxx11::string to std::string
  23. C++ lambda with captures as a function pointer
  24. Why do std::shared_ptr work
  25. No matches with c++11 regex [duplicate]
  26. Pass by value vs pass by rvalue reference
  27. Get function pointer from std::function when using std::bind
  28. Lambda expressions as class template parameters
  29. Using export keyword with templates
  30. Why do we use std::function in C++ rather than the original C function pointer? [duplicate]

Leave a Comment