c++primer第十章泛型算法小結-10

第十章--泛型算法

1、泛型算法簡介

插入，流，反向，移動疊代器，四種标準疊代器。

1， 标準庫沒有為每種容器類型都定義是吸納某些特定操作的成員函數，而是定義了一組泛型算法；自定義的容器類型隻要與标準庫相容，也可以使用這些算法。

2，每個泛型算法的實作獨立于容器，且不依賴于容器存儲的元素類型；

3，算法往往需要通過兩個疊代器周遊一段元素來實作其功能；疊代器支援自增操作符，相等和不等操作符；第二個疊代器為超出末端疊代器，第一個疊代器必須能夠通過自增到達第二個疊代器；

4，泛型算法本身不執行容器操作： 基于疊代器及其操作實作，不急于容器的操作；即算法從不修改基礎容器的大小，即可能會改變存儲在容器中的值，可能會移動元素，但是不會直接添加或者删除元素。 如果需要實作更多的操作，可以使用插入器（也是一種疊代器），但是算法本身不這麼做；

5，泛型算法需包含<algorithm>頭檔案，泛化的算術算法必須包含<numeric>頭檔案。

2、泛型算法分類為：

修改容器的算法，即變化序列算法（mutating-sequence algorithm），如copy()、remove()、replace()、swap()等；

不修改容器的算法，即非變化序列算法（non-mutating-sequence algorithm），如count()、find()等；以及數字型算法。

3、泛型算法函數名字尾：

_if 表示函數采用的操作是在元素上，而不是對元素的值本身進行操作。如“find_if”算法表示查找一些值滿足函數指定條件的元素；而“find”算法則查找特定的值。

_copy表示算法不僅操作元素的值，而且還把修改的值複制到一個目标範圍中。例如"reverser"算法颠倒範圍中元素的排列順序，而"reverse_copy"算法同時把結果複制到目标範圍中。

其它的字尾從英文意思上立即可以認出其意義。

4、泛型算法的構造與使用方法：

所有泛型算法的前兩個實參是一對iterator，通常稱為first和last，它們标出要操作的容器或内置數組中的元素範圍。元素的範圍，包括first，但不包含last的左閉合區間。即：[first,last)，當first==last成立，則範圍為空。

對iterator的屬性，則要求在每個算法聲明中指出，所聲明的是最低要求。如find()算法的最低要求為：InputIterator；還可以傳遞更進階别的疊代子。如：ForwardIterator、BidirectonalIterator及RandomAccessInterator。但不能用OutputInterator。

5、泛型算法分類：

查找算法：有13種查找算法用各種政策去判斷容器中是否存在一個指定值。equal_range()、lower_bound()和upper_bound()提供對半查找形式。

排序和通用整序算法：共有14種排序（sorting）和通用整序（ordering）算法，為容器中元素的排序提供各種處理方法。所謂整序，是按一定規律分類，如分割（partition）算法把容器分為兩組，一組由滿足某條件的元素組成，另一組由不滿足某條件的元素組成。

删除和代替算法：有15種删除和代替算法。

排列組合算法：有2種算法。

排列組合是指全排列。如：三個字元{a，b，c}組成的序列有6種可能的全排列：abc，acb，bac，bca，cab，cba；并且六種全排列按以上順序排列，認為abc最小，cba最大，因為abc是全順序（從小到大）而cba是全逆序（從大到小）。

生成和改變算法：有6種，包含生成（generate），填充（fill）等等。

關系算法：有7種關系算法，為比較兩個容器提供了各種政策，包括相等（equal()），最大（max()），最小（min()）等等。

集合算法：4種集合（set）算法提供了對任何容器類型的通用集合操作。包括并（union），交（intersection），差（difference）和對稱差（symmetric difference）。

堆算法：有4種堆算法。堆是以數組來表示二叉樹的一種形式。标準庫提供大根堆（max_heap），它的每個結點的關鍵字大于其子結點的關鍵字。

算術算法：該類算法有4種，使用時要求包含頭檔案<numeric>。

至于這一章重要的一個内容，疊代器，因為之前有了相應的的博文，是以在這不在重複。