別人已經幫你做好的事，就別再自己做了。我們在用的 C++ 其實有提供「標準函式庫（Standard Library，簡稱 STL）」來輔助程式設計者引用各式各樣常用的功能來簡化程式碼，避免寫程式時還要浪費時間寫一堆已經寫過的東西。

讓我們來複習一下在排序演算法時學過的插入排序法演算法：

void selection_sort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        int min_pos = i;
        for (int j = i + 1; j <= n; ++j) {
            if (a[min_pos] > a[j]) {
                min_pos = j;
            }
        }
        if (min_pos != i) { 
            int tmp = a[min_pos];
            a[min_pos] = a[i];
            a[i] = tmp;
        }
    }
}

如果好好運用 <algorithm> 的幫助，就可以簡化成這樣！

void selection_sort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        swap(a[i], *min_element(a + i, a + n + 1));
    }
}

是不是簡潔多了呢？

以下我們就來跟大家介紹幾個在演算法競賽中常用的函式。只要能熟悉的使用函式庫提供的函式，在比賽中往往都會是有利的加速。

<algorithm> 是 C++ 用來提供各式簡易演算法操作的函式庫，在裡面可以找到各種寫程式常常會用到的演算法。

只要在程式的開頭寫上 #include <algorithm> 就可以使用裡面的函式們。

交換兩個元素時，如果總是要花三行寫

int tmp = a;
a = b;
b = tmp;

不覺得很麻煩嗎？

這時候你只要使用

swap(a, b);

就可以乾淨的搞定！

每次要問兩個元素誰小誰大時，總是要多寫一個 if 很麻煩嗎？只要使用

min(a, b);
max(a, b);

就可以分別回傳兩個元素中較小和較大的值，

更進階一點，如果希望一次知道多個元素的最小或最大值時，只要多加一個大括號在外面，例如

min({a, b, c});
max({a, b, c});

就可以了。

不過，如果是要尋找一個陣列的最小值的話怎麼辦？自己寫的話得多開一個變數、寫一個迴圈遍歷元素才能搞定。

但如果使用函式庫的話，在 a[1] ~ a[n] 之間找最小值，就只需要寫

int min_val = *min_element(a + 1, a + n + 1);

需要特別注意的是，min_element 裡面第一個放的參數是「陣列開始位置的指標」，第二個則是「陣列結束位置的後一個位置的指標」。

那前面的 * 是來幹嘛的？這是因為我們偶爾尋找最小值時，不一定只是需要這個最小值的「值」，而是可能會希望知道「最小值位於哪個位置」。因此，min_element 回傳的值其實是「指標」，因此要加一個 * 來把值取出來。

所以，如果想知道位置的話，就可以寫

int min_pos = min_element(a + 1, a + n + 1) - a;

那如果有多個最小值呢？這時候得到的位置會是「最前面的最小值」，也就是從 a[1] 掃到 a[n]，最早碰到的最小值。

最大值的用法也完全一樣，供參考

int max_val = *max_element(a + 1, a + n + 1);
int max_pos = max_element(a + 1, a + n + 1) - a;

程式競賽最重要的武器之一，排序！要把一個序列 a[1] 到 a[n] 排序，用法也跟 min_element 等函式一樣，只要呼叫

sort(a + 1, a + n + 1);

整個序列就會在 $O(n\log n)$ 的時間內被排序好了！是不是很方便呢？

既然有最小、最大，那就有第 $k$ 小！如果要找出一個序列中第 $k$ 小的數字，聰明的讀者應該可以馬上想到以下寫法

sort(a + 1, a + n + 1);
int kth_val = a[k];

這樣的缺點是，時間複雜度是 $O(n\log n)$，但實際上尋找第 $k$ 小可以 $O(n)$ 搞定！因此，nth_element 就實作了足夠快的演算法來完成這件事。

nth_element 的用法與 min_element 有些差別，假設要找第 $k$ 小，可以這樣寫

nth_element(a + 1, a + k, a + n + 1);
int kth_val = a[k];

nth_element 的第一個和第三個參數與 min_element 一樣，而第二個參數就是「第 $k$ 小的值的位置」。

