前言

標(biāo)準(zhǔn)庫定義了許多用于操作序列的算法，大多在algorithm和numeric文件中，大多數(shù)函數(shù)的原理并不復(fù)雜，但是在很多情況下可以替代手寫的情況，甚至更加優(yōu)秀。

這類算法函數(shù)非常多，但是他們都有共同的結(jié)構(gòu)，類似的參數(shù)特性，所以非常好記憶。比如我們最經(jīng)典的std::sort(beg, end, cmp)，其中beg和end為首尾地址，左閉右開，既可以是C指針，也可以是STL線性容器的迭代器。cmp是可選的函數(shù)，用于替代默認(rèn)的<比較規(guī)則。實(shí)際上大多數(shù)函數(shù)基本都是這種形式，記住一個(gè)就是記住一百個(gè)。

摘自C++ Primer附錄

A. 查找算法

簡(jiǎn)單查找

find(beg, end, val)
find_if(beg, end, func1)
find_if_not(beg, end, func1)

find查找序列中第一個(gè)等于val的值，返回其指針或迭代器，在沒有找到時(shí)返回end。

find_if和find相同，不過查找標(biāo)準(zhǔn)變成使謂詞（布爾函數(shù)）返回true的第一個(gè)值。如查找序列中第一個(gè)奇數(shù)：

int a = *std::find(array, array+6, [](int x){
	return x & 1;
});

find_if_not和find_if相反，不過返回的是第一個(gè)使值為假的函數(shù)。

count(beg, end, val)
count_if(beg, end, func1)

count和count_if返回一個(gè)值，表示序列中多少值等于val或滿足func1。

all_of(beg, end, func1)
any_of(beg, end, func1)
none_of(beg, end, func1)

返回布爾值，all_of當(dāng)序列全部滿足時(shí)返回真，any_of在有一個(gè)滿足時(shí)返回真，none_of在全部不滿足時(shí)返回真。序列為空時(shí)，any_of返回假，另外兩個(gè)返回真。

查找重復(fù)值

adjacent_find(beg, end)
adjacent_find(beg, end, func2)
search_n(beg, end, count, val)

adjacent_find返回第一對(duì)相鄰的重復(fù)元素（使用==比較或滿足func為真的元素）的前面那個(gè)，若沒有返回end
search_n返回一個(gè)指針或迭代器，從此位置有count個(gè)相等元素（使用==比較），若沒有返回end

查找子序列

search(beg1, end1, beg2, end2)
find_end(beg1, end1, beg2, end2)
find_first_of(beg1, end1, beg2, end2)

search返回第二個(gè)序列在第一個(gè)序列中出現(xiàn)的位置，find_end相反，返回最后出現(xiàn)的位置，沒有時(shí)返回end1。find_first_of返回的是第二個(gè)序列中任一元素第一次出現(xiàn)在序列一的位置，此時(shí)序列二不是序列，而是充當(dāng)集合。

B. 其他只讀算法

for_each(beg, end, func1)
mismatch(beg1, end1, beg2)
mismatch(beg1, end1, beg2, func2)
equal(beg1, end1, beg2)
equal(beg1, end1, beg2, func2)

對(duì)序列中每個(gè)數(shù)執(zhí)行func1，很好用，很多時(shí)候可以減少代碼量替代for。
mismatch比較兩個(gè)序列中每一個(gè)元素，返回第一組不相等（使用==運(yùn)算符）或使func2為假的位置（是一個(gè)pair），沒有則返回倆end。
equal與mismatch類似，若所有元素相等（滿足mismatch返回end），結(jié)果為true，否則false。

C. 二分查找算法

lower_bound(beg, end, val)
lower_bound(beg, end, val, cmp)
upper_bound(beg, end, val)
upper_bound(beg, end, val, cmp)
equal_range(beg, end, val)
equal_range(beg, end, val, cmp)
binary_search(beg, end, val)
binary_search(beg, end, val, cmp)

老熟了。在序列l(wèi)ower_bound返回第一個(gè)大于等于val的位置，upper_bound返回第一個(gè)大于val的位置，equal_range相當(dāng)于前兩個(gè)加在一起，返回一個(gè)pair，即兩個(gè)函數(shù)的結(jié)果組合，包含一個(gè)值與val全部相等的區(qū)間。

如std::vector<int> a = {1, 2, 3, 3, 3, 4, 5}，lowerbound返回a.begin()+2，upperbound返回a.begin()+5，equal_range返回pair{a.begin()+2, a.begin()+5}。

binary_search只回答序列里是否存在val，存在則返回true，不存在返回false。

以上函數(shù)操作自定義結(jié)構(gòu)時(shí)都只使用<號(hào)，可以使用可選的自定義cmp函數(shù)

D. 只寫算法

