簡(jiǎn)介

algorithm頭文件是C++的標(biāo)準(zhǔn)算法庫(kù)，它主要應(yīng)用在容器上。 因?yàn)樗械乃惴ǘ际峭ㄟ^(guò)迭代器進(jìn)行操作的，所以算法的運(yùn)算實(shí)際上是和具體的數(shù)據(jù)結(jié)構(gòu)相分離的 ，也就是說(shuō)，具有低耦合性。 因此，任何數(shù)據(jù)結(jié)構(gòu)都能使用這套算法庫(kù)，只要它具有相應(yīng)的迭代器類型。

算法類別

如上圖所示，庫(kù)中的算法主要分為4類：

1. 非修改性順序操作（Non-modifying sequence operations）
2. 可變順序操作（Mutating sequence operations）
3. 排序和關(guān)系操作（Sorting and related operations）
4. C庫(kù)算法（C library algorithms）

用過(guò)這個(gè)算法庫(kù)的人都知道，里面的很多算法都是成對(duì)出現(xiàn)的，一個(gè)概念的算法經(jīng)常有多個(gè)版本:

• in-place version: 普通版本，直接操作對(duì)迭代器進(jìn)行操作。
• copying version: 拷貝版本，需要傳入輸出迭代器作為拷貝的destination。 該版本一般帶有copy字樣。
• predicate version: 謂詞版本，需要傳入謂詞作為判斷的標(biāo)準(zhǔn)。 該版本一般帶有if字樣。

Non-modifying sequence operations

• all_of ： 判斷是否范圍內(nèi)的所有元素都滿足條件。
• any_of ： 判斷是否范圍內(nèi)的所有元素中有一個(gè)滿足條件。
• none_of ： 判斷是否范圍內(nèi)的所有元素中沒(méi)有一個(gè)滿足條件。
• for_each ： 對(duì)指定范圍內(nèi)的每一個(gè)元素進(jìn)行指定的操作。
• find、find_if、find_if_not ： 在指定范圍中查找滿足某個(gè)條件（值相等、條件滿足、條件不滿足）的元素。
• find_end ： 在指定序列中查找最后一個(gè)相等（或滿足謂詞條件）子序列。
• find_first_of ： 在指定序列中查找第一個(gè)出現(xiàn)在另一個(gè)序列中（或滿足謂詞條件）的元素。
• adjacent_find ： 在指定序列中查找第一個(gè)相等（值相等、滿足條件）的元素對(duì)（2個(gè)元素）。
• count、count_if ： 對(duì)制定序列中的滿足條件（值相等、滿足條件）的元素進(jìn)行計(jì)數(shù)。
• mismatch ： 給定兩個(gè)元素序列，返回第一個(gè)不匹配（值不相等、不滿足條件）的元素位置，以一個(gè)迭代器對(duì)指出。
• equal ： 判斷兩個(gè)序列是否相等（值相等、滿足謂詞條件）。
• is_permutation ： 判斷是否一個(gè)序列是另一個(gè)序列的排列，即只有排列方式不相等（值不相等、不滿足謂詞條件）。
• search、search_n ： 在給定序列中查找子序列或者n個(gè)重復(fù)的元素序列。

Mutating sequence operations

• copy、copy_n、copy_if、copy_backward ： 拷貝序列、拷貝序列中前n個(gè)元素、拷貝序列中滿足條件的、從后往前拷貝序列。
• move、move_backward ： 移動(dòng)序列、從后往前移動(dòng)序列（移動(dòng)后，任然可以對(duì)源序列進(jìn)行操作，但元素值是未指定的）。
• swap、iter_swap ： 逐元素交換序列、交換兩個(gè)序列。
• transform ： 對(duì)一個(gè) 序列進(jìn)行變換并輸出、對(duì)兩個(gè)序列進(jìn)行變換并輸出（變換通過(guò)自定義謂詞來(lái)實(shí)現(xiàn)）。
• replace、replace_if、replace_copy、replace_copy_if ： 替換滿足條件（值相等、滿足謂詞條件）的元素為給定元素、替換滿足條件的元素并將其拷貝至別處。
• fill、fill_n ： 將給定序列元素填充為給定值、 將給定的前n個(gè)元素填充為給定值。
• generate、generate_n : 用自定義的生成器生成元素，并將這些元素賦值給給定序列或前n個(gè)序列。
• remove、remove_if ： 移除相等或滿足謂詞條件的元素。 注意，若有元素被移除，指向這些元素之后的迭代器的可以使用，但結(jié)果是未指定的（unspecified）。
• unique、unique_copy ： 使序列唯一（即若有重復(fù)元素，保留第一個(gè)，其余全部移除）、是序列唯一并拷貝至目的地。
• reverse、reverse_copy ： 將給定序列逆轉(zhuǎn)、將給定序列逆轉(zhuǎn)并拷貝至目的地。
• rotate、rotate_copy ： 將給定序列左旋轉(zhuǎn)（middle - first）個(gè)元素、將給定序列左旋轉(zhuǎn)（middle - first）個(gè)元素并拷貝。
• shuffle ： 使用均勻隨機(jī)數(shù)生成器將給定序列洗牌（即打亂，重新分布）。

