究极鬼畜：泛型auto

阿罗拉！ / 2023-08-13 / 原文

究极鬼畜：泛型auto

零前言

C++ 作为一门强大的语言，标准库中为我们提高了许多相当实用的模板。

然而有时候你 ~~（其实整个机房就我一个）~~ 又自己有一些代码，想转化为一个封装好的板子。

这时候，你就不得不接触泛型编程了。

~~那个 auto 是为了押韵乱加的，虽然 auto 确实可以用来泛型……~~

由于作者水平有限，许多地方并不是很严谨，而仅仅是方便理解地进行解释。

一为什么要泛型？

对于一份代码，如下面这个函数：

int plus(int x,int y){
    return x+y;
}

显然，它有将两个数加起来的功能。

然而当传入的参数类型为 long long，编译器会隐式地（你，即调用者不需要专门体现出来）把这个参数转化为 int 类型，从而造成溢出。

一个无脑地做法是，直接把参数类型都改为最大类型（比如这里用 long long 或 __int128）。

然而如果传入的是浮点数，那么就又出现问题了：小数部分的精度将会丢失。

固然可以对每种类型都写一遍，如这样：

#define __plus__(_Tp)	\
_Tp plus(_Tp x,_Tp y){	\
	return x+y;			\
}
__plus__(long long)
__plus__(double)
......
#undef __plus__

但是我们有更简单，且更全面的做法：

template<typename _Tp>
_Tp plus(_Tp x,_Tp y){
    return x+y;
}

这样，编译器就会为不同的类型都生成出这样一个函数，前提是有代码调用了这个类型的 plus。

相比第一种实现，这样做的好处有：

代码更短，更方便。
不需要用 long long 处理 int（当然第一种实现多写几行也可以）。
不会生成较冗余的代码，即没有使用 float 类型的 plus，就不会生成对应的函数。
可以更方便地特化（对某一种情况特殊处理）。
……

可以看到，泛型编程非常实用且有效，因此在各类库中常常会被用到。

（当然平时也可以用，特别是你一份板子写好了就不想翻上去改的情况下。）

二使用 `template`

我们来看一下刚刚这段代码：

template<typename _Tp>
_Tp plus(_Tp x,_Tp y){
    return x+y;
}
signed main(){
    plus(1,2);
    plus(1.0,3.2);
}

相较于普通函数，plus 明显地多出了一个叫 template 的东西，这就是模板元参数。

这份代码的原理翻译一下是：

template 发现你这玩意儿是泛型，有个 typename 类型的模板参 _Tp，就把编译器踢起来。
编译器出去转了圈，发现 _Tp 传了 int 和 double 两种参数。
编译器回来，把这两种参数的代码给写了一遍，然后把 int 和 double 填入对应的位置，替代掉那个占位的 _Tp。
函数调用的时候，找到最合适的一个（你不可能整型参数的函数不用，跑去用浮点型参数的函数吧）。

值得注意的是，编译器并不能很好地推断你的 _Tp 到底对应了什么类型，他是有要求的：

不能根据返回值推断，如 _Tp min(int x,int y) 就是非法的（鬼知道 _Tp 返回给谁），这种情况下需要手动指定，如 min<int>(3,4)。
不能经过类型转化，如 _Tp min(_Tp x,_Tp y) 不能生成供 min(2,3ll) 调用的函数。
……

并且注意，参数推导时可以得到“这是个指针”，但不能发现“这里要引用”或“这有 const 修饰”，因此在函数参数处要把对应的修饰填上。

当然，和函数参数一样，我们也可以有多个模板参，形如：

template<typename _Tp1,typename _Tp2>
bool less(_Tp1 x,_Tp2 y){
    return x<y?x:y;
}

定义起来就和函数一样方便，其实可以将模板参视作编译期间确定的参数，而 typename 占位符表示这传入的是一个类型而非产量。

没错，template 也可以传入常量，形如这样：

template<typename _Tp,int N,int *pri>
void get_prime(_Tp it){
    static bool vis[N];
    for(int i=2;i<N;++i){
        if(!vis[i]) pri[++pri[0]]=i;
        ......
    }
}

这里对 x 有要求，必须是编译期可以知道的整型常量（包括 bool，char，指针……）。

然后如果是编译器不可推断得到的模板参（这里的整型常量显然就不好推断），就需要我们手动指定，形如func<a,b,c,d,..>(x,y,z,...)，也即从左到右逐个指定，不可跳过。

但你还可以给一部分模板参预设参数，如：template<typename _Tp1,typename _Tp2=int>，这样如果编译器没办法推断出 _Tp2，会先把这里当作 int 处理。当然，和函数一样，这部分也是需要放在最后几个参数上的。

值得注意的一点是，形如 template<typename _Tp=int>，尽管你都指定了预设的参数，但你调用时若不能推断，仍需要打上一对 <>，因为这里本质上依然是指定参数。

