STL演算法分類

2020-07-16 10:04:25
在 STL 中,演算法就是函數模板。STL 中的演算法大多數是用來對容器進行操作的,如排序、 查詢等。大部分演算法都是在標頭檔案 <algorithm> 中定義的,還有些演算法用於數值處理,定義在標頭檔案 <numeric> 中。

不同的教學對 STL 中的演算法有不同的分類方法。本教學將演算法分為以下七類:
  1. 不變序列演算法。
  2. 變值演算法。
  3. 刪除演算法。
  4. 變序演算法。
  5. 排序演算法。
  6. 有序區間演算法。
  7. 數值演算法。

本教學介紹前六類演算法。第七類演算法共有三個,除了前面已經介紹過的 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 這樣有可自定義比較器版本的演算法,在後文的表格中列出時,將加註“(可自定義比較器)”。