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:
Overall, for insertions, the vector and deque are the fastest for small types and the list is the fastest for the very large types.
vector will outperform list for almost every use case.
The Containers library is a generic collection of class templates and algorithms that allow programmers to easily implement common data structures like queues, lists and stacks.
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:
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:
find
operationand 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 ?
Question 1.1: Ordered ?
unordered_
container, otherwise use its traditional ordered counterpart.Question 1.2: Separate Key ?
map
, otherwise use a set
Question 1.3: Duplicates ?
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.
find
function, thus an associative container1.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 ?
list
Question 2.1: Which ?
list
; a forward_list
is only useful for lesser memory footprint.Question 3: Dynamically sized ?
{ ... }
syntax), then use an array
. It replaces the traditional C-array, but with convenient functions.Question 4: Double-ended ?
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.
I like Matthieu's answer, but I'm going to restate the flowchart as this:
By default, if you need a container of stuff, use std::vector
. Thus, every other container is only justified by providing some functionality alternative to std::vector
.
std::vector
requires that its contents are move-constructible, since it needs to be able to shuffle the items around. This is not a terrible burden to place on the contents (note that default constructors are not required, thanks to emplace
and so forth). However, most of the other containers don't require any particular constructor (again, thanks to emplace
). So if you have an object where you absolutely cannot implement a move constructor, then you will have to pick something else.
A std::deque
would be the general replacement, having many of the properties of std::vector
, but you can only insert at either ends of the deque. Inserts in the middle require moving. A std::list
places no requirement on its contents.
std::vector<bool>
is... not. Well, it is standard. But it's not a vector
in the usual sense, as operations that std::vector
normally allows are forbidden. And it most certainly does not contain bool
s.
Therefore, if you need real vector
behavior from a container of bool
s, you're not going to get it from std::vector<bool>
. So you'll have to make due with a std::deque<bool>
.
If you need to find elements in a container, and the search tag can't just be an index, then you may need to abandon std::vector
in favor of set
and map
. Note the key word "may"; a sorted std::vector
is sometimes a reasonable alternative. Or Boost.Container's flat_set/map
, which implements a sorted std::vector
.
There are now four variations of these, each with their own needs.
map
when the search tag is not the same thing as the item you're looking for itself. Otherwise use a set
.unordered
when you have a lot of items in the container and search performance absolutely needs to be O(1)
, rather than O(logn)
.multi
if you need multiple items to have the same search tag.If you need a container of items to always be sorted based on a particular comparison operation, you can use a set
. Or a multi_set
if you need multiple items to have the same value.
Or you can use a sorted std::vector
, but you'll have to keep it sorted.
When iterators and references are invalidated is sometimes a concern. If you need a list of items, such that you have iterators/pointers to those items in various other places, then std::vector
's approach to invalidation may not be appropriate. Any insertion operation may cause invalidation, depending on the current size and capacity.
std::list
offers a firm guarantee: an iterator and its associated references/pointers are only invalidated when the item itself is removed from the container. std::forward_list
is there if memory is a serious concern.
If that's too strong a guarantee, std::deque
offers a weaker but useful guarantee. Invalidation results from insertions in the middle, but insertions at the head or tail causes only invalidation of iterators, not pointers/references to items in the container.
std::vector
only provides cheap insertion at the end (and even then, it becomes expensive if you blow capacity).
std::list
is expensive in terms of performance (each newly inserted item costs a memory allocation), but it is consistent. It also offers the occasionally indispensable ability to shuffle items around for virtually no performance cost, as well as to trade items with other std::list
containers of the same type at no loss of performance. If you need to shuffle things around a lot, use std::list
.
std::deque
provides constant-time insertion/removal at the head and tail, but insertion in the middle can be fairly expensive. So if you need to add/remove things from the front as well as the back, std::deque
might be what you need.
It should be noted that, thanks to move semantics, std::vector
insertion performance may not be as bad as it used to be. Some implementations implemented a form of move semantic-based item copying (the so-called "swaptimization"), but now that moving is part of the language, it's mandated by the standard.
std::array
is a fine container if you want the fewest possible dynamic allocations. It's just a wrapper around a C-array; this means that its size must be known at compile-time. If you can live with that, then use std::array
.
That being said, using std::vector
and reserve
ing a size would work just as well for a bounded std::vector
. This way, the actual size can vary, and you only get one memory allocation (unless you blow the capacity).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With