Associative Containers and Maps in C++

Before you write a program that stores a collection 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 items 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.

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.

The source describes map<K,V> as an associative array that pairs a key of type K with a value of type V. Each stored entry is therefore a pair: one key and the value attached to it. To trace what a map holds, follow the entries one at a time and ask, for each key, what value it is paired with. The keys and values in the picture below are a generated illustration of the idea, not data taken from the source.

The main difference between families is what you use to find an element. In a sequential container you think about where an element sits in the line. In an associative or unordered container you give the container a key and ask for the element that carries it. The same question, which item do I want, is answered by a different piece of information in each case.

Notice that the unordered family is also keyed. What sets it apart is the lookup mechanism, since the source states that these containers are implemented using hash tables. The source gives the stated purpose, which is fast lookup by key, and it does not describe the internal details of those hash tables, so this article does not describe them either.

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, and the differences between them come from how they are linked and which ends are easy to reach.

Both of the keyed families come in set and map forms, and in multi-versions that relax one rule each. Choosing among them is a question of whether you need a key with a value, a key alone, or permission for repeats. The two subsections below separate the associative family from the unordered family, because the source treats their purpose and mechanism differently.

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, gives their names, and advises you to look them up when you need them.

Some types behave like containers without fitting neatly into the three families or the adaptors. 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. Knowing about these prevents you from mistaking them for the variable-size containers described earlier.

The example below shows the key-value idea in code. A std::map<std::string, int> pairs each string key with an int value, and the lookup uses the key rather than a position. This snippet is an illustrative example written for this article, not code from the source.