Iterator Categories in C++

Tag dispatch selects a function based on properties of a type, here the kind of iterator a container provides.

Programming

One Sort Function, Two Strategies

Suppose you want one generic sort function that works on many different containers. Some containers let you jump straight to any position, while others only let you step forward one element at a time. Sorting efficiently in these two situations calls for different strategies. A random-access sequence can be sorted in place directly. A forward-only sequence cannot be sorted by jumping around inside it, so a different approach is needed.

The question this section explores is how a single entry point can quietly pick the right strategy without the caller having to choose. The technique that makes this possible is called tag dispatch. It selects a function based on the properties of a type, and here the property of interest is the kind of iterator a sequence provides.

What do you think happens?

When the generic sort is called on a std::list, which helper do you expect to run?

The random-access helper, which sorts the range directly
The forward helper, which copies into a vector, sorts it, and copies back

Reveal answer

Answer:

The forward helper runs.

A list iterator is bidirectional. Bidirectional is a stronger category than forward, so the forward overload matches the tag, while the random-access overload does not. The compiler makes this choice during overload matching, not through a runtime check.

Tracing the Tag Through the Wrapper

The generic wrapper does two things in sequence. First, it obtains the iterator type of the container. Second, it constructs an empty value of a tag type. That value does no work by itself. Its only purpose is to carry information about what kind of iterator was provided, so that overload resolution can match it to the correct helper.

When the generic wrapper calls a helper, the tag built from the iterator type is matched against the parameter type of each overload, and only one overload is chosen.

Notice what the wrapper does not contain: it never writes an if statement that checks whether the iterator is random-access. The branching is handled entirely by the compiler, which matches the tag type to the parameter type of each helper. The decision is expressed through types, not through runtime tests.

Two Helpers and Their Strategies

The first helper is written for random-access iterators. Because the code can subscript into the half-open range from beg to end, it sorts that range directly. The second helper is written for forward iterators, which can be traversed but not jumped into. It takes a different route: it copies the elements into a vector, sorts that vector, and copies the sorted values back into the original sequence.

cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

template <typename Iter>
void sort_helper(Iter beg, Iter end, std::random_access_iterator_tag) {
    std::cout << "random-access helper\n";
    std::sort(beg, end);
}

template <typename Iter>
void sort_helper(Iter beg, Iter end, std::forward_iterator_tag) {
    std::cout << "forward helper\n";
    std::vector<typename std::iterator_traits<Iter>::value_type> tmp(beg, end);
    std::sort(tmp.begin(), tmp.end());
    std::copy(tmp.begin(), tmp.end(), beg);
}

template <typename C>
void generic_sort(C& c) {
    using Iter = typename C::iterator;
    sort_helper(c.begin(), c.end(),
                typename std::iterator_traits<Iter>::iterator_category{});
}

int main() {
    std::vector<int> v{4, 1, 3};
    generic_sort(v);
    std::list<int> l{4, 1, 3};
    generic_sort(l);
}

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

template <typename Iter>
void sort_helper(Iter beg, Iter end, std::random_access_iterator_tag) {
    std::cout << "random-access helper\n";
    std::sort(beg, end);
}

template <typename Iter>
void sort_helper(Iter beg, Iter end, std::forward_iterator_tag) {
    std::cout << "forward helper\n";
    std::vector<typename std::iterator_traits<Iter>::value_type> tmp(beg, end);
    std::sort(tmp.begin(), tmp.end());
    std::copy(tmp.begin(), tmp.end(), beg);
}

template <typename C>
void generic_sort(C& c) {
    using Iter = typename C::iterator;
    sort_helper(c.begin(), c.end(),
                typename std::iterator_traits<Iter>::iterator_category{});
}

int main() {
    std::vector<int> v{4, 1, 3};
    generic_sort(v);
    std::list<int> l{4, 1, 3};
    generic_sort(l);
}

Output

random-access helper
forward helper

Walk through it

1
The random-access overload sorts the range in place with std::sort.
2
The forward overload copies the range into a temporary vector, sorts that vector, and copies the values back.
3
generic_sort(v) passes a random-access tag, so the first overload runs.
4
generic_sort(l) passes a bidirectional tag, which the forward overload accepts, so the second overload runs.

Notes on the code

Two overloads of sort_helper differ only in the tag parameter.
The wrapper passes an empty tag object; it never tests the iterator kind itself.
The standard library's iterator_traits supplies the category tag in this version.

The random-access helper uses direct jumps to sort in place, while the forward helper must work through a temporary copy.

How Overload Matching Chooses a Helper

Overload matching works because the tag types are related to each other. The standard iterator categories form a hierarchy, and a stronger category derives from a weaker one. A random-access tag therefore also matches an overload written for a forward or input tag, but the reverse is not true. When several overloads are viable, the most specific one wins, which is why the random-access helper is chosen whenever a random-access tag is passed.

Each category is a refinement of the one above it, so a tag can match overloads written for any weaker category.

Naming the Element Type with value_type

The forward helper needs a vector that holds the same kind of element as the sequence. The source names this element type through Value_type, which is defined through the value_type member that every standard-library iterator has. The standard library exposes the same idea through iterator_traits, as used in the code above. Naming the element type this way lets the helper build a vector of the correct type without spelling it out.

Worked example

Predicting the vector created from an iterator's value_type

Given a vector of int, find the element type through the iterator and construct a vector of that type with three slots. What does the new vector hold?

1
Name the iterator type
The iterator type is std::vector<int>::iterator.
2
Extract value_type
Using iterator_traits on that iterator type gives value_type, which is int.
3
Alias the element type
The alias Value is int, so Value and int name the same type.
4
Construct the vector
std::vector<Value> out(3) is the same as std::vector<int> out(3), which holds three value-initialized ints.

Result

The new vector is a vector of int with three elements, each equal to 0. Printing it produces 0 0 0.

Mistakes With Iterator Tags

Common mistake
Adding a runtime if statement to check whether the iterator is random-access
Why it fails
The technique depends on the compiler choosing an overload from the tag type. A runtime branch bypasses that mechanism and keeps the decision out of the types.
Do this instead
Leave the branching to overload matching and give each helper a tag parameter.
Common mistake
Assuming a list must use the random-access helper because it can be traversed in both directions
Why it fails
Traversal in both directions is bidirectional, not random-access. Random-access requires the ability to jump to any position.
Do this instead
Match the tag to the category the iterator actually provides, and remember that the forward overload accepts any stronger tag.
Common mistake
Writing the element type of the temporary vector by hand instead of deriving it from the iterator
Why it fails
A hand-written type can silently disagree with the container's element type, and the helper then stops being generic.
Do this instead
Derive the element type through value_type or iterator_traits, as the Value_type alias does.

Trace It Yourself

MEDIUM

Using the code from the two-helper example, predict the printed output if generic_sort is called on a std::vector<int> and then on a std::list<int>, and then say which helper ran for each call and why. Then add a third call on a std::vector<double> and predict its helper.

Hints

Ask which tag type the wrapper passes for each container.
A vector iterator is random-access, so its tag matches the random-access overload directly.
The forward overload accepts any tag that is forward or stronger.

Your attempt (not saved)

Key Takeaways

Tag dispatch selects a helper by the type of an empty tag object rather than by a runtime check on the iterator.
A random-access helper can sort a range directly, while a forward helper copies into a vector, sorts it, and copies the values back.
Iterator category tags form an inheritance hierarchy, so a stronger tag also matches overloads written for weaker categories.
value_type, or iterator_traits in the standard library, names the element type of an iterator and lets a helper build a vector of matching type.

Related concepts

More concepts starting with I