当前位置: 首页 > 工具软件 > Parallel STL > 使用案例 >

STL—algorithm(2)

孟俊发
2023-12-01


一、什么是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函数的,像vectorstring是可以使用sort函数的,但是像setmap这种容器本身有序,故不允许使用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

 类似资料: