STL讲义学习教程.pptx

《STL讲义学习教程.pptx》由会员分享，可在线阅读，更多相关《STL讲义学习教程.pptx（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、提纲1.概论2.模板机制的介绍3.STL中的基本概念4.容器概述5.迭代器6.算法简介第1页/共86页概论C+语言的核心优势之一就是便于软件的重用C+中有两个方面体现重用：1.面向对象的思想：继承和多态，标准类库2.泛型程序设计(genericprogramming)的思想：模板机制，以及标准模板库STL第2页/共86页泛型程序设计泛型程序设计，简单地说就是使用模板的程序设计法。将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。标准模板库(StandardTempla

2、teLibrary)就是一些常用数据结构和算法的模板的集合。主要由AlexStepanov开发，于1998年被添加进C+标准有了STL，不必再从头开始编写繁多的标准数据结构和算法，并且一样可获得非常高的性能。第3页/共86页模板引子1.假如设计一个求两参数最大值的函数，在实践中我们可能需要定义四个函数：intmax(inta,intb)return(ab)?a,b;longmax(longa,longb)return(ab)?a,b;doublemax(doublea,doubleb)return(ab)?a,b;charmax(chara,charb)return(ab)?a,b;2.这些函

3、数几乎相同，唯一的区别就是形参类型不同3.需要事先知道有哪些类型会使用这些函数，对于未知类型这些函数不起作用第4页/共86页模板的概念o所谓模板是一种使用无类型参数来产生一系列函数或类的机制。o若一个程序的功能是对某种特定的数据类型进行处理，则可以将所处理的数据类型说明为参数，以便在其他数据类型的情况下使用，这就是模板的由来。o模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。o通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而避免需要为每一种数据类型产生一个单独的类或函数。第5页/共86页模板分类函数模板(functiontemplate)是独立于类

4、型的函数可产生函数的特定版本类模板(classtemplate)跟类相关的模板，如vector可产生类对特定类型的版本，如vector6第6页/共86页求最大值模板函数实现1.求两个数最大值，使用模板templateTmax(Ta,Tb)return(ab)?a,b;2.template（模板函数形参表）/函数定义体7第7页/共86页模板工作方式函数模板只是说明，不能直接执行，需要实例化为模板函数后才能执行在说明了一个函数模板后，当编译系统发现有一个对应的函数调用时，将根据实参中的类型来确认是否匹配函数模板中对应的形参，然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同，它称之

5、为模板函数8第8页/共86页#includetemplateTmin(Ta,intn)inti;Tminv=a0;for(i=1;i ai)minv=ai;returnminv;编写一个对具有n个元素的数组a 求最小值的程序，要求将求最小值的函数设计成函数模板。void main()int a=1,3,0,2,7,6,4,5,2;double b=1.2,-3.4,6.8,9,8;cout”a数组的最小值为：”min(a,9)endl;cout”b数组的最小值为：”min(b,4)endl;此程序的运行结果为：a数组的最小值为：0b数组的最小值为：第9页/共86页函数模板与类模板使用时有何不同

6、?函数模板使用时不提供类型参数比如:直接调用min(a,9);类模板使用时要求提供类型参数比如:vectorv,其中int就是类型参数第10页/共86页模板优缺点函数模板方法克服了C语言解决上述问题时用大量不同函数名表示相似功能的坏习惯克服了宏定义不能进行参数类型检查的弊端克服了C+函数重载用相同函数名字重写几个函数的繁琐缺点，调试比较困难一般先写一个特殊版本的函数运行正确后，改成模板函数11第11页/共86页STL中的几个基本概念容器：可容纳各种数据类型的多元素数据结构。迭代器：可依次存取容器中元素的东西(指针？下标?)算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个

7、vector中的数据进行排序，用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如，数组intarray100就是个容器，而int*类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法第12页/共86页容器概述可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。容器分为三大类：1)顺序容器vector：后部插入/删除，直接访问deque：前/后部插入/删除，直接访问list：双向链表，任意位置插入/删除2)关联容器set：快速查找，无重复元素multiset：快速查找，可有重

