引言

从万能的《C++ Primer Plus》 里引用这样一段话:

在C++发展的早期,大多数人都没有想到模板函数和模板类会有这么强大而有用,他们甚至没有就这个主题发挥想象力。但聪明而专注的程序员挑战模板技术的极限,阐述了各种可能性。根据熟悉模板的程序员提供的反馈,C++98标准做了相应的修改,并添加了相应的标准模板库。从此以后,模板程序员在不断探索各种可能性,并消除模板的局限性。

“template”的曲折历史和程序员们的”laziness”可见一斑(笑)。譬如,我们在做算法题的时候,使用标准模板库中的容器类可以极大地减少代码量,提高做题效率。

在这个专题中,我打算用几篇的内容,对模板的定义与使用,算法竞赛常用的STL,以及C++11的一些新特性进行简要的讲解(或许只能算作介绍)。希望能对即将到来的蓝桥杯省赛和ACM校赛有些许帮助。


函数模板

使用函数模板的原因

之前我们讲了函数重载。使用函数重载,可以减少函数名称的冗余。但是我们仍要对各重载函数一一进行实现,尽管这几个函数都基本一样:

1
2
3
4
5
6
7
8
9
10
11
void Swap(int & a,int & b){
a=a+b;
b=a-b;
a=a-b;
}
void Swap(float & a,float & b){
a=a+b;
b=a-b;
a=a-b;
}
//double,char等同理

显然函数重载仍然存在有冗余!那么我们可不可以把这几个函数都写在一起,只用写一遍即可?这时我们就要用到函数模板!

函数模板的声明和定义

《C++ Primer Plus》 上对函数模板的说明为:

使用泛型来定义函数。当泛型用具体的类型替换,即将类型作为参数传入函数模板后,编译器就会自动生成相应的函数。

这里泛型的意思就是不是特指某一种类型,而可以是多种类型。

定义函数模板

我们先尝试使用函数模板来解决上面函数重载冗余的问题:

1
2
3
4
5
6
template <typename T>
void Swap(T & a,T & b){
a=a+b;
b=a-b;
a=a-b;
}
这就是定义一个函数模板的形式。

template <typename T>告诉编译器这是一个函数模板,称为模板头 ;其中的typename可以用class替换,但class可能与类在理解上产生歧义,所以更建议用typenameT则是自定义的类型名,和变量的命名方式相同,但T是一个比较常用的命名,我们遵循这个习惯就好啦。

使用函数模板

我们定义的模板只是一个程式,并不是函数。所以使用函数模板的时候还要有相应的函数才行!即进行实例化

隐式实例化

当我们向函数模板传入类型作为参数 时,编译器就会自动生成一个相应类型的函数。示例程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
template <typename T>
void Swap(T & a,T & b){
a=a+b;
b=a-b;
a=a-b;
}
int main(){
int a=1,b=2;
char c='A',d='B';
std::cout<<a<<b<<' '<<c<<d<<'\n';
Swap(a,b);Swap(c,d);
std::cout<<a<<b<<' '<<c<<d;
return 0;
}

正确输出:

1
2
12 AB
21 BA

此处编译器隐式地为我们生成了两个相应的函数。这里编译器做了两件事,一是匹配参数类型[1]二是生成相应函数[2] 。当然,我们也可以自己显示地从模板生成函数实例👇

显示实例化

使用时在函数模板名后添加类型:

1
Swap<int>(a,b);

这样就不用编译器来帮我们推断参数类型了,相当于我们自己完成了上面的[1]

1
template Swap<int>(int&,int&);

通过这种方式就在函数外创建了一个传入参数为int的函数模板的实例,然后使用时直接Swap(a,b)即可。这就相当于我们自己完成了上面的[2]