下面幾個(gè)函數(shù)有關(guān)分區(qū)的同一方面，但又功能卻不想上面所列那么相似，故而分開(kāi)敘述：

• is_partition ： 用給定的一元謂詞判斷給定序列是否被正確分區(qū)（即前一部分元素調(diào)用謂詞返回true，后一部分返回false）。
• partition ： 對(duì)給定序列進(jìn)行分區(qū)操作。
• stable_partition ： 與partition操作相似，但是兩個(gè)group（即分區(qū)成的兩個(gè)分區(qū)）內(nèi)元素的相關(guān)順序保持不變（stable）。
• partition_copy ： 與partition相似，但是兩個(gè)分區(qū)group結(jié)果被拷貝到兩個(gè)指定的位置。
• partition_point ： 返回分區(qū)點(diǎn)，該點(diǎn)之前、該點(diǎn)之后（包括該點(diǎn)）分別為兩個(gè)分區(qū)。

Sorting and related operations

這些函數(shù)都有兩個(gè)版本：使用operator < 的、使用函數(shù)子Compare的。

• sort ： 排序。
• stable_sort ： 穩(wěn)定排序。
• partial_sort ： 部分排序，對(duì)于給定的序列，只排序前middle - first個(gè)元素，并將它們放置在[first， middle）范圍中，剩余位置的元素順序?yàn)橹付ā?/li>
• partial_sort_copy ： paartial_sort函數(shù)的copy版本。
• is_sorted、is_sorted_util ： 判斷給定序列是否為已排序（使用operator < 或 自定義函數(shù)子判斷）的。
• nth_element ： 將nth迭代器指定的位置排序?yàn)榻Y(jié)果元素。(實(shí)際上應(yīng)該是使用快排實(shí)現(xiàn)的)
• lower_bound、upper_bound、equal_range ： 返回下界、上界、相等性范圍。
• binary_search ： 在給定序列中對(duì)元素進(jìn)行二分查找。
• merge、inplace_merge ： 合并兩個(gè)序列并輸出。
• includes ： 判斷是否一個(gè)序列重的所有元素都被包含在另一個(gè)序列中。
• set_union ： 并集。
• set_intersection ： 交集。
• set_difference ： 差集。
• set_symmetric_difference ： 對(duì)稱差集。
• push_heap ： 將一個(gè)元素push進(jìn)由序列表示的heap中，并維持堆得性質(zhì)。
• pop_heap ： 將一個(gè)元素從heap中pop（實(shí)際上被交換到尾部）。
• make_heap ： 將給定序列構(gòu)造成heap。
• sort_heap ： 對(duì)給定堆進(jìn)行排序（可能有特殊的算法對(duì)堆排序進(jìn)行優(yōu)化）。
• is_heap、is_heap_util ： 判斷給定序列是否為堆、判斷給定序列到哪個(gè)位置之前為堆。
• min、max ： 返回最小值、最大值。
• minmax ： 返回pair
• min_element、max_element ： 返回序列中第一個(gè)最小值、最大值。
• minmax_element ： 返回pair
• lexicographical_compare ： 對(duì)兩個(gè)序列進(jìn)行字典序排序。
• next_permutation、prev_permutation : 判斷給定序列是否存在下一個(gè)或者上一個(gè)組合（所有可能的排列組合先由字典序排序，再進(jìn)行判斷）。

C library algorithms

該頭文件還包含了標(biāo)準(zhǔn)C頭文件stdlib.h，大體相同。 只是出于與C兼容的目的，bsearch 和 qsort同時(shí)包含了C和C++的兩個(gè)函數(shù)簽名。

最新評(píng)論