說起map和set，想必我們都學過紅黑樹了吧，map和set就是紅黑樹的一個應用領域。它的底層就是由紅黑樹來實現的。下面簡單說一下map和set的使用吧。

首先，有一個栗子是這樣的，讓我們統計出每種水果出現的次數。

我們會想到怎么解決的。關于map，我們知道，當你插入同樣的key值時，它就不會將要插入的key值插入到map中。但是，我們還知道，map是有倆個參數的，一個是插入的key值，另一個value可以用來統計key值出現的次數。

關于統計水果次數的問題，我們主要有以下幾種方法：

    map<string,int> countMap;string strs[] = {"蘋果","香蕉","橘子","蘋果","蘋果","香蕉"};//1.從頭到尾遍歷看是否有數組中的值，沒有則插入，有則使second++for(int i = 0; i < sizeof(strs)/sizeof(strs[0]); i++){map<string,int>::iterator it = countMap.find(strs[i]);if(it != countMap.end()){it->second++;}else{countMap.insert(make_pair(strs[i],1));}}map<string,int>::iterator it1 = countMap.begin();while(it1 != countMap.end()){cout<<it1->first<<":"<<it1->second<<endl;++it1;}

//2.檢測插入的返回值pair<map<string,int>::iterator,bool>的second是否為false來確定pair<map<string,int>::iterator,bool> ret;for(int i = 0; i < sizeof(strs)/sizeof(strs[0]);i++){ret = countMap.insert(make_pair(strs[i],1));if(ret.second == false)ret.first->second++;}map<string,int>::iterator it1 = countMap.begin();while(it1 != countMap.end()){cout<<it1->first<<":"<<it1->second<<endl;++it1;}

//3.直接使用map重載的[]for(int i = 0; i < sizeof(strs)/sizeof(strs[0]);i++){countMap[strs[i]]++;}map<string,int>::iterator it1 = countMap.begin();while(it1 != countMap.end()){cout<<it1->first<<":"<<it1->second<<endl;++it1;}

運行結果：

這里需要注意的幾點是：

1.首先使用插入的時候，是需要插入一個pair結構體，因為map底層的value是一個pair結構體，里邊成員又有first和second；因此需要使用make_pair來構造insert的參數。
2.在使用第三種方法的時候，我們使用到map重載的operator[]，說一下operator[]的函數:
(*((this->insert(make_pair(x,T()))).first)).second
分解一下上邊的operator[]的式子：
this->insert(make_pair(x,T()))：返回值為pair<iterator,bool>結構體
((this->insert(make_pair(x,T()))).first)：表示pair結構體中的first，即指向一個pair結構體的迭代器，此pair結構體中有key和value，也即所謂的first和second
(*((this->insert(make_pair(x,T()))).first)).second：表示取迭代器中指向的pair的second

說到map，我們還有一個multimap，是用來插入冗余的值，比如有相同的key值的時候，對于map而言，它就不會將其插入，而對于multimap而言就會插入。典型的例子為字典，我們英譯漢的時候，同一個英語單詞代表著不同的意思，這時multimap就會將每一個key值對應的不同的value值都會插入，并且以排好序的方式顯示。

1.比如map來顯示字典的時候：

typedef map<string,string> Dict;typedef map<string,string>::iterator DictIt;Dict dict;dict.insert(make_pair("left","左邊"));dict.insert(make_pair("right","右邊"));dict.insert(make_pair("left","剩余"));DictIt it = dict.begin();while (it != dict.end()){cout<<it->first<<":"<<it->second<<endl;++it;}

結果為：

2.用multimap來實現字典的時候：

typedef multimap<string,string> Dict;typedef multimap<string,string>::iterator DictIt;Dict dict;dict.insert(make_pair("left","左邊"));dict.insert(make_pair("right","右邊"));dict.insert(make_pair("left","剩余"));DictIt it = dict.begin();while (it != dict.end()){cout<<it->first<<":"<<it->second<<endl;++it;}

運行結果：

綜上所述，
（1）map和multimap可以通過key來找value，也可通過key排序
（2）當我們查找某個key值的時候，發現有多個相同的key值，此時不知道it該指向哪個pair結構體，這里要說明的是，它將返回中序遍歷的第一個key值

驗證一下：

typedef multimap<string,string> Dict;typedef multimap<string,string>::iterator DictIt;Dict dict;dict.insert(make_pair("left","左邊"));dict.insert(make_pair("right","右邊"));dict.insert(make_pair("left","剩余"));DictIt it = dict.begin();it = dict.find("left");dict.erase(it);it = dict.begin();while (it != dict.end()){cout<<it->first<<":"<<it->second<<endl;++it;}

在這里，我們找到一個key值為left的pair，此時刪除它后再打印一下發現得出的是比它大的value值。

說完map和multimap后，與之對應的還有set和multiset。set和multiset是用來判斷這個值存在或者不存在。其次也可以用來排序。還有一個特點是過濾（去重）。

1.檢測其存在或者不存在

void TestSet()
{typedef set<string> MySet;typedef set<string>::iterator MySetIt;MySet myset;string strs[] = {"蘋果","香蕉","橘子","西瓜","草莓","櫻桃"};for(int i = 0; i < sizeof(strs)/sizeof(strs[0]); i++){myset.insert(strs[i]);}MySetIt it = myset.begin();if(it == myset.find("哈密瓜"))cout<<"哈密瓜存在"<<endl;elsecout<<"哈密瓜不存在"<<endl;cout<<"存在的其他水果為："<<endl;it = myset.begin();while(it != myset.end()){cout<<*it<<endl;++it;}
}

運行結果：

2.排序和去重

typedef set<int> MySet;typedef set<int>::iterator MySetIt;MySet myset;for(int i = 10; i > 0; i--)myset.insert(i);myset.insert(5);MySetIt it = myset.begin();while(it != myset.end()){cout<<*it<<endl;++it;}

運行結果：

對于過濾來說，就是如果有相同的key值，它就會去掉相同的key，只插入一個到set中。

這里multiset的意義和multimap差不多，也是處理冗余的數據。使用方法類似。

對于map和set的底層是怎么實現的呢。它是通過寫的一個紅黑樹。主要的區別是

里邊的value_type的意義，對于map來說，value_type指的是一個pair的結構體，結構體成員為key和value，而對于set來說，value_type指的是key值。
在紅黑樹中，用了枚舉來表示顏色。而在源碼的紅黑樹中使用了bool值來代替紅黑倆種顏色
我們還知道，map和multimap，set和multiset也有區別，底層是怎么用紅黑樹的呢。它是插入的時候分別對紅黑樹的插入分為唯一插入(insert_unique)和相等插入(insert_equal)（相等插入就是對冗余數據的考慮）。
set的插入：

map中value_type: typedef pair<const Key, T> value_type;
set中value_type: typedef Key value_type;

set的插入：

  typedef  pair<iterator, bool> pair_iterator_bool; pair<iterator,bool> insert(const value_type& x) { pair<typename rep_type::iterator, bool> p = t.insert_unique(x); return pair<iterator, bool>(p.first, p.second);}

map的插入：

pair<iterator,bool> insert(const value_type& x) 
{ return t.insert_unique(x); }

multimap的插入：

  iterator insert(const value_type& x) { return t.insert_equal(x); }

multiset的插入：

  iterator insert(const value_type& x) { return t.insert_equal(x);}

還可以進行相關的區間的插入，刪除，某個位置的插入刪除等操作。

小姿勢：

lower_bound : 用來找到比key值大的數
upper_bound : 用來找到比key值大的數