105个STL算法思维笔记模板_ProcessOn思维导图、流程图

参考链接

b站视频

原blog

目的

高效、简洁的代码

避免常见错误

the queriers

数值计算

count

count( InputIt first, InputIt last, const T& value );

计算给定范围内有几个满足条件的值/字符

内部常用：处理字符串，某些系统指令/AT 响应结果？

innner_prodcut

内积，等于每个对应项相乘，并求和

accumulate

累加

内部常用：某些批量数据处理，定位数据观测量?

adjacent_difference

求相邻元素的差

partial_sum

求一个数列的前N项和构成的数列

sample

采样算法

算法都有明确的数学含义，按相应的含义使用

查询

all_of

bool all_of(ForwardIt first, ForwardIt last, UnaryPred p );

全部满足p的条件

any_of

bool any_of( InputIt first, InputIt last, UnaryPred p );

至少有1各满足p的条件

none_of

bool none_of( InputIt first, InputIt last, UnaryPred p );

全不满足p的条件

以上较常用

字符串有效性判断（VIN/SN/DID等)、值有效性判断；

内部业务某些自定义的task/callback/service的集合，需要查询结果/获取某些状态

比较两个序列

equal

两个序列相等，或者满足同个条件

如果范围 [first1, last1) 和范围 [first2, first2 + (last1 - first1)) 相等/满足条件，返回 true ；
否则返回 false

bool equal( InputIt1 first1, InputIt1 last1,
InputIt2 first2 );

bool equal( InputIt1 first1, InputIt1 last1,
InputIt2 first2, BinaryPred p );

如果范围 [first1, last1) 和范围 [first2, last2)相等/满足条件，返回 true ；
否则返回 false

// 使用 == 运算符来比较元素
bool equal( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 );

// 使用自定义的p函数
bool equal( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, BinaryPred p );

lexicographical_compare

字典序比较，检查第一个序列是否“小于”第二个序列
“小”指的是字典序的小
比较顺序第一个元素起比较，比如 age”和“beauty”比较，age是小于beauty的，因为第一个字符a小于b

bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 );

bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
Compare comp );

mismatch

判断两个序列是否匹配；而且如果不匹配，返回不匹配的位置（第一对不满足条件的元素）

函数输入参数同equal

std::pair<ForwardIt1,ForwardIt2>
mismatch( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
BinaryPredicate p );

其它省略

查询一个值

对于未排序的序列

find

在指定范围内查找和目标元素值相等的第一个元素

InputIt find( InputIt first, InputIt last, const T& value );

返回一个输入迭代器，当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；
如果查找失败，则该迭代器的指向和 last 相同

常用比如：DID/DTC/平台层如VNS事件广播

find_if

InputIt find_if( InputIt first, InputIt last, UnaryPred p );

查找指定区域内第一个符合规则要求（使p函数返回 true）的元素。

返回一个输入迭代器，当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；
如果查找失败，则该迭代器的指向和 last 相同

find_if_not

InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred);

返回一个输入迭代器，当 find_if_not() 函数查找成功时，该迭代器指向的是查找到的那个元素；
反之，如果查找失败，该迭代器的指向和 last 迭代器相同。

查找指定区域内第一个“不”符合规则要求（使p函数返回 true）的元素。

adjacent_find

找到一对相邻的满足条件的元素

已排序的序列

equal_range，找到上界和下界

lower_bound，只找下界

upper_bound，只找上界

binary_search，不关心元素，只关心是否存在

查找一个序列中是否有另一个序列

find_first_of

在 A 序列中查找和 B 序列中任意元素相匹配的第一个元素
序列A [first1, last1) ，序列B [first2, last2)

如果匹配成功，该函数会返回一个指向该元素的输入迭代器；反之，则返回一个和 last1 迭代器指向相同的输入迭代器

//以判断两者相等作为匹配规则
InputIterator find_first_of (InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2);

