C++实用教程[郑阿奇主编]16课件

第16章 标准模板库（STL）16.1 迭代器16.1.1 迭代器的由来n在STL中，迭代器是一种“特殊”的指针，用来指定或引用容器中元素的位置 n正是因为对不同容器的操作具有相同的实现代码，所以才会形成STL的算法器及迭代器以优化和简化算法代码。16.1.2 迭代器的类型nSTL提供了5种不同的迭代器：输入、输出、正向、双向和随机访问迭代器 n（1）输入迭代器。它是一种单向迭代器，只可递增，不可回退 n（2）输出迭代器。它是一种单向迭代器，只不过它是向容器中写入元素。n（3）正向迭代器。它是输入迭代器和输出迭代器功能的组合，其操作元素总是向前移动（即支持+操作），与输入迭代器或输出迭代器不同的是，它多次遍历的顺序都是相同的。n（4）双向迭代器。它常用于reserse（逆序）等操作，支持指针的+和操作。n（5）随机访问迭代器。它具有双向迭代器的所有功能，同时增加了直接访问容器中任何元素的功能，即可向前、向后跳过任意多个元素，以及用于对元素排序的关系运算等 16.2 容器类n容器是一个与数组类似的单元，可以存取若干元素 n主要容器类有：deque（双端队列）、list（链表、列表）、queue（队列）、stack（栈）、vector（向量）、map（映像）、multimap（多重映像）、set（集合）和multiset（多重集合）16.2.1 向量、链表和双端队列n1.模型概述向量、链表和双端队列都可以看成是顺序存储的线性表，只是链表不像向量和双端队列那样具有随机访问的能力 n2.deque、list和vectortemplate class T,class Allocator=template class T,class Allocator=allocator allocator class vector class vector;template class T,class Allocator=template class T,class Allocator=allocator allocator class deque class deque;template class T,class Allocator=template class T,class Allocator=allocator allocator class list class list;n一旦建立了容器类vector、list或deque实例化类对象，就可以通过对象进行下列常用操作 n（1）元素的插入操作。用于元素插入操作的成员函数为insert、push_front和push_back n（2）元素的删除和清除操作。用于删除元素操作的成员函数有erase、pop_front和pop_ back，clear用于清除操作 n（3）元素访问操作。容器类vector和deque除了提供下标运算符“”来引用指定位置的对象元素的内存空间外，还提供下列元素访问操作 n（4）迭代器和空间大小属性操作。容器类vector、list和deque都提供下列有关迭代器和空间大小属性的常用操作 n（5）链表操作。与容器类vector和deque不同的是，容器类list自身还有不同的常用操作，如反序、排序、合并等 例Ex_Vector 向量容器类示例#include#include/向量容器类头文件包含#include/迭代器头文件包含#include/算法器头文件包含using namespace std;/演示iterator操作void show(vector&v)if(v.empty()cout该向量容器为空！n;return;vector:iterator ip;/定义指针for(ip=v.begin();ipv.end();ip+)cout*ip,t;coutendl;/演示操作n#include n#include/向量容器类头文件包含n#include/迭代器头文件包含n#include/算法器头文件包含nusing namespace std;n/演示iterator操作nvoid show(vector&v)nnif(v.empty()nncout该向量容器为空！n;return;nnvector:iterator ip;/定义指针nfor(ip=v.begin();ipv.end();ip+)ncout*ip,t;ncoutendl;n程序运行结果如下：4.list示例n例Ex_List 链表容器类示例。n#include n#include/链表容器类头文件包含n#include/迭代器头文件包含nusing namespace std;n/演示iterator操作nvoid show(list&v)nnif(v.empty()cout该链表为空！n;return;nlist:iterator ip=v.begin();/定义指针nwhile(ip!=v.end()nncout*ip,t;ip+;nncoutendl;nnint main()nnlist v;nv.push_back(20);v.push_back(40);v.push_back(5);v.push_back(7);nlist:iterator ip=v.begin();nip=v.insert(ip,13);nv.insert(ip,-7);nshow(v);/输出所有结点元素nv.remove(-7);/移除-7结点nv.reverse();show(v);nv.sort();show(v);nlist l;nl.push_back(12);l.push_back(8);l.push_back(16);l.push_back(7);nv.splice(v.end(),l);nshow(v);show(l);nv.pop_back();v.pop_back();v.pop_back();v.pop_back();nshow(v);nl.push_back(1);l.push_back(8);l.push_back(16);nv.merge(l);nshow(v);show(l);nreturn 0;n程序运行结果如下：16.2.2 栈和队列n栈（stack）是一种“FILO”（先进后出）或“LIFO”（后进先出）的线性表，它只允许在表的一端进行插入和删除操作。而队列（queue）是一种“FIFO”（先进先出）的线性表，与栈刚好相反。在队列中，只允许在表的一端插入元素，而在另一端删除元素。n定义对象时，它们都可以有下列简单的形式：X v;X int,vector v;/使用向量容器来构造/注意，vector的最后面是两个大于符号，它们之间一定要有空格说明:n（1）ANSI/ISO C+类模板stack和deque中都有一个protected数据成员c，其定义如下：protected:Container c;但在Visual C+2005中，该数据成员是公有的，因此可以在对象中通过c访问构造时指定的容器类模板的成员。对于Visual C+6.0需要通过派生才能使用该数据成员c。n（2）另外，类模板stack和deque还都重载了运算符=、=、=，用于两个栈或两个队列之间的关系比较。例Ex_Stack 栈类模板示例。n#include n#include/栈模板头文件包含n#include/向量容器类头文件包含n#include/迭代器头文件包含nusing namespace std;ntypedef stackint,vector STACK;nclass CStack:public STACKnnpublic:nvoid show()/遍历操作nnif(empty()cout栈为空！n;return;nvector:iterator ip=c.begin();/定义指针nwhile(ip!=c.end()ncout*ip,t;ip+;ncoutendl;n/清栈操作nvoid clear()nwhile(!empty()pop();n;int main()CStack v;v.push(20);v.push(40);v.push(5);v.push(7);v.show();v.top()=8;v.show();v.pop();v.show();v.clear();v.show();return 0;程序运行结果如下：16.2.3 映像n1.概述n与map概念相同，关联容器类multimapmultimap支持的是多对一关系，即一个键对应于多个值。map和multimap都支持双向迭代器，可以实现多路遍历操作 n2.map容器类容器类map具有下列声明：template class Key,class T,class Compare=template class Key,class T,class Compare=less,less,class Allocator=class Allocator=allocatorpair allocatorpair class mapclass map;一旦建立了容器类map的实例化对象，就可以通过实例化类对象进行下列常用操作 n（1）元素的插入操作。需要说明的是，这里操作的元素是指“键”和“值”的对子，简称键值对。在容器类map中，用于元素插入操作的成员函数为insert n（2）元素的删除和清除操作。容器类map用于删除元素操作的成员函数是erase，用于清除操作的是clear n（3）元素访问操作。容器类map只提供下标运算符“”来引用指定位置元素的内存空间 n（4）迭代器和空间大小属性操作。n（5）映像操作 n另外，容器类map还重载了运算符=、=、=，用于两个映像之间的关系比较 例Ex_Map 映像容器类示例#pragma warning(disable:4786)/避免string使用中的警告出现#include#include/映像容器类头文件包含#include/迭代器头文件包含#include/字符串类头文件包含using namespace std;typedefmapstring,int,less STR2INT;/定义类型名以便后面使用typedefSTR2INT:iterator POS;/定义类型名以便后面使用/输出键值对void showpair(POS pos)cout主键为：(*pos).first,t值为：(*pos).secondendl;/遍历输出void show(STR2INT&v)if(v.empty()cout(*pEnd).first)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)nshowpair(p);nn/显示某范围的键值对，演示lower_bound和upper_boundnvoid showl(STR2INT&v,string k1,string k2)nnPOS pFirst,pEnd,p;npFirst=v.lower_bound(k1);npEnd=v.upper_bound(k2);nif(*pFirst).first (*pEnd).first)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)nshowpair(p);nnint main()nnSTR2INT v;n/添加操作nv.insert(STR2INT:value_type(Zero,0);nv.insert(STR2INT:value_type(One,1);nv.insert(STR2INT:value_type(Two,2);nv.insert(STR2INT:value_type(Three,3);nvFour=4;vFive=5;nvSix=6;vSeven=7;nvEight=8;nshow(v);n/删除操作ncout-endl;nint n=v.erase(Two);ncout共删除了 n 个元素！endl;n/查找操作ncout-endl;nPOS pos=v.find(Six);nif(pos!=v.end()showpair(pos);n/显示某范围的键值对ncout-endl;nshowu(v,Four,Eight);ncout-endl;nshowl(v,Four,Eight);ncout-endl;npair pp=v.equal_range(FIVE);nshowpair(pp.first);nshowpair(pp.second);nreturn 0;n程序运行结果如下：16.2.4 集合n容器类set具有下列声明：ntemplate class Key,class Compare=template class Key,class Compare=less,less,nclass Allocator=class Allocator=allocator allocator nclass set;class set;25可编辑 例Ex_Set 集合容器类示例。#pragma warning(disable:4786)#include#include/映像容器类头文件包含#include/迭代器头文件包含#include/字符串类头文件包含using namespace std;typedefsetstring,less STRSET;/定义类型以便后面使用typedefSTRSET:iteratorPOS;/定义类型以便后面使用/遍历输出void show(STRSET&v)if(v.empty()cout该映像为空！n;return;POS ip;/定义指针for(ip=v.begin();ip!=v.end();ip+)cout*ipt;cout(*pEnd)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)ncout*pt;ncout(*pEnd)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)ncout*pt;ncoutendl;nnint main()nnSTRSET v;n/添加操作nv.insert(Zero);v.insert(One);v.insert(Two);nv.insert(Three);v.insert(Four);v.insert(Five);nv.insert(Six);nshow(v);n/删除操作ncout-endl;nint n=v.erase(Two);ncout共删除了 n 个元素！endl;n/查找操作ncout-endl;nPOS pos=v.find(Six);nif(pos!=v.end()cout*posendl;n/显示某范围的键值对ncout-endl;nshowu(v,Two,Five);ncout-endl;nshowl(v,Two,Five);ncout-endl;npair pp=v.equal_range(FIVE);ncout*(pp.first)endl;ncout*(pp.second)endl;nreturn 0;n程序运行结果如下：16.3 算法n16.3.1 概述nSTL算法部分主要由头文件、和组成。n16.3.2 copy和流迭代器n1.copyn函数模板copy将序列中某个范围的元素复制到另一个序列中 例Ex_Copy copy函数使用示例#include#include#include#include using namespace std;typedef vector IntVector;int main()int arr10=2,3,7,8,4,11,5,9,1,13 ;IntVector v(8);copy(arr,arr+8,v.begin();copy(arr,arr+8,v.begin();ostream_iterator out(cout,);copy(arr,arr+10,out);copy(arr,arr+10,out);cout endl;copy(v.begin(),v.end(),out);copy(v.begin(),v.end(),out);cout endl;return 0;程序运行结果如下：2.流迭代器n输出流迭代器ostream_iterator是STL预定义的迭代器类模板，它具有下列定义：template class T,class charT=char,class traits=char_traits class ostream_iteratorostream_iterator:public iterator public:ostream_iterator(ostream_type&s);ostream_iterator(ostream_type&s,const charT*delimiter);16.3.3 findn函数模板find用于查找，它的原型如下：ntemplatetemplatenInIt find(InItInIt find(InIt first,InIt,InIt last,const T&const T&value););ntemplate template nInIt find_if(InItInIt find_if(InIt first,InIt,InIt last,PredicatePredicate pred););例Ex_Find find函数使用示例。#include#include#include#include using namespace std;typedef vector IntVector;class USERDOpublic:bool operator()(int i)/运算符“()”重载函数return (i5)&(i8);int main()ostream_iterator out(cout,);int a=1,3,5,6,6,7,7,7,8,8,8,8;/整数数组aconst int ANUM=sizeof(a)/sizeof(int);IntVector v(a,a+ANUM);/A：构造copy(v.begin(),v.end(),out);coutendl;IntVector:iterator it=find(v.begin(),v.end(),3);/查找整数3cout找到*it 的位置在：it-v.begin()endl;cout-endl;IntVector:iterator start=v.begin();do/B：循环找出所有小于7的数it=find_if(start,v.end(),bind2nd(less(),7);if(it!=v.end()cout找到*it 的位置在：it-v.begin()endl;start=it+1;while(it!=v.end();cout-endl;start=v.begin();do/C：循环找出所有大于7的数it=find_if(start,v.end(),bind2nd(greater(),7);if(it!=v.end()cout找到*it 的位置在：it-v.begin()endl;start=it+1;while(it!=v.end();cout-endl;start=v.begin();do/D：循环找出所有(5,8)的数it=find_if(start,v.end(),USERDO();/Eif(it!=v.end()cout找到*it 的位置在：it-v.begin()endl;start=it+1;while(it!=v.end();return 0;程序运行结果如下：16.3.4 sortn函数模板sort用于为指定序列排序，它的原型如下：n/sort,RanIt表示随机访问迭代器ntemplatetemplaten void sort(RanIt void sort(RanIt first,RanIt,RanIt last););ntemplatetemplaten void sort(RanIt void sort(RanIt first,RanIt,RanIt last,BPred,BPred pred););n其功能是将first,last之间的序列按从小到大的升序进行排序 例Ex_Sort sort函数使用示例#include#include#include#include using namespace std;class C2Pred public:C2Pred(int a,int b):first(a),second(b)void show()cout(first,second)endl;bool operator (const C2Pred&m)const return first m.first;/按first值从小到大排序friend friend bool less_second(const C2Pred&m1,const C2Pred&m2)return m1.second m2.second;/按second值从小到大排序private:int first;int second;nint main()n nvector vect;nint i;nfor(i=0;i 5;i+)n C2Pred ob(10-i,i*3);vect.push_back(ob);nfor(i=0;i vect.size();i+)vecti.show();ncout按first值从小到大排序:endl;nsort(vect.begin(),vect.end();nfor(i=0;i vect.size();i+)vecti.show();ncout按second值从小到大排序:endl;nsort(vect.begin(),vect.end(),less_second);nfor(i=0;i vect.size();i+)vecti.show();nreturn 0;n程序运行结果如下：16.4 综合应用实例#include#include#include/链表类头文件包含#include/迭代器头文件包含#include#include#include using namespace std;class CStudent;ostream&operator(ostream&os,const CStudent&stu);class CStudentpublic:CStudent()CStudent(char*name,char*id,float s1,float s2,float s3);void print(int n=-1);char*GetName()return strName;friend ostream&operator(ostream&os,const CStudent&stu);bool operator (const CStudent&stu)const/重载 stu.total;/按total从高到低排序private:charstrName20;/姓名charstrID10;/学号floatfScore3;/三门课成绩floattotal;/总分;CStudent:CStudent(char*name,char*id,float s1,float s2,float s3)strncpy(strName,name,20);strncpy(strID,id,10);fScore0=s1;fScore1=s2;fScore2=s3;total=fScore0+fScore1+fScore2;void CStudent:print(int n)/n为序号，0)coutsetw(6)序号;coutsetw(20)姓名setw(10)学号setw(10)成绩1setw(10)成绩2setw(10)成绩3setw(10)总分0)coutsetw(6)n;coutsetw(20)strNamesetw(10)strIDsetw(10)fScore0setw(10)fScore1setw(10)fScore2setw(10)totalendl;ostream&operator(ostream&os,const CStudent&stu)os.write(stu.strName,20);os.write(stu.strID,10);os.write(char*)stu.fScore,sizeof(stu.fScore);os.write(char*)&stu.total,sizeof(float);return os;class CStuListpublic:voidAdd(CStudent stu);/添加记录intSeek(char*name,CStudent&stu);/按姓名查找,返回记录号，-1表示没有找到voidShowAll();/遍历列表显示voidSortToFile(char*filename);/按学生总成绩从高到低排序并写到文件中private:listtheBuf;/链表对象;void CStuList:Add(CStudent stu)theBuf.push_back(stu);int CStuList:Seek(char*name,CStudent&stu)/按姓名查找 int nRec=-1,i=0;list:iterator ip=theBuf.begin();/定义指针while(ip!=theBuf.end()stu=(CStudent)(*ip);if(0=strcmp(stu.GetName(),name)nRec=i;break;ip+;i+;return nRec;void CStuList:ShowAll()/遍历列表显示list:iterator ip=theBuf.begin();/定义指针int i=0;while(ip!=theBuf.end()ip-print(+i);ip+;void CStuList:SortToFile(char*filename)theBuf.sort();ShowAll();/将排序后的内容保存在文件中ofstream fout(filename);copy(theBuf.begin(),theBuf.end(),ostream_iterator(fout);int main()CStuList theStu;CStudent stu1(MaWenTao,99001,88,90,75.5);CStudent stu2(LiMing,99002,92,80,81.5);CStudent stu3(WangFang,99003,89,70,78);CStudent stu4(YangYang,99004,90,80,90);CStudent stu5(DingNing,99005,80,78,85);theStu.Add(stu1);theStu.Add(stu2);theStu.Add(stu3);theStu.Add(stu4);theStu.Add(stu5);theStu.ShowAll();CStudent stu;int nRec=theStu.Seek(LiMing,stu);if(nRec=0)cout找到的结果为：endl;stu.print(nRec+1);else cout没有找到！endl;cout执行SortToFile后的结果：endl;theStu.SortToFile(student.dat);return 0;程序运行结果如下：49可编辑