C++实用教程[郑阿奇主编]16.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,C+实用教程郑阿奇主编16,16.1.1 迭代器的由来,在STL中，迭代器是一种“特殊”的指针，用来指定或引用容器中元素的位置,正是因为对不同容器的操作具有相同的实现代码，所以才会形成STL的算法器及迭代器以优化和简化算法代码。,16.1.2 迭代器的类型,STL提供了5种不同的迭代器：输入、输出、正向、双向和随机访问迭代器,（1）输入迭代器。它是一种单向迭代器，只可递增，不可回退,（2）输出迭代器。它是一种单向迭代器，只不过它是向容器中写入元素。,（3）正向迭代器。它是输入迭代器和输出迭代器功能的组合，其操作元素总是向前移动（即支持+操作），与输入迭代器或输出迭代器不同的是，它多次遍历的顺序都是相同的。,（4）双向迭代器。它常用于reserse（逆序）等操作，支持指针的+和操作。,（5）随机访问迭代器。它具有双向迭代器的所有功能，同时增加了直接访问容器中任何元素的功能，即可向前、向后跳过任意多个元素，以及用于对元素排序的关系运算等,16.2 容器类,容器是一个与数组类似的单元，可以存取若干元素,主要容器类有：deque（双端队列）、list（链表、列表）、queue（队列）、stack（栈）、vector（向量）、map（映像）、multimap（多重映像）、set（集合）和multiset（多重集合）,16.2.1 向量、链表和双端队列,1.模型概述,向量、链表和双端队列都可以看成是顺序存储的线性表，只是链表不像向量和双端队列那样具有随机访问的能力,2.deque、list和vector,template ,class vector,;,template ,class deque,;,template ,class list,;,一旦建立了容器类vector、list或deque实例化类对象，就可以通过对象进行下列常用操作,（1）元素的插入操作。用于元素插入操作的成员函数为insert、push_front和push_back,（2）元素的删除和清除操作。用于删除元素操作的成员函数有erase、pop_front和pop_ back，clear用于清除操作,（3）元素访问操作。容器类vector和deque除了提供下标运算符“”来引用指定位置的对象元素的内存空间外，还提供下列元素访问操作,（4）迭代器和空间大小属性操作。容器类vector、list和deque都提供下列有关迭代器和空间大小属性的常用操作,（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;,/演示操作,#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;,程序运行结果如下：,4.list示例,例Ex_List 链表容器类示例。,#include,#include/链表容器类头文件包含,#include/迭代器头文件包含,using namespace std;,/演示iterator操作,void show(list&v),if(v.empty()cout该链表为空！n;return;,list:iterator ip=v.begin();/定义指针,while(ip!=v.end(),cout*ip,t;ip+;,cout v;/使用向量容器来构造,/注意，vector的最后面是两个大于符号，它们之间一定要有空格,说明:,（1）ANSI/ISO C+类模板stack和deque中都有一个protected数据成员c，其定义如下：,protected:,Container c;,但在Visual C+2005中，该数据成员是公有的，因此可以在对象中通过c访问构造时指定的容器类模板的成员。对于Visual C+6.0需要通过派生才能使用该数据成员c。,（2）另外，类模板stack和deque还都重载了运算符=、=、STACK;,class CStack:public STACK,public:,void show()/遍历操作,if(empty()cout栈为空！n;return;,vector:iterator ip=c.begin();/定义指针,while(ip!=c.end(),cout*ip,t;ip+;,cout,class map;,一旦建立了容器类map的实例化对象，就可以通过实例化类对象进行下列常用操作,（1）元素的插入操作。需要说明的是，这里操作的元素是指“键”和“值”的对子，简称键值对。在容器类map中，用于元素插入操作的成员函数为insert,（2）元素的删除和清除操作。容器类map用于删除元素操作的成员函数是erase，用于清除操作的是clear,（3）元素访问操作。容器类map只提供下标运算符“”来引用指定位置元素的内存空间,（4）迭代器和空间大小属性操作。,（5）映像操作,另外，容器类map还重载了运算符=、=、STR2INT;/定义类型名以便后面使用,typedefSTR2INT:iterator POS;/定义类型名以便后面使用,/输出键值对,void showpair(POS pos),cout主键为：(*pos).first,t值为：(*pos).secondendl;,/遍历输出,void show(STR2INT&v),if(v.empty(),cout(*pEnd).first),swap(pFirst,pEnd);,for(p=pFirst;p!=pEnd;p+),showpair(p);,/显示某范围的键值对，演示lower_bound和upper_bound,void showl(STR2INT&v,string k1,string k2),POS pFirst,pEnd,p;,pFirst=v.lower_bound(k1);,pEnd=v.upper_bound(k2);,if(*pFirst).first (*pEnd).first),swap(pFirst,pEnd);,for(p=pFirst;p!=pEnd;p+),showpair(p);,int main(),STR2INT v;,/添加操作,v.insert(STR2INT:value_type(Zero,0);,v.insert(STR2INT:value_type(One,1);,v.insert(STR2INT:value_type(Two,2);,v.insert(STR2INT:value_type(Three,3);,vFour=4;vFive=5;,vSix=6;vSeven=7;,vEight=8;,show(v);,/删除操作,cout-endl;,int n=v.erase(Two);,cout共删除了 n 个元素！endl;,/查找操作,cout-endl;,POS pos=v.find(Six);,if(pos!=v.end()showpair(pos);,/显示某范围的键值对,cout-endl;,showu(v,Four,Eight);,cout-endl;,showl(v,Four,Eight);,cout-,class set;,例Ex_Set 集合容器类示例。,#pragma warning(disable:4786),#include,#include/映像容器类头文件包含,#include/迭代器头文件包含,#include/字符串类头文件包含,using namespace std;,typedefset 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),swap(pFirst,pEnd);,for(p=pFirst;p!=pEnd;p+),cout*pt;,cout(*pEnd),swap(pFirst,pEnd);,for(p=pFirst;p!=pEnd;p+),cout*pt;,coutendl;,int main(),STRSET v;,/添加操作,v.insert(Zero);v.insert(One);v.insert(Two);,v.insert(Three);v.insert(Four);v.insert(Five);,v.insert(Six);,show(v);,/删除操作,cout-endl;,int n=v.erase(Two);,cout共删除了 n 个元素！endl;,/查找操作,cout-endl;,POS pos=v.find(Six);,if(pos!=v.end()cout*posendl;,/显示某范围的键值对,cout-endl;,showu(v,Two,Five);,cout-endl;,showl(v,Two,Five);,cout-endl;,pair pp=v.equal_range(FIVE);,cout*(pp.first)endl;,cout*(pp.second)endl;,return 0;,程序运行结果如下：,16.3 算法,16.3.1 概述,STL算法部分主要由头文件、和组成。,16.3.2 copy和流迭代器,1.copy,函数模板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();,ostream_iterator out(cout,);,copy(arr,arr+10,out);,cout endl;,copy(v.begin(),v.end(),out);,cout,class,ostream_iterator,:,public iterator,public:,ostream_iterator(ostream_type,ostream_iterator(ostream_type,;,16.3.3 find,函数模板find用于查找，它的原型如下：,template,InIt find(InIt,first,InIt,last,const T&,value,);,template,InIt find_if(InIt,first,InIt,last,Predicate,pred,);,例Ex_Find find函数使用示例。,#include,#include,#include,#include,using namespace std;,typedef vector IntVector;,class USERDO,public:,bool operator()(int i)/运算符“()”重载函数,return (i5),;,int main(),ostream_iterator out(cout,);,int a=1,3,5,6,6,7,7,7,8,8,8,8;/整数数组a,const 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);/查找整数3,cout找到*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();/E,if(it!=v.end(),cout找到*it 的位置在：it-v.begin()endl;,start=it+1;,while(it!=v.end();,return 0;,程序运行结果如下：,16.3.4 sort,函数模板sort用于为指定序列排序，它的原型如下：,/sort,RanIt表示随机访问迭代器,template,void sort(RanIt,first,RanIt,last,);,template,void sort(RanIt,first,RanIt,last,BPred,pred,);,其功能是将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,bool less_second(const C2Pred&m1,const C2Pred&m2),return m1.second m2.second;/按second值从小到大排序,private:,int first;,int second;,;,int main(),vector vect;,int i;,for(i=0;i 5;i+),C2Pred ob(10-i,i*3);vect.push_back(ob);,for(i=0;i vect.size();i+)vecti.show();,cout按first值从小到大排序:endl;,sort(vect.begin(),vect.end();,for(i=0;i vect.size();i+)vecti.show();,cout按second值从小到大排序:endl;,sort(vect.begin(),vect.end(),less_second);,for(i=0;i vect.size();i+)vecti.show();,return 0;,程序运行结果如下：,16.4 综合应用实例,#include,#include,#include/链表类头文件包含,#include/迭代器头文件包含,#include,#include,#include,using namespace std;,class CStudent;,ostream,class CStudent,public:,CStudent(),CStudent(char*name,char*id,float s1,float s2,float s3);,void print(int n=-1);,char*GetName()return strName;,friend ostream,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)成绩3,setw(10)总分0)coutsetw(6)n;,coutsetw(20)strNamesetw(10)strID,setw(10)fScore0setw(10)fScore1setw(10)fScore2,setw(10)totalendl;,ostream&operatorprint(+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;,程序运行结果如下：,