C++标签派发(Tag Dispatching)

标签派发是在 C++ 20 引入 concept 之前模板编程的一个手段：由于 C++ 不支持函数模板的偏特化，所以为例实现偏特化而产生的一个技巧

一、引入

一般重载函数的设计是根据不同的参数决定具体做什么事情，编译器会根据参数匹配的原则确定正确的重载版本。但是对于函数模板，其参数类 型是泛化的模板参数，此时又如何让编译器选择我们希望的那个函数模板的实例呢？

提供特化版本是一个方法，但是如果需要特殊处理的类型很多，就需要搞一大堆特化版本，非常不方便。C++ 11 的语言库提供了 std::enable_if，配合编译器的 SFINAE 原则（见 C++ SFINAE机制）也可以实现在编译期间的特定选择。C++ 17 还提供了一个 std::void_t，以模板别名定义的语法形式提供了另一种利用 SFINAE 的方法。当然，同样是 C++ 17 提供的 if constexpr 语言特性配合各种 type traits，可以更优雅地实现编译期间的特定选择。本文要介绍的是另一种常用的习惯用法（或技术）：Tag Dispatching。

在现代 C++ 中，标签派发（Tag Dispatching） 是一种编译期分派技术。它利用函数重载机制，根据传递的“标签类型”（通常是一个空的结构体）来决定具体调用哪一个重载函数。

这种技术常用于泛型编程（模板），以根据类型的特性（如迭代器类别、是否支持算术运算等）选择最优的算法实现。

二、核心机制

标签派发的本质是：

1. 定义标签类型：通过空的 struct 或 class 表示不同的状态或分类。
2. 重载函数：编写多个相同名称但参数不同的函数，其中一个参数专门用于接收标签。
3. 分发器（Dispatcher）：编写一个主函数，利用 std::integral_constant 或 std::bool_constant 等工具生成标签，并调用重载函数。

Tag Dispatching 是一种利用某种类型特征，在一系列重载函数之间进行编译期调度（分派、选择）的技术。Tag Dispatching 并不是 C++ 的某种特性，但是作为一种习惯用法在 C++ 中被广泛应用，尤其是在标准库中。这里说的 tag，其实就是定义一种没有操作、没有数据的类型，将这种类型作为重载函数的一个参数，通过不同的 tag 参数控制编译器的选择。定义一个 tag 非常简单，一般用 struct：

struct tag1 {};
struct tag2 {};

虽然结构体都是空的，但是在 C++ 编译器看来，tag1 和 tag2 是两个完全不同的类型。基于 Tag Dispatching 的实现就是定义不同的 tag，并将 tag 设计成函数的一个参数。一般会将 tag 设计成 函数的最后一个参数，因为编译器在代码生成的时候对这种完全是空的参数类型会有针对性的优化。具体来说，就是将重载函数设计成这个样子：

template <typename T>
int Function(T t, tag1) { ... }
 
template <typename T>
int Function(T t, tag2) { ... }

这就是所谓的 Tag Dispatching，其实就是利用 tag1 和 tag2 是不同类型的特性，控制编译器在编译期间选择希望的重载版本，实现在编译期间的重载分派，比如：

int a = Function(11, tag1());

下面是一个使用 Tag Dispatching 的简单例子：

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

// 1. 定义标签类型（通常标准库已有：std::random_access_iterator_tag 等）
// 这里为了演示自定义一套模拟标签
struct InputTag {};
struct RandomAccessTag {};

// 2. 实现具体的重载函数
void advanceImpl(const std::vector<int>::iterator& it, int n, RandomAccessTag) {
    std::cout << "使用随机访问优化算法 (O(1))" << std::endl;
    // it += n;
}

void advanceImpl(const std::list<int>::iterator& it, int n, InputTag) {
    std::cout << "使用线性扫描算法 (O(n))" << std::endl;
    // for(int i=0; i<n; ++i) ++it;
}

// 3. 分发器
template <typename Iterator>
void myAdvance(Iterator it, int n) {
    // 根据迭代器类型选择标签
    // 实例化标签并调用
    advanceImpl(it, n, typename std::iterator_traits<Iterator>::iterator_category{});
}

三、示例

3.1 advance

最经典的应用场景是 STL 中的 std::advance。不同容器的迭代器能力不同（如随机访问 vs 单向访问），我们需要根据迭代器类型选择最优路径。std::advance 函数的作用是将迭代器向前（或向后）移动 n 个位置。这里需要注意的是，根据迭代器类型的不同，std::advance 函数内部是不同的实现。比如对于随机类型的迭代器，可以采用高效的 it + n 的形式移动位置，对于不支持随机访问的单向迭代器，只能通过执行 n 次 ++it 的方式移动迭代器，而对于双向类型的迭代器，n 可以是负数，表示向后移动迭代器。

