STL-map 总结

文档链接

map基本操作

• 在STL的头文件中<map>中定义了模版类map和multimap，用有序二叉树表存储类型为pair<const Key, T>的元素对序列. 序列中的元素以 const Key 部分作为标识, map 中所有元素的Key值必须是唯一的，multimap 则允许有重复的 Key 值.
• 可以将map看作是由Key标识元素的元素集合，这类容器也被称为“关联容器”，可以通过一个Key值来快速决定一个元素，因此非常适合于需要按照Key值查找元素的容器.
• map模版类需要四个模版参数，第一个是键值类型，第二个是元素类型，第三个是比较算子，第四个是分配器类型。其中键值类型和元素类型是必要的.
• 定义map对象的代码示例：

map<string, int> m;

• 基本操作

/*  向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储存数据, 所以定义

map<key, value> m;
typedef pair<key, value> pa;
//把m中的值复制到vec中
vector<pa> vec(m.begin(), m.end());

• 之后定义排序函数通过vector排序

• 例题hdu-1236

/*************************************************************************
    > File Name: c.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com 
    > Created Time: 2019年05月06日 星期一 19时40分20秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
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;
}

---