Understanding variadic templates

GP and Templates（泛型编程与模板）

现实中许多问题错综而复杂，解决起来极为不易。

人们发现可以将这些问题拆解成更小的问题来进行解决。往往当把问题拆解到最小模块的时候，便能对问题产生新的理解。

能解决问题的根本在于：问题整体可分解为部分，部分可组成为整体，整体等于部分之和。这是还原论的思想，在编程世界叫作分治策略，实现手法分为迭代和递归。

向下拆分，向上总结，就能把一个大问题化为许多小问题，通过解决一个个小问题，最终就能解决整个大问题。

解决之时，需要描述问题的数据和关系。

在C++中，用面向对象来表示事物的整体结构，用数据结构来表示数据之间的关系，用算法来表示具体的逻辑实现。

数据有类型之分，而不同的问题可能本质上实为同类问题，这便导致每次遇到同类问题，还得提供不同类型版本的解法。

因此数据和方法应该进行分离，对数据进行更高层次的抽象。

面向对象编程的目的是将数据和方法关联起来，而为了分离数据和方法之间的依赖，出现了泛型编程。

泛型编程本质上就是对数据类型的高度抽象，使同一个方法能作用到不同的类型，为同类问题提供了一个通解。

C++泛型编程所提供的支持组件便是模板，而Variadic Templates（可变参数模板/可变模板参数），顾名思义，就是支持任意个数、任意类型的模板。

对于一类问题，若发现变化的永远是输入，而解决方法始终不变，便可以使用可变参数模板定义通解。

这个通解，就是问题的「最小模块」，通过迭代或递归，分多次解决分解后的小问题，最终就能解决整个问题。

然而迭代需要持有一个迭代器并改变它，直到某个条件符合。泛型编程发生于编译期，编译期中的整数计算（如enum）或是typedef（using）的类型定义之后就无法进行改变。所以迭代虽然比递归表示起来更加自然，却无法进行实现。

递归符合一切编译期编程的要求，所以可变参数模板由其实现。

由于递归本身的特性，再结合可变参数模板，使得理解起来极为不易。因为你无法看到实际的结果，对于无法看到的东西，理解起来总是比较困难的。

Ellipsis operator and Parameter pack（省略操作符与参数包）

先来看一个简单的可变参数模板示例：

template <class... Args>
void func(Args... args)
{
    std::cout << sizeof...(args) << std::endl;
}

... 叫做省略操作符（ellipsis operator），用以表示任意个参数，带省略号的参数称为参数包（Parameter pack）。

当省略操作符出现在参数名（args）左边时，标示着参数是一个参数包；出现在参数名右边时，用于扩展参数包。因为我们无法直接获取参数包 args 中的每个参数，所以只能通过展开的方式来获取，那么如何展开参数包就成了难点所在。

现在 func 函数可以接受任意个参数：

func<> f1;  // 0个参数
func<int> f2;  // 1个参数
func<int, float, string> f3;  // 3个参数
func<long, vector<int>, string, bool> f4;  // 4个参数
// ...etc.

若想知道可变参数模板中的参数个数，可以借助 sizeof...() 操作符（不是 sizeof）。一般情况下并不会使用该操作符，只有当你想要对参数包中的某个参数进行特殊处理的情况下才需要使用。

Function template and Class template（函数模板和类模板）

函数模板和类模板都支持可变参数模板，可以称它们为可变参数函数模板和可变参数类模板，不过，统称为可变参数模板。

在可变参数模板中，变化得不仅仅是参数的个数，还有参数的类型。

利用参数逐一递减的特性，可以使用每个不同类型参数，这个展开参数的过程，是可变参模板的核心所在。

如前文所述，在泛型编程中的拆解问题的手法依赖于递归，而由于函数模板不支持偏特化，所以它与类模板展开参数包的方式也不尽相同。

Function template

我们先来看如何使用可变参数函数模板。

程序开发中，免不了需要调试，比如一个游戏程序，在客户端运行时需要收集日志，方便后期跟踪调试。

平时大家都喜欢用 printf 调试法，直接将调试信息输出到控制台窗口上。可惜的是，若程序为Win32窗体程序，这种方法便没用，因为没有控件台用于输出。而若在MSVC调试器之下运行程序，可以使用 OutputDebugString 函数，向MSVC的调试主控台打印信息。

