C++实用教程ppt课件.ppt

第16章标准模板库（STL）,16.1迭代器,1,16.1.1迭代器的由来,在STL中，迭代器是一种“特殊”的指针，用来指定或引用容器中元素的位置正是因为对不同容器的操作具有相同的实现代码，所以才会形成STL的算法器及迭代器以优化和简化算法代码。,2,16.1.2迭代器的类型,STL提供了5种不同的迭代器：输入、输出、正向、双向和随机访问迭代器,3,（1）输入迭代器。它是一种单向迭代器，只可递增，不可回退（2）输出迭代器。它是一种单向迭代器，只不过它是向容器中写入元素。（3）正向迭代器。它是输入迭代器和输出迭代器功能的组合，其操作元素总是向前移动（即支持+操作），与输入迭代器或输出迭代器不同的是，它多次遍历的顺序都是相同的。（4）双向迭代器。它常用于reserse（逆序）等操作，支持指针的+和操作。（5）随机访问迭代器。它具有双向迭代器的所有功能，同时增加了直接访问容器中任何元素的功能，即可向前、向后跳过任意多个元素，以及用于对元素排序的关系运算等,4,16.2容器类,容器是一个与数组类似的单元，可以存取若干元素主要容器类有：deque（双端队列）、list（链表、列表）、queue（队列）、stack（栈）、vector（向量）、map（映像）、multimap（多重映像）、set（集合）和multiset（多重集合）,5,16.2.1向量、链表和双端队列,1.模型概述向量、链表和双端队列都可以看成是顺序存储的线性表，只是链表不像向量和双端队列那样具有随机访问的能力2.deque、list和vectortemplateclassvector;templateclassdeque;templateclasslist;,6,一旦建立了容器类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自身还有不同的常用操作，如反序、排序、合并等,7,例Ex_Vector向量容器类示例,#include#include/向量容器类头文件包含#include/迭代器头文件包含#include/算法器头文件包含usingnamespacestd;/演示iterator操作voidshow(vector/演示操作,8,#include#include/向量容器类头文件包含#include/迭代器头文件包含#include/算法器头文件包含usingnamespacestd;/演示iterator操作voidshow(vector,9,程序运行结果如下：,10,4.list示例,例Ex_List链表容器类示例。#include#include/链表容器类头文件包含#include/迭代器头文件包含usingnamespacestd;/演示iterator操作voidshow(list,11,intmain()listv;v.push_back(20);v.push_back(40);v.push_back(5);v.push_back(7);list:iteratorip=v.begin();ip=v.insert(ip,13);v.insert(ip,-7);show(v);/输出所有结点元素v.remove(-7);/移除-7结点v.reverse();show(v);v.sort();show(v);listl;l.push_back(12);l.push_back(8);l.push_back(16);l.push_back(7);v.splice(v.end(),l);show(v);show(l);v.pop_back();v.pop_back();v.pop_back();v.pop_back();show(v);l.push_back(1);l.push_back(8);l.push_back(16);v.merge(l);show(v);show(l);return0;,12,程序运行结果如下：,13,16.2.2栈和队列,栈（stack）是一种“FILO”（先进后出）或“LIFO”（后进先出）的线性表，它只允许在表的一端进行插入和删除操作。而队列（queue）是一种“FIFO”（先进先出）的线性表，与栈刚好相反。在队列中，只允许在表的一端插入元素，而在另一端删除元素。定义对象时，它们都可以有下列简单的形式：Xv;Xv;/使用向量容器来构造/注意，vector的最后面是两个大于符号，它们之间一定要有空格,14,说明:,（1）ANSI/ISOC+类模板stack和deque中都有一个protected数据成员c，其定义如下：protected:Containerc;但在VisualC+2005中，该数据成员是公有的，因此可以在对象中通过c访问构造时指定的容器类模板的成员。对于VisualC+6.0需要通过派生才能使用该数据成员c。（2）另外，类模板stack和deque还都重载了运算符=、=、STACK;classCStack:publicSTACKpublic:voidshow()/遍历操作if(empty()cout:iteratorip=c.begin();/定义指针while(ip!=c.end()cout*ip,t;ip+;coutclassmap;,18,一旦建立了容器类map的实例化对象，就可以通过实例化类对象进行下列常用操作,（1）元素的插入操作。需要说明的是，这里操作的元素是指“键”和“值”的对子，简称键值对。在容器类map中，用于元素插入操作的成员函数为insert（2）元素的删除和清除操作。容器类map用于删除元素操作的成员函数是erase，用于清除操作的是clear（3）元素访问操作。容器类map只提供下标运算符“”来引用指定位置元素的内存空间（4）迭代器和空间大小属性操作。（5）映像操作另外，容器类map还重载了运算符=、=、STR2INT;/定义类型名以便后面使用typedefSTR2INT:iteratorPOS;/定义类型名以便后面使用/输出键值对voidshowpair(POSpos)cout主键为：(*pos).first,t值为：(*pos).secondSTRSET;/定义类型以便后面使用typedefSTRSET:iteratorPOS;/定义类型以便后面使用/遍历输出voidshow(STRSET/显示某范围的键值对，演示lower_bound和upper_bound,25,voidshowu(STRSET,26,intmain()STRSETv;/添加操作v.insert(Zero);v.insert(One);v.insert(Two);v.insert(Three);v.insert(Four);v.insert(Five);v.insert(Six);show(v);/删除操作coutpp=v.equal_range(FIVE);cout*(pp.first)endl;cout*(pp.second)endl;return0;,27,程序运行结果如下：,28,16.3算法,16.3.1概述STL算法部分主要由头文件、和组成。16.3.2copy和流迭代器1.copy函数模板copy将序列中某个范围的元素复制到另一个序列中,29,例Ex_Copycopy函数使用示例,#include#include#include#includeusingnamespacestd;typedefvectorIntVector;intmain()intarr10=2,3,7,8,4,11,5,9,1,13;IntVectorv(8);copy(arr,arr+8,v.begin();ostream_iteratorout(cout,);copy(arr,arr+10,out);coutendl;copy(v.begin(),v.end(),out);cout5),33,intmain()ostream_iteratorout(cout,);inta=1,3,5,6,6,7,7,7,8,8,8,8;/整数数组aconstintANUM=sizeof(a)/sizeof(int);IntVectorv(a,a+ANUM);/A：构造copy(v.begin(),v.end(),out);cout(),7);if(it!=v.end()cout找到*it的位置在：it-v.begin()endl;start=it+1;while(it!=v.end();cout-endl;start=v.begin();,34,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();return0;,35,程序运行结果如下：,36,16.3.4sort,函数模板sort用于为指定序列排序，它的原型如下：/sort,RanIt表示随机访问迭代器templatevoidsort(RanItfirst,RanItlast);templatevoidsort(RanItfirst,RanItlast,BPredpred);其功能是将first,last之间的序列按从小到大的升序进行排序,37,例Ex_Sortsort函数使用示例,#include#include#include#includeusingnamespacestd;classC2Predpublic:C2Pred(inta,intb):first(a),second(b)voidshow()cout(first,second)endl;booloperator(constC2Pred,38,intmain()vectorvect;inti;for(i=0;i5;i+)C2Predob(10-i,i*3);vect.push_back(ob);for(i=0;ivect.size();i+)vecti.show();cout按first值从小到大排序:endl;sort(vect.begin(),vect.end();for(i=0;ivect.size();i+)vecti.show();cout按second值从小到大排序:endl;sort(vect.begin(),vect.end(),less_second);for(i=0;ivect.size();i+)vecti.show();return0;,39,程序运行结果如下：,40,16.4综合应用实例,#include#include#include/链表类头文件包含#include/迭代器头文件包含#include#include#includeusingnamespacestd;classCStudent;ostream,41,classCStudentpublic:CStudent()CStudent(char*name,char*id,floats1,floats2,floats3);voidprint(intn=-1);char*GetName()returnstrName;friendostream,42,voidCStud