|
|
I.背景
C++在很多人的心目中，一直是一种OO语言，而事实上，现在对C++的非OO部分的各种使用被逐渐地挖掘出来，其中最大的部分莫过于是 template。STL、loki、boost， ，很多先行者为我们提供了方案，有的已经被列入C++标准的一部分。template的一个重要使用方法就是template meta programming，它利用编译器对于template的解释是静态的这一特性，让编译器在编译时做计算，可以有效的提高程序的运行速度。有关于 template meta programming的记载，最早见于Erwin Unruh，他在1994年写了一个用template计算质数的程序。我希望通过这篇文章介绍一些TMP的基本技巧和应用，并且最终完成一个质数计算程序。
（阅读本文的过程中，建议你试图编译每一个给出的程序。由于所有的类只需要public成员，所以都用struct声明，但是仍然称之为类。）
II.技术
通常我们编写一个（小）程序，需要的语言支持其实不必很多，只要有顺序、选择和循环三种控制结构理论上就可以写出大多数程序了。我们先用TMP建立一个简单的语言环境。
1.打印
程序有了结果，需要有一个方式反馈给运行者，这里我们利用C++的出错信息，建立一个打印函数。要知道我们希望一切都在编译的时候结束，那么我们就必须让C++编译器在编译信息里面告诉我们，所以我们利用编译器的出错信息。当然这只是一个trick，如果你的TMP只是程序的一部分，你可以使用正常的输入输出。
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
这个类，每当别人引用到它的result的时候，编译器就会打印出错信息，因为一个unsigned int是不能隐式的转成一个unsigned char*的。譬如下面这段程序
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
unsigned int test1 = print<77>::result;
unsigned int test2 = print<123>::result;
在我的Dev C++里，会输出
main.cpp: In instantiation of `print<77>':
main.cpp:7: instantiated from here
main.cpp:4: invalid conversion from `unsigned char*' to `unsigned int'
main.cpp: In instantiation of `print<123>':
main.cpp:8: instantiated from here
main.cpp:4: invalid conversion from `unsigned char*' to `unsigned int'
这个输出虽然不是很好看，但也算是差强人意。
2.选择
Andrei Alexanderescu在他的大作Modern C++ Design里面使用过一个类，可以根据bool的值选择不同的类型。今天我们要写的一个是根据bool的值选择不同的整数。
template<bool condition, unsigned int value1, unsigned int value2>
struct template_if
{
static const unsigned int result = value1;
};
template<unsigned int value1, unsigned int value2>
struct template_if<false, value1, value2>
{
static const unsigned int result = value2;
};
这里用到了模板的特化，如果你对这个不熟悉，那么大致可以这样理解：第一个template_if的定义告诉编译器，“一般的” template_if，会选择第一个值作为结果。第二个template_if告诉编译器，如果第一个参数是false的话，我们就使用第二个值（第三个参数）作为结果。下面这段代码演示了template_if的用法。
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<bool condition, unsigned int value1, unsigned int value2>
struct template_if
{
static const unsigned int result = value1;
};
template<unsigned int value1, unsigned int value2>
struct template_if<false, value1, value2>
{
static const unsigned int result = value2;
};
template<unsigned int value>
struct print_if_77
{
static const unsigned int result = template_if<value == 77 , print<value>::result , 0>::result;
};
unsigned int test1 = print_if_77<77>::result;
unsigned int test2 = print_if_77<123>::result;
如果你去编译这段代码的话，你会发觉77和123都被打印出来了，虽然错误信息不一样，但是这不是我们想要的结果。为什么呢？很遗憾，对C++编译器来说，template_if<true, 1, 100>和template<true, 1, 200>是两个不同的类，虽然后一个参数的值我们并不关心，但是编译器必须在template初始化的时候，给出所有的参数，这就导致它会去计算 print<value>::result，当然，计算的结果就是报错。也就是说，因为编译器要计算这个值才导致了我们的print不可用，要解决这个问题，有两个方法：或者让编译器不计算这个值，或者让编译器在某些情况下可以计算出正确的值。
方法一可以让编译器不计算这个值，通过修改template_if，我们传入两个不同的类，而不是unsigned int。
首先修改print，加一个新的类dummy_print：
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct dummy_print
{
static const unsigned int result = value;
};
接着，加入一套对类型进行选择的模板：
template<bool condition, typename T1, typename T2>
struct template_if_type
{
static const unsigned int result = T1::result;
};
template<typename T1, typename T2>
struct template_if_type<false, T1, T2>
{
static const unsigned int result = T2::result;
};
这样原先的程序就变成：
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct dummy_print
{
static const unsigned int result = value;
};
template<bool condition, typename T1, typename T2>
struct template_if_type
{
static const unsigned int result = T1::result;
};
template<typename T1, typename T2>
struct template_if_type<false, T1, T2>
{
static const unsigned int result = T2::result;
};
template<unsigned int value>
struct print_if_77
{
static const unsigned int result = template_if_type<value == 77 ,
dummy_print<value> , print<value>>::result;
};
void main()
{
unsigned int test1 = print_if_77<77>::result;
//unsigned int test2 = print_if_77<123>::result;
}
现在的“运行结果”非常正确。
方法二可以让编译器在某些情况下计算出正确的值，我们加一套新的模板：
template<bool condition, unsigned int value>
struct print_if
{
static const unsigned int result = value;
};
template<unsigned int value>
struct print_if<false, value>
{
static const unsigned int result = (unsigned char*)value;
};
原先的程序变为：
template<bool condition, unsigned int value>
struct print_if
{
static const unsigned int result = value;
};
template<unsigned int value>
struct print_if<false, value>
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct print_if_77
{
static const unsigned int result = print_if<value == 77 , value>::result;
};
void main()
{
unsigned int test1 = print_if_77<77>::result;
//unsigned int test2 = print_if_77<123>::result;
}
输出也是正确的。
这两种方案，我个人倾向于后者，因为其实我们一定是要做一次判断的，并且这次判断一定会添加新的类，那么还是print_if的解决方案比较直观。
3. 循环
首先必须明确的是，template不可能实现我们一般意义上的循环，但是它可以做一件和循环类似的事情：迭代。
如果有这样一个循环：for( unsigned int i = 0 ; i < value ; ++i )
我们可以这样写：
template<unsigned int value>
struct loop
{
static const unsigned int result = loop<value - 1>::result + 1;
};
template<>
struct loop<0>
{
static const unsigned int result = 0;
};
这就是告诉编译器，我们的迭代从0开始，到value结束，每个值是前者加1。
下面给出一个更广泛的循环的实现：for( unsigned int i = begin ; i < end ; i = i + step )，假设0<=begin<end，并且step>0。（更复杂的情况，总可以通过template specialization分派完成）
template<unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct loop
{
static const unsigned int result = loop< begin + step, end, step>::result - step;
};
template<unsigned int begin, unsigned int end, unsigned int step>
struct loop<begin, end, step, false>
{
static const unsigned int result = begin;
};
这里的result的计算过程不重要，关键是为了驱动编译器进一步的实例化模板。
下面是一个实例程序，用来打印13到29之间的整数，步长为5。
template<bool condition, unsigned int value>
struct print_if
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct print_if<false, value>
{
static const unsigned int result = value;
};
template<unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct loop
{
static const unsigned int result = loop< begin + step, end, step>::result - step;
static const unsigned int print_result = print_if<true, result>::result;
};
template<unsigned int begin, unsigned int end, unsigned int step>
struct loop<begin, end, step, false>
{
static const unsigned int result = begin;
};
static unsigned int result = loop<13,29,5>::result;
III.应用
上面我已经介绍了怎样用TMP实现打印，选择和循环了，现在我们来把这些投入运用。下面我会用上面的所提供的机制，写两个程序：计算阶乘和计算质数。
1.计算阶乘
我们先写一个普通的C++程序来计算阶乘：
#include <iostream>
int main()
{
unsigned int limit = 10;
unsigned int factorial = 1;
for( unsigned int i = 1 ; i <= limit ; ++ i )
factorial *= i;
std::cout<<factorial<<std::endl;
}
这个程序是一个一重循环，我们就用循环来做：
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct loop
{
static const unsigned int result = loop< begin + step, end, step>::result * begin;
};
template<unsigned int begin, unsigned int end, unsigned int step>
struct loop<begin, end, step, false>
{
static const unsigned int result = begin;
};
static unsigned int result = print<loop<1, 10, 1>::result>::result;
因为这里不必要盘算是否输出，所以就直接用print了。
2.计算质数
同样，我们先写一个普通的程序来计算：
#include <iostream>
int main()
{
unsigned int limit = 30;
for( unsigned int i = 2 ; i <= limit ; ++i )
{
unsigned int j;
for( j = 2 ; j < i ; ++j )
if( i % j == 0 )
break;
if( i == j )
std::cout<<i<<std::endl;
}
}
这里用到了两层循环，而且还是用了分支和打印。用我们提供的机制转化成TMP形式如下：
template<bool condition, unsigned int value>
struct print_if
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct print_if<false, value>
{
static const unsigned int result = value;
};
template<bool condition, unsigned int value1, unsigned int value2>
struct template_if
{
static const unsigned int result = value1;
};
template<unsigned int value1, unsigned int value2>
struct template_if<false, value1, value2>
{
static const unsigned int result = value2;
};
// 这里增加一个i作为参数，因为在内循环也需要知道外部的i的值
template<unsigned int i, unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct inner_loop
{
static const unsigned int result = template_if<i % begin,
inner_loop< i, begin + step, end, step>::result,
begin>::result;
};
template<unsigned int i, unsigned int begin, unsigned int end, unsigned int step>
struct inner_loop<i, begin, end, step, false>
{
static const unsigned int result = begin;
};
template<unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct outer_loop
{
static const unsigned int result = outer_loop< begin + step, end, step>::result;
static const unsigned int is_prime = inner_loop<begin, 2, begin, 1>::result == begin;
static const unsigned int print_result = print_if<is_prime, begin>::result;
};
template<unsigned int begin, unsigned int end, unsigned int step>
struct outer_loop<begin, end, step, false>
{
static const unsigned int result = 0;
};
static unsigned int result = outer_loop<2, 30, 1>::result;
III.细节
另外有两点要说一下：
我们的template_if其实有一种更简单的写法，就是?:表达式。
而我们的print_if和print其实可以用确省的模板参数来统一，唯一的区别是，要把value放在condition前面。
template<unsigned int value, bool condition = true>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct print<value,false>
{
static const unsigned int result = value;
};
这样你可以用print<value>来打印一个数值，也可以用print<value, condition>来做判断打印。
IIII.后记
很久以前看Inside OLE2的时候，记得作者说过一句话：作者因为写书而明白。我其实几年前就写过类似的程序，但是从来没有对这样程序的写法进行过总结以至于每一次都是在重新开始。而写完这篇文章后，我觉得自己比过去明白很多。template meta programming还有很多不同的应用，我以后有机会会继续介绍给大家。
对于这篇文章有任何问题，请发信到 polyrandom@hotmail.com 和我联系，也请访问 http://www.allaboutprogram.com/ 以获得最近的更新。
|