C++模板元编程_c++ 模板元编程

---

0. 概述

所谓的元编程就是编写直接生成或操纵程序的程序，C++模板为C++语言提供了元编程的能力。模板使 C++ 编程变得异常灵活，能实现很多高级动态语言才有的特性（语法上可能比较丑陋，一些历史原因见下文）。普通用户对 C++ 模板的使用可能不是很频繁，大致限于泛型编程，但一些系统级的代码，尤其是对通用性、性能要求极高的基础库（如 STL、Boost）几乎不可避免的都大量地使用 C++ 模板，一个稍有规模的大量使用模板的程序，不可避免的要涉及元编程（如类型计算）。本文就是要剖析 C++ 模板元编程的机制。

1. C++模板的语法

函数模板（function template）和类模板（class template）的简单示例如下：

#include <iostream>
 
// 函数模板
template<typename T>
bool equivalent(const T& a, const T& b){
    return !(a < b) && !(b < a);
}
// 类模板
template<typename T=int> // 默认参数
class bignumber{
    T _v;
public:
    bignumber(T a) : _v(a) { }
    inline bool operator<(const bignumber& b) const; // 等价于 (const bignumber<T>& b)
};
// 在类模板外实现成员函数
template<typename T>
bool bignumber<T>::operator<(const bignumber& b) const{
    return _v < b._v;
}
 
