uncategorized

模板元编程:C++的黑魔法

关于模板与泛型

如果你曾经使用过template,那你一定对泛型编程有过了解,你可能在java和c#中使用过泛型代码,但是,需要注意的是,C++的泛型和java,C#一类的泛型有着根本性的不同,C++ 的泛型有个更适合的名字,叫做编译期多态,是的,C++的泛型本质上是一种多态。

怎么理解这个编译期多态?举个例子,假如你有一个template function 的定义如下

1
2
3
4
template<typename T>
const T& max(const T& a, const T& b){
return a > b ? a : b;
};

并且假设你是这样使用它的

1
2
3
4
5
6
7
8
9
int main() {
float af = 0.f;
float bf = 0.3f;
int ai = 0;
int bi = 1;
std::cout << max(af, bf) << std::endl;
std::cout << max(ai, bi) << std::endl;
return 0;
}

很明显,结果是0.3和0,你使用Java做上面这些事情也会得到同样的结果。但是在编译期两者做的事情是不一样的:

  • C++编译器会把所有用到的template全部展开一遍,生成多份代码。在上面这个例子中,template展开为参数分别为 float 和 int 的两个函数,由运行时参数决定运行哪个函数。
  • Java编译器则会对所有用到的类型执行擦除,也就是说会把所有带类型的引用向上转型到Object,并且在运行期需要类型化时强制转换为对应类型

注意到Java泛型实现中的装箱和拆箱过程了吗?毫无疑问这会有不小的效率损失。而C++可以避免这一点。更重要的是,C++ 的泛型实现机制赋予了程序员一定的在编译期生成代码的能力(因此template这样的命名更确切一些),有了这个,我们差不多就可以做一些事情了

tamplate 参数类型

有以下三种:

  • 模板的类型形参 (type parameter)
1
2
template<typename T>
template<class T>
  • 模板的非类型形参 (non-type parameter)

    模板的非类型行参只有以下几种形式

    • 整型或枚举型
    • 到对象的指针或函数指针
    • 到对象的引用或函数引用
    • 成员指针

​ 因此,以下几种代码都是可以接受的

1
2
3
template<int a> struct A {};
template<int* b> struct B {};
template<void f(int)> struct C{};
  • 模板形参 (template template parameter)

    模板行参的意思是模板里面可以是另一个模板,如

    1
    template<template<typename T>> class X{};

template 是图灵完备的

所谓的图灵完备指的是以下定义

可计算性理论里,如果一系列操作数据的规则(如指令集编程语言细胞自动机)可以用来模拟单带图灵机,那么它是图灵完备的

(WikiPedia)

我们可以按照百度百科的定义下去理解

在可计算理论中,当一组数据操作的规则(一组指令集,编程语言,或者元胞自动机)满足任意数据按照一定的顺序可以计算出结果,被称为图灵完备(turing complete)

(百度百科)

一般来讲,如果一个东西能支持一个无限的递归过程,那么它就是图灵完备的,很显然,C++ template是如此特殊,它本身就是图灵完备的!

理解这一点并不困难,我们把 C++ template 看做是一个特殊的图灵机,它以未做template展开的C++远代码为输入,以不带template的C++源代码为输出,在这种意义下,你甚至可以认为 template是一种只运行在编译期的语言!

我们来看一个有趣的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

template<int i>
struct sum {
enum {
value = i + sum<i-1>::value
};
};

// 对i = 1特化
template<>
struct sum<0> {
enum{
value = 1
};
};

int main() {
std::cout << sum<20>::value << std::endl;
return 0;
}

好,现在编译运行它,看输出了什么?

很简单,输出了211,它是 1+2+3+…+20的结果,而这个结果是编译期计算出来的!编译器在编译的时候把所有用到的template参数展开,在展开过程中 当模板实参是 i 的时候需要事先知道 i-1 的template,因此当给的实际参数是 20 的时候就会递归式的展开到 0,这样所需要的结果就在编译期算出来了,因此这是一种牺牲编译期性能来提高运行期性能的手段

关于C++模板的黑魔法还有很多,我们现在看到的只是冰山一角,著名的boost库就应用了大量这种技巧。不过在真正的工程上目前还用的不是很多,其缺点也是显然的:调试困难,错误信息不可读,编译时间大幅延长。

目前cpp 的 meta programming 还处在很多牛人的玩具的地位,不过能把运行期做的事情放到编译期,我相信这一特性还是非常吸引程序员的

Share