12-1 泛型程序设计-模板

泛型（类属）程序设计模板主要内容泛型（类属）的基本概念函数模板类模板模板的复用问题问题在程序设计中，经常需要用到一些功能完全相同的程序实体，但它们所涉及的数据的类型不同。例如，对不同元素类型的数组进行排序的函数：voidint_sort(intx[],intnum);voiddouble_sort(doublex[],intnum);voidA_sort(Ax[],intnum);这三个函数的实现是一样的（如都采用快速排序算法由小到大排序），能否只用一个函数来实现？再例如，元素类型不同的栈类：这三个类的实现是一样的（用数组表示元素）。能否只用一个类来实现？classIntStack{ intbuf[100]; public: voidpush(int); voidpop(int&);};classDoubleStack{ doublebuf[100];public: voidpush(double); voidpop(double&);};classAStack{ Abuf[100];public: voidpush(A); voidpop(A&);};泛型（类属）一个程序实体能对多种类型的数据进行操作或描述的特性称为类属或泛型（Generics）。基于具有类属性的程序实体进行程序设计的技术称为：泛型程序设计（或类属程序设计，GenericProgramming）。具有类属性的程序实体通常有：类属函数：一个能对不同类型的数据完成相同操作的函数。类属类：一个成员类型可变、但操作不变的类。类属函数类属函数是指一个函数能对不同类型的参数完成相同的操作。C++提供了两种实现类属函数的机制：采用通用指针类型的参数（C语言的做法）函数模板例：用通用指针参数实现类属排序函数

函数定义：typedefunsignedcharbyte;voidsort(void*base,//需排序的数据（数组）内存首地址 unsignedintnum,//数据元素的个数 unsignedintelement_size,//一个数据元素所占内存大小（字节数）

bool(*cmp)(constvoid*,constvoid*))//比较两个元素的函数{//不论采用何种排序算法，一般都需要对数组进行以下操作：

//取第i个元素（通过数组首地址、偏移量i以及元素内存大小算出元素地址）

(byte*)base+i*element_size//比较第i个和第j个元素的大小（利用调用者提供的回调函数cmp实现）

if(!cmp((byte*)base+i*element_size,(byte*)base+j*element_size)){//交换第i个和第j个元素的位置（把两个元素逐个字节进行交换）

byte*p1=(byte*)base+i*element_size, *p2=(byte*)base+j*element_size;for(intk=0;k<element_size;k++){bytetemp=p1[k];p1[k]=p2[k];p2[k]=temp;}

}}函数的使用int型数组排序boolint_compare(constvoid*p1,constvoid*p2)//比较int类型元素大小。{ if(*(int*)p1<*(int*)p2) returntrue; else returnfalse;}......inta[100];......sort(a,100,sizeof(int),int_compare);double型数组排序booldouble_compare(constvoid*p1,constvoid*p2)//比较double类型元素大小。{ if(*(double*)p1<*(double*)p2) returntrue; else returnfalse;}......doubleb[200];......sort(b,200,sizeof(double),double_compare);A类型数组排序boolA_compare(constvoid*p1,constvoid*p2)//比较A类元素大小。{ if(*(A*)p1<*(A*)p2)//类A需重载操作符：< returntrue; else returnfalse;}Ac[300];

......sort(c,300,sizeof(A),A_compare);用通用指针实现类属函数面临的问题：比较麻烦，需要大量的指针操作。容易出错！编译程序无法进行类型检查。在C++中，实现类属函数的另外一种途径是用函数模板。函数模板是指带有类型参数的函数定义，格式如下：template<classT1,classT2,...>//class也可以写成typename<返回值类型><函数名>(<参数表>){ ......}T1、T2等是函数模板的参数，它们的取值是某个类型。函数的<返回值类型>

、<参数表>中的参数类型以及函数体中的局部变量的类型可以是：T1、T2等。函数模板例：用函数模板实现类属排序函数排序函数模板的定义：template<classT>voidsort(Telements[],unsignedintcount){

//取第i个元素

elements[i]

//比较第i个和第j个元素的大小

if(!(elements[i]<elements[j]))

{//交换第i个和第j个元素

Ttemp=elements[i]; elements[i]=elements[j]; elements[j]=temp;

}}排序函数模板的使用：inta[100];sort(a,100);//对int类型数组进行排序doubleb[200];sort(b,200);//对double类型数组进行排序Ac[300];sort(c,300);//对A类型数组进行排序//在类A中，需重载操作符：<

