第10章排序及相关操作

1、第十章 排序及相关操作 n10.1 排序排序n10.2 第n个元素n10.3 二分检索n10.4 归并n10.5 序结构上的集合操作n10.6 堆操作n10.7 最大和最小n10.8 词典比较n10.9 排列生成器n10.10数值算法n10.11自定义STL函数n主要函数如下所示。序号功能函数名称说明1排序Sort以很好的平均效率排序stable_sort排序，并维持相同元素的原有顺序partial_sort将序列的前一部分排好序partial_sort_copy复制的同时将序列的前一部分排好序2第n个元素nth_element将第n各元素放到它的正确位置3二分检索lower_bound找到大

2、于等于某值的第一次出现upper_bound找到大于某值的第一次出现equal_range找到（在不破坏顺序的前提下）可插入给定值的最大范围binary_search在有序序列中确定给定元素是否存在4归并Merge归并两个有序序列inplace_merge归并两个接续的有序序列5序结构上的集合操作Includes一序列为另一序列的子序列时为真set_union构造两个集合的有序并集set_intersection构造两个集合的有序交集set_difference构造两个集合的有序差集set_symmetric_difference构造两个集合的有序对称差集（并-交）6堆操作make_heap从

3、序列构造堆pop_heap从堆中弹出元素push_heap向堆中加入元素sort_heap给堆排序7最大和最小min两个值中较小的max两个值中较大的min_element序列中的最小元素max_element序列中的最大元素8词典比较lexicographical_compare两个序列按字典序的第一个在前9排列生成器next_permutation按字典序的下一个排列prev_permutation按字典序的前一个排列10数值算法accumulate累积和inner_product内积partial_sum局部求和adjacent_difference临接差10.1 排序10.1.1 主要

4、函数主要函数sort原形：template void sort(RanIt first, RanIt last); template void sort(RanIt first, RanIt last, Pred pr); 第一个模板函数first,last）间迭代器指示的元素数据按升序排列，第二个模板函数定义了比较函数pr(x,y)代替了operator(x,y), 功能是相似的，属于不稳定排序。stable_sort原型：template void stable_sort(RanIt first, RanIt last); template void stable_sort(RanIt f

5、irst, RanIt last, Pred pr);第一个sort函数first,last）间迭代器指示的元素数据按升序排列，第二个sort函数定义了比较函数pr(x,y)代替了operator(x,y), 功能是相似的。与sort函数相比，和它的名字一样，属于稳定排序。partial_sort原型：template void partial_sort(RanIt first, RanIt middle, RanIt last); template void partial_sort(RanIt first, RanIt middle, RanIt last, Pred pr);该函数实现了

6、局部元素排序功能。对first, last）间的元素排序结束后，仅前middle-first-1个元素是必须按要求排好序的，其它元素不一定是排好序的。即：对任意N0,middle-first，M(N,last-first),都有*(first+N)*(first+M)。第二个函数与第一个函数相比定义了比较函数pr(x,y)代替了operator, 功能是相似的。partial_sort_copy原型：template RanIt partial_sort_copy(InIt first1, InIt last1,RanIt first2, RanIt last2); template RanI

7、t partial_sort_copy(InIt first1, InIt last1,RanIt first2, RanIt last2, Pred pr);该函数功能是: 与partial_sort相比有两点主要不同：（1）排序结果可以输出到另外一个容器（当然也可自身容器）；（2）partial_sort函数中直接给出了middle值，而该函数middle值是计算出来的。middle=min(last1-first1,last2-first2)+first1。之后：对任意N0,middle-first1，M(N,last1-first1),都有*(first2+N)*(first1+M)。

8、第二个函数与第一个函数相比定义了比较函数pr(x,y)代替了operator, 功能是相似的。10.1.2 示例分析示例分析【例10.1】利用sort对整形向量升序排序#include #include #include using namespace std;int main(int argc, char* argv)int a = 1,8,6,10,4;vector v(a, a+5);sort(v.begin(), v.end();cout 升序排序结果是: endl;copy(v.begin(), v.end(), ostream_iterator(cout, t);/1 4 6 8

