Choosing the Right Container

When you write a program that stores a group of values, you have to pick a container to hold them. Many container types exist, and they are not interchangeable in every situation. Some suit sequences that are usually empty, and others suit sequences that grow large or change constantly. Choosing well means matching the container to how the data will actually be used, including the performance requirements of the program.

A very common approach is to pick a container based on what seems fast. You reason that a container is probably quick for a certain task, and you build the program around that feeling without checking. This is the misconception this article addresses: relying on intuition to decide how a container will perform.

The source is direct about this: intuition is not a reliable guide to performance, so you should measure instead. A feeling that one container is faster can be wrong for the operations your program really performs, and you will not discover that until you check. The safer habit is to treat your first guess as a candidate to test rather than as a decision.

The source supports a decision flow. You start from the expected usage of the data. A sequence that is usually empty points to forward_list. Where that expectation does not settle the question, measurement is the way to decide rather than intuition. The diagram below traces that path from a usage question to a measured choice, and the steps that follow explain each stage.

Before you can choose among the standard containers, you need a way to think about them. The standard containers fall into families, and the family tells you how elements are arranged and how you reach them. Sequential containers keep elements in a line, so position is the main way to think about them. Associative containers store elements together with keys. Unordered containers are also keyed, but they are built on hash tables and are optimized for lookup. The concept map below places the main families under the single idea of a standard container.

A sequential container arranges its elements in a line, and you think about where an element sits in that line. The source names four examples. vector<T> is a variable-size vector, so it can grow or shrink as you add or remove elements. list<T> is a doubly-linked list, so each element knows about the element before it and the element after it. forward_list<T> is a singly-linked list, which links each element only to the next one. deque<T> is a double-ended queue, built for working at both of its ends. The differences in linking and in which ends are easy to reach are the reasons you would choose one over another.

The source's specific recommendation for forward_list is tied to usage. It recommends forward_list for sequences that are usually empty. Because the source links this recommendation to how often a sequence is expected to be empty, the question to ask is how the data is actually used, not which container has the most features.

A key-based container differs from an order-based container in how you locate a stored item. In a sequential container, you think about the position of an element in the line. In an associative container, you reach a stored item by its key. The source describes set<T> as a set that holds just a key with no separate value, while map<K,V> is an associative array that pairs a key of type K with a value of type V. The multi-versions relax one rule each: a multiset<T> lets a value occur many times, and a multimap<K,V> lets a key occur many times.

The diagram below shows how a map relates each key to its value. The names and values are a generated illustration of the idea, not data taken from the source. Notice that you do not ask for item number two; you ask for the item whose key is a given name.

The unordered containers are optimized for lookup with a key, and the source notes that a key is often a string. They are implemented using hash tables. The source lists four of them: unordered_map<K,V>, unordered_multimap<K,V>, unordered_set<T>, and unordered_multiset<T>. Each mirrors a container from the associative family, with the same set-or-map and single-or-multiple distinctions, but its lookup mechanism is hashed.

The point to hold onto is the purpose. When fast lookup by key is the main job, the unordered versions are the ones the source singles out. Because they are described by their lookup mechanism rather than by their ordering, do not expect them to behave like the associative containers in every respect. The source does not describe the internal details of the hash tables, so this article does not describe them either.

Container-like types are a separate group. The source gives array<T,N>, a fixed-size array whose size is set as part of its type rather than growing as elements are added, and bitset<N>, a fixed-size collection of bits. Both are more specialized than the variable-size containers above. Knowing them helps you avoid mistaking them for the containers that grow and shrink.

Choosing a container is a performance decision that should match how the data is used. Start from the expected usage, including whether a sequence is usually empty, then move to measurement when that expectation does not settle the question. Use the family to reason about access: position for sequential containers, keys for associative and unordered containers, and specialized types only when their narrower role fits.