Choosing a Container for Lookup

Suppose you already store your data in a map and you ask it to find one element. How much work does that search take? The answer depends on the container you chose, and choosing well is what this article is about. The source answers the question for a map directly: the cost of a map lookup is $O(\log(n))$, where $n$ is the number of elements in the map. The source calls this pretty good. The rest of this article explains why it is good, and when a different kind of container can do better.

A map finds elements by comparison. It uses an ordering function, such as the less-than operator, to decide which way to move as it searches. At each step, the map compares the key it is looking for against an element it has reached, and the result of that comparison tells it where the element must be if it exists at all. Its search is therefore a sequence of decisions, each one narrowing the set of places that could still hold the answer.

Read the picture below from top to bottom. Each step starts with a candidate set of elements and ends with a smaller one. The number on each node is the count of candidates still in play. The diagram shows the idea of repeated narrowing: the search space shrinks at every comparison, so the number of steps needed is far smaller than the number of elements.

A cost written as $O(\log(n))$ grows with the size of the collection, but much more slowly than the size itself. The source makes this concrete with a single example: for a map with 1,000,000 elements, one lookup performs only about 20 comparisons and indirections. The logarithm is the reason the number stays small. Each comparison eliminates a large share of the remaining candidates, so the count of steps rises only as the logarithm of the element count. In the source's example, $\log_2(1{,}000{,}000)$ is about 20, which matches the stated figure.

The two containers differ in the route a lookup takes. Both routes start from a key and end at an element, but the middle step is different. A map's route passes through comparisons against an ordering, which is why its cost is logarithmic. A hashed lookup avoids comparison using an ordering function. The source states that in many cases we can do better by using a hashed lookup instead, so this is the central idea of the article: the map's cost comes from relying on ordering, and a hashed route takes a different path that can beat that cost in many situations.

Notice what the diagram does not show. The source does not describe how a hashed container arranges its elements internally, so the comparison here focuses only on the lookup route. One container searches by comparing against an ordering, and the other avoids that ordering requirement entirely. Do not read the hashed route as a guarantee: the source calls the faster result a tendency, not a promise.

The standard-library hashed containers are called unordered because they do not require an ordering function. The name describes a requirement, not a messy or random layout. A map needs an ordering function such as the less-than operator to decide how its elements relate and how to search them. An unordered_map does not need that ordering function at all, so the name points to the absence of that requirement rather than to some disorder that a programmer must cope with.

The source gives a clear decision rule. If the goal is efficient lookup, consider a hashed lookup as an alternative to comparison using an ordering function, since it can be better in many cases. A hashed container is a reasonable choice when your main operation is finding an element by its key. A map remains the right tool when the ordering itself matters to your program, because a map uses an ordering function to decide how its elements relate. The source's own description of unordered containers, that they do not require an ordering function, is the test: if your code needs no ordering, the unordered route is available to you.