Choosing Between Sequential and Associative Containers

When a program has to keep track of many elements, the container you choose decides three things: how quickly you can look an element up, what order you see the elements in when you loop over them, and how the data is laid out internally. These are not small details. Two containers can hold exactly the same data and still behave very differently in your program.

This article focuses on associative containers, the family that includes map and unordered_map, and on the practical guidelines that help you pick one. The guidelines are rules you can apply directly, but the goal is to understand the reasoning behind each rule, so that you can apply it to a requirement the guidelines never mention explicitly. We will trace what happens inside each container when an element is inserted or looked up, then use those traces to make decisions.

A useful way to think about any container is that its behavior follows from the data structure underneath it. Once you know the underlying structure, most of the container's properties follow naturally.

A map is usually implemented as a red-black tree. A tree is made of nodes, and each node holds a key and a value. The arrangement of the nodes is what matters: keys are placed so that moving through the tree in a fixed direction visits the keys in sorted order. This is why a map is the choice when elements must be iterated over in order.

Follow one insertion step by step. Suppose the tree already holds the keys 40, 20, 60, 10 and 30, arranged as shown in the diagram without the key 25. To place 25, you start at the root, 40. Since 25 is less than 40, you move to the left child, 20. Since 25 is greater than 20, you move to the right child, 30. Since 25 is less than 30, the new key lands as the left child of 30. The key is placed by comparing it against nodes on the path down from the root, and the position it lands in is determined by those comparisons.

The tree's shape is what makes ordered iteration possible. Because every key is placed according to its comparison with the keys above it, an in-order walk through the tree (left subtree, then the node, then the right subtree) returns the keys from smallest to largest. You never sort anything during iteration; the sorted order is already present in the arrangement of the nodes.

An unordered_map is usually implemented as a hash table, and it is the choice for fast lookup on large amounts of data. Instead of arranging keys relative to one another, a hash table uses a hash of the key to decide where to look. The steps below trace a lookup for the key apple, as shown in the diagram.

Step one: the key apple is passed to a hash function, which produces a number from the key. Step two: that number is mapped to a bucket index, here 3. Step three: the search happens inside bucket 3, where apple is compared with the keys stored there. The other buckets are never examined for this lookup. This is why the hash table structure supports fast lookup: the work is concentrated in one small place rather than spread across the whole collection.

The consequence for ordering is direct. Keys are placed according to their hashes, not according to any relationship between them, so a hash table does not offer the sorted walk that a tree-based map offers. If your program needs to visit elements in order, the hash table arrangement is the wrong tool, however fast its lookups are.

The two containers pair their usual implementations with different strengths. Neither one claims the other's strength, so the choice depends on which property your program needs most. The table below puts the source's points about each container next to each other.

The source gives three guidelines for this decision. Use unordered containers when you need fast lookup for large amounts of data. Use ordered associative containers such as map and set when you need to iterate over their elements in order. Use unordered containers for element types that have no natural order, meaning types for which no reasonable less-than comparison exists.

Read the flowchart from the top. The ordering question comes first because it is the one hard constraint the source names: if the output must come out in order, an unordered container does not satisfy it, no matter how fast its lookups are. If ordering is not required, the next question is whether the element type has a natural order. If it does not, unordered_map is the choice. If it does, the question becomes whether you need fast lookup on large data, which also points to unordered_map. When neither condition applies, the source offers no default, and you must decide from your other requirements.

Container creation uses two initializer forms, and the source assigns each one a specific job. The parentheses form is used for sizes. The braces form is used for lists of elements. The same pair of symbols can therefore mean very different things depending on which form you use, and mixing them up is one of the most common sources of surprise with containers.

A practical habit follows from this split. When you want a container with a given number of elements, write the count in parentheses. When you want a container that starts with specific values, write those values inside braces. Reading the symbols as a statement of intent, size or list, makes the meaning of each declaration clear before you run the program.

Once a container exists, it often moves between functions. The source gives a direct guideline for this: pass a container by reference, and return a container by value. Passing by reference means the function receives the caller's container itself rather than a separate parameter, so the function works on the same container the caller holds. Returning by value means the function hands the container back as its result, and the caller receives it as the function's output.

Read the two directions separately. Inputs travel into a function by reference, so the function changes the caller's container. Results travel back out by value, so the caller ends up holding the container the function produced. In the example, add_score adds Bo to the same roster that main owns, and make_scores hands its new map back to main as its result.

The source also gives a general preference for data structures: prefer compact and contiguous ones. It warns that a list is relatively expensive to traverse. These two points tell you what to avoid when a container will be walked through repeatedly. A structure whose elements are scattered and costly to step through is a weaker default than one whose elements sit close together. These preferences sit alongside the ordered and unordered rules rather than replacing them. When you choose a structure, ask whether it is compact and contiguous, and whether you will traverse it often enough for traversal cost to matter.