9、10return 0;n【例10.2】对学生成绩进行升序排列#include #include #include #include using namespace std;class Studentpublic:int NO;/学号string name;int grade; /成绩Student(int NO, string name, int grade)this-NO = NO;this-name = name;this-grade = grade;bool operator(const Student &s) constreturn grade s.grade;ostream&

10、amp; operator (ostream& os, const Student& s)os s.NO t t s.grade;return os;int main(int argc, char* argv)n【例10.3】利用partial_sort取整形向量最小的4个元素。#include #include #include using namespace std;void main()int a = 10,1,3,9,7,6,2,4,5,8;vector v(a, a+10);cout 原始向量数据:;copy(v.begin(), v.end(), os

11、tream_iterator(cout, t);cout endl;partial_sort(v.begin(), v.begin()+4, v.end() ;cout partial_sort后(前4个元素按升序排列): ;copy(v.begin(), v.end(), ostream_iterator(cout, t);cout endl;n【例10.4】求成绩最好的3位同学。#include #include #include #include #include using namespace std;class Studentpublic:int NO;/学号string name;

12、int grade; /成绩Student() Student(int NO, string name, int grade)this-NO = NO;this-name = name;this-grade = grade;bool operator(const Student &s) constreturn grade s.grade;void main() vector v ;Student s1(101, aaa, 90);Student s2(102, bbb, 80);Student s3(103, ccc, 60);n【例10.5】list容器排序问题。#include #

13、include #include using namespace std;void main()int a = 10,1,3,9,7,6,2,4,5,8;list l(a, a+10);/sort(l.begin(), l.end(); /这一行是错误的l.sort();/这一行正确copy(l.begin(), l.end(), ostream_iterator(cout, t);/1 2 3 4 5 6 7 8 9 10n注释行的程序是错误的，说明list容器不能用sort通用排序算法。这是由于sort需要的是随机迭代器，方便排序算法中的数据交换，而list提供的仅是双向迭代器。因此要想排

14、序，只能用list类本身提供的sort函数，它有两种形式，已经在第6章6.3节list容器中简单讲过。如果要想让示例中元素降幂排列，如下调用就可以了：l.sort(greater()。当然也可以定义自定义二元函数。10.2 第n个元素10.2.1 主要函数主要函数nth_element原型: template void nth_element(RanIt first, RanIt nth, RanIt last); template void nth_element(RanIt first, RanIt nth, RanIt last, Pred pr); 该函数的功能是：在first, la

15、st)指示的元素中，找第n个满足条件的元素，结果反映在RanIt nth表示的迭代器指针中。例如：班上有10个学生，我想知道分数排在倒数第4名的学生。如果要满足上述需求，可以用sort排好序，然后取第4位（因为是由小到大排), 更聪明的会用partial_sort, 只排前4位，然后得到第4位。其实这时你还是浪费，因为前两位你根本没有必要排序，此时，你就需要nth_element。两个函数功能相近，第一个默认重载operate，第2个可定义二元函数对象。10.2.2 示例分析示例分析【例例10.6】求第求第3个成绩最好的学生个成绩最好的学生#include #include #include

16、#include #include using namespace std;class Studentpublic:int NO;/学号string name;int grade; /成绩Student(int NO, string name, int grade)this-NO = NO;this-name = name;this-grade = grade;bool operator(const Student &s) const return grade s.grade;void main() vector v ;Student s1(101, aaa, 90);10.3 二分检

17、索10.2.1 主要函数主要函数lower_bound原型原型: template FwdIt lower_bound(FwdIt first, FwdIt last, const T& val); template FwdIt lower_bound(FwdIt first, FwdIt last, const T& val, Pred pr);该函数功能是该函数功能是:容器元素已经排好序容器元素已经排好序, 在在0, last-first)范围内寻找位置范围内寻找位置N, 对第对第1个模板函数而言：个模板函数而言：*(first+M) =val，也就是说在有序容器中寻找第，