std::advance 函数首先针对不同类型的迭代器定义了相应的重载形式：

template <class RAIter, class Distance>
void advance(RAIter& it, Distance n, 
             std::random_access_iterator_tag) {
    it += n;
}
 
template <class BidirIter, class Distance>
void advance(BidirIter& it, Distance n, 
             std::bidirectional_iterator_tag) {
    if (n > 0) {
        while (n--) ++it;
    }
    else {
        while (n++) --it;
    }
}
 
template <class InputIter, class Distance>
void advance(InputIter& it, Distance n, 
             std::input_iterator_tag) {
    while (n--) {
        ++it;
    }
}

这几个重载函数的第三个参数就是所谓的 tag，以 std::input_iterator_tag 为例，标准库中的定义大概是这个样子：

struct input_iterator_tag {};

标准库还定义了 iterator_traits<> 类模板用于提取迭代器的 tag，对于支持随机访问的迭代器，它的 iterator_category 被特化处理为：

template <class Iter>
struct iterator_traits<Iter> {
    ....
    using iterator_category = random_access_iterator_tag;
};

可用 iterator_traits<Iter>::iterator_category 提取 Iter 类型迭代器的分类 tag。最终 advance() 的实现大致是这个样子：

template <class Iter, class Distance>
void advance(Iter& it, Distance n) {
         advance(it, n, 
         typename std::iterator_traits<Iter>::iterator_category{} );
}

3.2 copy

下面是一个 std::copy 实现的简化版本：

struct pod_tag {};
struct non_pod_tag {};

template<class T> struct copy_trait { using tag = non_pod_tag; };   // T is not "plain old data"

template<> struct copy_trait<int> { using tag = pod_tag; };         // int is "plain old data"

template<class Iter>
Out copy_helper(Iter first, Iter last, Iter out, pod_tag)
{
    // use memmove
    const auto n = static_cast<size_t>(last - first);
    if (n != 0)
        std::memmove(out, first, n * sizeof(Iter));
   	return out + n;
}

template<class Iter>
Out copy_helper(Iter first, Iter last, Iter out, non_pod_tag)
{
    // use loop calling copy constructors
	for (; first != last; ++first, ++out)
        *out = *first;
   	return out;
}

template<class Iter>
Out copy(Iter first, Iter last, Iter out)
{
    return copy_helper(first, last, out, typename copy_trait<Iter>::tag{})
}

void use(vector<int>& vi, vector<int>& vi2, vector<string>& vs, vector<string>& vs2)
{
    copy(vi.begin(), vi.end(), vi2.begin()); // uses memmove
    copy(vs.begin(), vs.end(), vs2.begin()); // uses a loop calling copy constructors
}

四、使用场景

以下是 Tag Dispatching 在 C++ 中的一些典型应用场景：

1. 算法特化（Algorithm Specialization）：当算法对于不同的数据类型有不同的最优实现时，可以使用 Tag Dispatching 来提供特化的版本。例如，对于交换两个元素的操作，对于基本类型可能需要三次拷贝操作，但对于像 std::vector 这样的容器类型，可以直接使用其成员函数 swap 来避免拷贝，从而提高效率。
2. 迭代器类型的优化：在 STL 中，不同的容器类型具有不同类型的迭代器（如输入迭代器、前向迭代器、双向迭代器和随机访问迭代器）。对于某些算法，根据迭代器的类型选择最优的实现方式可以提高效率。通过使用 Tag Dispatching，可以为不同类型的迭代器提供特化的算法实现。
3. 类型属性的判断：当需要根据类型的某些属性（如是否为整数类型、是否支持某种操作等）来选择不同的行为时，可以使用 Tag Dispatching。通过定义与这些属性相关的标签类型，并在函数模板中使用这些标签作为参数，可以在编译时根据类型属性选择正确的实现。
4. 编译时条件判断：在某些情况下，可能需要在编译时根据某些条件选择不同的函数实现。通过使用 if constexpr 和 Tag Dispatching，可以在编译时根据条件选择并执行相应的函数模板。
5. 模板元编程：Tag Dispatching 在模板元编程中也有广泛应用。通过定义与类型特征相关的标签类型，并在模板元函数中使用这些标签作为参数，可以在编译时根据类型特征执行不同的元编程逻辑。
6. 类型安全的接口设计：在设计类型安全的接口时，可以使用 Tag Dispatching 来确保函数只接受特定类型的参数。通过定义与参数类型相关的标签类型，并在函数模板中使用这些标签作为参数，可以在编译时检查参数类型，从而提高代码的类型安全性。