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;
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<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<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;
cout << "🚀 DEFAULT: " << endl;
show(asc_map);
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<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;
}
|