沒錯，nth_element 不直接回傳第 $k$ 小的值，而是讓使用者告訴他第 $k$ 小的值的位置，之後他就會幫忙把這個值放在這個位置。

更準確的說，讀者可以想像 nth_element 在做的事就是把「排序好後，會出現在第二個參數位置的值放過去」。不僅如此，nth_element 還會額外保證函式執行完後，「第 $1\sim k-1$ 小」會放在第 $k$ 小的值的左邊；「第 $k+1\sim n$ 小」則會放在第 $k$ 小的值的右邊，但不保證排序的順序。舉例來說，如果序列是

3 1 4 1 5 9 2 6

呼叫找第四小的話，一種可能的長相是

1 2 1 "3" 9 4 6 5

在已知第四小的數字是 3 的情況下，3 就會出現在第四個位置，而比較小的數字就會出現在左邊，但順序不一定；反之，比較大的數字就會出現在右邊，順序一樣不一定。

nth_element 在未來優化搜尋演算法時會有妙用，但現階段讀者可以先知道其存在就好。

unique 從字面意義上來看，很像是在「把一樣的數字過濾到只剩一個」，但實際上略有差異。準確的說，unique 在做的事情是「把相鄰一樣的數字過濾到只剩一個」，舉例來說，如果 a[1] 到 a[10] 是

1 3 3 2 4 4 4 3 3 5

呼叫 unique(a + 1, a + 11) 之後會變成

1 3 2 4 3 5 ? ? ? ?

其中 ? 的值代表不重要，這是因為我們需要的就是前六個「過濾完」的值。

但要怎麼知道呼叫完 unique 後，過濾完的值有幾個呢？這時候就要仰賴 unique 的回傳值，在上面的例子中，unique 會回傳的值是 a + 7，其實可以想像成「過濾完後序列結尾的下一個位置」，就跟我們傳入結尾時是一樣的概念。

unique 一個簡單的應用，就是可以真的把一樣的數字過濾掉，要達成這件事，我們勢必得讓所有一樣的數字「相鄰」。這要怎麼做呢？其實只要呼叫 sort 就完事了！也就是說，對於給定的序列 a[1] 到 a[n]，只要先呼叫一次 sort(a + 1, a + n + 1)，再 unique(a + 1, a + n + 1)，就完成一樣數字的過濾了。

<numeric> 很類似 <algorithm>，但專注在提供各式數值相關簡易演算法操作的函式庫，只要牽扯到數值（例如：四則運算），就容易被分類進 <numeric>。

只要在程式的開頭寫上 #include <numeric> 就可以使用裡面的函式們。

計算一個序列 a[1] 到 a[n] 的總和，最直接的做法就是開一個變數紀錄總和、再用一個迴圈掃過所有序列的值並加進變數內。

但 accumulate 可以一行完成總和的計算，用法大致如下：

accumulate(a + 1, a + n + 1, 0);

前兩個參數跟我們前面學的一樣，是序列的開頭和結尾的後一個位置，最後一個參數則是「起始值」，也就是說，accumulate 函式回傳的數值會是「起始值加上整段序列的總和」。

為什麼需要起始值呢？可以想成是其實 C++ 把「開好一個存值的變數」的決定權交給使用者了，讀者可以執行下面這段程式碼看看效果：

int a[3] = {1000000000, 1000000000, 1000000000};
cout << accumulate(a, a + 3, 0) << "\n";

理想上，上面這段程式碼的輸出應該要是 $3\times 10^9$，但實際上，讀者可能會得到 -1294967296 之類的輸出，應該不難猜到，總和吃了整數溢位（overflow），才會輸出不了超過 int 上限的 $3\times 10^9$。

這時候如果是一般跑迴圈算總和的寫法，修正方法應該是把一開始開好的變數設成 long long int。而這就是 accumulate 讓使用者自己給起始值的一種用意，使用者可以直接讓起始值的變數型態是 long long int 來迴避這樣基本的溢位問題。因此，只要改成以下模樣，就可以正常輸出了！

int a[3] = {1000000000, 1000000000, 1000000000};
cout << accumulate(a, a + 3, 0LL) << "\n";

這樣「指定起始值」的功能其實還可以配合自定義運算子（Operator overloading）等來產生一些妙用，但這就稍微進階一些了，這裡不再贅述。

