『C++』标准模板库(STL)之算法篇
STL 里除了上一篇中的那些好用的容器之外,还提供了大量基于迭代器的非成员模板函数,能大量简化我们的编程工作
这些模板函数都在 algorithm
头文件里(翻译为算法)
所以我们需要先引入这个头文件 #include <algorithm>
,同时不要忘记指定命名空间,例如 using namespace std;
max(x,y) 、 min(x,y) 、 abs(x) 和 swap(x,y)
这四个一起讲
如你所见,这几个分别用来求最大值,最小值,绝对值,还有交换两个变量
对于两个求最值的 x
和 y
不仅可以是整型,还可以是实型
但是 abs()
只能用于整型,实型要用 fabs()
而对于 swap()
,基本上所有地方都能用上
不过在比赛的话还是建议自己写函数覆盖掉,STL 里的没自己写的块
当然,你可能说使用宏不会更快吗?
1 |
我只能说尽量不要用宏,绝对值用用还行,最大值和最小值千万别用(别问我是怎么知道的)
reverse(s,t)
reverse(s,t)
可以将数组指针在 s
~t
之间的元素,或容器的迭代器在 s
~t
范围内的所有元素进行反转(老规矩,左闭右开)
1 | int a[10] = {10, 11, 12, 13, 14, 15}; |
next_permutation()
next_permutation()
能求出一个序列在全排列中的下一个序列,并在达到全排列的最后一个时会返回 false
例如,123
的全排列为:123
,132
,213
,231
,312
,321
,所以 231
的下一个排列就是 312
1 | int a[10] = {1, 2, 3}; |
fill()
fill()
可以把数组或容器的某一段区间赋为某个相同的值,和 memset()
不同,这里的赋值可以是数组类型对应范围中的任意值
1 | int a[5]; |
sort()
sort()
是实现自动排序的函数,鄙人认为它是 STL 中最重要而且也是最常用的函数了
sort()
在具体实现中规避了经典快速排序(包括 C 语言中的 qsort()
函数)可能出现的、会导致实际复杂度退化到 O () 的极端情况。它根据具体情形使用不同的排序方法,效率极高
它的基本使用格式为:
1 | sort(首元素地址, 尾元素地址的下一个地址, 比较函数); // 为什么说是下一个?因为左闭右开(顾头不顾腚) |
我们看到,sort()
有三个参数,其中前两个是必填的,如果数组中的元素是可以直接比较大小的,如 int
、double
、char
等,可以不指定比较函数,并且默认是递增
1 | int a[6] = {9, 4, 2, 5, 6, -1}; |
如果需要实现递减排序,或者对结构体(本身没有大小关系)等进行排序,就需要用到比较函数,一般写成 cmp
函数
1 | bool cmp(int a, int b) // 类型根据实际情况自行修改 |
然后这样使用
1 | int a[6] = {9, 4, 2, 5, 6, -1}; |
而如果要对结构体进行排序,假设定义了如下的结构体
1 | struct node |
下面想要按照 x
从大到小排序,那么排序函数就可以这么写
1 | bool cmp(node a, node b) |
如果想先按照 x
从大到小排序,在 x
相等的情况下,再按照 y
从小到大排序,即类似的双关键字排序,就可以这么写
1 | bool cmp(node a,node b){ |
当然,不仅是数组,对于 vector 等 STL 容器也是可以用的
1 | sort(v.begin(), v.end()); |
lower_bound() 和 upper_bound ()
lower_bound(first,last,val)
用来寻找一个有序数组或者容器中 first
~last
范围内(左闭右开),第一个 大于等于 val
的元素的位置。如果是数组,则返回该位置的指针;如果是容器,则返回该位置的迭代器。
upper_bound(first,last,val)
用来寻找一个有序数组或者容器中 first
~last
范围内(左闭右开),第一个 大于 val
的元素的位置。如果是数组,则返回该位置的指针;如果是容器,则返回该位置的迭代器。
如果数组或者容器中没有需要寻找的元素,则上面两个函数的返回值均为可以插入该值的位置的指针或者迭代器,时间复杂度均为 O(log2(last-first))
官方文档中的样例
1 | // lower_bound/upper_bound example |
当然,你也可以指定自己的比较函数(阅读原文)
1 |
|