18、也就是说在有序容器中寻找第1个大于等于个大于等于val值的值的位置，若找到返回位置，若找到返回first+N，否则返回，否则返回last；对第；对第2个模板函数而言功能相似，返回第一个不满个模板函数而言功能相似，返回第一个不满足足pr(*(first+M), val)的位置的位置N。upper_bound原型：原型：template FwdIt upper_bound(FwdIt first, FwdIt last, const T& val); template FwdIt upper_bound(FwdIt first, FwdIt last, const T& val,

19、Pred pr);该函数功能是该函数功能是: 容器元素已经排好序容器元素已经排好序, 在在0, last-first)范围内寻找位置范围内寻找位置N, 对第对第1个模板函数而言：个模板函数而言：*(first+M) val是是true, *(first+N)val，也就是说在有序容器中寻找第，也就是说在有序容器中寻找第1个大于个大于val值的位置，若值的位置，若找到返回找到返回first+N，否则返回，否则返回last；对第；对第2个模板函数而言功能相似，返回第一个不满足个模板函数而言功能相似，返回第一个不满足pr(*(first+M), val)的位置的位置N。equal_range原型:

20、template pair equal_range(FwdIt first, FwdIt last,const T& val);template pair equal_range(FwdIt first, FwdIt last,const T& val, Pred pr); 第1个模板函数功能是：在有序元素容器中，找出一对迭代指针midstart, midend，其间的元素都等于val。即：*(midstart+N)=val。如果有结果，结果保存在pair对象中，相当于pair(lower(first, last, val), upper(first,last,val)。第2个

21、模板函数与第1个模板函数功能相近：找出一对迭代指针midstart, midend，其间元素：pr(*(midstart+N), val)都是true。binary_search原型：template bool binary_search(FwdIt first, FwdIt last, const T& val); template bool binary_search(FwdIt first, FwdIt last, const T& val,Pred pr);第1个模板函数是在有序容器中查询*first,last）间有无元素值等于val，若有返回true，若无返回fals

22、e;第2个模板函数是在有序容器中查询*first,last）间有无元素值, 满足：若pr(*(first+N),val)成立则返回true，若无返回false。10.3.2 示例分析【例10.7】已知list容器1,2,2,3,3,3,4,4,4,4，求(1)有无元素5? (2)第1个2元素位置；（2）最后一个元素3的位置；（4）共有多少个元素4？#include #include #include using namespace std;void main()int a = 1,2,2,3,3,3,4,4,4,4;list l1(a, a+10);cout 原始数据a:;copy(l1.be

23、gin(), l1.end(), ostream_iterator(cout, t);cout endl;bool bExist = binary_search(l1.begin(), l1.end(), 5);cout 有元素5吗: (bExist=0?flase:true) endl;list:iterator first2 = lower_bound(l1.begin(), l1.end(),2);/求第1个2位置if(first2 != l1.end() /找到第1个元素2位置cout 第1个2位置: distance(l1.begin(), first2) endl;list:ite

24、rator last3 = upper_bound(l1.begin(), l1.end(),3);/最后1个3之后的指针if(last3 != l1.end() /找到最后1个3位置cout 最后1个3位置: distance(l1.begin(), -last3) endl;10.4 归并10.4.1 主要函数主要函数merge原型：原型：template OutIt merge(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x); template OutIt merge(InIt1 first1, InIt1 la

25、st1,InIt2 first2, InIt2 last2, OutIt x, Pred pr);第第1个模板函数：两个有序容器元素（均按个模板函数：两个有序容器元素（均按operator排序）交替比较，按排序）交替比较，按operate排序后，输出至排序后，输出至x迭代器表示的容器中。另当两个容器中比较元素相同，则第一个容器中元素先输出到迭代器表示的容器中。另当两个容器中比较元素相同，则第一个容器中元素先输出到x代表代表的容器中。若两个容器共有的容器中。若两个容器共有 N个元素合并，则返回个元素合并，则返回x+N。第二个函数与第。第二个函数与第1个函数功能相近，个函数功能相近，只是用二元函数

26、只是用二元函数pr代替了代替了operate。inplace_merge原型：原型：template void inplace_merge(BidIt first, BidIt middle, BidIt last);template void inplace_merge(BidIt first, BidIt middle, BidIt last, Pred pr);第一个模板函数功能是：一个容器分为两部分第一个模板函数功能是：一个容器分为两部分first,middle)、middle,last），每部分都已按），每部分都已按operator排好序，但整体不一定排好序。当进行排好序，但整体不一

27、定排好序。当进行inplace_merge时，时，first,middle)中指向元中指向元素交替与素交替与middle,last）指向元素按）指向元素按operate排序后，放入原容器中。当比较元素相同时，排序后，放入原容器中。当比较元素相同时，first,middle)间元素优先存放。第二个函数与第间元素优先存放。第二个函数与第1个函数功能相近，只是用二元函数个函数功能相近，只是用二元函数pr代替了代替了operate。10.4.2 示例分析【例10.8】合并函数简单示例#include #include using namespace std ;void main()int a = 1,

