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

小菜鸟 · 2022-07-11 16:54:42 · 科技·工程

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++了，这篇文章算是自己复习一下（虽然早就想写这个了

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