第14章标准库中的算法

1、C+程序设计实例教程程序设计实例教程第第14章章 标准库中的算法标准库中的算法 C+语言标准库中，使用函数模板实现了一些算法。这些算法用于对容器中的元素进行增、删、改、查等操作。 本章介绍STL中68个算法的使用。C+程序设计实例教程程序设计实例教程知识体系知识体系本章要点：本章要点：14.1算法概述算法概述 14.2accumulate、inner_product、partial_sum和和adjacent_difference 14.3copy和和copy_backward 14.4count、count_if、fill、fill_n、generate和和generate_n 14.5so

2、rt、stable_sort、partition、stable_partition、partial_sort、partial_sort_copy、nth_element和和random_shaffle 14.6adjacent_find、find、find_if、find_first_of、find_end 、search、search_n 、equal、mismatch和和lexicographical_campare C+程序设计实例教程程序设计实例教程知识体系知识体系本章要点：本章要点：14.7binary_search、lower_bound、upper_bound和和equal_ra

3、nge 14.8merge、inplace_merge、unique和和unique_copy 14.9includes、set_intersection、set_union、set_difference和和set_symmertric_difference 14.10 remove、remove_if、remove_copy、remove_copy_if、replace、replace_if、replace_copy和和replace_copy_if 14.11 reverse、reverse_copy、rotate、rotate_copy、swap、iter_swap和和swap_rang

4、esC+程序设计实例教程程序设计实例教程知识体系知识体系本章要点：本章要点： 14.12next_permutation和和prev_permutation 14.13min_element和和max_element 14.14push_heap、pop_heap、make_heap和和sort_heap 14.15for_each和和transform C+程序设计实例教程程序设计实例教程14.1 算法概述算法概述 在STL中，针对不同容器的相同操作而设计的一些函数模板，被称为算法。STL中的算法是通过迭代器间接访问容器元素而实现的，一个算法可以作用于多个不同的容器，甚至可以用于普通的数组，

5、因此，这些算法是“通用”的。 值得注意的是，本章介绍的算法可能会与上一章容器类模板中的成员函数同名，实现的操作也是相似的。 另外，STL中的算法通过迭代器间接访问容器元素时，经常会使用两个迭代器确定容器中的一段连续元素，一个迭代器指向这段连续元素中的首个元素，首个元素，另一个迭代器指向这段连续元素中的最后一个元素的下一个位置最后一个元素的下一个位置，而不是指向最后一个元素。 C+程序设计实例教程程序设计实例教程14.2 accumulate、inner_product、partial_sum和和adjacent_difference 1 /14.1 accumulate、inner_produ

6、ct、partial_sum和和adjacent_difference14 void print(int* arr, int len,const char* str)15 16 coutstr;17 for(int i=0;ilen;+i)18 coutarri ;19 coutendl;20 21 int f1(int a,int b)22 23 if(b%2)24 a+=b;25 return a;26 27 int f2(int a,int b)28 29 return a*b;30 C+程序设计实例教程程序设计实例教程32 int main()33 int a1=1,2,3,4,5;3

