C++序列操作函數實例分析

本文小編為大家詳細介紹“C++序列操作函數實例分析”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++序列操作函數實例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

前言

標準庫定義了許多用于操作序列的算法，大多在algorithm和numeric文件中，大多數函數的原理并不復雜，但是在很多情況下可以替代手寫的情況，甚至更加優秀。

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

摘自C++ Primer附錄

A. 查找算法

簡單查找

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

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

find_if和find相同，不過查找標準變成使謂詞（布爾函數）返回true的第一個值。如查找序列中第一個奇數：

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

find_if_not和find_if相反，不過返回的是第一個使值為假的函數。

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

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

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

返回布爾值，all_of當序列全部滿足時返回真，any_of在有一個滿足時返回真，none_of在全部不滿足時返回真。序列為空時，any_of返回假，另外兩個返回真。

查找重復值

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

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

查找子序列

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

search返回第二個序列在第一個序列中出現的位置，find_end相反，返回最后出現的位置，沒有時返回end1。find_first_of返回的是第二個序列中任一元素第一次出現在序列一的位置，此時序列二不是序列，而是充當集合。

B. 其他只讀算法

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

對序列中每個數執行func1，很好用，很多時候可以減少代碼量替代for。
mismatch比較兩個序列中每一個元素，返回第一組不相等（使用==運算符）或使func2為假的位置（是一個pair），沒有則返回倆end。
equal與mismatch類似，若所有元素相等（滿足mismatch返回end），結果為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)

老熟了。在序列lower_bound返回第一個大于等于val的位置，upper_bound返回第一個大于val的位置，equal_range相當于前兩個加在一起，返回一個pair，即兩個函數的結果組合，包含一個值與val全部相等的區間。

如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。

以上函數操作自定義結構時都只使用<號，可以使用可選的自定義cmp函數

D. 只寫算法

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

fill和fill_n為區間所有元素賦值val，他們給出區間所用的參數不一樣。generate不斷執行gen函數，將返回值逐個賦值給區間。普通版本無返回值，_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拷貝符合條件的分數。在C++中，應該使盡量使用std::fill和std::copy替代memset和memcpy。

move移動整個序列，對序列每個值調用std::move（右值轉化），移動到dest。

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

將序列元素調用func1后存入dest，第二個版本對兩個序列調用func2后將結果存入dest。

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

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

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

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

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

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版本將元素寫進新序列

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

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

iota(beg, end, val)

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

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的放在前面，不滿足的放在后面，返回分界點位置。stable版本保證相同元素的順序不發生改變。copy版本將滿足func1的輸入新序列beg2，不滿足的輸入beg3。

partition_point返回已經劃分好的元素的分界點，is_partitioned返回序列是否劃分好。

排序

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

將序列排序，默認使用<號，可以使用可選的cmp自定義函數。stable版本保證相等元素的順序在操作后不改變

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

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

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是另一類部分排序，參數nth是一個位置，函數將圍繞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的函數。移除的方式是將之后的元素往前移動，因此是線性復雜度，不過之后的元素不會被消除。返回尾位置。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)

將已經排好序的序列中刪除相鄰元素，返回尾位置，用==運算符或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)

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

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

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

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

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

G. 排列

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

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

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. 集合算法

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

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判斷第二個序列是否包含在第一個序列中。

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

I. 雜項

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

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

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

對序列求最值，返回的不是值，是指向目標值的指針或迭代器。可以使用自定cmp函數

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

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

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

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

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)

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

讀到這里，這篇“C++序列操作函數實例分析”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。