8、复元素map：一对一映射，无重复元素，基于关键字查找multimap：一对一映射，可有重复元素，基于关键字查找前2者合称为第一类容器3)容器适配器stack：LIFOqueue：FIFOpriority_queue：优先级高的元素先出第13页/共86页容器概述对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现=和运算符。第14页/共86页顺序容器简介1)vector头文件实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。2)deque头文件也是个动态数组，随机存取任

9、何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。3)list头文件双向链表，在任何位置增删元素都能在常数时间完成。不支持随机存取。上述三种容器称为顺序容器，是因为元素的插入位置同元素的值无关。第15页/共86页关联容器简介关联式容器内的元素是排序的，插入任何元素，都按相应的排序准则来确定其位置。关联式容器的特点是在查找时具有非常好的性能。1)set/multiset:头文件set即集合。set中不允许相同元素，multiset中允许存在相同的元素。2)map/multimap:头文件map与set的不同在于map中存放的是成对的key/value。并根据key

10、对元素进行排序，可快速地根据key来检索元素map同multimap的不同在于是否允许多个元素有相同的key值。上述4种容器通常以平衡二叉树方式实现，插入和检索的时间都是O(logN)第16页/共86页容器适配器简介1)stack:头文件栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则2)queue:头文件队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。3）priority_queue:头文件优先级队列。最高优先级元素总是第一个出列第17页/共86页容器的共有成员函数1)所有标准库容器共有的成员函数：相当于按词

11、典顺序比较两个容器大小的运算符：=,=,=,!=empty:判断容器中是否有元素max_size:容器中最多能装多少元素size:容器中元素个数swap:交换两个容器的内容第18页/共86页比较两个容器的例子19比较两个容器的例子：#include#include int main()std:vector v1;std:vector v2;v1.push_back(5);v1.push_back(1);v2.push_back(1);v2.push_back(2);v2.push_back(3);std:cout (v1,pre and post /increment,and equality

12、 testing operators /come hereprivate:ChainNode*current;第23页/共86页ConstructorChainIterator(ChainNode*startNode=0)current=startNode;第24页/共86页Dereferencing OperatorsT&operator*()const return current-data;T&operator-()const return¤t-data;第25页/共86页IncrementChainIterator&operator+()/preincrement curr

13、ent=current-link;return*this;ChainIterator&operator+(int)/postincrement ChainIterator old=*this;current=current-link;return old;第26页/共86页Equality Testingbool operator!=(const ChainIterator right)const return current!=right.current;bool operator=(const ChainIterator right)const return current=right.c

