map

• map可以将任何基本类型（包括stl容器）映射到任何基本类型（包括stl容器）
• map的键是唯一的, 如果有重复的键，新的value会覆盖旧的value
• map会以键从小到大的顺序自动排序，这是由于map的内部是使用红黑树实现的（set也是）

1. how to use?

#include <map>
using namespace std;

2. map的定义

• 格式：map<typename1, typename2> mp
• 案例：
  • map<string, int> mp;
  • map<set<int>, int> mp;
• 注意：如果是字符串到整型的映射，必须使用string而不能用char数组

3. map容器内元素的访问

1. 通过下标访问
   1. 建立映射的时候也可以直接mp["a"] = 2,
2. 通过迭代器访问
   1. 建立迭代器:map<string, int>::iterator it;
      1. map的迭代器使用与其他容器不同
      2. it->first访问键，it->second访问值

4. map常用函数实例解析

1. find(key): 返回键为key的映射的迭代器，时间复杂度O(logN)

   • 实例：map<string, int>::iterator it = mp.find("abc");

2. erase()

   1. 删除单个元素：
      1. mp.erase(it), it为下次要删除的元素的迭代器，O(1)
      2. mp.erase(key), key为欲删除的映射的键，O(logN)
   2. 删除一个区间内的所有元素
      1. mp.erase(first, end),删除[first, end), 可以结合find使用

3. size(): O(1)

4. clear(): O(N)

5. map的常见用途

1. 需要建立字符或字符串与数字的映射，使用map可以减少代码量
2. 判断大整数或者其他类型数据书否存在的题目，可以把map当bool使用
3. 字符串与字符串的映射也可能遇到

6. 拓展

• map的键和值是唯一的，而如果一个键需要对应多个值，就只能用multimap。
• 另外c++11还增加了unordered_map,以散列代替map内部的红黑树实现

7. 习题

1. Speech pattern
   1. 注意点
      1. 如何检查map中是否存在key
      2. 如何输入一行字符串
      3. ascii码中，大写字母码数更小

#include<iostream>
#include<string>
#include<map>
using namespace std;
int N;

bool isAlphaNum(char ch) {
    if((ch >= 'A' && ch <= 'z') || (ch >= '0' && ch <= '9')) return true;
    else return false;
}

int main() {
    // 应该read整行
    string sentence;
    getline(cin, sentence);
    map<string, int> counter;
    string word;
    for(int i = 0; i < sentence.size(); i++) {
        if(isAlphaNum(sentence[i])) {
            if(sentence[i] >= 'A' && sentence[i] <= 'Z') {
                sentence[i] = sentence[i]+32;
            }
            word += sentence[i];
        }
        // 结束一个word的条件是匹配到非字母数字或者匹配到末尾了
        if(!isAlphaNum(sentence[i]) || i == sentence.size() - 1) {
            // 必须要进行判断字符串的长度是不是空的。如果是空的，那么跳过。"are! are!" 当时这种情况的话，这个条件非常必要。
            if(word.length()!=0)
                counter[word]++;
            word = "";
        }
        
    }
    // why doesn't it print?
    int max_c = 0;
    string max_s;
    for(map<string, int>::iterator it = counter.begin(); it != counter.end(); it++) {
        if(max_c < it->second) {
            max_s = it->first;
            max_c = it->second;
        }
    }
    cout << max_s<< " " <<max_c<<endl;
    
    return 0;
}