我們要開始學(xué)習(xí)map和set的使用，雖然使用更加復(fù)雜，但是STL整體的設(shè)計，本身就具有很強(qiáng)的前瞻性和延續(xù)性，比如說迭代器等，我們順著文檔來看。這也是除了vector之外最重要的容器，當(dāng)然還有unordered_map 和 unord_set，其實(shí)這幾個也是C++里面用的最多的。

Set學(xué)習(xí)

模版參數(shù)

這里的set呢，它只有一個模版參數(shù)可就是T，然后還有一個比較器，默認(rèn)是小于，它給一個比較器呢，就是為了，有些地方默認(rèn)的operator <重載的比較不符合你的要求，假設(shè)你用的是指針，但是指針是按地址比較大小，當(dāng)這個T是一個指針的時候，但是你不想按地址比較大小，那么原生的行為不符合怎么辦，那你是不是就可以傳仿函數(shù)呀，去控制里面的比較規(guī)則呀。在下面就是空間配置器，它是負(fù)責(zé)申請內(nèi)存。

insert()

我們看到函數(shù)參數(shù)中有一個，value_type類型，但是不知道這個是什么類型。我們先寫一個最簡單來看看。
》set s;set 沒有push() ，線性表、鏈表、隊(duì)列等都是線性結(jié)構(gòu)，才會有push()接口 。后面非線性結(jié)構(gòu)的都是insert()接口了。我們隨便插入一些數(shù)據(jù)s.insert(4)；s.insert(5)…我們插入5個值。然后我們定義一個迭代器，set::iterator it = s.begin()；這個set呢，它是一個雙向迭代器，它底層用了特殊的算法迭代，是走的另一種非遞歸，后面也會講，不用像我們在前面的二叉樹OJ那里用棧模擬，但是它這里非遞歸有前提的，前提就是，它要有三叉鏈，它的邏輯底層是有parent成員變量的，反正我們先不管，后面我們才討論底層。
》然后我們while循環(huán)遍歷，while(it != s.end())，cout<< *it << " "；it++然后我們看到，走出來就是有序的！其實(shí)它不僅僅是有序的，它是在有序的情況下還加了一些東西，如果值已經(jīng)有了，它還會不會插入？不會了！所以嚴(yán)格來說，它不是排序，而是一個排序?去重！
》它這塊支持迭代器，是不是有普通迭代器支持可讀可寫，還有const迭代器只讀。然后它還有反向迭代器，就不演示了。
》它既然支持迭代器，那么就會支持范圍for。其實(shí)范圍for和我們迭代器在底層上是一樣的，只是在上層看來有些區(qū)別。
》我們發(fā)現(xiàn)，const迭代器和普通迭代器都是不支持修改的 ，雖然一個叫iteratro，一個叫const iterator，但是底層都是用的一個const_iterator來實(shí)現(xiàn)的。
》另外重載的兩個insert()函數(shù)用的很少。平時也很少用在某一個位置插入，這個接口價值很小。
》insert()不會有迭代器失效的問題，不像順序表，挪動數(shù)據(jù)會影響相對關(guān)系，它的erase()是會有迭代器失效的問題。

void test_set1()
{set<int> s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);// 排序 + 去重 set<int>::iterator it = s.begin();while (it != s.end()){//*it = 10;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;
}

empty()/size()/max_size()

erase()/find()—兩個是要配合的

erase()函數(shù)主要有兩種，一種是在某個位置刪除，另外一種是刪除某一個具體的值。第三種刪除特定的區(qū)間，這個用的很少。
》這塊要玩刪除的話，就得配合find()函數(shù)。我們前面插入了很多值，我們隨便set::iterator it = find(2)一個值，那么我們**怎么判斷是找到還是沒找到呢？**如果元素被找到了，是會返回value值對應(yīng)的迭代器，查找失敗就會返回end()迭代器。是不是就是if(pos != s.end())就是找到了呀。
》我們來對比一下，set自帶的find()和算法里面的find()有什么區(qū)別呢？ set::iterator it = find(20) 和 pos = find(s.begin()，s,end()，20),算法里面的find，能不能行呢？是行的。它們的區(qū)別很大，數(shù)據(jù)量小還好，數(shù)據(jù)量大就會差別很大。set的find()的效率是logN，而算法的查找效率是O(N)，因?yàn)樗惴ǖ氖潜┝Σ檎?。這個算法的find()查找不是給set用的，而是給像vector它們用的。

