C++模板入门

函数模板

C++可以重载函数，即可以定义多个函数名相同但是参数不同的函数，使用时编译器会自动选择。

我们可以定义两个分别计算 float 和 int 类型的相加的函数：

注意定义的浮点字面量后面没有 f 的话是默认为 double 类型。

问题出现了，如果我们想要其它类型也能使用 add 这个函数呢，或者要两个不同类型（如 int 和 float）相加呢？每增加一个类型就需要写一遍函数，太费程序员键盘了。

我们可以定义一个函数模板来解决这个问题：

在函数定义上面一行加上 template 关键字，尖括号里的 typename 表示定义的模板是一种类型，T1 是程序员自己定义的标识符，称为模板参数，代表了一个类型，T2 同理，后面就可以使用这个类型了，T1 a 表示 a 是 T1 类型的，T1 具体是哪个类型是调用这个 add 函数的时候确定的。比如 main 函数里的第一个调用，T1 是 int ，T2 是 double，确定模板参数的过程叫实例化。

学了模板就明白刚入门写的 ”hello world“ 原来也是有学问的，cin 和 cout 用的 >> 和 << 也是模板函数，所以能处理各种类型的数据。

返回值类型是 auto ，这也是由编译器自动推断返回类型，C++14的特性，编译时注意使用C++14以上标准，如 g++ 编译时的命令：

除了用模板定义类型，还可以定义数据：

N 是模板参数，它是一个 int 类型的数，这个函数在调用时编译器就没法推断了，我们需要指定 N 是多少，调用处的函数名后面尖括号填入模板参数 100 ，这个函数实现的是控制台打印 0 - 99 。

模板类

我们定义类的时候可以使用模板，模板类使用得较多，STL 当中定义了丰富的模板类。

我们可以定义一个模板类，可以存储任意类型，只有一个成员函数，就是把存储的数据打印出来：

模板类本身是一个类型，使用时需要把模板参数加上，模板参数也可以是数据，而且类成员函数也可以是模板函数。

特化和偏特化

特化是指定特定的模板参数对应的函数体，有点抽象，请看代码：

这段程序会先输出一句 "specialization"，再打印 0 - 99。

语法就是 template<>，尖括号里不写东西，下一行是是函数定义，函数名后面的尖括号写要特化的模板参数，调用的时候用到这个模板时就会调用你新定义的那个函数。模板类的特化就是类名后面写特化的参数了。

偏特化是只对部分模板参数特化，只有模板类支持，模板函数不支持：

我们用构造函数检验模板参数，这段程序会输出 1 - 6，再打印 "specialization"。

只要其中一个模板参数符合你偏特化的情况，那无论其它模板参数是什么，都会选择特化的那个定义。

上面只演示了模板参数是数值的情况，模板参数是类型其实也是类似的。

总结

所谓模板，是定义一个模子，填入不同的模板参数会生成不同的函数（类），gcc 和 msvc 等编译器就会针对不同的特化生成不同的汇编代码，所以特化越多，生成的代码体积越大。

上面的知识对C++复杂的模板系统来说只是很小一部分，我自己也太菜了，只能介绍这么多了。

前置芝士先到这里，下面点题。

利用模板进行循环展开

模板递归计算阶乘

以下内容应该不是语言层面的，但 gcc，msvc 等编译器应该适用。

上面提到模板的实例化是由编译器完成的，也就是在编译期所有特化的函数内部汇编，什么意思呢，我们实现一个阶乘计算函数：

它会递归地实例化 factorial<5> 到 factorial<0>，factorial<0> 是特化的返回 1，则到这里就停止了。

用模板递归代替循环

上面的阶乘实际上已经实现了类似循环的效果，利用递归的思想，我们设计一个函数从  0 打印到 N ：

函数会打印 0-100。

和阶乘类似，改变调用时的模板参数可以改变循环上界，改变模板特化的值可以改变循环下界。

现在的问题是，模板函数递归好像和普通递归一样，但根据生成的汇编来看，只不过生成了很多的函数依次调用，并没有降低函数调用开销（存在push、pop和ret等语句说明在调用函数），也就无法实现优化。但是当我们开-O2及以上优化呢？

我们发现和函数调用有关的语句几乎没有了，这些代码大家都可以自己去测试一下。

运行时改变参数

前面的代码的模板参数都是在编译期定好的，现在要我们从控制台输入一个 n，打印 0 到 n 要如何做到呢？我们可以定义一个选择函数 print_it ，用 switch 或者 if 语句判断：

但是又是个费键盘的活，所以我们让 print_it 使用模板递归：

这里模板参数也用了默认参数 N = 0 ，也就是说不填模板参数时，N 默认为 0，再特化一个上限（因为 gcc 允许的模板递归层数为 900），当然，现在的问题是它似乎又回到了普通的递归，所以建议主体函数（在这里就是 print 函数）体执行时间较长使用这个方法，否则 switch 可能会更快。

性能实测

直接贴 洛谷P1919 测试结果，使用模板递归的 FFT 性能接近第一名 NTT+AVX2 优化，而我没有对其进行任何手动的 simd 优化，可读性较好。

后面可能会更新这个 FFT 的实现细节，或者 FFT 从最基础开始优化的个人历程。透露一下，基于这个 FFT 设计的高精度乘法，在编译器开启自动 AVX 优化后的性能可以接近甚至超过GMP 库！