Iterator Categories and Their Capabilities

Generic algorithms receive iterators, and iterators do not all offer the same abilities. Some iterators let you move to any position in a sequence directly, while others can only advance one element at a time. An algorithm written to take advantage of direct movement may not suit an iterator that can only move forward, and the reverse is also true. Programmers therefore want a way for one algorithm name to route the work to the version that fits the iterator in hand.

The technique that handles this routing is called tag dispatch. Its defining feature is that the choice between alternatives is made based on the type of iterator that was provided, and it is made at compile time. This article follows the path a single iterator takes through that routing, then looks at the mistakes readers most often make along the way.

The first step in the path is to recover the iterator type from the container type alone. A generic function that has been handed a container type can use Iterator_type<C> to name the iterator type that belongs to that container. The source describes this as returning C::iterator, so the function does not need to know anything more about the container in advance.

The result of this step is still a type, not a value. Nothing has been asked to move or to inspect the container yet. The step only answers the question of which iterator type belongs to this container.

A type alone cannot be passed into a function in the way a value can, so the next step converts the iterator type into a value. Iterator_category<Iter>{} does this. It constructs a tag value that indicates the kind of iterator Iter is. The tag is what the helper overloads are matched against.

It helps to read the expression from left to right as a small sentence. The function name says that a category is being determined. The angle brackets say which iterator type the category is being determined for. The empty braces say that a value of the resulting kind is being produced. The output is a tag whose job is to carry information about the iterator's kind into a function call, where overload selection can use it.

The technique is built from two helper functions. They share a name. Each one takes an extra argument whose only purpose is to say which kind of iterator that helper is meant for. One helper is intended for random-access iterators, and the other is intended for forward iterators.

Because the extra argument carries the tag, the two helpers can share a name and still be told apart when a call is made. The name is the same for both, so the caller writes one algorithm name, and the tag argument decides which helper body is the match.

The random-access helper is the more straightforward of the two. Its body is trivial, which means there is little work to do once the right helper has been chosen. The interesting part of the design lies in the selection, not in the bodies. That is why most of the explanation concerns how the right helper gets picked.

The diagram below shows the order of events from the call to an algorithm to the overload that actually gets compiled. The branch sits at the point where the tag is compared against the helpers' extra arguments. That comparison is resolved while the program is compiled, so the branch does not exist as a decision at run time.

Tag dispatch lets one algorithm name serve iterators with different abilities. The routing is built from a type lookup, a value construction, and an overload match, and the match is made at compile time. The standard library relies on this technique, which is why it is used to improve both flexibility and performance.