第8章_模板和STL

第八章,模板和STL,本章要点,函数模板和类模板标准模板库STL,8.1模板简介,由于多种数据类型的存在，程序设计过程中经常会遇到针对不同的数据类型要进行完全相同操作的情况。例如比较两个相同类型数据的大小、求某个数的绝对值等。许多类之间也存在相似性。如数组类、链表类等。模板机制采用的主要方法是将所定义的函数或者类中的部分数据的类型作为参数定义，在使用时通过实参来决定真正的类型。这种方法也是一种多态方法，称为参数化多态。,8.2函数模板,用重载函数求两个数中较大的数的函数函数定义如下：intMax(inta,intb)returnab?a:b;doubleMax(doublea,doubleb)returnab?a:b;,上面两个重载的函数除了参数和返回值的类型不同外其余部分完全相同，所以存在着重复书写代码的情况。这样不仅会增加工作量，而且容易出现错误。,8.2函数模板,如果将上述函数中的类型参数化，即将int和double都使用参数Type来代替，可以得到如下的通用代码段TypeMax(Typea,Typeb)returnab?a:b;当需要求两个整数或实数的最大值时，只要将Type替换成int或者double，就可以得到前面定义的重载函数。参数类型可以是任意数值类型。,8.2函数模板,C+使用关键字template定义模板，其格式如下：template函数定义其中模板参数表中的内容为：class标识符或typename标识符（至少1个）当上述参数表中同时包含多个参数时，各项之间用逗号间隔。使用class关键字是早期C+中的语法，由于在C+中关键字class被用于类的定义，为了使语法更严格和清晰，标准C+建议使用关键字typename。上述参数化的函数称为函数模板。,#includeusingnamespacestd;templateTMax(Ta,Tb)returnab?a:b;,intmain()inti1=5，i2=3,imax；doubled1=1.2,d2=3.1,dmax;imax=Max(i1,i2);dmax=Max(d1,d2);coutimaxendl;coutdmaxi;ai=1;cout时，通过将T替换成int生成所需要的类。,程序运行时输入：5则结果显示：下标越界,#include#includearray.husingnamespacestd;templatevoidF(Array,8.3.2类模板用作函数的参数,编译期间，编译器通过类型推导将F(a,5)由函数模板生成如下模板函数：voidF(Array,8.3.3类模板用作基类,考虑对前面的数组类进行改进，使得数组的下标由创建数组时的指定值开始而不是通常的由“0”开始。为了使定义数组不受类型的限制，应该将数组实现为类模板，通过继承的方法可以实现需要的类模板,#includearray.h/barray.htemplateclassbArray:publicArraypublic:bArray(ints,intb=0);T,templatebArray:bArray(ints,intb):Array(s)min=b;templateT,Array是bArray的基类，所以在bArray构造函数的初始化列表中使用了表达式Array(s)以调用基类的构造函数。同理在实现下标运算符重载时，为了调用基类的成员函数，使用了函数调用表达式：Array:operator(imin),例8.4使用bArray模板。#include#includebarray.husingnamespacestd;intmain()bArraya(20,1);inti=100;a5=i;cout导致编译器从类模板生成模板类bArray,在生成这个模板时又产生了Array类数据结构。,C+的标准模板库（STL）包含容器、算法和迭代子，其中容器包括链表、向量、队列、结合、映射等；算法模板包括排序、查找等各种算法；迭代子可以在不同容器上进行操作。,8.4STL,8.4.1STL简介1994年7月，STL正式成为标准+库的一部分。STL中的容器是基于模板机制的，其中既包含线性容器也包含非线性容器。主要的容器有：vector(向量模板)、list(列表模板)、stack(栈模板)、queue(队列模板)、deque(双端队列模板)、map(映射模板)。使用迭代子可以很方便地访问STL容器中的对象。STL中的迭代子可以看成指针的推广，可以是普通的指针。迭代子有顺序访问和直接访问两种，分别对应顺序访问容器和直接访问容器。,STL的算法是用函数模板实现的，可以使用算法通过迭代子实现对不同类型对象的通用操作。算法与容器之间是通过迭代子进行沟通的，算法面向迭代子，迭代子则面向容器。通过迭代子可以获得容器内部的数据对象，算法对这个由迭代子获得的对象进行操作。STL中的算法主要有：排序（sort,merge）、查找（find,search）、比较（equal）和统计（max，min）等。,容器是一种面向对象的数据结构表示方法。C+中的数组就可以看成是一种+内置的容器。+提供了用户自己定义相关容器类的机制。很多情况下，程序中所处理的数据之间都是存在各种联系的。例如数组就是相同类型元素的集合，而且数组中的元素是有序的。现实世界中对象间的联系是普遍存在的。数据结构中元素之间的关系分为线性和非线性两大类。相应地，容器类也可以分为线性容器和非线性容器两大类。线性容器中元素是有序的，非线性容器中的元素是无序的。,8.4.2容器,下面以向量为例来对容器进行说明。向量容器是标准模板库提供的容器类。向量既可以象数组一样对容器内部对象进行直接访问，也可以象链表一样对容器内部的对象进行顺序访问。同时向量具有动态特征，也就是说容器的大小可以动态增长。前面已经讲过，容器是使用模板实现的，向量也不例外。向量模板中重要的成员函数模板有begin()、end()、push_back()、operator()、erase()等。其中begin()返回指向向量的第一个元素的迭代子，end()返回指向向量最后一个元素的后一个位置的迭代子，push_back()是在向量尾部添加元素，operator()是按位置索引向量元素，而erase()则是删除向量任意位置上的元素。,例8.5使用向量求斐波那契数列前十项。#include#includeusingnamespacestd;intmain()inti;vectorvec;vec.push_back(1);vec.push_back(1);for(i=2;i10;i+)vec.push_back(veci-1+veci-2);for(i=0;i10;i+)coutvecit;return0;/程序运行结果如下：11235813213455,8.4.3迭代子迭代子可以看成是指针的扩展，在很多方面指针类似，也是用于指向容器中的元素。迭代子存有它所指定的特定容器的状态信息，也就是说迭代子对每种类型的容器都有一个实现。前面介绍过，STL中有多种不同类型的容器，每种容器都有不同的特点。相应地，作用在不同容器上的迭代子也有不同的类型，不同类型的迭代子所支持的操作也不尽相同。但是有些操作却是通用的,例如，间接引用运算符“*”直接应用一个迭代子，这样就可以使用它所指向的元素；“+”运算符使得迭代子指向容器的下一个元素等。,迭代子为访问容器中的元素提供了除指针之外的一种替代方法。这就是前面介绍容器时提到过的成员函数begin()和end()，它们为迭代子访问容器中的元素提供了帮助。begin()函数返回一个指向容器中第一个元素的迭代子，end()函数返回一个指向容器中最后一个元素下一个位置（虚元素）的迭代子。从end()函数中返回的迭代子只在相等或不等的比较中使用，用于判断遍历容器的迭代子是否到达了容器的末端。,迭代子将容器中的元素抽象为一个序列，为后面介绍的算法提供了一个容器的通用界面。所以迭代子是连接容器和算法的纽带，它们为数据提供了一种抽象的视图，使编制算法的人不必关心多种多样的数据结构的具体细节。反过来说，由迭代子提供一个数据访问的标准模型，也缓解了要求容器提供一组更广泛操作的压力。,例8.6演示迭代子的使用方法。#include#include#includeusingnamespacestd;classComplexpublic:Complex()rpart=0.0;ipart=0.0;Complex(doubled1,doubled2)rpart=d1;ipart=d2;doubleGetrpart()returnrpart;doubleGetipart()returnipart;Complexoperator+(constComplex,private:doublerpart;doubleipart;ComplexComplex:operator+(constComplex,voidComplex:Display()coutcompvec1,compvec2;vector:iteratorcompItbegin,compItend;for(i=0;i10;i+)Complex*comp=newComplex(i*1.0,i*1.0);compvec1.push_back(*comp);compItbegin=compvec1.begin();compItend=compvec1.end();compvec2.insert(compvec2.begin(),compvec1.begin(),compvec1.end();,for(i=0;iDisplay();compItbegin+;i+;coutendl;return0;,程序运行结果如下：(0,0)(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)(7,7)(8,8)(9,9)(0,0)(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)(7,7)(8,8)(9,9),8.4.4算法容器解决的是数据的存储问题也就是数据结构的问题，但是标准容器只定义了很少的基本操作，这些操作不可能满足用户的要求，所以需要标准库提供更多的操作。标准库并没有为每种容器类型都定义实现各种操作的成员函数，而是定义了一组算法。标准库中的算法也称为泛型算法，称为算法是因为它们实现共同的操作；称为泛型是因为它们可以操作在多种容器类型上，既包括内置类型也包括标准库中的容器类，还包括用户自定义的与标准库兼容的容器类型。,例8.7标准库中的集中排序和搜索算法。#include#include#include#includeusingnamespacestd;boolgreater10(intvalule);intmain()constintsize=10;intasize=11,3,7,100,22,9,0,21,8,16;vectorv(a,a+size);ostream_iteratoroutput(cout,);coutvectorvcontains:;,copy(v.begin(),v.end(),output);vector:iteratorloc;loc=find(v.begin(),v.end(),16);if(loc!=v.end()coutnfound16atlocation(loc-v.begin();elsecoutn16notfound;loc=find(v.begin(),v.end(),100);if(loc!=v.end()coutnfound100atlocation(loc-v.begin();elsecoutn100notfound;loc=find_if(v.begin(),v.end(),greater10);,if(loc!=v.end()coutnthefirstvaluegreaterthan10is*locnfoundatlocation(loc-v.begin();elsecoutnnovaluesgreaterthan10werefound;sort(v.begin(),v.end();coutnvectorvaftersort:;copy(v.begin(),v.end(),output);if(binary_search(v.begin(),v.end(),13)coutn13wasfoundinv;elsecoutn13was