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

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

模板代码

进制转换的模板元版本

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

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};};

然后就可以这样使用：

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

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

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

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版本：

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项和完全没有运行时开销。
废话不多说，代码如下：

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代码(碍于篇幅只看主函数部分)：

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的概念，可以使匹配成功和失败执行不同的逻辑：

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的转换:

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

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

if(0){
  cout<<"yes"<<endl;
}else{
  cout<<"no"<<endl;
}

被编译器优化之后，去除死代码：

1	cout<<"no"<<endl;

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

@.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成员

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

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的类型，可以用这种写法：

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;
}

模板的数组引用参数不会隐式转换为指针

先看一下这个模板，用来获取数组类型的元素大小：

template<class T, size_t N>
size_t arr_size(T (&)[N])
{
  return N;
}

用法，传入一个数组类型，从返回值获取其元素数量：

int main()
{
  int i_array[10]={};
  cout<<arr_size(i_array)<<endl;
}

// output
10

我们从一行行来分析arr_size这个模板函数为什么要这么写。
首先这个模板类接收两个参数，一个是类型T一个是数组大小的N，编译器会根据传进来的实参来匹配到这两个模板参数。这个模板的意思就是，从数组的类型(e.g:int [N])上获取元素(N)的大小。
最重要的就是arr_size的函数形参声明的部分:

1	size_t arr_size(T (&)[N])

有两个问题：
0. 为什么需要&，pass by value不可以吗？

为什么要加括号？ T &[]不可以吗？

首先，第一个问题，为什么需要传引用？pass by value不可以吗？
pass by value不可以，我们可以自己写一个传递限定数组实参元素个数的函数来分析一下pass by value传递进来的实参到底是什么：

void test_array(int (arr)[10]){}

int main()
{
  int i_array[10]={0};
  test_array(i_array);
}

老规矩还是直接看上面的代码生成的LLVM-IR代码：

; Function Attrs: noinline nounwind optnone uwtable
define dso_local void @_Z10test_arrayPi(i32*) #4 {
  %2 = alloca i32*, align 8
  store i32* %0, i32** %2, align 8
  ret void
}

; Function Attrs: noinline norecurse nounwind optnone uwtable
define dso_local i32 @main() #5 {
  %1 = alloca i32, align 4
  %2 = alloca [10 x i32], align 16
  store i32 0, i32* %1, align 4
  %3 = bitcast [10 x i32]* %2 to i8*
  call void @llvm.memset.p0i8.i64(i8* align 16 %3, i8 0, i64 40, i1 false)
  %4 = getelementptr inbounds [10 x i32], [10 x i32]* %2, i32 0, i32 0
  call void @_Z10test_arrayPi(i32* %4)
  ret i32 0
}

直接看函数test_array的原型：

1	void @_Z10test_arrayPi(i32*)

具有数组到指针的隐式转换！在这一步也就丧失了数组的类型信息。
即，如果通过pass by value的方式，我们无法在类型推导的时候就从实参中获取数组的元素个数，因为数组的元素个数在传递进来的时候就丢失掉了。
那么传引用会解决这个问题吗？
是的，传引用不会有隐式转换，因为引用类型需要绑定上源类型，而指针类型和数组类型是不同的类型：

void test_array(int (&arr)[10]){}

int main()
{
  int i_array[10]={0};
  test_array(i_array);
}

其LLVM-IR代码为：

; Function Attrs: noinline nounwind optnone uwtable
define dso_local void @_Z10test_arrayRA10_i([10 x i32]* dereferenceable(40)) #0 {
  %2 = alloca [10 x i32]*, align 8
  store [10 x i32]* %0, [10 x i32]** %2, align 8
  ret void
}

; Function Attrs: noinline norecurse nounwind optnone uwtable
define dso_local i32 @main() #1 {
  %1 = alloca [10 x i32], align 16
  %2 = bitcast [10 x i32]* %1 to i8*
  call void @llvm.memset.p0i8.i64(i8* align 16 %2, i8 0, i64 40, i1 false)
  call void @_Z10test_arrayRA10_i([10 x i32]* dereferenceable(40) %1)
  ret i32 0
}

可以看到test_array的形参类型也是数组类型了，没有丢失类型信息，所以这种用法可以在模板里使用。

第二个问题：为什么要加括号？ T &arr_ref[N]不可以吗？
不可以，我们先来看一下T &arr_ref[N]是什么类型语义：

1	int &i_arr_ref[10]; // error: 'i_arr_ref' declared as array of references of type 'int &'

首先，[]的优先级比&高，所以T &arr_ref[N]的结合性为T &(arr_ref[10])，这是个数组的引用类型，但是C++标准里没有数组的引用类型：

[ISO/IEC 14882:2014 §8.3.2.5]There shall be no references to references, no arrays of references, and no pointers to references.

即没有引用的引用，没有数组的引用，也没有指向引用的指针。所以这个T &[N]是非法的类型。
如果加了括号呢：

1	int (&i_arr_ref)[10]; // error: declaration of reference variable 'i_arr_ref' requires an initializer

初始化：

1 2	int i_array[10]={0}; int (&i_arr_ref)[10]=i_array;

这个声明的类型是引用到int [10]的数组对象，它是合法的。其LLVM-IR代码为：

define dso_local i32 @main() #1 {
  %1 = alloca [10 x i32], align 16
  %2 = alloca [10 x i32]*, align 8
  %3 = bitcast [10 x i32]* %1 to i8*
  call void @llvm.memset.p0i8.i64(i8* align 16 %3, i8 0, i64 40, i1 false)
  store [10 x i32]* %1, [10 x i32]** %2, align 8
  ret i32 0
}

其实类似的声明还有指向数组对象的指针(和数组名隐式转换为的指针类型不同):

1	int (*pointer_to_array)[10];

之前我也介绍过，引用在编译器里面是使用指针来实现的，下面的代码会生成一模一样的LLVM-IR代码：

1
2
3

int i_array[10]={0};
int (*pointer_to_array)[10]=&i_array;
int (&i_array_ref)[10]=i_array;

其LLVM-IR代码为：

define dso_local i32 @main() #5 {
  // declare i_array
  %1 = alloca [10 x i32], align 16
  // declare pointer_to_array
  %2 = alloca [10 x i32]*, align 8
  // declare i_arr_ref
  %3 = alloca [10 x i32]*, align 8

  // // initialize i_array
  %4 = bitcast [10 x i32]* %1 to i8*
  call void @llvm.memset.p0i8.i64(i8* align 16 %4, i8 0, i64 40, i1 false)

  // initialize pointer_to_array
  store [10 x i32]* %1, [10 x i32]** %2, align 8
  // initialize i_arr_ref
  store [10 x i32]* %1, [10 x i32]** %3, align 8
  ret i32 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++模板的牛刀小试而已。