为方便打印，使用起来需要向 printf 那样简单，所以可以用可变参数函数模板来实现：

#include <Windows.h>
#include <stdio.h>

template <typename... Args>
int DebugPrintF(const char* format , Args... args)
{
    const unsigned int MAX_CHARS = 1023;
    static char buffer[MAX_CHARS + 1];

    int charsWritten = snprintf(buffer, MAX_CHARS, format, args...);
    buffer[MAX_CHARS] = '\0';

    OutputDebugString(buffer);
    return charsWritten;
}

int main() {
    DebugPrintF("[%s] [%s] %s:%d %s %dh", "2020-04-20 19:45:00", "INFO", "127.0.0.1:", 8006, "online time:", 3);
}

这种实现的确可以使用，然而你发现还是使用 snprintf，相当于仅是换身衣服罢了。

若不想用这种实现，那么来看第二种实现：

void PrintToSomewhere(const char* value)
{
    OutputDebugString(value);
}

void PrintToSomewhere(int value)
{
    char buf[20];
    _itoa_s(value, buf, 10);
    OutputDebugString(buf);
}

void PrintToSomewhere(const char value)
{
    char buffer[2];
    buffer[0] = value;
    buffer[1] = '\0';
    OutputDebugString(buffer);
}

template <typename T>
void DebugPrintF(T s)
{
    while (*s)
    {
        if (*s == '%' && *(++s) != '%')
            throw std::runtime_error("invalid s string: missing arguments");
        //std::cout << *s++;
        PrintToSomewhere(*s++);
    }
}

template <typename T, typename... Args>
void DebugPrintF(const char* s, T value, Args... args)
{
    while (*s)
    {
        if (*s == '%' && *(++s) != '%')
        {
            // 输出到指定位置
            PrintToSomewhere(value);

            DebugPrintF(++s, args...);
            return;
        }
        //std::cout << *s++;
        PrintToSomewhere(*s++);
    }
    throw std::logic_error("extra arguments provided to DebugPrintF");
}

该版本改自网上流传的一个使用可变参数模板实现 printf 的例子，这里职责分为两个：

1. 抓出传进来的参数
2. 进行输出

DebugPrintF负责第一个任务，它只需要将传进来的东西一个一个地抓出来，实际的输出任务交给 PrintToSomewhere，这个函数可以自由实现，可以自定义输出流，不论是文件也好，绘图也罢，都取决于具体的需求。

所以这里不关心 PrintToSomewhere，主要来看 DebugPrintF。

它分成两个版本，一个参数的版本用于终止递归，三个参数的版本用于完成主要任务。

三个参数的版本中，第一个参数为格式化字符串，第二个参数为实际的首个参数，参数包为其余的实际参数。

每次进来，都会检查格式化字符，将其替换为实际字符。输出后，指针后移，循此往复，以递归来不断分解问题，最终，来到一个参数的版本，标示问题解决。

Class template

因为类模板支持偏特化，所以可变参类模板可以利用该特性来展开参数包。

还是先来看一个简单的例子，这个例子用于获得参数包中参数类型的大小之和，类型可以是任意个：

template <typename... Args> struct TypeSize;

template <typename Last>
struct TypeSize<Last>
{
    enum { value = sizeof(Last) };
};

template <typename First, typename... Args>
struct TypeSize<First, Args...>
{
    enum { value = TypeSize<First>::value + TypeSize<Args...>::value  };
};

之后可以这样使用：

TypeSize<int>::value;  // value: 4
TypeSize<int, double, bool>::value;  // value: 13
TypeSize<std::string, float>::value;  // value: 36
TypeSize<std::string>::value;  // value: 32

这里利用了 C++ 泛型编程的工具之一：编译期整数计算。再加上递归，便能在编译期完成计算类型大小的工作。

因为我们的递归终止条件中有一个参数，所以 TypeSize 无法接受0个模板参数，实际上，那样也毫无意义。

当然，若你执意如此，也未为不可，递归的终止条件完全由你决定，比如上面的递归终止条件还可以写成这样：

// 0个参数终止
template <>
struct TypeSize<>
{
    enum { value = 0 };
};

// 2个参数终止
template <typename First, typename Second>
struct TypeSize<First, Second>
{
    enum { value = sizeof(First) + sizeof(Second) };
};

// ...etc.

我们还可以使用 C++11 的 integral_constant 来消除 enum：

