模板——黑魔法入门到入土
小菜鸟
2022-07-11 16:54:42
# C++黑魔法入门
C++的模板是图灵完备的，能够玩出很多有用的或没用的花活。
所以本文将会带着读者了解模板的使用，并尝试入门模板元编程。
**本文的主要目标群体是有一定C++基础的同学，提到的内容可能比较晦涩，看不懂的跳过就行了，总会有适合你的内容**
**由于NOI系列默认语言标准为C++14，本文也将采用C++14。少数在C++17中出现的特性将注明。**
**若要使用本文的代码，请`#include<type_traits>` `<utility>`和`<cstdint>`**
## 前置知识
1. 模板
C++中有函数模板、类模板、变量模板。
声明方式：`template<模板形参>函数/类/变量`，其中形参可以是类型，也可以是有一定限制的值（非类型模板形参），甚至可以是模板（模板模板形参）
使用方法：`模板名<模板实参>`
根据给定的模板实参，编译器将把整个模板中涉及到模板形参的地方替换成模板实参，从而**实例化**出对应代码。
例
函数模板：
```cpp
template<typename T>
constexpr size_t size_of()
{
return sizeof(T);
} //size_of<char>()==1
```
类模板：
```cpp
template<typename T>
struct wrapper
{
T value;
} //wrapper包装了一个T类型的值
```
变量模板（C++14起）：
```cpp
template<typename T>
constexpr size_t size_of=sizeof(T);
//size_of<char>==1
```
2. （非必要）模板实参推导(template argument deduction, TAD)
对于函数模板的参数可以进行一些推导，如
```cpp
template<typename T>
size_t size_of(const T&){return sizeof(T);}
//size_of('a')==1. Deduce T as char.
```
[详细规则](https://zh.cppreference.com/w/cpp/language/template_argument_deduction)
C++17起类模板也可以推导(class template argument deduction, CTAD)
[详细规则](https://zh.cppreference.com/w/cpp/language/class_template_argument_deduction)
3. **（重要）** 模板的特化(specialization)
可以对于指定的模板实参生成指定的代码，如
```cpp
template<typename T>
constexpr bool is_integral_v=false; //对于大多数类型，它们不是整数
template<>
constexpr bool is_integral_v<int>=true; //int是整数
template<>
constexpr bool is_integral_v<long>=true; //long是整数
...
```
4. **（重要）** 模板的偏特化(partial specialization)
对于类模板、变量模板**（函数模板不行）**可以指定其中一部分模板实参，或是指定部分实参的形式。
对模板进行特化/偏特化时，模板形参和实参不再一一对应，而是由指定的模式进行匹配。（详见下文的链表）
```cpp
template<typename T,typename... Args>
constexpr bool begin_as_int_or_ptr=false;
template<typename... Args>
constexpr bool begin_as_int_or_ptr<int,Args...>=true; //指定模板参数第一项为int
template<typename T,typename... Args>
constexpr bool begin_as_int_or_ptr<T*,Args...>=true; //指定模板参数第一项为指针
```
同一模板的不同特化/偏特化之间可以认为存在包含关系。如果特化a的要求被满足时，特化b的要求也满足（且两者要求不相同）则认为a比b更特殊。
编译器会试图找到所有特化里最特殊的一个。如果有多个或不存在，那么CE。
5. **（不必要但很有用）** 形参包(parameter pack)
可以声明一组形参，在使用时展开。如
```cpp
auto sum(){return 0;} //提前考虑边界情况
template<typename T,typename... Args>
auto sum(T v,Args... args)
{
return v+sum(args...); //args被展开
}
//sum(1,2ll,3.0)
//==1+sum(2ll,3.0)
//==1+(2ll+sum(3.0))
//==1+(2ll+(3.0+sum()))
//==1+(2ll+(3.0+0))
//==6.0
```
也可以以特定模式展开，如完美转发（之后会提到）
```cpp
template<typename... Args>
decltype(auto) foo(Args&&... args)
{
return bar(std::forward<Args>(args)...);
//对于任意Args中的T和args中对应的v，展开为std::forward<T>(v)
//要求Args和args有相同的长度
//sizeof...(Args)可以获得Args的长度
}
```
C++17开始有折叠表达式(folding)
```cpp
template<auto args...> //C++17起在非类型模板形参中可以使用auto来推导
constexpr auto accumulate=(args+...); //folding外面要有括号
//accumulate<1,2ll,3.0>展开为1+(2ll+3.0)
```
不作详细展开，感兴趣自行查询[cppreference](https://zh.cppreference.com/w/cpp/language/fold)
6. （了解即可）C++11起可以用`using`代替`typedef`书写类型别名。
区别是`using`可以带着模板。
```cpp
using u64=uint64_t; //Same as typedef uint64_t u64;
template<typename T>
using point=std::pair<T,T>; //Typedef cannot do this!
```
7. （了解即可）C++11起可以用静态断言来判断一个编译时表达式是否为`true`。如果为`false`，会导致编译错误并输出引号中的消息。
（C++17起可以省略消息，只写一个表达式）
```cpp
static_assert(std::is_same_v<int,bool>,"int and bool are different types!");
```
## 魔法の开端
有了这些东西，我们就可以试着来进行编译时计算了！
1. Fibonacci
```cpp
using u64=uint64_t;
template<size_t N> //主模板，有一个非类型模板形参
constexpr u64 fib=fib<N-1>+fib<N-2>;
template<> //特化
constexpr u64 fib<0>=1;
template<>
constexpr u64 fib<1>=1;
```
很简单对吧（
可以看到模板能够写成递归函数的样子。这种函数叫做元函数。
2. 编译时单链表
```cpp
template<typename T,T val,typename Next>
struct node
{
static constexpr T value=val; //把模板参数存进类里方便取出来
};
using null_type=void;
template<typename> //此处可以利用偏特化判断空链表或错误类型并给出提示
struct pop_front{}; //主模板不需要实质性内容
template<typename T,T val,typename List>
struct pop_front<node<T,val,List>>
//一个node实际上可以视为T,val,List打包
//偏特化的过程就是匹配node<T,val,List>的模式来解包
//有Haskell或Rust或其他fp风格经验的话应该不陌生
{
using type=List; //将当前node解包后取出List，实际上就是舍弃了链表的头结点
};
template<typename List,typename T,T val>
using push_front_t=node<T,val,List>; //push就是直接把原先的头结点打包进新的头结点
template<typename List>
using pop_front_t=typename pop_front<List>::type; //用来简化、统一代码的别名
template<typename List>
constexpr auto get_top_v=List::value; //当前结点就是头结点，直接取出值就行
//想一想，_a, _b, _c分别是什么类型什么值？
using a=push_front_t<null_type,int,1>;
constexpr auto _a=get_top_v<a>;
using b=push_front_t<a,char,'x'>;
constexpr auto _b=get_top_v<b>;
using c=pop_front_t<b>;
constexpr auto _c=get_top_v<c>;
```
可以看到模板能够作为编译时容器保存类型和值，并且能实现复杂的模式匹配。
练习1：给定一个模板`T<A,B>`，试求得类型`T<B,A>`（其中`A, B`皆为类型）
模板模板形参的应用。
```cpp
template<typename>
struct swap{};
template<template<typename,typename>class Tp,typename A,typename B>
struct swap<Tp<A,B>>//首先声明Tp,A,B并且Tp是接受两个类型实参的模板
//随后匹配Tp<A,B>这一模式将接受的类型解包
//注意：Tp前的class在C++17前只能是class，之后一般用typename代替class
{
using type=Tp<B,A>;
};
template<typename T>
using swap_t=typename swap<T>::type;
```
模板模板形参的一个典型应用场景是分配器的rebind：
对于容器`container<T>`，其分配器理应是`allocator<T,Args...>`。但是容器内部并不一定直接存储元素，而可能是结点。这个时候需要将`allocator<T,Args...>`rebind成`allocator<node<T>,Args...>`。
也就是用分配器的类型匹配`Alloc<T,Args...>`这一模式，从而得到`Alloc,T,Args...`并用这些参数构造出`Alloc<node<T>,Args...>`。
练习2：尝试实现一个编译时左偏树或[配对堆](https://www.luogu.com.cn/paste/cgvwq79p)。
## 高阶の魔法
很多时候我们需要精确描述一个偏特化的约束条件。
C++20提供的`concept`很好地满足了这个需求，但C++20以前呢？
答案是SFINAE(Substitution Failure Is Not An Error，替换失败不是错误)。
简单来说，编译器寻找可行的偏特化重载时，会试图把形参替换为实参。如果替换过程中出现一些失败的情形（这些情形称作SFINAE错误），那么不会CE，而是会不考虑这一重载。
例如
```cpp
//这个实现方法叫偏特化SFINAE，是当前更惯用的方法
template<bool,typename T=void>
struct enable_if //偏特化SFINAE中常用的辅助类
//注意，C++11开始这个辅助类就在标准库里了
{
using type=T;
};
template<typename T>
struct enable_if<false,T>
//对于条件不成立的情况，不定义type，从而在试图取得type时制造一个SFINAE错误
{};
template<bool cond,typename T>
using enable_if_t=typename enable_if<cond,T>::type;
template<int,typename T=void> //#1
constexpr bool negative=false;
template<int val> //#2
constexpr bool negative<val,enable_if_t<(val<0)>> =true;
```
当`val<0`时，`#2`比`#1`更特殊，故匹配到`#2`。
当`val>=0`时，`enable_if_t<false,void>`不存在，故替换`#2`时产生错误，可行重载只剩下`#1`，匹配到`#1`。
此外SFINAE能获取一些普通方法难以得到的类型信息，从而实现一些复杂的操作。
SFINAE并非只有这一种方法，[这里](https://zh.cppreference.com/w/cpp/language/sfinae)有更多方法。
在下文对于CRTP的介绍中也展示了一个SFINAE手法，是一个较为古典的实现。
## ~~返 璞 归 真~~
说了这么多，还是要来看一看模板的实际使用价值。
1. 泛型编程，节约代码量。（不多说
2. 计算量纲
有了上面的基础应该没啥难度吧？
这个在`boost::mpl`中有出现。
3. 对特定情形进行精准而优雅的优化
例如写容器的时候，存各种不同指针的容器本质上是一样的。（考虑`std::set<int*>`和`std::set<void*>`有没有区别？）
那么对于每个`T*`都生成一遍代码将是极大的浪费。
所以我们可以通过SFINAE令`T`不为`void`时，`container<T*>`的实现依赖于`container<void*>`并进行简单的类型转换。
4. 还是优化
众所周知，矩阵连乘的不同顺序会极大地影响计算效率。那么我们可以在编译时通过元编程DP计算出最优顺序。
于是在运行时就能得到比较好的效果。
这个方法在正经的线性代数库里都会用到。
5. [其他神奇的优化](https://www.zhihu.com/question/37135445/answer/1552075255)
6. [神仙](https://www.zhihu.com/question/66360542/answer/244544302)
在实践中还有一些技巧可以讲。
1. 完美转发
我们有时候要将一个函数的参数原封不动地传递给另一个函数。
典型的如标准库中的`emplace`类函数。
这里涉及到：值类别（详见往期洛谷日报）、模板实参推导。
```cpp
//在OI中常见的转发写法不考虑值类别，因为OI一般不涉及复杂的类型结构
//考虑如下情况
template<typename T>
auto foo(T a)
{
return bar(a);
}
//我们看到a可能将会被拷贝
//但要是a明明可以移动呢
//要是没有拷贝构造函数或者拷贝很慢呢
//考虑移动
template<typename T>
auto foo(T&& a)
{
return bar(std::move(a));
}
//要是a是个左值呢？移动走了原来的地方不就炸了？
//要是a是const的呢？
```
综上我们发现简单的拷贝/移动不足以完成转发，那么我们需要编译器帮助我们推导。
```cpp
//cpp中有一个规则叫做引用折叠
//规则：(T&)&&=T&
// (T&&)&=T&
// (T&&)&&=T&&
//另外对于转发引用，有特殊的模板实参推导规则
//template<typename T>
//void foo(T&& x);
//int a;foo(a);=>T推导为int&
//foo(1);=>T推导为int
//来看看在完美转发中如何利用这两条规则
template<typename T>
T&& std::forward(std::remove_reference_t<T>& v)
{
return static_cast<T&&>(v);
}
template<typename T>
T&& std::forward(std::remove_reference_t<T>&& v)
{
return static_cast<T&&>(v);
}
//remove_reference_t<T>，顾名思义
//T=X&时为X
//T=X&&时为X
//否则为T
template<typename T>
auto foo(T&& a)
{
return bar(std::forward<T>(a));
}
//考虑a的三种情况
int a;foo(a); //#1
//此时T推导为int&
//std::forward<int&>(a)即[伪代码]static_cast<int& &&>(a)，即static_cast<int&>(a)
//a是可变左值，cast到int&是正确的
const int a;foo(a); //#2
//此时T推导为const int&
//转发过程是static_cast<const int&>(a)
//同#1，显然也是正确的
foo(1); //#3
//1是个临时量，所以T&&即int&&，T推导为int
//转发过程是static_cast<int&& &&>(a)即static_cast<int&&>(a)
//a的右值性质得到了保留
//于是完美转发成功了！
//和形参包结合，就有了之前的代码
template<typename... Args>
decltype(auto) foo(Args&&... args)
{
return bar(std::forward<Args>(args)...);
}
//其中decltype(auto)保证了返回引用时也能正确推导，也就是返回值的完美转发
//因为auto不能正确推导出右值引用
```
一个小细节：有些时候，无论你怎么传递引用都免不了最终要复制，因为你要保存实实在在的数据，那么要么通过移动取得所有权，要么复制。
一个典型场景是构造容器结点的时候，如果传入的并非右值，容器内部的数据必然是复制而来的。这时有一个Best Practice：接收参数的时候直接按值传递，转发时用`std::move`。
```cpp
template<typename T>
struct wrapper
{
T value;
wrapper(T val): //这种做法实际上是在第一次接收参数时就确定了移动或者复制。
//在按值传递时，如果实参是个可移动的值（非const右值），val就是移动构造（或直接构造得来的）
//如果不可移动（左值或const），val就是复制的
//无论哪种情况，我们都已经获得了一个T对象的所有权，接下来一路移动就可以了
value(std::move(val))
{}
};
```
由于本文的重点不是值类别，本文不会精确区分将亡值(xvalue)和纯右值(prvalue)，并将从xvalue移动和从prvalue直接构造视为同一种情况。
2. 类型擦除
类型擦除是指在运行时抹去一些类型信息，只剩下少量编译时已知的特征。
典型的如`std::function`。
一个基本的想法就是使用模板接受不同类型，并用虚函数来擦除类型。
一个简化的（并不完善的）实现
```cpp
template<typename Res,typename... Args>
struct fn_base //注意此处的模板形参里没有Fn
{
virtual Res operator()(Args...)=0;
};
template<typename Fn,typename Res,typename... Args>
struct fn_block:fn_base<Res,Args...> //但是这里的模板形参有Fn
//换言之，fn_block在编译时保留了Fn的类型信息，而fn_base不保留Fn的类型信息
{
Fn fn;
fn_block(Fn&& f):
fn(std::move(f))
{}
Res operator()(Args... args)override
{
static_assert(std::is_convertible<decltype(fn(std::forward<Args>(args)...)),Res>::value,
"Can't be called with these arguments!");
//编译时限制fn必须能以fn(args...)的形式调用，并且返回的类型是Res或能转换为Res
return fn(std::forward<Args>(args)...);
}
};
//以上是类型擦除的过程
//可以看到，fn_base通过虚函数抹去了fn_block中事实上的类型，只保留了Res(Args...)这一调用签名
template<typename>
class function{};
template<typename Res,typename... Args>
class function<Res(Args...)>
{
std::unique_ptr<fn_base<Res,Args...>> fp;
public:
function()=default;
function(function&&)=default;
template<typename Fn> //最终构造的时候将Fn的类型信息直接传给fn_block，随后Fn的真实类型就无从得知了
function(Fn fn):
fp(new fn_block<Fn,Res,Args...>(std::move(fn)))
{}
function& operator=(function&&)=default;
template<typename Fn>
function& operator=(Fn fn)
{
fp=new fn_block<Fn,Res,Args...>(std::move(fn));
return *this;
}
Res operator()(Args... args)
{
return fp->operator()(std::forward<Args>(args)...); //虚调用，并不知道fp指向的具体类型
}
};
template<typename Res,typename... Args>
function(Res(*)(Args...))->function<Res(Args...)>;
//C++17开始的自定义类模板实参推导
//对于使用函数指针来构造的情况，直接从函数指针推导调用签名，可以不用手动指定模板参数
//举个例子
function my_puts=puts;//然后my_puts就可以当cstdio里面的puts用了，调用签名推导为int(const char*)
```
上面直接使用了虚函数。在实际应用中，对于函数指针等比较小的可调用对象，可以直接存进`function`中而不需要分配空间，称作小对象优化（Small Object Optimization,SOO）。
仿函数有很多骚操作，如`std::bind`，等有空了可能会实现一个挂上来。
3. CRTP（奇异的递归模板重现方式）
简单来说，`A`可以继承自`T<A>`，从而自动获取一些功能。
例如，我们可以自动给拥有小于号的类型添加大于号。
```cpp
template<typename T>
struct make_greater_op
{
//我们需要先判断T是否有小于号
//在C++20中我们可以通过concept来实现这一功能，但更早的C++需要依赖奇技淫巧
//这里出现的是古典的SFINAE方法，利用函数的参数、返回值来制造替换失败
//再次提醒，有concept优先用，不行的话用偏特化SFINAE，还不行再用古典SFINAE
private:
template<typename U>
static auto helper(const U& x)->decltype((x<x),std::true_type());
//在返回类型中带上x<x
//以此判断U是否有小于号，若有，则此重载替换成功，helper返回类型为true_type
static auto helper(...)->std::false_type;
//仅有...形参的重载拥有最低的优先级，在其他情况均替换失败的情况下匹配此重载，返回false_type
//在C++11以前没有decltype的时候，可以将两个函数的返回类型定为不同大小的类型，用sizeof判断对应重载
public:
bool operator>(const T& rhs)const
{
static_assert(decltype(
helper(rhs)
)::value,
"T must have operator< !"
); //若T没有operator<，则静态断言失败
return rhs<(const T&)(*this); //利用已有的小于号自动生成大于号
}
};
struct has_less:public make_greater_op<has_less>
{
int n;
bool operator<(const has_less& rhs)const
{
return n<rhs.n;
}
};
//于是has_less自动获得了operator>
```
相对于一般的继承，CRTP使得基类可以使用派生类的部分信息，从而为派生类提供更灵活的功能。
我们注意到这个方式和虚函数/类型擦除的机制有些类似：我们不需要关心派生类的具体类型，而只需要某些特定操作。有些人把CRTP称作静态多态。
## ~~走 近 O I~~
在OI中上面这些花里胡哨的技巧可能没有大用，但我们依然可以从模板机制中获益。
1. 方便的Pascal式IO
想必大家都希望能将快读做得好用一些。
```cpp
char gc();//更快的getchar，各位按自己的喜好写
void pc();//更快的putchar，同理
template<typename T>
void read(T& x)//对各种整数通用
{
x=0;
bool sym=0;
char c=gc();
while(!isdigit(c))
{
sym^=(c=='-');
c=gc();
}
while(isdigit(c))
{
x=x*10+c-48;
c=gc();
}
if(sym)x=-x;
}
template<size_t N>
void read(char (&str)[N]) //编译时提取数组大小来判断边界，防止溢出
{
size_t n=0;
char c=gc();
while(n<N-1&&!isspace(c))
{
str[n]=c;
c=gc();
++n;
}
str[n]=0;
}
...//可以给自己想要读的东西写read
template<typename T,typename... Args>
void read(T& x,Args&... args)//由此实现了简洁易用的读入
{
read(x);//这里的单参数read是前面写好的对特定类型的快读
read(args...);//C++14没有折叠表达式，所以习惯用递归来展开参数包
//实际上折叠表达式也就是递归的语法糖
//在C++17以后不需要用x解出第一个参数，可以用((read(args),1)&&...)
//一步到位，借助短路运算符保证读取顺序正确
}
```
输出就作为练习吧┏ (゜ω゜)=☞
2. 实现可以快速重用的数据结构/算法，避免类似的代码反复出现。
比如[我自己的玩具库](https://github.com/ILSYT/OIerTemplateLib)
之后会单独开文章讲如何把自己熟悉的模板写成泛型代码。
想到新的好玩的还会再更的（
### 2023.1.1 update
管理大大认为文字说明不够详细，本次新增注释（特别是编译时链表、模板模板形参），并加上了按值传递的部分。
同时修改了少量容易误解的表述。
## 后记
高考完终于有时间整活了！
很久没写C++了，这篇文章算是自己复习一下（虽然早就想写这个了
有兴趣玩耍黑魔法的人可以一起交流~