Learning a Part of C++(for ACM/ICPC) (4) 模板初步

在真的跳入使用STL之前，我们最后来认识下一个重要概念——模板（其他语言里称之为泛型）。

1、初识模板——模板函数

在这里思考了很久，我们还是从输入挂开始吧。
首先一起来看看夏天的风的输入挂 （输入输出加速）：

Exp 4.01
编译运行以下代码，输入12345 12345678901234 12345678901234，观察scan_d()的行为、printf()和out()输出的结果的差异

#include <stdio.h>
#include <math.h>
template <class T>  
inline void scan_d(T &ret) {  
    char c; ret=0;  
    while((c=getchar())<'0'||c>'9');  
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();  
}
inline void out(int x){  
   if(x>9) out(x/10);  
   putchar(x%10+'0');  
}
int main(){
    int a=0;
    long long b=0,c=0;
    scan_d(a);
    scan_d(b);
    scan_d<int>((int&)c);
    printf("%d %I64d %I64d\n",a,b,c);
    out(a); putchar(' '); out(b); putchar(' '); out(c);
    return 0;
}

首先分析scan_d()这个模板函数的写法。
第一行：template <class T>
template<>表明下面是个模板，<>内的东西，我们称作模板参数列表，具体在这里，class T表示声明了一个T，T待填，T应该填上一个类型名。
（据说在这里，class和typename是同义词，也就是说，你可以写作template <typename T>，我个人不确定，对此半信半疑）
所谓T待填，就是在这个函数里面，任何出现T的地方，都将被实际类型替代。

比如上面的scan_d(a);scan_d(b);
编译器会检查a和b的类型，a是int，b是long long，
那编译器知道了，
调用a的时候，那个T应该是int，然后生成了一份副本：

inline void scan_d(int &ret) {  
    //源代码上，内容一致
}

调用b的时候，那个T应该是long long，然后生成了一份副本：

inline void scan_d(long long &ret) {  
    //源代码上，内容一致
}

在里面做运算的时候，对a用int的运算，对b的调用，用long long的运算
——int的运算可比long long的运算快出一些来。

当然，你可也以强制指定类型，比如上面写的scan_d<int>((int&)c);。
这样，强制告诉编译器，对scan_d这个模板函数，我这里的调用指定T是int。

——等等，为什么函数参数那么别扭，带着(int &)？
——指定了T是int后，因为C++是个强类型语言，他会非常认真的确认，你传入的参数是不是和你指定的类型匹配，而long long类型的c与这里int的要求不匹配，如果不进行强制类型转换，会直接导致，编译错误，提示：

[Error] no matching function for call to 'scan_d(long long int&)

我们用几句简单的话，总结一下：

• 模板函数，第一行是template<>，说明这是一个模板函数。
• 尖括号内，放入一些待填信息（模板参数列表），比如class T1, typename T2。
• 之后函数的声明和实现中，所有写着T1、T2的地方，都会被编译器替换成相应的类型（或数值，具体在下面的模板类中说明），然后编译生成一种版本的函数调用。
• 对模板函数来说，编译器还会根据你传入的参数，推导待填的类型名应该是什么。
• 当然，使用模板函数时，我们也可以强制指定参数类型，具体语法函数名<模板参数列表>(函数参数列表)

Tips 4.01
为什么这样的输入挂会有加速效果？
scanf()/printf()是有缓冲区的，按理说这样应该很高效了才对。
可是注意到，前面有格式化字符串。比如你要读取10万个int，每次调用scanf都会重复解析这个格式化字符串，然后再去读入，就非常慢了。
输入挂直接确定了你要读入的数据类型，省去了字符串解析这个步骤，做到了提速。
（当然还有更快的输入/输出挂，一口气读入大量数据，一口气写出大量数据，就更好了）

Exercise 4.01
注意到上面我们在用out()函数输出的时候，普通函数out()会把所有传入的参数视作int类型，甚至long long也被转换成int，导致输出错误。
请把out()函数修改成模板函数，使其根据传入的参数，确定是要当做int输出（取模运算快一些），还是当做long long输出（取模运算慢一些，但是能正确输出long long）
（如果感兴趣，请试着加上对负数的支持）

2、模板类

思考这个情况：
写BFS的时候，我们要把扩展出的节点信息压入队列里。
如果是实现SPFA的时候，节点信息也许只有一个点的编号
如果是网格图上走的时候，节点信息是x和y，2个参数
如果转向还记做一步，那节点信息是x，y和方向，3个参数
………………………………
信息很多，但都用来表示位置的时候，那不放设计一个结构体吧：

