在了解map之前，我們先看看兩個場景，通過這兩個場景的對比，讓我們知道為什么要存在存儲雙關(guān)鍵字的容器

場景一：判斷一堆字符串中，某一個字符串是否出現(xiàn)過

在沒學(xué)set容器之前，我們只能想到把這一堆字符串存到一個字符型數(shù)組里面，從前往后遍歷每一個字符，判斷某一個字符串是否出現(xiàn)過，這個時間復(fù)雜度是O（N）級別的，如果我們學(xué)過set的話，我們就可以把這一堆字符串存到set容器里面，判斷某一字符串是否出現(xiàn)過的時候直接調(diào)用里面的count接口就可以了，時間復(fù)雜度是O（logN）級別的，所以我們用set特解決場景一問題的時候，時間復(fù)雜是更優(yōu)的

場景二：找出一堆字符串中，某一個字符串出現(xiàn)的次數(shù)

如果找的是次數(shù)，那么set容器就用不了了，set容器存儲的是單關(guān)鍵字，而且里面是不能有重復(fù)元素的，大家可能想到有multiset，它可以存儲重復(fù)的元素，因此要判斷某一個字符串出現(xiàn)的次數(shù)，直接調(diào)用multiset里面的count不就完了嗎？其實還有一個問題，如果這一堆字符串中，所有的字符全都長一樣，比如有10,000個字符串里面的每個字符都是a，當(dāng)我想找“aa”這個字符串出現(xiàn)的次數(shù)的時候，用multiset來解決的話是要遍歷整個紅黑樹一遍的，要全部把它掃描一遍才能統(tǒng)計出a次數(shù)，此時它的時間復(fù)雜度是O（N）級別的，那和數(shù)組存儲沒有任何的差別，所以我們想判斷某一個字符串出現(xiàn)的次數(shù)是不能用set容器的

此時存儲雙關(guān)鍵字的map就登場了，它可以做到存儲雙關(guān)鍵字，它把兩個關(guān)鍵詞綁定在一起，存到紅黑樹里面的，比如在這個問題里面，我想統(tǒng)計某一個字符串出現(xiàn)的字?jǐn)?shù)，map綁定的兩個關(guān)鍵字可以設(shè)置成，第一個是string第二個是int，它的意思是把字符串和出現(xiàn)的次數(shù)綁定在一起，放進(jìn)紅黑樹里面的一個一個節(jié)點中，也就是說紅黑樹的節(jié)點存的是一個結(jié)構(gòu)體，結(jié)構(gòu)體的第一個關(guān)鍵字是字符串，第二個是字符串出現(xiàn)的次數(shù)，此時在查找某一個字符串出現(xiàn)的次數(shù)的時候，直接在這個紅黑中找出對應(yīng)的字符串，拿到它出現(xiàn)的次數(shù)就可以了，至于如何解決這樣的一個問題，我們學(xué)完map的方式之后，在一起編寫代碼

map / multimap?

map 與 multimap 的區(qū)別： map 不能存相同元素， multimap 可以存相同的元素，其余的使??式完全?致。因此，這?只練習(xí)使? map 。?map 與 set 的區(qū)別： set ??存的是?個單獨的關(guān)鍵字，也就是存?個 int 、 char 、?double 或者 string 。? map ??存的是?個 pair<key, value> ，（k-v 模型）不僅有?個關(guān)鍵字，還會有?個與關(guān)鍵字綁定的值，?較?式是按照 key 的值來?較。?也就是中序遍歷的結(jié)果是按照第一個關(guān)鍵字的的大小來做比較的；可以這樣理解：紅?樹???個?個的結(jié)點都是?個結(jié)構(gòu)體，??有兩個元素分別是 key 和?value 。插?、刪除和查找的過程中，?較的是 key 的值。?

1. 存 <int, int> ，來統(tǒng)計數(shù)字出現(xiàn)的次數(shù)；?
2. 存 <string, int> ，來統(tǒng)計字符串出現(xiàn)的次數(shù)；?
3. 存 <string, string> ，表??個字符串變成另?個字符串；?
4. 甚?存 <int, vector<int>> 來表??個數(shù)后?跟了若?個數(shù)......，可以用來存儲樹，就是一個根結(jié)點，后面跟了一堆孩子，int表示根，vector<int>存它的一堆孩子，但用map存儲樹的效率不高，因為查找的時間復(fù)雜是O（logN），后面我們在學(xué)習(xí)哈希表的時候，可以給大家演示一下如何用這個東西存儲樹，因為用哈希表來存儲這樣的形式，查找是很快的

1 創(chuàng)建 map?

