C++序列操作函数
Ofnoname 人气:0前言
标准库定义了许多用于操作序列的算法，大多在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。默认使用+或-，可以自定义
总结
加载全部内容