void test_set2()
{set<int> s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);set<int>::iterator pos = s.find(20);  // O(logN)if (pos != s.end()){cout << "set.find找到了" << endl；}pos = find(s.begin(), s.end(), 2); // O(N)if (pos != s.end()){cout << "find找到了" << endl;}
}

》如果我們要erase了呢？，我想將我從鍵盤中輸入的值erase()掉，通過find()查找我們輸入的值再去erase(迭代器)。當(dāng)erase()成功之后，對應(yīng)的位置就不能訪問了，已經(jīng)是失效了。我們可以通過查找進(jìn)行持續(xù)的刪除。我們還可以直接傳參數(shù)去刪除，即erase(3)；也就是你可以理解成，這個erase(3)，相當(dāng)于調(diào)用了find()?erase(迭代器)。
》前面第一種是先是找到了再去刪除，它們會有什么區(qū)別呢？第二種用法，如果沒有找到直接去刪除是不會報錯的；而你第一種調(diào)用了find()沒有找到，你還是去刪除，是會報錯的。
》size_type erase(value)是會返回一個size_type類型的數(shù)據(jù)，他為什么不用bool類型呢，是因?yàn)樗土硗庵v的東西契合起來。我們能夠看到，刪除成功是返回1，刪除失敗是會返回0，為什么是返回這個，而不是返回bool呢？因?yàn)榇龝何覀冞€要學(xué)另外一個版本，另外一個版本是允許冗余的。

void test_set3()
{set<int> s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);cout << s.erase(3) << endl;cout << s.erase(30) << endl;for (auto e : s){cout << e << " ";}cout << endl;set<int>::iterator pos = s.find(3);if (pos != s.end())s.erase(pos);for (auto e : s){cout << e << " ";}cout << endl;/*int x;while (cin >> x){set<int>::iterator pos = s.find(x);if (pos != s.end()){s.erase(pos);cout << "刪除" << x << "成功" << endl;}else{cout << x << "不在set中" << endl;}for (auto e : s){cout << e << " ";}cout << endl;}*/if (s.count(5)){cout << "5在" << endl;}if (s.find(5) != s.end()){cout << "5在" << endl;}
}

swap()

swap()就跟我們以前講的一樣，比如說你要交換兩個set的對象，用算法的swap()直接交換是深拷貝，是樹的拷貝，代價很大，所以set自己有一個swap()，它們交換指針，代價小很多。

count()

count()函數(shù)這個設(shè)計是和一個版本對應(yīng)起來的，就是你給我一個值，我看一下這個值在我set里面有幾個，在這里的set而言，無非就是1個和0個。但是待會兒還有一個對稱的版本。我們說了，有些場景可能需要的不是排序?去重，而只是排序，那么它們就設(shè)計了multile版本，它是多樣性的意思，它是允許冗余的，它們的接口設(shè)計都是保持的一致。
》count()函數(shù)有一個非常有意義的點(diǎn)就是，判斷在不在，比用find()方便。比如說，我要判斷一個值在還是不在，用count()是不是就很方便呀，比如說我要count(3)，if(s.count(3))看一下這個3在不在，在的話是會返回1，不在的話，是會返回0。如果用find()的話就沒那么方便了嗎，要這樣if(s.find(3) != s.end())是不是相對來說不太方便了。

lower_bound()函數(shù)

lower_bound()是干嘛呢？比如lower_bound(30)是幫你去找 >= 30的值的迭代器，但是它在這兒又有一點(diǎn)問題，lower_bound()和upper_bound()的返回值還有點(diǎn)不一樣。我們試驗(yàn)一下。
》你看set::iterator lowIt = s.lower_bound(3)；如果有3，它會返回3位置的迭代器，沒有就返回 > 3的值，我們插入的值里面是有3的，所以返回的是3 的迭代器。如果是set::iterator lowIt = s.lower_bound(6)；我們插入里面沒有6，那它會返回什么呢？返回的是7的迭代器。
》它什么情況下比較有用么，比如說：要求刪除 >= x的所有值，那么你就不用遍歷去刪除了，這里的lower_bound()函數(shù)就可以幫干這件事情，怎么刪除呢？不要忘了，我們的erase()是支持迭代器區(qū)間的刪除！那么erase()左區(qū)間可以給個lowIt變量，右區(qū)間可以給end()，相當(dāng)于是左閉右開【），即erase(lowIt，s.end())；

