Tag Dispatch and Iterator Categories

Most code you write works with values: numbers, strings, and containers that hold them. Some code has to work with types instead, and it has to make its choice while the program is being compiled, before any values exist. This article starts from the idea of a name that stands for a type rather than a value, and then shows how the standard library applies the same technique to iterators.

The two ideas to keep in view are these. First, a type function takes a type as input and produces a type as output, at compile time. Second, tag dispatch uses the category of an iterator to choose among several implementations of the same work. The rest of the article explains how the first idea makes the second one possible, and why a routine such as sort() depends on both.

The source opens with two short lines of C++. Each one defines a name that refers to a type. The names are Iterator_type and Iterator_category. Neither name holds a value. Each one is an alias for a type that the compiler works out from another type you supply.

Think of the trace as a sequence of states. Before compilation, you have only text. During compilation, the template parameter is filled in with a concrete type, the lookup is performed, and a named type is produced. Nothing about this process runs when the program executes. The program later uses the result, but the work of finding the type is already finished.

The standard header <iterator> provides the class template iterator_traits, which supplies information about iterators. A class template is a pattern that the compiler instantiates for a specific type. When you write std::iterator_traits<Iter> with a concrete iterator type in place of Iter, you ask the library for the set of type-level facts it holds about that iterator.

The source names one of these facts directly: the iterator category, accessed as the member iterator_category. Other facts sit alongside it in the same traits class, and the diagram below shows the mapping. The important idea is that you give iterator_traits an iterator type as its key and receive a bundle of associated types back.

A type function takes a type as input and produces a type as output, at compile time. The Iterator_type alias in the source is a type function: given a container type C, it names C's iterator type. The alias is written as a template alias, which means it is a pattern that is filled in once a concrete type is supplied.

The typename keyword appears in both alias lines for the same reason. Because the expression depends on a template parameter, the compiler cannot know on its own whether the name that follows is a type or something else. Writing typename tells it that the name is a type. In the first line the dependent name is C::iterator, and in the second it is iterator_traits<It>::iterator_category.

Now trace one concrete lookup through the states it passes through. Work from the alias Cat and a concrete iterator type, and watch which name is filled in and which member is read at each stage.

Tag dispatch is a technique that uses iterator categories to dispatch to different implementations. The category of an iterator acts as a tag, and the compiler uses that tag to choose a matching implementation at compile time. The source states that tag dispatch is supported by iterator_traits, which is why the category is read through iterator_traits rather than computed by hand.

The standard iterator categories form a hierarchy. The random access category is the most capable, and each stronger category also counts as every weaker category it extends. So a random access iterator can be matched by an overload written for a weaker category, and the compiler prefers the most specific match when several are available.

The hierarchy matters because overload matching works through it. A routine written for the weakest category can accept any iterator, while a routine written for the strongest category accepts only iterators that support its operations. The compiler's choice follows from the tag each iterator reports through iterator_traits.

The source explains that iterator_traits gives simple definitions of the type functions used in sort(). The generic sort() code does not check the iterator's kind by hand. It asks iterator_traits for the category, and that category decides which implementation the compiler uses. This is the connection between the two ideas in this article: iterator_traits supplies the type-level information, and tag dispatch uses it to choose behavior.