14、urrent;第27页/共86页Using An IteratorChain:iterator xHere=x.Begin();Chain:iterator xEnd=x.End();for(;xHere!=xEnd;xHere+)examine(*xHere);vsfor(int i=0;i x.Size();i+)examine(x.Get(i);第28页/共86页迭代器用于指向第一类容器中的元素。有const和非const两种。通过迭代器可以读取它指向的元素，通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。定义一个容器类的迭代器的方法可以是：容器类名:iterator变

15、量名;或：容器类名:const_iterator变量名;访问一个迭代器指向的元素：*迭代器变量名第29页/共86页迭代器迭代器上可以执行+操作,以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的，就好像使用NULL或未初始化的指针一样。第30页/共86页例如：#include#include using namespace std;int main()vector v;/一个存放int元素的向量，一开始里面没有元素v.push_back(1);v.push_back(2);v

16、.push_back(3);v.push_back(4);vector:const_iterator i;/常量迭代器for(i=v.begin();i!=v.end();i+)cout *i ,;cout endl;第31页/共86页vector:reverse_iterator r;/反向迭代器for(r=v.rbegin();r!=v.rend();r+)cout *r ,;cout endl;vector:iterator j;/非常量迭代器for(j=v.begin();j!=v.end();j+)*j=100;for(i=v.begin();i!=v.end();i+)cout *

17、i ,;输出结果：1,2,3,4,4,3,2,1,100,100,100,100,第32页/共86页迭代器不同容器上支持的迭代器功能强弱有所不同。容器的迭代器的功能强弱，决定了该容器是否支持STL中的某种算法。例1：只有第一类容器能用迭代器遍历。例2：排序算法需要通过随机迭代器来访问容器中的元素，那么有的容器就不支持排序算法。第33页/共86页STL 中的迭代器STL中的迭代器按功能由弱到强分为5种：1.输入：Inputiterators提供对数据的只读访问。1.输出：Outputiterators提供对数据的只写访问2.正向：Forwarditerators提供读写操作，并能一次一个地向前推

18、进迭代器。3.双向：Bidirectionaliterators提供读写操作，并能一次一个地向前和向后移动。4.随机访问：Randomaccessiterators提供读写操作，并能在数据中随机移动。编号大的迭代器拥有编号小的迭代器的所有功能，能当作编号小的迭代器使用。第34页/共86页不同迭代器所能进行的操作(功能）所有迭代器：+p,p+输入迭代器：*p,p1=p,p=p1,p!=p1输出迭代器：*p,p=p1正向迭代器：上面全部双向迭代器：上面全部，-p,p-,随机访问迭代器：上面全部，以及：p+=i,p-=i,p+i：返回指向p后面的第i个元素的迭代器p-i：返回指向p前面的第i个元素的

19、迭代器pp1,pp1,p=p1第35页/共86页容器所支持的迭代器类别容器迭代器类别vector随机deque随机list双向set/multiset双向map/multimap双向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器第36页/共86页例如，vector的迭代器是随机迭代器，所以遍历 vector 可以有以下几种做法：vector v(100);vector:value_type i;/等效于写 int i；for(i=0;i ();i+)cout vi;vector:const_iterator ii;for(ii=();ii!=();ii+)

20、cout *ii;/间隔一个输出：ii=();while(ii ()cout *ii;ii=ii+2;第37页/共86页而 list 的迭代器是双向迭代器，所以以下代码可以：list v;list:const_iterator ii;for(ii=();ii！();ii+)cout *ii;以下代码则不行：for(ii=();ii ();ii+)cout *ii;/双向迭代器不支持 for(int i=0;i ();i+)cout vi;/双向迭代器不支持 第38页/共86页算法简介STL中提供能在各种容器中通用的算法，比如插入，删除，查找，排序等。大约有70种标准算法。算法就是一个个函数模板

21、。算法通过迭代器来操纵容器中的元素。许多算法需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面一个元素的迭代器。比如，排序和查找有的算法返回一个迭代器。比如find()算法，在容器中查找一个元素，并返回一个指向该元素的迭代器。算法可以处理容器，也可以处理C语言的数组第39页/共86页 算法分类变化序列算法copy,remove,fill,replace,random_shuffle,swap,.会改变容器非变化序列算法：adjacent-find,equal,mismatch,find,count,search,count_if,for_each,search_n以上函数模板都在中定义

22、此外还有其他算法，比如中的算法第40页/共86页算法示例：find()templateInItfind(InIt first,InIt last,const T&val);first和last这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点。这个区间是个左闭右开的区间，即区间的起点是位于查找范围之中的，而终点不是val参数是要查找的元素的值函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。如果找不到，则该迭代器指向查找区间终点。第41页/共86页#include#include#include using namespace std;main()int array1

23、0=10,20,30,40;vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:iterator p;p=find(v.begin(),v.end(),3);if(p!=()cout *p endl;第42页/共86页p=find(v.begin(),v.end(),9);if(p=()cout not found endl;p=find(v.begin()+1,v.end()-2,1);if(p!=()cout *p endl;int*pp=find(array,array+4,20);cou

24、t *pp endl;输出：3not found320第43页/共86页各种容器介绍第44页/共86页顺序容器除前述共同操作外，顺序容器还有以下共同操作：front():返回容器中第一个元素的引用back():返回容器中最后一个元素的引用push_back():在容器末尾增加新元素pop_back():删除容器末尾的元素比如，查list:front的help,得到的定义是：referencefront();const_referencefront()const;list有两个front函数第45页/共86页顺序容器reference和const_reference是typedef的类型对于li

25、st,list:reference实际上就是double&list:const_reference实际上就是constdouble&对于list,list:refrence实际上就是int&list:const_refreence实际上就是constint&第46页/共86页vector支持随机访问迭代器，所有STL算法都能对vector操作。随机访问时间为常数。在尾部添加速度很快，在中间插入慢。实际上就是动态数组。第47页/共86页例1：int main()int i;int a5=1,2,3,4,5;vector v(5);cout ()-()endl;for(i=0;i v.size()

26、;i+)vi=i;v.at(4)=100;for(i=0;i v.size();i+)cout vi ,;cout endl;vector v2(a,a+5);/构造函数v2.insert(v2.begin()+2,13);/在begin()+2位置插入 13for(i=0;i v2.size();i+)cout v2i ,;return 0;第48页/共86页输出：50,1,2,3,100,1,2,13,3,4,5,第49页/共86页例2：int main()const int SIZE=5;int aSIZE=1,2,3,4,5;vector v(a,a+5);/构造函数try v.at(

27、100)=7;catch(out_of_range e)cout ()endl;cout ()“,”()endl;();ostream_iterator output(cout,“*);copy(v.begin(),v.end(),output);();/等效于();第50页/共86页if()cout empty endl;(v.begin(),a,a+SIZE);copy(v.begin(),v.end(),output);/输出：invalid vector subscript1,52*3*4*5*empty1*2*3*4*5*第51页/共86页算法解释ostream_iteratorou

28、tput(cout,“*);定义了一个ostream_iterator对象，可以通过cout输出以*分隔的一个个整数copy(v.begin(),v.end(),output);导致v的内容在cout上输出copy函数模板(算法）：templateOutItcopy(InItfirst,InItlast,OutItx);本函数对每个在区间0,last-first)中的N执行一次*(x+N)=*(first+N)，返回x+N对于copy(v.begin(),v.end(),output);first和last的类型是vector:const_iteratoroutput的类型是ostream_i

29、terator第52页/共86页关于 ostream_iterator,istream_iterator的例子int main()istream_iterator inputInt(cin);int n1,n2;n1=*inputInt;/读入 n1inputInt+;n2=*inputInt;/读入 n2cout n1 ,n2 endl;ostream_iterator outputInt(cout);*outputInt=n1+n2;cout endl;int a5=1,2,3,4,5;copy(a,a+5,outputInt);/输出整个数组 return 0;第53页/共86页程序运行

30、后输入 78 90敲回车，则输出结果为：78,9016812345第54页/共86页list 容器在任何位置插入删除都是常数时间，不支持随机存取。除了具有所有顺序容器都有的成员函数以外，还支持8个成员函数：push_front:在前面插入pop_front:删除前面的元素sort:排序(list不支持STL的算法sort)remove:删除和指定值相等的所有元素unique:删除所有和前一个元素相同的元素merge:合并两个链表，并清空被合并的那个reverse:颠倒链表splice:在指定位置前面插入另一链表中的一个或多个元素,并在另一链表中删除被插入的元素第55页/共86页deque 容器

31、所有适用于vector的操作都适用于dequedeque还有push_front（将元素插入到前面）和pop_front(删除最前面的元素）操作第56页/共86页57关联容器set,multiset,map,multimap内部元素有序排列，新元素插入的位置取决于它的值，查找速度快map关联数组：元素通过键来存储和读取set大小可变的集合，支持通过键实现的快速读取multimap支持同一个键多次出现的map类型multiset支持同一个键多次出现的set类型与顺序容器的本质区别关联容器是通过键(key)存储和读取元素的而顺序容器则通过元素在容器中的位置顺序存储和访问元素。第57页/共86页58

32、关联容器除了各容器都有的函数外，还支持以下成员函数：设m表容器，k表键值m.find(k)：如果容器中存在键为k的元素，则返回指向该元素的迭代器。如果不存在，则返回end()值。m.lower_bound(k)：返回一个迭代器，指向键不小于k的第一个元素m.upper_bound(k)：返回一个迭代器，指向键大于k的第一个元素m.count(k)：返回m中k的出现次数插入元素用insert第58页/共86页59settemplateclassKey,classPred=less,classA=allocatorclassset插入set中已有的元素时，插入不成功。第59页/共86页multis

33、et定义：templateclassKey,classPred=less,classA=allocatorclassmultiset;第二个参数Pred是个函数对象Pred决定了multiset中的元素，“一个比另一个小”是怎么定义的，即Pred(x,y)如果返回值为true,则x比y小Pred的缺省值是lessless模板的定义：templatestructless:publicbinary_functionbooloperator()(constT&x,constT&y)returnxy;const;/less模板是靠来比较大小的第60页/共86页函数对象是个对象，但是用起来看上去象函数调

34、用，实际上也执行了函数调用 class CMyAverage public:double operator()(int a1,int a2,int a3)/重载()运算符return(double)(a1+a2+a3)/3;/重载()运算符时，参数可以是任意多个 CMyAverage Average;/函数对象 cout Average(3,2,3);/Average.operator(3,2,3)用起来看上去象函数调用输出 第61页/共86页multiset的用法classA.;multiseta;就等效于multisetA,lessa;由于less模板是用进行比较的，所以这都要求A的对象能

35、用比较，即适当重载了第62页/共86页/出错的例子：#include using namespace std;class A ;int main()multiset a;a.insert(A();/error return/编译出错是因为，插入元素时，multiset会将被插入元素和已有元素进行比较，以决定新元素的存放位置。本例中缺省地就是用less函数对象进行比较，然而less函数对象进行比较时，前提是A对象能用 进行比较。但本例中没有适当重载 第63页/共86页64pair模板pair模板类用来绑定两个对象为一个新的对象，该类型在头文件中定义。pair模板类支持如下操作：pairp1：创建

36、一个空的pair对象，它的两个元素分别是T1和T2类型，采用值初始化pairp1(v1,v2)：创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2make_pair(v1,v2)：以v1和v2值创建一个新的pair对象，其元素类型分别是v1和v2的类型p1p2字典次序：如果或者，则返回truep1=p2：如果两个pair对象的first和second成员依次相等，则这两个对象相等。：返回p中名为first的（公有）数据成员：返回p中名为second的（公有）数据成员第64页/共86页#include#include using

37、namespace std;int main()typedef setdouble,less double_set;const int SIZE=5;double aSIZE=2.1,4.2,9.5,2.1,3.7;double_set doubleSet(a,a+SIZE);ostream_iterator output(cout,);cout 1);copy(doubleSet.begin(),doubleSet.end(),output);cout endl;pair p;p=doubleSet.insert(9.5);if()cout 2)*()inserted endl;else c

38、out 2)*()not inserted endl;return 0;insert函数返回值是一个pair对象,其first是被插入元素的迭代器，second代表是否成功插入了第65页/共86页输出：2)9.5 not inserted第66页/共86页67multimaptemplateclassKey,classT,classPred=less,classA=allocatorclassmultimap.typedefpairvalue_type;.;/Key代表关键字multimap中的元素由组成，每个元素是一个pair对象。multimap中允许多个元素的关键字相同。元素按照关键字升

39、序排列，缺省情况下用less定义关键字的“小于”关系第67页/共86页68maptemplateclassKey,classT,classPred=less,classA=allocatorclassmap.typedefpairvalue_type;.;map中的元素关键字各不相同。元素按照关键字升序排列，缺省情况下用less定义“小于”第68页/共86页69map可以用pairskey访形式问map中的元素。pairs为map容器名，key为关键字的值。该表达式返回的是对关键值为key的元素的值的引用。如果没有关键字为key的元素，则会往pairs里插入一个关键字为key的元素，并返回其值

40、的引用如：mappairs;则pairs50=5;会修改pairs中关键字为50的元素，使其值变成5第69页/共86页#include#include using namespace std;ostream&operator(ostream&o,const pair&p)o (,);return o;int main()typedef mapint,double,less mmid;mmid pairs;cout 1)pairs.count(15)endl;pairs.insert(mmid:value_type(15,2.7);pairs.insert(make_pair(15,99.3);

41、/make_pair生成pair对象cout 2)pairs.count(15)endl;pairs.insert(mmid:value_type(20,9.3);第70页/共86页 mmid:iterator i;cout 3);for(i=();i!=pairs.end();i+)cout *i ,;cout endl;cout 4);int n=pairs40;/如果没有关键字为40的元素，则插入一个for(i=();i!=pairs.end();i+)cout *i ,;cout endl;cout 5);pairs15=6.28;/把关键字为15的元素值改成for(i=();i!=p

42、airs.end();i+)cout *i ,;return 0;第71页/共86页输出：1)02)13)(15,2.7),(20,9.3),4)(15,2.7),(20,9.3),(40,0),5)(15,6.28),(20,9.3),(40,0),第72页/共86页73思考题如何用程序用来统计一篇英文文章中单词出现的频率（为简单起见，假定依次从键盘输入该文章）#include#includeusingnamespacestd;intmain()mapwordCount;stringword;while(cinword)+wordCountword;for(map:iteratorit=()