fill(beg, end, val)
fill_n(dest, cnt, val)
generate(beg, end, gen)
generate_n(dest, cnt, gen)

fill和fill_n為區(qū)間所有元素賦值val，他們給出區(qū)間所用的參數(shù)不一樣。generate不斷執(zhí)行g(shù)en函數(shù)，將返回值逐個(gè)賦值給區(qū)間。普通版本無返回值，_n版本返回尾指針。

move(beg, end, dest)
copy(beg, end, dest)
copy_n(beg, n, dest)
copy_if(beg, end, dest, func1)

copy和copy_n將范圍元素全部拷貝到dest，copy_if拷貝符合條件的分?jǐn)?shù)。在C++中，應(yīng)該使盡量使用std::fill和std::copy替代memset和memcpy。

move移動(dòng)整個(gè)序列，對(duì)序列每個(gè)值調(diào)用std::move（右值轉(zhuǎn)化），移動(dòng)到dest。

transform(beg, end, dest, func1)
transform(beg1, end1, beg2, dest, func2)

將序列元素調(diào)用func1后存入dest，第二個(gè)版本對(duì)兩個(gè)序列調(diào)用func2后將結(jié)果存入dest。

merge(beg1, end1, beg2, end2, dest, cmp)
inplace_merge(beg, mid, end, cmp)

merge將兩個(gè)有序序列合并，輸出到dest，cmp是可選的自定義比較函數(shù)。這個(gè)函數(shù)相等于歸并排序的合并階段。

inplace_merge將左右的有序序列在原序列中執(zhí)行合并操作，cmp是可選的自定義比較函數(shù)。

iter_swap(iter1, iter2)
swap_ranges(beg1, end1, beg2)

iter_swap交換兩個(gè)迭代器指向的元素，swap_ranges一一交換兩個(gè)序列。

replace(beg, end, oldval, newval)
replace_if(beg, end, func1, newval)
replace_copy(beg, end, beg2, oldval, newval)
replace_copy_if(beg, end, beg2, func1, newval)

將序列中的oldval（或者滿足func1）的元素替換為newval，copy版本將元素寫進(jìn)新序列

copy_backward(beg, end, dest)
move_backward(beg, end, dest)

將序列元素從end開始倒序拷貝（或移動(dòng)）到dest（dest仍是正序，也就是說它應(yīng)該給定一個(gè)新序列尾位置）

iota(beg, end, val)

將val賦值給beg，再把++val依次賦值給下一個(gè)元素，直到賦值完整個(gè)序列。

E. 劃分和排序

劃分

partition(beg, end, func1)
stable_partition(beg, end, func1)
partition_copy(beg, end, beg2, beg3, func1)
partition_point(beg, end, func1)
is_partitioned(beg, end, func1)

將序列劃分成前后兩段，滿足func1的放在前面，不滿足的放在后面，返回分界點(diǎn)位置。stable版本保證相同元素的順序不發(fā)生改變。copy版本將滿足func1的輸入新序列beg2，不滿足的輸入beg3。

partition_point返回已經(jīng)劃分好的元素的分界點(diǎn)，is_partitioned返回序列是否劃分好。

排序

sort(beg, end, cmp)
stable_sort(beg, end, cmp)

將序列排序，默認(rèn)使用<號(hào)，可以使用可選的cmp自定義函數(shù)。stable版本保證相等元素的順序在操作后不改變

is_sorted(beg, end, cmp)
is_sorted_until(beg, end, cmp)

is_sorted返回bool值，表示是否已經(jīng)排好序。is_sorted_until尋找從起點(diǎn)開始的最長有序序列，返回尾位置。

partial_sort(beg, mid, end, cmp)
partial_sort_copy(beg, end, beg2, end2, cmp)
nth_element(beg, nth, end, cmp)

partial_sort部分排序，將前mid-beg小的元素填充到beg~mid中，copy版本將這些元素輸出到新序列中。

nth_element是另一類部分排序，參數(shù)nth是一個(gè)位置，函數(shù)將圍繞nth部分排序，nth之前的元素都小于它，nth之后的都大于他

int a[] = {6, 7, 2, 3, 4, 9};
nth_element(a, a+3, a+6);//a = {4, 3, 2, 6, 7, 9}，圍繞第4位排序

F. 重排算法

remove(beg, end, val)
remove_if(beg, end, func1)
remove_copy(beg, end, dest, val)
remove_copy_if(beg, end, dest, func1)

remove和remove_if移除序列中指定元素或滿足func1的函數(shù)。移除的方式是將之后的元素往前移動(dòng)，因此是線性復(fù)雜度，不過之后的元素不會(huì)被消除。返回尾位置。copy版本將元素輸出到新序列。

