Linear Search Versus Tree Search

Suppose you keep a list of people and their phone numbers, where each entry is a pair holding a name and a number. When you want the number for one particular name, you have to walk through the list and compare names until you find a match. For a short list this is perfectly fine. For a long list it becomes slow, and writing the search code over and over becomes tedious. The question this article answers is whether there is a container designed so that finding a value by its name is the natural operation, not an afterthought.

Two observations set up the rest of the topic. First, writing code to look up a name in a list of name-number pairs is quite tedious. Second, a linear search, which checks entries one after another from the beginning, is inefficient for all but the shortest lists. The standard library responds to this problem by offering a search tree called map.

A linear search starts at the first entry and compares it with the name you want. If it matches, the search stops and returns that entry. If it does not match, the search moves to the next entry and repeats the comparison. The search stops either when a match is found or when the list runs out of entries. Nothing about the list's arrangement helps it skip ahead, so in the worst case every entry must be examined.

The diagram uses five invented name-number pairs in alphabetical order. Even with the list sorted, a linear search does not exploit that order. It checks Alice, then Bob, then Dana, then Eve, and only stops once it reaches the match. Sorting alone does not change the procedure; the search still reads entries one at a time from the beginning.

The word container matters here. Like the other standard containers, a map holds a collection of items, and you create it, fill it, and query it. What sets a map apart is its purpose. A vector or a list is organized around positions in a sequence, while a map is organized around the pairs it stores so that a lookup can be performed efficiently. The map is optimized for lookup, which is the reason to choose it over a plain sequence when you frequently need to find values.

Creating a map looks familiar if you already know vectors and lists, because the same initializer style applies. You list starting values in braces, just as you would for a vector or a list, so the new container is easy to begin using. Familiar syntax should not hide the difference in purpose, however. The initializer tells you how to fill the container; the optimization for lookup tells you why you would choose a map in the first place.

The same container goes by different names in different contexts. Outside the standard library's own vocabulary, a map is known as an associative array or a dictionary. When you read documentation or discussions in other languages and tools, you may see any of these three names, and they all refer to a collection of pairs in which you look up one value by means of another.

Map is the name used by the standard library, while associative array and dictionary are names you will meet elsewhere. Which one a discussion uses depends on the context, but the underlying idea of a collection of pairs searched by one part of each pair is the same.

The reason a map can answer lookups quickly is its internal arrangement. The standard-library map is implemented as a balanced binary tree, which is a search tree designed to keep lookups efficient. Instead of a flat list that is scanned from the front, the pairs are stored in a branching structure whose shape is chosen so that searching for a key follows a short path.