43、;it!=();+it)coutWord:(*it).firsttCount:(*it).secondendl;return0;第73页/共86页74容器适配器:stack可用vector,list,deque来实现缺省情况下，用deque实现用vector和deque实现，比用list实现性能好templateclassT,classCont=dequeclassstack.;stack是后进先出的数据结构，只能插入、删除、访问栈顶的元素第74页/共86页75 容器适配器:stackstack上可以进行以下操作：push:插入元素pop:弹出元素top:返回栈顶元素的引用第75页/共86页7

44、6容器适配器:queue和stack基本类似，可以用list和deque实现，缺省情况下用deque实现templateclassT,classCont=dequeclassqueue;同样也有push,pop,top函数但是push发生在队尾，pop,top发生在队头，先进先出第76页/共86页77容器适配器:priority_queue和queue类似，可以用vector和deque实现，缺省情况下用vector实现。priority_queue通常用堆排序技术实现，保证最大的元素总是在最前面。即执行pop操作时，删除的是最大的元素，执行top操作时，返回的是最大元素的引用。默认的元素比较

45、器是less第77页/共86页#include#include using namespace std;int main()priority_queue priorities;priorities.push(3.2);priorities.push(9.8);priorities.push(5.4);while(!()cout ();();return 0;/输出结果：第78页/共86页79排序和查找算法Sorttemplatevoidsort(RanItfirst,RanItlast);findtemplateInItfind(InItfirst,InItlast,constT&val);b

