STL—algorithm（2）

---

一、什么是algorithm

在algorithm中，有很多函数，这些函数是已经写好的，可以直接调用，十分的方便，可以精简代码量辅助我们思考

在使用algorithm的函数之前需要添加头文件#include <algorithm>

由于algorithm下的函数有很多，这里分为两篇博客去介绍，第一篇博客见：STL—algorithm（1）

---

二、常用函数一览

6.sort()

顾名思义，sort函数就是用来排序的函数，根据不同的情况可以有不同的排序方法

（1）使用sort函数

sort(首元素地址[必填], 尾元素地址的下一个地址[必填], 比较函数[选填]);

可以看到，sort函数一共有三个参数，前两个是必填的，而比较函数可以根据自己的需求选填，当我们不填写比较函数的时候，则默认单调递增的排序方式

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int a[5] = {8, 4, 6, 12, 1};
    
    sort(a, a + 5);
    
    for (int i = 0; i < 5; i ++ ) cout << a[i] << ' ';
    
    return 0;
}

输出结果为：1 4 6 8 12

如果是char类型的数据，我们在不写比较函数的时候默认字典序从小到大排序

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    char a[5] = {'j', 'a', 'b', 'y', 'z'};
    
    sort(a, a + 5);
    
    for (int i = 0; i < 5; i ++ ) cout << a[i] << ' ';
    
    return 0;
}

输出结果为：a b j y z

（2）实现cmp函数

基本数据类型数组的排序

我们刚刚介绍了，如果什么都不填写的话，默认是从小到大进行排序，下面介绍如何实现从大到小排序

bool cmp(int a, int b)
{
	return a > b;
}

同样，如果是double或是char类型的数据，cmp函数就是：

bool cmp(double a, double b)
{
	return a > b;
}

bool cmp(char a, char b)
{
	return a > b;
}

下面给出样例和输出结果：
int类型

#include <iostream>
#include <algorithm>

using namespace std;

bool cmp (int a, int b)
{
    return a > b;
}

int main()
{
    int a[5] = {7, 3, 1, 8, 6};
    
    sort(a, a + 5, cmp);
    
    for (int i = 0; i < 5; i ++ ) cout << a[i] << ' ';
    
    return 0;
}

输出结果为：8 7 6 3 1

double类型

#include <iostream>
#include <algorithm>

using namespace std;

bool cmp (double a, double b)
{
    return a > b;
}

int main()
{
    double a[5] = {7.3, -3.1, 1, 8.7, 6.2};
    
    sort(a, a + 5, cmp);
    
    for (int i = 0; i < 5; i ++ ) cout << a[i] << ' ';
    
    return 0;
}

输出结果为：8.7 7.3 6.2 1 -3.1

char类型

#include <iostream>
#include <algorithm>

using namespace std;

bool cmp (char a, char b)
{
    return a > b;
}

int main()
{
    char a[5] = {'j', 'a', 'b', 'y', 'z'};
    
    sort(a, a + 5, cmp);
    
    for (int i = 0; i < 5; i ++ ) cout << a[i] << ' ';
    
    return 0;
}

输出结果为：z y j b a

结构体数组的排序

如下定义结构体：

struct node
{
    int x, y;
}s[10];

如果想将x数组按照x从大到小进行排序，那么可以写成：

struct node
{
    int x, y;
    
    bool operator < (const node w) const
    {
        return x > w.x;
    }
}s[10];

示例如下：

#include <iostream>
#include <algorithm>

using namespace std;

struct node
{
    int x, y;
    
    bool operator < (const node w) const
    {
        return x > w.x;
    }
}s[10];

int main()
{
    s[0] = {2, 2};
    s[1] = {1, 3};
    s[2] = {3, 1};
    
    sort(s, s + 3);
    
    for (int i = 0; i < 3; i ++ ) 
        cout << s[i].x << ' ' << s[i].y << endl;
        
    return 0;
}

输出结果为
3 1
2 2
1 3

如果想要先按x从大到小排序，但当x相等的情况下按照y的大小从小到大来排序，那么cmp的写法是：

struct node
{
    int x, y;
    