当然上面两个都可以用上,那就没编译器啥事了(bushi

函数模板的声明

和一般的函数一样,我们也可以把函数模板的声明放在前面,函数模板的实现放在程序的后面;或函数模板声明放在.h头文件中,实现放在cpp文件中

如,上面的程序我们可以这样写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
template <typename T>
void Swap(T&,T&);
int main(){
int a=1,b=2;
char c='A',d='B';
std::cout<<a<<b<<' '<<c<<d<<'\n';
Swap(a,b);Swap(c,d);
std::cout<<a<<b<<' '<<c<<d;
return 0;
}
template <typename T>
void Swap(T & a,T & b){
a=a+b;
b=a-b;
a=a-b;
}

其中,函数模板声明的形式如下:

1
2
template <typename T>
void Swap(T&,T&);

函数模板的具体化

我们先来分析一下函数模板的缺陷:

比如写一个比大小的函数模板。如果传入的类型为int,那一般是没问题的;如果传入的类型为vector<int>,那就是比较的数组的长短。但如果我们实际想要比较的是数组第一个元素的大小呢?这样就会产生和我们的预期不一样的结果。

总结一下,函数模板的问题就是因使用情况而异,对某些类型的处理可能不通用。 我们的想法就是单独为这种类型写一个模板作为该函数模板的特例,这就是函数模板的具体化

如下面的程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
template<class T>
short judge(T a,T b){
if(a>b) return 1;
else if(a<b) return -1;
else return 0;
}
int main(){
vector<int> a={1,2},b={1};
cout<<judge(a,b);
return 0;
}

它比较的是两个整型数组的长短。如果想要比较整型第一个元素的大小同时不影响其他类型的比较,我们就要为vector<int>提供函数模板的具体化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
template<class T>
short judge(T a,T b){
if(a>b) return 1;
else if(a<b) return -1;
else return 0;
}
template<>
short judge(vector<int> a,vector<int> b){
if(a[0]>b[0]) return 1;
else if(a[0]<b[0]) return -1;
else return 0;
}
int main(){
vector<int> a={1},b={1,2};
cout<<judge(a,b);
return 0;
}

这样遇到vector<int>类型,就会优先执行具体化的函数模板。即优先级:具体化的函数模板>一般的函数模板

函数模板还支持重载,但前提是不能有歧义 。重载的方式和一般的函数相同,所以不展开叙述。

类模板

因为类可以对数据结构进行封装,而数据结构是对数据的组织方式,与数据类型关系不大,所以在类中引入泛型则是很有意义的。可以说,类模板更能体现出模板的强大之处。

模板类的定义

请先观察下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T>
class ListNode{
private:
T data;
ListNode* next;
public:
ListNode();//构造函数
//对链表节点的操作
}
//构造函数的实现,注意写法!
template <typename T>
ListNode<T>::ListNode(){}
//其他函数的实现同理

和函数模板一样,模板头都是template <typename T>,同时在类中用T来表示泛型。值得注意的是(上面的代码以构造函数为例),成员函数如果要在类外实现的话,作用域 需要这样写:

1
2
template <typename T>
ListNode<T>::ListNode(){}

即先加上模板头表示是模板类中的成员函数;再再类名后加上<T>表示类名(可以理解为类名)。

模板类的使用

和函数模板一样,类模板在使用前也要先实例化

注意类模板的实例化和类的实例化的区别:类模板实例化得到类;类实例化得到对象

隐式实例化

我们一般都使用隐式实例化
1
ListNode<int> listNodei;

我们传入类型参数给类模板,编译器就会自动生成对应类型的类。

显示实例化

我们也可以事先”手动”将模板类实例化为类:

1
2
3
4
//将模板类实例化为类
template class ListNode<int>;
//使用实例化后的类生成对象
ListNode<int> listNodei;

多类型参数和非类型参数

多类型参数

如果一个模板类需要自定义多个参数类型,那么就可以使用多类型参数,即一次性传入多个参数 ,如:

1
2
3
4
5
template <typename T,U>
class Map{
T key;
U value;
}

非模板参数

如果类中有一个数组,我们还需要自定义数组的大小,那么就可以在传入类型参数时也传入非类型参数:

1
2
3
4
template <typename T,int n>
class String{
char str[n];
}

实际上,也可以使用构造函数实现数组大小的初始化,两种方式各有优劣:

  1. 使用构造函数的速度比使用非模板参数要慢一些。因为构造函数用到的是堆空间,而非模板参数遇到的是栈空间。
  2. 但使用非模板参数时,即使T是相同的,如果n不同,那么编译器就会隐式生成不同的类;而构造函数n不同,类依然只有一个。

函数模板和类模板的简要介绍就是这些。

你已经学会了模板的基本语法,来写一个STL吧!(x)

你已经学会了基本的与或非门,来做一台电脑吧!😁(√)

揩烷哮的,要自己写STL,还需要了解迭代器,分配器等知识。这又是另一个故事……(to be continued)