C++模板STL库教程

C++模板与STL库介绍第8章提纲1.概论2.模板机制的介绍3.STL中的基本概念4.容器概述5.迭代器6.算法简介概论C++语言的核心优势之一就是便于软件的重用C++中有两个方面体现重用：1.面向对象的思想：继承和多态，标准类库2.泛型程序设计(genericprogramming)的思想：模板机制，以及标准模板库STL这次课的重点泛型程序设计泛型程序设计，简单地说就是使用模板的程序设计法。将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。标准模板库(StandardTemplateLibrary)就是一些常用数据结构和算法的模板的集合。主要由AlexStepanov开发，于1998年被添加进C++标准有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。模板引子1.假如设计一个求两参数最大值的函数，在实践中我们可能需要定义四个函数：intmax(inta,intb){return(ab)?a,b;}longmax(longa,longb){return(ab)?a,b;}doublemax(doublea,doubleb){return(ab)?a,b;}charmax(chara,charb){return(ab)?a,b;}2.这些函数几乎相同，唯一的区别就是形参类型不同3.需要事先知道有哪些类型会使用这些函数，对于未知类型这些函数不起作用intabs(inta){returna0?-a:a；}doubleabs(doublea){returna0?-a:a；}数据为int或double时的求绝对值问题classSquare1{public:Square1(inty):x(y){}intfun(){returnx*x;}private:intx;};用类实现求一个数的平方classSquare2{public:Square(doubley):x(y){}doublefun(){returnx*x;}private:doublex;};样例：求最大值模板函数实现1.求两个数最大值，使用模板templateclassTTmax(Ta,Tb){return(ab)?a,b;}2.template模板形参表//模板声明格式返回值类型函数名（模板函数形参表）{//函数定义体}8模板的概念1.所谓模板是一种使用无类型参数来产生一系列函数或类的机制。2.若一个程序的功能是对某种特定的数据类型进行处理，则可以将所处理的数据类型说明为参数，以便在其他数据类型的情况下使用，这就是模板的由来。3.模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。4.通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而避免需要为每一种数据类型产生一个单独的类或函数。注意：●模板并非通常意义上可直接使用的函数或类，它仅仅是对一族函数或类的描述，是参数化的函数和类。●模板是一种使用无类型参数来产生一族函数或类的机制。模板分类函数模板(functiontemplate)是独立于类型的函数可产生函数的特定版本类模板(classtemplate)跟类相关的模板，如vector可产生类对特定类型的版本，如vectorint11模板工作方式函数模板只是说明，不能直接执行，需要实例化为模板函数后才能执行在说明了一个函数模板后，当编译系统发现有一个对应的函数调用时，将根据实参中的类型来确认是否匹配函数模板中对应的形参，然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同，它称之为模板函数12#includeiostreamtemplateclassT,classT1Tmin(Ta[],T1n){inti;Tminv=a[0];for(i=1;in;i++){if(minva[i])minv=a[i];}returnminv;}编写一个对具有n个元素的数组a[]求最小值的程序，要求将求最小值的函数设计成函数模板。voidmain(){inaa[]={1,3,0,2,7,6,4,5,2};doubleb[]={1.2,-3.4,6.8,9,8};cout”a数组的最小值为：”min(a,9)endl;cout”b数组的最小值为：”min(b,4)endl;}此程序的运行结果为：a数组的最小值为：0b数组的最小值为：-3.42、模板的实例化●模板通过参数实例化可以构建具体的函数或类，称为模板函数和模板类。模板实例化示意图模板函数模板类模板模板类模板函数对象实例化实例化实例化1.函数模板的定义定义格式如下：template模板形参表返回值类型函数名(参数表){函数体}//模板参数列表不能为空8.2函数模板函数模板只是一种说明，并不是一个具体的函数，C++编译系统不会产生任何可执行代码。当遇到具体的函数调用时，才根据调用处的具体参数类型，在参数实例化以后才生成相应的代码，此时的代码称为模板函数。2.函数模板的使用函数模板的实例化是在编译按系统处理函数调用时由系统自动完成。在调用函数模板时，系统首先确定模板参数所对应的具体类型，并依据该类型生成一个具体函数，系统实际上是调用了这个具有确定参数类型的函数。模板函数是函数模板的一个具体实例，是模板参数实例化后的一个可执行的具体函数，只处理一种确定的数据类型。3.模板函数的生成#includeiostream.htemplateclassType1,classType2voidmyfunc(Type1x,Type2y){coutx''y'\n';}intmain(){myfunc(10,hi);myfunc(0.23,10L);return0;}#includestringtemplateclassTTmax(Ta,Tb){return(ab)?a:b;}templateclassTTmax(Ta,Tb,Tc){Tt;t=(ab)?a:b;return(tc)?t:c;}char*max(char*a,char*b){return(strcmp(a,b)0)?a:b;}#includeiostream.hmain(){intx=10,y=20,max1;doublea=10.4,b=21.3,c=13.4,max2;max1=max(x,y);max2=max(a,b,c);coutThemaxinumofxandyis:max1endl;coutThemaxinumofaandbandcis:max2endl;char*c1,*c2,*c3;c1=aaaa;c2=bbbb;c3=max(c1,c2);coutThemaxinumofc1andc2is:c3endl;return0;}8.3类模板如同函数模板一样，类模板是参数化的类，即用于实现数据类型参数化的类。应用类模板可以使类中的数据成员、成员函数的参数及成员函数的返回值，能根据模板参数匹配情况取任意数据类型。1.类模板的定义template模板形参表class类模板名{成员的声明；}定义格式如下：●模板类的成员函数必须是函数模板。●类模板中的成员函数的定义，若放在类模板的定义之中，则与类的成员函数的定义方法相同；若在类模板之外定义，则成员函数的定义格式如下：类模板成员函数的定义template模板形参表返回值类型类模板名类型名表::成员函数名(参数表){成员函数体}当类模板在程序中被引用时，系统根据引用处的参数匹配情况将类模板中的模板参数置换为确定的参数类型，生成一个具体的类。这种由类模板实例化生成的类称为模板类。类模板必须先实例化为相应的模板类，并定义该模板类的对象以后才可以使用。2.类模板的使用类模板实例化==》模板类的格式如下：类模板实例化类模板名实际类型；Squareintinta(15);定义模板类的对象的格式类模板名实际类型对象名(实参表)；举例例8-4类模板的应用例8-5含有成员函数的类模板定义模板优缺点函数模板方法克服了C语言解决上述问题时用大量不同函数名表示相似功能的坏习惯克服了宏定义不能进行参数类型检查的弊端克服了C++函数重载用相同函数名字重写几个函数的繁琐缺点，调试比较困难一般先写一个特殊版本的函数运行正确后，改成模板函数28STL中的几个基本概念容器：可容纳各种数据类型的数据结构。迭代器：可依次存取容器中元素的东西算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如，数组intarray[100]就是个容器，而int*类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法容器概述可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。容器分为三大类：1)顺序容器vector：后部插入/删除，直接访问deque：前/后部插入/删除，直接访问list：双向链表，任意位置插入/删除2)关联容器set：快速查找，无重复元素multiset：快速查找，可有重复元素map：一对一映射，无重复元素，基于关键字查找multimap：一对一映射，可有重复元素，基于关键字查找前2者合称为第一类容器3)容器适配器stack：LIFOqueue：FIFOpriority_queue：优先级高的元素先出容器概述对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现==和运算符。顺序容器简介1)vector头文件vector实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。2)deque头文件deque也是个动态数组，随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。3)list头文件list双向链表，在任何位置增删元素都能在常数时间完成。不支持随机存取。上述三种容器称为顺序容器，是因为元素的插入位置同元素的值无关。关联容器简介关联式容器内的元素是排序的，插入任何元素，都按相应的排序准则来确定其位置。关联式容器的特点是在查找时具有非常好的性能。1)set/multiset:头文件setset即集合。set中不允许相同元素，multiset中允许存在相同的元素。2)map/multimap:头文件mapmap与set的不同在于map中存放的是成对的key/value。并根据key对元素进行排序，可快速地根据key来检索元素map同multimap的不同在于是否允许多个元素有相同的key值。上述4种容器通常以平衡二叉树方式实现，插入和检索的时间都是O(logN)容器适配器简介1)stack:头文件stack栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则2)queue:头文件queue队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。3）priority_queue:头文件queue优先级队列。最高优先级元素总是第一个出列容器的共有成员函数1)所有标准库容器共有的成员函数：相当于按词典顺序比较两个容器大小的运算符：=,,=,,=,==,!=empty:判断容器中是否有元