CPP 容器排序方法_cpp compare排序

vector

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

vector<int> nums;
sort(nums.begin(),nums.end(),cmp);
1
2
3
4
5
6
7

vector稳定排序，相同值前后顺序不变

 static bool cmp(const int a, const int b ) //不能用引用
 {
     return a > b;
 }

vector<int> nums;
stable_sort(nums.begin(),nums.end(),cmp);
1
2
3
4
5
6
7

map

无法直接排序，转换成pair的vector

    static bool cmp(const pair<int,int>&a, const pair<int,int>&b )
    {
        return a.second > b.second;
        //return a.first > b.first;
    }
    
    unordered_map<int,int> my_map;
    
    vector<pair<int,int>> tmp(my_map.begin(),my_map.end()); 
    sort(tmp.begin(),tmp.end(),cmp);

    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

set

set容器默认排序规则为从小到大
利用仿函数，可以改变排序规则

#include <iostream>
using namespace std;
#include <set>

class mycompare
{
public:
    bool operator()(int v1,int v2){
        return v1>v2;
    }
};
void test01()
{
    set<int> s1;
    s1.insert(1);
    s1.insert(4);
    s1.insert(2);
    s1.insert(5);
    s1.insert(3);

    for(set<int>::iterator it=s1.begin();it!=s1.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
    //1 2 3 4 5 默认从小到大排序

    //利用仿函数
    set<int,mycompare> s2;
    s2.insert(1);
    s2.insert(4);
    s2.insert(2);
    s2.insert(5);
    s2.insert(3);

    for(set<int>::iterator it=s2.begin();it!=s2.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
    //5 4 3 2 1
}

int main()
{
    test01();
    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

priority_queue

堆(heap)的介绍
堆通常是一个可以被看做一棵树的数组对象，满足两个条件：1，堆中的某个结点的值总是不大于或者不小于其父结点的值 2，堆是一颗完二叉树。根结点最大的数叫做大根堆，最小的叫做小根堆。

在C++ STL中没有堆的数据结构，所以借助其中的 priority_queue(默认是大根堆)

常用操作

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
1
2
3
4
5
6

priority_queue使用
定义：priority_queue<Type, Container, Functional> ，priority_queue属于是容器适配器，需要指定底层的容器，

• 第一个参数Type queue里面存的数据的类型，
• 第二个参数Container是要使用的底层容器(一般是vector)，Functional 就是比较的方式（准确来说应该是比较方式的类型）.

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。
//其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
1
2
3
4
5
6

当使用自定的数据类型时，比较方式的写法

1. lambda函数（如果有不清楚的可以参考我的这篇文章：c++11新特性）

auto cmp = [](pair<int, int> left, pair<int, int> right) -> bool { return left.second > right.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)>  pri_que(cmp);
1
2

2. 仿函数实现(最常用)

class mycomparison {
public:
    bool operator()(const pair<int, int>& left, const pair<int, int>& right) {
        return left.second > right.second;
    }
};
priority_queue<pair<int,int>,vector<pair<int, int>>,mycomparison> pri_que2;
1
2
3
4
5
6
7