C++程序设计自考4737第7章

第7章类模板与向量在C+中，不但可以设计函数模板，满足对不同类型数据的同一功能要求，还可以设计类模板，来表达具有相同处理方法的数据对象集。类模板也是实现STL库的基础。向量容器vector是使用最广泛的容器之一，它克服了数组的局限性。本章将简要介绍使用向量容器类的基础知识，并引入STL库和范型算法的基础知识。,主要内容,7.1类模板7.2向量容器与范型算法7.3向量应用实例_出圈游戏,7.1类模板如果将类看做包含某些数据类型的框架，然后将数据类型从类中分离出来形成一个通用的数据类型T，并且允许具体数据类型的类能使用数据类型T所提供的不同操作，这将避免因为类的数据类型不同而产生的重复性设计。其实，这种类型并不是类，而仅仅是类的描述，常称之为类模板。在编译时，由编译器将类模板与某种特定数据类型联系起来，就产生一个真实的类。由此可见，利用类模板进行程序设计，就如烹调食物一样，只要购买了原料，就可以做出不同口味的菜肴。,7.1.1类模板基础知识1.类模板的成分及语法可以用类模板来定义类，类模板是对象特性更一般的抽象。简言之，一个类模板就是一个抽象的类。类模板与函数模板的有些成分是相同的，例如声明的方法及参数的格式等。关键字class在这里的含义是“任意内部类型或用户定义类型”，但T也可能是结构或类。对于函数模板及类模板来说，模板层次结构的大部分内容都是一样的，然而在模板声明之后，对类而言便显示出了根本性的差异。为了创建类模板，在模板参数表之后，应有类声明。在类中可以像使用其他类型(如int或double)那样使用模板参数。例如，可以把模板参数用做数据成员，返回类型的成员函数或成员函数的参数等。,类模板声明的一般方法如下：templateclass类名/类体；,【例7.1】使用类模板的实例。template/带参数T的模板声明/可用typename代替classclassTAnyTempTx,y;/类型为T的私有数据对象public:TAnyTemp(TX,TY):x(X),y(Y)/类构造函数Tgetx()returnx;/内联类成员函数，返回类型为TTgety()returny;/内联类成员函数，返回类型为T;类模板TAnyTemp声明了两个私有数据成员，即类型都为T的数据成员x和y，一旦使用类模板，它就可以保存被指定类型的两个值。,2.类模板的对象类模板也称为参数化类型。初始化类模板时，传给它具体的数据类型，就产生了模板类。使用模板类时，编译器自动产生处理具体数据类型的所有成员（数据成员和成员函数）。如使用上述模板定义对象iObject，并以int替换参数T:,2.类模板的对象如使用上述模板定义对象iObject，并以int替换参数T:TAnyTempiObject(321,556);告诉编译器从模板产生一个类，并用int替换所有的参数T，所产生的类的名字变成TAnyTemp，定义的对象名为iObject。两个整型值321和556传递给对象的构造函数以初始化该对象的私有数据对象。所产生类的全名是TAnyTemp，这包括尖括号和int数据类型。可以从这个模板再产生一个实例：TAnyTempdObject(3.1416,5.1552);对象dObject能保存两个double值，这是因为又产生一个实例TAnyTemp，它是与前者毫无关系的类，相同之处只是都产生于同一个模板。,只要赋给模板一种实际的数据类型，就会产生新的类，而且以特定类型替代模板参数。定义对象的一般格式如下：类名对象名(构造函数实参列表);类名对象名;/默认或者无参/数构造函数模板实例化参数类型包括数据类型和值，参考【例7.3】的等形式。编译器不能从构造函数列表推断出模板实例化参数类型，所以必须显式地给出它们的参数类型。,【例7.2】求4个数中最大值的类模板程序。#includeusingnamespacestd;templateclassMax4Ta,b,c,d;TMax(Ta,Tb)return(ab)?a:b;public:Max4(T,T,T,T);TMax(void);template/定义成员函数必须再次声明模板Max4:Max4(Tx1,Tx2,Tx3,Tx4):a(x1),b(x2),c(x3),d(x4)template/定义成员函数必须再次声明模板TMax4:Max(void)/定义时要将Max4看做整体returnMax(Max(a,b),Max(c,d);,voidmain()Max4C(W,w,a,A);/比较字符Max4A(-25,-67,-66,-256);/比较整数Max4B(1.25,4.3,-8.6,3.5);/比较双精度实数coutC.Max()A.Max()“B.Max()endl;输出结果为：w-254.3,在类体外面定义成员函数时，必须用template重写模板函数声明。一般格式如下：template返回类型类名:成员函数名(函数参数列表)/函数体是指template的“”内使用class(或typename)声名的类型参数，也就是使用的类型参数列表。构造函数和析构函数没有返回类型。,【例7.3】演示对4个数字求和的类模板程序。#includeusingnamespacestd;template/可以传递程序中的整数参数值classSumTmsize;/数据成员public:Sum(Ta,Tb,Tc,Td)/构造函数m0=a;m1=b;m2=c;m3=d;TS()/求和成员函数returnm0+m1+m2+m3;,voidmain()Sumnum1(-23,5,8,-2);/整数求和Sumf1(3.5f,-8.5f,8.8f,9.7f);/单精度求和。使用f显式说明float型Sumd1(355.4,253.8,456.7,-67.8);Sumc1(W,-2,-1,-1);/字符减，等效/于W-4，结果为Scoutnum1.S(),f1.S(),“d1.S(),c1.S()endl;输出结果为：-12,13.5,998.1,S。,7.1.2类模板的派生与继承模板类的成员函数不能声明为虚函数，它的基类和派生类都可以是模板(或非模板)类。前面已经讨论过全是非模板类的情况，同样，类模板也可以继承，继承的方法也一样。声明模板继承之前，必须重新声明模板。下面讨论其他3种情况。1.模板类继承非模板类用一个非模板类，为一组模板提供一种共同实现的方法。,1.模板类继承非模板类用一个非模板类，为一组模板提供一种共同实现的方法。【例7.4】设计一个非模板类Point类，然后设计一个继承Point类的类模板Line。#includeusingnamespacestd;classPoint/非模板类Pointintx,y;public:Point(inta,intb)x=a;y=b;voiddisplay()coutx,yendl;,template/类模板classLine:publicPointTx2,y2;public:Line(inta,intb,Tc,Td):Point(a,b)x2=c;y2=d;voiddisplay()Point:display();coutx2,y2endl;,voidmain()Pointa(3,8);a.display();Lineab(4,5,6,7);ab.display();Linead(4,5,6.5,7.8);ad.display();程序输出结果如下：3,84,56,74,56.5,7.8,2.非模板类继承类模板的一个实例类模板能产生不同实例，所以非模板类只能继承一个确定的模板类，既继承一个实例。【例7.5】设计一个模板类Point类，然后设计一个继承Point类的Line类。#includeusingnamespacestd;template/类模板classPointTx,y;public:Point(Ta,Tb)x=a;y=b;voiddisplay()coutx,yendl;,classLine:publicPoint/继承Point的int模板类intx2,y2;public:Line(inta,intb,intc,intd):Point(a,b)x2=c;y2=d;voiddisplay()Point:display();coutx2,y2endl;,voidmain()Pointa(3.5,8.9);/可以是用double类型a.display();Lineab(4,5,6,7);/只能是int类型ab.display();程序运行结果如下：3.5,8.94,56,7,3.从类模板派生一个类模板它与上一个的重要区别：前者只能继承类模板的一个实例，这里是继承类模板的所有实例(模板类)。【例7.6】设计一个模板类Point，然后共有派生一个模板类Line。#includeusingnamespacestd;templateclassPointTx,y;public:Point(Ta,Tb)x=a;y=b;voiddisplay()coutx,yendl;,templateclassLine:publicPointTx2,y2;public:Line(Ta,Tb,Tc,Td):Point(a,b)x2=c;y2=d;voiddisplay()Point:display();coutx2,y2y1(125,188);则将模板类作为基类。这个未知基类还可以是派生类。,7.2向量容器与泛型算法在数组生存期内，数组的大小是不会改的，向量容器则可在运行中动态地增长或缩小。向量是类模板，具有成员函数，例如可以使用size()方法动态地获得vector的当前大小。面向对象的向量vector是使用最广泛的一个容器类，本节重在介绍它的使用方法。,7.2.1定义向量列表vector类模板定义在头文件vector中，它提供4种构造函数，用来定义由各元素组成的列表。用length表示长度，数据类型用type表示，对象名为name，则：vectorname;/定义type的向量空表vectorname(length);/定义具有length个type的/向量，元素初始化为0vectorname(length,a);/定义具有length个type的/向量，元素初始化为avectorname1(name);/使用已定义的向量name/构造向量name1,空表没有元素，它使用成员函数获取元素。下面是典型的使用方法：vectorA;/空的char向量vectorB(20);/具有20个int的向量,元素/初始化值均为0vectorC(20,1);/具有20个int的向量，其/元素均被置为1vectorD(C);/用C初始化D，即D与C一样vectorE(20,t);/具有20个char的向量，其元/素均被置为tvectorF(2*2,5);/具有4个int的向量，其元素/均被置为5vectorG(F);/与F相同，有4个int向量/且均被置为5D=F;/整体赋值，使D与F相同G=C;/整体赋值，使G与C相同,向量定义的赋值运算符“=”，允许同类型的向量列表相互赋值，而不管它们的长度。它可以改变赋值目标的大小，使它的元素数目与赋值源的元素数目相同。虽然E和C的元素数目相同，因为它们的类型不同，因此也不能相互赋值。向量第1个元素也是从0开始，使用下面语句可得到它们的大小为：20,20,4,20,4,20coutB.size(),C.size(),“D.size(),E.size(),F.size(),G.size()endl;这样，使用for语句循环输出时，可以利用size()函数。例如输出向量B:for(inti=0;iB.size();i+)coutBiendl;不能使用列表初始化向量，但可以先初始化一个数组，,然后把数组的内容复制给向量。例如，先定义具有10个整数元素的整型数组IA，然后初始化向量VB：intIA10=1,3,5,7,9,12,14,16,18,20;vectorVB(IA,IA+10);IA是数组名，代表数组起始地址。IA+10是VB的结束标志位，VB的长度为10。因为向量自动产生一个结束标志，所以VB不需要与IA等长。这里VB的长度可以小于10或大于10。当定义的VB比IA长时，10个以后的元素值不定。从这一点看，它具有字符串数组的特点。zj1这是定义向量的又一种方式，而且是在定义向量的同时完成初始化。需要注意的是，不能使用这种方法去初始化一个已经存在的向量。,7.2.2泛型指针泛型算法提供了许多可用于容器类的操作行为，而这些算法和想要操作的元素类型无关。也就是说，它们和int,double或者string全然无关。泛型算法达到了“与操作对象的数据类型相互独立”的目的。而达到“与容器无关”的诀窍，就是不直接在容器身上进行操作。这种操作是借助一对iterators(迭代子)实现的。迭代子就是一种泛型指针,具有指示第一个元素的begin()和指示结束的标记end()，也就是标识要进行迭代的元素空间。如果begin不等于end，算法便会首先作用于begin所指元素，并将begin前进一个位置，然后作用于当前的begin所指的元素身上，如此继续进行，直到begin等于end为止。因为end是最后一个元素的下一个位置，所以元素存在范围是半开区间begin，end)。图7.1是向量a和迭代子示意图。,在容器类里，是在底层指针的行为之上提供一层抽象化机制，取代程序原来的“指针直接操作方式”。这种指针称为泛型指针，正向泛型指针定义的一般形式如下：vector:iterator泛型指针名;iterator是正向泛型指针关键字。,如向量的数据类型为char，指针名为p。注意定义里使用p，不是*p。如果用*p，则含义为指针的指针，是错误的。泛型指针是使用类实现的，不要与前面介绍的指针定义混淆。当然，它也是使用“*p”代表它指向的元素值。容器提供“迭代因子”供泛型指针使用，例如p=a.begin();将向量a的第1个元素的地址赋给泛型指针p。这时，p就可使用与指针一样的运算方式，例如p+2代表顺序移动两个元素位置，*(p+1)是输出位置的下一个元素。对向量的访问可以是双向的，图中的rbegin和rend是提供给逆向泛型指针的开始和结束标志。逆向泛型指针的加操作是使它向rend方向移动，减操作向rbegin移动。它的定义方法如下：,vector:reverse_iterator指针名;reverse_iterator是逆向泛型指针关键字。第1.4.4节所介绍的算法，显然也都适合向量。使用方法可参考2.6节。下面的例子演示先使用使用正向范型指针，来回遍历一次输出容器内容，再使用copy算法正向输出一次。然后换一行，使用逆向指针来回输出，再使用copy逆向输出。即：1.14.43.32.22.23.34.41.11.14.43.32.22.23.34.41.11.14.43.32.22.23.34.41.1【例7.9】演示范型指针和copy函数的例子。#include#include#includeusingnamespacestd;voidmain(),doublea=1.1,4.4,3.3,2.2;vectorva(a,a+4),vb(4);typedefvector:iteratoriterator;iteratorfirst=va.begin();for(first;firstva.begin()-1;first-)cout(cout,);cout:reverse_iteratorreverse_iterator;,reverse_iteratorlast=va.rbegin();for(last;lastva.rbegin()-1;last-)cout(cout,);,7.2.3向量的数据类型向量除了可以使用基本数据类型之外，还可以使用构造类型(包括容器)，只要符合构成法则即可。本节再举几个简单的例子。【例7.10】演示向量使用范型算法的例子。#include#include#include#includeusingnamespacestd;voidmain()doublea=1.1,4.4,3.3,2.2;vectorva(a,a+4),vb(4);,copy(va.begin(),va.end(),ostream_iterator(cout,);cout(cout,);cout(cout,);cout();copy(va.begin(),va.end(),ostream_iterator(cout,);,cout(cout,);cout(cout,);cout(cout,);coutendl;cout=capacity()=size()empty()：当前容器为空时，返回true值。,2.访问向量中对象的方法front()：返回向量中的第1个对象。back()：返回向量中的最后一个对象。operator(size_type,n)：返回容器中的第n+1个对象(下标为n的向量元素)。【例7.12】演示访问容器容量信息及对象实例。#include#include#include#includeusingnamespacestd;voidmain()vectora(10),b(10);/产生向量a，元素内容均为0couta.empty()“,”sizeof(a)“,”;/内容不空时/输出0，sizeof(a)为16,for(chari=a,j=0;j(cout,);/输出向量a的内容cout(cout,);/逆向输出b,cout();/降幂排序copy(b.begin(),b.end(),ostream_iterator(cout,);/输出向量b的内容语句a.operator(5)是输出第6个元素内容，即a5(内容为f)。sizeofa输出16。这说明编译系统为向量vect分配16个字节。程序输出结果如下：0,16,4294967295,10,10abcdefghijabcdefghijjihgfedcbaa,j,fjihgfedcba,3.在向量中插入对象的方法(1)push_back(constTvoidmain()charst11=abcdefghij;vectora(st,st+10);/不复制字符串数组的结束标志0for(intj=0;j10;j+)/输出向量内容abcdefghijcoutaj;coutendla.capacity(),“a.size()endl;/输出10,10a.pop_back();/删除元素j,a.push_back(W);a.push_back(P);/在尾部增加/元素W和Pfor(j=0;ja.size();j+)/输出现在内/容abcdefghWPcoutaj;coutendla.capacity(),“a.size(),;/输出20,11a.clear();/删除所有元素couta.empty()endl;/输出1程序输出结果如下：abcdefghij10,10abcdefghiWP20,11,1,【例7.14】演示使用泛型指针进行插入和删除实例。#include#include#includeusingnamespacestd;voidmain()charst11=abcdefghij;vectora(st,st+10);/不复制字符串数组的结束标志0vector:iteratorp;/定义泛型指针pp=a.begin();/p指向第1个元素的地址a.insert(p+3,X);/a3=X/输出向量a的内容为abcXdefghijcopy(a.begin(),a.end(),ostream_iterator(cout,);,cout(cout,);cout(cout,);coutendl;a.erase(p+5,p+10);/删除a5a10的元素,/输出为AefgAdefghijcopy(a.begin(),a.end(),ostream_iterator(cout,);cout(cout,);coutendl;/输出为AefgAdefhij程序输出结果如下：abcXdefghijAAAabcXdefghijAefgAAabcXdefghijAefgAdefghijAefgAdefhij,【例7.15】演示双向访问的例子。#include#includeusingnamespacestd;voidmain()charst11=abcdefghij;vectora(st,st+10);vector:iteratorp=a.begin();/定义正向泛型/指针并初始化vector:reverse_iteratorps;/定义逆向泛型指针for(p=a.begin();p!=a.end();+p)/正向访问cout*p;/输出abcdefghijcoutendl;,for(p=a.end()-1;p!=a.begin()-1;-p)/使用正向泛型/指针逆向访问cout*p;/输出jihgfedcbacoutendl;for(ps=a.rbegin();ps!=a.rend();+ps)/使用逆向泛型/指针正向访问,使用+运算cout*ps;/输出jihgfedcbacoutendl;for(-ps;ps!=a.rbegin()-1;-ps)/使用逆向泛型/指针逆向访问,使用-运算cout*ps;/输出abcdefghij,使用typedef可使定义泛型指针的手续简单易懂。例如使用如下语句typedefvector:iteratoriterator;定义标识符iterator，在程序中就可使用iterator定义泛型指针。例如，可用如下方式定义泛型指针p：iteratorp;,7.3出圈游戏假