iota 在做的事情其實非常單純，他可以在給定的序列範圍中填入一段連續的數字，例如以下的 code

for (int i = 1; i <= n; ++i)
    a[i] = i;

用 iota 取代的話就是

iota(a + 1, a + n + 1, 1);

前兩個參數跟一樣是序列的開頭和結尾的後一個位置，最後一個參數則是「連續數字的起始值」，代表這個範圍中藥填入的數字開頭是多少。因此，如果要改填入 10 到 n + 9 的話，可以呼叫

iota(a + 1, a + n + 1, 10);

來達成。

有了上述工具可以用確實很方便，但感覺缺少了一點自由度。舉例來說，如果想用 sort 來把數字大到小排序該怎麼辦呢？或甚至複雜一點，如果我們要讓奇數擺前面、偶數擺後面，兩邊再各自比大小怎麼辦呢？又或者我們要排序自定義的 struct，C++ 要怎麼在我們沒有告訴他誰要擺前面的情況下知道要怎麼排序呢？

C++ 為了應付這種情況，其實大多數的函式他都提供了「自定義比較函式」的功能，我們用排序來當例子白話一點的說，還記得我們在排序時介紹過「 基於比較的排序演算法」這個概念嗎？在大多數的排序問題中，程式其實只需要不斷的詢問「元素 $x$ 和元素 $y$ 誰要擺前面？」就可以排出使用者期望的順序，而這個問題預設的答案就是「$x$ 比 $y$ 小的話，就擺前面」。

因此，如果要把數字大排到小的話，只需要把問題的答案改成「$x$ 比 $y$ 大的話，就擺前面」，這樣就好了！

要告訴 C++「誰擺前面」的指示時，使用者需要寫一個 bool 函式，支援傳入兩個元素的值 $x$ 和 $y$ 後，回傳 $x$ 是不是一定要在 $y$ 前面。

大致上會寫出如下的東西，拿大排到小當範例：

bool cmp(int x, int y) {
    return x > y;
}

上述這個函式，會在傳入的 x 比 y 大時回傳 true，也就達成了我們前面說的結果，x 必須要在 y 前面。

而要呼叫 sort 時，排序 a[1] 到 a[n] 只需要寫成

sort(a + 1, a + n + 1, cmp);

也就是在原本呼叫 sort 時在後面多加一個參數負責傳入比較函式，就完成大到小排序的操作了！

再拿自定義 struct 當例子，如果要對自定義的 struct 排序時，可以寫成以下樣子：

struct Data {
    int key;
    Custom_Type something_else;
};

bool cmp(Data a, Data b) {
    return a.key < b.key;
}

這樣一樣對型態是 Data 的序列 a[1] 到 a[n] 排序時，一樣寫

sort(a + 1, a + n + 1, cmp);

就可以完成排序，是不是很方便呢？

bool cmp(int x, int y) {
    return x <= y;
}

自定義比較函式的使用範圍，其實不只有 sort 而已，包含前面提到的 min、min_element、nth_element 其實都適用，可以想成 min 就是指要擺在最前面的元素，nth_element 當然就一樣是把第 $k$ 小的基準想成是利用給予的比較函式排序後的第 $k$ 個位置。

unique 則比較特殊，因為他是要把相鄰一樣的元素過濾掉，所以他的比較函式反而是「詢問兩個元素 $x$ 和 $y$ 是不是一樣？」，這聽起來很奇怪，但其實在一些特殊的狀況下是真的需要自定義的喔！

實作上一樣，比較函式只需要擺在最後面當一個額外的參數就可以了。

再順帶一提，accumulate 其實也可以額外傳入自定義函式，但講起來有點複雜，有興趣的讀者可以去他的說明頁面看看。

以下提供一些題目讓讀者做函式庫的練習。

C++ 提供的內建函式可不只以上這些，只是礙於篇幅，我們這裡只特別挑了一些常用的出來講，更有一些函式需要對演算法有一定程度的認識才好使用，讀者若有興趣，可以參考 https://cppreference.com/ 內 <algorithm> 和 <numeric> 的章節，搞不好可以找到更多可以讓程式碼更簡潔的工具。