逐个取 [first1, last1) 范围内的元素（假设为 A），和 [first2, last2) 中的每个元素（假设为 B）做 A==B 运算，如果成立则匹配成功；

//以 pred 作为匹配规则
InputIterator find_first_of (InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2,
BinaryPredicate pred);

逐个取 [first1, last1) 范围内的元素（假设为 A），和 [first2, last2) 中的每个元素（假设为 B如果函数返回 true 则匹配成功。
如果函数返回 true 则匹配成功。

pred规则实际上是一个包含 2 个参数且返回值类型为 bool 的函数（第一个参数接收 [first1, last1) 范围内的元素；
第二个参数接收 [first2, last2) 范围内的元素）。
函数定义的形式可以是普通函数，也可以是函数对象。

find_end 找子序列最后一次出现的

在序列 A 中查找序列 B 最后一次出现的位置
序列A [first1, last1) ，序列B [first2, last2)

//查找序列 [first1, last1) 中最后一个子序列 [first2, last2)
ForwardIterator find_end (ForwardIterator first1, ForwardIterator last1,
ForwardIterator first2, ForwardIterator last2);

//查找序列 [first2, last2) 中，和 [first2, last2) 序列满足 pred 规则的最后一个子序列
ForwardIterator find_end (ForwardIterator first1, ForwardIterator last1,
ForwardIterator first2, ForwardIterator last2,
BinaryPredicate pred);

find_end() 函数会返回一个正向迭代器，当函数查找成功时，该迭代器指向查找到的子序列中的第一个元素；
反之，如果查找失败，则该迭代器的指向和 last1 迭代器相同。

search 找子序列第一次出现位置

在序列 A 中查找序列 B 第一次出现的位置，比较的是整个序列B

常用：处理字符串/回调函数list/DTC/DID/某些系统指令/AT指令的返回值等

searchi 和 find_first_of 比较

子主题

the permutationers
排列之地 Lands of Permutation

PROVINCE OF HEAPS

堆是一种非线性结构，可以把堆看作一个数组，也可以被看作一个完全二叉树；
通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组但堆并不一定是完全二叉树，按照堆的特点可以把堆分为大顶堆和小顶堆
大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值

大顶堆

小顶堆

堆相关接口的参数：
_First：指向开始元素的迭代器
_Last：指向最末尾元素的迭代器
_Comp: 比较函数（仿函数）,其规则——如果函数的第一个参数小于第二个参数应返回true，否则返回false。
使用建议：
大顶堆，就每一个函数都加上第三个参数less<type>()，假如元素是int类型的，就是less<int>()
小顶堆，就每一个函数都加上第三个参数greater<type>()，假如元素是int类型的greater<int>()，一直加上，后续使用一直保持一致。
第三个参数默认情况下为less<>()，也就是默认生成大顶堆

make_heap

把一个不是堆的序列重排为堆

push_heap

为堆新增一个元素，新元素应在序列最后

推入元素

将数据冒泡到对应位置

pop_heap

void sort_heap( RandomIt first, RandomIt last );

void sort_heap( RandomIt first, RandomIt last, Compare comp );

先将栈顶元素与最后一个元素交换

逐步冒泡维持黄色部分为堆

最后使用 pop_back删除栈顶元素

删除堆顶元素，把它放到最后

sort_heap

专用于堆上排序的方法，针对堆的排序，比sort快

假如pop_heap

大顶堆sort_heap()后是一个递增序列
小顶堆是一个递减序列

SHORE OF SORTING

sort 整体排序

void sort(RandomIt first, RandomIt last, Compare comp );

对容器或数组first~last范围内的元素进行排序，默认升序排序，也可以指定自定义的比较函数来实现降序排序等其他排序方式。

容器的迭代器必须是随机访问迭代器，如std::array、std::vector、std::deque
如果采用默认的升序排序方法，则元素必须支持operate<运算符
自定义类对象容器使用std::sort()排序时，因为需要交换位置，所以必须提供拷贝构造函数和赋值运算符
std::sort()无法保证相同元素的原始位置，这里的相同是指进行比较的结果为相等，而对象本身不相同。
如果需要保持相对顺序相同，则应该使用std::stable_sort()

