跳转至

STL 算法

STL 提供了大約 100 個實現算法的模版函數，基本都包含在 <algorithm> 之中，還有一部分包含在 <numeric> 和 <functional>。完備的函數列表請 參見參考手冊，排序相關的可以參考 排序內容的對應頁面。

  • find：順序查找。find(v.begin(), v.end(), value)，其中 value 為需要查找的值。

  • reverse：翻轉數組、字符串。reverse(v.begin(), v.end()) 或 reverse(a + begin, a + end)。

  • unique：去除容器中相鄰的重複元素。unique(ForwardIterator first, ForwardIterator last)，返回值為指向 去重後 容器結尾的迭代器，原容器大小不變。與 sort 結合使用可以實現完整容器去重。

  • random_shuffle：隨機地打亂數組。random_shuffle(v.begin(), v.end()) 或 random_shuffle(v + begin, v + end)。

    random_shuffle 函數在最新 C++ 標準中已被移除

    random_shuffle 自 C++14 起被棄用，C++17 起被移除。

    在 C++11 以及更新的標準中，您可以使用 shuffle 函數代替原來的 random_shuffle。使用方法為 shuffle(v.begin(), v.end(), rng)（最後一個參數傳入的是使用的隨機數生成器，一般情況使用以真隨機數生成器 random_device 播種的梅森旋轉偽隨機數生成器 mt19937）。

    1
2
3
    // #include <random>
std::mt19937 rng(std::random_device{}());
std::shuffle(v.begin(), v.end(), rng);

  • sort：排序。sort(v.begin(), v.end(), cmp) 或 sort(a + begin, a + end, cmp)，其中 end 是排序的數組最後一個元素的後一位，cmp 為自定義的比較函數。

  • stable_sort：穩定排序，用法同 sort()。

  • nth_element：按指定範圍進行分類，即找出序列中第 \(n\) 大的元素，使其左邊均為小於它的數，右邊均為大於它的數。nth_element(v.begin(), v.begin() + mid, v.end(), cmp) 或 nth_element(a + begin, a + begin + mid, a + end, cmp)。

  • binary_search：二分查找。binary_search(v.begin(), v.end(), value)，其中 value 為需要查找的值。

  • merge：將兩個（已排序的）序列 有序合併 到第三個序列的 插入迭代器 上。merge(v1.begin(), v1.end(), v2.begin(), v2.end() ,back_inserter(v3))。

  • inplace_merge：將兩個（已按小於運算符排序的）：[first,middle), [middle,last) 範圍 原地合併為一個有序序列。inplace_merge(v.begin(), v.begin() + middle, v.end())。

  • lower_bound：在一個有序序列中進行二分查找，返回指向第一個 大於等於 \(x\) 的元素的位置的迭代器。如果不存在這樣的元素，則返回尾迭代器。lower_bound(v.begin(),v.end(),x)。

  • upper_bound：在一個有序序列中進行二分查找，返回指向第一個 大於 \(x\) 的元素的位置的迭代器。如果不存在這樣的元素，則返回尾迭代器。upper_bound(v.begin(),v.end(),x)。

    lower_bound 和 upper_bound 的時間複雜度

    在一般的數組裏，這兩個函數的時間複雜度均為 \(O(\log n)\)，但在 set 等關聯式容器中，直接調用 lower_bound(s.begin(),s.end(),val) 的時間複雜度是 \(O(n)\) 的。

    set 等關聯式容器中已經封裝了 lower_bound 等函數（像 s.lower_bound(val) 這樣），這樣調用的時間複雜度是 \(O(\log n)\) 的。

  • next_permutation：將當前排列更改為 全排列中的下一個排列。如果當前排列已經是 全排列中的最後一個排列（元素完全從大到小排列），函數返回 false 並將排列更改為 全排列中的第一個排列（元素完全從小到大排列）；否則，函數返回 true。next_permutation(v.begin(), v.end()) 或 next_permutation(v + begin, v + end)。

  • prev_permutation：將當前排列更改為 全排列中的上一個排列。用法同 next_permutation。

  • partial_sum：求前綴和。設源容器為 \(x\)，目標容器為 \(y\)，則令 \(y[i]=x[0]+x[1]+\dots+x[i]\)。partial_sum(src.begin(), src.end(), back_inserter(dst))。

使用樣例

  • 使用 next_permutation 生成 \(1\) 到 \(9\) 的全排列。例題：Luogu P1706 全排列問題

    實現 
    1
2
3
4
5
    int N = 9, a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
do {
  for (int i = 0; i < N; i++) cout << a[i] << " ";
  cout << endl;
} while (next_permutation(a, a + N));
    • 使用 lower_bound 與 upper_bound 查找有序數組 \(a\) 中小於 \(x\)，等於 \(x\)，大於 \(x\) 元素的分界線。
    實現 
    1
2
3
4
5
    int N = 10, a[] = {1, 1, 2, 4, 5, 5, 7, 7, 9, 9}, x = 5;
int i = lower_bound(a, a + N, x) - a, j = upper_bound(a, a + N, x) - a;
// a[0] ~ a[i - 1] 為小於x的元素， a[i] ~ a[j - 1] 為等於x的元素，
// a[j] ~ a[N - 1] 為大於x的元素
cout << i << " " << j << endl;
    • 使用 partial_sum 求解 \(src\) 中元素的前綴和，並存儲於 \(dst\) 中。
    實現 
    1
2
3
4
5
    vector<int> src = {1, 2, 3, 4, 5}, dst;
// 求解src中元素的前綴和，dst[i] = src[0] + ... + src[i]
// back_inserter 函數作用在 dst 容器上，提供一個迭代器
partial_sum(src.begin(), src.end(), back_inserter(dst));
for (unsigned int i = 0; i < dst.size(); i++) cout << dst[i] << " ";
    • 使用 lower_bound 查找有序數組 \(a\) 中最接近 \(x\) 的元素。例題：UVa10487 Closest Sums
    實現 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    int N = 10, a[] = {1, 1, 2, 4, 5, 5, 8, 8, 9, 9}, x = 6;
// lower_bound將返回a中第一個大於等於x的元素的地址，計算出的i為其下標
int i = lower_bound(a, a + N, x) - a;
// 在以下兩種情況下，a[i] (a中第一個大於等於x的元素) 即為答案：
// 1. a中最小的元素都大於等於x；
// 2. a中存在大於等於x的元素，且第一個大於等於x的元素 (a[i])
// 相比於第一個小於x的元素 (a[i - 1]) 更接近x；
// 否則，a[i - 1] (a中第一個小於x的元素) 即為答案
if (i == 0 || (i < N && a[i] - x < x - a[i - 1]))
  cout << a[i];
else
  cout << a[i - 1];
    • 使用 sort 與 unique 查找數組 \(a\) 中 第 \(k\) 小的值（注意：重複出現的值僅算一次，因此本題不是求解第 \(k\) 小的元素）。例題：Luogu P1138 第 k 小整數
    實現 
    1
2
3
4
5
    int N = 10, a[] = {1, 3, 3, 7, 2, 5, 1, 2, 4, 6}, k = 3;
sort(a, a + N);
// unique將返回去重之後數組最後一個元素之後的地址，計算出的cnt為去重後數組的長度
int cnt = unique(a, a + N) - a;
cout << a[k - 1];
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用