第13章 模板
第三篇 泛型程序设计与模板库
第13章 模板
(本资料qq讨论群112133686)模板是C++语言的重要特征，使用能够显著提高编程效率。利用C++的函数模板和类模板，能够快速建立具有类型安全的类库集合和函数集合，进行大规模软件开发，同时提高软件的通用性和灵活性。C++的标准模板库（standard template library，简称STL）编程完全依赖模板的实现。本章举的实例都是泛型编程的实例，如怎样定义模板函数、类模板、泛型编程等。C++的标准模板库是把一些常用的数据结构比如链表、数组、二叉树等和算法比如排序、查找等写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，都不必重新实现数据结构，重新编写算法。
本章重点讲解了泛型编程举例及简单应用、类模板及容器实例、数据结构实例，这些对于初学者反复多实践，加深理解，举一反三。
13.1 为什么定义模板
所谓模板是一种使用无类型参数来产生一系列函数或类的机制。若一个程序的功能是对某种特定的数据类型进行处理，则可以将所处理的数据类型说明为参数，以便在其他数据类型的情况下使用，这就是为什么药定义模板的原因。
案例13-1 绕过形参限制
【案例描述】
本章开始演示泛型编程技术的实例，简单地说就是使用模板的程序设计实例。泛型程序设计（generic programming）的思想是基于模板机制以及标准模板库STL的实现技术。本实例从最简单模板说起，针对多个数据类型取最大数。本例效果如图13-1所示。
【实现过程】
声明函数模板T，定义函数体GetMax，功能求最大数，主函数中两次调用声明函数模板，输出结果。代码如下：
#include <iostream.h>
#include <iostream>
template <class T> //声明函数模板
T GetMax (T a, T b) { //定义函数体
T result;
result = (a>b)? a : b; //取最大数
return (result);
}
int main () {
int i=15, j=6, k;
double l=10.6, m=8.5, n;
k=GetMax(i,j); //调用函数模板
n=GetMax(l,m);
cout <<"输出最大整数："<< k << endl;//打印结果
cout <<"输出最大浮点数："<< n << endl;
system("pause");
return 0;
}
【案例分析】
（1）模板函数 GetMax()，类型T可以被用来声明新的对象，T result；result是一个T类型的对象， 就像a和b一样，也就是说，它们都是同一类型，这种类型就是当调用模板函数时写在尖括号<>中的类型。在这个具体的例子中，通用类型T 被用作函数GetMax()的参数，不需要说明<int>或< double>，编译器也可以自动检测到传入的数据类型代码。第一次调用函数模板实际上函数模板函数int abs(int x)，第二次为double abs(double x)。
（2）模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而避免需要为每一种数据类型产生一个单独的类或函数重复代码。
提示：模板并非通常意义上可直接使用的函数或类，仅仅是对一族函数或类的描述，是参数化的函数和类。模板是一种使用无类型参数来产生一族函数或类的机制。
案例13-2 定义一个实现计算的静态模板
【案例描述】
使用模板的目的就是能够让程序员编写与类型无关的代码。本实例定义一个静态模板类实现相加、相乘、判断功能。本例效果如图13-2所示。
图13-2 定义一个实现计算的静态模板
【实现过程】
建立一个静态模板类T，类中有相加、相乘、判断功能，主函数调用这些功能，并且输出结果。代码实现如下：
#include <iostream>
using namespace std;
template <class T>
class Operate{ //建立一个静态模板类
public:
static T Add(T a,T b){return a+b;} //相加
static T Mul(T a,T b){return a*b;} //相乘
static T Judge(T a,T b=1){
if(a>=0){ //判断
return a;
}
else{ a/b;
} } };
int main(){
int A,B,C,D,E,x,y,z; //定义整型变量
A=10,B=12,C=13,D=40,E=50; //初始化
x=Operate<int>::Add(A,B); //调用函数
y=Operate<int>::Mul(C,D);
z=Operate<int>::Judge(E,B);
cout<<"Add="<<x<<'\n'<<"Mul="<<y<<'\n'<<"Judge="<<z<<endl;
system("pause");
return 0;
}
【案例分析】
模板是C++语言最强大又是最少使用的特征之一。在C++语言中，模板让程序员能够定义一种使用不同类型对象的行为。表面上看有点像宏，但是宏不是类型安全的，而模板是类型安全的。模板声明以关键字template和一个参数列表组成，声明格式如下：
template<parename list>。
13.2 函数模板
案例13-3 求N*N的值
【案例描述】
数学运算中虽然给出了标准的算法，但是输入的数据类型不确定，要编写几个函数实现算法。这个时候就可以用到函数模板，本实例举个矩阵相乘的函数模板。效果如图13-3所示。
图13-3 求N*N的值
【实现过程】
程序定义两个矩阵模板函数multi()和output()，分别实现矩阵的乘法和输出矩阵的数据，主函数定义3个整数数组result、matrix1和matrix2，存储输出结果、输入矩阵、实现矩阵相乘和输出结果。其代码如下：
#include <iostream>
#include <iomanip>
using namespace std;
//矩阵模板函数
template <typename T1,typename T2>void multi(T1 *mat1,T2 *mat2,T2 *result,int a,int b,int c);
template <typename T>void output(T *mat,char*s,int a,int b);
int main(){
int result[6][4];
int matrix1[6][3]={7,11,12,23,2,3,5,7,9,1,4,6,34,45,56,2,3,6};
int matrix2[3][4]={2,3,1,0,-1,-2,5,3,7,6,5,4};
char *s1="result"; //定义字符串
multi(matrix1,matrix2,result,6,3,4); //调用矩阵相乘
//显式：multi <int[3],int[4]> (middle,matrix2,result,6,3,4);
output(matrix1,"matrix1",3,6);
output(matrix2,"matrix2",3,4);
output(result,s1,6,4);
system("pause");
return 0;
}
template <typename T1,typename T2>void multi(T1 *mat1,T2 *mat2,T2 *result,int a,int b,int c){
//二维数组的类型仅指其组成元素类型(一维数组),而与元素数量无关
//如matrix2和result是同一类型，其元素同为整型4元素一维数组，尽管前者只有3个元素，后者有6个
int i,j,k;
for (i=0;i<a;i++){
for (j=0;j<c;j++){ //矩阵的列
result[i][j] = 0;
for (k=0;k<b;k++) //矩阵的行
result[i][j]+=mat1[i][k]*mat2[k][j];
}
}
return;
}
template <typename T>void output(T *mat,char *s,int a,int b){
int i,j;
cout<<s<<endl;
for (i=0;i<a;i++){ //矩阵的行
for (j=0;j<b;j++) //矩阵的列
cout<<setw(6)<<mat[i][j];
cout<<endl;
}
return;
}
【案例分析】
（1）代码mat1[i][k]*mat2[k][j]，构成的矩阵称为矩阵A与B的乘积。
（2）multi(matrix1,matrix2,result,6,3,4);调用矩阵相乘，就是函数模板的显式实例化multi <int[3],int[4]> (middle,matrix2,result,6,3,4);。
案例13-4 万能计算器（支持各类数据的加法函数）
【案例描述】
假如设计一个求输入的两参数求加、减的函数，因涉及到几个数据类型可能需要定义几个函数，这几个函数几乎相同，唯一的区别就是形参类型不同，需要事先知道有哪些类型会使用这些函数，对于未知类型这些函数不起作用。本实例用一个模板就可以实现数学四则运行。效果如图13-4所示。
图13-4 万能计算器（支持各类数据的加法函数）
【实现过程】
声明函数模板T，定义函数体Add()、Substraction()和display()，功能求加法、减法和显示输入计算的数，主函数中两次调用声明函数模板，输出结果。代码如下：
#include <iostream>
using namespace std;
template <class T> //声明函数模板
T Add (T a, T b) { //定义函数体，加法
T result;
result = a+b;
return (result);
}
template <class T>
T Substraction (T a, T b) { //定义函数体，减法
T result;
result = a-b;
return (result);
}
template <class T>
void display (T a, T b) { //显示输入计算的数
T result;
cout << "a:" << a << endl;
cout << "b:" << b << endl;
}
int main(int argc, char* argv[])
{
int a=5, b=6;
display(5,6); //显示输入计算的数
cout << "a+b Add():" << Add(a,b) << endl; //调用函数模板
cout << "a-b Sub():" << Substraction(a,b)<<endl<<endl;
double l=30.23, m=40;
display(l,m);
cout << "a+b Add():" << Add(l,m) << endl; //调用函数模板
cout << "a-b Sub():" << Substraction(l,m) << endl;
system("pause");
return 0;
}
【案例分析】
（1）函数模板声明了类型T，表示一种抽象的类型。当编译器检测到程序中调用函数模板Add，便用Add的第一个实参的类型替换掉整个模板定义中的T，模板函数与重载是密切相关的，从函数模板产生的相关函数都是同名的，编译器用重载的解决方法调用相应的函数。另外函数模板本身也可以用多种方式重载。
（2）函数模板的实例化是在编译中，按系统处理函数调用时由系统自动完成。在调用函数模板时，系统首先确定模板参数所对应的具体类型，并依据该类型生成一个具体函数，系统实际上是调用了这个具有确定参数类型的函数。
提示：模板函数是函数模板的一个具体实例，是模板参数实例化后的一个可执行的具体函数，只处理一种确定的数据类型。
案例13-5 用户与管理员（判断若是布尔类型则使用特化例程）
【案例描述】
C++语言引入特化来解决某些类型在函数中的特殊操作。当编译器寻找到函数调用特化后，使用特化的定义，不再使用模板函数。本例效果如图13-5所示。
图13-5 用户与管理员（判断若是布尔类型则使用特化例程）
【实现过程】
定义函数模板Greater，进行特化声明template<> bool Greater(bool,bool);，主函数调用两次Greater，实现隐式实例化和优先调用特化函数。代码如下：
#include <iostream>
using namespace std;
template<class T>
T Greater(T x,T y);
template<> bool Greater(bool,bool); //特化声明
int main()
{
int intX=13,intY=20;
bool dblX=1,dblY=0;
cout<<"最小值"<<Greater(intX,intY)<<endl; //隐式实例化
cout<<"返回布尔值"<<Greater(dblX,dblY)<<endl; //优先调用特化函数
system("pause");
return 0;
}
template<class T>
T Greater(T x,T y)
{
return x<y?x:y;
}
template<> bool Greater(bool x,bool y) //特化定义
{
if(x||y) return 1;
else return 0;
}
【案例分析】
（1）模板特化是指对于某个特定的类型，需要对模板进行特殊化，即特殊的处理。例如，stack类模板针对bool类型有特化，因为实际上bool类型只需要一个二进制位，就可以对其进行存储，使用一个字或者一个字节都是浪费存储空间的。
（2）同样函数模板特化也是针对某个特定类型的特殊处理，特化基本格式：template<>返回类型 函数名[<函数实参标>] (函数参数表) { //函数定义}，类型实参表可以省略，由后续的函数表来制定。
提示：在使用特化函数时，须完成其定义在前面或后面定义均可，在在使用前要对其进行声明。
案例13-6 模板函数的重载例程
【案例描述】
函数模板支持重载，既可以在模板之间重载（同名模板），又可以实现模板和普通函数间的重载；单模板的重载相比普通函数的重载要复杂一些。本实例取最大数重载例程，效果如图13-6所示。
图13-6 模板函数的重载例程
【实现过程】
定义四个函数分别是：函数模板、重载函数模板、用普通函数重载函数模板。和用普通函数重载函数模板，在主函数中定义个整数、字符调用函数max()查看输出结果。代码如下：
#include<iostream>
using namespace std;
template<class T>
const T&max(const T&x,const T&y) //函数模板
{
return(x>y)?x:y;
}
template<class T>
const T&max(const T&a,const T&b,const T&c) //重载函数模板
{
return max(max(a,b),c);
}
const int&max(const int&x,const int&y) //用普通函数重载函数模板1
{
return (x>y)?x:y;
}
const char max(const int&x,char const&y) //用普通函数重载函数模板2
{
return (x>y)?x:y;
}
void main()
{
int i=50;
char c='A';
double f=100.05;
cout<<max(i,i)<<endl; //用普通函数重载函数模板1
cout<<max(c,c)<<endl; //函数模板
cout<<max(1.3,5.1,3.2)<<endl; //重载函数模板
cout<<max(i,c)<<endl; //用普通函数重载函数模板2
cout<<max(c,i)<<endl; //用普通函数重载函数模板2
cout<<max(f,f)<<endl; //函数模板
cout<<max(f,i)<<endl; //用普通函数重载函数模板2
cout<<max(i,f)<<endl; //用普通函数重载函数模板2
system("pause");
}
【案例分析】
（1）重载函数模板匹配约定：
1、寻找和使用最符合函数名和参数类型的函数，若找到则调用它。
2、否则，寻找一个函数模板，将其实例化产生一个匹配的模板函数，若找到则调用它。
3、否则，寻找可以通过类型转换进行参数匹配的重载函数，若找到则调用它。
4、如果按以上步骤均未找到匹配函数，则调用错误。
5、如果调用有多于一个的匹配选择，则调用匹配出现二义性。
（2）模板重载的应做到不引起“二义性”，是否会出现二义性不仅仅取决于定义的形式和传递的参数类型，还取决于编译器对函数执行顺序。
案例13-7 输出内存区域的各类型数据（void*）
【案例描述】
模板函数目的是一个函数实现对多个数据类型进行处理，体现出C++语言泛型编程技术的优越性能。函数参数传递，用引用做形参，引用(&)是标识符的别名，如输入int& a, int& b，进行函数处理会不会交换里面的值，本实例讨论这方面问题。本例效果如图13-7所示。
图13-7 输出内存区域的各类型数据（void*）
【实现过程】
声明函数模板T，模板函数分配内存，然后通过C++库函数memcpy()，交换输入的两个元素，然后释放内存。代码实现如下：
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <process.h>
#define GENERIC
template <typename T> //声明函数模板
//item_size为每个元素所占的字节数，item2和item1交换
int swap( T *item1,void* item2, size_t item_size)
{
void* item_temp = malloc(item_size);//分配内存
if(!item_temp)
return 0;
memcpy(item_temp, item1,item_size); //拷贝item_size个字节
memcpy(item1, item2,item_size);
memcpy(item2, item_temp,item_size);
free(item_temp);//释放内存
return 1;
}
void main()
{
int i=0,j=1;
swap(&i, &j, sizeof(int)); //调用交换模板
printf("i=%d j=%d\n",i,j); //打印交换后的值
double d1=1.0,d2=2.1;
swap(&d1, &d2, sizeof(double));
printf("d1=%.2f d2=%.2f\n",d1,d2);
char s[]="123456789"; //定义字符数组
char d[]="123";
swap(&s, &d, sizeof(char)); //调用交换模板
printf("s=%s d=%s\n",s,d); //打印交换后的值
system("pause");
}
【案例分析】
（1）void*也可称泛型指针，也就是可以指向任何类型的数据的指针，指向一段内存地址，当然可以指向一存储的字符串。
（2）上面代码swap()，输入参数是地址。memcpy()，从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。
13.3 类模板与模板类
案例13-8 模拟栈空间（数组+算法）
【案例描述】
栈（Stack）是按后进先出的规则进行的的线性表，仅限制在表的一端进行插入和删除运算。本例用数组模拟栈操作，其入栈和出栈操作在数组中进行，效果如图13-8所示。
图13-8 模拟栈空间（数组+算法）
【实现过程】
声明类模板IStack，栈内私有数组成员是一个数组，定义一个构造函数，构造函数中数组初始化为0，类外定义它的一个成员函数pop()出栈、push()入栈、display()显示栈内元素；主函数中提示输入进栈元素个数，提示输入进栈元素，出栈一个元素后，程序显示栈内元素。其代码如下：
#include<iostream>
using namespace std;
const int size=100; //数组大小
template <typename T> //定义类模板
class IStack{
public:
IStack();
T pop ();
int push (T);
int getcount();
int display();
private: T IArray [size]; //栈内元素存在数组中
int count;
};
template <typename T>
IStack<T>::IStack(){ //构造函数
for (int i = 0; i<size; i++)
{
IArray[i]=0;
}
count=0;
}
template <typename T> //成员函数pop，出栈
T IStack<T>::pop(){
T temp =IArray[count-1];
count--;
return
temp;
}
template <typename T> //成员函数push，入栈
int IStack<T>::push(T rhs)
{
IArray [count++]=rhs;
return 0;
}
template <typename T>
int IStack<T>::display() //成员函数display，显示栈内元素
{
for (int i =0; i<count; i++)
{
cout << IArray[i] <<" ";
}
return 0 ;
}
template <typename T>
int IStack<T>::getcount() //成员函数getcount
{
return count;
}
int main()
{
IStack<int> istack;
int i, n; //n表示进栈元素个数
int a[1005];
cout<<"输入进栈元素个数:"<<endl;
cin>>n;
cout<<"输入进栈元素:"<<endl;
for (i = 0;i < n;i ++)
{
cin>>a[i];
istack.push(a[i]);
}
istack.pop();
cout<<"出栈一个元素后，栈内元素为:"<<endl;
istack.display();
system("pause");
return 0;
}
【案例分析】
（1）代码IArray [size]为类模板的私有数组，栈内元素存在数组中，成员函数push()入栈，数组指针加1，并把一个数赋值给数组；pop()出栈的操作与入栈相反。主函数中IStack<int> istack;定义栈内操作为整数。
（2）类模板使得一个类可以有基于通用类型的成员，而不需要在类生成的时候定义具体的数据类型，例如，代码中template <typename T> class IStack{…}，在类之外定义它的一个成员函数，必须在每一个函数前面加template <... >，如代码中的pop()为出栈，push()为入栈。
提示：数组的数据类型也可以是类模板，实现具体类中的操作。
案例13-9 判断参数为字符串类型就输出字符串
【案例描述】
若有两个或多个类，其功能是相同的，仅仅是数据类型不同，如声明成几个类效率显然不高，这时就可以用类模板提高效率。本实例讨论类模板支持不同数据类型，如整数、浮点数和字符。本例效果如图13-9所示。
图13-9 判断参数为字符串类型就输出字符串
【实现过程】
声明一个类模板，利用它分别实现两个整数、浮点数和字符的比较，求出大数和小数。其代码如下：
#include <iostream>
using namespace std;
template <class T> //声明函数模板
T max (T x, T y) { //定义函数体，加法
{return (x>y)?x:y;}
}
template <class T> //声明函数模板
T min (T x, T y) { //定义函数体，加法
{return (x<y)?x:y;}
}
template <class T>
void display (T a, T b) { //显示输入计算的数
T result;
cout << "a:" << a << endl;
cout << "b:" << b << endl;
}
int main( )
{
int a=5, b=6; //定义整数，用于两个整数的比较
cout<<max(5,6 )<<" 为两个整数最大."<<endl;
cout<<min(5,6 )<<" 为两个整数最小."<<endl<<endl;
double l=30.23, m=40; //定义浮点数，用于两个浮点数的比较
cout<<max(l,m )<<" 为两个浮点数最大."<<endl;
cout<<min(l,m)<<" 为两个浮点数最小."<<endl<<endl;
char x='a',y='A'; //定义字符，用于两个字符的比较
cout<<max(x,y)<<" 为两个字符最大."<<endl;
cout<<min( x,y)<<"为两个字符最小."<<endl;
system("pause");
return 0;
}
【案例分析】
用类模板定义对象时用以下格式：类模板名<实际类型名>对象名;类模板名<实际类型名>对象名(实参表列);如Compare<int> cmp; Compare<int> cmp(3,7);，如果在类模板外定义成员函数，应写成类模板形式：template <class虚拟类型参数>函数类型 类模板名<虚拟类型参数>::成员函数名(函数形参表列) {…}。函数cmp(const void* a,const void* b)中，参数a和b是常量指针不能修改的。
提示：类模板的类型参数可以有一个或多个，每个类型前面都必须加class，如template <class T1,class T2> class someclass {…};。在定义对象时分别代入实际的类型名，如someclass<int,double> obj;。和使用类一样，使用类模板时要注意其作用域，只能在其有效作用域内用它定义对象。模板可以有层次，一个类模板可以作为基类，派生出派生模板类。
案例13-10 模拟压栈退栈
【案例描述】
栈是一种先进后出（FILO）的结构，在程序设计中广泛使用栈。栈的基本操作有：压栈push、出栈pop。其他操作有判空、判满、读栈顶元素等。将栈设计成一个类模板，在栈中存放任意类型的数据。本例效果如图13-10所示。
【实现过程】
定义了类模板Stack，Stack中有3个函数为出栈、入栈和获取栈顶元素值，私有成员变量最大深度、当前深度、内存指针，主函数压入栈元素1至10，显示出栈结果。代码实现如下：
#include <iostream>
using namespace std;
template<typename Type>
class Stack{public: Stack(int iLenth);
~Stack() //函数
{
delete[] m_p; //释放内存
}
Type Pop(); //出栈
void Push(Type newData); //入栈
Type GetData(); /获取栈顶元素值
private: int m_iMaxLenth; //最大深度
int m_iCurLenth; Type *m_p; //当前深度、内存指针
};
template<typename Type>Stack<Type>::Stack(int iLenth): m_iMaxLenth(iLenth), m_iCurLenth(0){ m_p = new Type[m_iMaxLenth];
if (NULL == m_p) //申请内存
throw(1)
;
}template<typename Type>Type Stack<Type>::Pop(){ if (NULL == m_p) throw(2); //出栈
if (0 == m_iCurLenth) throw(3);
Type k = m_p[--m_iCurLenth]; return k;
}
template<typename Type>void Stack<Type>::Push(const Type newData){ if (NULL == m_p) throw(2); //入栈
if (m_iCurLenth == m_iMaxLenth) throw(4);//如当前栈指针为最大
m_p[m_iCurLenth++] = newData; //插入新元素
}
template<typename Type>Type Stack<Type>::GetData()//获取栈顶元素值
{
if (NULL == m_p) //如为栈顶
throw(2);
if (0 == m_iLenth) //如为栈底
throw(3);
return m_p[m_iCurLenth-1];} //返回栈元素值
int main(void)
{
Stack<int> s(10);
cout<<"压栈元素为"<<endl;
for(int i=0; i<10; i++) {
s.Push(i); } //入栈
cout<<"退栈元素为"<<endl;
for(i=0; i<10; i++) { cout << s.Pop() << endl; }//出栈
system("pause");
return 0;
}
【案例分析】
（1）栈空间可以使用静态数组，本例中使用动态数组。使用指针top指向栈顶元素，使用成员函数push()、pop()、IsEmpty()、IsFull()分别进行压栈、出栈、判空、判满的操作。
（2）抛出异常（也称为抛弃异常）即检测是否产生异常，在C++语言中，采用throw语句来实现，如果检测到产生异常，则抛出异常。该语句的格式为：throw表达式;，在上述代码几次使用了throw。
提示：程序修改下，也可以定义个队列数据结构。
案例13-11 双向链表历遍
【案例描述】
本实例继续演示数据结构的算法。双向链表应用很广，如打开一个文本后读取文本的内容，可用链表的方式暂存读取到的文本内容。本实例演示怎样定义双向链表，并进行插入、删除等操作，通过类模板等技术实现。本例效果如图13-11所示。
【实现过程】
定义模板node、模板类Dlink，主程序定义3个Dlink类的La、Lb和Lc，给它们插入数据，删除节点数据和打印节点数据，输入节点长度。代码如下：
template<typename T>struct node{
T data;
node<T> *prior,*next;
};
template<typename T> class DLink{
private:
node<T> *head;
public:
DLink() //构造函数
{
head=new node<T>;
head->next=head->prior=head;
}
~DLink() //析构函数
{
clearLink();
delete head;
}
//代码略
int main()
{
DLink<int> La,Lb,Lc; //定义类
cout<<boolalpha<<La.empty()<<endl; //判断La是否为空
for(int i=1;i<4;i++)
La.Insert(i,i); //La插入结点
for(i=1;i<4;i++)
Lb.Insert(i,i+1); //Lb插入结点
int e;
for( i=1;i<5;i++)
{
La.getElem(i,e); //取双向链表La的节点
cout<<e<<" ";
}
cout<<endl;
while(!La.empty())
{
La.Delete(La.linkLength(),e); //删除一节点
La.print(); //打印节点
}
cout<<"链表La的长度是:"<<La.linkLength()<<endl;
cout<<"链表的Lb长度是:"<<Lb.linkLength()<<endl;
cout<<"链表的Lc长度是:"<<Lc.linkLength()<<endl;
return 0;
}
【案例分析】
（1）双向链表也叫双链表。每个节点有两个连接：一个指向前一个节点，而另一个指向下一个节点。双向链表中不仅有指向后一个节点的指针，而且还有指向前一个节点的指针。可实现从任何一个节点访问前一个节点，也可以访问后一个节点，以至整个链表。
（2）本实例涉及到模板node，模板类DLink和友元函数ostream &等，代码比较复杂。print()打印节点，利用while循环；node<T> *p遍历每一个节点并输出。
提示：对类和模板的内容可参阅第7章和第8章。
案例13-12 井字游戏（矩形数组）
【案例描述】
在C++游戏开发中可综合利用类和模板机制，这样就能体现面向对象编程语言的优点。本实例演示井字游戏，实现怎样用类定义棋盘，棋的移动，定义模板记录进行游戏的每一步。本例利用类和矩形数组实现井字游戏功能，效果如图13-12所示。
图13-12 井字游戏（矩形数组）
【实现过程】
定义棋盘类Board，移动类Move，MyStack定义栈存储下棋的过程。头文件定义代码如下：
class Board { //棋盘类
public:
Board( ); //棋盘初始化为空
bool done( ) const; //游戏结束或玩家已赢或棋盘下满，返回true
void print( ) const; //显示棋盘
void instructions( ) const; //这是井字游戏，等待计算机继续
bool better(int value, int old_value) const;
bool ValidStep(Move try_it) const;
void play(Move try_it); //游戏成员函数
int worst_case( ) const;
int evaluate( ) const;
int legal_moves(MyStack<Move> &moves) const;
int the_winner( ) const;
private:
int squares[3][3]; //存储行、列值
int moves_done; //下的步数
};
class Move { //移动类
public:
Move( ); //初始化为不合法，设置默认值
Move(int r, int c); //初始化为给定坐标
int row; //行
int col; //列
};
enum Error_code{underflow, overflow, success};
const int maxstack = 10; //用于测试小的值
template<class Stack_entry>
class MyStack { //栈存储下的过程
public:
MyStack();
bool empty() const; //是否是空
Error_code pop(); //出栈
Error_code top(Stack_entry &item) const;
Error_code push(const Stack_entry &item); //进栈
private:
int count;
Stack_entry entry[maxstack];
};
【案例分析】
（1）井字游戏类似五子棋，是一种在3*3格子上进行的连珠游戏。由于棋盘一般不画边框，格线排成井字而得名。游戏需要的工具仅为纸和笔，然后由分别代表O和X的两个游戏者轮流在格子里留下标记（一般来说先手者为X）。棋盘一共有9个格子为3乘3排列，棋子只能下在格子里。
（2）定义类Stack_entry，函数有push()、pop()、top()、empty()，用来栈存储下棋的过程。
提示：以数组作为函数参数，通过指针进行通信，是调用函数向被调用函数传递大量数据的一种方法。
案例13-13 贪食蛇
【案例描述】
跟上述13-12实例一样游戏开发要综合利用类和模板的技术，发挥面向对象技术的优点。本实例为贪食蛇游戏，这是一款比较老的游戏很简单，主要是怎样用类定义围墙，实现蛇的移动功能。本例效果如图13-13所示。
图13-13 贪食蛇
【实现过程】
（1）定义围墙类Fence 画出围墙；蛇结点类SnakeNode，实现蛇的各种动作；移动类move。头文件定义代码如下：
class Fence{ //围墙
public:
void InitFence(); //画框框
void OutputF(); //显示框框
public:
char game[20][20]; //存储游戏坐标点
}f; //定义对象;
void Fence::InitFence(){ //画框框
for(int i=0; i<20; i++) //for循环
for(int j=0; j<20; j++){
if(i==0||i==19||j==0||j==19) //显示框框
game[i][j]= '*';
else game[i][j]= ' ';
}
}
void Fence::OutputF(){ //显示框框
for(int i=0; i<20; i++){ //for循环
for(int j=0; j<20; j++)
cout<<game[i][j]<<' ';
cout<<endl;
}
}
（2）定义移动类m画框框和小蛇，while循环进行各种操作。代码如下：
int main(){
cout<<"Using 'w,s,a,d'to control direction!!!\n\n\n";
move m; //画框框和小蛇;
f.InitFence(); //画框框
head->add_head(4,3); //插入头结点
head->add_head(4,4);
head->add_head(4,5);
m.get_food(); //取得食物
f.OutputF(); //显示框框
while (true){
char keydown= getch(); //getch()返回键盘上读取的字符，包含头文件<conio.h>
m.change_point(keydown); //改变方向
while(!kbhit()){ //判断有没有按键按下
system("cls"); //清屏函数
m.moving();
f.OutputF(); //显示框框
Sleep(200);
}
}
return 0;
}
【案例分析】
（1）贪吃蛇又称贪食蛇，是一款经典的小游戏。玩此游戏的人使用方向键操控一条长长的蛇不断吞下豆子，同时蛇身随着吞下的豆子不断变长，一旦蛇头撞到蛇身或碰到壁时游戏结束。
（2）程序定义三个类Fence、SnakeNode、move来封装游戏功能。
13.4 模板的嵌套
案例13-14 求AB对象成员的和（类模板成员数组）
【案例描述】
模板的嵌套可以理解在另外一个模板中定义个模板，以模板（类或者函数）作为另一个模板（类或者函数）的成员，也称成员模板。本实例为嵌套类定义模板，本例效果如图13-14所示。
图13-14 求AB对象成员的和（类模板成员数组）
【实现过程】
定义类Number1，类中嵌套类定义模板Number2，在主函数声明Number2类对象obin，显示类，创建Number1类对象obout。代码实现如下：
#include <iostream>
using namespace std;
template<class T>
class Number1 //外部Num8ber1类定义
{
public:
template<class R>
class Number2 //嵌套类模板定义
{
private:
R r;
public:
Number2(R x) //模板类的成员函数可以在定义时实现
{
r=x;
}
void disp();
};
Number1(T x):t(x)
{
}
void disp();
private:
Number2<T> t;
};
template<class T>
template<class R>
void Number1<T>::Number2<R>::disp() //模板类的成员函数也可以在定义外实现
{
cout<<"Number2: "<<Number1<T>::Number2<R>::r<<endl;
}
template<class T>
void Number1<T>::disp()
{
cout<<"Number1:";
t.disp();
}
int main()
{
Number1<int>::Number2<double> obin(13.5);//声明Number2类对象obin
obin.disp();;
Number1<int> obout(2); //创建Number1类对象obout
obout.disp();
return 0;
}
【案例分析】
类模板不等于类定义，因此需要实例化或特化来生成类实例。代码Number2类模板的访问权限为public，因此可以调用Number1<int>:: Number2<double> obin(3.5);。在Number1类内使用Number1<T>t，语句声明了Number1<T>类对象，在Number1模板类对象创建时，首先采用隐式化生成Number1<T>类的定义，其次在根据此定义创建对象成员t。
提示：类模板的定义可以放在另一个类中，实例化后的模板类对象可以作为另一个类的成员。
13.5 模板的嵌套
案例13-15 变幻的对象——使用template定义一个类模板
【案例描述】
类模板相对于类是属于更高层次的抽象，因为类是一组对象的公共性质的抽象，而类模板则是对不同类的公共性质的抽象。因此利用C++语言的函数模板和类模板，能够快速建立具有类型安全的类库集合和函数集合，提高大规模软件开发效率，达到软件的通用性和灵活性目的。本例定义了一个模板类，实现查找字母和数字功能，效果如图13-15所示。
图13-15 变幻的对象——使用template定义一个类模板
【实现过程】
定义了一个模板类Search，成员函数Search()实现赋值数组元素，成员函数seek()利用递归机制用二分查找法查找字母，主函数类模板s，调用seek查找字母。代码实现如下：
#include<iostream.h>
#include<iostream>
const int max=100; //最大数组
template <class T>
class Search
{
T A[max]; //最大数组
int n; //查找元素个数
public:
Search(){}
Search(T a[],int i);
int seek(T b[],int l,int h,T x);
void disp() //显示输入字符串
{
for (int i=0;i<n;i++)
cout<<A[i]<<" "; //显示字符
cout<<endl;
}
};
template <class T>
Search<T>::Search(T a[],int i) //类模板
{
n=i;
for(int j=0;j<i;j++)
A[j]=a[j]; //赋值数组元素
}
template <class T>
int Search<T>::seek(T b[],int l,int h,T x)//查找字母
{
int m;
if(l>h) //b[]:字符数组l:开始位置，h:结束位置，x：查找字母
{
cout<<endl<<"没有查找到!"<<endl;
return -1;
}
else
{
m=(l+h)/2; //二分查找
if(x<b[m])
return (seek(b,l,m-1,x));//递归算法
else if(x==b[m]) //查找到
return m; //返回查找到的字母
else
return (seek(b,m+1,h,x));//递归算法
}
}
void main()
{
char a[]="wxzacegkmp",d; //定义字符数组
Search<char> s(a,10); //定义类模板s
cout<<"输入的字符串数组:";
s.disp(); //显示输入字符串
cout<<"需要查找的字母:";
cin>>d; //取得需要查找的字母
cout<< "\'"<<d<< "\'"<<"位置为："<< "是:";
cout<<s.seek(a,0,9,d)+1<<endl; //显示查找字母的位置
system("pause");
}
【案例分析】
模板类的成员函数也可以在类外定义，其语法如下：template <模板参数表>类型 类名 <模板参数名表>∷函数名(参数表){ 函数体;}，其中模板参数表与类模板的模板参数表相同。模板参数名表列出的是模板参数表中的参数名，顺序与模板参数表中是一致的。
提示：定义了一个模板类，为了增强类的适用性，将模板类设计成参数化类型，它可以实例化成字符串、整型等。
13.6 模板的嵌套
案例13-16 输出浮点型数据和整型数据（隐式实例化）（显式实例化）
【案例描述】
隐式实例化指函数模板，实际上不是个完整函数定义。因为其中的一些参数还不确定，只是定义了某些类型的角色（或变量）在函数中的操作形式，必须将模板参数化后才能使用函数，也成为模板函数。在C++标准允许显示实例化，用命令编译器创建满足条件的模板函数，用以解决因重载等引入的二义性问题。本例效果如图13-16所示。
图13-16 输出浮点型数据和整型数据（隐式实例化）（显式实例化）
【实现过程】
定义显式实例化Greater1()函数模板、隐式实例化Greater1函数模板，主函数定义两个整数，两个双精型并调用显式实例化、隐式实例化函数。代码如下：
#include <iostream>
using namespace std;
template<class T>
T Greater(T &a, T &b );
template<class T1>
T1 Greater1( T1 &a, T1 &b );
template int Greater1<int> (int,int); //显式实例化Greater1函数模板
template<class T>
T Greater(T &a, T &b )
{
T temp;
temp = a; //输入的两个数交换
a = b;
b = temp;
return a/b; //返回相除的值
};
template<class T1>
T1 Greater1( T1 &a, T1 &b ) //隐式实例化Greater1函数模板
{
T1 temp;
temp = a; //输入的两个数交换
a = b;
b = temp;
return a/b; //返回相除的值
};
int main()
{
int intX=1,intY=2;
double dblX=3.0,dblY=2.9;
cout<<"隐式实例化:"<<endl;
cout<<Greater(intX,intY)<<endl; //实参为int型，生成int型模板函数，并对第二个参数进行检查
cout<<Greater(dblX,dblY)<<endl<<endl; //实参为double型，生成double型模板函数，并对第二个参数进行检查
intX=1,intY=2;
dblX=3.0,dblY=2.9;
cout<<"显式实例化:"<<endl;
cout<<Greater1(intX,intY)<<endl; //调用实例化的Greater1(int,int)
cout<<Greater1(dblX,dblY)<<endl; //实参为double型，生成double型模板函数，并对第二个参数进行检查
return 0;
}
【案例分析】
（1）隐式实例化指的是：在使用模板之前编译器不生成模板的声明和定义实例，只有当使用模板时编译器才根据模板定义生成相应类型的实例。如代码：int i=0, j=1;swap(i, j);，编译器根据参数i，j的类型隐式地生成swap<int>(int &a, int &b)函数的定义。Array<int> arVal;，编译器根据类型参数隐式地生成Array<int>类的声明和类函数的定义。
（2）显式实例化：当显式实例化模板时，在使用模板之前编译器根据显式实例化指定的类型生成模板实例。如显示实例化（explicit instantiation）模板函数和模板类。其格式为：template typename function<typename>(argulist);template class classname<typename>;。
提示：显式实例化只需声明，不需要重新定义，编译器会根据模板实现实例声明和实例定义。
案例13-17 补充代码使输出结果成立
【案例描述】
一般来说实例化函数的执行顺序和模板的特化函数相比，模板的特化函数要优先于实例化函数。本例演示这几个同名函数执行顺序，效果如图13-17所示。
图13-17 补充代码使输出结果成立
【实现过程】
程序分3个函数，分别是实例化函数、模板的特化函数和一般函数，定义整数、浮点数和字符串调用函数名Max，演示查看调用具体的函数。代码如下：
#include <iostream>
using namespace std;
template<class T>
T Max(T x,T y);
template<> double Max(double,double); //特化声明
int main()
{
int X=210,Y=102;
double lX=16.8,lY=11.8;
cout<<Max(X,Y)<<endl; //实例化
cout<<Max(lX,lY)<<endl; //优先调用特化函数
cout<<Max("C++","HELLO")<<endl;
system("pause");
return 0;
}
template<class T>
T Max(T x,T y)
{
return x>y?x:y;
}
template<> double Max(double x,double y) //特化定义
{
return x-y;
}
char* Max(char* x,char* y) //一般函数
{
cout<<"一般函数被执行"<<endl;
return(strcmp(x,y)>0)?x:y; //比较两个字符串的大小
}
【案例分析】
代码中前两个结果是正确的，但字符串的比较出了问题。原来在调用Max ("world","hello")时，编译器将类型参数Ex实例化为char*，由此模板形成的函数char*Max (char* x,char* y) { return x>y?x:y;} 的比较结果实际上是x和y两个字符串的地址大小，而不是字符串内容的比较。
提示：重载解析用于最匹配的函数。如果有多个可选函数，首先是普通函数，其次是模板函数；如果都是模板函数，则选择最特化的那个。如果有多个函数，并且编译器不能决定选择那个，就会出现二义性错误，如果无函数可选也是错误的。
案例13-18 求AB对象的和（类参数）
【案例描述】
模板包含类型参数和非类型参数，实际上，模板的参数可以是另一个模板，也就是说，如本实例所举定义类，类里面定义个模板，这种形式是合法的。本例效果如图13-18所示。
【实现过程】
定义类Stack，类里面定义个模板T1，在主函数main()中进行函数模板的隐式实例化，并调用。其代码如下：
#include <iostream>
using namespace std;
template <class T,int num> //类型参数表
class Stack //Stack类定义
{
private:
T sz[num]; //存储空间，用数组表示
public:
int ReturnNum(); //判断栈是否为空
};
template<class T1,int num1> //参数列表不要求字字相同，但形式要相同
int Stack<T1,num1>::ReturnNum()
{
return num1; //返回数组大小
}
template<template<class Type,int NUM> class TypeClass,class T1,int N>
void disp() //函数模板，其类型参数表中包含一个类模板
{
TypeClass<T1,N> ob; //类模板的隐式实例化,创建对象ob
cout<<ob.ReturnNum()<<endl; //调用ob的public成员函数
}
int main()
{
disp<Stack,int,8>(); //函数模板的隐式实例化，并调用
return 0;
}
【案例分析】
（1）代码定义了函数模板disp，该模板的类型参数表中又包含了一个类模板T1。在函数模板内可以对类隐式实例化并调用。
（2）模板的参数可以是另一个模板，如代码template<template<class Type,int NUM> class TypeClass,class T1,int N>，将原来简单的“class TypeClass”或“class T1”扩充为“template<class Type,int NUM> class TypeClass”。
案例13-19 显式调用析构函数实例
【案例描述】
通常是不需要显式的调用析构函数的。显式的调用析构函数是一件非常危险的事情，因为如果系统调用析构函数，无论是否已经调用过，仍然会再次调用。换句话说所谓的显式调用析构函数，实际上只是调用了一个成员函数，并没有真正意义上的让对象“析构”。本例效果如图13-19所示。
图13-19 显式调用析构函数实例
【实现过程】
程序定义类cellphone，数据成员brand是字符型指针，brand=new char[]为指针初始化，分配动态内存，程序调用析构函数控制对象撤销。代码如下：
#include <iostream>
#include <cstring>
using namespace std;
class cellphone
{
private:
char *brand; //品牌，指针成员
float price; //价格
public:
cellphone(const char* sz,float p)
{
brand=new char[strlen(sz)+1]; //对象创建时为brand分配一块动态内存
strcpy(brand,sz); //字符串复制
price=p; //价格
}
~cellphone() //析构函数
{
delete[] brand; //对象被撤销时，释放内存避免泄露
cout<<"清理现场"<<endl;
}
void print() //信息输出
{
cout<<"品牌："<<brand<<endl;
cout<<"价格："<<price<<endl;
}
};
int main()
{
cellphone cell("Apple",3900); //调用构造函数声明cellphone变量cell
cell.print(); //信息输出
cell.~cellphone();
system("pause");
return 0;
}
【案例分析】
堆区（heap）一般由程序员分配释放， 若程序员不释放，程序结束时可能由操作系统回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。栈区（stack）由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
系统在什么情况下不会自动调用析构函数呢？显然如果对象被建立在堆上，系统就不会自动调用。一个常见的例子是new...delete组合。但是好在调用delete的时候，析构函数还是被自动调用了。例外的是使用布局new的时候，在delete设置的缓存之前，需要显式调用的析构函数；但这实在是很少见的情况。
提示：一般不要去调用析构函数，或者要是不嫌麻烦的话，析构之前最好先看看堆上的数据是不是已经被释放过了。
案例13-20 隐式转换错误实例
【案例描述】
同名函数，输出整数都没有问题；但是输出带有小数点的数的时候，就需要进行类型转换，否则编译器就报错。数字本身是没有类型如output(0.5);，计算机自动转换为double型；但如提供了一个转换成float的函数，计算机就不知道转换成什么类型了。所以要强制转换才行。本例效果如图13-20所示。
图13-20 隐式转换错误实例
【实现过程】
定义函数output()，输入分别为整数和浮点数，测试输出结果，主函数定义个整数和浮点数，调用output，测试输出结果。代码实现如下：
#include <iostream>
using namespace std;
void output( int x); //函数声明
void output( float x); //函数声明
void output( int x) //输出整数
{
cout << " output int " << x << endl ;
}
void output( float x) //输出浮点数
{
cout << " output float " << x << endl ;
}
void main(void)
{
int x = 8;
float y = 8.0;
output(x); //输出整数 8
output(y); //输出浮点数 8
output(1); //输出整数 1
// output(8.5); //error! ambiguous call, 因为自动类型转换
output(int(8.5)); //输出整数 8
output(float(8.5)); //输出浮点数8.5
system("pause");
}
【案例分析】
（1）output( x ); output( y );，这两个输入的参数都是一个变量，变量是有存储区域的，并标识了存放的数据的类型，所以它能正确匹配重载函数。
（2）代码output(8);，首先将8转换成一个temp，当没有小数点时，默认temp为整型，再将temp传给函数，即output( temp )；output(8.5 );，编译器识别8.5时，会将8.5转换成double型的temp，但发现没有一个匹配的函数，于是又将temp转换成另一个temp，这时有int与float都可以转换，编译器就不知道要转换成哪一个了。
（3）output( int(8.5) );这个作了强制类型转换，自然可以正确匹配了。
13.8 本章练习