C++ 序列操作函数最全总结

标准库定义了许多用于操作序列的算法,大多在algorithmnumeric文件中,大多数函数的原理并不复杂,但是在很多情况下可以替代手写的情况,甚至更加优秀。

这类算法函数非常多,但是他们都有共同的结构,类似的参数特性,所以非常好记忆。比如我们最经典的std::sort(beg, end, cmp),其中begend为首尾地址,左闭右开,既可以是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。默认使用+或-,可以自定义

上一篇:『无为则无心』Python面向对象 — 55、多层继承和继承中的私有成员


下一篇:基于 WPF + Modern UI 的 公司OA小助手 开发总结