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