int main()
{
    bignumber<> a(1), b(1); // 使用默认参数，"<>"不能省略
    std::cout << equivalent(a, b) << '\n'; // 函数模板参数自动推导
    std::cout << equivalent<double>(1, 2) << '\n';
    std::cin.get();    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

程序输出如下：

1
0

关于模板实例化（template instantiation）（详见文献[4]模板）：

指在编译或链接时生成函数模板或类模板的具体实例源代码，即用使用模板时的实参类型替换模板类型参数（还有非类型参数和模板型参数）；
隐式实例化（implicit instantiation）：当使用实例化的模板时自动地在当前代码单元之前插入模板的实例化代码，模板的成员函数一直到引用时才被实例化；
显式实例化（explicit instantiation）：直接声明模板实例化，模板所有成员立即都被实例化；
实例化也是一种特例化，被称为实例化的特例（instantiated (or generated) specialization）。

隐式实例化时，成员只有被引用到才会进行实例化，这被称为推迟实例化（lazy instantiation），由此可能带来的问题如下面的例子（文献[6]，文献[7]）：

#include <iostream>
 
template<typename T>
class aTMP {
public:
    void f1() { std::cout << "f1()\n"; }
    void f2() { std::ccccout << "f2()\n"; } // 敲错键盘了，语义错误：没有 std::ccccout
};
 
int main(){
    aTMP<int> a;
    a.f1();
    // a.f2(); // 这句代码被注释时，aTMP<int>::f2() 不被实例化，从而上面的错误被掩盖!
    std::cin.get(); return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

所以模板代码写完后最好写个诸如显示实例化的测试代码，更深入一些，可以插入一些模板调用代码使得编译器及时发现错误，而不至于报出无限长的错误信息。另一个例子如下（GCC 4.8 下编译的输出信息，VS2013 编译输出了 500 多行错误信息）：

#include <iostream>
 
// 计算 N 的阶乘 N!
template<int N>
class aTMP{
public:
    enum { ret = N==0 ? 1 : N * aTMP<N-1>::ret }; // Lazy Instantiation，将产生无限递归!
};
 
int main(){
    std::cout << aTMP<10>::ret << '\n';
    std::cin.get(); return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

sh-4.2# g++ -std=c++11 -o main *.cpp
main.cpp:7:28: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘class aTMP<-890>’
enum { ret = N==0 ? 1 : N * aTMP::ret };
^
main.cpp:7:28: recursively required from ‘class aTMP<9>’
main.cpp:7:28: required from ‘class aTMP<10>’
main.cpp:11:23: required from here
main.cpp:7:28: error: incomplete type ‘aTMP<-890>’ used in nested name specifier

上面的错误是因为，当编译 aTMP 时，并不判断 N==0，而仅仅知道其依赖 aTMP（lazy instantiation），从而产生无限递归，纠正方法是使用模板特例化，如下：

#include <iostream>
 
// 计算 N 的阶乘 N!
template<int N>
class aTMP{
public:
    enum { ret = N * aTMP<N-1>::ret };
};
template<>
class aTMP<0>{
public:
    enum { ret = 1 };
};
 
int main(){
    std::cout << aTMP<10>::ret << '\n';
    std::cin.get(); return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3228800

关于模板的编译和链接（详见文献[1] 1.3、文献[4]模板）：

包含模板编译模式：编译器生成每个编译单元中遇到的所有的模板实例，并存放在相应的目标文件中；链接器合并等价的模板实例，生成可执行文件，要求实例化时模板定义可见，不能使用系统链接器；
分离模板编译模式（使用 export 关键字）：不重复生成模板实例，编译器设计要求高，可以使用系统链接器；
包含编译模式是主流，C++11 已经弃用 export 关键字（对模板引入 extern 新用法），一般将模板的全部实现代码放在同一个头文件中并在用到模板的地方用 #include 包含头文件，以防止出现实例不一致（如下面紧接着例子）；

实例化，编译链接的简单例子如下（参考了文献[1]第10页）：

// file: a.cpp
#include <iostream>
template<typename T>
class MyClass { };
template MyClass<double>::MyClass(); // 显示实例化构造函数 MyClass<double>::MyClass()
template class MyClass<long>;        // 显示实例化整个类 MyClass<long>
 
template<typename T>
void print(T const& m) { std::cout << "a.cpp: " << m << '\n'; }
 
void fa() {
    print(1);   // print<int>，隐式实例化
    print(0.1); // print<double>
}
void fb(); // fb() 在 b.cpp 中定义，此处声明
 
int main(){
    fa();
    fb();
    std::cin.get(); return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// file: b.cpp
#include <iostream>
template<typename T>
void print(T const& m) { std::cout << "b.cpp: " << m << '\n'; }
 
void fb() {
    print('2'); // print<char>
    print(0.1); // print<double>
}
1
2
3
4
5
6
7
8
9

a.cpp: 1
a.cpp: 0.1
b.cpp: 2
a.cpp: 0.1

上例中，由于 a.cpp 和 b.cpp 中的 print 实例等价（模板实例的二进制代码在编译生成的对象文件 a.obj、b.obj 中），故链接时消除了一个（消除哪个没有规定，上面消除了 b.cpp 中的）。

关于 template、typename、this 关键字的使用（文献[4]模板，文献[5]）：

依赖于模板参数（template parameter，形式参数，实参英文为 argument）的名字被称为依赖名字（dependent name），C++标准规定，如果解析器在一个模板中遇到一个嵌套依赖名字，它假定那个名字不是一个类型，除非显式用 typename 关键字前置修饰该名字；
和上一条 typename 用法类似，template 用于指明嵌套类型或函数为模板；
this 用于指定查找基类中的成员（当基类是依赖模板参数的类模板实例时，由于实例化总是推迟，这时不依赖模板参数的名字不在基类中查找，文献[1]第 166 页）。

一个例子如下（需要 GCC 编译，GCC 对 C++11 几乎全面支持，VS2013 此处总是在基类中查找名字，且函数模板前不需要 template）：

#include <iostream>
 
template<typename T>
class aTMP{
public: typedef const T reType;
};
 
void f() { std::cout << "global f()\n"; }
 
template<typename T>
class Base {
public:
    template <int N = 99>
    void f() { std::cout << "member f(): " << N << '\n'; }
};
 
template<typename T>
class Derived : public Base<T> {
public:
    typename T::reType m; // typename 不能省略
    Derived(typename T::reType a) : m(a) { }
    void df1() { f(); }                       // 调用全局 f()，而非想象中的基类 f()
    void df2() { this->template f(); }        // 基类 f<99>()
    void df3() { Base<T>::template f<22>(); } // 强制基类 f<22>()
    void df4() { ::f(); }                     // 强制全局 f()
};
 
int main(){
    Derived<aTMP<int>> a(10);
    a.df1(); a.df2(); a.df3(); a.df4();
    std::cin.get(); return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

global f()
member f(): 99
member f(): 22
global f()

C++11 关于模板的新特性（详见文献[1]第15章，文献[4]C++11）：

“>>” 根据上下文自动识别正确语义；
函数模板参数默认值；
变长模板参数（扩展 sizeof…() 获取参数个数）；
模板别名（扩展 using 关键字）；
外部模板实例（拓展 extern 关键字），弃用 export template。

在本文中，如无特别声明将不使用 C++11 的特性（除了 “>>”）。

2. 模板元编程概述

如果对 C++ 模板不熟悉（光熟悉语法还不算熟悉），可以先跳过本节，往下看完例子再回来。

C++ 模板最初是为实现泛型编程设计的，但人们发现模板的能力远远不止于那些设计的功能。一个重要的理论结论就是：C++ 模板是图灵完备的（Turing-complete），其证明过程请见文献[8]（就是用 C++ 模板模拟图灵机），理论上说 C++ 模板可以执行任何计算任务，但实际上因为模板是编译期计算，其能力受到具体编译器实现的限制（如递归嵌套深度，C++11 要求至少 1024，C++98 要求至少 17）。C++ 模板元编程是“意外”功能，而不是设计的功能，这也是 C++ 模板元编程语法丑陋的根源。

C++ 模板是图灵完备的，这使得 C++ 成为两层次语言（two-level languages，中文暂且这么翻译，文献[9]），其中，执行编译计算的代码称为静态代码（static code），执行运行期计算的代码称为动态代码（dynamic code），C++ 的静态代码由模板实现（预处理的宏也算是能进行部分静态计算吧，也就是能进行部分元编程，称为宏元编程，见 Boost 元编程库即 BCCL，文献[16]和文献[1] 10.4）。

具体来说 C++ 模板可以做以下事情：编译期数值计算、类型计算、代码计算（如循环展开），其中数值计算实际不太有意义，而类型计算和代码计算可以使得代码更加通用，更加易用，性能更好（也更难阅读，更难调试，有时也会有代码膨胀问题）。编译期计算在编译过程中的位置请见下图（取自文献[10]），可以看到关键是模板的机制在编译具体代码（模板实例）前执行：

从编程范型（programming paradigm）上来说，C++ 模板是函数式编程（functional programming），它的主要特点是：函数调用不产生任何副作用（没有可变的存储），用递归形式实现循环结构的功能。C++ 模板的特例化提供了条件判断能力，而模板递归嵌套提供了循环的能力，这两点使得其具有和普通语言一样通用的能力（图灵完备性）。

从编程形式来看，模板的“<>”中的模板参数相当于函数调用的输入参数，模板中的 typedef 或 static const 或 enum 定义函数返回值（类型或数值，数值仅支持整型，如果需要可以通过编码计算浮点数），代码计算是通过类型计算进而选择类型的函数实现的（C++ 属于静态类型语言，编译器对类型的操控能力很强）。代码示意如下：

#include <iostream>
 
template<typename T, int i=1>
class someComputing {
public:
    typedef volatile T* retType; // 类型计算
    enum { retValume = i + someComputing<T, i-1>::retValume }; // 数值计算，递归
    static void f() { std::cout << "someComputing: i=" << i << '\n'; }
};
template<typename T> // 模板特例，递归终止条件
class someComputing<T, 0> {
public:
    enum { retValume = 0 };
};
 
template<typename T>
class codeComputing {
public:
    static void f() { T::f(); } // 根据类型调用函数，代码计算
};
 
int main(){
    someComputing<int>::retType a=0;
    std::cout << sizeof(a) << '\n'; // 64-bit 程序指针
    // VS2013 默认最大递归深度500，GCC4.8 默认最大递归深度900（-ftemplate-depth=n）
    std::cout << someComputing<int, 500>::retValume << '\n'; // 1+2+...+500
    codeComputing<someComputing<int, 99>>::f();
    std::cin.get(); return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

8
125250
someComputing: i=99

C++ 模板元编程概览框图如下（取自文献[9]）：

下面我们将对图中的每个框进行深入讨论。

3. 编译期数值计算

第一个 C++ 模板元程序是 Erwin Unruh 在 1994 年写的（文献[14]），这个程序计算小于给定数 N 的全部素数（又叫质数），程序并不运行（都不能通过编译），而是让编译器在错误信息中显示结果（直观展现了是编译期计算结果，C++ 模板元编程不是设计的功能，更像是在戏弄编译器，当然 C++11 有所改变），由于年代久远，原来的程序用现在的编译器已经不能编译了，下面的代码在原来程序基础上稍作了修改（GCC 4.8 下使用 -fpermissvie，只显示警告信息）：

// Prime number computation by Erwin Unruh
template<int i> struct D { D(void*); operator int(); }; // 构造函数参数为 void* 指针
 
template<int p, int i> struct is_prime { // 判断 p 是否为素数，即 p 不能整除 2...p-1
    enum { prim = (p%i) && is_prime<(i>2?p:0), i-1>::prim };
};
template<> struct is_prime<0, 0> { enum { prim = 1 }; };
template<> struct is_prime<0, 1> { enum { prim = 1 }; };
 
template<int i> struct Prime_print {
    Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    // prim 为真时， prim?1:0 为 1，int 到 D<i> 转换报错；假时， 0 为 NULL 指针不报错
    void f() { D<i> d = prim?1:0; a.f(); } // 调用 a.f() 实例化 Prime_print<i-1>::f()
};
template<> struct Prime_print<2> { // 特例，递归终止
    enum { prim = 1 };
    void f() { D<2> d = prim?1:0; }
};
 
#ifndef LAST
#define LAST 10
#endif
 
int main() {
    Prime_print<LAST> a; a.f(); // 必须调用 a.f() 以实例化 Prime_print<LAST>::f()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

sh-4.2# g++ -std=c++11 -fpermissive -o main .cpp
main.cpp: In member function ‘void Prime_print<2>::f()’:
main.cpp:17:33: warning: invalid conversion from ‘int’ to 'void’ [-fpermissive]
void f() { D<2> d = prim ? 1 : 0; }
^
main.cpp:2:28: warning: initializing argument 1 of ‘D:

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/799442