Iterator Categories and Their Operations

Suppose you have a collection of values and you want them in order. A natural design is a sort function that receives the container itself and does all the work. The standard library's range version of sort() is shaped differently. It does not take a container. It takes a pair of iterators that together define a sequence: one marks where the sequence begins, the other marks where it ends, and sort() works on everything between them.

That shape looks harmless, but it carries a hidden requirement. The iterators passed to sort() are not allowed to be just any iterators. They must offer random access to the sequence. Whether a given call is valid therefore depends on what kind of iterator the container provides, not only on whether the container can be looped over. This article follows that requirement from the call site down into the iterator itself.

The reason random access matters becomes clearer when you picture how the two kinds of container store their elements. In a random-access container, the elements sit at numbered positions, and a program can jump straight to position i. In a forward_list, each element holds a link to the element after it and nothing else useful for navigation. To reach position i, you must start at the beginning and follow links one at a time.

Read the diagram as a contrast in access, not a ranking of quality. The top row can be reached by naming a position. The bottom row can only be reached by walking. The links in the forward_list also point only forward, because each element knows about the element after it and not about the one before it. That is why stepping back is not a reasonable operation for this container.

sort() moves elements around in a non-sequential way. It does not simply pass once from front to back, swapping neighbours as it goes. Because it reorders elements across the whole sequence, it needs to reach any position directly. Random access is the capability that provides this: it lets a program reach any position in the sequence without stepping through each element before it.

Random access is therefore a property of how a container's iterators behave. A container can hold a great many elements, be walked from start to finish, and still fail this precondition if its iterators cannot jump to arbitrary positions.

If a sort function simply accepted any pair of iterators, it would fail on a forward_list at the point where it tried to use a capability that iterator does not have. A better design checks the kind of iterator before it commits to a strategy. The standard library provides a mechanism named iterator_traits for exactly this purpose. It allows a program to check which kind of iterator a container supports.

The source uses this mechanism to improve the range sort() function from an earlier section, so that it accepts either a vector or a forward_list. The goal is a single function that can be called on both containers, with the kind of iterator determining what the function is able to do. The example is written in C++, the language the source uses for the standard library. Its value here is the calling pattern: one function name, two different containers, and no separate sorting function for each.

The diagram shows the order of decisions. The category is looked up before the sorting work begins, so the function's behaviour follows from the kind of iterator it was given. The same function name therefore covers both containers, while the iterator determines which path is open to it.

Consider a call such as sort(lst), where lst is a forward_list. When you read this call, the question to ask is not whether the container holds numbers or can be walked from front to back. The question is whether its iterators meet the requirement of the function being called. The sequence below follows that question through the call.

Notice that the same values, the same loop structure, and the same container could be fine for a different algorithm that only needs forward traversal. The mismatch is between the container's iterator kind and the function's requirement, which is why it is found at the call and not inside the element values.