模板——黑魔法入门到入土

小菜鸟

2022-07-11 16:54:42

Tech. & Eng.

C++黑魔法入门

C++的模板是图灵完备的，能够玩出很多有用的或没用的花活。

所以本文将会带着读者了解模板的使用，并尝试入门模板元编程。

本文的主要目标群体是有一定C++基础的同学，提到的内容可能比较晦涩，看不懂的跳过就行了，总会有适合你的内容

由于NOI系列默认语言标准为C++14，本文也将采用C++14。少数在C++17中出现的特性将注明。

若要使用本文的代码，请#include<type_traits> <utility>和<cstdint>

前置知识

  1. 模板

    C++中有函数模板、类模板、变量模板。

    声明方式：template<模板形参>函数/类/变量，其中形参可以是类型，也可以是有一定限制的值（非类型模板形参），甚至可以是模板（模板模板形参）

    使用方法：模板名<模板实参>

    根据给定的模板实参，编译器将把整个模板中涉及到模板形参的地方替换成模板实参，从而实例化出对应代码。

    例

    函数模板：

    template<typename T>
constexpr size_t size_of()
{
   return sizeof(T);
} //size_of<char>()==1

    类模板：

    template<typename T>
struct wrapper
{
   T value;
} //wrapper包装了一个T类型的值

    变量模板（C++14起）：

    template<typename T>
constexpr size_t size_of=sizeof(T);
//size_of<char>==1

  2. （非必要）模板实参推导(template argument deduction, TAD)

    对于函数模板的参数可以进行一些推导，如

    template<typename T>
size_t size_of(const T&){return sizeof(T);}
//size_of('a')==1. Deduce T as char.

    详细规则

    C++17起类模板也可以推导(class template argument deduction, CTAD)

    详细规则

  3. （重要） 模板的特化(specialization)

    可以对于指定的模板实参生成指定的代码，如

    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)

    对于类模板、变量模板（函数模板不行）可以指定其中一部分模板实参，或是指定部分实参的形式。 对模板进行特化/偏特化时，模板形参和实参不再一一对应，而是由指定的模式进行匹配。（详见下文的链表）

    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)

    可以声明一组形参，在使用时展开。如

    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

    也可以以特定模式展开，如完美转发（之后会提到）

    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)

    template<auto args...> //C++17起在非类型模板形参中可以使用auto来推导
constexpr auto accumulate=(args+...); //folding外面要有括号
//accumulate<1,2ll,3.0>展开为1+(2ll+3.0)

    不作详细展开，感兴趣自行查询cppreference

  6. （了解即可）C++11起可以用using代替typedef书写类型别名。

    区别是using可以带着模板。

    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起可以省略消息，只写一个表达式）

    static_assert(std::is_same_v<int,bool>,"int and bool are different types!");

魔法の开端

有了这些东西，我们就可以试着来进行编译时计算了！

  1. Fibonacci

    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. 编译时单链表

    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皆为类型）

模板模板形参的应用。

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：尝试实现一个编译时左偏树或配对堆。

高阶の魔法

很多时候我们需要精确描述一个偏特化的约束条件。

C++20提供的concept很好地满足了这个需求，但C++20以前呢？

答案是SFINAE(Substitution Failure Is Not An Error，替换失败不是错误)。

简单来说，编译器寻找可行的偏特化重载时，会试图把形参替换为实参。如果替换过程中出现一些失败的情形（这些情形称作SFINAE错误），那么不会CE，而是会不考虑这一重载。

例如

//这个实现方法叫偏特化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并非只有这一种方法，这里有更多方法。

在下文对于CRTP的介绍中也展示了一个SFINAE手法，是一个较为古典的实现。

返 璞 归 真

说了这么多，还是要来看一看模板的实际使用价值。

  1. 泛型编程，节约代码量。（不多说

  2. 计算量纲

    有了上面的基础应该没啥难度吧？

    这个在boost::mpl中有出现。

  3. 对特定情形进行精准而优雅的优化

    例如写容器的时候，存各种不同指针的容器本质上是一样的。（考虑std::set<int*>和std::set<void*>有没有区别？）

    那么对于每个T*都生成一遍代码将是极大的浪费。

    所以我们可以通过SFINAE令T不为void时，container<T*>的实现依赖于container<void*>并进行简单的类型转换。

  4. 还是优化

    众所周知，矩阵连乘的不同顺序会极大地影响计算效率。那么我们可以在编译时通过元编程DP计算出最优顺序。

    于是在运行时就能得到比较好的效果。

    这个方法在正经的线性代数库里都会用到。

  5. 其他神奇的优化

  6. 神仙

在实践中还有一些技巧可以讲。

  1. 完美转发

    我们有时候要将一个函数的参数原封不动地传递给另一个函数。

    典型的如标准库中的emplace类函数。

    这里涉及到：值类别（详见往期洛谷日报）、模板实参推导。

    //在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中有一个规则叫做引用折叠
//规则：(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。

    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。

    一个基本的想法就是使用模板接受不同类型，并用虚函数来擦除类型。

    一个简化的（并不完善的）实现

    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>，从而自动获取一些功能。

    例如，我们可以自动给拥有小于号的类型添加大于号。

    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

    想必大家都希望能将快读做得好用一些。

    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. 实现可以快速重用的数据结构/算法，避免类似的代码反复出现。

    比如我自己的玩具库

    之后会单独开文章讲如何把自己熟悉的模板写成泛型代码。

想到新的好玩的还会再更的（

2023.1.1 update

管理大大认为文字说明不够详细，本次新增注释（特别是编译时链表、模板模板形参），并加上了按值传递的部分。

同时修改了少量容易误解的表述。

后记

高考完终于有时间整活了！

很久没写C++了，这篇文章算是自己复习一下（虽然早就想写这个了

有兴趣玩耍黑魔法的人可以一起交流~