28、3,5,7;int b = 2,4,6,8;int result8;cout 原始a: endl;copy(a, a+4, ostream_iterator(cout, t); /1 3 5 7cout endl;cout 原始b: endl; copy(b, b+4, ostream_iterator(cout, t);/2 4 6 8cout endl;merge(a, a+4, b, b+4, result);cout a、bmerge后: endl;copy(result, result+8, ostream_iterator(cout,t);/1 2 3 4 5 6 7 8cout

29、endl endl;int c8 = 1,3,4,8,2,5,6,7 ;cout 原始c: endl;copy(c, c+8, ostream_iterator(cout, t);/1 3 4 8 2 5 6 7cout endl;inplace_merge(c, c+4, c+8);cout c inplace_merge后 endl;copy(c, c+8, ostream_iterator(cout, t);/1 2 3 4 5 6 7 8cout endl;10.5 序结构上的集合操作10.4.1 主要函数主要函数includes原型原型: template bool includes

30、(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2);template bool includes(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, Pred pr);第第1个模板函数功能是：两个容器按个模板函数功能是：两个容器按operate已排好序，若容器已排好序，若容器first2, last2)指向的每个元素都在指向的每个元素都在first1,last1)指向的元素范围内，则指向的元素范围内，则first1,last1)代表容器包含代表容器包含first2, last2)代表的

31、容器。第代表的容器。第2个模板函数功能与第一个功能相近：两个容器按个模板函数功能与第一个功能相近：两个容器按pr已排好序，若容器已排好序，若容器first2, last2)指向的每指向的每个元素都在个元素都在first1,last1)指向的元素范围内，则指向的元素范围内，则first1,last1)代表容器包含代表容器包含first2, last2)代表代表的容器。的容器。set_union原型：原型：template OutIt set_union(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x); template

32、OutIt set_union(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x, Pred pr);第第1个模板函数功能是：两个容器个模板函数功能是：两个容器first1,last1）、）、first2,last2）均按）均按operate排好序，两个容器元排好序，两个容器元素交替比较，小的值进入输出容器小素交替比较，小的值进入输出容器小x中，若比较两值相等，则取中，若比较两值相等，则取first1,last1）中的元素。）中的元素。如果有如果有N个元素拷贝到个元素拷贝到x代表的容器中，则返回代表的容器中，则返回x+N。

33、第。第2个模板函数功能与第个模板函数功能与第1个函数功能相个函数功能相近，只不过用二元函数近，只不过用二元函数pr代替了代替了operate。set_intersection原型：template OutIt set_intersection(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x); template OutIt set_intersection(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x, Pred pr);第1个模板函数功能是:

34、两个容器first1,last1）、first2,last2）均按operate排好序，两个容器元素交替比较，若比较两值相等，则取first1,last1）中的元素。如果有N个元素拷贝到x代表的容器中，则返回x+N。第2个模板函数功能与第1个函数功能相近，只不过用二元函数pr代替了operate。set_difference原型：template OutIt set_difference(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x); template OutIt set_difference(InIt1 first

35、1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x, Pred pr);第1个模板函数功能是: 两个容器first1,last1）、first2,last2）均按operate排好序，两个容器元素交替比较，若比较两值相等，则取first1,last1）中的元素。如果有N个元素拷贝到x代表的容器中，则返回x+N。第2个模板函数功能与第1个函数功能相近，只不过用二元函数pr代替了operate。set_symmetric_difference原型：template OutIt set_symmetric_difference(InIt1 first1

36、, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); template OutIt set_symmetric_difference(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x, Pred pr);10.5.2 示例分析【例10.9】集合操作简单示例#include #include #include using namespace std ;void main()int a = 1,2,3,4,5;int b = 1,2,3,6;list l1(a, a+5);li

