Unordered Containers and Hash Tables 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? These questions shape the whole design, and the C++ standard library answers them with a set of ready-made container types. 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, so that a list of names becomes a set of choices you can reason about. The most useful question to ask first is how you intend to reach an element: by its position in a line, or by a key that identifies it.

Start with the behavior of a keyed container. You store a value under a key, and later you give the same key to retrieve that value. The diagram below traces this for a small generated example: a container that maps fruit names to counts. Each key appears once, and each key leads to exactly one value. The keys and values here are an illustration of the idea and are not data from the source.

The diagram shows what a lookup means: you supply the key pear and receive 7. The source does not describe how an unordered container internally arrives at the place where a value is stored, so this article does not describe that step either. What you can rely on is the stated purpose: unordered containers are built on hash tables and are optimized for lookup, often with a string key.

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. The diagram places the main families under the single idea of a standard container.

Now trace what changes when you finish storing data and go to find it. In an order-based sequential container you locate an element by where it sits in the line. In a key-based container you locate an element by the key that was attached to it when it was stored. The comparison below sets these two ways of reaching data side by side.

Two things follow from the source's description. A key-based container is the right choice when your question is which value belongs to this name or label. An order-based container is the right choice when your question is what comes first, what comes next, or what is at a given place in the line. The source's description of unordered containers stresses lookup rather than ordering, so do not assume they organize elements the way a sequence does.

The keyed families come in matching pairs. Each associative container has an unordered counterpart with the same set-or-map and single-or-multiple distinctions. The table below lines these up so you can see which rule each name relaxes.

When you choose among these, ask two separate questions. First, does each item need a separate value, or is the key the whole item? Second, may the same key or value appear more than once? The family question, whether you want associative or unordered, is a third question that depends on whether fast lookup by key is your main job.

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 adaptors sit alongside the containers as a distinct category, each offering its own interface to underlying storage. 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. Both are described as specialized container-like types. They are useful to know about so that you do not mistake them for the variable-size containers above.