void test_set4()
{set<int> s;s.insert(4);s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(9);// 返回>= val得位置迭代器  3返回3位置  6 返回7位置/*set<int>::iterator lowIt = s.lower_bound(3); 存在lowIt = s.lower_bound(6); 不存在*/for (auto e : s){cout << e << " ";}cout << endl;// 要求刪除>=x的所有值int x;cin >> x;set<int>::iterator lowIt = s.lower_bound(x);s.erase(lowIt, s.end());for (auto e : s){cout << e << " ";}cout << endl;
}

upper_bound()

比如upper_bound(60)，如果有60的話，它是不回返回60，而是返回 > 60的值，我們來驗(yàn)證一下。這里我們比如說是，set::iterator upIt = s.upper_bound(5)，我們傳一個5，然后再來一個，set::iterator upIt = s.upper_bound(6)，我們傳的是6，這兩個區(qū)別就是一個值在我們插入的里面，一個是不存在。我們來看看結(jié)果，我傳的是5，有5它返回5了嗎？答案是：不會的！它返回的是7，我傳的是6，它返回的是7。所以，這里的upper_bound()，它要找的不是 >=的值，它是返回 > x位置的迭代器。
》所以upper_bound和lower_bound，一個是返回 >=，一個是返回 >。其實(shí)他們**兩個可以配合起來并配合ease()，貫徹“左閉右開【）”。**比如說要刪除 x <= [] <=y的區(qū)間，是不是就可以將這兩個配合起來使用了呀。比如auto leftIt = s.lower_bound(x)，auto rightIt = s.upper_bound(y)，erase(letfIt，rightIt)所以它會刪除【x，y】

void test_set5()
{set<int> s;s.insert(4);s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(9);for (auto e : s){cout << e << " ";}cout << endl;// 返回>x位置的迭代器  -》 都是返回 7位置的迭代器//set<int>::iterator upIt = s.upper_bound(5);  // 存在//upIt = s.upper_bound(6); // 不存在// 刪除x <=  <= y的區(qū)間 刪除 [x,y]int x, y;cin >> x >> y;auto leftIt = s.lower_bound(x);  // [auto rightIt = s.upper_bound(y); // )s.erase(leftIt, rightIt);for (auto e : s){cout << e << " ";}cout << endl;
}

講講multiset版本

multiset它是允許鍵值冗余的，它的用法和set一樣的，但就是要記一下它的名字，比如mutilset mS；它是排序不去重。
》真正有區(qū)別的就是count()函數(shù)，比如說你要統(tǒng)計一個值s.count(1)；set版本那邊的count沒有給bool類型的返回值，而是給int類型返回值，這其實(shí)是為保證接口的設(shè)計一致。其實(shí)set不需要count，是個bool就行了，但是為了和multiset保持一致，返回值類型也是int。
》同樣的，set版本里面的erase()函數(shù)的返回值不是bool，而是size_type，也是為了和multiset里面的erase()設(shè)計保持一致，可以返回刪除了幾個對應(yīng)的值。
》還有一個區(qū)別就是這里的find()函數(shù)，比如我這里有多個同樣的值，那么我auto pos = s.find(3)會返回哪個3的迭代器呢？那么這里就可以做一件事情，它會返回中序的第一個，可以由while(pos != s.end())cout << *pos << " "；++pos驗(yàn)證。我們以后講了搜索樹，會知道，插入的時候，樹是會旋轉(zhuǎn)的，所以同樣的值插入在左邊還是右邊都不影響。

void test_set6()
{multiset<int> s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);s.insert(3);s.insert(3);s.insert(3);s.insert(3);// 排序 set<int>::iterator it = s.begin();while (it != s.end()){//*it = 10;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;cout << s.count(1) << endl;cout << s.erase(1) << endl;for (auto e : s){cout << e << " ";}cout << endl;// 多個x的話，find返回中序第一個xauto pos = s.find(3);while (pos != s.end()){cout << *pos << " ";++pos;}cout << endl;
}

看一下題目

題一：

