C++类模板与STL编程

第10章类模板与STL编程C++语言程序设计教程第10章类模板第10章类模板学习目标1.理解类模板的概念；2.掌握类模板的定义、实例化过程，会运用类模板；3.掌握栈类模板、链表类模板的使用；4.理解STL编程的基本思想；5.掌握STL容器的使用；6.熟练使用STL算法；7.理解STL函数对象；C++语言程序设计教程第10章类模板C++语言程序设计教程第10章类模板10.1类模板模板是C++语言的重要特征，它能够显著提高编程效率。利用C++的函数模板和类模板，能够快速建立具有类型安全的类库集合和函数集合，进行大规模软件开发，并提高软件的通用性和灵活性。C++的标准模板库（standardtemplatelibrary，简称STL）编程完全依赖模板的实现。类模板是能根据不同参数建立不同类型成员的类。类模板中的数据成员、成员函数的参数、成员函数的返回值可以取不同类型，在实例化成对象时，根据传入的参数类型，实例化成具体类型的对象。类模板也称模板类。类模板定义的语法为：其中：template为模板关键字。模板参数表中的类型为参数化(parameterized)类型，也称可变类型，类型名为class(或typename)；模板参数表中的类型也可包含普通类型，普通类型的参数用来为类的成员提供初值。类模板中的成员函数可以是函数模板，也可以是普通函数。C++语言程序设计教程第10章类模板1.类模板的定义template模板参数表class类名{成员名；};例如，下面定义了一个模板类Student，为了增强类的适用性，将学号设计成参数化类型，它可以实例化成字符串、整型等；将成绩设计成参数化类型，它可以实例化成整型、浮点型、字符型(用来表示等级分)等；C++语言程序设计教程第10章类模板1.类模板的定义templateclassTNO,classTScore,intnum//TNO,TScore为参数化类型classStudent{private:TNOStudentID[num];//参数化类型数组，存储姓名TScorescore[num];//参数化类型数组，存储分数public:TNOTopStudent()//普通函数{returnStudentID[0];}intBelowNum(TScoreascore)//函数模板{return0;}voidsort()//普通函数{}};模板类的成员函数还可以在类外定义，其语法如下：：其中：模板参数表与类模板的模板参数表相同。模板参数名表列出的是模板参数表中参数名，顺序与模板参数表中的顺序一致。C++语言程序设计教程第10章类模板1.类模板的定义template模板参数表类型类名模板参数名表∷函数名(参数表){函数体;}模板类的成员函数还可以在类外定义，其语法如下：C++语言程序设计教程第10章类模板1.类模板的定义template模板参数表类型类名模板参数名表：：函数名(参数表){函数体；}其中：模板参数表与类模板的模板参数表相同；模板参数名表列出的是模板参数表中参数名，顺序与模板参数表中的顺序一致；例如，模板类Student的成员函数在类外实现如下：模板类Student的成员函数在类外实现如下：templateclassTNO,classTScore,intnumclassStudent{private:TNOStudentID[num];TScorescore[num];public:TNOTopStudent();intBelowNum(TScoreascore);voidsort();};templateclassTNO,classTScore,intnumintStudentTNO,TScore,num::BelowNum(TScoreascore){return0;}templateclassTNO,classTScore,intnumvoidStudentTNO,TScore,num::sort(){}templateclassTNO,classTScore,intnumTNOStudentTNO,TScore,num::TopStudent(){returnStudentID[0];}一个类模板是具体类的抽象，在使用类模板建立对象时，才根据给定的模板参数值实例化(专门化)成具体的类，然后由类建立对象。与函数模板不同，类模板实例化只能采用显式方式。类模板实例化、建立对象的语法如下:C++语言程序设计教程第10章类模板2.类模板的实例化类模板名模板参数值表对象1,对象2,…,对象n;其中：模板参数值表的值为类型名，类型名可以是基本数据类型名，也可以是构造数据类型名，还可以是类类型名。模板参数值表的值还可以是常数表达式，以初始化模板参数表中普通参数。模板参数值表的值按一一对应的顺序实例化类模板的模板参数表。例如，下面对模板类Student实例化:classString{public:charStr[20];};voidmain(){StudentString,float,100S1;S1.sort();Studentlong,int,50S2;S2.TopStudent();}编译StudentString,float,100S1；时：String取代TNOfloat取代TScore100取代numC++语言程序设计教程第10章类模板2.类模板的实例化templateclassTNO,classTScore,intnumclassStudent{private:TNOStudentID[num];TScorescore[num];public:TNOTopStudent()intBelowNum(TScoreascore)voidsort()};classStudent{private:StringStudentID[100];floatscore[100];public:StringTopStudent();intBelowNum(floatascore);voidsort();};将类Student实例化成：C++语言程序设计教程第10章类模板2.默认模板参数templateclassTNO,classTScore=int,intnum=10classStudent{private:TNOStudentID[num];TScorescore[num];public:TNOTopStudent();intBelowNum(TScoreascore);voidsort();};类模板的实例化过程与函数调用的实参与形参结合的过程相似，函数的形参可以采用默认值，类模板的类型参数也可以采用默认值，这样避免每次实例化时都显式给出实参。TScore,num分别给出默认值int，10。用以下方式实例化：Studentchar*S1;classStudent{private:char*StudentID[10];intscore[10];public:char*TopStudent();intBelowNum(intascore);voidsort();};10.2类模板应用1.栈类模板C++语言程序设计教程第10章类模板栈是一种先进后出FILO(FirstInLastOut)的一种结构，在程序设计中广泛使用栈，栈的基本操作有:压栈push、出栈pop。其他操作有判空、判满、读栈顶元素等。下图演示栈的操作：toputopzztopyytopxxx(a)栈空(b)进栈push(x)(c)栈满(d)出栈pop()【例10-1】将栈设计成一个类模板，在栈中存放任意类型的数据。分析：栈空间可以使用静态数组，本例中使用动态数组。使用指针top指向栈顶元素，使用成员函数push()、pop()、IsEmpty()、IsFull()分别进行压栈、出栈、判空、判满。1.栈类模板891011121314151617181920212223242526272829303132//*p10_1.cpp栈类模板templateclassTclassStack{private:intsize;inttop;T*space;public:Stack(int=10);~Stack(){delete[]space;}boolpush(constT&);Tpop();boolIsEmpty()const{returntop==size;}boolIsFull()const{returntop==0;}};C++语言程序设计教程第10章类模板33343536373839404142434445464748495051525354555657585960616263646566templateclassTStackT::Stack(intsize){this-size=size;space=newT[size];top=size;}templateclassTboolStackT::push(constT&element){if(!IsFull()){space[--top]=element;returntrue;}returnfalse;}templateclassTTStackT::pop(){returnspace[top++];}intmain(){StackcharS1(4);S1.push('x');S1.push('y');S1.push('z');S1.push('u');S1.push('v');while(!S1.IsEmpty())coutS1.pop()endl;return0;}运行结果:uzyx2.链表类模板C++语言程序设计教程第10章类模板【例10-2】将线性链表设计成一个类模板，从而可以在链表节点中存放任意类型的数据。分析：链表的操作见5.5.1，为了节省内存空间，将头指针与当前节点指针设计成static,为同类型链表所共有；为了便于操作，同样将链表的第一个节点当成头节点，不存储数据。链表的构成如下图所示：headheadCurNodeCurNodedatadata‘A’‘B’nextNULLnextNULL(a)仅含头节点的空链表(b)添加节点后的链表2.链表类模板C++语言程序设计教程第10章类模板5678910111213141516171819202122232425//p10_2.cpp*单向链表的类模板*#includeiostreamusingnamespacestd;templateclassTYPEclassListNode{private:TYPEdata;ListNode*next;staticListNode*CurNode;staticListNode*head;public:ListNode(){next=NULL;head=CurNode=this;}ListNode(TYPENewData){data=NewData;next=NULL;}程序解释：第16行为不带参数的构造函数，用于建立头节点。第62行建立对象时，调用了不带参数的构造函数，建立了一个仅含头节点的链表。第20行为带数据域参数的构造函数，供函数AppendNode()动态建立节点对象时调用。2.链表类模板C++语言程序设计教程第10章类模板262728293031323334353637383940414243444546474849voidAppendNode(TYPENewNode);voidDispList();voidDelList();};templateclassTYPEListNodeTYPE*ListNodeTYPE::CurNode;templateclassTYPEListNodeTYPE*ListNodeTYPE::head;templateclassTYPEVoidListNodeTYP