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
2
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

我只能说尽量不要用宏，绝对值用用还行，最大值和最小值千万别用（别问我是怎么知道的）

reverse(s,t)

reverse(s,t) 可以将数组指针在 s~t 之间的元素，或容器的迭代器在 s~t 范围内的所有元素进行反转（老规矩，左闭右开）

1
2
3
4
5
6
7
8
9
10
int a[10] = {10, 11, 12, 13, 14, 15};
reverse(a, a + 4); //将 a[0] 到 a[3] 这4个元素反转
for (int i = 0; i < 6; i++)
    printf("%d ", a[i]);
//输出 13 12 11 10 14 15
string str = "abcdefghi";
reverse(str.begin() + 2, str.begin() + 6);
for (int i = 0; i < str.length(); i++)
    printf("%c", str[i]);
//输出 abfedcghi

next_permutation()

next_permutation() 能求出一个序列在全排列中的下一个序列，并在达到全排列的最后一个时会返回 false

例如，123 的全排列为：123，132，213，231，312，321，所以 231 的下一个排列就是 312

1
2
3
4
5
6
int a[10] = {1, 2, 3};
do
{
    printf("%d %d %d\n", a[0], a[1], a[2]);
} while (next_permutation(a, a + 3));
// a[0],a[1],a[2]三个元素的排列

fill()

fill() 可以把数组或容器的某一段区间赋为某个相同的值，和 memset() 不同，这里的赋值可以是数组类型对应范围中的任意值

1
2
3
4
5
int a[5];
fill(a, a + 5, 123); // 将 a[0] 到 a[4] 均赋值为 123
for (int i = 0; i < 5; i++)
    printf("%d", a[i]);
}

sort()

sort()是实现自动排序的函数，鄙人认为它是 STL 中最重要而且也是最常用的函数了

sort() 在具体实现中规避了经典快速排序（包括 C 语言中的 qsort() 函数）可能出现的、会导致实际复杂度退化到 O (n2n^{2}) 的极端情况。它根据具体情形使用不同的排序方法，效率极高

它的基本使用格式为：

1
sort(首元素地址, 尾元素地址的下一个地址, 比较函数); // 为什么说是下一个？因为左闭右开（顾头不顾腚）

我们看到，sort() 有三个参数，其中前两个是必填的，如果数组中的元素是可以直接比较大小的，如 int、double、char 等，可以不指定比较函数，并且默认是递增

1
2
3
4
5
6
7
8
9
10
int a[6] = {9, 4, 2, 5, 6, -1};
sort(a, a + 4);
for (int i = 0; i < 6; i++)
    printf("%d ", a[i]);
//输出 2 4 5 9 6 -1
char c[] = {'T', 'W', 'A', 'K'};
sort(c, c + 4);
for (int i = 0; i < 4; i++)
    printf("%c", c[i]); 
//输出 AKTW

如果需要实现递减排序，或者对结构体（本身没有大小关系）等进行排序，就需要用到比较函数，一般写成 cmp 函数

1
2
3
4
bool cmp(int a, int b) // 类型根据实际情况自行修改
{
    return a > b; //可以理解成如果 a>b 就把 a 放在前面
}

然后这样使用

1
2
3
4
5
int a[6] = {9, 4, 2, 5, 6, -1};
sort(a, a + 6, cmp);
for (int i = 0; i < 6; i++)
    printf("%d ", a[i]); 
//输出9 6 5 4 2 -1

而如果要对结构体进行排序，假设定义了如下的结构体

1
2
3
4
struct node
{
    int x, y;
} s[10];

下面想要按照 x 从大到小排序，那么排序函数就可以这么写

1
2
3
4
bool cmp(node a, node b)
{
    return a.x > b.x; //按照 x 的值从大到小对结构体进行排序
}

如果想先按照 x 从大到小排序，在 x 相等的情况下，再按照 y 从小到大排序，即类似的双关键字排序，就可以这么写

1
2
3
4
bool cmp(node a,node b){
  if(a.x != b.x) return a.x > b.x;
  else return a.y < b.y;
}

当然，不仅是数组，对于 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

当然，你也可以指定自己的比较函数（阅读原文）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
using namespace std;
struct point{
    point(){

    }
    point(int _x, int _y){
        x = _x;
        y = _y;
    }
    int x;
    int y;
};

bool cmp(point a, point b){
    return a.x < b.x;
}
int main(int argc, char *argv[]){
    point a[5];

    a[0].x = 1;
    a[0].y = 100;

    a[1].x = 100;
    a[1].y = 1;

    a[2].x = 30;
    a[2].y = 50;

    a[3].x = 25;
    a[3].y = 120;

    a[4].x = 301;
    a[4].y = 103;
    // 随便赋值
    sort(a, a + 5, cmp);
    // 先排序
    for (int i = 0; i < 5; i++){
        printf("a[%d].x = %d, a[%d].y = %d\n", i, a[i].x, i, a[i].y);
    }
    // 输出会发现他们按照x从小到大排序了
    cout << (lower_bound(a, a + 5, point(1, 1000), cmp) - a) << endl;
    // 第一个x值大于1的元素是(1, 100)这个元素，它的下标为0
    cout << (lower_bound(a, a + 5, point(101, 1000), cmp) - a) << endl;
    // 第一个x值大于101的元素是(301, 103)这个元素，它的下标为4
    cout << (lower_bound(a, a + 5, point(1000, 1000), cmp) - a) << endl;
    // 因为找不到所以返回a + 5，再减a就是5
    
}