template<typename First, typename... Args> struct TypeSize;

template <typename First, typename... Args>
struct TypeSize<First, Args...> 
        : std::integer_constant<int, TypeSize<First>::value + TypeSize<Args...>::value>
{};

template<typename Last>
struct TypeSize<Last> : std::integer_constant<int, sizeof(Last)>
{};

TypeSize<int, double, short>::value; // output: 14

interal_constant 可以包覆任意类型的一个静态常量，它的定义如下：

template<class T, T v>struct integral_constant {
    static constexpr T value = v;
    using value_type = T;
    using type = integral_constant; // using injected-class-name
    constexpr operator value_type() const noexcept { return value; }
    constexpr value_type operator()() const noexcept { return value; } //since c++14
};

通过其中的编译期静态常量 value，便能以递归的方式得到每个类型的大小，使用方式和上面的方式完全一样。

Recursive inheritance（递归继承）

boost 中有一个工具—— tuple（元组），可以存放任意类型的多个数据，C++11 中也加入了 tuple。

这个东西就是用可变参数模板实现的（可变参数模板是 C++11 才支持的，boost 中的 tuple 并非采用可变参数模板实现，它的 tuple 默认支持最多十个模板参数，可以满足绝大多数应用。）

本节不是要讨论 tuple 的用法，也不是要研究 tuple 的源码，而是要利用可变参数模板实现出一个自己的 Tuple。虽不算完善，却也包含了主要的技术。

我们先来看看 tuple 的用法：

typedef tuple<int, double, string> my_tuple;
my_tuple t(1, 2.7, "blah blah...");
t.get<0>();  // 1
t.get<1>();  // 2.7
t.get<2>();  // blah blah...

可以看到，它可以接受任意类型、任意个数的参数，并可以访问指定位置的参数内容。

因此，下面根据需求来进行实现：

template <typename... Types> class Tuple;
template<> class Tuple<> {}

template <typename Head, typename... Tail>
class Tuple<Head, Tail...> : private Tuple<Tail...>
{
    using TailType = Tuple<Tail...>;
public:
    Tuple() {}
    Tuple(Head v, Tail... vtails) : head_(v), TailType(vtails...) {}

protected:
    Head head_;

public:
    Head head() { return head_; }
    TailType& tail() { return *this; }
};

在这短短的几行代码中，包含的诸多技巧，我们从上到下依次来看。

1. Tuple 支持可变参数的模板，因此可以接受任意个数、任意类型的参数。
2. 通过特化，提供了空类型的 Tuple<>，该类型可用于终止递归。
3. 主版本的 Tuple，将传递进来的参数分为第一个和其余个（1, N）。这样每次传递进来的参数会依次减少，达到遍历所有参数的效果。
4. 主版本的 Tuple 通过私有继承，递归式地继承自后一个 Tuple，也就是参数逐次递减的下一个 Tuple，我们将其称为尾部 Tuple。
5. 私有继承表示 has-a 关系，继承其实现；公有继承表示 is-a 关系，继承其接口。表示父子关系或访问接口时使用公有继承，此处应该是 has-a 关系，所以使用私有继承。
6. 因为要访问传入的数据，所以必须添加一个成员变量来进行保存，这个变量为 head ——每次传入 Tuple 中的第一个参数类型所定义的数据。
7. 利用 head() 来访问传入的数据，利用 tail() 来访问其余的数据。

我们需要对每个传入的参数都定义数据，但却不能对每个类型都定义一个偏特化版本来满足需求。

针对这种情况，有一个令人拍案叫绝的技巧，就是利用继承和递归来依次展开参数，这样就会层层往上继承，最终继承到 Tuple<>，这个技巧就称为「递归继承」。

举个例子，假如我们使用了 Tuplet(1, 2.0, "blah blah...")，那么展开后就是这样的：

------------------------------
Tuple<>                      |
------------------------------
↑
------------------------------
Tuple<string>                |
string head_("blah blah...");|
------------------------------
↑
------------------------------
Tuple<float, string>         |
float head_(2.0);            |
------------------------------
↑
------------------------------
Tuple<int, float, string>    |
int head_(1);                |
------------------------------

别看我们才写了几行代码，实际使用时通过「递归继承」可以自动产生成百上千行的代码。

索引式访问Tuple

可以通过 head 和 tail 来访问 tuple 保存的数据：

