Tag Dispatch in C++: Selecting Functions at Compile Time

Tag dispatch is a C++ template metaprogramming idiom used to select different function implementations at compile time based on type properties. By passing an instantiated, empty struct—called a "tag"—as an extra argument to an overloaded implementation function, the compiler uses standard overload resolution to select the most suitable version. This mechanism delivers zero runtime overhead and clear separation between algorithm variants, serving as the foundational design pattern behind standard utilities such as std::advance.

How Tag Dispatch Works

Tag dispatch relies on three main components: tag types, overloaded implementation functions, and a public wrapper function that queries a type trait.

1. Tag Types: Lightweight, empty structs that represent specific capabilities, categories, or traits of a type.
2. Implementation Functions: Overloaded functions (impl functions) that take an instance of a specific tag type as an auxiliary parameter.
3. Public Interface: A single entry-point function that extracts the appropriate tag from a type trait and passes a default-constructed instance of that tag to the implementation function.

Because tag structs contain no state, optimizing compilers eliminate the tag argument entirely, leaving behind direct, optimal machine instructions without virtual dispatch or runtime branching.

Implementation Example: Custom advance

A classic demonstration of tag dispatch is advancing an iterator. While random-access iterators can jump directly to a target position in constant time (O(1)), forward iterators must step through elements sequentially in linear time (O(N)).

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

namespace detail {
    // Implementation for random access iterators: O(1)
    template <typename Iter, typename Distance>
    void advance_impl(Iter& it, Distance n, std::random_access_iterator_tag) {
        it += n;
    }

    // Implementation for bidirectional/input iterators: O(N)
    template <typename Iter, typename Distance>
    void advance_impl(Iter& it, Distance n, std::input_iterator_tag) {
        while (n > 0) {
            ++it;
            --n;
        }
    }
}

// Public interface
template <typename Iter, typename Distance>
void my_advance(Iter& it, Distance n) {
    // 1. Extract the iterator category tag using traits
    using category = typename std::iterator_traits<Iter>::iterator_category;
    
    // 2. Dispatch to the matching overload by constructing the tag
    detail::advance_impl(it, n, category{});
}

Leveraging Tag Hierarchies for Fallback Behavior

Tag dispatch becomes particularly powerful when tags are organized in an inheritance hierarchy. The C++ standard library defines iterator categories using inheritance:

struct input_iterator_tag {};
struct forward_iterator_tag       : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

When an exact match for a tag does not exist, standard C++ overload resolution falls back to a base class. In the example above, if a std::bidirectional_iterator_tag is passed, the compiler matches advance_impl(..., std::input_iterator_tag) because bidirectional_iterator_tag derives from input_iterator_tag. This enables library authors to provide specialized implementations for advanced types while automatically falling back to generic implementations for others.

Tag Dispatch vs. Modern Alternatives

While tag dispatch remains a core pattern in legacy codebases and specific template designs, modern C++ offers direct alternatives:

• C++17 if constexpr: Allows compile-time branching within a single function body without needing separate overloaded helper functions or tag types.
• C++20 Concepts: Enables constraint-based overload resolution directly on function signatures using requires clauses, producing more concise code and clearer compiler diagnostics.

Despite these advancements, tag dispatch remains an essential technique. It demonstrates how standard overload resolution can resolve complex compile-time polymorphism without introducing language extensions beyond fundamental template types.