int a[] = {6, 7, 2, 3, 4, 9};
std::remove(a, a+6, 2); // 6 7 3 4 9 | 9

unique(beg, end, val)
unique_if(beg, end, func2)
unique_copy(beg, end, dest, val)
unique_copy_if(beg, end, dest, func2)

將已經(jīng)排好序的序列中刪除相鄰元素，返回尾位置，用==運(yùn)算符或func2判斷相等，多余的元素被swap到尾位置之后。copy版本將元素輸出到新序列。

int a[] = {1, 2, 2, 3, 3, 4};
std::remove(a, a+6, 2); // 1 2 3 4 | 2 3

rotate(beg, mid, end)
rotate_copy(beg, mid, end, dest)

將序列循環(huán)右移，將mid成為beg處首元素，mid之前的元素循環(huán)到end處。copy版本將元素輸出到新序列。

reverse(beg, end)
reverse_copy(beg, end, dest)

翻轉(zhuǎn)序列元素，不必多說。copy版本將元素輸出到新序列。

random_shuffle(beg, end)
random_shuffle(beg, end, rand)
shuffle(beg, end, func)

隨機(jī)打亂序列，可以帶入自定義隨機(jī)函數(shù)rand，或者外部傳入隨機(jī)數(shù)生成器func。

G. 排列

is_permutation(beg, end, beg2, cmp)
prev_permutation(beg, end, cmp)
next_permutation(beg, end, cmp)

is_permutation求解兩個(gè)序列是否互為排列。具體來說，若兩個(gè)序列擁有相同元素且同一種元素個(gè)數(shù)都相等，就是真，否則是假。
prev_permutation和next_permutation返回序列的上一個(gè)或者下一個(gè)排列（字典序意義），如果已經(jīng)是最后一個(gè)排列，則循環(huán)到第一個(gè)排列，反之亦然。

int a[] = {1, 2, 3, 4};
for (int i = 0; i <= 24; ++i) {
	std::next_permutation(a, a+4);
	for (int x: a) std::cout << x; // 1234->1243->1324->1342->1423....->4321->1234
}	

H. 集合算法

這些算法用的比較少，將有序序列視作集合，執(zhí)行一些集合操作。

includes(beg, end, beg2, end2, cmp)
set_union(beg, end, beg2, end2, dest, cmp)
set_intersection(beg, end, beg2, end2, dest, cmp)
set_difference(beg, end, beg2, end2, dest, cmp)
set_symmetric_difference(beg, end, beg2, end2, dest, cmp)

include判斷第二個(gè)序列是否包含在第一個(gè)序列中。

set_union和set_intersection求集合的并集和交集，set_difference求只在第一個(gè)集合，不在第二個(gè)集合中的函數(shù)。set_symmetric_difference求只出現(xiàn)在一邊的元素。他們都將結(jié)果輸出到dest，返回dest的尾位置。默認(rèn)使用<，可以使用自定cmp函數(shù)。

I. 雜項(xiàng)

min({list})
max({list})
minmax({list})

雙元素版本就不放了，現(xiàn)在min和max可以以列表形式支持變長參數(shù)了，如min({1,2,3})的形式，而minmax返回一個(gè)pair，fisrt和second分別代表最小和最大值。

min_element(beg, end, cmp)
max_element(beg, end, cmp)
minmax_element(beg, end, cmp)

對(duì)序列求最值，返回的不是值，是指向目標(biāo)值的指針或迭代器。可以使用自定cmp函數(shù)

lexicographical_compare(beg1, end1, beg2, end2, cmp)

比較兩個(gè)序列的字典序，一次調(diào)用每個(gè)元素的<或cmp函數(shù)比較，若都相等則較短的序列更小，若長度也一樣返回false。

accumulate(beg, end, init, func2)
inner_product(beg, end, beg2, init, func21, func22)

accumulate即字面意義“求和”，對(duì)序列從左往右求和，init為初始值，決定了返回值類型，默認(rèn)調(diào)用+，可以自定函數(shù)；inner_product即字面意義“求內(nèi)積”，將兩個(gè)序列元素相乘再相加，默認(rèn)調(diào)用*和+，兩個(gè)函數(shù)都可以自定義。

int a[] = {1, 2, 4, 5, 90};
int xorans = std::accumulate(a, a+5, [](int x, int y){
	return x ^ y;
});// 求異或和

partial_sum(beg, end, dest, func2)
adjacent_difference(beg, end, dest, func2)

字面意思，第一個(gè)求前綴和，第二個(gè)求差分，將結(jié)果輸出到dest。默認(rèn)使用+或-，可以自定義

總結(jié)

到此這篇關(guān)于C++序列操作函數(shù)學(xué)習(xí)指南的文章就介紹到這了,更多相關(guān)C++序列操作函數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論