程序设计实习第二十讲标准模板库stl i

《程序设计实习》课程(C++ProgrammingPractice)程序设计实习第二十讲标准模板库STLI主讲教师：田永鸿[e-mail]://idm.pku.edu.cn/jiaoxue-CPP/cpp08.htm2008年5月19日北京大学《程序设计实习》课程2课堂问题1.下列代码是否存在错误，若存在，该如何改正？templateclassT,intsizeclassCTemp{friendvoidmyClassT::func();private:Telements[size];public:CTemp(Targ);};templateclassTvoidmyClassT::func(){CTempT,50a(10);inti;for(i=0;i50;i++){couta.elements[i]endl;}return;}myClassintobj;obj.func();北京大学《程序设计实习》课程3课堂问题2.有如下类模板定义templateclassT1,classT2,intsizeclassCTemp{friendmyClassAT1;friendmyClassBT2;private:T1elements[size];public:CTemp(Targ){};};则myClassAint、myClassBdouble、myClassAdouble、myClassAchar都是CTempint,double,50的友员类北京大学《程序设计实习》课程4课堂问题3.找出下列代码中的错误之处，并解释a(10)（或b(8.9)、…的含义）templateclassT,intsizeclassCTemp{friendvoidfunc(int);private:Telements[size];public:CTemp(Targ){};};voidfunc(intsize){CTempint,50a(10);CTempdouble,50b(8.9);CTempint,sizec(10);CTempdouble,sized(10);inti;for(i=0;i50;i++){couta.elements[i]“”b.elements[i]endl;}return;}北京大学《程序设计实习》课程5提纲1.引言2.STL中的基本概念3.容器概述4.迭代器5.算法简介6.顺序容器北京大学《程序设计实习》课程6概论C++语言的核心优势之一就是便于软件的重用C++中有两个方面体现重用：1.面向对象的思想：继承和多态，标准类库2.泛型程序设计(genericprogramming)的思想：模板机制，以及标准模板库STL北京大学《程序设计实习》课程7泛型程序设计泛型程序设计，简单地说就是使用模板的程序设计法。将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。标准模板库(StandardTemplateLibrary)就是一些常用数据结构和算法的模板的集合。主要由AlexStepanov开发，于1998年被添加进C++标准有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。北京大学《程序设计实习》课程8STL中的几个基本概念容器：可容纳各种数据类型的数据结构。迭代器：可依次存取容器中元素的东西算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如，数组intarray[100]就是个容器，而int*类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法北京大学《程序设计实习》课程9容器概述可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。容器分为三大类：1)顺序容器vector：后部插入/删除，直接访问deque：前/后部插入/删除，直接访问list：双向链表，任意位置插入/删除2)关联容器set：快速查找，无重复元素multiset：快速查找，可有重复元素map：一对一映射，无重复元素，基于关键字查找multimap：一对一映射，可有重复元素，基于关键字查找前2者合称为第一类容器3)容器适配器stack：LIFOqueue：FIFOpriority_queue：优先级高的元素先出北京大学《程序设计实习》课程10容器概述对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现==和运算符。北京大学《程序设计实习》课程11顺序容器简介1)vector头文件vector实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。2)deque头文件deque也是个动态数组，随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。3)list头文件list双向链表，在任何位置增删元素都能在常数时间完成。不支持随机存取。上述三种容器称为顺序容器，是因为元素的插入位置同元素的值无关。北京大学《程序设计实习》课程12关联容器简介关联式容器内的元素是排序的，插入任何元素，都按相应的排序准则来确定其位置。关联式容器的特点是在查找时具有非常好的性能。1)set/multiset:头文件setset即集合。set中不允许相同元素，multiset中允许存在相同的元素。2)map/multimap:头文件mapmap与set的不同在于map中存放的是成对的key/value。并根据key对元素进行排序，可快速地根据key来检索元素map同multimap的不同在于是否允许多个元素有相同的key值。上述4种容器通常以平衡二叉树方式实现，插入和检索的时间都是O(logN)北京大学《程序设计实习》课程13容器适配器简介1)stack:头文件stack栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则2)queue:头文件queue队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。3）priority_queue:头文件queue优先级队列。最高优先级元素总是第一个出列北京大学《程序设计实习》课程14容器的共有成员函数1)所有标准库容器共有的成员函数：相当于按词典顺序比较两个容器大小的运算符：=,,=,,=,==,!=empty:判断容器中是否有元素max_size:容器中最多能装多少元素size:容器中元素个数swap:交换两个容器的内容比较两个容器的例子：#includevector#includeiostreamclassA{private:intn;public:friendbooloperator(constA&,constA&);A(intn_){n=n_;}};booloperator(constA&o1,constA&o2){returno1.no2.n;}intmain(){std::vectorAv1;std::vectorAv2;v1.push_back(A(5));v1.push_back(A(1));v2.push_back(A(1));v2.push_back(A(2));v2.push_back(A(3));std::cout(v1v2);return0;}输出：0•若两容器长度相同、所有元素相等，则两个容器就相等，否则为不等。•若两容器长度不同，但较短容器中所有元素都等于较长容器中对应的元素，则较短容器小于另一个容器•若两个容器均不是对方的子序列，则取决于所比较的第一个不等的元素北京大学《程序设计实习》课程16容器的成员函数2)只在第一类容器中的函数：begin返回指向容器中第一个元素的迭代器end返回指向容器中最后一个元素后面的位置的迭代器rbegin返回指向容器中最后一个元素的迭代器rend返回指向容器中第一个元素前面的位置的迭代器erase从容器中删除一个或几个元素clear从容器中删除所有元素HeadTailbeginrbeginrendend北京大学《程序设计实习》课程17迭代器用于指向第一类容器中的元素。有const和非const两种。通过迭代器可以读取它指向的元素，通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。定义一个容器类的迭代器的方法可以是：容器类名::iterator变量名;或：容器类名::const_iterator变量名;访问一个迭代器指向的元素：*迭代器变量名北京大学《程序设计实习》课程18迭代器迭代器上可以执行++操作,以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的，就好像使用NULL或未初始化的指针一样。例如：#includevector#includeiostreamusingnamespacestd;intmain(){vectorintv;//一个存放int元素的向量，一开始里面没有元素v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vectorint::const_iteratori;//常量迭代器for(i=v.begin();i!=v.end();i++)cout*i,;coutendl;vectorint::reverse_iteratorr;//反向迭代器for(r=v.rbegin();r!=v.rend();r++)cout*r,;coutendl;vectorint::iteratorj;//非常量迭代器for(j=v.begin();j!=v.end();j++)*j=100;for(i=v.begin();i!=v.end();i++)cout*i,;}输出结果：1,2,3,4,4,3,2,1,100,100,100,100,北京大学《程序设计实习》课程21迭代器不同容器上支持的迭代器功能强弱有所不同。容器的迭代器的功能强弱，决定了该容器是否支持STL中的某种算法。例1：只有第一类容器能用迭代器遍历。例2：排序算法需要通过随机迭代器来访问容器中的元素，那么有的容器就不支持排序算法。北京大学《程序设计实习》课程22STL中的迭代器STL中的迭代器按功能由弱到强分为5种：1.输入：Inputiterators提供对数据的只读访问。1.输出：Outputiterators提供对数据的只写访问2.正向：Forwarditerators提供读写操作，并能一次一个地向前推进迭代器。3.双向：Bidirectionaliterators提供读写操作，并能一次一个地向前和向后移动。4.随机访问：Randomaccessiterators提供读写操作，并能在数据中随机移动。编号大的迭代器拥有编号小的迭代器的所有功能，能当作编号小的迭代器使用。北京大学《程序设计实习》课程23不同迭代器所能进行的操作(功能）所有迭代器：++p,p++输入迭代器：*p,p=p1,p==p1,p!=p1输出迭代器：*p,p=p1正向迭代器：上面全部双向迭代器：上面全部，--p,p--,随机访问