分别接受三个参数, 先是照例两个迭代器划分区间, 第三个参数前者是一个值, 后者是一个函数. 前者将值与参数相等的元素删除掉, 后者将使函数返回 true 的元素删除掉. 由于删除后区间会变短所以返回删除部分元素后新的右端点(依然遵循STL的左闭右开原则).

9. std::swap 

接受两个类型相同的参数, 并将它们的值交换. 这个库函数跑得比谁都快, 不要想着自己搞个奇技淫巧就能卡常.

10. std::iter_swap 

和 std::swap 功能类似, 不同的是本函数接受的参数是指向待交换变量的迭代器.

11. std::reverse 

接受一对迭代器指定的区间然后暴力翻转w

12. std::rotate 

以轮转的方式旋转指定区间. (即滑动该区间, 并将滑出去的元素补到开头OwO) 第三个参数为一个迭代器, 指定要旋转到左端的元素位置.

13. std::random_shuffle 

接受一对迭代器指定的区间, 对区间里的值进行随机打乱, 防Hack&随机化&造数据时的好帮手OwO

14. std::unique 

给区间去重. 但是只去重连续的重复元素. 即区间  中该函数会将三个 $4$ 去重为 $1$ 个, 但是区间  中的三个 $4$ 不会被去重.

可以先 std::sort 排个序把相等的元素集中起来再去重.

15. std::partition 

重排区间. 接受一对指定区间的迭代器与一个函数. 区间内所有使一元函数返回 true 的值都排在返回 false 的值之后从而将其分为两组. 此重排过程不稳定.

16. std::stable_partition 

 std::partition 的稳定版本, 保证同一组内的元素的相对次序保持不变.

17. std::sort 

STL里极其强劲的函数... 可以根据数据自我调整排序方式...

指定一个区间即可. 要求区间内的元素重载了 <  运算符或者传入一个自定义比较函数.

数据量小, 快排优势体现不出来? 没事, 我们用插入排序.

数据量大而且比较随机? 快排走起.

数据量过大递归过多? 上堆排序

数据原始位置不好结果把快排卡到了接近 $O(n^2)$ ? 接着堆排上.

不可能有哪个手写排序能打败这个库函数的.

此排序不稳定.

18. std::stable_sort 

 std::sort 的稳定版本, 内部在内存足够的情况下使用 $O(nlog(n))$ 的多路归并排序, 内存不足时使用 $O(nlog^2(n))$ 的次优算法.

保证相等的元素相对次序不变.

19. std::lower_bound 

只能在有序区间上操作.

指定一个区间和一个待查找的值, 可选参数为自定义比较函数, 返回指向第一个不小于给定值的元素的迭代器. 或者说指向"第一个可插入位置".

20. std::upper_bound 

只能在有序区间上操作.

指定一个区间和一个待查找的值, 可选参数为自定义比较函数, 返回指向第一个大于给定值的元素的迭代器. 或者说指向"最后一个可插入位置".

21. std::nth_element 

指定一个区间和值 $n$ , 该函数将会以第 $n$ 大的值为分割点, 将所有大于第 $n$ 个值的元素放在第 $n$ 个元素之前, 所有小于第 $n$ 个值的元素放在它之后, 第 $n$ 大的元素将刚好在第 $n$ 个值的位置上.

可传入自定义比较函数.

22. std::merge 

合并两个有序区间.

前四个参数为指定操作区间的两对迭代器, 第五个参数为输出区间的左端迭代器. 可传入自定义比较函数.

23. std::is_heap 

判断一个区间里的元素是否满足堆性质.(大端堆)

STL对区间大端堆的定义:

对于区间 $[f,l)$, 设 $N=l-f$, 则:

\[\forall \: i \in (0,N) , f[\left \lfloor \frac{i-1}{2} \right \rfloor] \geq f[i]\]

可传入自定义比较函数.

24. std::make_heap 

在 $O(n)$ 时间复杂度内构造一个大端堆. 参数为指定操作区间的一对迭代器. 可传入自定义比较函数.

25. std::push_heap 

在 $O(log(n))$ 时间内插入一个数到建好的堆中. 待插入的值应该置于区间尾部, 原来的堆应位于 $[l,r-1)$

26. std::pop_heap 

在 $O(log(n))$ 时间内将堆顶元素弹出并放到原来堆的尾部.

27. std::sort_heap 

在 $O(n)$ 时间内建立一个堆并通过反复调用 $pop_heap$ 实现堆排序. 总时间复杂度 $O(nlog(n))$

28. std::max 

参数为两个类型相同的变量, 返回其中的较大值.

可传入自定义比较函数.

比自己用三目运算符手写再inline快.

29. std::max_element 

参数为一对迭代器指定的区间, 返回区间中最大元素的值.

可传入自定义比较函数.

30. std::min 

参数为两个类型相同的变量, 返回其中的较小值.

可传入自定义比较函数.

比手写快系列.

31. std::min_element

参数为指定操作区间的一对迭代器,  返回区间中最小元素的值.

可传入自定义比较函数.

32. std::next_permutation 

参数为指定操作区间的一对迭代器, 这个函数会计算区间内数据的下一个排列.

若有下一个排列返回 true , 否则返回 false 

33. std::prev_permutation 

基本同 std::next_permutation , 不同的是这个函数计算上一个排列并返回上一个排列是否存在.

3. 技巧

STL中的各种元素按照一定的方式配合起来使用功能可以变得十分强大, 下面介绍一些博主见到或者使用过的奇技淫巧使用方式.

3.1 离散化