Understanding Iterator Traits and Tag Dispatch

Tag dispatch selects between algorithms based on the type of iterator provided, and the selection happens at compile time.

Programming

One Algorithm Name, Two Different Jobs

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. 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 one algorithm name to route the work to the version that fits the iterator in hand.

The technique that does this routing is called tag dispatch. Its defining feature is that the choice between alternatives is made at compile time, based on the type of iterator that was provided. This article follows the path a single iterator takes through that routing. Then it looks at the mistakes readers most often make while following that path. Keep one question in mind as you read: when does the choice actually happen?

Why Iterators Differ in What They Can Do

Think about two kinds of iterator. A random-access iterator can move to any position in a sequence directly, so reaching the fifth element from where you stand is a single movement. A forward iterator can only advance, and it does so one element at a time, so reaching the fifth element means stepping through each element before it. The same goal, moving an iterator forward by some number of positions, can therefore be carried out in two very different ways.

In the real world

Imagine two travelers asked to get to house number 500 on a street. One has a map that lets them jump straight to any address. The other must walk past every house in order. Both arrive, but the work each one does is not the same. An algorithm that can exploit the map should use it, and an algorithm that only has the walking option must walk. Tag dispatch is the mechanism that lets one algorithm name pick the right method for the traveler it was given.

Following One Iterator Through the Router

The routing begins with a type, not a value. A generic function is handed a container type and needs to know which iterator type belongs to it. The rest of the trace is a short chain of steps. Each step produces something the next step consumes. The diagram below shows that chain from the container type to the tag object that drives overload selection.

What is passed from the container type to the trait, and how does that value become the tag argument used for overload selection?

Two Helpers Sharing One Name

The technique is built from two helper functions. Each takes an extra argument whose only purpose is to say which kind of iterator the helper is meant for. One helper is intended for random-access iterators and the other 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 sketch below is an illustrative generated example, not code from the source. It shows the shape of the idea in C++. The source does not show the definition of Iterator_category, so the sketch assumes it returns the matching tag.

cpp

struct forward_tag {};
struct random_access_tag {};

template <typename Iter>
void advance_by_impl(Iter& it, int n, forward_tag) {
    while (n-- > 0) ++it;      // one step at a time
}

template <typename Iter>
void advance_by_impl(Iter& it, int n, random_access_tag) {
    it += n;                   // one direct movement
}

template <typename Iter>
void advance_by(Iter& it, int n) {
    advance_by_impl(it, n, Iterator_category<Iter>{});
}

struct forward_tag {};
struct random_access_tag {};

template <typename Iter>
void advance_by_impl(Iter& it, int n, forward_tag) {
    while (n-- > 0) ++it;      // one step at a time
}

template <typename Iter>
void advance_by_impl(Iter& it, int n, random_access_tag) {
    it += n;                   // one direct movement
}

template <typename Iter>
void advance_by(Iter& it, int n) {
    advance_by_impl(it, n, Iterator_category<Iter>{});
}

Notes on the code

The two helpers share the name advance_by_impl and differ only in their extra tag argument.
The caller advance_by never mentions which helper to use; it passes the tag produced from the iterator type.
The random-access helper body is a single movement, which matches the source's remark that its body is trivial.

Notice where the interesting work sits. The random-access helper is the more straightforward of the two, because its body is trivial once it has been chosen. The design lies in the selection, not in the bodies. That is why most of the explanation concerns how the right helper gets picked.

Where the Choice Is Made

The phrase that matters most in this technique is at compile time. The comparison between the tag value and the helper arguments is resolved while the program is being compiled. By the time the program runs, it already contains the selected helper. Nothing has to inspect the iterator during execution in order to decide which algorithm to use.

After the tag value is produced, which overload is chosen, and at what point in compilation does that choice happen?

The diagram reads from the top. The call produces a tag, the tag is compared against the helper arguments, and exactly one helper survives into the compiled program. The decision node is the compile-time comparison, not a runtime branch. The standard library relies on this technique, and the source connects it to two benefits: flexibility, because one algorithm name serves several iterator kinds, and performance, because the selection costs nothing while the program runs.