7、5 print(a1,5,a1:);36 coutaccumulate(a1,a1+5,100)=accumulate(a1,a1+5,100)endl;37 coutaccumulate(a1,a1+5,0,f1)=accumulate(a1,a1+5,0,f1)endl;38 cout-endl;40 coutinner_product(a1,a1+5,a1,0)=inner_product(a1,a1+5,a1,0)endl;41 coutinner_product(a1,a1+5,a1,0,minus(),divides()=42 inner_product(a1,a1+5,a1,0,

8、minus(),divides()endl;43 cout-endl;45 int a25;46 partial_sum(a1,a1+5,a2);47 print(a2,5,a2:);48 partial_sum(a1,a1+5,a2,f2);49 print(a2,5,a2:);50 cout-endl;52 adjacent_difference(a1,a1+5,a2);53 print(a2,5,a2:);54 adjacent_difference(a1,a1+5,a2,f2);55 print(a2,5,a2:);56 cout-endl;58 return 0;59 显示结果：显示

9、结果：a1:1 2 3 4 5accumulate(a1,a1+5,100)=115accumulate(a1,a1+5,0,f1)=9-inner_product(a1,a1+5,a1,0)=55inner_product(a1,a1+5,a1,0,minus(),divides()=-5-a2:1 3 6 10 15a2:1 2 6 24 120-a2:1 1 1 1 1a2:1 2 6 12 20-C+程序设计实例教程程序设计实例教程14.3 copy和和copy_backward 1 /14.2 copy和和copy_backword 2 #include9 void print(in

10、t* arr, int len,const char* str)10 11 coutstr;12 for(int i=0;ilen;+i)13 coutarri ;14 coutendl;15 17 int main()18 19 int a1=1,2,3,4,5;20 int a25,a35;21 copy(a1,a1+5,a2);22 copy_backward(a1,a1+5,a3+5);23 print(a2,5,a2:);24 print(a3,5,a3:);25 26 return 0;27 显示结果：显示结果：a2:1 2 3 4 5a3:1 2 3 4 5C+程序设计实例教程程

11、序设计实例教程14.4 count、count_if、fill、fill_n、generate和和generate_n 1 /14.3 count、count_if、fill、fill_n、generate和和generate_n13 void print(int* arr, int len,const char* str)14 15 coutstr;16 for(int i=0;ilen;+i)17 coutarri ;18 coutendl;19 20 bool less_3(int n)21 22 return n3;23 24 int gen()25 26 static int a=0

12、;27 return +a;28 C+程序设计实例教程程序设计实例教程30 int main()31 32 int a=1,2,3,2,2;33 print(a,5,a:);34 coutcount(a,a+5,2):count(a,a+5,2)endl;35 coutcount_if(a,a+5,less_3):count_if(a,a+5,less_3)endl;36 cout-endl;37 38 fill(a,a+5,10);39 print(a,5,a:);40 fill_n(a+2,3,20);41 print(a,5,a:);42 cout-endl;43 44 generate

13、(a,a+5,gen);45 print(a,5,a:);46 generate_n(a+2,3,gen);47 print(a,5,a:);48 cout-endl;49 50 return 0;51 显示结果：显示结果：a:1 2 3 2 2count(a,a+5,2):3count_if(a,a+5,less_3):4-a:10 10 10 10 10a:10 10 20 20 20-a:1 2 3 4 5a:1 2 6 7 8- C+程序设计实例教程程序设计实例教程14.5 sort、stable_sort、partition、stable_partition、partial_sort

14、、partial_sort_copy、nth_element和和random_shaffle 本节介绍与排序有关的算法sort、stable_sort、partition、stable_partition、partial_sort、partial_sort_copy和nth_element，同时，为了每次能为同一个容器中的元素排序，我们还介绍了可将容器中元素随机打乱的算法random_shaffle，以上8个算法均被包含在中。 C+程序设计实例教程程序设计实例教程14.6 adjacent_find、find、find_if、find_first_of、find_end 、search、sea

15、rch_n 、equal、mismatch和和lexicographical_campare 本节介绍与查找、匹配、比较有关的算法adjacent_find、find、find_if、find_first_of、find_end 、search、search_n 、equal、mismatch和lexicographical_campare，这些算法与容器中的元素是否排序无关，它们均被包含在中。 C+程序设计实例教程程序设计实例教程14.7 binary_search、lower_bound、upper_bound和和equal_range 本节介绍与查找有关的算法binary_search、

16、lower_bound、upper_bound和equal_range，这些算法与容器中的元素是否排序有关，即只有容器中元素排好序之后，在该容器上使用算法得到的结果才是正确的。这些算法均被包含在中。 C+程序设计实例教程程序设计实例教程14.8 merge、inplace_merge、unique和和unique_copy 本节介绍与归并和去除重复元素有关的算法merge、inplace_merge、unique和unique_copy，算法merge、inplace_merge与容器中的元素是否排序有关，即只有容器中元素排好序之后，在该容器上使用算法得到的结果才是正确的。算法unique和u

17、nique_copy用于去除容器中的重复元素，虽然容器中的元素不必排好序，但是若想使它们的运算结果正确，就必须保证容器中等值的元素都是连续存放的。另外，这些算法均被包含在中。C+程序设计实例教程程序设计实例教程13.9 includes、set_intersection、set_union、set_difference和和set_symmertric_difference 本节介绍与集合操作有关的算法includes、set_intersection、set_union、set_difference和set_symmertric_difference，这算法只有在所操作容器中元素有序的情况下，

18、才能得到正确结果。另外，这些算法均被包含在中。 C+程序设计实例教程程序设计实例教程14.10 remove、remove_if、remove_copy、remove_copy_if、replace、replace_if、replace_copy和和replace_copy_if 本节介绍与删除和替换有关的算法remove、remove_if、remove_copy、remove_copy_if、replace、replace_if、replace_copy和replace_copy_if，这些算法均被包含在中。 C+程序设计实例教程程序设计实例教程13.11 reverse、reverse_copy、rotate、rotate_copy、swap、iter_swap和和swap_ranges 本节介绍与翻转、旋转和交换有关的算法reverse、reverse_copy、rotate、rotate_copy、swap、iter_swap和swap_ranges，这些算法均被包含在中。 C+程序设计实例教程程序设计实例教程14.12 nex