37、st l2(b, b+4);cout 原始l1:;copy(l1.begin(), l1.end(), ostream_iterator(cout,t);cout endl;cout 原始l2:;copy(l2.begin(), l2.end(), ostream_iterator(cout,t);cout endl;/包含bool bRet = includes(l1.begin(), l1.end(), l2.begin(),l2.end();cout l1包含l2? (bRet=1?yes:no ) endl;/l1并l2list l3;set_union(l1.begin(),l1.e

38、nd(), l2.begin(),l2.end(), back_inserter(l3);cout l1并l2:;copy(l3.begin(), l3.end(), ostream_iterator(cout,t);cout endl;n【例10.10】深入理解序结构集合操作中operator函数作用。已知两个学生集合初始是无序的，要求按学号排序后判定第一个学生集合是否包含第2个学生集合。#include #include using namespace std ;struct Studentint NO;/学号char name20; /姓名bool operator(Student&am

39、p; s)return NOs.NO;void main()bool bRet = true;Student s1 = 1001,zhang,1003,li,1004,wang,1002,zhao;/第1个学生模拟集合Student s2 = 1001,zhang,1004,wang,1002,zhao;/第2个学生模拟集合sort(s1, s1+4);/排序sort(s2, s2+3);/排序bRet = includes(s1, s1+4, s2, s2+3); /判定包含关系cout (bRet=true?s1包含s2:s1不包含s2) endl;n【例10.11】已知学生结构体包含信息

40、:学号(int)、姓名(string)、语文成绩(int)、数学成绩(int)。语文老师形成了一个成绩文件，数学老师形成了一个文件，均已按学号升序排好序。把学生语文成绩与数学成绩合并，形成学生的全信息。如表10.2所示。要考虑某学生某科缺考情况（按0分处理）。语文、数学成绩文件说明语文、数学成绩文件说明语文老师成绩文件d:chinese.txt数学老师成绩文件d:math.txt文本格式：学号 姓名 语文成绩文本格式：学号 姓名 数学成绩 1001 zhang 75 1002 li 85 1003 sun 78 1001 zhang 77 1002 li 87 1003 sun 80 1004

41、 zhao 85此表表明：zhang,li,sun考了语文、数学，zhao考了数学，语文缺考。n程序代码#include #include #include #include #include using namespace std;struct Studentint NO;string name;int chinese;int math;public:bool operator(const Student&s)if(NO = s.NO)math = s.math;return NOs.NO;int main(int argc, char* argv)vector v1;/语文成绩向量

42、vector v2;/数学成绩向量ifstream in1(d:chinese.txt);/打开语文成绩文件ifstream in2(d:math.txt);/打开数学成绩文件10.6 堆操作10.6.1 主要函数主要函数make_heap原型：原型：template void make_heap(RanIt first, RanIt last); template void make_heap(RanIt first, RanIt last, Pred pr);第第1个模板函数功能是个模板函数功能是:把随机迭代器把随机迭代器first, last)间元素按间元素按operator排序，形成一

43、个堆；第排序，形成一个堆；第2个函数个函数与第与第1个函数功能相近，只不过用二元函数个函数功能相近，只不过用二元函数pr代替了代替了operator。pop_heap原型原型: template void pop_heap(RanIt first, RanIt last); template void pop_heap(RanIt first, RanIt last, Pred pr);第第1个模板函数功能是：不是真的把最大（最小）的元素从堆中弹出来。而是重新排序堆。它先把个模板函数功能是：不是真的把最大（最小）的元素从堆中弹出来。而是重新排序堆。它先把first和和last交换，然后将交换，

44、然后将first,last-1)的数据按的数据按operator再做成一个堆。第再做成一个堆。第2个函数与第个函数与第1个函个函数功能相近，只不过用二元函数数功能相近，只不过用二元函数pr代替了代替了operator。push_heap原型: template void push_heap(RanIt first, RanIt last); template void push_heap(RanIt first, RanIt last, Pred pr);第1个模板函数功能是：假设由first,last-1)是一个有效的堆，然后，再把堆中的新元素加进来，按operator做成一个堆。第2个函数

45、与第1个函数功能相近，只不过用二元函数pr代替了operator。sort_heap原型: template void sort_heap(RanIt first, RanIt last); template void sort_heap(RanIt first, RanIt last, Pred pr);第1个模板函数功能是：对first,last)中的序列按operator进行排序, 它假设这个序列是有效堆。当然，经过排序之后就不是一个有效堆了。第2个函数与第1个函数功能相近，只不过用二元函数pr代替了operator。10.6.2 示例分析【例10.12】已知整形序列1,4,2,10,6

