C++序列操作函数学习最全指南

目录

• 前言
• A.查找算法
• 简单查找
• 查找重复值
• 查找子序列
• B.其他只读算法
• C.二分查找算法
• D.只写算法
• E.划分和排序
• 划分
• 排序
• F.重排算法
• G.排列
• H.集合算法
• I.杂项
• 总结

前言

标准库定义了许多用于操作序列的算法，大多在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++序列操作函数学习指南的文章就介绍到这了,更多相关C++序列操作函数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！