//可能还需要自定义拷贝构造函数和重载操作符=函数模板的实例化函数模板定义了一系列重载的函数。要使用函数模板所定义的函数，首先必须要对函数模板进行实例化：给模板参数提供一个具体的类型，从而生成具体的函数。函数模板的实例化通常是隐式的：由编译程序根据函数调用的实参类型自动地把函数模板实例化为具体的函数。这种确定函数模板实例的过程叫做模板实参推导（templateargumentdeduction）。inta[100];sort(a,100);实例化：voidsort(intelements[],unsignedintcount){......}doubleb[200];sort(b,200);实例化：voidsort(doubleelements[],unsignedintcount){......}Ac[300];sort(c,300);实例化：voidsort(Aelements[],unsignedintcount){......}带比较函数的排序模板template<classT1,classT2>voidsort(T1

elements[],unsignedintcount,T2cmp){ ......

//比较第i个和第j个元素的大小

if(!cmp(elements[i],elements[j]))

{交换元素次序}

......}inta[100];sort(a,100,[](int&x1,int&x2){returnx1<x2;});doubleb[200];sort(b,200,[](double&x1,double&x2){returnx1<x2;});Ac[300];sort(c,300,[](A&x1,A&x2){returnx1<x2;});有时，编译程序无法根据调用时的实参类型来确定所调用的模板实例函数。例如：template<classT>Tmax(Ta,Tb){returna>b?a:b;}......intx,y,z;doublel,m,n;z=max(x,y);//实例化和调用：intmax(int,int)l=max(m,n);//实例化和调用：doublemax(double,double)问题：max(x,m)

如何实例化？解决办法：显式类型转换max((double)x,m);

//调用：doublemax(doublea,doubleb)或max(x,(int)m);//调用：intmax(inta,intb)显式实例化 max<double>(x,m);或 max<int>(x,m);除了类型参数外，函数模板还可以带有非类型参数。例如，template<classT,intsize>//size为一个int型的普通参数voidf(Ta){ Ttemp[size];

......

}这样的函数模板在使用时需要显式实例化。例如，f<int,10>(1);//调用模板函数f(inta)，其中的size为10

带非类型参数的函数模板类模板如果一个类定义中用到的类型可变、但操作不变，则该类称为类属类。在C++中，类属类用类模板实现。类模板的格式为：template<classT1,classT2,...>//class也可以写成typenameclass<类名>{ <类成员说明>}T1、T2等为类模板的类型参数，在类成员的说明中可以用T1、T2等来作为它们的类型。

例如，用类模板实现类属的栈类：template<classT>classStack{ Tbuffer[100]; inttop; public: Stack(){top=-1;} voidpush(constT&x); voidpop(T&x);};template<classT>voidStack<T>::push(constT&x){......}template<classT>voidStack<T>::pop(T&x){......}类模板的实例化类模板定义了若干个类，在使用这些类之前需要对类模板进行实例化。类模板的实例化需要在程序中显式地指出。例如：Stack<int>st1;//实例化int型栈类并创建一个相应类的对象intx;st1.push(10);st1.pop(x);Stack<double>st2;//实例化double型栈类并创建一个相应类的对象doubley;st2.push(1.2);st2.pop(y);

Stack<A>st3;//实例化A类型栈类并创建一个相应类的对象Aa,b;st3.push(a);st3.pop(b);//A中可能要重载赋值操作符！为什么？注意：一个类模板的不同实例之间不共享该类模板中的静态成员。例如：template<classT>classA{ staticintx; Ty; ......};template<classT>intA<T>::x=0;......A<int>a1,a2;//a1和a2共享一个x。A<double>a3,a4;//a3和a4共享另一个x。

除了类型参数外，类模板也可以带非类型参数。例如： template<classT,intsize>classStack{ Tbuffer[size]; inttop; public: Stack(){top=-1;} voidpush(constT&x); voidpop(T&x);};template<classT,intsize>voidStack<T,size>::push(constT&x){......}template<classT,intsize>voidStack<T,size>::pop(T&x){......}......Stack<int,100>st1;//st1为元素个数最多为100的int型栈Stack<int,200>st2;//st2为元素个数最多为200的int型栈带非类型参数的类模板模板的复用模板也属于一种多态，称为参数化多态：一段带有类型参数的代码，给该参数提供不同的类型就能得到多个不同的代码，即，一段代码有多种解释。模板的复用是通过对模板进行实例化（用一个具体的类型去替代模板的类型参数）来实现的：由于实例化是在编译时刻进行的，它一定要见到相应的源代码，因此，模板属于源代码复用。一个模板可以有很多的实例，是否实例化模板的某个实例，这要由使用情况来决定。//file1.htemplate<classT>classS//类模板S的定义{Ta;public:voidf();};externvoidfunc();//file1.cpp#include"file1.h"template<classT>voidS<T>::f()//类模板S中f的实现{......}voidfunc(){S<float>x;//实例化“S<float>”并创建该类的一个对象xx.f();//实例化“voidS<float>::f()”并调用之}

//file2.cpp#include"file1.h"intmain(){S<float>s1;//实例化“S<float>”并创建该类的一个对象s1s1.f();//没有实例化“voidS<float>::f()”，但调用之S<int>s2;//实例化“S<int>”并创建该类的一个对象s2s2.f();//没有实例化“voidS<int>::f()”，但调用之func();return0;}

两个模块都能通过编译，但在连接时出错，连接程序指出：file2中调用的“voidS<int>::f()”不存在！解决上述问题的通常做法是把模板的定义和实现都放在头文件中。//file1.htemplate<classT>classS//类模板s的定义{Ta;public:voidf();};template<classT>voidS<T>::f()//类模板S中f的实现{......}externvoidfunc();使用者通过包含这个头文件，把模板的源代码全包含进来，以备实例化所需。//file1.cpp#include"file1.h"voidfunc(){S<float>x;//实例化“S<float>”并创建该类的一个对象x。x.f();//实例化“voidS<float>::f()”并调用之。}//file2.cpp#include"file1.h"intmain(){S<float>s1;//实例化“S<float>”并创建该类的一个对象s1。s1.f();//实例化“voidS<float>::f()”并调用之。S<int>s2;//实例化“S<int>”并创建该类的一个对象s2。

s2.f();//实例化“voidS<int>::f()”并调用之。

func();return0;}

因此，模板是基于源代码的复用！在由多模块构成的程序中，由于每个模块是单独编译的，因此，会导致一个模板的某个实例存在于多个模块的编译结果中：相同的函数模板实例相同的类模板成员函数实例相同代码的存在会造成目标代码庞大！重复实例的处理//file1.cpp#include"file1.h"voidfunc(){S<float>x;//实例化“S<float>”并创建该类的一个对象x。x.f();//实例化“voidS<float>::f()”并调用之。}//file2.cpp#include"file1.h"intmain(){S<float>s1;//实例化“S<float>”并创建该类的一个对象s1。s1.f();//实例化“voidS<float>::f()”并调用之。S<int>s2;//实例化“S<int>”并创建该类的一个对象s2。

s2.f();//实例化“voidS<int>::f()”并调用之。

func();return0;}

voidS<float>::f()在两个模块（file1.cpp和file2.cpp）的编译结果中都存在！如何处置这两个相同的实例？由开发环境来解决：编译第二个模块的时候不生成这个实例。（代价大！）由链接程序来解决：舍弃一个相同的实例。template<classT>//类模板A的定义classA{Tx,y;......friendvoidf(A<T>&a);//f是多个重载的函数， //它们与A的实例是一对一友元！};voidf(A<int>&a){......}

//该f仅是A<int>的友元，voidf(A<double>&a){......}

//该f仅是A<double>的友元......A<int>a1;

//实例化A<int>A<double>a2;//实例化A<double>A<char*>a3;//实例化A<char*>f(a1);//调用f(A<int>&)f(a2);//调用f(A<double>&)f(a3);//调用f(A<char*>&)，但连接时出错，该函数不存在！类模板的友元函数template<cla