#include <iostream>?
#include <vector>?
#include <map>?
using namespace std;?
int main()?
{?map<int, int> mp1;?map<int, string> mp2;?map<string, int> mp3;?map<int, vector<int>> mp4; // 甚?可以掛?個 vectorreturn 0;
}

2 size / empty

1. size ：求紅?樹的??。時間復(fù)雜度： O(1) 。
2. empty ：判斷紅?樹是否為空。時間復(fù)雜度： O(1) 。

3 begin / end

• 迭代器，可以使?范圍 for 遍歷整個紅?樹。
• 遍歷是按照中序遍歷的順序，因此是?個有序的序列。

4 insert

• 向紅?樹中插??個元素。這?需要插??個 pair，可以? {} 形式。?如： mp.insert({1,?2}) 。時間復(fù)雜度： O(log N) 。

5 operator []

• 重載 [] ，使得?map 可以像數(shù)組?樣使?。
• 這是 map 最好?的接?，有了這個重載，map 的使?就變得特別輕松，不?寫很多冗余的代碼。
• 它的底層其實就是調(diào)?了 insert 函數(shù)，并且會返回 val 的引?。我們?前就先學(xué)會使?即可。

6 erase

• 刪除?個元素。時間復(fù)雜度： O(log N) 。

7 find / count

1. find ：查找?個元素，返回的是迭代器。時間復(fù)雜度： O(log N) 。
2. count ：查詢元素出現(xiàn)的次數(shù)，?般?來判斷當(dāng)前元素是否在紅?樹中。時間復(fù)雜度：O(log N) 。

8 lower_bound / upper_bound

1. lower_bound ：?于等于 x 的最?元素，返回的是迭代器。時間復(fù)雜度： O(log N) 。
2. upper_bound ：?于 x 的最?元素，返回的是迭代器。時間復(fù)雜度： O(log N) 。

代碼：

#include <iostream>
#include <map>
#include <string>
using namespace std;//傳引用使得mp不需要拷貝
void print(map<string, int>& mp)
{//&避免拷貝//雙關(guān)鍵字用auto提取出來的是一個pair類型，所以打印要用first、secondfor (auto& p : mp){cout << p.first << " " << p.second << endl;}
}void test1()
{map<string, int> mp;//插入mp.insert({ "張三", 1 });mp.insert({ "李四", 2 });mp.insert({ "王五", 3 });print(mp); //打印出來的結(jié)果按第一個關(guān)鍵字作比較，后面的關(guān)鍵字只起到綁定作用//李四 2//王五 3//張三 1//operator[] 可以讓 map 像數(shù)組一樣使用int a[2] = { 1,2 };a[1] = 4;cout << a[1] << endl; //4cout << mp["張三"] << endl; //1mp["張三"] = 110;cout << mp["張三"] << endl; //110// 注意事項：operator[] 有可能會向 map 中插入本不想插入的元素if (mp["趙六"] == 4) cout << "yes";else cout << "no" << endl;  //no//雖然我們只是想判斷趙六存不存在，但是一旦調(diào)用了[]，就把趙六插入進(jìn)來了// [] 里面的內(nèi)容如果不存在 map 中，會先插入，然后再拿值// 插入的時候：第一個關(guān)鍵字就是 [] 里面的內(nèi)容，第二個關(guān)鍵字是一個默認(rèn)值print(mp);//李四 2//王五 3//張三 110//趙六 0//這樣的邏輯去寫就沒有插入張飛，從mp.count("張飛")這句話就斷掉了//后面的語句沒有執(zhí)行了，此時打印張飛是不存在map里的if (mp.count("張飛") && mp["趙六"] == 4) cout << "yes" << endl;else cout << "no" << endl;  //noprint(mp);cout << endl;//李四 2//王五 3//張三 110//趙六 0//刪除mp.erase("張三");print(mp);cout << endl;//李四 2//王五 3//趙六 0//auto x = mp.lower_bound("李四");map<string, int>::iterator x = mp.lower_bound("李四");cout << x->first << " " << x->second << endl; //李四x = mp.upper_bound("李四");cout << x->first << " " << x->second << endl; //王五
}// 統(tǒng)計一堆字符串中，每一個字符串出現(xiàn)的次數(shù)
void fun()
{string s;map<string, int> mp; // <字符串，字符串出現(xiàn)的次數(shù)>for (int i = 1; i <= 5; i++){cin >> s;mp[s]++; // 體現(xiàn)了 operator 的強大，s字符串不存在會先插入	}print(mp);//輸入//sdf//aa//dd//aa//dd//輸出//aa 2//dd 2//sdf 1
}int main()
{test1();//fun();return 0;
}