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
    4
    map<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秒
     ************************************************************************/

    #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;
    }