1. 關(guān)聯(lián)式容器

STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，這些容器統(tǒng)稱為序列式容器，因?yàn)槠涞讓訛?strong>線性序列的數(shù)據(jù)結(jié)構(gòu)，里面存儲的是元素本身。
那什么是關(guān)聯(lián)式容器？它與序列式容器有什么區(qū)別？
關(guān)聯(lián)式容器也是用來存儲數(shù)據(jù)的，與序列式容器不同的是，其里面存儲的是<key, value>結(jié)構(gòu)的鍵值對。序列式容器中存儲的元素默認(rèn)都是未經(jīng)過排序的，而使用關(guān)聯(lián)式容器存儲的元素，默認(rèn)會根據(jù)各元素的鍵值的大小做升序排序，在數(shù)據(jù)檢索時比序列式容器效率更高。

2. 鍵值對

用來表示具有一一對應(yīng)關(guān)系的一種結(jié)構(gòu)，該結(jié)構(gòu)中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應(yīng)的信息。比如：現(xiàn)在要建立一個英漢互譯的字典，那該字典中必然有英文單詞與其對應(yīng)的中文含義，英文單詞與其 中文含義是一一對應(yīng)的關(guān)系，即通過該應(yīng)該單詞，在詞典中就可以找到與其對應(yīng)的中文含義。
SGI-STL中關(guān)于鍵值對的定義：

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2())//默認(rèn)構(gòu)造{}pair(const T1& a, const T2& b) : first(a), second(b)//拷貝構(gòu)造{}
};

3. 樹形結(jié)構(gòu)的關(guān)聯(lián)式容器

根據(jù)應(yīng)用場景的不同，STL總共實(shí)現(xiàn)了兩種不同結(jié)構(gòu)的管理式容器：樹型結(jié)構(gòu)與哈希結(jié)構(gòu)。樹型結(jié)構(gòu)的關(guān)聯(lián)式容器主要有四種：map、multimap、set、multiset。這四種容器的共同點(diǎn)是：使用平衡搜索樹(即紅黑樹)作為其底層結(jié)果，容器中的元素是一個有序的序列。下面一依次介紹每一個容器。

3.1 set

3.1.1 set的介紹

1. set是按照一定次序存儲元素的容器
2. 在set中，元素的value也標(biāo)識它(value就是key，類型為T)，并且每個value必須是唯一的。set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。
3. 在內(nèi)部，set中的元素總是按照其內(nèi)部比較對象(類型比較)所指示的特定嚴(yán)格弱排序準(zhǔn)則進(jìn)行排序。
4. set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據(jù)順序?qū)ψ蛹M(jìn)行直接迭代。
5. set在底層是用二叉搜索樹(紅黑樹)實(shí)現(xiàn)的。

注意：

1. 與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key, value>，set中只放value，但在底層實(shí)際存放的是由<value, value>構(gòu)成的鍵值對。
2. set中插入元素時，只需要插入value即可，不需要構(gòu)造鍵值對。
3. set中的元素不可以重復(fù)(因此可以使用set進(jìn)行去重)。
4. 使用set的迭代器遍歷set中的元素，可以得到有序序列（排序）
5. set中的元素默認(rèn)按照小于來比較(升序)
6. set中查找某個元素，時間復(fù)雜度為：$lo{g}_{2}n$
7. set中的元素不允許修改
8. set中的底層使用二叉搜索樹(紅黑樹)來實(shí)現(xiàn)。

3.1.2 set的使用

1.set的模板參數(shù)列表

T: set中存放元素的類型，實(shí)際在底層存儲<value, value>的鍵值對。
Compare：set中元素默認(rèn)按照小于來比較（升序）
Alloc：set中元素空間的管理方式，使用STL提供的空間配置器管理

2.set的構(gòu)造

函數(shù)聲明	功能介紹
set (const Compare& comp = Compare(), const Allocator& = Allocator() );	構(gòu)造空的set
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& =Allocator() );	用[first, last)區(qū)間中的元素構(gòu)造set
set ( const set<Key,Compare,Allocator>& x);	set的拷貝構(gòu)造

3.set的迭代器

