【C++】STL算法

STL算法

标签：c++

STL算法

整理出头文件algorithm中的一些有趣的算法，仿佛打开了新世界的大门~~

一、不变序列算法

1、熟悉的`min()`, `max()`

2、找最值还自己动手么？不了不了

min_element

itetator min_element(iterator first, iterator last)

max_element

itetator max_element(iterator first, iterator last)

3、熟悉的`find()`和新学会的`count()`

二、变值算法

1、`fill()`函数，emmm放这充个数

三、变序算法

1、熟悉的`reverse()`函数

2、为啥不用`rotate()`

void rotate(iterator first, iterator newFirst, iterator last)

数组的循环右移，比如：

rotate(num, num, n, num + len)

得到的结果是：num[n], num[n + 1], ..., num[len - 1], num[1], num[2], ..., num[n - 1]

3、排列再也不用自己动手了

将排列按照字典序排序

prev_permutation

bool prev_permutation(iterator first, iterator last)：改为上一个排列，如果当前排列已经是最小排列，返回false

next_permutation

bool next_permutation(iterator first, iterator last)：改为下一个排列，如果当前排列已经是最大排列，返回false

4、快速排序干啥还要自己写`partition()`

partition()

iterator partition(iterator first, iterator last, Pred op)：根据比较规则op(x)将区间划分，满足op(x) == true的放到x的前面，不满足的放在后面，返回的为满足op(x) == false的第一个迭代器，划分部分不保持原先的相对次序

stable_partition()

iterator stable_partition(iterator first, iterator last, Pred op)：用法同上，划分部分保持原先的相对次序

实例：

将序列中的偶数放在前面，奇数放在后面

bool op(int n)
{
    return !(n & 1);
}
partition(num, num + len, op);

四、排序算法

1、学会`sort()`走天下

sort()的实现原理

2、`stable_sort()`和`partial_sort()`了解一下

stable_sort()用法同sort()，但是整体速度低于sort()

void partial_sort(iterator first, iterator mid, iterator last)：([first, mid))有序，并且其中任意的元素都不大于([mid, last）)中的元素，堆排序实现

3、妈妈再也不用担心我的堆写不好啦(大顶堆)

make_heap

void make_heap(iterator first, iterator last)：将区间([first, last))变为堆，复杂度为(O(n))

push_heap

void push_heap(iterator first, iterator last)：当区间([first, last - 1))是堆时，末尾插入新的元素，再将区间([first, last))调整为堆，复杂度为(O(logn))

pop_heap

void pop_heap(iterator first, iterator last)：将堆顶元素（即数组中的第一个元素）移动到末尾

sort_heap

void sort_heap(iterator first, iterator last)：堆排序

五、有序区间算法

1、二分相关还说啥

lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。

upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 最后一个 出现的位置。

binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。

2、归并排序我也不动手啦

inplace_merge

void inplace_merge(iterator first, iterator mid, iterator last)：原地合并，合并完后的区间为([first, last))

对于归并排序，可以使用inplace_merge()函数，也可以直接用sort()