兩個數(shù)組的交集，找交集怎么找呢？是不是可以考慮這樣，你也有，我也有的就是交集。
》最簡單的方案就是，將其中一個數(shù)組放進(jìn)set里面，我直接去你里面找，是不是太慢了。我們可以遍歷將值inser()插入進(jìn)set里面。然后繼續(xù)遍歷另一個數(shù)組，在我們的set里面找對應(yīng)的值，那其中是不是就可以用count()函數(shù)而不必調(diào)用find()函數(shù)呀，然后，存在的話，就將值插入到我們另一個開辟的數(shù)組里面。但是這里有可能過不去，為什么呢？因?yàn)樵谖覀冮_辟的vector來存交集的值，會有重復(fù)！因?yàn)榻患请[形的要求你去重的。
》那你的另一個數(shù)組是不是也用set來去重一下呀。但是這個算法不夠高效，因?yàn)?#xff0c;假設(shè)你set里面有n個元素，那么每調(diào)用一次count()的時間復(fù)雜度是logN，那么總的時間復(fù)雜度是不是N*logN。
》還有一個優(yōu)化算法，這個優(yōu)化算法在很多找交集都能有效。找并集的話，只需要一個set就行了?，F(xiàn)在來說一個交集/差集的優(yōu)化算法，這個算法不一定要set，但是set用在這里剛剛好。
》我們inset()到set之后是不是就相當(dāng)于有序了呀，有了排序就好說。如果你要求并集的話，只要放到一個set里面就行了，它是可以去重的。那么交集和差集怎么搞呢，有些地方需要同步，同步數(shù)據(jù)的話就要找交和差集。
》兩個數(shù)組已經(jīng)是有序了的，然后分別有一個指針先是指向各自的開始。交集的話：兩個相比較的話，1.小的++；2.相等的就是交集，同時++；3.有一個結(jié)束就結(jié)束了。這個優(yōu)化之后就變成了時間復(fù)雜度是2N了。
》這個算法除了可以找交集，還可以找差集。1.相比較，小的就是差集，小的++；2.相等的話，同時++；3.一個走到頭了，另一個剩下的是不是也屬于差集了。
》差集和交集在，服務(wù)器和你網(wǎng)盤需要同步的時候是有用到的。比如你有一個服務(wù)器文件夾和一個本地文件夾，你要將本地文件同步到服務(wù)器文件里面，相當(dāng)于備份嘛，那是不是一方刪除，另一方也會刪除，你添加的，另一方是不是也要添加呀。

map

首先map數(shù)據(jù)結(jié)構(gòu)里面呢，有一個Key和Value。它里面有一個valuse_type類型，它里面不是把數(shù)據(jù)分開存儲的，不像我們前面講的，自己寫的搜索樹里面，單獨(dú)分開定一個key和value，而map，它是將key和value是放在一個結(jié)構(gòu)里面的，這個結(jié)構(gòu)是在C++里面被定義成pair<>類型，pair就是一對一對的意思，在map這里呢叫做鍵值對。

insert()

》我們先用map來存一個字典的例子，map的insert()插入的一個值是value_type類型的，value_type其實(shí)就是pair<>類型的數(shù)據(jù)。pair<>類型呢，有兩個參數(shù)，第一個參數(shù)叫做first，第二個參數(shù)叫做second。