void TupleTest()
{
    Tuple<int, float, std::string> t(10, 2.0, "blah blah...");
    std::cout << "sizeof(t):" << sizeof(t) << std::endl;

    std::cout << t.head() << std::endl;
    std::cout << t.tail().head() << std::endl;
    std::cout << t.tail().tail().head() << std::endl;
}

输出如下：

呵！虽然现在可以访问，但由于这种方式访问会出现 tail() 的多次调用，若参数非常长，用这种方式访问是不切实际的，所以需要通过别的方式来提供访问接口。

这种问题有多种解决方案，统称为「索引式访问」。只需提供一个索引，就能返回指定位置的数据。

让我们先来观察现在的访问方式是如何实现的：

TailType& tail() { return *this; }

TailType 是 （1，N）个参数中后 N 个参数的 Tuple 类型，当前 Tuple 继承自 TailType。

那么返回当前 this 指针给上层 Tuple，就会发生强制类型转换，当前 Tuple 转换为 TailType，这样当前 Tuple 的 head_ 成员就会消失，只有上层 Tuple 的 head_。此时通过 head() 调用得到的是上层 Tuple 的 head_，也就是第二个参数。

如此递归，就能访问所有元素。

可以看到，核心是类型向上转换，那么我们只要获得指定索引的 Tuple 类型，就能直接把当前 Tuple 强制转换成需要的类型，从而访问元素。

开始提供索引式访问之前，我们需要修改 Tuple 类如下：

template <typename... Types> class Tuple;
template<> class Tuple<> {};

template <typename Head, typename... Tail>
class Tuple<Head, Tail...> : public Tuple<Tail...>
{
    using ValueType = Head;
    using ReferenceType = Head&;
    using ThisType = Tuple<Head, Tail...>;
    using TailType = Tuple<Tail...>;

public:
    Tuple() {}
    Tuple(Head v, Tail... vtails) : head_(v), TailType(vtails...) {}

    ReferenceType head() { return head_; }
    //TailType& tail() { return *this; }

protected:
    ValueType head_;
};

除了增加一些类型定义外，最大的一点改变在于将私有继承改成了公有继承。

各位应该都知道，私有继承的子类是无法向基类转型的。而在前面的 Tuple 实现中，却是私有继承，那么为何它在 tail() 返回时能向上转型呢？

前面的 Tuple 实现使用 public 继承也是完全可以的，之所以没那么写，是我想在这里强调一下私有继承。

一个简单的例子：

class A {};
class B : private A 
{
public:
    void test()
    {
        A& a = *this;  // ok! B cast to its private base class A
    }
};

B b;
A& a = b;  // error! cannot cast B to its private base class A

不知你曾经是否迷惑过这二者之间的不同？

假想一下，母亲（A）传给小短腿（B）一份秘制菜谱，并嘱咐他不要泄露给别人。那么小短腿就只能做菜给小伙伴吃，而不能告诉具体的做法。外人不知道做法，而小短腿自己是知道的。所以他自己可以拥有菜谱，外人可以吃他做出来的菜，却无法得到菜谱。

所以第一种情况可以转换，第二种情况无法转换。

而现在我们要提供的索引式访问是在外部，要想也拥有转型的能力，那么就得使用公有继承，所有人共享菜谱。

回顾一下，只要知道指定位置的 Tuple 类型，就能进行转换，从而访问到数据。

因为是对类型进行操作，所以要使用类模板。

定义 TupleAt，获取类型，如下：

template <std::size_t I, typename... TList> struct TupleAt;

template <std::size_t I, typename T, typename... TList>
struct TupleAt<I, Tuple<T, TList...>>
{
    using ValueType = typename TupleAt<I - 1, Tuple<TList...>>::ValueType;
    using TupleType = typename TupleAt<I - 1, Tuple<TList...>>::TupleType;
};

template <typename T, typename... TList>
struct TupleAt<0, Tuple<T, TList...>>
{
    using ValueType = T;
    using TupleType = Tuple<T, TList...>;
};

template<>
struct TupleAt<0, Tuple<>>
{
    using ValueType = Tuple<>;
    using TupleType = Tuple<>;
};

TupleAt 有两个模板参数，一个是 size_t 类型，用于表示索引；另一个是可变参数模板。