函數(shù)聲明	功能介紹
iterator begin()	返回set中起始位置元素的迭代器
iterator end()	返回set中最后一個元素后面的迭代器
const_iterator cbegin()const	返回set中起始位置元素const迭代器
const_iterator cend() const	返回set中最后一個元素后面的const迭代器
reverse_iterator rbegin()	返回set第一個元素的反向迭代器，即rend
reverse_iterator rend()	返回set最后一個元素下一個位置的反向迭代器，即rbegin
const_reverse_iterator crbegin() const	返回set第一個元素的反向const迭代器，即crend
const_reverse_iterator crend() const	返回set最后一個元素下一個位置的反向const迭代器，即crbegin

4. set的容量

函數(shù)聲明	功能介紹
bool empty ( ) const	檢測set是否為空，空返回true，否則返回true
size_type size() const	返回set中有效元素的個數(shù)

5.set修改操作

函數(shù)聲明	功能介紹
pair<iterator,bool> insert (const value_type& x )	在set中插入元素x，實(shí)際插入的是<x, x>構(gòu)成的鍵值對，如果插入成功，返回<該元素在set中的位置，true>,如果插入失敗，說明x在set中已經(jīng)存在，返回<x在set中的位置，false>
void erase ( iterator position )	刪除set中position位置上的元素
size_type erase ( const key_type& x )	刪除set中值為x的元素，返回刪除的元素的個數(shù)
void erase ( iterator first,iterator last )	刪除set中[first, last)區(qū)間中的元素
void swap (set<Key,Compare,Allocator>&st );	交換set中的元素
void clear ( )	將set中的元素清空
iterator find ( const key_type& x ) const	找到了，返回set中值為x的元素的位置，沒有找到返回end()
size_type count ( const key_type& x ) const	返回set中值為x的元素的個數(shù),在set中不是1就是0，而在multiset中允許插入重復(fù)值，就不一定是0或1了

其他：

函數(shù)聲明	功能介紹
iterator lower_bound (const value_type& val) const;	返回第一個大于等于val的迭代器
iterator upper_bound (const value_type& val) const;	返回第一個大于val的迭代器

6.set的使用舉例

#include <set>
void TestSet()
{// 用數(shù)組array中的元素構(gòu)造setint array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };set<int> s(array, array + sizeof(array) / sizeof(array[0]));cout << s.size() << endl;// 正向打印set中的元素，從打印結(jié)果中可以看出：set可去重for (auto& e : s)cout << e << " ";cout << endl;// 使用迭代器逆向打印set中的元素for (auto it = s.rbegin(); it != s.rend(); ++it)cout << *it << " ";cout << endl;// set中值為3的元素出現(xiàn)了幾次cout << s.count(3) << endl;
}

運(yùn)行結(jié)果：自動排序+去重

3.2 multiset

3.2.1 multiset的介紹

1. multiset是按照特定順序存儲元素的容器，其中元素是可以重復(fù)的。
2. 在multiset中，元素的value也會識別它(因?yàn)閙ultiset中本身存儲的就是<value, value>組成的鍵值對，因此value本身就是key，key就是value，類型為T). multiset元素的值不能在容器中進(jìn)行修改(因?yàn)樵乜偸莄onst的)，但可以從容器中插入或刪除。
3. 在內(nèi)部，multiset中的元素總是按照其內(nèi)部比較規(guī)則(類型比較)所指示的特定嚴(yán)格弱排序準(zhǔn)則進(jìn)行排序。
4. multiset容器通過key訪問單個元素的速度通常比unordered_multiset容器慢，但當(dāng)使用迭代器遍歷時會得到一個有序序列。
5. multiset底層結(jié)構(gòu)為二叉搜索樹(紅黑樹)。

注意：

1. multiset中再底層中存儲的是<value, value>的鍵值對
2. 需要注意的是由于multiset有允許元素重復(fù)，find函數(shù)找的時候是中序的第一個位置。例如：多個重復(fù)值中序遍歷結(jié)果是3 3 3，使用find函數(shù)會把第一個3的迭代器位置返回。
3. mtltiset的插入接口中只需要插入即可
4. 與set的區(qū)別是，multiset中的元素可以重復(fù)，set是中value是唯一的
5. 使用迭代器對multiset中的元素進(jìn)行遍歷，可以得到有序的序列
6. multiset中的元素不能修改
7. 在multiset中找某個元素，時間復(fù)雜度為$O(lo{g}_{2}N)$
8. multiset的作用：可以對元素進(jìn)行排序

