Writing Generic Algorithms with Iterators

Suppose you want to sort everything held in a container. A natural design is a sort function that receives the container and does the work itself. The standard library's range version of sort() is shaped differently. It takes a pair of iterators that together define a sequence. The first iterator marks where the sequence begins, the second marks where it ends, and sort() works on everything between them.

This shape matters because it moves the question. The function no longer asks what kind of container it was given. It asks what its iterators can do. That single change is the idea this article builds on: a generic algorithm is written against a capability, and the iterator is what provides that capability.

The important detail is what sort() demands of those iterators. They are not allowed to be just any iterators. They must offer random access to the sequence. Sorting moves elements around in a non-sequential way, so the algorithm must be able to reach any position in the sequence directly, rather than stepping through one element at a time.

Random access is the capability to reach any position in a sequence directly. In the source's terms, a random-access iterator supports operations such as it + n and it[i], which move to or read the element a given distance from where the iterator currently is. A function that depends on this capability has a precondition, and that precondition belongs to the iterator, not to the container's name or its size.

Read the cells above as the sequence that sort() must rearrange. Because the algorithm may need to touch position 3 right after position 0, it needs a way to address each cell by its index. A capability that lets the program index into the sequence is what makes the sort possible at all.

The reason a forward_list cannot jump is rooted in how it is stored. The source describes forward_list as a singly-linked list. Each element knows only about the element after it, so the structure is a chain that can be followed in one direction. The two sub-topics below contrast this chain with a container that supports random access.

If a sort function simply accepts any pair of iterators, it will fail on a forward_list at the point where it tries to use a capability the 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 source describes the calling pattern as one function name, two different containers, and no separate sorting function for each. It also states that the techniques needed to make that work are generally useful beyond this one case.

The sort function does not need to know the container's name. It asks iterator_traits which kind of iterator it has been given, and that answer decides which strategy the function can take. A vector's iterators provide random access, so the function can use the direct-jump strategy. A forward_list's iterators provide only forward traversal, so a function that checks first can avoid committing to a strategy that the iterator cannot support.

The flowchart below follows a sort() call on a forward_list. The question is at which step the failure happens. Read it as the order of checks the function must satisfy, not as a claim about any particular compiler's messages.

The step that fails is the requirement check at the call, where sort() needs random access and the forward_list's forward iterators cannot provide it. A function that skips the check and simply begins working will fail later, at the point where it tries to use the missing capability. Checking first places the failure at the call, where the cause actually lies.

Designing against iterator capabilities makes one generic function usable across containers. The technique is to let the iterator kind determine what the function may do, rather than writing a separate sort for each container. The source notes that this approach is generally useful beyond the single sort example.