这些大概就是基本的 template 用法。

三模板参数包

这是一个更高级的模板参数，它的定义形如这样：

template<typename ...Args>
void func(Args ...args){
}

其中 ... 代表着这是一个参数包，即可接受多个参数。

既然如此，那一个函数中显然不能有多个这种参数，且它应该被放在最后。

这样有什么用呢？我们联想一下 C 的 printf，它可以支持任意多个参数，我们的 template 现在也可以了！（当然，C 是用 define 宏实现的，两者不能混为一谈）

那么我们要对这若干个参数进行展开，可以参照以下实现：

template<typename _Tp>
void func(_Tp x){
    //do somethins
}
template<typename _Tp,typename ...Args>
void func(_Tp x,Args ...args){
    func(x),func(args...);
}

这段代码的原理是：在参数大于一个时调用下面的函数进行递归展开，当参数只有一个时调用上面的函数进行处理，其中 args... 意味展开 args 这个参数包。

不过还有另一种做法，不需要进行递归，用到了 C++ 11 的 initializer_list（这是个很轻巧的小东西，你可以放心使用）。

template<typename _Tp>
void func(_Tp x){
    //do somethins
}
template<typename _Tp,typename ...Args>
void func(_Tp x,Args ...args){
    std::initializer_list<int>{(func(args),0/*这里用逗号表达式塞一个0进去，因为前面要求返回值为int*/).../*错误写法 (func(args...),0)*/};
}

上面说到的错误写法相当于把整个参数包展开传给 func，而会调用到自身，造成死循环。正确写法则是只传入一个参数，然后展开这个过程。

除此之外还有个很鬼畜的东西，我们可以用 sizeof...(args) 或 sizeof...(Args) 来得到参数包的大小而不计算……暂时想不出有什么用。

结合前面两部分，我们就可以写出一份漂亮的快读：

template<typename _Tp>
void read(_Tp &x){
    x=0;bool flag=false;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=true;
    if(flag) for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)-(ch&15);
    else for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch&15);
}
template<typename ...Args>
void read(Args &...args){
    void(std::initializer_list<int>{(read(args),0)...});
}

但是有个问题，这份快读只支持整数类型，那我想读字符串，或者自定义一个类型，怎么办？

看下一部分。

四特化

模板的特化很简单，比如对于上面的快读，你只需要这样：

template<>//你如果放在前两个函数上面，甚至这行都能删，但不建议删
void read/*这个可以不要*/<std::string>/*就是这部分*/(std::string &str){
    std::cin>>str;//这里就图方便了
}

不过细究下来，特化还是有很多要求，这里暂时就不展开讲了。

五仿函数

仿函数的本质是类，但调用方式却类似于函数。

常见的仿函数如 std::less 等等用于比较的仿函数，还有一种比较高级的是 std::function。

而当你使用 std::less 的时候，会发现STL容器要求你后面不接 ()，但如 std::sort 一类的STL函数，则要求你后面接这个 ()。

这就要唠嗑一下仿函数的实现了。

我们看这一段代码：

template<typename _Tp>//类的泛型和函数的基本原理类似，但使用时有些不一样的地方，一般不影响
struct less{
    bool operator()(const _Tp &x,const _Tp &y)const{
        return x<y;
    }
};

这里我们重载了 () 运算符，因此可以有这样的调用：

less cmp;
cmp(3,5);

这样，cmp 就可以类似与函数地进行使用。

而STL容器内部，就是用传入的 _Compare 定义了一个 Compare 成员，然后使用该成员进行比较。

但是STL算法提供的接口，要求你使用提供这么一个成员（因为内部是直接调用函数的形式），所以你要在传参的时候构造这么一个对象，也就是调用构造函数生成一个。

仿函数有什么用呢，比如上面，比较运算符不能作为模板参或者函数参数传入，这时你就只能传一个仿函数来实现。

而且我们还可以再来看个好玩的：

struct modify{
    int L,R,Val;
    void func(int p,int l,int r){
        //线段树区间修改……
    }
    modify(int _L,int _R,int _Val):L{_L},R{_R},Val{_Val}{func(1,1,n)}
};
modify(1,n,-114514)

看起来是不是很无聊？其实也有点用处。

我们知道，传参需要往栈里面放参数，这会导致大量的时间和空间消耗。

一种解决方法是借助引用来传入固定不变的参数，同时避免不必要的拷贝，但引用这玩意儿并不是很靠谱，因为其底层实现依然是指针，而你还需要对指针进行解引用，这样一来反而会更慢……

现在我们写出这样一个类，把固定不变的参数作为其成员变量，就可以避免对这部分的传参，起到优化~~（卡常）~~的作用。

上面的实现和仿函数存在一点区别，它可以直接调用。事实上，这样的实现更贴近我们下面要介绍的小东西：lambda表达式。