構(gòu)成
| 頭文件 | 功能 |
|---|---|
<algorithm> |
算法函數(shù) |
<numeric> |
數(shù)值算法 |
<functional> |
函數(shù)對象/仿函數(shù) |
分類
| No. | 分類 | 說明 | |
|---|---|---|---|
| 1 | 非可變序列算法 | Non-modifying sequence operations | 不直接修改容器內(nèi)容的算法。 |
| 2 | 可變序列算法 | Modifying sequence operations | 可以修改容器內(nèi)容的算法。 |
| 3 | 排序算法 | Sorting/Partitions/Binary search/ | 對序列排序、合并、搜索算法操作。 |
| 4 | 數(shù)值算法 | Merge/Heap/Min/max | 對容器內(nèi)容進(jìn)行數(shù)值計算。 |
填充
| 函數(shù) | 作用 |
|---|---|
fill(beg,end,val) |
將值val賦給[beg,end)范圍內(nèi)的所有元素。 |
fill_n(beg,n,val) |
將值val賦給[beg,beg+n)范圍內(nèi)的所有元素。 |
generate(beg,end,func) |
連續(xù)調(diào)用函數(shù)func填充[beg,end)范圍內(nèi)的所有元素。 |
generate_n(beg,n,func) |
連續(xù)調(diào)用函數(shù)func填充[beg,beg+n)范圍內(nèi)的所有元素。 |
-
fill()/fill_n()用于填充相同值，generate()/generate_n()用于填充不同值。
遍歷/變換
| 函數(shù) | 作用 |
|---|---|
for_each(beg,end,func) |
將[beg,end)范圍內(nèi)所有元素依次調(diào)用函數(shù)func，返回func。不修改序列中的元素。 |
transform(beg,end,res,unary) |
將[beg,end)范圍內(nèi)所有元素依次調(diào)用函數(shù)unary，結(jié)果放入res中。 |
transform(beg2,end1,beg2,res,binary) |
將[beg,end)范圍內(nèi)所有元素與[beg2,beg2+end-beg)中所有元素依次調(diào)用函數(shù)unary，結(jié)果放入res中。 |
最大最小
| 函數(shù) | 作用 |
|---|---|
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個)：提供元素排序策略
1 排序
| 函數(shù) | 作用 |
|---|---|
sort(beg,end) |
默認(rèn)升序重新排列元素 |
sort(beg,end,comp) |
使用函數(shù)comp代替比較操作符執(zhí)行sort()。 |
partition(beg,end,pred) |
元素重新排序，使用pred函數(shù)，把結(jié)果為true的元素放在結(jié)果為false的元素之前。 |
stable_sort(beg,end) |
與sort()類似，保留相等元素之間的順序關(guān)系。 |
stable_sort(beg,end,pred) |
使用函數(shù)pred代替比較操作符執(zhí)行stable_sort()。 |
stable_partition(beg,end) |
與partition()類似，保留容器中的相對順序。 |
stable_partition(beg,end,pred) |
使用函數(shù)pred代替比較操作符執(zhí)行stable_partition()。 |
partial_sort(beg,mid,end) |
部分排序，被排序元素個數(shù)放到[beg,end)內(nèi)。 |
partial_sort(beg,mid,end,comp) |
使用函數(shù)comp代替比較操作符執(zhí)行partial_sort()。 |
partial_sort_copy(beg1,end1,beg2,end2) |
與partial_sort()類似，只是將[beg1,end1)排序的序列復(fù)制到[beg2,end2)。 |
partial_sort_copy(beg1,end1,beg2,end2,comp) |
使用函數(shù)comp代替比較操作符執(zhí)行partial_sort_copy()。 |
nth_element(beg,nth,end) |
單個元素序列重新排序，使所有小于第n個元素的元素都出現(xiàn)在它前面，而大于它的都出現(xiàn)在后面。 |
nth_element(beg,nth,end,comp) |
使用函數(shù)comp代替比較操作符執(zhí)行nth_element()。 |
2 反轉(zhuǎn)/旋轉(zhuǎn)
| 函數(shù) | 作用 |
|---|---|
reverse(beg,end) |
元素重新反序排序。 |
reverse_copy(beg,end,res) |
與reverse()類似，結(jié)果寫入res。 |
rotate(beg,mid,end) |
元素移到容器末尾，由mid成為容器第一個元素。 |
rotate_copy(beg,mid,end,res) |
與rotate()類似，結(jié)果寫入res
|
3 隨機(jī)
| 函數(shù) | 作用 |
|---|---|
random_shuffle(beg,end) |
元素隨機(jī)調(diào)整次序。 |
random_shuffle(beg,end,gen) |
使用函數(shù)gen代替隨機(jī)生成函數(shù)執(zhí)行random_shuffle()。 |
查找算法(13個)：判斷容器中是否包含某個值
1 統(tǒng)計
| 函數(shù) | 作用 |
|---|---|
count(beg,end,val) |
利用==操作符，對[beg,end)的元素與val進(jìn)行比較，返回相等元素個數(shù)。 |
count_if(beg,end,pred) |
使用函數(shù)pred代替==操作符執(zhí)行count()。 |
2 查找
| 函數(shù) | 作用 |
|---|---|
find(beg,end,val) |
利用==操作符，對[beg,end)的元素與val進(jìn)行比較。當(dāng)匹配時結(jié)束搜索，返回該元素的InputIterator。 |
find_if(beg,end,pred) |
使用函數(shù)pred代替==操作符執(zhí)行find()。 |
find_first_of(beg1,end1,beg2,end2) |
在[beg1,end1)范圍內(nèi)查找[beg2,end2)中任意一個元素的第一次出現(xiàn)。返回該元素的Iterator。 |
find_first_of(beg1,end1,beg2,end2,pred) |
使用函數(shù)pred代替==操作符執(zhí)行find_first_of()。返回該元素的Iterator。 |
find_end(beg1,end1,beg2,end2) |
在[beg1,end1)范圍內(nèi)查找[beg2,end2)最后一次出現(xiàn)。找到則返回最后一對的第一個ForwardIterator，否則返回end1。 |
find_end(beg1,end1,beg2,end2,pred) |
使用函數(shù)pred代替==操作符執(zhí)行find_end()。返回該元素的Iterator。 |
adjacent_find(beg,end) |
對[beg,end)的元素，查找一對相鄰重復(fù)元素，找到則返回指向這對元素的第一個元素的ForwardIterator。否則返回end。 |
adjacent_find(beg,end,pred) |
使用函數(shù)pred代替==操作符執(zhí)行adjacent_find()。 |
3 搜索
| 函數(shù) | 作用 |
|---|---|
search(beg1,end1,beg2,end2) |
在[beg1,end1)范圍內(nèi)查找[beg2,end2)首一次出現(xiàn)，返回一個ForwardIterator，查找成功,返回[beg1,end1)內(nèi)第一次出現(xiàn)[beg2,end2)的位置，查找失敗指向end1。 |
search(beg1,end1,beg2,end2,pred) |
使用函數(shù)pred代替==操作符執(zhí)行search()。 |
search_n(beg,end,n,val) |
在[beg,end)范圍內(nèi)查找val出現(xiàn)n次的子序列 |
search_n(beg,end,n,val,pred) |
使用函數(shù)pred代替==操作符執(zhí)行search_n()。 |
binary_search(beg,end,val) |
在[beg,end)中查找val，找到返回true。 |
binary_search(beg,end,val,comp) |
使用函數(shù)comp代替比較操作符執(zhí)行binary_search()。 |
4 邊界
| 函數(shù) | 作用 |
|---|---|
lower_bound(beg,end,val) |
在[beg,end)范圍內(nèi)的可以插入val而不破壞容器順序的第一個位置，返回一個ForwardIterator。 |
lower_bound(beg,end,val,comp) |
使用函數(shù)comp代替比較操作符執(zhí)行lower_bound()。 |
upper_bound(beg,end,val) |
在[beg,end)范圍內(nèi)插入val而不破壞容器順序的最后一個位置，該位置標(biāo)志一個大于val的值，返回一個ForwardIterator。 |
upper_bound(beg,end,val,comp) |
使用函數(shù)comp代替比較操作符執(zhí)行upper_bound()。 |
equal_range(beg,end,val) |
返回一對iterator，第一個表示lower_bound，第二個表示upper_bound。 |
equal_range(beg,end,val,comp) |
使用函數(shù)comp代替比較操作符執(zhí)行lower_bound()。 |
刪除和替換算法(15個)
復(fù)制
| 函數(shù) | 作用 |
|---|---|
copy(beg,end,res) |
復(fù)制[beg,end)到res
|
copy_backward(beg,end,res) |
與copy()相同，不過元素是以相反順序被拷貝。 |
移除
| 函數(shù) | 作用 |
|---|---|
remove(beg,end,val) |
刪除[beg,end)內(nèi)所有等于val的元素。注意，該函數(shù)不是真正刪除函數(shù)。 |
remove_if(beg,end,pred) |
刪除[beg,end)內(nèi)pred結(jié)果為true的元素。 |
remove_copy(beg,end,res,val) |
將所有不等于val元素復(fù)制到res，返回OutputIterator指向被拷貝的末元素的下一個位置。 |
remove_copy_if(beg,end,res,pred) |
將所有使pred結(jié)果為true的元素拷貝到res。 |
替換
| 函數(shù) | 作用 |
|---|---|
replace(beg,end,oval,nval) |
將[beg,end)內(nèi)所有等于oval的元素都用nval代替。 |
replace_copy(beg,end,res,oval,nval) |
與replace()類似，不過將結(jié)果寫入res。 |
replace_if(beg,end,pred,nval) |
將[beg,end)內(nèi)所有pred為true的元素用nval代替。 |
replace_copy_if(beg,end,res,pred,nval) |
與replace_if()，不過將結(jié)果寫入res。 |
去重
| 函數(shù) | 作用 |
|---|---|
unique(beg,end) |
清除序列中相鄰重復(fù)元素，不能真正刪除元素。重載版本使用自定義比較操作。 |
unique(beg,end,pred) |
將所有使pred結(jié)果為true的相鄰重復(fù)元素去重。 |
unique_copy(beg,end,res) |
與unique類似，不過把結(jié)果輸出到res。 |
unique_copy(beg,end,res,pred) |
與unique類似，不過把結(jié)果輸出到res。 |
交換
| 函數(shù) | 作用 |
|---|---|
swap(a,b) |
交換存儲在a與b中的值。 |
swap_range(beg1,end1,beg2) |
將[beg1,end1)內(nèi)的元素[beg2,beg2+beg1-end1)元素值進(jìn)行交換。 |
iter_swap(it_a,it_b) |
交換兩個ForwardIterator的值。 |
算術(shù)算法(4個)<numeric>
| 函數(shù) | 作用 |
|---|---|
accumulate(beg,end,val) |
對[beg,end)內(nèi)元素之和，加到初始值val上。 |
accumulate(beg,end,val,binary) |
將函數(shù)binary代替加法運(yùn)算，執(zhí)行accumulate()。 |
partial_sum(beg,end,res) |
將[beg,end)內(nèi)該位置前所有元素之和放進(jìn)res中。 |
partial_sum(beg,end,res,binary) |
將函數(shù)binary代替加法運(yùn)算，執(zhí)行partial_sum()。 |
adjacent_difference(beg1,end1,res) |
將[beg,end)內(nèi)每個新值代表當(dāng)前元素與上一個元素的差放進(jìn)res中。 |
adjacent_difference(beg1,end1,res,binary) |
將函數(shù)binary代替減法運(yùn)算，執(zhí)行adjacent_difference()。 |
inner_product(beg1,end1,beg2,val) |
對兩個序列做內(nèi)積(對應(yīng)元素相乘，再求和)并將內(nèi)積加到初始值val上。 |
inner_product(beg1,end1,beg2,val,binary1,binary2) |
將函數(shù)binary1代替加法運(yùn)算,將binary2代替乘法運(yùn)算，執(zhí)行inner_product()。 |
關(guān)系算法(4個)
| 函數(shù) | 作用 |
|---|---|
equal(beg1,end1,beg2) |
判斷[beg1,end1)與[beg2,end2)內(nèi)元素都相等 |
equal(beg1,end1,beg2,pred) |
使用pred函數(shù)代替默認(rèn)的==操作符。 |
includes(beg1,end1,beg2,end2) |
判斷[beg1,end1)是否包含[beg2,end2)，使用底層元素的<操作符，成功返回true。重載版本使用用戶輸入的函數(shù)。 |
includes(beg1,end1,beg2,end2,comp) |
將函數(shù)comp代替<操作符，執(zhí)行includes()。 |
lexicographical_compare(beg1,end1,beg2,end2) |
按字典序判斷[beg1,end1)是否小于[beg2,end2) |
lexicographical_compare(beg1,end1,beg2,end2,comp) |
將函數(shù)comp代替<操作符，執(zhí)行lexicographical_compare()。 |
mismatch(beg1,end1,beg2) |
并行比較[beg1,end1)與[beg2,end2)，指出第一個不匹配的位置，返回一對iterator，標(biāo)志第一個不匹配元素位置。如果都匹配，返回每個容器的end。 |
mismatch(beg1,end1,beg2,pred) |
使用pred函數(shù)代替默認(rèn)的==操作符。 |
集合算法(6個)
| 函數(shù) | 作用 |
|---|---|
merge(beg1,end1,beg2,end2,res) |
合并[beg1,end1)與[beg2,end2)存放到res。 |
merge(beg1,end1,beg2,end2,res,comp) |
將函數(shù)comp代替<操作符，執(zhí)行merge()。 |
inplace_merge(beg,mid,end) |
合并[beg,mid)與[mid,end)，結(jié)果覆蓋[beg,end)。 |
inplace_merge(beg,mid,end,cmp) |
將函數(shù)comp代替<操作符，執(zhí)行inplace_merge()。 |
set_union(beg1,end1,beg2,end2,res) |
取[beg1,end1)與[beg2,end2)元素并集存放到res。 |
set_union(beg1,end1,beg2,end2,res,comp) |
將函數(shù)comp代替<操作符，執(zhí)行set_union()。 |
set_intersection(beg1,end1,beg2,end2,res) |
取[beg1,end1)與[beg2,end2)元素交集存放到res。 |
set_intersection(beg1,end1,beg2,end2,res,comp) |
將函數(shù)comp代替<操作符，執(zhí)行set_intersection()。 |
set_difference(beg1,end1,beg2,end2,res) |
取[beg1,end1)與[beg2,end2)元素內(nèi)差集存放到res。 |
set_difference(beg1,end1,beg2,end2,res,comp) |
將函數(shù)comp代替<操作符，執(zhí)行set_difference()。 |
set_symmetric_difference(beg1,end1,beg2,end2,res) |
取[beg1,end1)與[beg2,end2)元素外差集存放到res。 |
排列組合算法(2個)：提供計算給定集合按一定順序的所有可能排列組合
| 函數(shù) | 作用 |
|---|---|
next_permutation(beg,end) |
取出[beg,end)內(nèi)的下移一個排列。 |
next_permutation(beg,end,comp) |
將函數(shù)comp代替<操作符，執(zhí)行next_permutation()。 |
prev_permutation(beg,end) |
取出[beg,end)內(nèi)的上移一個排列。 |
prev_permutation(beg,end,comp) |
將函數(shù)comp代替<操作符，執(zhí)行prev_permutation()。 |
堆算法(4個)
| 函數(shù) | 作用 |
|---|---|
make_heap(beg,end) |
把[beg,end)內(nèi)的元素生成一個堆。 |
make_heap(beg,end,comp) |
將函數(shù)comp代替<操作符，執(zhí)行make_heap()。 |
pop_heap(beg,end) |
重新排序堆。它把first和last-1交換，然后重新生成一個堆?？墒褂萌萜鞯腷ack來訪問被"彈出"的元素或者使用pop_back進(jìn)行真正的刪除。并不真正把最大元素從堆中彈出。 |
pop_heap(beg,end,comp) |
將函數(shù)comp代替<操作符，執(zhí)行pop_heap()。 |
push_heap(beg,end) |
假設(shè)first到last-1是一個有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向該函數(shù)前，必須先把元素插入容器后。 |
push_heap(beg,end,comp) |
將函數(shù)comp代替<操作符，執(zhí)行push_heap()。 |
sort_heap(beg,end) |
對[beg,end)內(nèi)的序列重新排序。 |
sort_heap(beg,end,comp) |
將函數(shù)comp代替<操作符，執(zhí)行push_heap()。 |