3.2.2 multiset的使用

此處只簡單演示set與multiset的不同，其他接口接口與set相同。

#include <set>//頭文件和set是一樣的
void TestSet()
{int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };// 注意：multiset在底層實(shí)際存儲的是<int, int>的鍵值對multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));for (auto& e : s)cout << e << " ";cout << endl;
}

3.3 map

3.3.1 map的介紹

1. map是關(guān)聯(lián)容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。

2. 在map中，鍵值key通常用于排序和唯一的標(biāo)識元素，而值value中存儲與此鍵值key關(guān)聯(lián)的內(nèi)容。鍵值key和值value的類型可以不同。在map的內(nèi)部，key與value通過成員類型value_type綁定在一起，為其取別名稱為 pair即：typedef pair<const key, T> value_type;。舉個例子：map<string,int> My_Map單拿出來My_Map中的每一個元素都是一個一個的pair<string,int>，區(qū)分不同的pair時就用pair的first也就是string來區(qū)分每一個pair。下圖為pair的成員變量first和second，以及對于value_type的定義。
   
   

3. 在內(nèi)部，map中的元素總是按照鍵值key進(jìn)行比較排序的。

4. map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據(jù)順序?qū)υ剡M(jìn)行直接迭代(即對map中的元素進(jìn)行迭代時，可以得到一個有序的序列)。

5. map支持下標(biāo)訪問符，即在[]中放入key，就可以找到與key對應(yīng)的value。

6. map通常被實(shí)現(xiàn)為二叉搜索樹(更準(zhǔn)確的說：平衡二叉搜索樹(紅黑樹))。

3.3.2 map的使用

1.map的模板參數(shù)說明

key: 鍵值對中key的類型
T： 鍵值對中value的類型
Compare: 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下(內(nèi)置類型元素)該參數(shù)不需要傳遞，如果無法比較時(自定義類型)，需要用戶自己顯式傳遞比較規(guī)則(一般情況下按照函數(shù)指針或者仿函數(shù)來傳遞)
Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標(biāo)準(zhǔn)庫提供的空間配置器。
注意：在使用map時，需要包含頭文件。

2. map的構(gòu)造

函數(shù)聲明	功能介紹
map (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());	構(gòu)造一個空的map
map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());	用[first, last)區(qū)間中的元素構(gòu)造map
map (const map& x);	map的拷貝構(gòu)造

3. map的迭代器

函數(shù)聲明	功能介紹
begin()和end()	begin:首元素的位置，end最后一個元素的下一個位置
cbegin()和cend()	與begin和end意義相同，但cbegin和cend所指向的元素不能修改
rbegin()和rend()	反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作與begin和end操作移動相反
crbegin()和crend()	與rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改

4. map的容量與元素訪問

函數(shù)聲明	功能簡介
bool empty ( ) const	檢測map中的元素是否為空，是返回true，否則返回false
size_type size() const	返回map中有效元素的個數(shù)
mapped_type& operator[] (const key_type& k)	返回去key對應(yīng)的value

5. map中元素的修改

函數(shù)聲明	功能簡介
pair<iterator,bool> insert (const value_type& x )	在map中插入鍵值對x，注意x是一個鍵值對，返回值也是鍵值對：iterator代表新插入元素的位置，bool代表釋放插入成功
void erase ( iterator position )	刪除position位置上的元素
size_type erase ( const key_type& x )	刪除鍵值為x的元素
void erase ( iterator first,iterator last )	刪除[first, last)區(qū)間中的元素
void swap (map<Key,T,Compare,Allocator>&mp )	交換兩個map中的元素
void clear ( )	將map中的元素清空
iterator find ( const key_type& x)	在map中插入key為x的元素，找到返回該元素的位置的迭代器，否則返回end
const_iterator find ( const key_type& x ) const	在map中插入key為x的元素，找到返回該元素的位置的const迭代器，否則返回cend
size_type count ( const key_type& x ) const	返回key為x的鍵值在map中的個數(shù)，注意map中key是唯一的，因此該函數(shù)的返回值要么為0，要么為1，因此也可以用該函數(shù)來檢測一個key是否在map中

