C++模板元编程资料辑录

本文主要是我学习模板元编程过程中的一些心得总结,以及我写的一些模板元编程的代码也都会放到这里来。

模板代码

进制转换的模板元版本

实现了一个从10进制转换到2~10进制的模板元版本:

1
2
3
4
5
6
7
8
9
template<int N,int Z>
struct Convert{
enum:size_t{
resault=(N<Z)?N:(10*Convert<N/Z,Z>::resault+N%Z)
};
};
template<int Z>
struct Convert<0,Z>{enum:size_t{resault=0};};

然后就可以这样使用:

1
2
3
4
5
int main()
{
printf("%d\n",Convert<12345,2>::resault);
printf("%d\n",Convert<12345,8>::resault);
}

接收的参数的范围均不能超过size_t

查看上面main函数的IR代码也可以看到,没有运行时开销的。

1
2
3
4
5
define i32 @main() #4 {
%1 = call i32 (i8*, ...) @_ZL6printfPKcz(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i64 11000000111001)
%2 = call i32 (i8*, ...) @_ZL6printfPKcz(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i64 30071)
ret i32 0
}

另附一个模板元的整型pow版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<int N,int Z>
struct mtpow{
enum:size_t{
resault=N*mtpow<N,Z-1>::resault
};
};
template<int N>
struct mtpow<N,1>{
enum:size_t{
resault=N
};
};
int main()
{
printf("%d\n",mtpow<3,2>::resault);
}

斐波那契数列的模板元版本

斐波那契数列是啥就不多说了,今天午休睡不着,撸了个模板元版本,求斐波那契数列的第N项和前N项和完全没有运行时开销。
废话不多说,代码如下:

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
33
34
35
36
template<int N>
struct FibonacciN
{
enum:size_t{
resault=FibonacciN<N-1>::resault+FibonacciN<N-2>::resault
};
};
template<>
struct FibonacciN<1>{
enum:size_t{resault=1};
};
template<>
struct FibonacciN<2>{
enum:size_t{resault=1};
};
template<int N>
struct FibonacciNSum{
enum:size_t{
resault=FibonacciN<N>::resault+FibonacciNSum<N-1>::resault
};
};
template<>
struct FibonacciNSum<1>{
enum:size_t{
resault=FibonacciN<1>::resault
};
};
int main()
{
printf("%d\n",FibonacciN<5>::resault);
printf("%d\n",FibonacciNSum<5>::resault);
}

还是来看一下LLVM-IR代码(碍于篇幅只看主函数部分):

1
2
3
4
5
6
7
8
9
10
11
define i32 @main(i32, i8**) #4 {
%3 = alloca i32, align 4
%4 = alloca i32, align 4
%5 = alloca i8**, align 8
store i32 0, i32* %3, align 4
store i32 %0, i32* %4, align 4
store i8** %1, i8*** %5, align 8
%6 = call i32 (i8*, ...) @_ZL6printfPKcz(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i32 5)
%7 = call i32 (i8*, ...) @_ZL6printfPKcz(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i32 12)
ret i32 0
}

可以看到,在printf里输出的直接就是常量5和12,即完全没有运行时开销。

编译时类型判断

如何在编译时判断一个类型是否是类类型呢?
基于C++中SFINAE的概念,可以使匹配成功和失败执行不同的逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct True{
char x;
};
struct False{
char x[2];
};
template<typename T>
struct IsClass{
template<typename C> static True isClass(int C::*){return True{};}
template<typename C> static False isClass(...){return False{};}
enum{ISCLASS=sizeof(IsClass<T>::isClass<T>(0))==sizeof(True)};
};
int main()
{
if(IsClass<double>::ISCLASS){
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}
}
// output: no

这里主要的地方在于True isClass(int C::*),回想一下我之前的一篇文章C++中指向类成员的指针并非指针,0可以转换为指向成员的指针。判断的思想就是若类型T存在具有指向类成员的指针那么它就是一个类,反之则不是。
基于同样的思想,也可以实现判断是否存在从一个类型A到另一个B的转换:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename A,typename B>
struct haveConvert{
static True Convert(B){return True{};}
static False Convert(...){return False{};}
enum{CHECK=sizeof(haveConvert<A, B>::Convert(A{}))==sizeof(True)};
};
int main()
{
if(haveConvert<string,double>::CHECK){
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}
}
// output: no

而且完全没有运行时开销,这里的代码在编译时时就已经确定了,所以在运行时就是直接的输出:
等同于:

1
2
3
4
5
if(0){
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}

被编译器优化之后,去除死代码:

1
cout<<"no"<<endl;

可以从其LLVM-IR代码中看到主函数中在运行时只执行了cout的输出:

1
2
3
4
5
6
7
8
@.str = private unnamed_addr constant [3 x i8] c"no\00", align 1
; Function Attrs: norecurse uwtable
define i32 @main() #4 {
%1 = call dereferenceable(272) %"class.std::basic_ostream"* @_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc(%"class.std::basic_ostream"* dereferenceable(272) @_ZSt4cout, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i32 0, i32 0))
%2 = call dereferenceable(272) %"class.std::basic_ostream"* @_ZNSolsEPFRSoS_E(%"class.std::basic_ostream"* %1, %"class.std::basic_ostream"* (%"class.std::basic_ostream"*)* @_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_)
ret i32 0
}

这也是模板编程的精华所在,完全没有运行时开销是多么一颗赛艇的事!!

自身类型的using成员

怎么定义一个类的成员中能够获取到当前类类型的成员呢?
可以用下面这种写法:

1
2
3
4
5
6
7
template<typename T>
struct base{
using selfType=T;
};
template<typename T>
struct foo:public base<foo<T>>{};

虽然有种强行搞事的意思...

将模板作为参数传递给模板

其实也就是模板的模板参数,如果我们有这样的需求:模板的第二个参数是一个模板,其的参数为第一个参数的类型:

1
2
// 期待于将string在TempClass内部作为vector的模板实参
TempClass<string,vector> test;

但是不可以用上面的那种写法的,也不可以是TempClass<string,vector<>>这样。
因为,是要传入一个模板而不是一个vector的类型,可以用这种写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
template<class X,template<class Y=X> class Z>
struct A
{
Z<> x; // equal Z<X>,because default template parameter of template Z is X
void getZname(){
cout<<typeid(this->x).name()<<endl;
}
};
template<class T>
using Vector=vector<T>;
int main(int argc,char* argv[])
{
A<string,Vector> x;
x.getZname();
vector<string> y;
cout<<typeid(y).name()<<endl;
return 0;
}

模板元编程资料

模板(Templates)的发展历史

摘自C++标准委员会主席Herb Sutter的著作——《Exceptional C++: 40 New Engineering Puzzles, Progrmming Problems, And Solutions》。

  • C++模板的第一份设计方案是 Bjarne Stroustrup 在 1988 年 10 月提出的[Stroustrup88]。
  • 到了1990年,Margaret Ellis 和 Bjarne Stroustrup 合著了 The Annotated C++ Reference Manual(也称 ARM)[Ellis90]。同年,ISO/ANSI C++标准委员会继续进展,并将 ARM选作阶段的“起点”基础文档。ARM 是第一份包含模板描述的 C++参考,其中描述的模板并非今天所熟知的样子,那时的模板还相当单薄,整个规范说明和描述只占了 10 页纸 那时,人们关注的重心完全落在如何支持参数化类型以及参数化函数,ARM 中给出的例子是一个能够存放各种类型对象的 List 容器,以及一个 sort 算法,它可以对各种类型的序列进行排序。然而,即便是在那时,人们已经思考是否给模板一个分离式编译能力。Cfront(Stroustrup 的 C++编译器)就支持当时尚处于初级阶段的模板的“分离式”编译,尽管它当时采用的做法并不具有可伸缩性(参见上一条中的标注)。
  • 从 1990 年至 1996 年这 6 年间,C++编译器开发商纷纷涌现,并各自为战,采用不同的途径实现模板这一语言特性,同时标准委员会也对模板进行了极大的改进和扩充(使其更为复杂化了)。在透彻讲述 C++模板的著作 C++ Templates [Vandevoorde03]中,仅标准C++模板的完整描述就占了 552 页中的大约 133 页篇幅,而整本书则完全用来详细描述模板这一语言特性以及如何有效地使用它。
  • 在20世纪90年代的早期至中期,C++标准委员会将主要的精力放在让模板更健壮和实用,从而对它的基本使用有更好的支持。很少有人会怀疑他们创造出了一个极度灵活而有点古怪的奇迹般的东西,后来人们才知道模板原来本身就是一门图灵完备(Turing-complete)的元语言,用它可以写出任意复杂的程序,而这个程序是在编译期执行的。然而,如今在C++中大行其道的模板元编程以及高级的库设计技术却是当初赋予C++模板生命的人怎么也没有想到的,正是他们当时的决策造就了今天的一切,在1990年至1996年之间这些模板技术绝大部分还没出现呢!还记得吗,1994年底Stepanov把他的STL库第一次提交给标准委员会,1995年STL被采纳为标准,当时人们认为它是突破性的成就,然而在今天看来STL“只不过”是一个容器和算法库而已。当然,STL在1995年的背景下的确是个革命性的突破,而且即便是放在今天也仍然是令C++区别于其他语言的强大证据之一,然而从如今的标准来看,STL却只不过是C++模板的牛刀小试而已。
全文完,若有不足之处请评论指正。

扫描二维码,分享此文章

本文标题:C++模板元编程资料辑录
文章作者:ZhaLiPeng
发布时间:2017年06月17日 23时21分
本文字数:本文一共有2,123字
更新历史: Blame, History  文本模式: .md Raw
原始链接:https://imzlp.me/posts/23043/
许可协议: CC BY-NC-SA 4.0
转载请保留原文链接及作者信息,谢谢!
您的捐赠将鼓励我继续创作!