第十一章 标准模板类库STL

11.1基本数据结构知识11.2标准模板类库STL简介11.3向量11.4链表类的使用11.5双端队列11.6栈与队列11.7集合第11章标准模板类库STLC++语言的标准模板类库STL(StandardTemplateLibrary)已经成为一个标准，它是一个基于模板的群性类库，包含群体类（链表、向量、栈、队列、集合、映象），算法(排序、查找)以及迭代子(iterator)。本章将着重介绍STL的使用。实现了数组和链表，它们属于线性群体。还有两种特殊的线性群体：栈和队列。Ele1……Ele2Elen入栈出栈栈顶栈底图栈的示意图栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。对栈顶位置的标记称为栈顶指针，对栈底位置的标记称为栈底指针。向栈顶添加元素称为“压入栈”(push)，删除栈顶元素称为“弹出栈”(pop)。栈中元素的添加和删除操作具有“后进先出”（LIFO）的特性。【11.1基本数据结构知识】有一种限定的线性数据群体叫双端队列，它类似于限定删除和插入操作都必须在两端进行的链表。队列是一种特殊的线性群体。队列只能向一端添加元素，从另一端删除元素的线性群体，可以添加元素的一端称队尾，可以删除元素的一端称队头。对队头位置的标记称为队头指针，对队尾位置的标记称为队尾指针。Ele1出队入队Ele2Elen……队头队尾非线性群体：集合和映射。集合由若干个元素组成，对于一个指定的元素，它或者属于该集合，或者不属于；可以对两个集合求交集和差等。映射则类似于字典的功能，如一个身份证号码可以映射为某个确定的人，图书馆中一本书的编号和这本书也是一个映射。向队尾添加元素称为“入队”，删除队头元素称为“出队”。队列中元素的添加和删除操作具有“先进先出”（FIFO）的特性。图队列的逻辑结构示意图1994年7月，STL正式成为标准C++库的一部分。STL中的群体类是基于模板的，它既包含线性群体类，也包含非线性群体类，其中主要有：vector(向量)list(链表)stack(栈)queue(队列)deque(双端队列)set(集合)map(映射)STL的迭代子可以看成是指针的推广，迭代子也可以是普通的指针。类型分类顺序访问：直接访问：顺序迭代子使用++、--等进行移动，但只能顺序访问群体类中的对象。直接访问迭代子则可以直接访问群体类中的某个特定对象。【11.2标准模板类库STL简介】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位置的对象iteratorerase(iteratorfirst,iteratorlast);//移走first到last之间的对象用法如下：begin返回指向该向量的第一个对象的迭代子。end返回一个指向向量末尾值的迭代子。insert和erase是向量类的插入和删除方法。【11.3向量】向量应用举例(一)//EXAMPLE11_1.CPP#includeiostream#includenumeric#includealgorithm#includevector#includeiteratorusingnamespacestd;voidmain(){说明一下copy和accumulate函数的用法：templateclassInIt,classOutItOutItcopy(InItfirst,InItlast,OutItx);//该函//数将从first到last之间的对象依次赋给位置x的对象，//同时x++。在本例中是赋给标准输出流。templateclassInIt,classTTaccumulate(InItfirst,InItlast,Tval);//在first//和last之间依次取得对象值，每次该值与val的和替代原val值，返回val。templateclassInIt,classT,classPredTaccumulate(InItfirst,InItlast,Tval,Predpr);//在first和last之间依次取得对象值，每次该值与val进行pr运算后得到的//新值(在例中用到multiplies,进行乘法运算)替代原val值,返回val。例11-1vectorintnMyVector1,//整型向量nMyVector2;//该向量类型的迭代子vectorint::iteratornItBegin,nItEnd;//该向量类型的输出流迭代子ostreamiteratorintnOutput(cout,″″);//对向量类型对象中的数据进行顺序赋值for(inti=1;i=10;i++){nMyVector1.pushback(i);}//将该向量类型对象中的数据输出到标准输出流，显示出来。copy(nMyVector1.begin(),nMyVector1.end(),nOutput);coutendl;//该向量类型的迭代子被赋值nItBegin=nMyVector1.begin();nItEnd=nMyVector1.end();（续）//用insert函数实现两个向量类型对象成员数据的复制nMyVector2.insert(nMyVector2.begin(),nMyVector1.begin(),nMyVector1.end());for(i=0;inMyVector2.size();i++){coutnMyVector2［i］″″;}coutendl;//用迭代子输出该向量类型对象的数据while(nItBegin!=nItEnd){cout*nItBegin″″;nItBegin++;}coutendl;//用标准算法得到整型向量对象中所有数据的和cout″ThesumofnMyVector1［i］is:″accumulate(nMyVector1.begin(),nMyVector1.end(),0.0f)endl;nItBegin=nMyVector1.begin();nItEnd=nMyVector1.end();（续）//用一个已经存在的向量对象初始化另一个向量对象vectorintnMyVector3(nItBegin,nItEnd);vectorintnMyVector4(nMyVector3);//输出两个新的向量对象copy(nMyVector3.begin(),nMyVector3.end(),nOutput);coutendl;copy(nMyVector4.begin(),nMyVector4.end(),nOutput);coutendl;}123456789101234567891012345678910ThesumofnMyVector1［i］is:551234567891012345678910（续）向量应用举例（二）//EXAMPLE11_2.CPP//程序开始#pragmawarning(disable:4786)//防止一个编译警告的出现,过长的标识符(例如变//量名字长度超过255个)将在debug(程序调试状态)下被截断，以下同#includeiostream#includenumeric#includealgorithm#includefunctional#includevector#includeiterator#includestringusingnamespacestd;/*声明使用std名称空间，这里名空间是ANSIC++为解决C/C++程序员经常遇到的命名冲突而采取的一个措施，名空间内的变量、函数与其他名空间内的同名变量或者函数无关，这样增加了程序员对变量和函数命名的灵活性。std是标准名空间。*/classPoint//Point类的声明及实现{private://声明私有数据成员例11-2intx;inty;public://声明对外接口Point(intxx=0,intyy=0)//带默认形参值的构造函数{x=xx;y=yy;}voiddisplay()//显示函数{cout″Point″″(″x″,″y″)″″″;}intgetx()const{returnx;}intgety()const{returny;}booloperator==(constPoint&point2)const;//用户自定义类型必须重载″==″和//″″运算符，因为STL中的模板类都要支持关系运算如″=″、″=″。booloperator(constPoint&point2)const;};boolPoint::operator==(constPoint&point2)const{if((x==point2.getx())&[KG-*4]&(y==point2.gety()))（续）returntrue;elsereturnfalse;}boolPoint::operator(constPoint&point2)const{if((getx()point2.getx())&[KG-*4]&(gety()point2.gety()))returntrue;elsereturnfalse;}voidmain(){vectorintnMyVector1,//整型向量nMyVector2;vectordoubledblMyVector1,//双精度型向量dblMyVector2;vectorcharcMyVector1,//字符型向量cMyVector2;vectorstringstrMyVector1,//字符串型向量strMyVector2;vectorPointptMyVector1,//Point型向量（续）ptMyVector2;//针对不同向量类型的迭代子vectorint::iteratornItBegin,nItEnd;vectordouble::iteratordblItBegin,dblItEnd;vectorchar::iteratorcItBegin,cItEnd;vectorstring::iteratorstrItBegin,strItEnd;vectorPoint::iteratorpt