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;// 局部排序,將數組中的前6個元素進行排序,后面的不排列int middle = 5;  // 指定排序索引,索引從0開始partial_sort(iArray, iArray + middle, iArray + len);for_each(iArray, iArray + len, MyPrint);cout << endl;// 排序并拷貝元素,將iArray中前5個元素排序后拷貝到var中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);// lower_bound 找出不小于某值的有序數組下確界元素int *result1 = lower_bound(iArray, iArray + len, 16);cout << "lower_bound = " << *result1 << endl;// upper_bound 找出大于某值的有序數組上確界元素int *result2 = upper_bound(iArray, iArray + len, 20);cout << "upper_bound = " << *result2 << endl;// equal_range 找出可插入某值的區間元素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;// 剩余 max /min 比較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;// ------------------------------------------------// 求 var1 與 var2 的交集// ------------------------------------------------// 分配最小空間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;// ------------------------------------------------// 求 var1 與 var2 的并集// ------------------------------------------------// 分配最大空間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;// ------------------------------------------------// 求 var1 與 var2 的差集// ------------------------------------------------// 分配最大數組的空間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)
{// 利用較大的組合返回truewhile (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;
}

本文作者： 王瑞
本文鏈接： https://www.lyshark.com/post/bba79f2e.html
版權聲明： 本博客所有文章除特別聲明外，均采用 BY-NC-SA 許可協議。轉載請注明出處！