46、inary_search折半查找，要求容器已经有序templateboolbinary_search(FwdItfirst,FwdItlast,constT&val);第79页/共86页int main()const int SIZE=10;int a1=2,8,1,50,3,100,8,9,10,2;vector v(a1,a1+SIZE);ostream_iterator output(cout,);vector:iterator location;location=find(v.begin(),v.end(),10);if(location!=()cout endl 1)location

47、-();();if(binary_search(v.begin(),v.end(),9)cout endl 3)9 found;else cout endl 3)9 not found;return 0;第80页/共86页输出：(无sort语句)1)82)33)9 not found输出：(有sort语句)1)82)33)9 found第81页/共86页82sortsort实际上是快速排序，时间复杂度O(n*log(n);平均性能最优。但是最坏的情况下，性能可能非常差。如果要保证“最坏情况下”的性能，那么可以使用stable_sortstable_sortstable_sort实际上是归并排序

48、（将两个已经排序的序列合并成一个序列），特点是能保持相等元素之间的先后次序在有足够存储空间的情况下，复杂度为n*log(n)，否则复杂度为n*log(n)*log(n)stable_sort用法和sort相同排序算法要求随机存取迭代器的支持，所以list不能使用排序算法，要使用list:sort第82页/共86页83sortpartial_sort:部分排序，直到前n个元素就位即可nth_element:排序，直到第n个元素就位，并保证比第n个元素小的元素都在第n个元素之前即可partition:改变元素次序，使符合某准则的元素放在前面第83页/共86页小结C+模板函数模板STL库各种容器迭代器算法84第84页/共86页STL学习资料很多资料的汇总网站85第85页/共86页感谢您的观看！第86页/共86页