struct State{
    int x,y,direction;
    //还有相应的构造函数等
}

这样，只要压入一个State结构体的实例进队列就好了。

如果我们直接数组模拟一个队列，有个问题——不可扩展啊！
第一次是存int元素的队列，之后要改一下，改成存State的队列，得修改压队列函数的参数、出队列函数的返回值、存队列的数组的类型，等等等等。
不仅改的烦，定了类型以后还不可扩展、不可复用。

那么我们想想，如果对队列这种通用数据结构，用泛型实现，不就一劳永逸了？

Exp 4.02
编译运行以下代码，观察结果，理解泛型类的写法与使用。

#include <stdio.h>
/************
循环队列，常见的数组模拟队列的实现方案
具体思想是，维护2个指针，一个头一个尾，从0开始往后移动，
移到MaxSize-1的时候，回到0
就相当于，看做MaxSize-1这个单元之后的下一个元素是0
************/
template<class X,int MaxSize>
struct LoopQueue{
    X data[MaxSize];
    int head,tail,sz;
    LoopQueue(){
        init();
    }
    void init(){
        head=0;tail=0;sz=0;
    }
    void push(const X& x){
        data[tail]=x;
        tail++;if(tail>=MaxSize)tail-=MaxSize;
        sz++;
    }
    void pop(){
        head++;if(head>=MaxSize)head-=MaxSize;
        sz--;
    }
    X front(){
        return data[head];
    }
    int size(){
        return sz;
    }
    bool empty(){
        return head==tail;
    }
};
LoopQueue<int,20> q;
int main(){
    for(int i=1;i<=10;i++){
        q.push(i);
    }
    while(!q.empty()){
        printf("%d ",q.front());
        q.pop();
    }
    puts("\n==========");
    for(int i=15;i<=30;i++){
        q.push(i);
    }
    while(!q.empty()){
        printf("%d ",q.front());
        q.pop();
    }
    return 0;
}

事实上泛型类在真的你去写一个的时候，没那么恐怖，和模板函数非常相似。
同样的，第一行template<模板参数列表>，之后正常的声明一个类，待填的地方用参数列表里的名字填进去，最后实例化这个模板类的时候，用类名<模板参数列表> 类的实例名;的格式（比如上面的LoopQueue<int,20> q;），然后使用的时候并没有任何特别的，只要正常的，使用这个类的方法，就行了。
注意：模板类，你就不要指望编译器帮你做类型推定了，你必须老老实实的写出模板参数

当然，注意到，这里有个模板参数，是个int类型的！
是的，你们没看错，是可以有一个int类型（甚至其他具体类型）的参数，实例化的时候直接int对应的填进去就行了。
（这个在STL的bitset中有使用，会介绍的。）

补充一句：
还记得第一讲提到的，C++里函数参数可以有默认值吗？
模板参数也是可以有默认值的，比如我可以声明：

template<class X,int MaxSize=10000>

这样允许你，如下的实例化：

LoopQueue<int> qint; // MaxSize会被当做10000
LoopQueue<int,15> q2; //MaxSize为15的一个，能存int类型数据的LoopQueue

Tips 4.02
如果用过STL提供的queue和stack的同学，会注意到，我这里的实现实际上是在模仿STL里提供的方法。为什么呢？
说来话长了……
一次比赛，队友写出了一题，然后超时，Claris怀疑是当时用了STL的stack的锅，然后选择让我手写一个数组模拟的，结果过了……
因为stack和queue他们是二次封装的容器，底层的容器（或者说，空间管理）是deque（之后STL部分会介绍），这个deque慢的人实在受不了……
虽说，的确，很少有情况会卡你使用STL的queue和stack，但是，就算出现了，手写一个也不应该有困难。

Exercise 4.02
1、既然我们提到了，我用泛型实现过一个stack（栈），那不妨试试？（说不好有天你就用了……）

2、（小米电话面试，远程共享代码窗口，真题）
使用C++语言实现一个双端队列（双端队列，一个允许从头部或尾部插入/删除的队列，也就是，支持4种修改元素操作）模板类Deque<T>，实现要求使用静态数组方式存储，在初始化时指定静态数组的大小（如果超过大小，不需要扩展大小，只需要提示错误即可），并实现以下方法（此处指给出函数名，请自己设计函数签名（函数参数和返回值））：
首尾添加元素：push_front(), push_back()
首尾删除元素：pop_front(), pop_back()
首尾获取元素：front(), back()
请注意，请尽量高效实现（所有操作的复杂度都应该为$O ( 1 )$）