上一讲我们简单介绍了模板的基本用法及其在泛型编程中的应用。这一讲我们来看一下模板的另外一种重要用途——编译期计算也称作“模板元编程”。编译期计算首先我们给出一个已经被证明的结论C 模板是图灵完全的 [1]。这句话的意思是使用 C 模板你可以在编译期间模拟一个完整的图灵机也就是说可以完成任何的计算任务。当然这只是理论上的结论。从实际的角度我们并不想、也不可能在编译期完成所有的计算更不用说编译期的编程是很容易让人看不懂的——因为这并不是语言设计的初衷。即便如此我们也还是需要了解一下模板元编程的基本概念它仍然有一些实用的场景并且在实际的工程中你也可能会遇到这样的代码。虽然我们在开篇就说过不要炫技但使用模板元编程写出的代码仍然是可理解的尤其是如果你对递归不发怵的话。好闲话少叙我们仍然拿代码说话template int n struct factorial { static const int value n * factorialn - 1::value; }; template struct factorial0 { static const int value 1; };上面定义了一个递归的阶乘函数。可以看出它完全符合阶乘的递归定义除了顺序有特定的要求——先定义才能特化——再加语法有点特别代码基本上就是这个数学定义的简单映射了。那我们怎么知道这个计算是不是在编译时做的呢我们可以直接看编译输出。下面直接贴出对上面这样的代码加输出printf(%d\n, factorial10::value);在 x86-64 下的编译结果.LC0: .string %d\n main: push rbp mov rbp, rsp mov esi, 3628800 mov edi, OFFSET FLAT:.LC0 mov eax, 0 call printf mov eax, 0 pop rbp ret我们可以明确看到编译结果里明明白白直接出现了常量 3628800。上面那些递归什么的完全都没有了踪影。如果我们传递一个负数给 factorial 呢这时的结果就应该是编译期间的递归溢出。如 GCC 会报告fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth to increase the maximum)如果把 int 改成 unsigned不同的编译器和不同的标准选项会导致不同的结果。有些情况下错误信息完全不变有些情况下则会报负数不能转换到 unsigned。通用的解决方案是使用 static_assert确保参数永远不会是负数。template int n struct factorial { static_assert( n 0, Arg must be non-negative); static const int value n * factorialn - 1::value; };这样当 factorial 接收到一个负数作为参数时就会得到一个干脆的错误信息error: static assertion failed: Arg must be non-negative下面我们看一些更复杂的例子。这些例子不是为了让你真的去写这样的代码而是帮助你充分理解编译期编程的强大威力。如果这些例子你都完全掌握了那以后碰到小的模板问题你一定可以轻松解决完全不在话下。回想上面的例子我们可以看到要进行编译期编程最主要的一点是需要把计算转变成类型推导。比如下面的模板可以代表条件语句template bool cond, typename Then, typename Else struct If; template typename Then, typename Else struct Iftrue, Then, Else { typedef Then type; }; template typename Then, typename Else struct Iffalse, Then, Else { typedef Else type; };If 模板有三个参数第一个是布尔值后面两个则是代表不同分支计算的类型这个类型可以是我们上面定义的任何一个模板实例包括 If 和 factorial。第一个 struct 声明规定了模板的形式然后我们不提供通用定义而是提供了两个特化。第一个特化是真的情况定义结果 type 为 Then 分支第二个特化是假的情况定义结果 type 为 Else 分支。我们一般也需要循环template bool condition, typename Body struct WhileLoop; template typename Body struct WhileLooptrue, Body { typedef typename WhileLoop Body::cond_value, typename Body::next_type::type type; }; template typename Body struct WhileLoopfalse, Body { typedef typename Body::res_type type; }; template typename Body struct While { typedef typename WhileLoop Body::cond_value, Body::type type; };这个循环的模板定义稍复杂点。首先我们对循环体类型有一个约定它必须提供一个静态数据成员cond_value及两个子类型定义res_type 和 next_typecond_value 代表循环的条件真或假res_type 代表退出循环时的状态next_type 代表下面循环执行一次时的状态这里面比较绕的地方是用类型来代表执行状态。如果之前你没有接触过函数式编程的话这个在初学时有困难是正常的。把例子多看两遍自己编译、修改、把玩一下就会渐渐理解的。排除这个抽象性模板的定义和 If 是类似的虽然我们为方便使用定义了两个模板。WhileLoop 模板有两个模板参数同样用特化来决定走递归分支还是退出循环分支。While 模板则只需要循环体一个参数方便使用。如果你之前模板用得不多的话还有一个需要了解的细节就是用 :: 取一个成员类型、并且 :: 左边有模板参数的话得额外加上 typename 关键字来标明结果是一个类型。上面循环模板的定义里就出现了多次这样的语法。MSVC 在这方面往往比较宽松不写 typename 也不会报错但这是不符合 C 标准的用法。为了进行计算我们还需要通用的代表数值的类型。下面这个模板可以通用地代表一个整数常数template class T, T v struct integral_constant { static const T value v; typedef T value_type; typedef integral_constant type; };integral_constant 模板同时包含了整数的类型和数值而通过这个类型的 value 成员我们又可以重新取回这个数值。有了这个模板的帮忙我们就可以进行一些更通用的计算了。下面这个模板展示了如何使用循环模板来完成从 1 加到 n 的计算template int result, int n struct SumLoop { static const bool cond_value n ! 0; static const int res_value result; typedef integral_constant int, res_value res_type; typedef SumLoopresult n, n - 1 next_type; }; template int n struct Sum { typedef SumLoop0, n type; };然后你使用 While::type::type::value 就可以得到 1 加到 10 的结果。虽然有点绕但代码实质就是在编译期间进行了以下的计算int result 0; while (n ! 0) { result result n; n n - 1; }估计现在你的头已经很晕了。但我保证这一讲最难的部分已经过去了。实际上到现在为止我们讲的东西还没有离开 C98。而我们下面几讲里很快就会讲到如何在现代 C 里不使用这种麻烦的方式也能达到同样的效果。编译期类型推导C 标准库在 头文件里定义了很多工具类模板用来提取某个类型type在某方面的特点trait[2]。和上一节给出的例子相似这些特点既是类型又是常值。为了方便地在值和类型之间转换标准库定义了一些经常需要用到的工具类。上面描述的 integral_constant 就是其中一个我的定义有所简化。为了方便使用针对布尔值有两个额外的类型定义typedef std::integral_constant bool, true true_type; typedef std::integral_constant bool, false false_type;这两个标准类型 true_type 和 false_type 经常可以在函数重载中见到。有一个工具函数常常会写成下面这个样子template typename T class SomeContainer { public: … static void destroy(T* ptr) { _destroy(ptr, is_trivially_destructible T()); } private: static void _destroy(T* ptr, true_type) {} static void _destroy(T* ptr, false_type) { ptr-~T(); } };类似上面很多容器类里会有一个 destroy 函数通过指针来析构某个对象。为了确保最大程度的优化常用的一个技巧就是用 is_trivially_destructible 模板来判断类是否是可平凡析构的——也就是说不调用析构函数不会造成任何资源泄漏问题。模板返回的结果还是一个类要么是 true_type要么是 false_type。如果要得到布尔值的话当然使用 is_trivially_destructible::value 就可以但此处不需要。我们需要的是使用 () 调用该类型的构造函数让编译器根据数值类型来选择合适的重载。这样在优化编译的情况下编译器可以把不需要的析构操作彻底全部删除。像 is_trivially_destructible 这样的 trait 类有很多可以用来在模板里决定所需的特殊行为is_arrayis_enumis_functionis_pointeris_referenceis_consthas_virtual_destructor…这些特殊行为判断可以是像上面这样用于决定不同的重载也可以是直接用在模板参数甚至代码里记得我们是可以直接得到布尔值的。除了得到布尔值和相对应的类型的 trait 模板我们还有另外一些模板可以用来做一些类型的转换。以一个常见的模板 remove_const 为例用来去除类型里的 const 修饰它的定义大致如下template class T struct remove_const { typedef T type; }; template class T struct remove_constconst T { typedef T type; };同样它也是利用模板的特化针对 const 类型去掉相应的修饰。比如如果我们对 const string 应用 remove_const就会得到 string即remove_const::type 等价于 string。这里有一个细节你要注意一下如果对 const char* 应用 remove_const 的话结果还是 const char*。原因是const char* 是指向 const char 的指针而不是指向 char 的 const 指针。如果我们对 char * const 应用 remove_const 的话还是可以得到 char* 的。简易写法如果你觉得写 is_trivially_destructible::value 和 remove_const::type 非常啰嗦的话那你绝不是一个人。在当前的 C 标准里前者有增加 _v 的编译时常量后者有增加 _t 的类型别名template class T inline constexpr bool is_trivially_destructible_v is_trivially_destructible T::value;template class T using remove_const_t typename remove_constT::type;至于什么是 constexpr我们会单独讲。using 是现代 C 的新语法功能大致与 typedef 相似但 typedef 只能针对某个特定的类型而 using 可以生成别名模板。目前我们只需要知道在你需要 trait 模板的结果数值和类型时使用带 _v 和 _t 后缀的模板可能会更方便尤其是带 _t 后缀的类型转换模板。通用的 fmap 函数模板你应当多多少少听到过 map-reduce。下面我们演示一个 map 函数当然在 C 里它的名字就不能叫 map 了其中用到了目前为止我们学到的多个知识点template template typename, typename class OutContainer vector, typename F, class R auto fmap(F f, R inputs) { typedef decay_tdecltype( f(*inputs.begin())) result_type; OutContainer result_type, allocatorresult_type result; for (auto item : inputs) { result.push_back(f(item)); } return result; }我们用 decltype 来获得用 f 来调用 inputs 元素的类型用 decay_t 来把获得的类型变成一个普通的值类型缺省使用 vector 作为返回值的容器但可以通过模板参数改为其他容器使用基于范围的 for 循环来遍历 inputs对其类型不作其他要求存放结果的容器需要支持 push_back 成员函数。下面的代码可以验证其功能vectorint v{1, 2, 3, 4, 5}; int add_1(int x) { return x 1; } auto result fmap(add_1, v);在 fmap 执行之后我们会在 result 里得到一个新容器其内容是 2, 3, 4, 5, 6。内容小结本讲我们介绍了模板元编程的基本概念和例子其本质是把计算过程用编译期的类型推导和类型匹配表达出来然后介绍 type traits 及其基本用法最后我们演示了一个简单的高阶函数 map其实现中用到了我们目前已经讨论过的一些知识点。