stable_sort() 和 sort() 具有相同的使用场景，就连语法格式也是相同的，stable_sort除了可以实现排序，还可以保证不改变相等元素的相对位置。

比如 1 4 6 7 4 使用stable_sort排序后是 1 4 4 6 7

partial_sort 部分排序

//按照默认的升序排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);

//按照 comp 排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);

将 [first, last) 范围内最小（或最大）的 middle-first 个元素移动到 [first, middle) 区域中，并对这部分元素做升序（或降序）排序

示例

std::vector<int> myvector{ 3,2,5,4,1,6,9,7};
//以默认的升序排序作为排序规则，将 myvector 中最小的 4 个元素移动到开头位置并排好序
std::partial_sort(myvector.begin(), myvector.begin() + 4, myvector.end());

nth_element 取得第n大/小的元素。

它不会对所有元素排序，只是使得第n大/小的元素、处在第n-1个位置（从0起）

如果采用默认的升序排序规则（std::less<T>）时，该函数可以从某个序列中找到第 n 小的元素 K，并将 K 移动到序列中第 n 的位置处。不仅如此，整个序列经过 nth_element() 函数处理后，所有位于 K 之前的元素都比 K 小，所有位于 K 之后的元素都比 K 大。
如果定义为降序排序，此时该函数会找到第 n 大的元素 K 并将其移动到第 n 的位置处，同时所有位于 K 之前的元素都比 K 大，所有位于 K 之后的元素都比 K 小。

比如 3 4 1 2 5 ，按照升序排序、通过 nth_element() 函数查找此序列中第 3 小的元素，此序列会变成 2 1 3 4 5

void nth_element (RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last,
Compare comp);
升序排序第4个参数可省略

示例

//默认的升序排序作为排序规则
std::vector<int> myvector{3,1,2,5,4};
std::nth_element(myvector.begin(), myvector.begin()+2, myvector.end());

inplace_merge

将 2 个有序序列合并为 1 个有序序列，前提是这 2 个有序序列的排序规则相同（要么都是升序，要么都是降序）

OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);

int first[] = { 5,10,15,20,25 };
int second[] = { 7,17,27,37,47,57 };
//用于存储新的有序序列
vector<int> myvector(11);
//将 [first,first+5) 和 [second,second+6) 合并为 1 个有序序列，并存储到 myvector 容器中。
merge(first, first + 5, second, second + 6, myvector.begin());

sort_heap

子主题

partition 分区

根据用户自定义的筛选规则，重新排列指定区域内存储的数据，使其分为 2 组，第一组为符合筛选条件的数据，另一组为不符合筛选条件的数据。

ForwardIterator partition (ForwardIterator first,
ForwardIterator last,
UnaryPredicate pred);

筛选规则：本质就是一个可接收 1 个参数且返回值类型为 bool 的函数，可以是普通函数，也可以是一个函数对象。

partition_point

ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred);

找到已经分组的数据的分界点

同样地，first 和 last 为正向迭代器，[first, last) 用于指定该函数的作用范围；pred 用于指定数据的筛选规则。

其它

rotate 序列旋转

对一组元素进行左旋转

ForwardIt rotate( ForwardIt first,
ForwardIt middle,
ForwardIt last );

第一个参数是这个序列的开始迭代器；
第二个参数是指向新的第一个元素的迭代器，需要在序列之内
第三个参数是这个序列的结束迭代器

返回值：一个迭代器，它指向原始的第一个元素所在的新位置

示例

是许多排序算法的基础

shuffle

使用一个随机数产生器来打乱[first, last)之间元素的顺序

void shuffle (RandomAccessIterator first,
RandomAccessIterator last,
URNG&& g);

first, last-要随机打乱的元素范围
g-均匀随机位生成器 (UniformRandomBitGenerator)

