Iterator Traits and Type Functions

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 that choice while the program is being compiled, before any values exist. This article starts from two short lines of C++ that do exactly that kind of work, and then shows how the standard library applies the same technique to iterators.

Keep one question in mind as you read: if a generic function needs to behave differently depending on what kind of iterator it receives, how can it find out what kind that is without running any code first? The answer the standard library uses is the subject of the rest of this article. The two names that the source introduces, Iterator_type and Iterator_category, each stand for a type rather than a value, and tracing what each one refers to is the best way to see the whole mechanism.

The Iterator_type alias from the source is a type function. Given a container type C, it names C's iterator type. You can think of it as a lookup table with one row: put in a container type, and the alias gives back the iterator type that container declares. Because the lookup happens in the compiler, the result can shape the code that is generated for that exact type.

A class template is the pattern the compiler uses to build a concrete class for a specific type. Writing std::iterator_traits<Iter> with a concrete iterator type in place of Iter asks the library for the information it holds about that iterator. The source describes this information as a set of type-level facts, and the one it names is the iterator category, accessed as the member iterator_category.

The pattern from the source can be written in a generic form. The first line declares a template parameter C that stands for any container type. The second line defines a new name, Iterator_type, as an alias for C::iterator. The diagram below labels each part of that line so you can see what each piece contributes.

Read the alias from left to right in the same order the compiler does. The template line says the alias works for any C. The using line gives the new name. The typename keyword marks C::iterator as a type. The final part, iterator, is a member that C must provide. If you substitute a concrete container type for C, the compiler looks inside that container for its member named iterator and returns the type it finds there.

The typename keyword appears in the middle of the Iterator_type line for a reason the source spells out. Because the expression depends on the template parameter C, the compiler cannot know on its own whether C::iterator names a type or something else, such as a value or a function. Writing typename tells it that the name is a type. The same keyword appears in the Iterator_category line for the same reason, where iterator_traits<Iter> depends on the template parameter Iter and the compiler needs to be told that iterator_category is a type.

The standard header <iterator> provides the class template iterator_traits, which supplies information about iterators. The information comes out as member names. The member named in the source is iterator_category, and you read it by writing the name of the iterator type inside the angle brackets and then the member name after the scope operator. The diagram shows the lookup path: the iterator type goes into the template, and the member comes out.

The diagram also shows something the source does not spell out in detail: a raw pointer does not declare nested members of its own, yet iterator_traits still gives it the same set of type-level facts. This is why generic code can ask for iterator_category without first checking whether the iterator is a class or a pointer. The lookup is uniform across both.

The example below is an original illustration that uses only the pattern shown in the source. It defines a small container type whose iterator member is a plain pointer. Follow the alias from the container type to the answer it produces.

Tag dispatch is a technique that uses iterator categories to choose among different implementations of the same work. One generic function can pick one of several versions based on the kind of iterator it receives. The category of the iterator acts as a tag, and the compiler selects the 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.

Read the diagram from top to bottom. The generic code never checks the iterator's kind by hand. It asks iterator_traits for the category, and the 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 that information to choose behavior.

The source says that iterator_traits gives simple definitions of the type functions used in sort() and supports tag dispatch. In other words, sort() does not hard-code what kind of iterator it is working with. It reads the category through a type function and lets tag dispatch pick the version of the work that suits that category.

The plan for this article notes that sort() only compiles when the iterator category supports constant-time jumps, which is the random-access category. The reasoning follows from the dispatch step above: if the category does not offer that capability, the overload chosen for sort() cannot be built for that iterator type. Use the category tag, not your own guess about the iterator, to decide whether a given iterator can be sorted.