在 STL 中,演算法就是函數模板。STL 中的演算法大多數是用來對容器進行操作的,如排序、 查詢等。大部分演算法都是在標頭檔案 <algorithm> 中定義的,還有些演算法用於數值處理,定義在標頭檔案 <numeric> 中。
不同的教學對 STL 中的演算法有不同的分類方法。本教學將演算法分為以下七類:
-
不變序列演算法。
-
變值演算法。
-
刪除演算法。
-
變序演算法。
-
排序演算法。
-
有序區間演算法。
-
數值演算法。
本教學介紹前六類演算法。第七類演算法共有三個,除了前面已經介紹過的 accumulate 以外,另外兩個演算法既不常用,講解起來又比較煩瑣,本教學就不介紹了,有需要的讀者可自行查閱相關資料。
有的演算法可能同時屬於多個分類。
許多演算法都是過載的,有不止一個版本。篇幅所限,本教學往往只能列出其中的一個版本。有些演算法也不給出原型,直接通過程式來演示其用法。
實際上,大多數過載的演算法都有兩個版本,其中一個用
==
判斷元素是否相等,或用
<
比較大小;而另一個版本多出來一個型別引數 Pred 以及函數形參 Pred op,該版本通過表示式
op(x, y)
的返回值是 true 還是 false 來判斷 x 是否“等於”y 或者“小於”y。例如,在《C++函數物件詳解》一節中的“應用範例2”中提到的 sort,再如下面有兩個版本的 min_element:
iterate min_element(iterate first, iterate last);
iterate min_element(iterate first, iterate last, Pred op);
min_element 返回區間中最小的元素。第一個版本用
<
比較大小,而第二個版本用自定義的比較器 op 來比較大小,op(x, y) 的值為 true,則說明 x 比 y 小。
類似 sort 和 min_element 這樣有可自定義比較器版本的演算法,在後文的表格中列出時,將加註“(可自定義比較器)”。