C++ 的另一个新世界
C++ 的 MetaProgramming
废话就不说了, 按照C的传统惯例,介绍programming的最好方式就是show代码, 第一个例子就是Hello,world, 这篇文章也不例外
在任何一个cpp文件中,输入
struct hello_world; //forward declaration
struct A : hello_world
{
};
然后编译..,注意我没有说"编译运行",而仅仅说的是"编译", 如果不意外的话,在你编译器的输出窗口会出现
base class hello_world undefined
或者
base class `hello_world' has incomplete type
等类似的语句, 至少在你的屏幕上打印出了 "hello_world" 字样,对吧? 对了,这就是这个例子的目的, 我不也打印出来的吗?
上面这个简陋的例子阐述了一个重要的现象, "编译时"而不是运行时, 这就是meta programming的世界, 一个处于编译期间, 而不是运行期间的世界.
运行时我们能作的事情很多在编译时我们不能作, 例如我们不能调用函数, 我们不能创建对象, 我们也不能设置断点, 一切都交给你的C++编译器.
接下来, 首先回顾一下一些C++的基本模板知识.
由于C++的编译器符合ISO 标准的程度不一, 我使用的是VC++ 6 和 gcc version 3.2.3 (mingw special 20030504-1)
下面的例子我在这两个编译器中都测试过.
C++模板的最经常的认识就是STL中的容器, 例如
vector<int> 就是一个可以装int的动态数组, vector<sharp*> 就是一个可以装sharp对象指针的数组.
然后我们还需要一点点模板特化的知识.
例如
template<class T> struct Foo {};
这是一个通用模板, 必配任何类型, 如果我们需要对int进行特别处理, 那么
template<> struct Foo<int> {};
这样就实现了对 int 类型的完全特化 . VC6 只支持完全特化, 不支持偏特化, 或者部分特化.
不过还是稍微介绍一下:
什么是遍特化了? 还就上面这个例子而言, 如果我们想对所有的指针进行特化, 那么应该是
template<class T> struct Foo<T*> {}
那么什么又是部分特化了, 看看这个:
template<class T, class U> struct bar {};
template<class T> struct bar<T, int> {};
后面这个就是对U模板参数的部分特化,使得 U为 int的时候 使用这个版本.
这篇文章由于针对VC6, 因此你不会遇到偏特化和部分特化的情况.
hello,world的例子以后, 我们准备干点有意思的事情. 例如求两数之和. 首先看看在运行时的函数我们应该如何实现:
定义:
int sum(int x, int y) { return x+y; }
调用:
int j = sum(3, 4)
那么如何用meta programming的方式实现了?
meta programming 由于处于编译器, 因此给它的参数必须是编译时就可以确定的, 在当前C++中允许的为,integer 和 type.
就上面这个例子, 对于模板的调用应该是:
int j = sum_<3,4>::value;
3,4 都为整形常量, 编译时确定, 然后返回值如何取得? 记住在编译时是无法进行真正的函数调用的,因此我们只有通过定义在模板类中的一个常量
来获得返回结果. 最简单的方法就是在一个 struct定义一个匿名的enum .
sum的定义如下:
template<int x, int y>
struct sum_
{
enum { value = x + y };
};
然后你可以编译后"运行"检查检查看看运行结果
#include <iostream>
using namespace std;
template<int x, int y>
struct sum_
{
enum { value = x + y };
};
int main()
{
cout << sum_<3, 4>::value << endl;
return 0;
}
上面之所以使用struct sum_而不是class sum_是因为struct的默认作用范围上public, 可以省略几个键击.
这个例子通用展示了一个重要的观点, 对应通常可以在运行时调用的函数
int foo(int a, int b)
其对应的meta 实现为:
foo<a, b>::value
也就是我们的foo现在为一个struct name, 参数通过< > 中的模板投递, 结果通过 ::value 获得其中定义的一个匿名enum值.
那么如何计算 3,4,5的和?
你可能会想如下:
sum_<3,4,5>::value
但是c++不支持一个模板类使用不同的参数参数存在, 换一个方式,
你如何在 int sum(int a, int b) 存在的情况下获得3个数的和?
我们可以这样：
sum( 3, sum(4, 5))
有lisp 背景的可能发现这很符合他们的思考方式, 至少以我浮浅的emacs lisp知识, 不使用中间变量. 同样,meta中你也可以这样使用:
sum_< //开始参数
sum_< 3 //第一个参数为3
sum_< 3, sum_< //第二个参数是另外一个表达式的结果
sum_< 3, sum_<4, //这个表达式的第一个参数为４
sum_< 3, sum_<4, 5> //这个表达式的第二个参数为５
sum_< 3, sum_<4, 5>::value //通过::value获得这个表达式的结果
sum_< 3, sum_<4, 5>::value >::value //然后获得整个表达式的结果
ok, 就这么多, 看出来没有, 再解释一次, 将上面我们的
cout << sum_<3, 4>::value << endl;
中４的位置用一个sum_ 替换就得到了我们需要的三个数之和.
cout << sum_<3, ?? >::value << endl;
===>
?? = sum_<4, 5>::value
===> then
cout << sum_<3, sum_<4, 5>::value >::value << endl;
如果我需要算 2, 3, 4, 5之和呢?
同样简单, 你将上面的3, 4 ,5 中的任何一个常量替换成对sum_ 进行一个调用就可以了.
例如:
out << sum_< ?? , sum_<4, 5>::value >::value << endl;
?? = sum_< 2, 3 >::value
合并后为
cout << sum_< sum_<2, 3>::value , sum_<4, 5>::value >::value << endl;
运行的结果为 14.
这就是meta中最简单的一个例子, 顺序调用, 如果你看明白了同时觉得有点意思的话, 下来我们讲讲
循环语句, 通常我们写程序都避免递归, 因为容易造成堆栈和大脑溢出,但是在 meta 中必须使用递归的方式.
下面看看一个计算"阶乘"的例子, 其实这个才真正是meta 中的hello,world.
先看后面, 我们调用的方式:
cout << fac<5>::value ; // 结果应该是 5 * 4 * 3 * 2 * 1 = 120;
通过前面的知识, 你知道fac是一个template struct的名字, 有一个模板参数int, value是其中的一个匿名枚举变量
于是你可以毫不犹豫的写下:
template<int i>
struct fac
{
enum { value = ??? };
};
但是在value的地方你卡住了, 如果根据 i 得到 value?
让我们将大脑从"编译时世界"切换到"运行时的世界", 你如何写一个通常的递归函数来计算阶乘?
int fac(int n)
{
if( n == 1)
return 1;
return n * fac(n-1);
}
注意 n == 1是一个递归退出条件,先不考虑n为1时的递归退出,
其他情况下是将n 乘以 fac (n - 1). 有了前面的sum_ 知识, 你应该可以推出 value = ???
中的??? 应该是
n * //n*
fac //调用下一个fac
fac<n-1> //参数为n-1
fac<n-1>::value //获得结果
因此fac "函数"的模板实现就是
template<int i>
struct fac
{
enum { value = i * fac<i - 1>::value };
};
然后我们再考虑递归退出条件, 为1时value应该为1, 拿起C++中的特化模板武器来
template<>
struct fac<1> //参数为1时的特化
{
enum { value = 1 };
};
这样就将参数为 1 时的返回值设置为1, 结束递归.
这样,当你输入
cout << fac<5>::value << endl;
时,编译器会实例化
template<>
struct fac<5>
{
enum { value = 5 * fac<4>::value };
};
由于fac<5> 需要 fac<4> , 因此然后实例化 fac<4>, 同样的原因, fac<3> , fac<2>, fac<1>
到fac<1> , 编译器发现了一个特化版本fac<1> 匹配, 在fac<1>中的value已经是一个常量, 不依赖其他的fac实例, 递归退出, 最后
我们得到最终结果120 .
easy, 对不?
然后再介绍 if语句.
还是上面的这个fac例子, 负数的阶乘是没有意义的,先不考虑数学问题,假设我们希望在这个情况下返回-1,如何实现?
如果我们输入fac<-2>::value , 那么编译器会尝试实例化fac<-3>, fac<-4>, ......
你发现这是一个无限递归条件, 在运行时会造成你堆栈溢出, 由于我们在"编译时世界", 取决于你编译器, 最终总有结束的时候.
例如VC6 报错: fatal error C1202: recursive type or function dependency context too complex
G++报错 : template instantiation depth exceeds maximum of 500
因此我们需要一个if判断语句, 发现当模板参数 < 1的时候返回 -1.
按照测试先行的原则, 我们可以预计
fac<-1>::value == -1 是成立的.
现在的问题是如何实现? 下次再说吧! 也给个机会折磨折磨你的大脑. 记住, 模板不仅仅可以通过enum返回整数, 还可以通过嵌套 typedef返回一个类型.
上回说到一个fac的版本, 希望在负数的情况下返回-1, 而不是无限递归下去.
还是按照我们的思维, 先写个对应"运行时世界"的版本.
int safe_fac(int n)
{
if( n < 1)
return -1;
return fac(n);
}
这个if逻辑很简单, 如果模板参数<1, 那么直接返回 -1, 否则 还是使用前面的fac那个版本.
好, 转换成我们的meta 版本.
你想,用个 ?: 运算符不就解决了吗?
template<int n>
struct safe_fac
{
enum { value = (n < 1 ? -1 : fac<n>::value ) };
};
可惜不对, ?= 只有在"运行时世界"才能使用. 那么 value 后面的???写什么好呢?
先轻松轻松, 写一个if的meta 版本, 我敢保证你能看得懂.
template< bool b , class T, class U>
struct if_
{
typedef T type;
};
注意了, 如果以前我们提到的例如sum_, fac等meta functions(其实就是c++中的模板类, 称之为meta function是因为它们就像是function)
是通过一个 在enum中的value 返回整形的话, 上面刚刚的if_这个例子就展示了 meta中的另外一个武器, 通过typedef 一个type 返回一个类型.
如果我们这样调用
if_<true, int, double>::type 的结果就是 int 类型, 注意是"类型", 不是对象.
我们想在b为false的时候返回第二个类型U, 即:
if_<false, int, double>::type 的返回结果是double
那么还是很简单, 部分特化 b 参数就可以了.即:
template<class T, class U>
struct if_<false, T, U>
{
typedef U type;
};
我最前面说了, VC6不支持部分特化, 但是别忘了计算机时间的一条公理:
任何计算机问题都可以通过增加一层来解决. 大部分VC6中的模板的问题还是可以解决的. 如果你不使用VC6, 这部分就不用看了.
VC6是支持全部特化的, 因此我们可以将true, false特化出来
template<bool>
struct if_help
{
...
};
template<>
struct if_help<false>
{
...
};
这个在vc6中是支持的. 然后我们还需要两个额外的类型参数T,U, 这可以通过嵌套类来实现. 即
template<bool>
struct if_help
{
template<class T, class U>
struct In
{
typedef T type;
};
};
template<>
struct if_help<false>
{
template<class T, class U>
struct In
{
typedef U type;
};
};
然后我们真正的if_ "meta 函数"如下定义:
template<bool b, class T, class U>
struct if_
{
typedef if_help<b>::In<T, U>::type type;
};
先根据b的内容实例化一个对应的if_help, : if_help<b>
然后给其中的In模板投递T,U参数, ::In<T, U>
然后通过type获得其中的返回类型 ::type
最后typedef type一下作为自己的返回类型, 这样外部就可以通过
if_<true, int, double>::type 获得返回的类型了.
上面if_ 的实现实际上要用几个C++关键字修饰一下:
typedef if_help<b>::In<T, U>::type type;
===>
typedef typename if_help<b>::template In<T, U>::type type;
为什么要加上typename 和 template, 这个解释起来到是很费劲. 有空再说.
好了, 从模板的语法世界中清醒过来, 现在你知道的是, 我们有了一个if_ 的meta函数, 接受3个参数bool b, class T, class U,
如果b为true, 那么它的返回值 (通过 if_::type 返回) 就是T,
如果b为false, 那么它的返回值 (通过 if_::type 返回) 就是U.
前面我提过了, 参数是通过<>来传递的, 因此一个例子就是
if_
//函数名
if_<true,
//第一个参数, bool 型
if_<true, int //第二个参数, 类型
if_<true, int, double //第3个参数, 类型
if_<true, int, doubble> //右括号表示参数结束
if_<true, int, double>::type //通过::type获得返回结果, 不是value了, 当然这仅仅是一个命名惯例.
因此上面的那个 if_<true, int, double>::type 返回的就是 int,
在"运行时世界", 你可以如下使用:
for( if_<true, int, double>::type i = 0; i < 10; i++) {
cout << "line " << i << "\n";
}
等同于
for( int i = 0; i < 10; i++) {
cout << "line " << i << "\n";
}
当然对于这个例子这样使用是"有病". 我们等会会用到if_来实现前面的 safe_fac 实现了.
注意我说的返回值并不是前面sum_例子中的整形了, 这个时候返回一个类型. 类型不是实例对象, 这点我想你应该清楚.
编译时不可能返回对象, 因为要调用构造函数, 要确定对象地址, 我们还没有进入到" 运行时世界" , 对吧?
实际上meta programming 最重要的使用并不是前面我们提到过的sum_, fac这些, 因为毕竟拿个计算器算一下也花不了几个时间.
但是返回type就不同了.
那么type可以是什么呢? 可以是int, double这样的基本类型, 也可以我们前面的 sum_ 模板类等等.
然后再看safe_fac的实现:
先不考虑 <1 的情况, 那么value就应该是直接调用以前的 fac 函数
template<int n>
struct safe_fac
{
enum { value = fac<n>::value };
};
然后再使得 >= 1时才使用fac函数, 那么利用我们前面的if_, 先忽略语法错误, 那么可以如下
enum
{
value = if_< n < 1,???, fac<n> >::type::value
};
首先, n < 1 为真时返回一个类型???, 暂时我们还没有实现, 为false时返回
fac<n>类型, 然后通过::type获得返回的类型,或者为???, 或者为fac<n>,
然后通过::value得到这个类型的整数结果.
那么 ??? 应该是什么呢? 当然不能直接是-1, 否则 -1::value 就是语法错误.
因此我们可以定义一个简单的"函数", 返回-1:
struct return_neg1
{
enum { value = -1 };
};
如果我们需要返回-2怎么办? 又定义一个return_neg2 "函数"? 干脆我们一劳永逸, 定义如下:
template<int n>
struct int_
{
enum { value = n };
};
这样int_ 这个"函数"就是你给我什么, 我就返回什么. 不过int_是一个类型, 例如:
通过如下调用 int_<3>::value 返回它的结果3.
有了这个, 我们的代码就如下:
value = if_< n < 1, int_<-1>, fac<n> >::type::value
原理清楚了, 最终的版本就是:
template<int n>
struct safe_fac
{
enum { value = if_< n < 1, int_<-1>, fac<n> >::type::value };
};
试试:
cout << safe_fac<-1>::value 输出 -1.
循环(递归表示), 条件判断, 顺序执行都有了, 剩下的就看你自己了.
--------------------------------------------------------------------------------
Boost中的mpl (meta programming library) 提供了一个专门用于metaprogramming的library, 同时前面提到的if_, int_等等就
是从mpl中拷贝来的, 当然我简化了很多.
Modern C++ Design 其中的Typelist将meta progamming的循环(就是递归)发挥得淋漓尽致, 在侯捷的网站上www.jjhou.com有免费的前4章可读. Typelist在第三章.
书中序言部分, Effective C++的作者Meyers说到, 如果第3章的typelists没有让你感到振奋, 那你一定是很沉闷.
就我亲身体验, 我觉得Meyers可能是说到委婉了些:
如果第3章的typelists没有让你感到振奋, 那1%的可能是你是很沉闷, 99%的可能是你没有看懂. I did.
GoF之一的 John Vlissides同样提到了typelists这一章就值得本书的价格. I believe.
另外, 我发现即使在这本让人抓狂的天才之作中, 作者仍然使用了n个TYPELIST_n 这样的预处理宏来处理多个type的情况, 但是在sourceforge
下的Loki库中我发现已经有了一个MakeTypelist"函数", 看来 meta programming 确实是, 啊...
是不是作者当时都没有预见到还能够以C++编译器内建的模板能力, 而不是依赖预处理宏来处理typelist.?
又, mpl中有专门装type的容器....