本篇所有算法源碼均已同步收錄 GitHub 倉庫，歡迎點個小??：https://github.com/rongweihe/CPPNotes/tree/master/STL-source-code-notes
STL 算法博大精深，涵蓋范圍之廣，其算法之大觀，細節之深入，泛型思維之于字里行間，每每閱讀都會有不同的收獲。
STL 將很多常見的邏輯都封裝為現成的算法，熟悉這些算法的使用和實現很多時候可以大大簡化編程。
并且在需要的時候能夠對 STL 進行擴展，將自定義的容器和算法融入到 STL 中。
侯捷大師在書中說到：深入源碼之前，先觀察每一個算法的表現和大觀，是一個比較好的學習方式。
不多 BB，先上思維導圖：
回顧
STL 源碼剖析系列：
基本算法
在 STL 標準規格中，并沒有區分基本算法或復雜算法，然而 SGI 卻把常用的一些算法定義于 <stl_algobase.h>之中，其它算法定義于 <stl_algo.h>中。
常見的基本算法有 equal、fill、fill_n、iter_swap、lexicographical_compare、max、min、mismatch、swap、copy、copy_backward 等。
質變算法和非質變算法
所有的 STL 算法歸根到底，都可以分為兩類。
所謂“質變算法”是指作用在由迭代器[first,last]所標示出來的區間，上運算過程中會更改區間內的元素內容：
比如拷貝(copy)、互換(swap)、替換(replace)、填寫(fill)、刪除(remove)、排列組合(permutation)、分割(partition)。隨機重排(random shuffling)、排序(sort)等算法，都屬于這一類。
而非質變算法是指在運算過程中不會更改區間內的元素內容。比如查找(find)，匹配(search)、計數（count）、遍歷(for_each)、比較(equal_mismatch)、尋找極值(max,min)等算法。
輸入參數
所有泛型算法的前兩個參數都是一對迭代器，通過稱為 first，last 用來標示算法的操作區間。
每一個 STL 算法的聲明，都表現出它所需要的最低程度的迭代器類型。
比如 find() 需要一個 inputiterator ，這是它的最低要求，但同時也可以接受更高類型的迭代器。
如 Forwarditerator、Bidirectionaliterator 或 RandomAcessIterator。
因為，前者都可以看做是一個 inputiterator，而如果你給 find() 傳入一個 Outputiterator，會導致錯誤。
將無效的迭代器傳給某個算法，雖然是一種錯誤，但不保證能夠在編譯器期間就被捕捉出來。
因為所謂“迭代器類型”并不是真實的型別，它們只是function template的一種型別參數。
許多 STL 算法不僅支持一個版本，往往第一個版本算法會采用默認的行為，另一個版本會提供額外的參數，接受一個仿函數，以便采取其它的策略。
例如 unique() 默認情況下會使用 equality 操作符來比較兩個相鄰元素，但如果這些元素的型別并沒有提供，那么便可以傳遞一個自定義的函數（或者叫仿函數）。
知道了這一點，對于想要深入研究源碼的小伙伴們會更好理解一些。
算法的泛型化
將一個表述完整的算法轉化為程序代碼，是一個合格程序員的基本功。
如何將算法獨立于其所處理的數據結構之外，不受數據的牽絆，使得設計的算法在即將處理的未知的數據結構上（也許是 array，也許是 vector，也許是 list，也許是 deque）上，正確地實現所有操作呢？
這就需要進一步思考：關鍵在于只要把操作對象的型別加以抽象化，把操作對象的標示法和區間目標的移動行為抽象化，整個算法也就在一個抽象層面上工作了。
這個過程就叫做算法的泛型化，簡稱泛化。
比如在 STL 源碼剖析這本書里舉了一個 find 的例子，如果一步步改成 template + 迭代器的形式，來說明了泛化的含義。
下面我們就來看看 STL 那些牛批的算法，限于篇幅，算法的代碼沒有貼出。
具體源碼細節可以去開頭的 GitHub 倉庫里研究，還有注釋哦。
構成
| 頭文件 | 功能 |
|---|---|
<algorithm> | 算法函數 |
<numeric> | 數值算法 |
<functional> | 函數對象/仿函數 |
分類
| No. | 分類 | 說明 | |
|---|---|---|---|
| 1 | 非質變算法 | Non-modifying sequence operations | 不直接修改容器內容的算法 |
| 2 | 質變算法 | Modifying sequence operations | 可以修改容器內容的算法 |
| 3 | 排序算法 | Sorting/Partitions/Binary search/ | 對序列排序、合并、搜索算法操作 |
| 4 | 數值算法 | Merge/Heap/Min/max | 對容器內容進行數值計算 |
填充
| 函數 | 作用 |
|---|---|
fill(beg,end,val) | 將值val賦給[beg,end)范圍內的所有元素 |
fill_n(beg,n,val) | 將值val賦給[beg,beg+n)范圍內的所有元素 |
generate(beg,end,func) | 連續調用函數func填充[beg,end)范圍內的所有元素 |
generate_n(beg,n,func) | 連續調用函數func填充[beg,beg+n)范圍內的所有元素 |
fill()/fill_n()用于填充相同值，generate()/generate_n()用于填充不同值。
遍歷/變換
| 函數 | 作用 |
|---|---|
for_each(beg,end,func) | 將[beg,end)范圍內所有元素依次調用函數func，返回func。不修改序列中的元素 |
transform(beg,end,res,func) | 將[beg,end)范圍內所有元素依次調用函數func，結果放入res中 |
transform(beg2,end1,beg2,res,binary) | 將[beg,end)范圍內所有元素與[beg2,beg2+end-beg)中所有元素依次調用函數binnary，結果放入res中 |
最大最小
| 函數 | 作用 |
|---|---|
max(a,b) | 返回兩個元素中較大一個 |
max(a,b,cmp) | 使用自定義比較操作cmp,返回兩個元素中較大一個 |
max_element(beg,end) | 返回一個ForwardIterator，指出[beg,end)中最大的元素 |
max_element(beg,end,cmp) | 使用自定義比較操作cmp,返回一個ForwardIterator，指出[beg,end)中最大的元素 |
min(a,b) | 返回兩個元素中較小一個 |
min(a,b,cmp) | 使用自定義比較操作cmp,返回兩個元素中較小一個 |
min_element(beg,end) | 返回一個ForwardIterator，指出[beg,end)中最小的元素 |
min_element(beg,end,cmp) | 使用自定義比較操作cmp,返回一個ForwardIterator，指出[beg,end)中最小的元素 |
排序算法(12個)：元素排序策略
| 函數 | 作用 |
|---|---|
sort(beg,end) | 默認升序重新排列元素 |
sort(beg,end,comp) | 使用函數comp代替比較操作符執行sort() |
partition(beg,end,pred) | 元素重新排序，使用pred函數，把結果為true的元素放在結果為false的元素之前 |
stable_sort(beg,end) | 與sort()類似，保留相等元素之間的順序關系 |
stable_sort(beg,end,pred) | 使用函數pred代替比較操作符執行stable_sort() |
stable_partition(beg,end) | 與partition()類似，保留容器中的相對順序 |
stable_partition(beg,end,pred) | 使用函數pred代替比較操作符執行stable_partition() |
partial_sort(beg,mid,end) | 部分排序，被排序元素個數放到[beg,end)內 |
partial_sort(beg,mid,end,comp) | 使用函數comp代替比較操作符執行partial_sort() |
partial_sort_copy(beg1,end1,beg2,end2) | 與partial_sort()類似，只是將[beg1,end1)排序的序列復制到[beg2,end2) |
partial_sort_copy(beg1,end1,beg2,end2,comp) | 使用函數comp代替比較操作符執行partial_sort_copy() |
nth_element(beg,nth,end) | 單個元素序列重新排序，使所有小于第n個元素的元素都出現在它前面，而大于它的都出現在后面 |
nth_element(beg,nth,end,comp) | 使用函數comp代替比較操作符執行nth_element() |
反轉/旋轉
| 函數 | 作用 |
|---|---|
reverse(beg,end) | 元素重新反序排序 |
reverse_copy(beg,end,res) | 與reverse()類似，結果寫入res |
rotate(beg,mid,end) | 元素移到容器末尾，由mid成為容器第一個元素 |
rotate_copy(beg,mid,end,res) | 與rotate()類似，結果寫入res |
隨機
| 函數 | 作用 |
|---|---|
random_shuffle(beg,end) | 元素隨機調整次序 |
random_shuffle(beg,end,gen) | 使用函數gen代替隨機生成函數執行random_shuffle() |
查找算法(13個)：判斷容器中是否包含某個值
統計
| 函數 | 作用 |
|---|---|
count(beg,end,val) | 利用==操作符，對[beg,end)的元素與val進行比較，返回相等元素個數 |
count_if(beg,end,pred) | 使用函數pred代替==操作符執行count() |
查找
| 函數 | 作用 |
|---|---|
find(beg,end,val) | 利用==操作符，對[beg,end)的元素與val進行比較。當匹配時結束搜索，返回該元素的InputIterator |
find_if(beg,end,pred) | 使用函數pred代替==操作符執行find() |
find_first_of(beg1,end1,beg2,end2) | 在[beg1,end1)范圍內查找[beg2,end2)中任意一個元素的第一次出現。返回該元素的Iterator |
find_first_of(beg1,end1,beg2,end2,pred) | 使用函數pred代替==操作符執行find_first_of()。返回該元素的Iterator |
find_end(beg1,end1,beg2,end2) | 在[beg1,end1)范圍內查找[beg2,end2)最后一次出現。找到則返回最后一對的第一個ForwardIterator，否則返回end1 |
find_end(beg1,end1,beg2,end2,pred) | 使用函數pred代替==操作符執行find_end()。返回該元素的Iterator |
adjacent_find(beg,end) | 對[beg,end)的元素，查找一對相鄰重復元素，找到則返回指向這對元素的第一個元素的ForwardIterator。否則返回end |
adjacent_find(beg,end,pred) | 使用函數pred代替==操作符執行adjacent_find() |
搜索
| 函數 | 作用 |
|---|---|
search(beg1,end1,beg2,end2) | 在[beg1,end1)范圍內查找[beg2,end2)首一次出現，返回一個ForwardIterator，查找成功,返回[beg1,end1)內第一次出現[beg2,end2)的位置，查找失敗指向end1 |
search(beg1,end1,beg2,end2,pred) | 使用函數pred代替==操作符執行search() |
search_n(beg,end,n,val) | 在[beg,end)范圍內查找val出現n次的子序列 |
search_n(beg,end,n,val,pred) | 使用函數pred代替==操作符執行search_n() |
binary_search(beg,end,val) | 二分查找，在[beg,end)中查找val，找到返回true |
binary_search(beg,end,val,comp) | 使用函數comp代替比較操作符執行binary_search() |
邊界
| 函數 | 作用 |
|---|---|
lower_bound(beg,end,val) | 在[beg,end)范圍內的可以插入val而不破壞容器順序的第一個位置，返回一個ForwardIterator（返回范圍內第一個大于等于值val的位置） |
lower_bound(beg,end,val,comp) | 使用函數comp代替比較操作符執行lower_bound() |
upper_bound(beg,end,val) | 在[beg,end)范圍內插入val而不破壞容器順序的最后一個位置，該位置標志一個大于val的值，返回一個ForwardIterator（返回范圍內第一個大于val的位置） |
upper_bound(beg,end,val,comp) | 使用函數comp代替比較操作符執行upper_bound() |
equal_range(beg,end,val) | 返回一對iterator，第一個表示lower_bound，第二個表示upper_bound |
equal_range(beg,end,val,comp) | 使用函數comp代替比較操作符執行lower_bound() |
刪除和替換算法(15個)
復制
| 函數 | 作用 |
|---|---|
copy(beg,end,res) | 復制[beg,end)到res |
copy_backward(beg,end,res) | 與copy()相同，不過元素是以相反順序被拷貝 |
移除
| 函數 | 作用 |
|---|---|
remove(beg,end,val) | 移除[first,last)區間內所有與val值相等的元素，并不是真正的從容器中刪除這些元素(原容器的內容不會改變)而是將結果復制到一個以result為起始位置的容器中。新容器可以與原容器重疊 |
remove_if(beg,end,pred) | 刪除[beg,end)內pred結果為true的元素 |
remove_copy(beg,end,res,val) | 將所有不等于val元素復制到res，返回OutputIterator指向被拷貝的末元素的下一個位置 |
remove_copy_if(beg,end,res,pred) | 將所有使pred結果為true的元素拷貝到res |
替換
| 函數 | 作用 |
|---|---|
replace(beg,end,oval,nval) | 將[beg,end)內所有等于oval的元素都用nval代替 |
replace_copy(beg,end,res,oval,nval) | 與replace()類似，不過將結果寫入res |
replace_if(beg,end,pred,nval) | 將[beg,end)內所有pred為true的元素用nval代替 |
replace_copy_if(beg,end,res,pred,nval) | 與replace_if()，不過將結果寫入res |
去重
| 函數 | 作用 |
|---|---|
unique(beg,end) | 清除序列中相鄰重復元素，不真正刪除元素。重載版本使用自定義比較操作 |
unique(beg,end,pred) | 將所有使pred結果為true的相鄰重復元素去重 |
unique_copy(beg,end,res) | 與unique類似，不過把結果輸出到res |
unique_copy(beg,end,res,pred) | 與unique類似，不過把結果輸出到res |
交換
| 函數 | 作用 |
|---|---|
swap(a,b) | 交換存儲在a與b中的值 |
swap_range(beg1,end1,beg2) | 將[beg1,end1)內的元素[beg2,beg2+beg1-end1)元素值進行交換 |
iter_swap(it_a,it_b) | 交換兩個ForwardIterator的值 |
算術算法(4個)
| 函數 | 作用 |
|---|---|
accumulate(beg,end,val) | 對[beg,end)內元素之和，加到初始值val上 |
accumulate(beg,end,val,binary) | 將函數binary代替加法運算，執行accumulate() |
partial_sum(beg,end,res) | 將[beg,end)內該位置前所有元素之和放進res中 |
partial_sum(beg,end,res,binary) | 將函數binary代替加法運算，執行partial_sum() |
adjacent_difference(beg1,end1,res) | 將[beg,end)內每個新值代表當前元素與上一個元素的差放進res中 |
adjacent_difference(beg1,end1,res,binary) | 將函數binary代替減法運算，執行adjacent_difference() |
inner_product(beg1,end1,beg2,val) | 對兩個序列做內積(對應元素相乘，再求和)并將內積加到初始值val上 |
inner_product(beg1,end1,beg2,val,binary1,binary2) | 將函數binary1代替加法運算,將binary2代替乘法運算，執行inner_product() |
關系算法(4個)
| 函數 | 作用 |
|---|---|
equal(beg1,end1,beg2) | 判斷[beg1,end1)與[beg2,end2)內元素都相等 |
equal(beg1,end1,beg2,pred) | 使用pred函數代替默認的==操作符 |
includes(beg1,end1,beg2,end2) | 判斷[beg1,end1)是否包含[beg2,end2)，使用底層元素的<操作符，成功返回true。重載版本使用用戶輸入的函數 |
includes(beg1,end1,beg2,end2,comp) | 將函數comp代替<操作符，執行includes() |
lexicographical_compare(beg1,end1,beg2,end2) | 按字典序判斷[beg1,end1)是否小于[beg2,end2) |
lexicographical_compare(beg1,end1,beg2,end2,comp) | 將函數comp代替<操作符，執行lexicographical_compare() |
mismatch(beg1,end1,beg2) | 并行比較[beg1,end1)與[beg2,end2)，指出第一個不匹配的位置，返回一對iterator，標志第一個不匹配元素位置。如果都匹配，返回每個容器的end |
mismatch(beg1,end1,beg2,pred) | 使用pred函數代替默認的==操作符 |
集合算法(6個)
| 函數 | 作用 |
|---|---|
merge(beg1,end1,beg2,end2,res) | 合并[beg1,end1)與[beg2,end2)存放到res |
merge(beg1,end1,beg2,end2,res,comp) | 將函數comp代替<操作符，執行merge() |
inplace_merge(beg,mid,end) | 合并[beg,mid)與[mid,end)，結果覆蓋[beg,end) |
inplace_merge(beg,mid,end,cmp) | 將函數comp代替<操作符，執行inplace_merge() |
set_union(beg1,end1,beg2,end2,res) | 取[beg1,end1)與[beg2,end2)元素并集存放到res |
set_union(beg1,end1,beg2,end2,res,comp) | 將函數comp代替<操作符，執行set_union() |
set_intersection(beg1,end1,beg2,end2,res) | 取[beg1,end1)與[beg2,end2)元素交集存放到res |
set_intersection(beg1,end1,beg2,end2,res,comp) | 將函數comp代替<操作符，執行set_intersection() |
set_difference(beg1,end1,beg2,end2,res) | 取[beg1,end1)與[beg2,end2)元素內差集存放到res |
set_difference(beg1,end1,beg2,end2,res,comp) | 將函數comp代替<操作符，執行set_difference() |
set_symmetric_difference(beg1,end1,beg2,end2,res) | 取[beg1,end1)與[beg2,end2)元素外差集存放到res |
排列組合算法：提供計算給定集合按一定順序的所有可能排列組合
| 函數 | 作用 |
|---|---|
next_permutation(beg,end) | 取出[beg,end)內的下移一個排列 |
next_permutation(beg,end,comp) | 將函數comp代替<操作符，執行next_permutation() |
prev_permutation(beg,end) | 取出[beg,end)內的上移一個排列 |
prev_permutation(beg,end,comp) | 將函數comp代替<操作符，執行prev_permutation() |
堆算法(4個)
| 函數 | 作用 |
|---|---|
make_heap(beg,end) | 把[beg,end)內的元素生成一個堆 |
make_heap(beg,end,comp) | 將函數comp代替<操作符，執行make_heap() |
pop_heap(beg,end) | 重新排序堆。它把first和last-1交換，然后重新生成一個堆。可使用容器的back來訪問被"彈出"的元素或者使用pop_back進行真正的刪除。并不真正把最大元素從堆中彈出 |
pop_heap(beg,end,comp) | 將函數comp代替<操作符，執行pop_heap() |
push_heap(beg,end) | 假設first到last-1是一個有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向該函數前，必須先把元素插入容器后 |
push_heap(beg,end,comp) | 將函數comp代替<操作符，執行push_heap() |
sort_heap(beg,end) | 對[beg,end)內的序列重新排序 |
sort_heap(beg,end,comp) | 將函數comp代替<操作符，執行push_heap() |
參考：
《STL源碼剖析》-侯捷
https://www.jianshu.com/p/eb554b0943ab
感謝你的閱讀，歡迎點贊，在看，留言，加我好友一起交流
。
往期推薦