》如果我們想插入的話，map<string, string>dict；dict.insert(pair<string，string>(“sort”，“排序”))；這是第一種，匿名對象的一種傳參數(shù)，用起來比正常的要舒服很多。第二種，正常點(diǎn)是這樣的，pair<string，string>kv(“insert”，“插入”)；dict.insert(kv)；還有第三種方式，用起來更爽：用到make_pair，make_pair就是制造一個pair對象，即dict.insert(make_pair(“l(fā)eft”，左邊))；
》前面第一、第二種都是借用的pair的構(gòu)造函數(shù)來進(jìn)行。第三種，make_pair是一個函數(shù)模版，它的優(yōu)勢是不用聲明參數(shù)，讓它自動推導(dǎo)。第四種，還能這么寫，dict.insert({“right”，右邊})；雖然知道可以這么寫，但是目前還是不太清楚為什么，這個涉及到C++11點(diǎn)類型轉(zhuǎn)換，C++11再講。
》map的遍歷：map<string，string>::iterator it = dict.begin()；我們也說過，如果你清楚的情況下可以用auto讓它自己推導(dǎo)。while(it != dict.end())coyt << it << " "；++it；**發(fā)現(xiàn)不支持it**。有沒有人想過，你直接分別單獨(dú)用變量表示key和value不就好了嘛，為什么要封裝一個pair？這個地方就能看出來，為什么要搞一個pair了。這個map的迭代器和鏈表的迭代器有些相似，它用自定義類型去封裝，封裝節(jié)點(diǎn)，只不過在map這里是一個樹的節(jié)點(diǎn)，那么解引用是不是去調(diào)用operator呀，那C++是否支持一個函數(shù)返回兩個值呢？這里it本質(zhì)是it->operator()，它是不是要返回節(jié)點(diǎn)里面的數(shù)據(jù)呀，對于set還好，set里面只有一個key，但是map這里是一個key和value，那C++是否支持一次返回兩個值呢？不支持是吧，但是你這里用到了模擬解引用的行為，那就要返回節(jié)點(diǎn)，如果你這里分別單獨(dú)用變量表示key和value就沒辦法搞了，所以我把key和value給你打包成一個結(jié)構(gòu)數(shù)據(jù)，這個結(jié)構(gòu)數(shù)據(jù)就叫做pait<>類型，所以operator，返回的是節(jié)點(diǎn)數(shù)據(jù)，這個節(jié)點(diǎn)數(shù)據(jù)是一個pair<>類型。
》但是你這類型pair<>支不支持流呢，即cout << it嗎？答案是：不支持。有同學(xué)說，我們來支持一下就可以了，但是支持的話是不是就要改庫里面的代碼呀，那么我們換一種方法玩。你不是一個結(jié)構(gòu)嘛，那么我們就是cout << (*it).first << “:” << (*it).second << endl；但是在這種地方，你的迭代器是不是指針的行為呀，那你還用解引用*嗎？不會，而是用迭代器重載的->運(yùn)算符來用*，即cout << it->first << “:” << it->second << endl；
》那這里的范圍for，for(const auto& kv : dict)，kv其實(shí)是返回的*解引用后的pair數(shù)據(jù)類型，用kv.first()和kv.second()來訪問。

void test_map1()
{map<string, string> dict;// pair構(gòu)造函數(shù)dict.insert(pair<string, string>("sort", "排序"));pair<string, string> kv("insert", "插入");dict.insert(kv);// make_pairauto ret1 = dict.insert(make_pair("left", "左邊"));auto ret2 = dict.insert(make_pair("left", "剩余"));dict["operator"] = "重載"; // 插入+修改dict["left"] = "左邊、剩余"; // 修改dict["erase"];  // 插入cout << dict["left"] << endl; // 查找// C++11 再講//dict.insert({ "right", "右邊" });// 遍歷//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//cout << *it << " "; // it->operator*()//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (const auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}
}//mapped_type& operator[] (const key_type& k)
//{
//	pair<iterator,bool> ret = insert(make_pair(k, mapped_type()));
//
//	//return (*(ret.first)).second;
//	return ret.first->second;
//}

那你現(xiàn)在統(tǒng)計水果出現(xiàn)的次數(shù)是不是就很方便了呀，先構(gòu)建一顆map樹，map<string，int> countMap；for(aoto& str : arr)是不是就可以先調(diào)用map的find()函數(shù)，auto it = countMap.find(str)；如果水果沒有插入到我們的樹里面，那么我們就構(gòu)建一個pair<string，int>，即countMap.insert(make_pair(str，1))；如果已經(jīng)存在了，就it->second++;

void test_map2()
{string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };// 17:08繼續(xù)/*map<string, int> countMap;for (auto& str : arr){map<string, int>::iterator it = countMap.find(str);if (it != countMap.end()){it->second++;}else{countMap.insert(make_pair(str, 1));}}*///map<string, int> countMap;//for (auto& str : arr)//{//	//pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));//	auto ret = countMap.insert(make_pair(str, 1));//	if (ret.second == false)//	{//		ret.first->second++;//	}//}map<string, int> countMap;for (auto& str : arr){countMap[str]++;}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}int main()
{//test_set6();test_map1();return 0;
}

其實(shí)map這里最重要的就是剛剛講的，那么剛剛上面講的呢還有優(yōu)化的空間，這個優(yōu)化的空間是要幫我們?nèi)ジ愫竺娴氖虑椤?/p>

