9.1 C++ STL 排序、算數與集合

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)
{
  // 利用較大的組合返回true
  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;
}

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