    bool operator < (const node w) const
    {
        if (x != w.x) return x > w.x;
        else return y < w.y;
    }
}s[10];

示例如下：

#include <iostream>
#include <algorithm>

using namespace std;

struct node
{
    int x, y;
    
    bool operator < (const node w) const
    {
        if (x != w.x) return x > w.x;
        else return y < w.y;
    }
}s[10];

int main()
{
    s[0] = {2, 2};
    s[1] = {1, 3};
    s[2] = {2, 1};
    
    sort(s, s + 3);
    
    for (int i = 0; i < 3; i ++ ) 
        cout << s[i].x << ' ' << s[i].y << endl;
        
    return 0;
}

输出结果为
2 1
2 2
1 3

容器的排序

并不是所有的STL容器都是可以用sort函数的，像vector，string是可以使用sort函数的，但是像set，map这种容器本身有序，故不允许使用sort排序

同样，在没有写cmp函数的时候，也是默认从小到大进行排序

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;
    
    for (int i = 0; i < 10; i ++ ) v.push_back(i);
    
    sort(v.begin(), v.end());
    
    for (int i = 0; i < 10; i ++ ) cout << v[i] << ' ';
    
    return 0;
}

输出结果为：0 1 2 3 4 5 6 7 8 9

如果我们想从大到小排序：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    vector<int> v;
    
    for (int i = 0; i < 10; i ++ ) v.push_back(i);
    
    sort(v.begin(), v.end(), cmp);
    
    for (int i = 0; i < 10; i ++ ) cout << v[i] << ' ';
    
    return 0;
}

输出结果为：9 8 7 6 5 4 3 2 1 0

再来看string的排序：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main()
{
    string str[3] = {"bbbb", "cc", "aaa"};
    
    sort(str, str + 3);
    
    for (int i = 0; i < 3; i ++ ) 
        cout << str[i] << endl;
        
    return 0;
}

输出结果为：
aaa
bbbb
cc

如果在上面这个例子中，我们要按照字符串长度从小到大排序：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

bool cmp(string str1, string str2)
{
    return str1.length() < str2.length();
}

int main()
{
    string str[3] = {"bbbb", "cc", "aaa"};
    
    sort(str, str + 3, cmp);
    
    for (int i = 0; i < 3; i ++ ) 3 
        cout << str[i] << endl;
        
    return 0;
}

输出结果为：
cc
aaa
bbbb

7.lower_bound() 和 upper_bound()

lower_bound() 和 upper_bound()需要在一个有序数组或容器中

lower_bound(first, last, val)是用来寻找数组或容器的[first, last)范围内第一个值大于等于val的元素的位置，如果是数组就返回该位置的指针，如果是容器，就返回该位置的迭代器

upper_bound(first, last, val)是用来寻找数组或容器的[first, last)范围内第一个值大于val的元素的位置，如果是数组就返回该位置的指针，如果是容器，就返回该位置的迭代器

显然，如果数组或容器中没有需要寻找的元素，则lower_bound()和upper_bound()均返回可以插入该元素的位置的指针或迭代器（即假设存在该元素的时候，该元素应当在的位置），lower_bound()和upper_bound()的时间复杂度均为O(log(last - first))

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int a[10] = {1, 2, 2, 3, 3, 3, 5, 5, 5, 5};
    //注意数组的下标是从0开始的
    //寻找-1
    cout << lower_bound(a, a + 10, -1) - a << ' ' << upper_bound(a, a + 10, -1) - a << endl;
    //寻找1
    cout << lower_bound(a, a + 10, 1) - a << ' ' << upper_bound(a, a + 10, 1) - a << endl;
    //寻找3
    cout << lower_bound(a, a + 10, 3) - a << ' ' << upper_bound(a, a + 10, 3) - a << endl;
    //寻找4
    cout << lower_bound(a, a + 10, 4) - a << ' ' << upper_bound(a, a + 10, 4) - a << endl;
    //寻找6
    cout << lower_bound(a, a + 10, 6) - a << ' ' << upper_bound(a, a + 10, 6) - a << endl;
    
    return 0;
}

输出结果为：
0 0
0 1
3 6
6 6
10 10