g表示随机性来源对象（比如均匀随机生成器）

注意

std::shuffle是从C++11之后才开始出现，必须与随机数生成器一起使用
URNG&& g

std::random_shuffle在C++11之前就已经存在，可以不指定随机数生成器而使用默认的随机数生成器。
std::random_shuffle在 C++14 中弃用， C++17 中移除。
std::random_shuffle的随机数产生器使用了std::rand()。
而std::rand()使用了一个全局静态变量保存其状态，这样使得std::rand()无法同时产生两个独立互不干扰的随机数流。

推荐使用std::shuffle

next_permutation

next_permutation的作用是在给定范围内找到字典更大的下一个排列；
如果有下一个排列（下一个排列大于上一个排列），则返回true，否则返回false

bool next_permutation( BidirIt first, BidirIt last );

bool next_permutation( BidirIt first, BidirIt last, Compare comp );

字典序又称字母序，含义是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系

比如”abc“ < “acb” < “acbd”, 其规则是先比较第一个字母，如果不相等，就直接得到结果，如果相等，就比较下一个字母
如果两个字符串的长度不相等，但是长的那个字符串包含了短的那个，那长的那个字符串更大（比如"acb" < “acbd”）
比较规则，a' < 'b' < 'c' < ... < 'z'

prev_permutation

将[first, last)范围内的元素重新排列为上一个按字典顺序排列的排列

bool prev_permutation( BidirIt first, BidirIt last );

bool prev_permutation( BidirIt first, BidirIt last, Compare comp );

用途：比如为给定值数组查找的字典编排较小的值

reverse

反转范围 [first, last) 中元素的顺序

void reverse( BidirIt first, BidirIt last );

假如一个序列，如果是完全升序，然后一直使用next_permutation取下一个排列；
取到最后，就是一个完全降序的序列，它与第一个排列的关系是reverse

Secret Runes

*部分可以嵌入其它的算法，形成新的算法

stable_*

*_copy

*_n

*_if

is_*_until

is_*

is_sorted

/判断 [first, last) 区域内的数据是否符合 std::less<T> 排序规则，即是否为升序序列
bool is_sorted( ForwardIt first, ForwardIt last );

//判断 [first, last) 区域内的数据是否符合 comp 排序规则
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

is_sorted_until

检测出某个序列是否有序，并返回一个正向迭代器，该迭代器指向的是当前序列中第一个破坏有序状态的元素。

//排序规则为默认的升序排序
ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);

函数返回的是指向序列中第一个破坏升序规则的元素；

//排序规则是自定义的 comp 规则
ForwardIterator is_sorted_until (ForwardIterator first,
ForwardIterator last,
Compare comp);

返回的是指向序列中第一个破坏 comp 排序规则的元素

如果 [first, last) 指定的序列完全满足默认排序规则或者 comp 排序规则的要求，则该函数将返回一个和 last 迭代器指向相同的正向迭代器。

the algos on sets
集合处理

子主题

the movers
移动

std::copy

把一个序列复制到另一个序列

常用：复制字符串/list

std::copy_n

std::move

&&

把一个序列移动到另一个序列

保证移动之后，输入序列不再使用

常用：参数传递/某些较大的不再使用的字符串、数据流

the value modifiers
修改值

fill

void fill( ForwardIt first, ForwardIt last, const T& value );

给序列填上相同的值，fill() 会填充整个序列

fill_n

以给定的迭代器为起始位置，为指定个数的元素设置值

ForwardIt fill_n(ForwardIt first, Size count, const T& value );

generate 给序列填上生成的值

iota 给序列填上生成的递增的值

replace 给序列中的A值，填上B值

常用：未序列赋初值，填充替换某些序列
比如固定长度DID，设置填充值和未填充值

the structure changers,
修改结构

remove

transform

the algos of raw memory
原始之地(针对未初始化内存)

针对在未始化的内存上，如何填弃，如何复制，如何构造类型。