Tracing a Call Through the Sketch

Worked example

Choosing the helper for a random-access iterator

A caller invokes advance_by with a random-access iterator and n equal to 5. Which helper runs, and what does it do?

1
Recover the iterator type
The generic function works with the iterator type Iter, which belongs to the container in use.
2
Produce the tag
Iterator_category<Iter>{} constructs a tag value that indicates Iter is a random-access iterator, so the tag is random_access_tag.
3
Match the overload
The call advance_by_impl(it, n, tag) is resolved at compile time. The tag matches the random-access helper, so that helper is the one selected.
4
Run the selected body
The random-access body runs it += n, one direct movement, rather than stepping five times.

Result

The random-access helper is selected during compilation and performs a single movement. The caller wrote one call and never mentioned which helper to use.

Repeat the trace with a forward iterator. The tag is forward_tag, the compiler selects the forward helper, and that helper advances one element at a time. The caller's code does not change. Only the type of iterator passed in changes, and that alone determines which helper is kept.

Common Misreadings of Tag Dispatch

Common mistake
Believing the helper is chosen while the program runs
Why it fails
The choice is made at compile time, based on the type of iterator that was provided. Nothing inspects the iterator during execution to decide which algorithm to use.
Do this instead
Treat the overload selection as part of compilation. The compiled program already contains the selected helper.
Common mistake
Assuming the tag object carries the data the algorithm works on
Why it fails
The tag exists to carry information about the iterator's kind into a function call so that overload selection can use it. Its role is to select a helper, not to hold the sequence or the position.
Do this instead
Think of the tag as a label that drives matching. The actual movement is performed by the chosen helper on the iterator passed alongside the tag.
Common mistake
Expecting the random-access helper to be the complicated one
Why it fails
The source notes that the random-access helper's body is trivial. The interesting part of the design is the selection.
Do this instead
Focus study effort on how the right helper is picked, and treat the bodies as the simpler part of the mechanism.
Common mistake
Thinking the caller must name the helper
Why it fails
The caller writes one algorithm name. The routing to the fitting helper happens inside the technique.
Do this instead
The benefit of tag dispatch is that callers stay unchanged while the implementation adapts to each iterator kind.
Common mistake
Guessing what iterator_traits and type predicates mean from their names
Why it fails
The section names these ideas without defining them, so a definition should not be inferred from the names alone.
Do this instead
Record the one stated link between them, and keep a separate list of questions about each idea.

How Iterator Traits Relate to Type Predicates

This section introduces two named ideas from the chapter on type functions in C++: iterator_traits and type predicates. Both are presented as topics to understand, and the section connects them. Both names appear together in one entry, which signals that the section treats them as a pair. The section states one relationship: iterator_traits is related to type predicates.

How do iterator_traits and type predicates relate, and which one supplies the information the other uses?

Checking Your Understanding

What do you think happens?

Before reading on, predict which helper is selected when Iter is a forward iterator, and whether that choice happens while the program runs.

The random-access helper, at run time
The forward helper, at compile time
The forward helper, at run time
The random-access helper, at compile time

Reveal answer

Answer:

The forward helper, at compile time

The tag for a forward iterator is forward_tag, which matches the forward helper. The comparison is resolved during compilation, so the compiled program already contains that helper.

EASY

Explain in your own words how Iterator_type<C> and Iterator_category<Iter>{} differ in what they produce. One produces a type and the other produces a value. Say which is which and why a value is needed for the function call.

Hints

Ask whether a type can be passed into a function the way a value can.
Look at what the source says Iterator_type<C> returns, and what the braces in Iterator_category<Iter>{} create.

Your attempt (not saved)

MEDIUM

Write three study questions you would need to answer to understand iterator_traits in more depth. Make each question specific. For example, ask what the section means by the relationship it states, rather than asking what iterator_traits is in general.