map

• map可以將任何基本類型（包括stl容器）映射到任何基本類型（包括stl容器）
• map的鍵是唯一的, 如果有重復的鍵，新的value會覆蓋舊的value
• map會以鍵從小到大的順序自動排序，這是由于map的內(nèi)部是使用紅黑樹實現(xiàn)的（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數(shù)組

3. map容器內(nèi)元素的訪問

1. 通過下標訪問
   1. 建立映射的時候也可以直接mp["a"] = 2,
2. 通過迭代器訪問
   1. 建立迭代器:map<string, int>::iterator it;
      1. map的迭代器使用與其他容器不同
      2. it->first訪問鍵，it->second訪問值

4. map常用函數(shù)實例解析

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. 刪除一個區(qū)間內(nèi)的所有元素
      1. mp.erase(first, end),刪除[first, end), 可以結(jié)合find使用

3. size(): O(1)

4. clear(): O(N)

5. map的常見用途

1. 需要建立字符或字符串與數(shù)字的映射，使用map可以減少代碼量
2. 判斷大整數(shù)或者其他類型數(shù)據(jù)書否存在的題目，可以把map當bool使用
3. 字符串與字符串的映射也可能遇到

6. 拓展

• map的鍵和值是唯一的，而如果一個鍵需要對應多個值，就只能用multimap。
• 另外c++11還增加了unordered_map,以散列代替map內(nèi)部的紅黑樹實現(xiàn)

7. 習題

1. Speech pattern
   1. 注意點
      1. 如何檢查map中是否存在key
      2. 如何輸入一行字符串
      3. ascii碼中，大寫字母碼數(shù)更小

#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];
        }
        // 結(jié)束一個word的條件是匹配到非字母數(shù)字或者匹配到末尾了
        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;
}