Sequential Containers in C++

Before you write a program that stores a group of values, you have to decide what kind of collection you need. Should the items stay in the order you added them? Should you look an item up by a name or label? Should duplicates be allowed? The C++ standard library answers these questions with a set of ready-made container types, so you do not have to build each storage structure yourself. The library is designed around the idea that you pick the container that best fits the needs of your application.

This article walks through the containers by asking what each one is good at. The goal is to turn a list of names into a set of choices you can reason about. Keep three questions in mind as you read: does the container keep elements in a sequence, does it store elements under keys, and does it use hashed lookup?

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 sequence, so position is the main way to think about them. Associative containers store elements together with keys, so you reach a stored item by its key. Unordered containers are also keyed, but they are built on hash tables and are optimized for lookup, which is often done with a string key.

Read the diagram from top to bottom. The root is the idea of a standard container, and the three families sit beneath it. Each family then contains the specific containers the source names. The unordered family mirrors the associative family in its set-or-map and single-or-multiple distinctions, but its lookup mechanism is different. The rest of this article explains each family in turn, starting with the one whose elements are reached by position.

Trace what happens when you want an element from a sequential container. A sequential container arranges its elements in a line, so you think about where an element sits in that line. Suppose the container holds four scores in order. To get the score that sits at position 2, you name that position. You do not search the values to find the one you want.

The highlighted cell is the one the lookup asks for. Its position, 2, identifies it. The values in the picture are invented for illustration. The source does not give example scores. The point of the picture is that a position-based lookup answers the question which place in the line, not which value.

The source names four sequential containers, and each one differs in how it is built and which ends are easy to reach. The vector<T> is described as a variable-size vector, so it can grow or shrink as you add or remove elements. The list<T> is a doubly-linked list, so each element knows about the element before it and the element after it. The forward_list<T> is a singly-linked list, which links each element only to the next one. The deque<T> is a double-ended queue, so it is built for working at both of its ends.

The differences in linking and in the ends that are easy to reach are the reasons you would choose one over another. The source does not compare their speed or memory use, so this article does not make those claims. Choose by asking which kind of growth or end access your program needs.

An associative container stores elements that are reached through keys. Instead of asking for the element at a position, you give the container a key and receive the stored item for that key. The source describes set<T> as a set that holds just a key with no separate value. The map<K,V> is an associative array that pairs a key of type K with a value of type V.

The keys and values in this picture are a generated illustration of the idea, not data taken from the source. The picture shows that you find a value by its key, and that the key itself is the handle you use to store and retrieve data.

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. So if the same key may appear more than once, a multimap is the family member the source points you to, while a plain map keeps one value per key.

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 one mirrors a container from the associative family, with the same set-or-map and single-or-multiple distinctions, but the lookup mechanism is a hashed one.

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. When you need the stored order or the sorted keys, the associative family is the one to consider, since the unordered family is described by its lookup mechanism rather than by ordering.

The standard library also provides container adaptors, named queue<T>, stack<T>, and priority_queue<T>. An adaptor is a class that provides a different interface to a container. It does not present the operations of a general-purpose collection. Instead, it presents a narrower set of operations suited to a particular access pattern. The source tells you the adaptors exist and gives their names, and it advises you to look them up when you need them.

Some types in the standard library behave like containers without fitting neatly into the three families or the adaptors. The source gives two examples. The array<T,N> is a fixed-size array, so its size is set as part of its type rather than growing as elements are added. The bitset<N> is a fixed-size collection of bits. Both are described as more specialized container-like types, and they are useful to know about so that you do not mistake them for the variable-size containers above.