10. 模板和泛型编程

面向对象程序设计与C++第十章模板与泛型编程教师：王涛电话:51688243办公室:九教北525E-mail:[e-mail]1.普通函数的缺陷•求两个数最大值的函数,可以重载多个函数：intmax(inta,intb){return(ab)?a:b;}charmax(characharb){return(ab)?a:b;}floatmax(floata,floatb){return(ab)?a:b;}doublemax(doublea,doubleb){return(ab)?a:b;}以上函数的实现方式完全一样，是否可以用一个通用函数完成？普通类的缺陷•分别有整数链表及浮点数链表：structinode{structfnode{intval;floatval;inode*next;};fnode*next;};classilist{classflist{inode*head;fnode*head;public:public:ilist();flist();~ilist();~flist();voidclear();voidclear();voidinsert(int);voidinsert(float);voidappend(int);voidappend(float);boolremove(int);boolremove(float);boolcontains(int);boolcontains(float);intlength();intlength();};};•对于一些结构及操作相同,只是成员数据类型不同的抽象数据结构,若是用普通类class进行封装,需要将不同的数据类型封装成不同的类,造成代码重复及使用不便.•解决的方法之一：利用class封装较为通用的数据类型,使用的时候再进行数据类型转换.•解决的方法之二：使用模板普通类的缺陷2.模板•对于结构和操作相同,但成员数据类型不同的抽象类型，可以通过模板实现。•模板有两种形式：–模板函数(函数模板)–模板类(类模板)•模板声明格式为：template模板参数表函数模板•对于功能和操作基本相同,只是参数或返回值类型不同的若干函数，可以通过函数模板实现.intmax(intx,inty){//求两个整数的最大值return(xy)?x:y;}floatmax(floatx,floaty){//求两个浮点数的最大值return(xy)?x:y;}charmax(charx,chary){//求两个字符的最大值return(xy)?x:y;}templateclassTTmax(Tx,Ty){return(xy)?x:y;}voidmain(){intx1=10,y1=8;floatx2=20.3,y2=33.5;charx3=‘k’,y3=‘n’;cout“max(x1,y1)=“max(x1,y1)endl;cout“max(x2,y2)=“max(x2,y2)endl;cout“max(x3,y3)=“max(x3,y3)endl;}模板函数输出:max(x1,y1)=10max(x2,y2)=33.5max(x3,y3)=n•采用模板参数的各参数之间必须保持完全一致的类型.templateclassTTmax(Tx,Ty){return(xy)?x:y;}voidmain(){inti;charc;floatf;max(i,i);//ok.max(c,c);//ok.max(f,f);//ok.max(i,c);//error:templateparameter'T'isambiguousmax(i,f);//error:templateparameter'T'isambiguousmax(c,f);//error:templateparameter'T'isambiguous}模板函数•可以重载于与之同名的非模板函数.templateclassTTmax(Tx,Ty){return(xy)?x:y;}//模板函数char*max(char*x,char*y){//非模板函数return(strcmp(x,y)=0)?x:y;}voidmain(){charch1[6]=“abc”;charch2[6]=“def”;cout“max(ch1,ch2)=“max(ch1,ch2)endl;}重载模板函数输出：max(ch1,ch2)=def若只有模板函数,则输出:max(ch1,ch2)=abc•模板函数与非模板函数的优先匹配顺序.templateclassTTmax(Tx,Ty){return(xy)?x:y;}//函数1char*max(char*x,char*y){//函数2return(strcmp(x,y)=0)?x:y;}constchar*max(char*x,constchar*y){//函数3return(strcmp(x,y)=0)?x:y;}voidmain(){charch1[6]=“abc”;charch2[6]=“def”;cout“max(ch1,ch2)=“max(ch1,ch2)endl;}重载模板函数函数匹配顺序：函数2函数1函数3模板类•模板类允许用户为类定义一种模式，使得类中某些数据成员,成员函数的参数以及返回值，能取任意类型(包括标准类型及自定义类型).templateclassT//模板声明classarray{T*data;intsize;public:array(intsize);T&operator[](intindex);//….};•在类定义体外定义成员函数时，需进行模板声明，并在类名后缀“T”.templateclassT//模板声明arrayT::array(intsize){//…}templateclassT//模板声明T&arrayT::operator[](intindex){//…}模板类模板类的使用•模板类的使用其实就是将模板实例化成一个具体的类.格式为:模板类名数据类型.main(){arrayintx(5);for(inti=0;i5;i++)x[i]=i;for(i=0;i5;i++)coutx[i]endl;}•示例程序:10_013.STL的使用•STL(standardtemplatelibrary)是C++提供的一套模板库，包含:–list链表–vector集合(动态数组)–stack栈–queue队列–map图–……其它几种list模板•STL中的list模板封装了链表操作:–begin()指向链表头(节点)–end()指向链表结束(不是指向表尾节点)–push_front(),push_back()添加头/尾节点–pop_front(),pop_back()取出头/尾节点–erase()删除链表中一节点–insert()插入节点到链表中–clear()清空链表–size()返回链表大小–……其它操作•示例程序:10_02vector模板•STL的vector模板封装了动态数组的操作:–begin()指向数组头(节点)–end()指向数组结束(不是指向数组尾元素)–push_back()添加头/尾节点–pop_back()取出头/尾节点–erase()删除链表中一节点–insert()插入节点到链表中–clear()清空链表–size()返回链表大小–operator[]下标操作–……其它操作迭代器iterator•在链表等结构中,一般都有prev,next等指针,通过指针迭代来遍历链表.•大多数模板中，都有迭代器类型iterator,通过迭代器来实现遍历.listintintList;/*此处省略加入数据操作*/listint::iteratorit=intList.begin();//指向头元素while(it!=intList.end()){//直到链表最后cout*it““;it++;//迭代指向下一元素}•示例程序：10_03泛型算法•为了方便程序员开发，STL中不仅封装了多种模板，还提供了很多泛型算法(函数).•泛型算法指独立于具体模板的算法:–min(),max()求最大值最小值–sort()排序–find()查找–remove()删除–accumulate()算数计数•更多的算法请教材或《C++Primer》相关章节及附录.•所有泛型算法前两个实参都是一对iterator,通常被称为first和last.•泛型算法正确工作的要求：–能遍历模板中元素集合：从first通过反复递增操作能到达last.–模板种元素能进行比较：关联的底层类型支持‘等于’操作符.–需要一个公共类型来表示元素在容器中的位置，以及没有找到时使用的无位置(noposition).•使用泛型算法需要包含algorithm和iterator头文件.泛型算法•因为STL中list不像vector一样支持随即访问,所以remove,sort等泛型算法不能用于list，但list模板本身封装了这些算法：–list::sort()排序–list::merge()合并两个有序序列–list::reverse()元素方向排列–list::remove()删除等于某个值的元素–……泛型算法泛型算法示例•从屏幕(或文件)输入一段文字，利用泛型函数(算法)实现：–按字母顺序排列单词–去掉所有重复的单词–去掉没有意义的中性词(如and,if,or,but等)–统计超过6个字母的单词的个数.•示例程序10_04.•仿照示例程序10_01编写模板类matrix，支持任意数据类型的矩阵，重载+,-,*,=,==,[]等操作。利用int,double,类complex(包含实数real,虚数virt两部分)等数据类型测试所写matrix类接口.templateclassTclassmatrix{protected:introw,col;T*elems;public:matrix(intr,intc);/*…*/};上机题