《泛型程序设计与CSTL简介L简介》由会员分享，可在线阅读，更多相关《泛型程序设计与CSTL简介L简介（77页珍藏版）》请在金锄头文库上搜索。
1、C+教程第十五章 泛型程序设计与C+STL简介清华大学郑莉学习目标掌握泛型程序设计思想以及概念；掌握STL中顺序容器的使用，了解关联容器；掌握迭代器的使用；了解泛型算法和函数对象。2目录15.1泛型程序设计的概念和术语15.1.1泛型程序设计15.1.2STL的相关概念和术语15.2C+STL中的容器15.2.1顺序容器15.2.2关联容器15.2.3容器适配器3目录（续）15.3迭代器15.3.1迭代器的分类15.3.2迭代器适配器15.3.3迭代器相关的辅助函数15.4标准C+库中的算法简介15.4.1非可变序列算法15.4.2可变序列算法15.4.3排序及相关算法4目录（续）15.4标准
2、C+库中的算法简介15.4.4数值算法15.5函数对象15.5.1函数对象15.5.2函数适配器515.1.1 泛型程序设计泛型程序设计是继面向对象程序设计之后的又一种程序设计方法。泛型程序设计就是让程序写得通用，能够适用于各种数据类型与数据结构，并且并不损失程序效率。面向对象与泛型程序设计这两种程序设计方法并不矛盾，而是相得益彰。标准模板库( Standard Temp late L ibrary，简称STL)是建立在C+中模板机制上的泛型程序设计思想的实现。615.1 泛型程序设计的概念和术语15.1.2 标准模板库相关概念和术语容器容器是存放其他对象的对象。比如我们常见的C+内置数组，从
3、广义上讲也属于一种容器。容器可以存放同一种类型的一组元素或对象，称为同类容器类（homogenousconstainer）；或者存放不同类型的的元素或对象时，称为异类容器类（heterogenousconstainer）。对于STL容器库，其包含了两类容器，一种为顺序容器（sequencecontsainer），另一种为关联容器（associativecontainer）。迭代器在C+中，我们经常使用指针。而迭代器就是相当于指针，它提供了一种一般化的方法使得C+程序能够访问不同数据类型的顺序或者关联容器中的每一个元素，我们可以称它为“泛型指针”。STL定义了五种迭代器类型，前向迭代器（forw
4、arditerator），双向迭代器(bidirectionaliterator)，输入迭代器(inputiterator)，输出迭代器(outputiterator)，随机访问迭代器(randomaccessiterator)。715.1 泛型程序设计的概念和术语15.1.2 标准模板库相关概念和术语算法算法是STL中的核心，它它包含了70多个通用算法。可以分为四类：不可变序列算法（non-modifyingsequencealgorithms）、可变序列算法(mutatingsequencealgorithms)、排序及相关算法(sortingandrelatedalgorithms)和算
5、术算法（numericalgorithms）。函数对象函数对象是STL提供的四种组件中的一种，它是定义了操作符【operator()】的对象。在C+中，除了定义了操作符operator()的对象之外，普通函数或者函数指针也满足函数对象的特征。结合函数模板的使用，函数对象使得STL更加灵活和方便，同时也使得代码更为高效。本章在15.5小节将单独介绍函数对象。815.1 泛型程序设计的概念和术语15.1.2 标准模板库相关概念和术语适配器(adapter)适配器是一种接口类，可以认为是标准组件的改装。通过修改其它类的接口，使适配器满足一定需求，可分为容器适配器、迭代器适配器和函数对象适配器三种。分
6、配器(allocator)分配器是STL提供的一种内存管理类模块。每种STL容器都是用了一种分配器类，用来封装程序所用的内存分配模式的信息。不同的内存分配模式采用不同的方法从 操作系统中检索内存。分配器类可以封装许多方面的信息，包括指针、常量指针、引用、常量引用、对象大小、不同类型指针之间的差别、分配函数与释放函数、以及一些函数的信息。分配器上的所有操作都具有分摊常量的运行时间。915.1 泛型程序设计的概念和术语15.1.2 标准模板库相关概念和术语容器接口STL为容器提供了一些公共接口，这些公共接口是通用的，也可以说是泛型的。这些都是容器设计的规范，对于容器而言，定义的公共接口主要有以下几
7、个部分：1015.1 泛型程序设计的概念和术语通用运算说明a=b同类容器的相等比较操作，判断是否相等，相等则为truea!=b同类容器的不等比较操作，判断是否不等，不等则为trueab两个容器大小判断，首先判断size，接着判断元素值，ab与上同，不过ab时为trueab）a=b等同与！（ab）r=b赋值操作15.1.2 标准模板库相关概念和术语容器接口所有容器定义的迭代器访问接口1115.1 泛型程序设计的概念和术语迭代方法说明begin（）返回一个指向容器第一个元素的迭代器end（）返回一个指向容器末尾元素的迭代器rbegin（）返回一个逆向迭代器，指向反序后的首元素rend（）返回一个逆
8、向迭代器，指向反序后的末尾元素15.1.2 标准模板库相关概念和术语容器接口其他访问接口1215.1 泛型程序设计的概念和术语操作说明Size()返回容器元素个数Max_size()返回容器最大的规模Empty()判断容器是否为空，是，则返回trueSwap（）交换两个容器的所有元素15.2.1 顺序容器顺序容器顺序容器包含Vector，deque和list三种容器，其中vector和deque属于直接访问容器，list属于顺序访问容器。向量（vector）向量相当于一个动态数组，其可以动态存储元素，并提供对容器元素的随机访问。为了提高效率，vector并不是随着每一个元素的插入而增长自己，而
9、是当vector要增长自己的时候，他分配的空间比当前所需的空间要多一些。这多一些的内存空间使需要添加新元素的时候不必再重新分配内存。与C+的内置数组相比较，除了动态之外，向量容器支持向对象。1315.2 C+STL中的容器例15-1：建立一个整型向量容器#include#include/使用向量容器须包含的头文件#includeusingnamespacestd;constintn=5;intmain()intarrayn=12,4,5,9,1;vectorvec1;/构造1：定义一个空的整型向量容器vec1inti;for(i=0;in;i+)/赋值/vec1i=arrayi;/错误,因为v
10、ec1还没有分配内存空间vec1.push_back(arrayi);/压入向量尾部vectorvec2(vec1);/构造2：拷贝构造vec2vectorvec3(array,array+3);/构造3：用array到array+3的值初始化vectorvec4(n,3);/ 构造4：用n个3初始化向量1415.2 C+STL中的容器15.2.1顺序容器例15-1（续）for(i=0;in;i+)coutsetw(5)vec1i;coutendl;for(i=0;in;i+)coutsetw(5)vec2i;coutendl;for(i=0;i3;i+)coutsetw(5)vec3i;co
11、utendl;for(i=0;in;i+)coutsetw(5)vec4i;coutendl;1515.2 C+STL中的容器15.2.1顺序容器运行结果：运行结果：124591124591124533333例15-1（续）15.2 C+STL中的容器15.2.1顺序容器16例15-2：向量容器中元素的添加和删除#include#include#include#includeusingnamespacestd;voiddisplay(vector&_str)/向量元素显示函数coutthereare_str.size()elementsinthevector.endl;for(inti=0;i
12、_str.size();i+)coutsetw(15)_stri;/逐个显示元素coutendl;1715.2 C+STL中的容器15.2.1顺序容器例15-2（续）intmain()stringstr3=Hello,C+,Love;vectorvec1;/将str至str+3之间的元素插入vec1，vec1.insert(vec1.begin(),str,str+3);vectorvec2;/将vec1.begin()至vec1.end()之间的元素插入到vec2，等效于将vec1复制到vec2中，vec2.insert(vec2.end(),vec1.begin(),vec1.end();
13、vec2.insert(vec2.begin(),1,welcomtoC+);/在vec2.begin()前插入字符串display(vec1);display(vec2);vec1.clear();/清除整个vec1display(vec1);vec2.erase(vec2.begin();/删除vec2的首元素display(vec2);vec2.pop_back();/删除vec2的末尾元素display(vec2);1815.2 C+STL中的容器15.2.1顺序容器运行结果：运行结果：thereare3elementsinthevector.HelloC+Lovethereare4e
14、lementsinthevector.welcomtoC+HelloC+Lovethereare0elementsinthevector.thereare3elementsinthevector.HelloC+Lovethereare2elementsinthevector.HelloC+例15-2（续）15.2 C+STL中的容器15.2.1顺序容器例15-3：向量容器中元素的添加和删除#include#include#include#includeusingnamespacestd;intmain()intarray4=2,3,5,2;vectornval;coutnvalssizeis:
15、nval.size()andthecapacityis:nval.capacity()endl;for(inti=0;i17;i+)nval.push_back(i);if(!(i%4)coutnvalssizeis:nval.size()andthecapacityis:nval.capacity()endl;2015.2 C+STL中的容器15.2.1顺序容器运行结果：运行结果：nvalssizeis:0andthecapacityis:0nvalssizeis:1andthecapacityis:1nvalssizeis:5andthecapacityis:6nvalssizeis:9a
16、ndthecapacityis:9nvalssizeis:13andthecapacityis:13nvalssizeis:17andthecapacityis:19例15-3（续）15.2 C+STL中的容器15.2.1顺序容器例15-4：复杂对象的向量容器#include#include#include#includeusingnamespacestd;constintn=6;structEvaluate/结构体，stringName;/学生的姓名doubleRank;/学生的排名;voiddisplay(vector&_student)/显示排名情况if(!_student.empty(
17、) /如果不空则显示for(inti=0;i_student.size();i+)cout_studenti.Namesrankissetw(5)_studenti.Rankendl;2215.2 C+STL中的容器15.2.1顺序容器例15-4（续）intmain() stringnamen=John,Lily,David,Jevons,Mike,Jane;vectorNameSet;vectorrank(n,0);/初始化一个大小为n，元素都为0的向量NameSet.insert(NameSet.begin(),name,name+n);inti;for(i=0;in;i+)coutPle
18、aseenterNameSetiranki;vectorStudent;2315.2 C+STL中的容器15.2.1顺序容器例15-4（续）for(i=0;in;i+)Evaluatetemp;temp.Name=NameSeti;temp.Rank=double(ranki)/100;Student.push_back(temp);/将建立的结构体逐个存放到Student向量中cout“therankofStudentsetis”endl;display(Student);/显示学生以及排名情况vectorStudent2(Student);/调用向量的拷贝构造函数cout“theparti
19、alrankofStudent2setis”endl;display(Student);2415.2 C+STL中的容器15.2.1顺序容器例15-4（续）vectorStudent3(Student2.begin(),Student2.end()-3);cout“thesizeofStudent3is:”Student3.size()endl;/向量所含元素Student3.swap(Student);/交换两个容器coutthesizeofStudentis:Student.size()endl;/交换后的student的元素个数coutthesizeofStudent3is:Studen
20、t3.size()endl;/交换后的student3的元素个数Student3.pop_back();/删除最后一个元素coutsetw(5)Student3.size();Student3.erase(Student3.begin();/删除最开始的一个元素coutsetw(5)Student3.size()endl;display(Student3);/显示更新后的向量容器2515.2 C+STL中的容器15.2.1顺序容器运行结果：运行结果：PleaseenterJohnsrank(0100):1PleaseenterLilysrank(0100):2PleaseenterDavids
21、rank(0100):3PleaseenterJevonssrank(0100):4PleaseenterMikesrank(0100):5PleaseenterJanesrank(0100):6therankofStudentsetisJohnsrankis0.01Lilysrankis0.02Davidsrankis0.03Jevonssrankis0.04Mikesrankis0.05例15-4（续）15.2 C+STL中的容器15.2.1顺序容器Janesrankis0.06thepartialrankofStudent2setisJohnsrankis0.01Lilysrankis0
22、.02Davidsrankis0.03Jevonssrankis0.04Mikesrankis0.05Janesrankis0.06thesizeofStudent3is:3thesizeofStudentis:3thesizeofStudent3is:654Lilysrankis0.02Davidsrankis0.03Jevonssrankis0.04Mikesrankis0.052615.2.1 顺序容器（续）双端队列（deque）双端队列是一种增加了访问权限的队列。在队列中，我们只允许从队列的一端添加元素，在队列的另一端提取元素；在双端队列中，其支持两端的出队和入队，这个我们可以通过前面
23、所述的顺序容器接口看出。Vector与deque同属于随机访问容器，vector拥有的成员函数deque也都含有。这个我们在顺序容器一般接口表中可以看出。列表（list）列表如我们在13章学习的链表一样，但是在13章中我们只实现了单链表，也就是只支持从一个方向遍历元素，STL实现的list由节点组成的双向链表，每个结点包含着一个元素，提供从两个方向遍历元素。2715.2 C+STL中的容器例15-5：建立一个双端队列容器#include#include/使用deque需要包含的头文件#includeusingnamespacestd;constintn=10;intmain()dequede;
24、intarrayn=10,1,3,4,5,7,2,9,8,6;inti;for(i=0;i5;i+)de.push_back(arrayi);de.push_front(arrayn-1-i);for(i=0;in;i+)coutsetw(5)dei;coutendl;for(i=0;in;i+)de.pop_front();de.push_back(arrayi);for(i=0;in;i+)coutsetw(5)dei;coutendl;2815.2 C+STL中的容器15.2.1顺序容器例15-5：建立一个双端队列容器#include#include/使用deque需要包含的头文件#in
25、cludeusingnamespacestd;constintn=10;intmain()dequede;intarrayn=10,1,3,4,5,7,2,9,8,6;inti;for(i=0;i5;i+)de.push_back(arrayi);de.push_front(arrayn-1-i);for(i=0;in;i+)coutsetw(5)dei;coutendl;for(i=0;in;i+)de.pop_front();de.push_back(arrayi);for(i=0;in;i+)coutsetw(5)dei;coutendl;2915.2 C+STL中的容器15.2.1顺序
26、容器运行结果：运行结果：7298610134510134572986例15-5（续）15.2 C+STL中的容器15.2.1顺序容器30例15-6：建立一个列表#include#include/使用list需要包含的头文件#includeusingnamespacestd;constintn=10;voiddisplay(list_list)if(!_list.empty()list:iteratorit;for(it=_list.begin();it!=_list.end();it+)coutsetw(5)*it;coutendl;elsecoutNulllistendl;3115.2 C+
27、STL中的容器15.2.1顺序容器例15-6：建立一个列表intmain()intarrayn=2,3,5,7,34,3,4,1,0,10;listlist1;list1.insert(list1.begin(),array,array+n);display(list1);listlist2=list1;for(inti=0;i7;i+)list2.remove(i);display(list2);list2.splice(list2.end(),list1);display(list2);display(list1);3215.2 C+STL中的容器15.2.1顺序容器运行结果：运行结果：2
28、357343410107341073410235734341010Nulllist例15-6（续）15.2 C+STL中的容器15.2.1顺序容器33例15-7：列表中的算法#include#include#includeusingnamespacestd;constintn=5;voiddisplay(list_list)if(!_list.empty()list:iteratorit;for(it=_list.begin();it!=_list.end();it+)coutsetw(5)*it;coutendl;elsecoutNulllistendl;3415.2 C+STL中的容器15
29、.2.1顺序容器例15-7：列表中的算法intmain()intarrayn=2,7,5,3,34;listlist1;list1.insert(list1.begin(),array,array+n);display(list1);list1.sort(greater();/按降序排列，greater为降序函数对象display(list1);list1.sort();/升序排列display(list1);listlist2=list1;for(inti=0;i4;i+)list2.remove(i);/将列表中小于4的元素移除 display(list2);list1.merge(lis
30、t2);/默认operator,也可以greater()display(list1);display(list2);list1.reverse(); /逆序display(list1);3515.2 C+STL中的容器15.2.1顺序容器运行结果：运行结果：27533434753223573457342355773434Nulllist3434775532例15-7（续）15.2 C+STL中的容器15.2.1顺序容器3615.2.2 关联容器映射（map）映射提供了一个键/值对，基于键的查询，迅速查找到键相对应的所需的值。如mapmap_name，其建立的是一个以Type1为索引，Type2
31、的值的查询。 集合（set） 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序。这个与map存储的结构是一致的，都是以二叉树结构的节点形式存放。3715.2 C+STL中的容器例15-8：建立一个学生学号与姓名的映射#include#include#include/使用映射需要包含的头文件#includeusingnamespacestd;intmain()mapstudent;student2004010001=李山;/直接插入元素typedefmap:value_typevaltype;/利用map中提供的键值对类型v
32、altype(2004010002,刘丽);/建立一个键值对student.insert(valtype(2004010002,刘丽);/利用insert方法插入元素student.insert(valtype(2004010003,张斌);map:iteratorit; /声明迭代器it=student.find(2004010003);/查找学号为2004010003的学生信息if(it!=student.end()/如果返回的是映射的结尾cout(*it).second;/则输出该键对应的的值intcount=student.count(2004010005);/查询是否存在200401
33、0005/删除退学的学生信息student.erase(it=find(2004010001);3815.2 C+STL中的容器15.2.2关联容器运行结果：运行结果：张斌例15-8（续）15.2 C+STL中的容器15.2.2关联容器39例15-9：建立快速查询的集合#include#include/使用set需要包含的头文件#includeusingnamespacestd;intmain()setDepartment;stringstr1(DPIM);stringstr=DME,DAE,DTE,DBE;Department.insert(“DCE”);for(inti=0;i4;i+)D
34、epartment.insert(stri);set:iteratorit;it=Department.find(DAE);/if(it!=Department.end()cout*itendl;if(!Department.count(str1)Department.insert(str1);/for(it=Department.begin();it!=Department.end();it+)cout*it;coutendl;4015.2 C+STL中的容器15.2.2关联容器运行结果：运行结果：DAEDAEDBEDCEDMEDPIMDTE例15-9（续）15.2 C+STL中的容器15.
35、2.2关联容器4115.2.3 容器适配器容器适配器是通过修改调整容器的接口，使得容器适用于另一种不同效果。修改顺序容器接口的容器适配器有stack和queue，其中stack是具有后进先出特性的访问受限的线性结构，而queue是具有先进先出特性的访问受限的线性结构，此外还有优先队列。栈容器适配器stack（栈）是一种容器适配器，前面已经讲过，它不是独立的容器，只是某种序列容器的变化，它提供原容器的一个专用的受限接口。缺省的stack类（定义在头文件中），是对deque（双端队列）的一种限制。队列容器适配器queue（队列容器）是另外一种容器适配器。它默认通过deque来实现队列，提供了如pu
36、sh，pop等成员函数，还包括测试队列的使用情况，元素个数，是否为空等等功能。4215.2 C+STL中的容器例15-10： 简单的栈应用#include#includeusingnamespacestd;intmain()stacksk1;for(inti=0;i10;i+)sk1.push(i);coutpopfromthestack:;while(!sk1.empty()coutsk1.top();sk1.pop();4315.2 C+STL中的容器15.2.3容器适配器运行结果：运行结果：popfromthestack:9876543210例15-10（续）15.2 C+STL中的容器
37、15.2.3容器适配器44例15-11：杨辉三角的显示#include#include#includeusingnamespacestd;voidYanghui(intn);/输出杨辉三角intmain()Yanghui(10);voidYanghui(intn)queueq;q.push(1);/首先在队列中存第一行元素1ints=0;for(inti=0;i=n;i+)coutendl;/对于每一行输出换行coutsetw(n-i)*2); /设置输出格式q.push(0);/在每一行数据中间添加0for(intj=1;j=i+2;j+)/对于每一行的输出i+2项元素intt=q.fron
38、t();/获取队首元素q.pop();q.push(s+t);/保存两项之和s=t;if(j!=i+2)coutsetw(4)）。输出迭代器outputiterator迭代器可以被认为是与输入迭代器相反功能的迭代器。它用来向容器中写写入元素，但是不保证支持读取容器的内容。支持的操作为至少需要包括操作符（+）（包括前置和后置）和指针操作符（*）（左值形式）。前向迭代器forwarditerator迭代器可以用来以一个方向遍历容器的元素，支持支持容器元素的读写。4715.3 迭代器15.3.1 迭代器的分类（续）双向迭代器bidirectionaliterator迭代其可以用来从两个方向遍历容器的
39、元素，支持容器元素的读写。随机访问迭代器randomaccessiterator迭代器支持容器元素的随机访问，同样支持容器元素的读与写。五类迭代器功能包含关系4815.3 迭代器随机随机双向双向前向前向输入输入输出输出例15-12：使用迭代器访问向量容器#include#includeusingnamespacestd;constintN=7;voiddisplay(constvector&_vec);intmain()vectorinvec;intarrayN=2,3,5,2,8,18,4;invec.insert(invec.begin(),array,array+N);display(i
40、nvec);vectorinvec2;invec2.insert(invec2.begin(),invec.begin(),invec.begin()+invec.size()/2);display(invec2);4915.3 迭代器15.3.1迭代器的分类例15-12：使用迭代器访问向量容器voiddisplay(constvector&_vec)vector:const_iteratoriter=_vec.begin();vector:const_iteratorit_end=_vec.end();for(;iter!=it_end;iter+)cout(*iter);coutendl;
41、5015.3 迭代器15.3.1迭代器的分类运行结果：运行结果：23528184235例15-12（续）15.3 迭代器15.3.1迭代器的分类5115.3.2 迭代器适配器迭代器适配器是通过修改调整迭代器的接口获得的适配器。STL提供了两类迭代器适配器：逆向迭代器和插入型迭代器。逆向迭代器是一种适配器，他通过重新定义递增运算和递减运算，使其行为正好倒置。这样，使用这类迭代器算法将以逆向次序处理元素。所有标准容器都支持通过逆向迭代器来遍历元素。插入型迭代器插入型迭代器用来将赋值操作转换为插入操作。通过这种迭代器，算法可以执行插入行为而不是覆盖行为。5215.3 迭代器15.3.3 迭代器相关的
42、辅助函数STL为迭代器提供了三个辅助函数：advance()、distance()、iter_swap()。三个函数的原型如下：voidadvance(InputIterator&pos,Distn);distdistance(InputIteratorpos1,InputIteratorpos2);voiditer_swap(ForwardIteratorpos1,ForwardIteratorpos2);5315.3 迭代器例15-13：辅助函数使用#include#include#includeusingnamespacestd;constintN=7;intmain()listiLis
43、t;intarrayN=7,2,6,3,8,10,8;iList.insert(iList.begin(),array,array+N);list:iteratorit=iList.begin();list:iteratoritend=iList.end();intsize=distance(it,itend);coutthesizeofthelistis:;coutsizeendl;advance(it,5);coutthe6thelementis:;cout(*it)endl;iter_swap(it,-iList.end();for(it=iList.begin();it!=itend;
44、it+)cout(*it);coutendl;5415.3 迭代器15.3.3迭代器相关的辅助函数运行结果：运行结果：thesizeofthelistis:7the6thelementis:1072638810例15-13（续）15.3 迭代器15.3.3迭代器相关的辅助函数5515.4 标准C+库中的算法简介在STL中的算法都是通过C+模板实现的。容器是一个黑匣子，而算法也是一个黑匣子，迭代器可以认为是一跟导线。STL算法是通用的，每个算法都适合于若干不同的数据结构。STL标准算法可以分为四类。第一类非可变序列算法，通常这类算法在对容器进行操作的时候不会改变容器的内容；第二类是可变序列算法，
45、这类算法一般会改变所操作的容器的内容；第三类是排序以及相关的算法，包括排序和合并算法、二分查找算法、有序序列的集合操作算法；第四类算法是通用数值算法。 5615.4.1 非可变序列算法非可变序列算法可以修改所操作容器的元素。支持这类算法的迭代器的为输入迭代器和前向迭代器。共11个。5715.4 标准C+库中的算法简介循环for_each()对序列中的每个元素执行某操作查找find()在序列中找出某个值的第一次出现的位置find_if()在序列中找出符合条件的第一个元素find_end()在序列中找出一子序列的最后一次出现的位置find_first_of()在序列中找出第一次出现指定值集中之值的
46、位置adjacent_find() 在序列中找出相邻的一对值计数count()在序列中统计某个值出现的次数count_if()在序列中统计符合某个条件的值出现的次数比较mismatch()找出两个序列相异的第一个元素equal()两个序列中的对应元素都相同时为真搜索search()在序列中找出一子序列的第一次出现的位置search_n()在序列中找出一值的连续n次出现的位置例15-14：可变序列算法实例#include#include/算法需要包含的头文件#include/使用函数对象需要包含的头文件#includeusingnamespacestd;classoutpublic:voidop
47、erator()(intx)coutx;5815.4 标准C+库中的算法简介15.4.1非可变序列算法intmain()intarray=2,4,7,4,9,3,2,7,8;vectorivec(array,array+sizeof(array)/sizeof(int);vector:iteratoriter;/找到第一个为4的元素位置，并输出此值和后面的所有值for(iter=find(ivec.begin(),ivec.end(),4);iter!=ivec.end();iter+)cout*iter;coutendl;/输出容器中等于4的元素个数coutcount(ivec.begin(
48、),ivec.end(),4)endl;/输出容器中小于等于4元素的个数coutcount_if(ivec.begin(),ivec.end(),bind2nd(less_equal(),4)endl;/利用for_each算法输出每个元素for_each(ivec.begin(),ivec.end(),out();coutendl;5915.4 标准C+库中的算法简介15.4.1非可变序列算法例15-14（续）运行结果：运行结果：4749327825247493278例15-14（续）15.4 标准C+库中的算法简介15.4.1非可变序列算法6015.4.2 可变序列算法可变序列算法可以修改
49、他们所操作的容器的元素，这类算法28个。6115.4 标准C+库中的算法简介复制copy()从序列的第一个元素起进行复制copy_backward()从序列的最后一个元素起进行复制交换swap()交换两个元素swap_ranges()交换指定范围的元素iter_swap()交换由迭代器所指的两个元素变换transform()将某操作应用于指定范围的每个元素替换replace()用一个给定值替换一些值replace_if()替换满足条件的一些元素replace_copy()复制序列时用一给定值替换元素replace_copy_if()复制序列时替换满足条件的元素15.4.2 可变序列算法（续）6
50、215.4 标准C+库中的算法简介填充fill()用一给定值取代所有元素fill_n()用一给定值取代前n个元素生成generate()用一操作的结果取代所有元素generate_n()用一操作的结果取代前n个元素删除remove()删除具有给定值的元素remove_if()删除满足条件的元素remove_copy()复制序列时删除具有给定值的元素remove_copy_if()复制序列时删除满足条件的元素剔除unique()删除相邻的重复元素unique_copy()复制序列时删除相邻的重复元素反转reverse()反转元素的次序reverse_copy()复制序列时反转元素的次序循环rot
51、ate()循环移动元素rotate_copy()复制序列时循环移动元素随机random_shuffle()采用均匀分布来随机移动元素划分partition()将满足某条件的元素都放到前面stable_partition()将满足某条件的元素都放到前面并维持原顺序例15-15：可变序列算法实例#include#include#include#includeusingnamespacestd;constintn=9;classsquare/定义平方操作的函数对象public:intoperator()(intiter)returniter*iter;classodd_by_one/定义每次乘以2的
52、函数对象public:intoperator()()returnx=x*2;private:staticintx;intodd_by_one:x=1;6315.4 标准C+库中的算法简介15.4.2可变序列算法例15-15（续）intmain()intarrayn=0,1,2,3,5,3,8,5,1;vectorivec1(n,0);vector:iteratoriter=ivec1.begin();ostream_iteratoroutput(cout,t);/定义输出流迭代器copy(array,array+n,output);/利用copy将数组内容考到输出流对象中coutendl;/输
53、出/将数组内容拷贝到向量ivec1中copy(array,array+n,ivec1.begin();copy(ivec1.begin(),ivec1.end(),output);coutendl;/从ivec1首元素开始填充2个3fill_n(ivec1.begin(),2,3);copy(ivec1.begin(),ivec1.end(),output);coutendl;/利用generate生成一个2为比的等比数列vectorivec2(array,array+n);generate(ivec2.begin(),ivec2.end(),odd_by_one();copy(ivec2.b
54、egin(),ivec2.end(),output);coutendl;6415.4 标准C+库中的算法简介15.4.2可变序列算法例15-15（续）/利用transform将ivec1中的每一个元素进行平方操作，并拷贝到ilist1中listilist1(n,0);transform(ivec1.begin(),ivec1.end(),ilist1.begin(),square();copy(ilist1.begin(),ilist1.end(),output);coutendl;/移除ilist1中所有值等于9的元素，并传递给list的earse函数进行删除list:iteratorit=
55、remove(ilist1.begin(),ilist1.end(),9);ilist1.erase(it,ilist1.end();copy(ilist1.begin(),ilist1.end(),output);coutendl;/交换两个向量容器swap(ivec1,ivec2);6515.4 标准C+库中的算法简介15.4.2可变序列算法运行结果：运行结果：01235385101235385133235385124816326412825651299492596425142564251例15-15（续）15.4 标准C+库中的算法简介15.4.2可变序列算法6615.4.3 排序及相关
56、算法6715.4 标准C+库中的算法简介排序sort()以很好的平均效率排序stable_sort()排序，并维持相同元素的原有顺序partial_sort()将区间个数的元素排好序partial_sort_copy()将区间个数的元素排序并复制到别处第n个元素nth_element()将第n各元素放到它的正确位置二分检索lower_bound()找到大于等于某值的第一次出现upper_bound()找到大于某值的第一次出现equal_range()找到（在不破坏顺序的前提下）可插入给定值的最大范围binary_search()在有序序列中确定给定元素是否存在归并merge()归并两个有序序列
57、inplace_merge()归并两个接续的有序序列有序结构上的集合操作includes()一序列为另一序列的子序列时为真set_union()构造两个集合的有序并集set_intersection()构造两个集合的有序交集set_difference()构造两个集合的有序差集set_symmetric_difference()构造两个集合的有序对称差集（并-交）15.4.3 排序及相关算法（续）6815.4 标准C+库中的算法简介有序结构上的集合操作includes()一序列为另一序列的子序列时为真set_union()构造两个集合的有序并集set_intersection()构造两个集合的
58、有序交集set_difference()构造两个集合的有序差集set_symmetric_difference()构造两个集合的有序对称差集（并-交）堆操作push_heap()向堆中加入元素pop_heap()从堆中弹出元素make_heap()从序列构造堆sort_heap()给堆排序最大和最小min()返回两个元素最小值max()返回两个元素最大值min_element()返回序列中的最小元素的位置max_element()返回序列中的最大元素的位置词典比较 lexicographical_compare()两个序列按字典序的第一个在前排列生成器next_permutation()按字典
59、序的下一个排列prev_permutation()按字典序的前一个排列例15-16： 排序算法举例#include#include#include#includeusingnamespacestd;constintn=8;intmain()intarrayn=4,3,7,2,2,3,8,5;vectorivec1(array,array+n);ostream_iteratoroutput(cout,);/输出容器中最大和最小的元素cout*max_element(ivec1.begin(),ivec1.end()endl;cout*min_element(ivec1.begin(),ivec1
60、.end()endl;/利用部分排序算法排序partial_sort(ivec1.begin(),ivec1.begin()+3,ivec1.end();copy(ivec1.begin(),ivec1.end(),output);coutendl;6915.4 标准C+库中的算法简介15.4.3排序及相关算法例15-16（续）/部分排序，并将排序的拷贝到新的容器vectorivec2(5,0);partial_sort_copy(ivec1.begin(),ivec1.begin()+5,ivec2.begin(),ivec2.end();copy(ivec2.begin(),ivec2.e
61、nd(),output);coutendl;/进行全区间的排序，默认为升序sort(ivec1.begin(),ivec1.end();copy(ivec1.begin(),ivec1.end(),output);coutendl;/利用二分法查找确定元素可插入的迭代器位置cout*lower_bound(ivec1.begin(),ivec1.end(),5)endl;cout*upper_bound(ivec1.begin(),ivec1.end(),5)endl;/利用合并算法将两个向量容器合并，并拷贝到新的数组中intarray15+n;merge(ivec1.begin(),ivec
62、1.end(),ivec2.begin(),ivec2.end(),array1);copy(array1,array1+13,output);coutendl;7015.4 标准C+库中的算法简介15.4.3排序及相关算法运行结果：运行结果：82223743852234722334578572222333445778例15-16（续）15.4 标准C+库中的算法简介15.4.3排序及相关算法7115.4.4 数值算法数值算法包括4个算法，分别为accumulate（累积算法）、partial_sum（累加部分元素和算法）、adjacent_difference（相邻元素差）和inner_pr
63、oduct（内积算法）。我们使用数值算法需要包含头文件。7215.4 标准C+库中的算法简介例15-17：数值算法实例#include#include#include/所需要包含的头文件usingnamespacestd;constintn=6;intmain()intarrayn=2,2,1,5,3,6;vectorivec1(array,array+n);vectorivec2(ivec1);ostream_iteratoroutput(cout,);/对序列进行求和累积coutaccumulate(ivec1.begin(),ivec1.end(),0)endl;/对序列进行部分求和pa
64、rtial_sum(ivec1.begin(),ivec1.end(),output);coutendl;/对序列求相邻元素的差adjacent_difference(ivec1.begin(),ivec1.end(),output);coutendl;/对两个向量做内积coutinner_product(ivec1.begin(),ivec1.end(),ivec2.begin(),0)endl;7315.4 标准C+库中的算法简介15.4.4数值算法运行结果：运行结果：1924510131920-14-2379Pressanykeytocontinue例15-17（续）15.4 标准C+库
65、中的算法简介15.4.4数值算法7415.5.1 函数对象在C+程序中，任何普通的函数、函数指针和任何重载了调用operator（）的类对象都满足函数对象的特征，都可以作为函数对象来使用。STL提供了标准的函数对象，包括算术，关系和逻辑函数对象。算术：plus，minus，multiplies，negate关系：equal_to，not_equal_to，greater，less，greater_equal，less_equal逻辑：logical_and，logical_or，logical_not7515.5 函数对象15.5.2 函数适配器标准库提供了一组函数适配器，可以分为两类：一是绑
66、定器（binder）；二是取反器（negator）。绑定器通过把二元函数对象的一个实参绑定到一个特殊的值上，将其转换成一元函数对象。取反器是将一个函数的对象的值翻转的函数适配器。7615.5 函数对象小结本章引入了泛型算法的概念，并对C+中利用模板机制编写的标准模板库（STL）进行了比较详细的介绍。我们主要介绍了容器、迭代器、算法、函数对象和适配器的概念，并介绍了标准容器vector、list以及deque的详细用法，并且介绍了容器适配器stack和deque，除了顺序容器之外，还简单介绍了关联容器set和map的使用。迭代器做为泛型指针用于访问容器的桥梁，我们介绍了其分类以及在容器中的使用，并且介绍了迭代器辅助函数的应用。77