46、,5,9,7,8,3，(1)建最大堆；(2)建最小堆；(3)求堆中最大值及次大值。#include #include #include #include using namespace std;void main()int a = 1,4,2,10,6,5,9,7,8,3;cout 原始a: ;copy(a, a+10, ostream_iterator(cout, t);cout endl;vector v1(a, a+10);make_heap(v1.begin(), v1.end(), greater();/形成最小堆cout 最小堆:;copy(v1.begin(), v1.end()

47、, ostream_iterator(cout, t);cout endl;vector v2(a, a+10);make_heap(v2.begin(), v2.end(), less();/形成最大堆cout 最大堆:;copy(v2.begin(), v2.end(), ostream_iterator(cout, t);cout endl;n建最小堆用的二元函数是greater，不是less；建最大堆用的二元函数是less，而不是greater。与常规用到的二元函数语义正好相反。n【例10.13】进一步封装4个堆操作函数，并编制测试类加以测试。#include #include #in

48、clude #include using namespace std;templateclass T,class Pred=less class MyHeapPred pr;vector v;int ValidSize;public:MyHeap(T t, int nSize):v(t, t+nSize)/建立堆ValidSize = nSize;make_heap(v.begin(), v.begin()+ValidSize, pr);void Insert(const T& t)/向堆中新加元素v.push_back(t);ValidSize +;push_heap(v.begin

49、(), v.begin()+ValidSize, pr);bool Remove(T& result)/获得堆中最大值或最小值if(ValidSize = 0)return false;pop_heap(v.begin(), v.begin()+ValidSize, pr);result = *(v.begin()+ValidSize-1);10.7 最大和最小10.7.1 主要函数主要函数min原型：原型：template const T& min(const T& x, const T& y); template const T& min(const

50、 T& x, const T& y, Pred pr);第第1个模板函数功能是：按个模板函数功能是：按operator返回两个元素中较小的一个。第返回两个元素中较小的一个。第2个函数与第个函数与第1个函数功能相近，个函数功能相近，只不过用二元比较函数只不过用二元比较函数pr代替了代替了operator。max原型：原型：template const T& max(const T& x, const T& y); template const T& max(const T& x, const T& y, Pred pr);第第1个模

51、板函数功能是：按个模板函数功能是：按operator返回两个元素中较大的一个。第返回两个元素中较大的一个。第2个函数与第个函数与第1个函数功能相近，个函数功能相近，只不过用二元比较函数只不过用二元比较函数pr代替了代替了operator。min_element原型：template FwdIt min_element(FwdIt first, FwdIt last); template FwdIt min_element(FwdIt first, FwdIt last, Pred pr);第1个模板函数功能是:按operator比较，找出first,last)指向元素的最小值，若设第N个元素是

52、最小值，则返回first+N。第2个函数与第1个函数功能相近，只不过用二元比较函数pr代替了operator。max_element原型：template FwdIt max_element(FwdIt first, FwdIt last); template FwdIt max_element(FwdIt first, FwdIt last, Pred pr);第1个模板函数功能是:按operator比较，找出first,last)指向元素的最大值，若设第N个元素是最大值，则返回first+N。第2个函数与第1个函数功能相近，只不过用二元比较函数pr代替了operator。10.7.2 示例

