阅读这篇文章需要了解基本的 C++ 模板语法规则, 以及模板的泛化, 偏特化, 当然还包括完全特化这些基本概念. 这篇文章将给出基于 C++ 模板的 Metaprogramming 程序设计中需要注意的事项以及渐进式设计思路.
0. 基础
这一段介绍 Metaprogramming 基础, 包括模板模式匹配规则, 使用模板实现循环或分支的基本方法. 对 Metaprogramming 已经有了解的同学可以跳过这一段.
本质上来说, 现代计算机的核心任务是数值计算, 周边任务是 I/O. 现代几个主流的编程语言, 如 C/C++/Java, 它们的语法组织方式与现代计算机的主流体系结构是 "平行" 的, 即, 语句的先后顺序表示它们的逻辑顺序, 而这种顺序与人的一贯思维顺序又是相同的 (在计算机中表达式的计算顺序会与书写顺序稍有不同, 但却很符合人类的思路); 可以说这是什么样的爹生什么样的崽, 什么样的人造什么样的语言和计算机.
然而, 在 C++ 模板世界中, 这个规则被打破了. 从分类上来说, Metaprogramming 更类似于函数式编程, 而不是传统的 C++ 程序设计. 在这个异世界中, 程序员不被允许使用循环或者分支语句, 包括函数返回语句都不允许: 在函数式编程中起码还有函数返回, 而在 Metaprogramming 中, 由于一切函数都没有被调用 (还在编译呢), 因此一切的值都谈不上返回, 它们只是存在于模板符号表中, 一旦编译结束便烟消云散.
当然, 没有循环, 分支这些编程语言中的基本元素, 并不意味着程序员只被允许设计顺序程序. 只不过, 在这里, 一切分流动作都被转化为了另一个语言特性: 模式匹配. (这一点与函数式编程非常相似)
下面一段代码展示了模式匹配的威力:
#include <iostream>
template <unsigned I>
struct limit_to_2
{
static unsigned const R = 2;
};
template <>
struct limit_to_2<1>
{
static unsigned const R = 1;
};
template <>
struct limit_to_2<0>
{
static unsigned const R = 0;
};
int main(void)
{
std::cout << limit_to_2<0>::R << std::endl;
std::cout << limit_to_2<1>::R << std::endl;
std::cout << limit_to_2<2>::R << std::endl;
std::cout << limit_to_2<3>::R << std::endl;
return 0;
}模板 limit_to_2 为传入的整数设置了一个上限, 当传入模板的参数为 0 或者 1 时内部定义的 R 值与参数相同, 否则将 R 设置为 2. 这看起来很像是 switch-case 语句, 0 和 1 分别是两个 case, 而未特化的模板则是 default.
但是, 这样做有一些不方便, 如果所设的上限非常高, 那岂不是要为低于限制的情况写很多特化? 所以引入分支是非常必要的. 下面这个例子展示了如何利用模式匹配来实现编译期分支:
#include <iostream>
template <bool reach_upboundary, unsigned I> struct limit_branch;
template <unsigned I>
struct limit_to_100
{
static unsigned const R = limit_branch<100U < I, I>::R;
};
template <unsigned I>
struct limit_branch<true, I>
{
static unsigned const R = 100U;
};
template <unsigned I>
struct limit_branch<false, I>
{
static unsigned const R = I;
};
int main(void)
{
std::cout << limit_to_100<98>::R << std::endl;
std::cout << limit_to_100<99>::R << std::endl;
std::cout << limit_to_100<100>::R << std::endl;
std::cout << limit_to_100<101>::R << std::endl;
return 0;
}在程序的开始定义了模板 limit_branch, 但并没有实现它. 它的两个特化实现在后面. 当其中的 bool 参数为真时表示达到上界.
小心使用大于号! 尝试将上面的程序中, limit_to_100 中的定义改为
static unsigned const R = limit_branch*<I >* 100U, I>::R;这时大于号被当作右尖括号, 编译器会吐出一个尴尬的模板编译错误.
Metaprogramming 中循环的秘诀在于递归, 而不是将循环拆分成分支和跳转. 下面来展示一个典型的循环:
#include <iostream>
template <bool reach_upboundary, unsigned I> struct limit_branch;
template <unsigned I>
struct limit_to_100
{
static unsigned const R = limit_branch<100U < I, I>::R;
};
template <unsigned I>
struct limit_branch<true, I>
{
static unsigned const R = 100U;
};
template <unsigned I>
struct limit_branch<false, I>
{
static unsigned const R = I;
};
template <unsigned I>
struct loop_print
{
static inline void print()
{
loop_print<I - 1>::print();
std::cout << limit_to_100<I>::R << std::endl;
}
};
template <>
struct loop_print<0>
{
static inline void print()
{
std::cout << 0 << std::endl;
}
};
int main(void)
{
loop_print<120>::print();
return 0;
}在这段程序中, loop_print 将递归调用另一模板实例 print 函数, 直到参数匹配 0, 这时模板特化中的函数之输出, 退出递归.
这里出现了一个问题: 如果不设置退出条件, 编译器会死循环吗? 当然, 聪明的编译器会设置一个递归深度阈值, 当模板递归太深时直接认为发生了模板实例化发生错误, 这一点比运行时程序默默无闻地死循环要好一些. (对应地, 也会出现本来不该死的情况就死了. 停机问题不可解, 谁知道呢~)
说到死循环, 忘记特化退出条件的情形应该是很少的. 但是, C++ 中的隐患也是出名的多 (继续诅咒标准委员会吧), 在模板方面很不可思议的一点是, 条件短路失灵了! 如下程序:
#include <iostream>
template <int I>
struct inf
{
static bool const R = I < 100 && inf<I + 1>::R;
};
int main(void)
{
inf<120>::R;
return 0;
}看起来人畜无害, 因为传入的参数会使得表达式 I < 100 不成立, 那么按理来说后面的条件不会再被计算. 然而这段程序会让大多数编译器出错. 另外, 三目运算符也不靠谱:
#include <iostream>
template <int I>
struct inf
{
static bool const R = I < 100 ? inf<I + 1>::R : false;
};
int main(void)
{
inf<120>::R;
return 0;
}要跳出这个困境只能添加额外的分流模板来解决, 如
#include <iostream>
template <int I>
struct inf
{
template <bool Cond, int II> struct branch;
static bool const R = branch<I < 100, I>::R;
template <int II>
struct branch<true, II>
{
static bool const R = inf<II + 1>::R;
};
template <int II>
struct branch<false, II>
{
static bool const R = false;
};
};
int main(void)
{
inf<120>::R;
return 0;
}甚至不可以去掉 branch 的参数 II, 因为内部模板特化不允许引用外部模板参数!
1. 渐进设计
假设现在要设计一个程序, 在编译期计算前 N 个素数之和. 为了完成这个任务, 先列出一份清单:
- 测试给定的整数是不是素数, 即实现一个模板
template <int N>
struct is_prime
{
static bool const YES /* 是的, 参数是一个素数 */ ;
};- 根据上面这个模板, 实现一个模板, 告诉我们第 N 个素数是多少
template <int N>
struct the_Nth_prime
{
static int const P /* 第 N 个素数的值 */;
};- 写一个循环, 咳, 写一个递归, 计算前 N 个素数之和
template <int N>
struct sum_first_Nth_primes
{
static int const S /* 前 N 个素数之和 */;
};如此, 大业可图矣.
2. 筛子
作为优雅的程序员可不能给 is_prime 构造很多个偏特化来暴力枚举素数, 而是使用筛法来完成素数判断工作, 而 is_prime 只是一个壳而已.
要准确而完备地找出素数, 还是必须使用传统的暴力试除法: 给定整数 N, 从第 1 个素数 2 开始, 将每个素数作为被除数进行试除, 如果除得余数为 0 则判定 N 不是素数, 如果除到大于或等于某个值的素数仍然除不尽, 那么这个数就是素数. 现在的问题是, 那个 "某个值" 选取多少呢? 为了不让程序复杂到 "好吧我们再来实现编译时求近似平方根" 这种问题, 可以考虑将它简单地定为 N 的一半.
因为现在是在验证整数 N 是否是素数, 那么, 正如数学归纳法一样, 可以认为对于小于 N 的整数, is_prime<N> 都已经实现了, 并且已经统计出小于 N 的素数中有 PrimeNo 个数是素数, 当然, the_Nth_prime<PN>::P 对于所有 PN <= PrimeNo 也都实现了. 为筛的过程画个简易流程图:
PrimeNo = 1:
N / 2 < the_Nth_prime<PN>::P ?
=> NO: N is a prime! END loop
=> YES: N % the_Nth_prime<PN>::P reminds 0 ?
=> YES: N is NOT a prime!
=> NO: PrimeNo += 1, continue loop为了完成筛过程, 需要两个参数: PrimeNo 和 N
template <int PrimeNo, int N>
struct prime_verify
{
static bool const BINGO /* 是素数 */;
};而流程图中的两个分支语句需要实现为两个分流模板, 分流模板需要与筛子模板相同的参数以完成递归, 那么可以考虑这样设计判断除法是否有余数的分流模板:
template <bool NoReminder, int PrimeNo, int N>
struct verify_branch_no_rem;它的两个偏特化的实现为
template <int PrimeNo, int N>
struct verify_branch_no_rem<false, PrimeNo, N>
{
/* 继续向上递归 */
static bool const R = prime_verify<PrimeNo + 1, N>::BINGO;
};
template <int PrimeNo, int N>
struct verify_branch_no_rem<true, PrimeNo, N>
{
/* 整除了! 不是素数 */
static bool const R = false;
};另一分流模板, 验证是否到达上界, 可以这么干:
template <bool Reached, int PrimeNo, int N>
struct verify_branch_reach_upbdr;
template <int PrimeNo, int N>
struct verify_branch_reach_upbdr<false, PrimeNo, N>
{
static bool const R = /* 调用 verify_branch_no_rem 分流 */
verify_branch_no_rem<0 == N % the_Nth_prime<PrimeNo>::P,
PrimeNo, N>::R;
};
template <int PrimeNo, int N>
struct verify_branch_reach_upbdr<true, PrimeNo, N>
{
/* 达到上界! 是素数 */
static bool const R = true;
};实现 `prime_verify`:
template <int PrimeNo, int N>
struct prime_verify
{
static bool const BINGO = /* 调用 verify_branch_reach_upbdr 分流 */
verify_branch_reach_upbdr<N / 2 < the_Nth_prime<PrimeNo>::P,
PrimeNo, N>::R;
};最外面的壳 is_prime 的实现很简单:
template <int N>
struct is_prime
{
/* 从第 1 个素数开始验证 */
static bool const YES = prime_verify<1, N>::BINGO;
};当然, 别忘了偏特化, 为最小的几个数进行偏特化当然是必要的了:
template <>
struct is_prime<1>
{
static bool const YES = false;
};
template <>
struct is_prime<2>
{
static bool const YES = true;
};3. 嗅探第 N 个素数
仍然用递推方法, 假定现在前 (N - 1) 个素数都计算出了 (即, 模板 the_Nth_prime 在参数介于 1 到 (N - 1) 闭区间内的所有特化都已经实例化了), 那么计算第 N 个素数, 则可以从 (the_Nth_prime<N - 1>::P + 1) 开始递推. 搜索下一素数的流程图如下
Num = the_Nth_prime<N - 1>::P + 1:
is_prime<Num>::YES ?
=> YES: return Num
=> No : Num += 1, continue loop很明显, 至少还需要一个分流模板来进行递归. 此外, `the_Nth_prime` 本身也只作为一个壳, 它的参数太少了, 难以进行递归操作. 设计如下:
template <bool UntilNowItMayBeAPrime, int Num>
struct seek_next_branch;
template <int Num>
struct seek_next_branch<true, Num>
{
/* 找到了. */
static int const N = Num;
};
template <int Num>
struct seek_next_branch<false, Num>
{
/* 继续嗅探 */
static int const N = seek_next_prime<Num + 1>::N;
};
template <int Num>
struct seek_next_prime
{
/* 分流 */
static int const N = seek_next_branch<is_prime<Num>::YES, Num>::N;
};那么最后把这些东西揉在一起, 就完成了任务:
template <int N>
struct the_Nth_prime
{
static int const P = seek_next_prime<the_Nth_prime<N - 1>::P + 1>::N;
};
template <>
struct the_Nth_prime<1>
{
/* 记得要偏特化这个 */
static int const P = 2;
};
template <int N>
struct sum_first_Nth_primes
{
static int const S = the_Nth_prime<N>::P
+ sum_first_Nth_primes<N - 1>::S;
};
template <>
struct sum_first_Nth_primes<1> /* 偏特化 */
{
static int const S = the_Nth_prime<1>::P;
};4. 一个完整的实例
#include <iostream>
template <int N> struct the_Nth_prime;
template <bool Reached, int PrimeNo, int N> struct verify_branch_reach_upbdr;
template <bool NoReminder, int PrimeNo, int N> struct verify_branch_no_rem;
template <int PrimeNo, int N>
struct prime_verify
{
static bool const BINGO =
verify_branch_reach_upbdr<N / 2 < the_Nth_prime<PrimeNo>::P,
PrimeNo, N>::R;
};
template <int N>
struct is_prime
{
static bool const YES = prime_verify<1, N>::BINGO;
};
template <>
struct is_prime<1>
{
static bool const YES = false;
};
template <>
struct is_prime<2>
{
static bool const YES = true;
};
template <bool UntilNowItMayBeAPrime, int Num> struct seek_next_branch;
template <int Num>
struct seek_next_prime
{
static int const N = seek_next_branch<is_prime<Num>::YES, Num>::N;
};
template <int N>
struct the_Nth_prime
{
static int const P = seek_next_prime<the_Nth_prime<N - 1>::P + 1>::N;
};
template <>
struct the_Nth_prime<1>
{
static int const P = 2;
};
template <int N>
struct sum_first_Nth_primes
{
static int const S = the_Nth_prime<N>::P + sum_first_Nth_primes<N - 1>::S;
};
template <>
struct sum_first_Nth_primes<1>
{
static int const S = the_Nth_prime<1>::P;
};
/* branch implementation */
template <int Num>
struct seek_next_branch<true, Num>
{
static int const N = Num;
};
template <int Num>
struct seek_next_branch<false, Num>
{
static int const N = seek_next_prime<Num + 1>::N;
};
template <int PrimeNo, int N>
struct verify_branch_reach_upbdr<true, PrimeNo, N>
{
static bool const R = true;
};
template <int PrimeNo, int N>
struct verify_branch_reach_upbdr<false, PrimeNo, N>
{
static bool const R =
verify_branch_no_rem<0 == N % the_Nth_prime<PrimeNo>::P,
PrimeNo, N>::R;
};
template <int PrimeNo, int N>
struct verify_branch_no_rem<false, PrimeNo, N>
{
static bool const R = prime_verify<PrimeNo + 1, N>::BINGO;
};
template <int PrimeNo, int N>
struct verify_branch_no_rem<true, PrimeNo, N>
{
static bool const R = false;
};
/* loop print */
template <int Prime, int SumOfThePrimes>
struct printz
{
private: printz();
};
template <int N>
struct loop_print
{
loop_print<N - 1> _1;
printz<the_Nth_prime<N>::P, sum_first_Nth_primes<N>::S> _2;
};
template <>
struct loop_print<0> {};
int main(void)
{
loop_print<10> _;
return 0;
}选一个报错能力强的编译器编译它, 然后会看到...