map<string, int> countMap;for (auto& str : arr){map<string, int>::iterator it = countMap.find(str);if (it != countMap.end()){it->second++;}else{countMap.insert(make_pair(str, 1));}}

這個代碼其實(shí)是可以改進(jìn)優(yōu)化的。find()這里有這么一個問題，我去find()是不是一直去找，不在的話是不是我就相當(dāng)于從根找到尾了呀，沒有的話，我就得去插入，插入是不是又得去找一次，那是不是重復(fù)了呀，find()找一次，沒找到后，insert又找了一次。其實(shí)不優(yōu)化也無關(guān)痛癢，但是這里講優(yōu)化是為下面做鋪墊，為下面的玩法做鋪墊。
》所以這里就可以用insert()來做一件事情，正常的呢，insert()的返回值是一個pair<>類型的數(shù)據(jù)，pair的first數(shù)據(jù)被設(shè)置成為一個iterator迭代器，這個迭代器指向兩種可能，要么指向新插入的元素（插入成功），要么指向與key相等的元素（插入不成功）。意味著是這樣的，我insert()返回的pair<>類型的數(shù)據(jù)，first是一個迭代器，這個迭代器呢，一定是指向一個位置的，要么是你新插入元素的迭代器，要么是沒有插入成功，因?yàn)榉慈哂嗟穆?#xff0c;那么itreator就是已經(jīng)有了的元素的迭代器。那么pair<>的second數(shù)據(jù)類型是一個bool，如果是新插入的，那就是true，如果已經(jīng)有相等的了，就是flase。也就是說，它插入成功或者失敗是會返回bool值的。我insert()返回的pair的迭代器不管你是插入成功還是失敗都會返回一個元素的位置，那么就可以利用起來。

》就拿上面統(tǒng)計水果個樹來說，如果水果已經(jīng)存在map里面了，還會插入嗎？不會。**這個待會兒對我們理解"[]"的使用非常重要 。**它insert()返回的pair類型的值非常有意義和我們待會兒要講的“【】”有很大關(guān)系。我們插入atuo ret1 = dict.insert((“l(fā)eft”，左邊))和auto ret2 = dict.insert((“l(fā)eft”，剩余))，按理來說第一次插入的left是成功的，ret1的second數(shù)據(jù)是true，first數(shù)據(jù)是新插入元素的迭代器；第二次插入left，ret2的second數(shù)據(jù)是flase，然后ret2的first數(shù)據(jù)和ret2一樣的。
》我們就可以進(jìn)行對上面代碼改進(jìn)，不需要再調(diào)用find()函數(shù)了，就調(diào)用insert()就行。我們不管有沒有插入，都調(diào)用insert()函數(shù)，即pair<map<string，int>::iterator，bool> ret = countMap.insert(make_pair(str，1))；寫簡單一點(diǎn)就是auto ret = countMap.insert(make_pair<str，1>)；有兩種情況，插入成功我用不用管，我不管，也就是第一次出現(xiàn)，那么返回的pair的second是一個true；插入失敗，說明水果已經(jīng)有了，那么insert()是不是同時充當(dāng)了find()的作用，因?yàn)樗褜?yīng)的元素的迭代器也給我了。 if(ret.second == false)那就是插入失敗，已經(jīng)有該水果了，所以ret.first->second++；

map<string, int> countMap;for (auto& str : arr){pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));auto ret = countMap.insert(make_pair(str, 1));if (ret.second == false){ret.first->second++;}}

operator[]

》其實(shí)我們統(tǒng)計也不會用這個方法，這個方法太憋屈了，我們**講這個真正的目的是為了玩“【】”**這個重載運(yùn)算符，而且C++里面的map非常喜歡用“【】”，如果說map的話，我們重點(diǎn)學(xué)習(xí)的就是這個“【】”重載運(yùn)算符。我們統(tǒng)計次數(shù)怎么統(tǒng)計，我先寫好：

map<string, int> countMap;for (auto& str : arr){countMap[str]++;}

此書成功統(tǒng)計出來，沒有毛病，這個“【】”很絕。一句代碼統(tǒng)計完次數(shù)！就用了operator []這么一個重載運(yùn)算符。