ValutType 表示 Tuple 中的数据类型，TupleType 表示 Tuple 的类型。同样从（1，N）依次递归，由索引进行控制递归次数，当索引递减至 0，就能获得欲访问位置的数据和 Tuple 类型。

而这只是类型，我们要提供接口给用户使用，因为要对具体的数值进行操作，所以应该使用函数模板。

定义访问接口如下：

template <std::size_t I, typename... TList>
typename TupleAt<I, Tuple<TList...>>::ValueType&
TupleGet(Tuple<TList...>& tuple)
{
    using TupleType = Tuple<TList...>;
    using BaseTupleType = typename TupleAt<I, TupleType>::TupleType;

    return static_cast<BaseTupleType&>(tuple).head();
}

外部接口只需简单的进行转换，真正的工作由 TupleAt 进行完成。若 Tuple 是私有继承，此处的转换会报错。

现在可以这样使用：

void TupleTest()
{
    Tuple<int, float, std::string> t(10, 32.0, "blah blah...");
    std::cout << "sizeof(t):" << sizeof(t) << std::endl;

    // std::cout << t.head() << std::endl;
    // std::cout << t.tail().head() << std::endl;
    // std::cout << t.tail().tail().head() << std::endl;

    std::cout << TupleGet<0>(t) << std::endl;
    std::cout << TupleGet<1>(t) << std::endl;
    std::cout << TupleGet<2>(t) << std::endl;
}

Recursive composition（递归复合）

最后，小作补充，除了「递归继承」，上述 Tuple 也可以使用「递归复合」来完成。

「递归复合」不需要继承，直接在当前类中进行递归展开，实现起来如下：

template <typename Head, typename... Tail>
class Tuple<Head, Tail...>
{
public:
    using ValueType = Head;
    using ReferenceType = Head&;
    using ThisType = Tuple<Head, Tail...>;
    using TailType = Tuple<Tail...>;

    Tuple() {}
    Tuple(Head v, Tail... vtail) : head_(v), tail_(vtail...) {}

    ReferenceType head() { return head_; }
    TailType& tail() { return tail_; }

protected:
    TailType tail_;
    ValueType head_;
};

注意这里的增加了一个 TailType 的成员 tail_，这是（1，N）中的后 N 个参数组成的 Tuple，在递归继承中是继承这部分的，而递归复合是直接在当前类中原地展开。

标准中用的是递归继承，这里的区别在于：递归继承有继承关系，可以进行向上转换；而递归复合中的每个 Tuple 类型都不相同，无法通过直接转换类型来进行索引式访问。

也就是说，递归复合中的 tail() 函数所返回的类型每次都不一样，第一样访问你用 auto tail = tuple.tail()，而第二次再调用 tail = tail.tail()，就会产生返回类型不同的问题。

这意味着之前靠强制转换而实现的索引式访问，在这里会失效。

我们可以使用 typeid 来查看具体的类型：

Tuple<int, float, std::string> t(10, 32.0, "blah blah...");

std::cout << "sizeof(t):" << sizeof(t) << std::endl;

std::cout << typeid(decltype(tuple)).name() << std::endl;
std::cout << typeid(decltype(tuple.tail())).name() << std::endl;
std::cout << typeid(decltype(tuple.tail().tail())).name() << std::endl;

输出如下：

这里推荐使用递归继承，处理和理解起来都要容易些。

总结

可变参数模板是一把威力巨大的宝刀，通过它可以实现一些特别有用的组件，但好刀不是轻易就能使的，需要掌握许多技巧，才能真正发挥它的威力。

我们可以在函数模板和类模板上使用可变参模板，二者都依赖于递归实作，而具体手法又有所不同。

函数模板处理的是数值，依赖于递归调用。若要对具体的数值进行处理，则使用函数模板。

类模板处理的是类型，依赖于两种手法：递归继承或递归复合。若要对类型进行操作，则使用类模板。

二者也可以协作使用，通过类模板在内部处理类型，外部接口则为函数模板，递归继承的索引式访问便是如此实现的。

为了实现一些强大的组件，往往要用到一些精妙的技巧，高超的手法。而这也导致仅仅几行代码，就包含了大量的信息，不易理解，得慢慢消化理解。

实际上，可变参数模板在标准库中已经被广泛使用了，例如一些算法或容器，里面包含着更多的技术和细节，以后再来带大家来剖析一些相关的源码。