Tag dispatch is a metaprogramming technique where overloaded functions are selected based on “tag” types (usually empty structs), enabling different behavior for different type categories at compile time. For example, passing std::random_access_iterator_tag vs. std::forward_iterator_tag to choose an optimized vs. general algorithm.

Use tag dispatch to specialize algorithms based on iterator or type categories without runtime overhead.

This example shows tag dispatch optimizing algorithms based on iterator type.

// compile: g++ -std=c++17 -o tag tag.cpp
// run: ./tag
// description: tag dispatch selects overloads based on type properties
 
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
 
// Tag dispatch implementation
template <typename It>
void advance_impl(It& it, int n, std::random_access_iterator_tag) {
    it += n;  // O(1) for random access
    std::cout << "Random access advance\n";
}
 
template <typename It>
void advance_impl(It& it, int n, std::forward_iterator_tag) {
    for (int i = 0; i < n; ++i) ++it;  // O(n) for forward
    std::cout << "Forward iterator advance\n";
}
 
template <typename It>
void my_advance(It& it, int n) {
    advance_impl(it, n, typename std::iterator_traits<It>::iterator_category());
}
 
int main() {
    std::vector<int> v{1, 2, 3, 4, 5};
    auto it_v = v.begin();
    my_advance(it_v, 2);  // uses random access
 
    std::list<int> l{1, 2, 3, 4, 5};
    auto it_l = l.begin();
    my_advance(it_l, 2);  // uses forward
 
    return 0;
}