C++ STL(Standard Template Library)是C++标准库中的一个重要组成部分,提供了丰富的模板函数和容器,用于处理各种数据结构和算法。在STL中,排序、算数和集合算法是常用的功能,可以帮助我们对数据进行排序、统计、查找以及集合操作等。
STL提供的这些算法,能够满足各种数据处理和分析的需求。通过灵活使用这些算法,我们可以高效地对数据进行排序、查找和聚合操作,提高代码的性能和可读性。在实际编程中,根据具体问题的需求选择合适的算法,能够更好地发挥STL的优势,提高程序的效率。
9.1 堆排序算法 Sort_heap 算法函数,用于对堆容器进行排序。sort_heap的用法如下:
template<class RandomAccessIterator> void sort_heap (RandomAccessIterator first, RandomAccessIterator last) ;
其中,first、last
是随机访问迭代器,表示待排序的堆容器的范围。sort_heap
函数将[first, last]
范围的堆容器排序,并将排序后的结果存储在相同的容器中。
读者需要注意,sort_heap
函数执行前,必须先使用make_heap
函数对容器进行堆化,然后再利用堆排序算法对其进行排序。
sort_heap函数通过重复执行pop_heap
操作来实现排序。pop_heap
操作从堆顶提取元素,将该元素放到容器的末尾位置;然后重新调整剩余元素的顺序,使之形成新的堆结构。重复执行pop_heap
操作,就可以将堆容器中的所有元素按照递增顺序排序。
#include <iostream> #include <algorithm> #include <vector> using namespace std ; void MyPrint (int val) { cout << val << " " ; }int main (int argc, char * argv[]) { vector <int > var {45 ,76 ,89 ,32 ,11 ,23 ,45 ,9 ,0 ,3 }; for_each(var.begin(), var.end(), MyPrint); cout << endl ; make_heap(var.begin(), var.end()); if (is_heap(var.begin(), var.end())) { sort_heap(var.begin(), var.end()); } for_each(var.begin(), var.end(), MyPrint); system("pause" ); return 0 ; }
9.2 局部排序与复制 Partial_sort 算法函数,用于对指定区间的元素进行部分排序。partial_sort的用法如下:
template<class RandomAccessIterator> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) ;
其中,first、last
是随机访问迭代器,表示待排序序列的范围;middle
是迭代器,表示指定的部分排序位置。partial_sort
函数将[first, last]
范围内的元素进行部分排序,使得从[first, middle)
的元素按照递增顺序排列,其余元素不保证有序。也就是说,middle
之前的元素是排过序的,middle
之后的元素未排序。
由于该函数使用的是堆排序算法。在实现排序功能前,partial_sort
函数首先将元素按照一定规则生成部分堆,然后重复执行pop_heap
操作,将堆顶元素放到middle
前,重新调整剩余元素的顺序,使之形成新的堆结构。重复执行pop_heap
操作,就可以将[first, middle)
范围内的元素按照递增顺序排列。
该算法可实现对容器中部分元素进行排序,还可以将结果拷贝到其他容器中,如下是一个简单的局部排序与排序拷贝案例。
#include <iostream> #include <algorithm> #include <vector> using namespace std ; void MyPrint (int val) { cout << val << " " ; }int main (int argc, char * argv[]) { int iArray[] = { 3 , 4 , 8 , 23 , 56 , 3 , 89 , 0 , 32 , 6 }; const int len = sizeof (iArray) / sizeof (int ); for_each(iArray, iArray + len, MyPrint); cout << endl ; int middle = 5 ; partial_sort(iArray, iArray + middle, iArray + len); for_each(iArray, iArray + len, MyPrint); cout << endl ; vector <int > var (6 ) ; partial_sort_copy(iArray, iArray + 5 , var.begin(), var.end()); for_each(iArray, iArray + 5 , MyPrint); system("pause" ); return 0 ; }
9.3 快速排序算法 Sort 算法函数,用于对序列进行排序。sort的用法如下:
template<class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last) ;
其中,first、last
是随机访问迭代器,表示待排序的序列的范围。sort函数将[first, last]
范围内的元素按照递增顺序排序,并将排序后的结果存储在相同的容器中。sort函数在执行前,需要保证所排序的元素类型支持<
运算符。
sort函数使用的是快速排序算法,在实现排序功能前,sort函数首先会选择[first, last]
范围内的一个元素作为分割基准元素,然后按照分割基准元素将范围内的元素分为两个序列,其中一个序列的元素均小于基准元素,另一个序列的元素均大于等于基准元素。然后对两个序列分别递归调用sort
函数,不断进行分割和排序,直到分割出的序列长度为1,排序就完成了。
#include <iostream> #include <algorithm> #include <vector> #include <functional> using namespace std ; void MyPrint (int val) { cout << val << " " ; }int main (int argc, char * argv[]) { int iArray[] = { 56 , 43 , 22 , 1 , 34 , 7 , 89 , 0 , 43 , 56 }; const int len = sizeof (iArray) / sizeof (int ); sort(iArray, iArray + len); for_each(iArray, iArray + len, [](int val){cout << val << " " ; }); cout << endl ; vector <int > var = { 45 , 76 , 33 , 21 , 7 , 89 , 0 , 34 , 5 , 7 }; sort(var.begin(), var.end(), greater<int >()); for_each(var.begin(), var.end(), MyPrint); system("pause" ); return 0 ; }
9.4 稳定排序算法 Stable_sort 算法函数,用于对序列进行稳定排序。stable_sort的用法如下:
template<class RandomAccessIterator> void stable_sort (RandomAccessIterator first, RandomAccessIterator last) ;
其中,first、last
是随机访问迭代器,表示待排序的序列的范围。stable_sort函数将[first, last]
范围内的元素按照递增顺序排序,并保证相等元素的相对顺序不变,将排序后的结果存储在相同的容器中。
stable_sort函数使用的是归并排序算法,具有良好的稳定性,可以保证相等元素的相对顺序不变。在实现排序功能前,stable_sort
函数首先将序列从中间分成两个子序列,然后分别对两个子序列进行排序,最后归并两个排序好的子序列,形成一个完整的排序序列。
#include <iostream> #include <algorithm> #include <vector> using namespace std ; struct Student { int id; char *name; int score; Student(int _id, char * _name, int _score) { id = _id; name = _name; score = _score; } }; void MyPrint (Student val) { cout << val.id << val.name << val.score << endl ; } bool CompByScore (Student x, Student y) { return x.score < y.score ? 1 : 0 ; } int main (int argc, char * argv[]) { vector <Student> var; var.push_back(Student(1 , "keey" , 90 )); var.push_back(Student(2 , "marry" , 82 )); var.push_back(Student(3 , "lisa" , 70 )); stable_sort(var.begin(), var.end(), CompByScore); for_each(var.begin(), var.end(), MyPrint); system("pause" ); return 0 ; }
9.5 容器归并算法 Merge 算法函数,用于将两个已排序的序列合并成一个有序序列。merge的用法如下:
template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) ;
其中,first1、last1、first2、last2
是输入迭代器,表示待合并的两个已排序序列的范围;result
是输出迭代器,表示合并后的有序序列的目标位置。merge
函数将已排序的两个序列按照递增顺序合并成一个新的有序序列,输出到result
所指向的迭代器位置,并将输出结果的尾后迭代器作为函数的返回值返回。
merge函数使用的是归并排序算法,在实现合并功能前,merge函数首先将输入序列分成若干个小的段,将不同段之间的元素合并成一个有序段,然后再将合并后的所有段依次合并,完成最终的排序结果。
该算法可以实现将两个具有相同升降方向的有序序列(必须有序),合并成另一个有序序列。
#include <iostream> #include <algorithm> #include <functional> using namespace std ; void MyPrint (int val) { cout << val << " " ; }int main (int argc, char * argv[]) { int iArray1[3 ] = { 1 , 2 , 3 }; int iArray2[7 ] = { 4 , 5 , 6 , 7 , 8 , 9 , 10 }; int result[10 ]; merge(iArray1, iArray1 + 3 , iArray2, iArray2 + 7 , result); for_each(result, result + 10 , MyPrint); cout << endl ; int iArray3[5 ] = { 30 , 20 , 15 , 9 , 2 }; int iArray4[4 ] = { 10 , 5 , 3 , 1 }; int result2[9 ]; merge(iArray3, iArray3 + 5 , iArray4, iArray4 + 4 , result2, greater<int >()); for_each(result2, result2 + 9 , MyPrint); cout << endl ; int iArray5[] = { 100 , 80 , 60 , 40 , 20 , 10 , 90 , 70 , 50 , 30 }; const int len = sizeof (iArray5) / sizeof (int ); int middle = 6 ; inplace_merge(iArray5, iArray5 + middle, iArray5 + len, greater<int >()); for_each(iArray5, iArray5 + len, MyPrint); system("pause" ); return 0 ; }
9.6 容器区间查找算法 Bound 算法函数,用于查找序列中指定值的边界位置。bound的用法如下:
template<class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& value) ; template<class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& value) ;
其中,first、last
是迭代器,表示待查找的序列的范围;value
是需要查找的元素的值。lower_bound
函数返回指向序列中第一个不小于value
的元素的迭代器,如果所有元素都小于value
,则返回last;upper_bound
函数返回指向序列中第一个大于value
的元素的迭代器,如果所有元素都不大于value
,则返回last。
读者需要注意,该函数函数执行前,需要保证所输入的序列本身已经是已排序的序列,并且元素类型支持<
运算符。
bound函数使用的是二分查找算法,可以高效地找到指定值的边界位置。lower_bound
函数首先将序列分成若干个小的区间,每个区间内的元素都不大于value;然后在这些区间中继续执行二分查找操作,直到定位到第一个不小于value的元素位置。upper_bound
函数和lower_bound
函数类似,只是在找到不小于value
的元素时,继续向前遍历,直到定位到第一个大于value
的元素位置。
#include <iostream> #include <algorithm> using namespace std ; int main (int argc, char * argv[]) { int iArray[] = { 3 , 6 , 9 , 12 , 13 , 18 , 20 , 27 , 55 , 44 }; const int len = sizeof (iArray) / sizeof (int ); int *result1 = lower_bound(iArray, iArray + len, 16 ); cout << "lower_bound = " << *result1 << endl ; int *result2 = upper_bound(iArray, iArray + len, 20 ); cout << "upper_bound = " << *result2 << endl ; pair <int *, int *> range = equal_range(iArray, iArray + len, 5 ); cout << "lower_bound = " << *range.first << endl ; cout << "upper_bound = " << *range.second << endl ; system("pause" ); return 0 ; }
9.7 最大值/最小值算法 min_element和max_element 算法函数,用于查找序列中的最小元素和最大元素。它们的用法如下:
template<class ForwardIterator> ForwardIterator min_element (ForwardIterator first, ForwardIterator last) ; template<class ForwardIterator> ForwardIterator max_element (ForwardIterator first, ForwardIterator last) ;
其中,first
和last
是迭代器,表示待查找的序列的范围。min_element
函数返回指向序列中最小元素的迭代器,max_element
函数返回指向序列中最大元素的迭代器。
读者需要注意,min_element
和max_element
函数执行前,需要保证所输入的序列本身已经是已排序的序列。另外,为了实现更高效的运行时间,C++ STL中提供了另一个函数模板来查找最大或最小值。它可以在部分或未排序的序列中查找最大或最小的元素:
template <class ForwardIterator , class Compare > ForwardIterator min_element (ForwardIterator first, ForwardIterator last, Compare comp) ; template <class ForwardIterator , class Compare > ForwardIterator max_element (ForwardIterator first, ForwardIterator last, Compare comp) ;
其中,comp是一个可调用函数或函数对象,用于指定元素的比较方法。min_element
和max_element
函数的功能与之前相同,只是增加了一个参数comp,用于指定元素的比较方法。
总之,min_element
和max_element
函数是C++ STL中非常实用的查找函数,可以方便地查找序列中的最小元素和最大元素,并支持自定义的比较方法,实现各种元素查找和排序等操作。
#include <iostream> #include <algorithm> #include <list> using namespace std ; int main (int argc, char * argv[]) { list <int > ls = { 1 , 4 , 5 , 6 , 7 , 2 , 3 , 4 , 9 , 7 , 6 }; cout << *min_element(ls.begin(), ls.end()) << endl ; cout << *max_element(ls.begin(), ls.end()) << endl ; cout << max(100 , 30 ) << endl ; cout << min(1 , -10 ) << endl ; system("pause" ); return 0 ; }
9.8 交集/并集/差集算法 set_intersection、set_union和set_difference 算法函数,分别用于求两个集合的交集、并集和差集。它们的用法如下:
template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) ; template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) ; template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) ;
其中,first1、last1、first2、last2
是输入迭代器,表示待运算的两个集合的范围;result
是输出迭代器,表示运算结果的位置。set_intersection
函数返回两个集合的交集,set_union
函数返回两个集合的并集,set_difference
函数返回两个集合的差集。这些函数将运算结果复制到由result
指定的迭代器范围内,并返回一个指向输出序列尾后位置的迭代器。
读者需要注意,函数执行前,需要保证输入的两个集合已经是有序的集合,并且元素类型支持<
运算符。
set_intersection、set_union和set_difference函数使用的是归并排序的思想,可以高效地计算两个集合的交集、并集和差集。具体实现方式为,从输入集合的第一个元素开始遍历,将两个集合中相同的元素复制到输出序列中(set_intersection),将所有元素(包括重复元素)复制到输出序列中(set_union),将只存在于第一个集合中的元素复制到输出序列中(set_difference)。
#include <iostream> #include <algorithm> #include <vector> #include <iterator> using namespace std ; int main (int argc, char * argv[]) { vector <int > var1 = { 1 ,2 ,3 ,4 ,5 ,23 }; vector <int > var2 = { 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 }; vector <int > vTarget; vTarget.resize(min(var1.size(), var2.size())); vector <int >::iterator itEnd; itEnd = set_intersection(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin()); copy(vTarget.begin(), itEnd, ostream_iterator<int >(cout , " " )); cout << endl ; vTarget.resize(var1.size()+var2.size()); vector <int >::iterator itEnd1; itEnd1 = set_union(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin()); copy(vTarget.begin(), itEnd1, ostream_iterator<int >(cout , " " )); cout << endl ; vTarget.resize(max(var1.size(),var2.size())); vector <int >::iterator itEnd2; itEnd2 = set_difference(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin()); copy(vTarget.begin(), itEnd2, ostream_iterator<int >(cout , " " )); system("pause" ); return 0 ; }
9.9 求容器上/下排列组合 next_permutation和prev_permutation算法函数,用于获取一个序列的下一个或上一个排列。它们的用法如下:
template<class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last) ;template<class BidirectionalIterator> bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last) ;
其中,first
和last
是双向迭代器,表示待排列的序列的起始和终止位置。next_permutation
函数将序列转换为下一个排列,prev_permutation
函数将序列转换为上一个排列,如果没有下一个或上一个排列,则返回false,否则返回true。
next_permutation和prev_permutation函数使用的是字典序算法,即通过比较相邻的排列,从而找到下一个或上一个排列。具体实现方式为,从序列的最后一个元素开始遍历,找到第一个满足a[i]<a[i+1]
的元素a[i]
,然后在i的右边找到最小的元素a[j]
,使得a[j]>a[i]
,将a[i]
和a[j]
互换位置,最后将i右边的元素按升序排列,从而得到下一个排列。prev_permutation
函数实现方式类似,只是将上述步骤中的<
和>
反转即可。
该算法用于对区间元素进行组合排列,选择一个字典顺序更大或更小的排列。
#include <iostream> #include <algorithm> using namespace std ; void MyPrint (int x) { cout << x << " " ; }template <class BidirectionalIter > void nextPermu_sort (BidirectionalIter first, BidirectionalIter last) { while (next_permutation(first, last)){} } int main (int argc, char * argv[]) { int iArray[] = { 3 , 5 , 8 , 1 , 8 , 9 , 3 , 2 , 1 , 9 }; const int len = sizeof (iArray) / sizeof (int ); next_permutation(iArray, iArray + len); for_each(iArray, iArray + len, MyPrint); cout << endl ; prev_permutation(iArray, iArray + len); for_each(iArray, iArray + len, MyPrint); system("pause" ); return 0 ; }
9.10 容器元素求和算法 accumulate、inner_product和partial_sum 算法函数,分别用于计算序列中的累加和、内积和和部分和序列。它们的用法如下:
template<class InputIterator, class T> T accumulate (InputIterator first, InputIterator last, T init) ; template<class InputIterator1, class InputIterator2, class T> T inner_product (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init) ; template<class InputIterator, class OutputIterator> OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result) ;
其中,first、last、first1、last1、first2
是输入迭代器,表示待计算的序列范围;init
是计算的初始值,result
是输出迭代器,表示计算结果的位置。accumulate
函数返回序列中元素的累加和,inner_product
函数返回序列的内积和,partial_sum
函数返回序列的部分和序列。这些函数将计算结果复制到由result
指定的迭代器范围内,并返回一个指向输出序列尾后位置的迭代器。
需要说明的是,accumulate和inner_product函数可以接受一个自定义的二元操作符(比如加法、乘法等),从而实现各种自定义的累加和和内积和的计算。partial_sum函数不需要自定义操作符,固定使用加法运算。
accumulate、inner_product和partial_sum函数使用的都是迭代算法,在遍历序列时进行累加和、内积和和部分和的计算。具体实现方式为,遍历序列中的元素,根据特定的操作符将每个元素进行累加、相乘或相加,从而得到总体的累加和、内积和或部分和序列。
#include <iostream> #include <numeric> #include <algorithm> using namespace std ; void MyPrint (int x) { cout << x << " " ; }int multiply (int x, int y) { return x*y; }int main (int argc, char * argv[]) { int iArray[5 ] = {1 ,2 ,3 ,4 ,5 }; cout << accumulate(iArray, iArray + 5 , 0 ) << endl ; int iArray1[3 ] = { 2 , 5 , 4 }; int iArray2[3 ] = { 10 , 6 , 5 }; cout << inner_product(iArray1, iArray1 + 3 , iArray2, 0 ) << endl ; int iArray3[5 ] = { 1 , 2 , 3 , 4 , 5 }; int result[5 ]; partial_sum(iArray3, iArray3 + 5 , result); for_each(iArray3, iArray3 + 5 , MyPrint); cout << endl ; int result1[5 ]; partial_sum(iArray3, iArray3 + 5 , result1,multiply); for_each(result1, result1 + 5 , MyPrint); system("pause" ); return 0 ; }