53、分析示例分析【例10.14】最大和最小函数简单示例#include #include using namespace std;void main()int a = _MIN(10,20);int b = _MAX(10,20);cout min(10,20): a endl;cout max(10,20): b endl;int c=1,10,5,7,9;cout 原始c:; copy(c, c+5, ostream_iterator(cout, t);/1 10 5 7 9cout endl;int *it_min = min_element(c, c+5);int *it_max = ma

54、x_element(c, c+5);cout c最小值: *it_min endl;/1cout c最大值: *it_max endl;/1010.8 词典比较10.8.1 主要函数主要函数lexicographical_compare原型：原型：template bool lexicographical_compare(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2); template bool lexicographical_compare(InIt1 first1, InIt1 last1,InIt2 first2, InIt2

55、last2, Pred pr);第第1个模板函数功能是：该算法比较两个序列中的对应元素个模板函数功能是：该算法比较两个序列中的对应元素e1和和e2(分别来自序列分别来自序列1和序列和序列2)。如果。如果e1e2，则算法立即返回，返回值为真；如果，则算法立即返回，返回值为真；如果e2e1，则算法也立即返回，返回值为假；否则，则算法也立即返回，返回值为假；否则继续对下一对元素进行比较。如果已到达第继续对下一对元素进行比较。如果已到达第1个序列的末尾，但没有到达第个序列的末尾，但没有到达第2个序列的末尾，个序列的末尾，则算法返回，返回值为真；否则返回假。第则算法返回，返回值为真；否则返回假。第2个函

56、数与第个函数与第1个函数功能相近，只不过用二元比个函数功能相近，只不过用二元比较函数较函数pr代替了代替了operator。10.8.2示例分析【例10.15】lexicographical_compare词典比较函数简单示例。void main()int a = 1,2,3;int b = 1,2,2;bool bRet = lexicographical_compare(a, a+3, b, b+3);cout (bRet=1?”ab”) b10.9 排列生成器10.9.1 主要函数主要函数next_permutation原型：原型：template bool next_permutati

57、on(BidIt first,BidIt last); template bool next_permutation(BidIt first, BidIt last,Pred pr)第第1个模板函数功能是：按个模板函数功能是：按operator生成生成first, last)指向容器的下一个词典序排列。第指向容器的下一个词典序排列。第2个函数与第个函数与第1个函数功能相近，只不过用二元比较函数个函数功能相近，只不过用二元比较函数pr代替了代替了operator。prev_permutation原型：原型：template bool prev_permutation(BidIt first,Bi

58、dIt last); template bool prev_permutation(BidIt first, BidIt last,Pred pr)第第1个模板函数功能是：按个模板函数功能是：按operator生成生成first, last)指向容器的上一个词典序排列。第指向容器的上一个词典序排列。第2个函数与第个函数与第1个函数功能相近，只不过用二元比较函数个函数功能相近，只不过用二元比较函数pr代替了代替了operator。10.9.2示例分析示例分析【例10.16】排列生成器简单示例#include #include using namespace std;int main() int

59、A = 2, 3, 4, 5, 6, 1; const int N = sizeof(A) / sizeof(int); cout 初始化: ; copy(A, A+N, ostream_iterator(cout, );/2 3 4 5 6 1 cout endl; prev_permutation(A, A+N); cout prev_permutation后: ; copy(A, A+N, ostream_iterator(cout, );/2 3 4 5 1 6 cout endl; next_permutation(A, A+N); cout next_permutation后: ;

60、 copy(A, A+N, ostream_iterator(cout, );/2 3 4 5 6 1 cout endl;n【例10.17】一个整形6位数由0,0,1,1,2,3组成，编程显示它的全排列。#include #include using namespace std;void main() int a = 0,0,1,1,3,2; sort(a, a+6); if(a0 = 0) int *it = upper_bound(a, a+6 , 0) ; swap(a0, *it); do copy(a, a+6, ostream_iterator(cout, t); cout endl; while(next_permutation(a, a+6);10.10 数值算法10.10.1 主要函数主要函数accumulate原型：原型：template T accumulate(InItfirst