Ordering Functions and Comparison in Containers

Suppose you already store your data in a map and you ask it to find one element. How much work does that search take? This article answers that question and then asks what it would take for a container to be even faster for lookups, and what that container gives up in exchange.

A map finds an element by comparison. At each step it uses an ordering function, such as the less-than operator, to decide which direction to move in as it searches. Each comparison rules out a large share of the candidates that could still hold the key, so the search shrinks quickly. The source does not spell out every internal detail of this process, so the halving pattern below is an illustration of how a logarithmic cost behaves, not a literal trace of any particular implementation.

Read the diagram from top to bottom. The first comparison leaves about half of the million candidates in play, the second leaves about a quarter, and so on. The search does not visit each entry in turn; it removes large blocks of candidates with each comparison. Because the count is cut repeatedly, the number of steps needed is small even when the collection is very large.

The cost of a map lookup is written $O(\log(n))$, where $n$ is the number of elements in the map. The notation describes growth. The number of steps grows with the size of the map, but much more slowly than the size itself. A cost of this form does not promise a fixed number of steps; it describes how the count changes as the collection grows.

The source's own example uses this calculation. For a map with 1,000,000 elements, a lookup performs about 20 comparisons and indirections. The logarithm base 2 of one million is about 20, which matches that stated figure. The useful habit is to read the cost as a growth rate: multiplying the collection size by a thousand adds only about ten more steps in this model, which is why logarithmic lookup is attractive for large maps.

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 searches by comparison: it uses an ordering function to relate keys and move through the search. An unordered_map takes a hashed route that avoids comparison using an ordering function. The source notes that in many cases a hashed lookup can do better than a comparison-based lookup.

Notice what the diagram leaves out. It does not show the internal layout of either container, because the source does not describe how a hashed container arranges its elements. The comparison focuses on the lookup route alone: one container searches by comparing against an ordering, and the other avoids that ordering requirement entirely.

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. This is why the word unordered should be read as a statement about what the container does not require. It is a claim about the absence of an ordering requirement, and it should not be read as a promise that the container is disorganized.

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. The flowchart below turns that rule into a sequence of questions. The question about sorted order is drawn from the meaning of the word unordered, which tells you the hashed container does not provide an ordering requirement.