一.映射（map）

map是STL的一个关联容器，map中的所有元素都是pair，有序，提供一对一的hash。

  • 第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
  • 第二个可能称为该关键字的值(value)；

map就是从键（key）到值（value）的映射，key 和 value可以是任意你需要的类型。

二.map的基本操作

（以第一个构造的key-value类型为例）

  1. 构造：
    map<string, int> m;

  2. 插入：
    ①insert()：m.insert(pair<string,int>("july",7));
    如果插入的key已经有了对应的value，则插入无效，想让关键字重复出现的话，可以用multimap。
    ②直接赋值：m["March"]=3;

  3. 访问：cout << m["March"];

  4. 查找：
    ①m.find(k);//返回第一个键为k的元素的位置
    ②m.count(k);//返回键为k的元素的数量
    ③m.lower_bound(k);//返回键中第一个大于等于k的元素的位置
    ④m.upper_bound(k);///返回键中第一个大于k的元素的位置

  5. 遍历：
    map<string,int>::iterator it ;
    for (it = m.begin(); it != m.end(); it++) cout << it->first << " " << it->second << endl;

pair用first成员保存关键字，second保存对应的值
6. 清空：m.clear();
7. 删除：m.erase("july"); 删除成功就返回1，删除失败就返回0

三.例题

Problem Description
商店的价格每天都在上涨，想知道“memory”这家店每天的价格排名。

Input
第一行是数字n（n <= 10000），代表商店数量。后面n行，每行有一个字符串（长度小于31，只包含大小写字母），表示商店名称。
然后一行为m（1<=m<=50），表示天数。
后面有m部分，每部分n行，每行是数字s和一个字符串p，表示商店p在这一天涨价s。

Output
包含m行，第i行显示第i天后店铺“memory”的排名。排名定义为如果有t个商店价格高于“memory”，那么它的排名为t+1。

Sample Input

3
memory
kfc
wind
2
49 memory
49 kfc
48 wind
80 kfc
85 wind
83 memory

Sample Output

1
2
#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main() {
  fio
  map<string, int> m;
  int n, d, p;
  while (cin >> n) {
    string s;
    for (int i = 0; i < n; i++) cin >> s;
    cin >> d;
    while (d--) {
      for (int i = 0; i < n; i++) {
      cin >> p >> s;
      m[s] += p; 
    } 
    int num = 1;
    map<string, int>::iterator it;
    for (it = m.begin(); it != m.end(); it++)
      if (it->second > m["memory"]) num++;
    cout << num << endl;
    }
    m.clear();
  }
}