C++模板&STL库教程PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,北京大学,程序设计实习,课程,C+,模板与,STL,库介绍,第,8,章,1,提纲,1.,概论,2.,模板机制的介绍,3.STL,中的基本概念,4.,容器概述,5.,迭代器,6.,算法简介,2,概论,C+,语言的核心优势之一就是便于软件的重用,C+,中有两个方面体现重用：,1.,面向对象的思想：继承和多态，标准类库,2.,泛型程序设计,(generic programming),的思想：模板机制，以及标准模板库,STL,这次课的重点,3,泛型程序设计,泛型程序设计，简单地说就是,使用模板的程序设计,法。,将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。,标准模板库,(Standard Template Library),就是一些常用数据结构和算法的模板的集合。主要由,Alex Stepanov,开发，于,1998,年被添加进,C+,标准,有了,STL,，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。,4,模板引子,1.,假如设计一个求两参数最大值的函数，在实践中我们可能需要定义四个函数：,int,max,(,int,a,int,b,),return,(,a,b,),?,a,b,;,long,max(,long,a,long,b)return(a b)?a,b;,double,max(,double,a,double,b)return(a b)?a,b;,char,max(,char,a,char,b)return(a b)?a,b;,2.这些函数几乎相同，唯一的区别就是形参类型不同,3.需要事先知道有哪些类型会使用这些函数，对于未知类型这些函数不起作用,5,int abs(int a),return a0?-a:a,；,double abs(double a),return a b)?a,b;,2.template/,模板声明格式,（模板函数形参表）,/,函数定义体,8,8,模板的概念,所谓模板是一种使用无类型参数来产生一系列,函数,或,类,的机制。,若一个程序的功能是对某种特定的数据类型进行处理，则可以将所处理的数据类型说明为参数，以便在其他数据类型的情况下使用，这就是,模板的由来,。,模板是以一种完全通用的方法来设计函数或类而,不必预先说明,将被使用的每个对象的类型。,通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而,避免,需要为每一种数据类型产生一个单独的类或函数。,9,注意：,模板并非通常意义上可直接使用的函数或类，它仅仅是对,一族,函数或类的描述，是参数化的函数和类。,模板是一种使用,无类型参数,来产生,一族,函数或类的机制。,10,模板分类,函数模板,(function template),是独立于类型的函数,可产生函数的特定版本,类模板,(class template),跟类相关的模板，如,vector,可产生类对特定类型的版本，如,vector,模板工作方式,函数模板只是说明，不能直接执行，需要实例化为模板函数后才能执行,在说明了一个函数模板后，当编译系统发现有一个对应的函数调用时，将根据实参中的类型来确认是否匹配函数模板中对应的形参，然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同，它称之为,模板函数,#include,template,T min(T a,T1 n),int i;,T minv=a0;,for(i=1;i ai),minv=ai;,return minv;,编写一个对具有,n,个元素的数组,a,求最小值的程序，要求将求最小值的函数设计成函数模板。,void main(),ina 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,数组的最小值为：,0,b,数组的最小值为：,-3.4,13,2,、模板的实例化,模板通过参数实例化可以构建具体的函数或类，称为,模板函数,和,模板类,。,14,模板实例化示意图,模 板,函数模板 类模板,模 板 类,模板函数,对 象,实例化,实例化,实例化,15,1.,函数模板的定义,定义格式如下：,template,返回值类型 函数名,(,参数表,),函数体,/,模板参数列表不能为空,8.2,函数模板,16,函数模板只是一种说明，并不是一个具体的函数，,C+,编译系统不会产生任何可执行代码。,当遇到具体的函数调用时，才根据调用处的具体参数类型，在参数实例化以后才生成相应的代码，此时的代码称为,模板函数,。,2.,函数模板的使用,17,函数模板的实例化是在编译按系统处理函数调用时由系统自动完成。,在调用函数模板时，系统首先确定模板参数所对应的具体类型，并依据该类型生成一个具体函数，,系统,实际上是,调用了这个具有确定参数类型的函数,。,模板函数,是函数模板的一个具体实例，是模板参数实例化后的一个可执行的具体函数，只处理一种确定的数据类型。,3.,模板函数的生成,18,#include,template,void myfunc(Type1 x,Type2 y),cout x y b)?a:b;,template,T max(T a,T b,T c),T t;,t=(ab)?a:b;,return(tc)?t:c;,char*max(char*a,char*b),return(strcmp(a,b)0)?a:b;,20,#include,main(),int x=10,y=20,max1;,double a=10.4,b=21.3,c=13.4,max2;,max1=max(x,y);,max2=max(a,b,c);,coutThe maxinum of x and y is:max1endl;,coutThe maxinum of a and b and c is:max2endl;,char*c1,*c2,*c3;,c1=aaaa;,c2=bbbb;,c3=max(c1,c2);,coutThe maxinum of c1 and c2 is:c3endl;,return 0;,21,8.3,类模板,如同函数模板一样，类模板是参数化的类，即用于实现数据类型参数化的类。,应用类模板可以使类中的,数据成员,、成员,函数的,参数,及成员函数的,返回值,，能根据模板参数匹配情况取任意数据类型。,22,1.,类模板的定义,template,class,类模板名,成员的声明；,定义格式如下：,23,模板类的成员函数必须是函数模板,。,类模板中的成员函数的定义，若放在类模板的定义之中，则与类的成员函数的定义方法相同；若在类模板之外定义，则成员函数的定义格式如下：,类模板成员函数的定义,template,返回值类型,类模板名,:,成员函数名,(,参数表,),成员函数体,24,当类模板在程序中被引用时，系统根据引用处的参数匹配情况,将,类模板中的,模板参数置换为确定的参数类型,，生成一个具体的类。,这种由类模板实例化生成的类称为,模板类,。,类模板必须先实例化为相应的模板类，并定义该模板类的对象以后才可以使用。,2.,类模板的使用,25,类模板实例化,=,模板类,的格式如下：,类模板实例化,类模板名,；,Square inta(15);,定义模板类的对象的格式,类模板名,对象名,(,实参表,),；,26,举 例,例,8-4,类模板的应用,例,8-5,含有成员函数的类模板定义,27,模板优缺点,函数模板方法克服了,C,语言解决上述问题时用大量不同函数名表示相似功能的坏习惯,克服了宏定义不能进行参数类型检查的弊端,克服了,C+,函数重载用相同函数名字重写几个函数的繁琐,缺点，调试比较困难,一般先写一个特殊版本的函数,运行正确后，改成模板函数,STL,中的几个基本概念,容器：可容纳各种数据类型的数据结构。,迭代器：可,依次存取,容器中元素的东西,算法：用来操作容器中的元素的,函数模板,。例如，,STL,用,sort(),来对一个,vector,中的数据进行排序，用,find(),来搜索一个,list,中的对象。,函数本身与他们操作的数据的结构和类型无关,，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。,比如，数组,int array100,就是个容器，而,int*,类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法,29,容器概述,可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。,容器分为三大类：,1),顺序容器,vector,：后部插入,/,删除，直接访问,deque,：前,/,后部插入,/,删除，直接访问,list,：双向链表，任意位置插入,/,删除,2),关联容器,set,：快速查找，无重复元素,multiset,：快速查找，可有重复元素,map,：一对一映射，无重复元素，基于关键字查找,multimap,：一对一映射，可有重复元素，基于关键字查找,前,2,者合称为第一类容器,3),容器适配器,stack,：,LIFOqueue,：,FIFOpriority_queue,：优先级高的元素先出,30,容器概述,对象被插入容器中时，被插入的是,对象的一个复制品,。,许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，,放入容器的对象所属的类，还应该实现,=,和,=,=,!=,empty:,判断容器中是否有元素,max_size:,容器中最多能装多少元素,size:,容器中元素个数,swap:,交换两个容器的内容,35,比较两个容器的例子,比较两个容器的例子：,#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 v2),;,return 0;,若两容器长度相同、所有元素相等，则两个容器就相等，否则为不等。,若两容器长度不同，但较短容器中所有元素都等于较长容器中对应的元素，则较短容器小于另一个容器,若两个容器均不是对方的子序列，则取决于所比较的第一个不等的元素,输出：,0,容器的成员函数,2),只在第一类容器中的函数：,begin,返回指向容器中,第一个元素,的迭代器,end,返回指向容器中,最后一个元素后面,的位置的迭代器,rbegin,返回指向容器中,最后一个元素,的迭代器,rend,返回指向容器中,第一个元素前面,的位置的迭代器,erase,从容器中删除一个或几个元素,clear,从容器中删除所有元素,Head,Tail,begin,rbegin,rend,end,37,迭代器,用于指向,第一类容器,中的元素。有,const,和非,const,两种。,通过迭代器可以读取它指向的元素，通过,非,const,迭代器还能修改其指向的元素,。迭代器用法和,指针,类似。,定义一个容器类的迭代器的方法可以是：,容器类名,:iterator,变量名,;,或：,容器类名,:const_iterator,变量名,;,访问一个迭代器指向的元素：,*迭代器变量名,38,迭代器,迭代器上可以执行,+,操作,以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成,past-the-end,值。,使用一个,past-the-end,值的迭代器来访问对象是非法的,，就好像使用,NULL,或未初始化的指针一样。,39,例如：,#include,#include,using namespace std;,int main(),vector v;/,一个存放,int,元素的向量，一开始里面没有元素,v.push_back(1);,v.push_back(2);,v.push_back(3);,v.push_back(4);,vector:const_iterator i;/,常量迭代器,for(i=v.begin();i!=v.end();i+),cout *i ,;,cout endl;,40,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 *i=p1,44,容器所支持的迭代器类别,容器迭代器类别,vector,随机,deque,随机,list,双向,set/multiset,双向,map/multimap,双向,stack,不支持迭代器,queue,不支持迭代器,priority_queue,不支持迭代器,45,例如，,vector,的迭代器是随机迭代器，所以遍历,vector,可以有以下几种做法：,vector v(100);,vector:value_type i,;/,等效于写,int i;(P687),for(i=0;i v.size();i+),cout,vi;,vector:const_iterator ii;,for(ii=v.begin();ii!=v.end();ii+),cout,*ii,;,/,间隔一个输出：,ii=v.begin();,while(ii v.end(),cout *ii;,ii=ii+2;,46,而,list,的迭代器是双向迭代器，所以以下代码可以：,list v;,list:const_iterator ii;,for(ii=v.begin();ii,！,v.end();ii+),cout,*ii,;,以下代码则不行：,for(ii=v.begin();ii,v.end();ii+),cout *ii;,/,双向迭代器不支持,for(int i=0;i v.size();i+),cout,vi,;,/,双向迭代器不支持,47,算法简介,STL,中提供能在各种容器中通用的算法，比如插入，删除，查找，排序等。大约有,70,种标准算法。,算法就是一个个,函数模板,。,算法通过,迭代器,来操纵容器中的元素。许多算法需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面一个元素的迭代器。比如，排序和查找,有的算法返回一个迭代器。比如,find(),算法，在容器中查找一个元素，并返回一个指向该元素的迭代器。,算法可以处理容器，也可以处理,C,语言的数组,48,算法分类,变化序列算法,copy,remove,fill,replace,random_shuffle,swap,.,会改变容器,非变化序列算法：,adjacent-find,equal,mismatch,find,count,search,count_if,for_each,search_n,以上函数模板都在,中定义,此外还有其他算法，比如,中的算法,49,算法示例：,find(),template,InIt,find(InIt first,InIt last,const T,first,和,last,这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点。,这个区间是个左闭右开的区间，即区间的起点是位于查找范围之中的，而终点不是,val,参数是要查找的元素的值,函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。如果找不到，则该迭代器指向查找区间终点。,50,#include,#include,#include,using namespace std;,main(),int array10=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!=v.end(),cout *p endl;,51,p=find(v.begin(),v.end(),9);,if(p=v.end(),cout not found endl;,p=find(v.begin()+1,v.end()-2,1);,if(p!=v.end(),cout *p endl;,int*pp=find(array,array+4,20);,cout *pp endl;,输出：,3,not found,3,20,52,顺序容器,(vector,deque list,),的算法,除前述共同操作外，顺序容器还有以下共同操作：,front():,返回容器中第一个元素的,引用,back():,返回容器中最后一个元素的,引用,push_back():,在容器末尾增加新元素,pop_back():,删除容器末尾的元素,比如，查,list:front,的,help,得到的定义是：,reference front();,const_reference front()const;,list,有两个,front,函数,53,顺序容器的引用,reference,和,const_reference,是,typedef,的类型,对于,list,list:reference,实际上就是,double&,list:const_reference,实际上就是,const double&,对于,list,list:refrence,实际上就是,int&,list:const_refreence,实际上就是,const int&,54,vector,支持随机访问迭代器，所有,STL,算法都能对,vector,操作。,随机访问时间为常数。在尾部添加速度很快，在中间插入慢。实际上就是,动态数组,。,55,例,1,：,#include#include#include using namespace std;,int main()int i;,int a5=1,2,3,4,5;vector v(5);,cout v.end()-v.begin()endl;,for(i=0;i v.size();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,位置插入,13,for(i=0;i v2.size();i+),cout v2i ,;,return 0;,56,输出：,5,0,1,2,3,100,1,2,13,3,4,5,57,#include,#include,#include,#include,using namespace std;,void main(),istream_iterator input(cin);,int n1,n2;,n1=*input;,input+;,n2=*input;,coutn1,n2endl;,ostream_iterator output(cout,*);,*output=n1+n2;,coutendl;,58,例,2,：,#include#include#include using namespace std;,int main(),const int SIZE=5;,int aSIZE=1,2,3,4,5;,vector v(a,a+5);/,构造函数,try,v.at(100)=7;,catch(out_of_range e),cout e.what()endl;,cout v.front()“,”v.back()endl;,v.erase(v.begin();,ostream_iterator output(cout,“*);,copy(v.begin(),v.end(),output);,v.erase(v.begin(),v.end();/,等效于,v.clear();,59,if(v.empty(),cout empty endl;,v.insert(v.begin(),a,a+SIZE);,copy(v.begin(),v.end(),output);,/,输出：,invalid vector subscript,1,5,2*3*4*5*empty,1*2*3*4*5*,60,算法解释,ostream_iterator output(cout,“*);,定义了一个,ostream_iterator,对象，可以通过,cout,输出以*分隔的一个个整数,copy(v.begin(),v.end(),output);,导致,v,的内容在,cout,上输出,copy,函数模板,(,算法）：,template,OutIt copy(InIt first,InIt last,OutIt x);,本函数对每个在区间,0,last-first),中的,N,执行一次*,(x+N)=*(first+N),，返回,x+N,对于,copy(v.begin(),v.end(),output);,first,和,last,的类型是,vector:const_iterator,output,的类型是,ostream_iterator,61,关于,ostream_iterator,istream_iterator,的例子,#include,#include,#include,#include,using namespace std;,int main(),istream_iterator inputInt(cin);,int n1,n2;,n1=*inputInt;/,读入,n1,inputInt+;,n2=*inputInt;/,读入,n2,cout 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;,62,程序运行后输入,78 90,敲回车，则输出结果为：,78,90,168,12345,63,list,容器,在任何位置插入删除都是,常数时间,，,不支持随机存取,。除了具有所有顺序容器都有的成员函数以外，还支持,8,个成员函数：,push_front:,在前面插入,pop_front:,删除前面的元素,sort:,排序,(list,不支持,STL,的算法,sort),remove:,删除和指定值相等的所有元素,unique:,删除所有和前一个元素相同的元素,merge:,合并两个链表，并清空被合并的那个,reverse:,颠倒链表,splice:,在指定位置前面插入另一链表中的一个或多个元素,并在另一链表中删除被插入的元素,64,#include,#include,using namespace std;,int main(),list v;,v.push_front(1);,v.push_front(5);,v.push_front(3);,v.push_front(4);,v.push_front(3);,v.push_front(4);,/v.pop_front();,/v.remove(3);,v.sort();,v.unique();,list:const_iterator i;/,常量迭代器,for(i=v.begin();i!=v.end();i+),cout *i ,;,cout endl;,v.reverse();,for(i=v.begin();i!=v.end();i+),cout *i ,;,cout endl;,65,deque,容器,所有适用于,vector,的操作都适用于,deque,deque,还有,push_front,（将元素插入到前面）和,pop_front(,删除最前面的元素）操作,66,67,关联容器,set,multiset,map,multimap,内部元素有序排列,，新元素插入的位置取决于它的值，查找速度快,map,关联数组：元素通过键来存储和读取,set,大小可变的集合，支持通过键实现的快速读取,multimap,支持同一个键多次出现的,map,类型,multiset,支持同一个键多次出现的,set,类型,与顺序容器的本质区别,关联容器是通过键,(key),存储和读取元素的,而顺序容器则通过元素在容器中的位置顺序存储和访问元素。,关联容器,除了各容器都有的函数外，还支持以下成员函数：设,m,表容器，,k,表键值,m.find(k),：如果容器中存在键为,k,的元素，则返回指向该元素的迭代器。如果不存在，则返回,end(),值。,m.lower_bound(k),：返回一个迭代器，指向,键不小于,k,的第一个元素,m.upper_bound(k),：返回一个迭代器，指向,键大于,k,的第一个元素,m.count(k),：返回,m,中,k,的出现次数,插入元素用,insert,pair,模板,pair,模板类用来绑定两个对象为一个新的对象，该类型在,头文件中定义。,pair,模板类支持如下操作：,pair p1,：创建一个空的,pair,对象，它的两个元素分别是,T1,和,T2,类型，采用值初始化,pair p1(v1,v2),：创建一个,pair,对象，它的两个元素分别是,T1,和,T2,类型，其中,first,成员初始化为,v1,，,second,成员初始化为,v2,make_pair(v1,v2),：以,v1,和,v2,值创建一个新的,pair,对象，其元素类型分别是,v1,和,v2,的类型,p1 p2,字典次序：如果,p1.firstp2.first,或者,!(p2.first p1.first)&p1.second 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(p.second),cout 2)*(p.first)inserted endl;,else,cout 2)*(p.first)not inserted,class multimap,.,typedef pair,value_type,;,.,;/Key,代表关键字,multimap,中的元素由,组成，每个元素是一个,pair,对象。,multimap,中允许多个元素的关键字相同。元素按照关键字升序排列，缺省情况下用,less,定义关键字的“小于”关系,map,template,class A=allocator,class map,.,typedef pair,value_type,;,.,;,map,中的元素关键字各不相同。元素按照关键字升序排列，缺省情况下用,less,定义“小于”,map,可以用,pairskey,访形式问,map,中的元素。,pairs,为,map,容器名，,key,为关键字的值。,该表达式返回的是对关键值为,key,的元素的值的引用。,如果没有关键字为,key,的元素，则,会往,pairs,里插入一个关键字为,key,的元素，并返回其值的引用,如：,map pairs;,则,pairs50=5;,会修改,pairs,中关键字为,50,的元素，使其值变成,5,#include,#include,using namespace std;,ostream&operator&p),o (p.first ,p.second mmid;,mmid pairs;,cout 1)pairs.count(15)endl;,pairs.insert(mmid:value_type(15,2.7);,pairs.insert(make_pair(15,99.3);/,make_pair,生成,pair,对象,cout 2)pairs.count(15)endl;,pairs.insert(mmid:value_type(20,9.3);,76,mmid:iterator i;,cout 3);,for(i=pairs.begin();i!=pairs.end();i+),cout *i ,;,cout endl;,cout 4);,int n=pairs40;/,如果没有关键字为,40,的元素，则插入一个,for(i=pairs.begin();i!=pairs.end();i+),cout *i ,;,cout endl;,cout 5);,pairs15=6.28;/,把关键字为,15,的元素值改成,6.28,for(i=pairs.begin();i!=pairs.end();i+),cout *i word)+wordCountword;for(map:iterator it=wordCount.begin();it!=,wordCount.end();+it)coutWord:(*it).first tCount:(*it).second,class stack,.,;,stack,是后进先出的数据结构，只能插入、删除、访问栈顶的元素,容器适配器,:stack,stack,上可以进行以下操作：,push:,插入元素,pop:,弹出元素,top:,返回栈顶元素的引用,容器适配器,:queue,和,stack,基本类似，可以用,list,和,deque,实现，缺省情况下用,deque,实现,template,class queue,;,同样也有,push,pop,top,函数,但是,push,发生在队尾，,pop,top,发生在队头，先进先出,容器适配器,:priority_queue,和,queue,类似，可以用,vector,和,deque,实现，缺省情况下用,vector,实现。,priority_queue,通常用,堆排序技术,实现，保证最大的元素总是在最前面。即执行,pop,操作时，删除的是最大的元素，执行,top,操作时，返回的是最大元素的引用。默认的元素比较器是,less,#include,#include,using namespace std;,int main(),priority_queue priorities;,priorities.push(3.2);,priorities.push(9.8);,priorities.push(5.4);,while(!priorities.empty(),cout priorities.top();priorities.pop();,return 0;,/,输出结果,：,9.8 5.4 3.2,84,排序和查找算法,Sort,template,void sort(RanIt first,RanIt last);,find,template,InIt find(InIt first,InIt last,const T,binary_search,折半查找，要求容器已经有序,template,bool binary_search(FwdIt first,FwdIt last,const T,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!=v.end(),cout endl 1)location-v.begin();,sort(v.begin(),v.end();,if(binary_search(v.begin(),v.end(),9),cout endl 3)9 found;,else,cout endl,3),9 not found;,return 0;,86,输出：,(,无,sort,语句,),1)8,2)3,3)9 not found,输出：,(,有,sort,语句,),1)8,2)3,3)9 found,87,sort,sort,实际上是快速排序，时间复杂度,O(n*log(n),;,平均性能最,优。但是最坏的情况下，性能可能非常差。,如果要保证“最坏情况下”的性能，那么可以使用,stable_sort,stable_sort,stable_sort,实际上是,归并排序（,将两个已经排序的序列合并成一个序列），特点是能保持相等元素之间的先后次序,在有足够存储空间的情况下，复杂度为,n*log(n),，否则复杂度为,n*log(n)*log(n),stable_sort,用法和,sort,相同,排序算法要求随机存取迭代器的支持，所以,list,不能使用排序算法，要使用,list:sort,sort,partial_sort:,部分排序，直到 前,n,个元素就位即可,nth_element:,排序，直到第,n,个元素就位，并保证比第,n,个元素小的元素都在第,n,个元素之前即可,partition:,改变元素次序，使符合某准则的元素放在前面,举 例,例,8-7,利用,STL,提供的容器和算法，对数组进行倒序输出,例,8-8,利用,STL,求任意指定整数以内的全部素数,例,8-9,比较数据大小并排序,90,小结,C+,模板,函数模板,STL库,各种容器,迭代器,算法,STL学习资料,www.stlchina.org,很多资料的汇总网站,