5 分钟 读完 (大约 800 个字)

STL-map

STL-map

近日做题用到了C++中STL的map容器，在涉及map的排序过程时，通常有两种方式进行排序

  • Sort by key
  • Sort by value

为了加深这两种排序方式的写法，我又写了一个demo来梳理两种排序方式的写法

map的参数

1
2
3
4
5
template < class Key,                                     // map::关键字类型
           class T,                                       // map::值类型
           class Compare = less<Key>,                     // map::关键字比较函数
           class Alloc = allocator<pair<const Key,T> >    // map::allocator类
           > class map;

Sort by key

升序

默认情况下，map按照key的大小升序排序，即less<Key>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void show(map<string, int>& map) {
    for (auto it = map.begin(); it != map.end(); it++) {
        cout << it -> first << "  " << it -> second << endl;
    }
    cout << "================================" << endl;
    cout << endl;
}		

map<string, int> asc_map;
asc_map["boss"] = 2;
asc_map["abuse"] = 1;
asc_map["unit"] = 3;
asc_map["duty"] = 4;
// map默认按照key的大小升序排列, 即第三个参数为less<string>
cout << "🚀 DEFAULT: " << endl;
show(asc_map);

所以打印结果如下:

1
2
3
4
5
6
🚀 DEFAULT: 
abuse  1
boss  2
duty  4
unit  3
================================

降序

我们可以通过修改map的第三个参数来改变排序规则，使map按照Key的降序排列:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void show(map<string, int, greater<string>>& map) {
    for (auto it = map.begin(); it != map.end(); it++) {
        cout << it -> first << "  " << it -> second << endl;
    }
    cout << "================================" << endl;
    cout << endl;
}

// map可以指定按照key的大小升序或降序排列
map<string, int, greater<string>> desc_map;
desc_map["boss"] = 2;
desc_map["abuse"] = 1;
desc_map["unit"] = 3;
desc_map["duty"] = 4;
cout << "🚀 DESC:" << endl;
show(desc_map);

打印结果为:

1
2
3
4
5
6
🚀 DESC:
unit  3
duty  4
boss  2
abuse  1
================================

Sort by value

对map的value进行排序需要借助别的容器，比如vector，将每一个map中的entry放到一个新的vector中，然后使用sort()函数加上自定义比较规则cmp即可对map中的元素按照value进行排序:

demo中使用的比较函数将按照value升序排序：

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
// 升序排列
bool cmp(const pair<string, int>& p1, const pair<string, int>& p2) {
    return p1.second < p2.second;
}

void sortByValue(map<string, int>& map) {
    vector<pair<string, int> > data;
    for (auto it = map.begin(); it != map.end(); it++) {
        data.push_back(make_pair(it -> first, it -> second));
    }
    sort(data.begin(), data.end(), cmp);
    for (pair<string, int> p : data) {
        cout << p.first << "  " << p.second << endl;
    }
    cout << "================================" << endl;
    cout << endl;
}

// 对map的value进行排序
map<string, int> value_sort_map;
value_sort_map["boss"] = 2;
value_sort_map["abuse"] = 1;
value_sort_map["unit"] = 3;
value_sort_map["duty"] = 4;
cout << "🚀 SORT BY VALUE" << endl;
sortByValue(value_sort_map);

打印结果如下：

1
2
3
4
5
6
🚀 SORT BY VALUE
abuse  1
boss  2
unit  3
duty  4
================================

完整代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <map>
#include <utility> // 使用make_pair()
#include <string>
#include <vector>
using namespace std;

// 升序排列
bool cmp(const pair<string, int>& p1, const pair<string, int>& p2) {
    return p1.second < p2.second;
}

void sortByValue(map<string, int>& map) {
    vector<pair<string, int> > data;
    for (auto it = map.begin(); it != map.end(); it++) {
        data.push_back(make_pair(it -> first, it -> second));
    }
    sort(data.begin(), data.end(), cmp);
    for (pair<string, int> p : data) {
        cout << p.first << "  " << p.second << endl;
    }
    cout << "================================" << endl;
    cout << endl;
}


void show(map<string, int>& map) {
    for (auto it = map.begin(); it != map.end(); it++) {
        cout << it -> first << "  " << it -> second << endl;
    }
    cout << "================================" << endl;
    cout << endl;
}

void show(map<string, int, greater<string>>& map) {
    for (auto it = map.begin(); it != map.end(); it++) {
        cout << it -> first << "  " << it -> second << endl;
    }
    cout << "================================" << endl;
    cout << endl;
}


int main() {
    map<string, int> asc_map;
    asc_map["boss"] = 2;
    asc_map["abuse"] = 1;
    asc_map["unit"] = 3;
    asc_map["duty"] = 4;
    // map默认按照key的大小升序排列, 即第三个参数为less<string>
    cout << "🚀 DEFAULT: " << endl;
    show(asc_map);

    // map可以指定按照key的大小升序或降序排列
    map<string, int, greater<string>> desc_map;
    desc_map["boss"] = 2;
    desc_map["abuse"] = 1;
    desc_map["unit"] = 3;
    desc_map["duty"] = 4;
    cout << "🚀 DESC:" << endl;
    show(desc_map);


    // 对map的value进行排序
    map<string, int> value_sort_map;
    value_sort_map["boss"] = 2;
    value_sort_map["abuse"] = 1;
    value_sort_map["unit"] = 3;
    value_sort_map["duty"] = 4;
    cout << "🚀 SORT BY VALUE" << endl;
    sortByValue(value_sort_map);
    return 0;
}
3 分钟 读完 (大约 485 个字)