》operator[]返回值是一個mapped_type&類型。我們想想，我們什么時候重載過operator[]了？我們在vector、string的時候重載了operator[]，但是這里map支持隨機(jī)訪問嗎？并不支持，目的也不是。
》其實(shí)這里map的operator[]已經(jīng)改變了[]的意義了，它不是隨機(jī)訪問，它的參數(shù)也不是下標(biāo)。它的參數(shù)是key，返回值是value的引用&。
》那么這里怎么做到一句話就統(tǒng)計了此書呢？insert()都沒有了嗎？我們來看看源碼實(shí)現(xiàn)，

這個代碼能把人看崩掉，我們簡化一下代碼，我們先提取出(this->insert(make_pair(K，mapped_type()))).first，這一串其實(shí)是誰呢？實(shí)際上就是調(diào)用了insert()嘛。
》insert的返回值是不是pair<map<>::iterator，bool>類型數(shù)據(jù)呀，即pair<map<>::iterator，bool> ret = insert(make_pair(K，mapped_type()))，然后它取了ret的first數(shù)據(jù)，first是個什么呢，不就是指向節(jié)點(diǎn)的迭代器嘛。
》所以一開始的代碼就可以理解成

pair<map<>::iterator，bool> ret = insert(make_pair(K，mapped_type()))
return (*(ret.first)).second;

》其實(shí)這個也繞了一點(diǎn)，其實(shí)等價于：

pair<map<>::iterator，bool> ret = insert(make_pair(K，mapped_type()))
return (ret.first)->second;

我們在“【】”里面給的是key值，有兩種情況：1.Key在map對象中；2.Key不在map對象中。這里是精華，很多面試中都會考這里。
》第一種，Key在map對象中，我們要進(jìn)行插入，make_pair(k，mapped_type())中的mapped_type()是個啥？我們先來看看mapped_type是誰？是不是T類型，就是Value的類型呀，也就是第二個模版參數(shù)的類型，第一個模版參數(shù)的類型是key的類型，K嘛。那么mapped_type()是不是用Value類型進(jìn)行構(gòu)造的匿名對象呀！
》也就是說，你來了一個Key，我不管你在不在，我先insert(0。假設(shè)第一種情況，Key是存在的，那么插入失敗，那么insert()也就會插入失敗，那么你pair<map<>::iterator，bool> ret = insert(make_pair(K，mapped_type()))中的ret的second數(shù)據(jù)bool類型就是flase！first數(shù)據(jù)就是Key所在節(jié)點(diǎn)的迭代器。然后return (*(ret.first)).second；可能早期沒有支持“->”這個符號，所以我們現(xiàn)在支持，就這樣寫：ret.first->second------>這個是不是就是節(jié)點(diǎn)的Value值呀。并且不要忘了**，我operator[]的返回值，是Value的引用&！引用的作用是：1.減少拷貝；2.支持修改！**
》所以此時operato[]的作用有兩層：1.查找K對應(yīng)的Value；2.修改K對應(yīng)的Value值。
》第一種情況，插入失敗，insert()完全沒有起作用，它反而充當(dāng)?shù)氖遣檎业淖饔?/strong>。它這里的operator[]返回值只用的是insert()返回值的first，即返回節(jié)點(diǎn)的迭代器。插入成功還是失敗無所謂呀，為什么呢？如果Key在map對象中，肯定插入失敗嘛；
》第二種情況，如果Key不在對象中，那么insert()是不是插入成功，operator[]的返回值是不是節(jié)點(diǎn)的迭代器中的Value值的引用&呀，這個值一開始是匿名構(gòu)造的對象，上面有說（如果Value是stirng類型就是空串，如果是int類型就是0，如果是指針類型就是空nullptr）。我返回的Value值的引用，那也就意味著充當(dāng)著 插入 和 修改兩層作用，你可以修改，也可以不修改。
》我們再來分析一下，我們寫的代碼：

countMap[str]++;

auto ret1 = dict.insert(make_pair("left", "左邊"));
auto ret2 = dict.insert(make_pair("left", "剩余"));
dict["operator"] = "重載"; // 插入+修改
dict["left"] = "左邊、剩余"; // 查找 + 修改
dict["erase"];  // 插入
cout << dict["left"] << endl; // 查找

multimap<string，string> dict；
dict.insert(make_pair("left"，“左邊”))；
dict.insert(make_pair("left"，“剩余”))；