程序设计实习第九讲标准模板库(一)标准模板库STLC++语言的核心优势之一就是便于软件的重用C++中有两个方面体现重用:1.面向对象的思想:继承和多态,标准类库2.泛型程序设计(genericprogramming)的思想:模板机制,以及标准模板库STL泛型程序设计,简单地说就是使用模板的程序设计法。将一些常用的数据结构(比如链表,数组,二叉树)和算法(比如排序,查找)写成模板,以后则不论数据结构里放的是什么对象,算法针对什么样的对象,则都不必重新实现数据结构,重新编写算法。标准模板库(StandardTemplateLibrary)就是一些常用数据结构和算法的模板的集合。主要由AlexStepanov开发,于1998年被添加进C++标准有了STL,不必再写大多的标准数据结构和算法,并且可获得非常高的性能。STL中有几个基本的概念:容器:可容纳各种数据类型的数据结构。迭代器:可依次存取容器中元素的东西算法:用来操作容器中的元素的函数模板。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如,对于intarray[100];这个数组就是个容器,而int*类型的指针变量就可以作为迭代器,可以为这个容器编写一个排序的算法1容器概述可以用于存放各种类型的数据(基本类型的变量,对象等)的数据结构。容器分为三大类:1)顺序容器vector,deque,list2)关联容器set,multiset,map,multimap前2者合称为第一类容器3)容器适配器stack,queue,priority_queue对象被插入容器中时,被插入的是对象的一个复制品。许多算法,比如排序,查找,要求对容器中的元素进行比较,所以,放入容器的对象所属的类,还应该实现==和运算符。1.1顺序容器简介1)vector头文件vector实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。2)deque头文件deque也是个动态数组,随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能。3)list头文件list双向链表,在任何位置增删元素都能在常数时间完成。不支持随机存取。上述三种容器称为顺序容器,是因为元素的插入位置同元素的值无关。1.2关联容器简介关联式容器内的元素是排序的,插入任何元素,都按相应的排序准则来确定其位置。关联式容器的特点是在查找时具有非常好的性能。1)set/multiset:头文件setset即集合。set中不允许相同元素,multiset中允许存在相同的元素。2)map/multimap:头文件mapmap与set的不同在于map中存放的是成对的key/value。并根据key对元素进行排序,可快速地根据key来检索元素。map同multimap的不同在于是否允许相同key的元素。上述4中容器通常以平衡二叉树方式实现,插入和检索的时间都是O(logN)1.3容器适配器简介1)stack:头文件stack栈。是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则2)queue:头文件queue队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。3)priority_queue:头文件queue优先级队列。最高优先级元素总是第一个出列1.4容器的共有成员函数: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;}main(){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);}输出:02)只在第一类容器中的函数:begin返回指向容器中第一个元素的迭代器end返回指向容器中最后一个元素后面的位置的迭代器rbegin返回指向容器中最后一个元素的迭代器rend返回指向容器中第一个元素前面的位置的迭代器erase从容器中删除一个或几个元素clear从容器中删除所有元素2迭代器用于指向第一类容器中的元素。有const和非const两种。通过迭代器可以读取它指向的元素,通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。定义一个容器类的迭代器的方法可以是:容器类名::iterator变量名;或:容器类名::const_iterator变量名;访问一个迭代器指向的元素:*迭代器变量名迭代器上可以执行++操作,以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面,则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的,就好像使用NULL或未初始化的指针一样。例如:#includevector#includeiostreamusingnamespacestd;main(){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,不同容器上支持的迭代器功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持STL中的某种算法。比如,只有第一类容器能用迭代器遍历。排序算法需要通过随机迭代器来访问容器中的原素,那么有的容器就不支持排序算法。STL中的迭代器按功能由弱到强分为5种:1.输入:Inputiterators提供对数据的只读访问。1.输出:Outputiterators提供对数据的只写访问2.正向:Forwarditerators提供读写操作,并能一次一个地向前推进迭代器。3.双向:Bidirectionaliterators提供读写操作,并能一次一个地向前和向后移动。4.随机访问:Randomaccessiterators提供读写操作,并能在数据中随机移动。编号大的迭代器拥有编号小的迭代器的所有功能,能当作编号小的迭代器使用。不同迭代器所能进行的操作(功能):所有迭代器:++p,p++输入迭代器:*p,p=p1,p==p1,p!=p1输出迭代器:*p,p=p1正向迭代器:上面全部双向迭代器:上面全部,--p,p--,随机访问迭代器:上面全部,以及:p+=i,p-=i,p+i:返回指向p后面的第i个元素的迭代器p-i:返回指向p前面的第i个元素的迭代器p[i]:p后面的第i个元素的引用pp1,p=p1,pp1,p=p1容器迭代器类别vector随机deque随机list双向set/multiset双向map/multimap双向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器例如,vector的迭代器是随机迭代器,所以遍历vector可以有以下几种做法:vectorintv(100);vectorint::value_typei;//等效于写inti;(P687)for(i=0;iv.size();i++)coutv[i];vectorint::const_iteratorii;for(ii=v.begin();ii!=v.end();ii++)cout*ii;for(ii=v.begin();iiv.end();ii++)cout*ii;//间隔一个输出:ii=v.begin();while(iiv.end()){cout*ii;ii=ii+2;}而list的迭代器是双向迭代器,所以以下代码可以:listintv;listint::const_iteratorii;for(ii=v.begin();ii!=v.end();ii++)cout*ii;以下代码则不行:for(ii=v.begin();iiv.end();ii++)cout*ii;//双向迭代器不支持for(inti=0;iv.size();i++)coutv[i];//双向迭代器不支持[]3算法简介STL中提供能在各种容器中通用的算法,比如插入,删除,查找,排序等。大约有70种标准算法。算法就是一个个函数模板。算法通过迭代器来操纵容器中的元素。许多算法需要两个参数,一个是起始元素的迭代器,一个是终止元素的后面一个元素的迭代器。比如,排序和查找有的算法返回一个迭代器。比如find()算法,在容器中查找一个元素,并返回一个指向该元素的迭代器。算法可以处理容器,也可以处理C语言的数组1)变化序列算法:copy,remove,fill,replace,random_shuffle,swap,…..会改变容器2)非变化序列算法:adjacent-find,equal,mismatch,find,count,search,count_if,for_each,search_n以上函数模板都在algorithm中定义P692此外还有其他算法,比如numeric中的算法算法示例:find()templateclassInIt,classTInItfind(InItfirst,InItlast,constT&val);first和last这两个参数都是容器的迭代器,它们给出了容器中的查找区间起点和终点。这个区间是个左闭右开的区间,即区间的起点是位于查找范围之中的,而终点不是val参数是要查找的元素的值函数返回值是一个迭代器。如果找到,则该迭代器指向被找到的元素。如果找不到,则该迭代器指向查找区间终点。#includevector#includealgorithm#includeiostreamusingnamespacestd;main(){intarray[10]={10,20,30,40};vectorintv;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vectorint::iteratorp;p=find(v.begin(),v.end(),3);if(p!=v.end())cout*pendl;p=find(v.begin(),v.end(),9);if(p==v.end())coutnotfoun