STL-map 总结
文档链接
map基本操作
- 在STL的头文件中
<map>中定义了模版类map和multimap，用有序二叉树表存储类型为pair<const Key, T>的元素对序列. 序列中的元素以 const Key 部分作为标识, map 中所有元素的Key值必须是唯一的，multimap 则允许有重复的 Key 值. - 可以将map看作是由Key标识元素的元素集合，这类容器也被称为“关联容器”，可以通过一个Key值来快速决定一个元素，因此非常适合于需要按照Key值查找元素的容器.
- map模版类需要四个模版参数，第一个是键值类型，第二个是元素类型，第三个是比较算子，第四个是分配器类型。其中键值类型和元素类型是必要的.
- 定义map对象的代码示例：
1
map<string, int> m;
- 基本操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21/* 向map中插入元素 */
// [key]操作是map很有特色的操作,如果在map中存在键值为key的元素对, 则返回该元素对的值域部分,否则将会创建一个键值为key的元素对,值域为默认值。所以可以用该操作向map中插入元素对或修改已经存在的元素对的值域部分.
m[key] = value;
m.insert(make_pair(key, value)); // 也可以直接调用insert方法插入元素对,insert操作会返回一个pair,当map中没有与key相匹配的键值时,其first是指向插入元素对的迭代器,其second为true;若map中已经存在与key相等的键值时,其first是指向该元素对的迭代器,second为false。
/* 查找元素 */
// 要注意的是,当与该键值相匹配的元素对不存在时,会创建键值为key（当另一个元素是整形时，m[key]=0）的元素对.
int i = m[key];
// 如果map中存在与key相匹配的键值时,find操作将返回指向该元素对的迭代器,否则,返回的迭代器等于map的end()(参见vector中提到的begin()和end()操作).
map<string, int>::iterator it = m.find(key);
/* 删除元素 */
// 删除与指定key键值相匹配的元素对,并返回被删除的元素的个数.
m.erase(key);
// 删除由迭代器it所指定的元素对,并返回指向下一个元素对的迭代器.
m.erase(it);
/* 其他操作 */
m.size(); // 返回元素个数
m.empty(); // 判断是否为空
m.clear(); // 清空所有元素
map的排序
为了实现快速查找, map内部本身就是按序存储的(比如红黑树). 在我们插入
<key, value>键值对时, 就会按照key的大小顺序进行存储, 这也是作为key的类型必须能够进行<运算比较的原因. 但有些时候需要用特殊的规则进行排序, 这时可以用vector进行间接地排序map中通过
pair储存数据, 所以定义1
2
3
4map<key, value> m;
typedef pair<key, value> pa;
//把m中的值复制到vec中
vector<pa> vec(m.begin(), m.end());之后定义排序函数通过
vector排序例题hdu-1236
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/*************************************************************************
> File Name: c.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: 2019年05月06日 星期一 19时40分20秒
************************************************************************/
using namespace std;
typedef pair<string, int> pa;
int fen[20];
//定义比较函数
bool cmp(const pa &a, const pa &b){
if(a.second != b.second)
return a.second > b.second;
else{
return a.first.compare(b.first) < 0 ? 1 : 0;
}
}
int main(){
int n, m, g;
while(scanf("%d", &n) && n){
scanf("%d %d", &m, &g);
int ans = 0;
map<string, int> jifen;
for(int i = 0; i < m; i++){
scanf("%d", fen + i + 1);
}
for(int i = 0; i < n; i++){
string hao;
int num;
cin >> hao >> num;
jifen[hao] = 0;
for(int j = 0; j < num; j++){
int in;
scanf("%d", &in);
jifen[hao] += fen[in];
}
if(jifen[hao] >= g){
ans++;
}
}
cout << ans << endl;
vector<pa> vec(jifen.begin(), jifen.end());
// 排序
sort(vec.begin(), vec.end(), cmp);
for(pa vecc : vec){
if(vecc.second >= g)
cout << vecc.first << " " << vecc.second << endl;
}
}
return 0;
}