operator[]

insert函數(shù)的返回值：

//將上面藍(lán)框的內(nèi)容化簡可得
V& operatort[](const K& k）  
{pair<iterator,bool> ret = insert(make_pair(k，V()));return ret.first->second;
}

operator[]的原理是：
用<key, T()>構(gòu)造一個鍵值對，然后調(diào)用insert()函數(shù)將該鍵值對插入到map中，
如果key已經(jīng)存在，插入失敗，insert函數(shù)返回該key所在位置的迭代器。
如果key不存在，插入成功，insert函數(shù)返回新插入元素所在位置的迭代器，operator[]函數(shù)最后將insert返回值鍵值對中的value返回。

注意：在元素訪問時，有一個與operator[]類似的操作at()(該函數(shù)不常用)函數(shù)，
都是通過key找到與key對應(yīng)的value，然后返回value的引用（返回引用表示可以對value進(jìn)行寫和讀），
不同的是：當(dāng)key不存在時，operator[]調(diào)用 value的默認(rèn)構(gòu)造 與 key的構(gòu)造 二者組成鍵值對然后插入，返回該 默認(rèn)value，而at()函數(shù)直接拋異常。

來咱用一用，請看使用示例代碼：

#include<iostream>
#include<string>
#include <map>
using namespace std;int main()
{///operate[]的不同使用場景map<string, string> dict;dict.insert(pair<string, string>("排序", "sort"));dict.insert(pair<string, string>("左邊", "left"));dict.insert(pair<string, string>("右邊", "right"));dict.insert(make_pair("字符串", "string")); dict["迭代器"] = "iterator"; // 插入+修改dict["insert"]; // 插入  key不在就是插入// 插入失敗，搜索樹只比較keydict.insert(pair<string, string>("左邊", "xxx")); dict["insert"] = "插入"; //修改cout << dict["左邊"] << endl; // 查找  key在就是查找//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//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;}// 統(tǒng)計水果出現(xiàn)的次數(shù)/string arr[] = { "蘋果", "西瓜", "香蕉", "草莓", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };map<string, int> countMap;//for (auto& e : arr)//{//	//map<string, int>::iterator it = countMap//	auto it = countMap.find(e);//	if (it == countMap.end())//	{//		countMap.insert(make_pair(e, 1));//	}//	else//	{//		it->second++;//	}//}for (auto& e : arr){countMap[e]++;}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}return 0;
}

向map中插入元素的方式（insert、operator[]、erase的使用舉例）：

#include <string>
#include <map>
void TestMap()
{map<string, string> m;// 將鍵值對<"peach","桃子">插入map中，用pair直接來構(gòu)造鍵值對m.insert(pair<string, string>("peach", "桃子"));// 將鍵值對<"peach","桃子">插入map中，用make_pair函數(shù)來構(gòu)造鍵值對m.insert(make_pair("banan", "香蕉"));// 借用operator[]向map中插入元素// 將<"apple", "">插入map中，插入成功，返回value的引用，將“蘋果”賦值給該引用結(jié)果，m["apple"] = "蘋果";// key不存在時拋異常//m.at("waterme") = "水蜜桃";cout << m.size() << endl;// 用迭代器去遍歷map中的元素，可以得到一個按照key排序的序列for (auto& e : m)cout << e.first << "--->" << e.second << endl;cout << endl;// map中的鍵值對key一定是唯一的，如果key存在將插入失敗auto ret = m.insert(make_pair("peach", "桃色"));if (ret.second)cout << "<peach, 桃色>不在map中, 已經(jīng)插入" << endl;elsecout << "鍵值為peach的元素已經(jīng)存在：" << ret.first->first << "--->"<< ret.first->second << " 插入失敗" << endl;// 刪除key為"apple"的元素m.erase("apple");if (1 == m.count("apple"))cout << "apple還在" << endl;elsecout << "apple被吃了" << endl;}

【總結(jié)】

1. map中的的元素是鍵值對
2. map中的key是唯一的，并且不能修改
3. 默認(rèn)按照小于的方式對key進(jìn)行比較
4. map中的元素如果用迭代器去遍歷，可以得到一個有序的序列
5. map的底層為平衡搜索樹(紅黑樹)，查找效率比較高$O(lo{g}_{2}N)$
6. 支持[]操作符，operator[]中實(shí)際進(jìn)行 插入 查找 修改。

3.4 multimap

3.4.1 multimap的介紹

1. Multimaps是關(guān)聯(lián)式容器，它按照特定的順序，存儲由key和value映射成的鍵值對<key,value>，其中多個鍵值對之間的key是可以重復(fù)的。
2. 在multimap中，通常按照key排序和唯一的標(biāo)識元素，而映射的value存儲與key關(guān)聯(lián)的內(nèi)容。key和value的類型可能不同，通過multimap內(nèi)部的成員類型value_type組合在一起，value_type是組合key和value的鍵值對:typedef pair<const Key, T> value_type;
3. 在內(nèi)部，multimap中的元素總是通過其內(nèi)部比較對象，按照指定的特定嚴(yán)格弱排序標(biāo)準(zhǔn)對key進(jìn)行排序的。
4. multimap通過key訪問單個元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍歷multimap中的元素可以得到關(guān)于key有序的序列。
5. multimap在底層用二叉搜索樹(紅黑樹)來實(shí)現(xiàn)。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重復(fù)的。

3.4.2 multimap的使用

multimap中的接口可以參考map，功能都是類似的。
注意：

1. multimap中的key是可以重復(fù)的。
2. multimap中的元素默認(rèn)將key按照小于來比較
3. multimap中沒有重載operator[]操作，因?yàn)檫@里是一對多的結(jié)構(gòu)。
4. 使用時與map包含的頭文件相同。

3.5 map和set在OJ中的使用

1、前K個高頻單詞
題目鏈接
思路：定義一個 map<string,int>類型的map，將vector<string>& words中的元素利用operator[]插入到map中，此時已經(jīng)自動將所有字符串按字典序排序 并在int中記錄出現(xiàn)次數(shù)。
然后轉(zhuǎn)移到 vector<pair<string,int>> v方便下一步對于出現(xiàn)次數(shù)的排序，排序時要對int進(jìn)行排序，但是題中又說 如果不同的單詞有相同出現(xiàn)頻率， 按字典順序排序。
面臨的問題有兩個
1、pair默認(rèn)的比較大小方式并不適合此題，需要自己寫仿函數(shù)
2、sort排序是不穩(wěn)定的排序，對于出現(xiàn)次數(shù)相同的兩個單詞，可能會把它們的字典序也打亂，所以要使用穩(wěn)定的排序stable_sort。

代碼：

class Solution {
public:class compare{public://需要自己按照題目要求定義一個仿函數(shù)bool operator()(const pair<string,int>& x, const pair<string,int>& y) const{return x.second > y.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> CountMap;for(const auto& one_words:words){CountMap[one_words]++;//關(guān)鍵的第一步}//然后轉(zhuǎn)移到vector中vector<pair<string,int>> v;for(auto sp:CountMap){v.push_back(sp);}//使用穩(wěn)定排序，對pair的second也就是int進(jìn)行排序——關(guān)鍵的第二步stable_sort(v.begin(),v.end(),compare());vector<string> ret;for(int i=0;i<k;i++){ret.push_back(v[i].first);}return ret;}
};

2、兩個數(shù)組的交集
題目鏈接
思路：創(chuàng)建兩個set< int >類型的對象s1和s2分別來“裝”num1和num2，以此達(dá)到對num1和num2實(shí)現(xiàn)排序+去重的目的，然后就是遍歷s1和s2。

• 相等就是交集值，插入到要返回的vector< int >中，同時讓s1和s2的迭代器++
• 不相等，對應(yīng)的值小的 迭代器 ++，有一個set到結(jié)尾end了，那么就結(jié)束統(tǒng)計了。

代碼：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> s1,s2;//自動排序+去重for(auto n1:nums1){s1.insert(n1);}for(auto n2:nums2){s2.insert(n2);}vector<int> ret;auto it1=s1.begin();auto it2=s2.begin();while(it1!=s1.end()&&it2!=s2.end())//遍歷s1和s2{if(*it1==*it2){ret.push_back(*it1);it1++;it2++;}else if(*it1>*it2){it2++;}else{it1++;}}return ret;}
};