C++-priority_queue

C+±priority_queue

C++ STL-priority_queue 用法

priority_queue存在于头文件<queue>中，以下代码解释了该容器如何使用

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

struct Node{
    int a,b;
    Node(){}
    Node(int aa,int bb):a(aa),b(bb){}

    // 二级排序，a相同时按照b升序排序，否则按照a升序排序
    // (a,b): (1,1)<(1,2)<(2,1)<(2,2)
    // 这里重载的大于号和小于号在逻辑上等价
    bool operator < (const Node &r) const{
        if(a==r.a)
            return b<r.b;
        else
            return a<r.a;
    }
    bool operator > (const Node &r) const{
        if(a==r.a)
            return b>r.b;
        else
            return a>r.a;
    }
};

int main(){

    //priority_queue 是基于堆实现的优先队列

    // .size()返回当前优先队列的元素个数
    // empty()为true表示当前队列为空，false表示不空
    priority_queue<int> tmp_q;
    cout<<tmp_q.size()<<endl;   //0
    cout<<tmp_q.empty()<<endl;  //1
    tmp_q.push(1);
    cout<<tmp_q.size()<<endl;   //1
    cout<<tmp_q.empty()<<endl;  //0
    tmp_q.pop();
    cout<<tmp_q.size()<<endl;   //0
    cout<<tmp_q.empty()<<endl;  //1

    // priority_queue<int> 表示队列中存储的元素是int类型（STL模板类）
    // 默认priority_queue表示队列按照less出队
    // 后出队的元素比先出队的元素要小，出队的元素越来越小，所以是less
    // push 加入元素
    // top 返回队首元素
    // pop 队首元素出队
    priority_queue<int> q;  
    q.push(5);
    q.push(6);
    cout<<q.top()<<endl;        //6
    q.pop();
    cout<<q.top()<<endl;        //5
    q.pop();

    // greater 表示后出队的元素比先出队的元素要大, 出队的元素越来越大，所以是greater
    priority_queue<int, vector<int>, greater<int>> q_greater;
    // <>中第二个参数vector<int>表示优先队列中使用vector<int> 存储元素，可以更换成deque
    // 第二个参数中更换的其他类型应支持.begin(),.end(),.push(),.pop()等操作
    //  绝大多数情况都使用vector<>，极少需要更换
    // 例子：priority_queue<int, deque<int>, greater<int>> q_greater;
    q_greater.push(5);
    q_greater.push(6);
    cout<<q_greater.top()<<endl;    //5
    q_greater.pop();
    cout<<q_greater.top()<<endl;    //6
    q_greater.pop();

    // 更换为double类型，出队法则是less
    priority_queue<double, vector<double>, less<double>> q_less;
    q_less.push(5.2);
    q_less.push(6.6);
    cout<<q_less.top()<<endl;       //6.6
    q_less.pop();
    cout<<q_less.top()<<endl;       //5.2
    q_less.pop();

    // 自定义类Node的priority_queue 使用greater需要对元素重载大于号
    priority_queue<Node, vector<Node>, greater<Node>> q_greater_node;
    q_greater_node.push(Node(1,1));
    q_greater_node.push(Node(1,2));
    q_greater_node.push(Node(2,1));
    q_greater_node.push(Node(2,2));
    cout<<q_greater_node.top().a<<" "<<q_greater_node.top().b<<endl;    // 1 1
    q_greater_node.pop();
    cout<<q_greater_node.top().a<<" "<<q_greater_node.top().b<<endl;    // 1 2
    q_greater_node.pop();
    cout<<q_greater_node.top().a<<" "<<q_greater_node.top().b<<endl;    // 2 1
    q_greater_node.pop();
    cout<<q_greater_node.top().a<<" "<<q_greater_node.top().b<<endl;    // 2 2
    q_greater_node.pop();

    // 自定义类Node的priority_queue 使用less需要对元素重载小于号
    priority_queue<Node, vector<Node>, less<Node>> q_less_node;
    q_less_node.push(Node(1,1));
    q_less_node.push(Node(1,2));
    q_less_node.push(Node(2,1));
    q_less_node.push(Node(2,2));
    cout<<q_less_node.top().a<<" "<<q_less_node.top().b<<endl;  // 2 2 
    q_less_node.pop();
    cout<<q_less_node.top().a<<" "<<q_less_node.top().b<<endl;  // 2 1
    q_less_node.pop();
    cout<<q_less_node.top().a<<" "<<q_less_node.top().b<<endl;  // 1 2
    q_less_node.pop();
    cout<<q_less_node.top().a<<" "<<q_less_node.top().b<<endl;  // 1 1
    q_less_node.pop();

    return 0;
}
关注我

归档

最新文章

标签

Algorithm1
Blog1
C++1
Hexo1
Java2
LaTeX1
Life1
Moment2
MongoDB1
STL2
Spring Boot10
Vue1
redis2
机器学习1
×