第十章 模板与标准模板库模板(程序设计语言)

10.1函数模板10.2类模板10.3标准模板库第10章模板与标准模板库模板模板是C++支持参数化多态的工具，使用模板可以使用户为类或者函数声明一种一般模式，使得类中的某些数据成员或者成员函数的参数、返回值取得任意类型。C++的标准模板库STL(StandardTemplateLibrary)已经成为一个标准，它包含容器，算法以及迭代子(或称迭代器)。本章首先探讨函数模板和类模板，然后介绍C++标准模板库的使用。函数模板的语法形式如下：templateclassT函数定义利用函数模板，可以建立一个具有通用功能的函数，支持不同的函数参数和返回值，达到减少代码书写量的目的。T代表在函数模板中要使用的通用类型，在该函数的调用过程中，T被具体化。【10.1函数模板】或：templateclassT1，classT2，classTn函数定义templateclassTTabs(Tvalue){returnvalue0?value:-value;}例如重载函数，求绝对值的函数只要声明一个函数模板：intmain(){intnValue=-1,nResult;doubledblValue=-1.2,dblResult;nResult=abs(nValue);dblResult=abs(dblValue);coutnValue″″nResultendl;coutdblValue″″dblResultendl;return0;}-11-1.21.2第一次使用函数模板abs（）时，实参为整数，由此可以推导出函数模板中的参数类型T为整数，函数的返回值也是整数。第二次调用abs()时实参为双精度型，由此推导出函数模板中的参数类型T为双精度型，函数的返回值为双精度型。在主程序中可以这样使用函数模板：数据成员变成另外一种数据类型，或者干脆是一个类的对象，又要重新拷贝，重新进行修改。这样不仅程序的代码数量急剧增加，修改过程中也很容易出现各种疏漏。用一种类似函数模板的机制来解决问题——类模板。C++语言中的类模板的语法定义如下：Template模板参数表类声明当模板参数表中同时包含上述多项内容时，各项内容之间以逗号隔开。注与函数模板相同，类模板只有使用的时候才被具体化为某一种类型。使用模板类来产生对象时，按如下形式声明：模板模板参数表对象名1，......对象名n;模板参数表中的内容可以为：class标识符类型说明符标识符【10.2类模板】类模板举例//EXAMPLE10_02.H#ifndefEXAMPLE10_02_H#defineEXAMPLE10_02_HtemplateclassTclassMax//声明类模板Max{private:Titem1,//类型为T,T在该类的对象生成时具体化item2,item3;public:Max(){}Max(Tthefirst,Tthesecond,Tthethird);TGetMaxItem();//求得3个元素中的最大值并按类型T返回voidSetItem(Tthefirst,Tthesecond,Tthethird);//设置类中的3个元素的值}#endif//EXAMPLE10_02B.H例10-2//类模板的实现#ifndefEXAMPLE10_02B_H#defineEXAMPLE10_02B_HtemplateclassTTMaxT::Max(Tthefirst,Tthesecond,Tthethird):item1(thefirst),item2(thesecond),item3(thethird){return;}templateclassTvoidMaxT::SetItem(Tthefirst,Tthesecond,Tthethird){item1=thefirst;item2=thesecond;item3=thethird;}templateclassTTMaxT::GetMaxItem()（续）{Tmaxitem;maxitem=item1item2?item1:item2;maxitem=maxitemitem3?maxitem:item3;returnmaxitem;}#endif//EXAMPLE10_2.CPP//主程序#includeiostream.h#include″EXAMPLE1002.H″#include″EXAMPLE1002B.H″intmain(){MaxintnmyMax(1,2,3);MaxdoubledblmyMax(1.2,1.3,-1.4);coutnmyMax.GetMaxItem()endl;coutdblmyMax.GetMaxItem()endl;return0;}31.3编程实现栈类模板并测试//EXAMPLE10_03.CPP//源程序开始#includeiostream.h#includestdlib.htemplateclassTclassCStack//模板名{public:CStack(intsize_t=10);//构造函数模板~CStack();//析构函数模板boolEmpty()const;//栈空判断boolFull()const;//栈满判断voidClear();//清空栈T&Top()const;//查询栈顶元素voidPush(constT&);//入栈T&Pop();//出栈private:intsize;inttop;例10-3（续）T*ptrStack;};templateclassTCStackT::CStack(intsize_t)//构造函数模板{if(size_t0)size=size_t;elsesize=10;top=-1;ptrStack=newT[size];}templateclassTCStackT::~CStack()//析构函数模板{delete[]ptrStack;}templateclassTboolCStackT::Empty()const//栈空判断{returntop==-1;}（续）templateclassTboolCStackT::Full()const//栈满判断{returntop==size-1;}templateclassTT&CStackT::Top()const//查询栈顶元素{if(!Empty())returnptrStack[top];elseexit(1);}templateclassTvoidCStackT::Clear()//清空栈{top=-1;}templateclassTvoidCStackT::Push(constT&value)//入栈{if(!Full()){（续）ptrStack[++top]=value;}elseexit(1);}templateclassTT&CStackT::Pop()//出栈{if(!Empty()){top--;returnptrStack[top+1];}elseexit(1);}//测试程序intmain(){CStackdoubledblStack(5);//定义一个CStackdouble模板类对象dblStackinti;doubletemp;（续）for(i=0;i5;i++){coutPushelementsiinstack:;cintemp;dblStack.Push(temp);//入栈}while(!dblStack.Empty()){temp=dblStack.Pop();//出栈cout---tempendl;}return0;}Pushelements0instack:11.11Pushelements1instack:22.22Pushelements2instack:33.33Pushelements3instack:44.44Pushelements4instack:55.55---55.55---44.44---33.33---22.22---11.11程序运行结果：实现了数组、链表、线性表、栈和队列，它们属于线性容器。另外，这里还将使用到双端队列，就是两端都可以进行插入和删除操作的线性表。除了线性容器，我们还将接触到两种非线性容器：集合和映射。【10.3.1基本数据结构知识】C++的标准模板库STL包含容器、算法和迭代子，其中容器模板包括链表、向量、栈、队列、集合、映象等，算法模板包括诸如排序、查找等各种算法，而迭代子则可以针对不同容器进行操作。本章将着重介绍STL的使用。【10.3标准模板库】若干个固定事物的全体叫做一个集合，组成集合的事物叫做这个集合的元素。例如对于一个有四个元素的集合A可以如下表示：A={a1,a2,a3,a4}映射则是把一个集合中的元素和另一个集合中的元素联系起来。日常生活中也存在大量映射的例子，如一个身份证号码可以映射为某个确定的人，图书馆中一本书的编号和这本书也是一个映射。例如两个集合A和B：A={1,2,3,4}B={a,b,c,d}我们可以构造从集合A到集合B的映射(1,a),(2,b),(3,d),(4,c)等等。子集：如果一个集合A的所有元素都是另一个集合B的元素，则集合A是集合B的子集。交集：取集合A和集合B中所有相同元素组成的集合差集：集合A对集合B的差集可以定义为由所有属于集合A但不属于集合B的元素组成的集合。1994年7月，STL正式成为标准C++库的一部分。STL中的容器类是基于模板的，它既包含线性容器，也包含非线性容器，其中主要有：vector(向量模板)list(链表模板)stack(栈模板)queue(队列模板)deque(双端队列模板)set(集合模板)map(映射模板)STL的迭代子可以看成是指针的推广，迭代子也可以是普通的指针。类型分类顺序访问：直接访问：顺序迭代子使用++、--等进行移动，但只能顺序访问容器中的对象。直接访问迭代子则可以直接访问容器中的某个特定对象。【10.3.2标准模板类库简介】STL的算法是用函数模板实现的，可以实现对不同类型对象的通用操作。排序（sort、merge）查找（find、search）比较（equal）集合（includes、setunion、setdifference）计算（accumulate、partialsum）统计（max、min）管理（swap、fill、replace、copy、unique、rotate、reverse）堆操作（makeheap、pushheap、popheap、sortheap）算法与STL容器类之间是通过迭代子来进行沟通的，算法面向迭代子，迭代子则面向容器类,对于迭代子，可以将它理解为一个指针，通过它我们可以获得容器内部的数据对象，然后算法对这个由迭代子获得的对象进行操作。STL的主要算法有：C++语言标准类库提供了向量容器，向量既有象数组一样可以对容器内部对象进行直接访问的特点，也有类似于链表可以对容器内部对象进行顺序访问的特点，同时向量具有动态特征，所以C++语言中的向量容器具有数组和链表两者的优点。向量模板类中较为重要的成员函数有begin、end、insert、erase、operator［］等。iteratorinsert(iteratorit,constT&x=T());//将x复制到it位置之前voidinsert(iteratorit,sizetypen,constT&x);//将n个x复制到it位置之前voidinsert(iteratorit,constiteratorfirst,constiteratorlast);//将first和last//之间的对象复制到it位置之前iteratorerase(iteratorit);//移走it位置的对象iterat