一、前言
1.1 關聯式容器
關聯式容器也是用來存儲數據的，與序列式容器不同的是，其里面存儲的是<key,value>結構的鍵值對，在數據檢索時比序列式容器效率更高。
1.2 鍵值對
用來表示具有一一對應關系的一種結構，該結構中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應的信息。
二、set
2.1 介紹
1、set是按照一定次序存儲元素的容器
2、在set中，元素的value也標識它（value就是key，類型為T），并且每個value必須是唯一的。set中的元素不能再容器中修改（元素總是const），但是可以從容器中插入或刪除它們
3、在內部，set中的元素總是按照其內部比較對象（類型比較）所指示的特定嚴格弱排序準則進行排序
4、set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據順序對子集進行直接迭代
5、set在底層是用二叉搜索樹實現的
【注意】
- 與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key,calue>，set中只放value，但在底層實際存放的是有<value,value>構成的鍵值對。
- set中插入元素時，只需要插入value即可，不需要構建鍵值對。
- set中的元素不可以重復（因此可以使用set進行去重）。
- 使用set的迭代器遍歷set中的元素，可以得到有序序列。
- set中的元素默認按照小于來比較。
- set中查找某個元素，時間復雜度為O(logN)。
- set中的元素不允許修改。
- set中的底層使用二叉搜索樹來實現。
2.2 使用
2.3 實現
void Test_set()
{set<int> s;s.insert(5);s.insert(2);s.insert(4);s.insert(6);s.insert(1);s.insert(3);s.insert(2);s.insert(8);s.insert(4);// 正向打印set中的元素，從打印結果可以看出set可以去重for (auto e : s){cout << e << " ";}cout << endl;auto ret1 = s.insert(2);cout << ret1.second << endl;pair<set<int>::iterator, bool> ret2 = s.insert(2);cout << ret2.second << endl;if (s.count(6)){cout << "6在" << endl;}else{cout << "6不在" << endl;}if (s.count(10)){cout << "10在" << endl;}else{cout << "10不在" << endl;}s.erase(3); // 刪除存在的s.erase(10); // 刪除不存在的for (auto e : s){cout << e << " ";}cout << endl;
}三、map
3.1 介紹
- map是關聯容器，它按照特定的次序（按照key來比較）存儲由鍵值key和值value組合而成的元素。
- 在map中鍵值key通常用于排序和唯一的標示元素，而值value中存儲與此鍵值key關聯的內容。鍵值key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，為其取別名為pair：typedef pair<const key,T>value_type;
- 在內部，map中的元素總是按照鍵值key進行比較排序的。
- map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據順序對元素進行直接迭代（即對map中的元素進行迭代時，可以得到一個有序的序列）。
- map支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。
- map通常被實現為二叉搜索樹，更準確的說是平衡二叉樹。
3.2 使用
3.2.1 模板參數說明
- key: 鍵值對中key的類型
- T： 鍵值對中value的類型
- Compare : 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比
較，一般情況下(內置類型元素)該參數不需要傳遞，如果無法比較時(自定義類型)，需要用戶
自己顯式傳遞比較規則(一般情況下按照函數指針或者仿函數來傳遞) - Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標準庫提供的
空間配置器 - 注意：在使用map時，需要包含頭文件。
3.2.2 迭代器
3.2.3 修改
3.3 實現
void Test_map()
{map<string, string> m;// 向map中插入元素的方式：// 1.將鍵值對<"peach","桃子">插入map中，用pair直接構造鍵值對m.insert(pair<string, string>("peach", "桃子"));// 2.將鍵值對<"banana","香蕉">插入map中，用make_pair函數來構造鍵值對m.insert(make_pair("banana", "香蕉"));// 3.用operator[]向map中插入元素m["apple"] = "蘋果";/*operator[]的原理是：用<key, T()>構造一個鍵值對，然后調用insert()函數將該鍵值對插入到map中如果key已經存在，插入失敗，insert函數返回該key所在位置的迭代器如果key不存在，插入成功，insert函數返回新插入元素所在位置的迭代器operator[]函數最后將insert返回值鍵值對中的value返回*///m.at("waterme") = "水蜜桃"; // key不存在時拋異常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中, 已經插入" << endl;}else{cout << "鍵值為peach的元素已經存在：" << ret.first->first << "--->"<< ret.first->second << " 插入失敗" << endl;}// 刪除key為"apple"的元素m.erase("apple");if (1 == m.count("apple")){cout << "apple還在" << endl;}else{cout << "apple被吃了" << endl;}
}四、muitiset
1. multiset是按照特定順序存儲元素的容器，其中元素是可以重復的。
2. 在multiset中，元素的value也會識別它(因為multiset中本身存儲的就是<value, value>組成的鍵值對，因此value本身就是key，key就是value，類型為T).multiset元素的值不能在容器中進行修改(因為元素總是const的)，但可以從容器中插入或刪除。
3. 在內部，multiset中的元素總是按照其內部比較規則(類型比較)所指示的特定嚴格弱排序準則進行排序。
4. multiset容器通過key訪問單個元素的速度通常比unordered_multiset容器慢，但當使用迭代器遍歷時會得到一個有序序列。
5. multiset底層結構為二叉搜索樹(紅黑樹)。
【注意】
- multiset 中再底層中存儲的是 <value, value> 的鍵值對
- multiset的插入接口中只需要插入即可
- 與set的區別是，multiset中的元素可以重復，set中的value是唯一的
- 使用迭代器對multiset中的元素進行遍歷，可以得到有序的序列
- multiset中的元素不能修改
- 在multiset中找某個元素，時間復雜度為O(logN)
- multiset的作用：可以對元素進行排序
五、multimap
1. Multimaps是關聯式容器，它按照特定的順序，存儲由key和value映射成的鍵值對<key,value>，其中多個鍵值對之間的key是可以重復的。
2. 在multimap中，通常按照key排序和惟一地標識元素，而映射的value存儲與key關聯的內容。key和value的類型可能不同，通過multimap內部的成員類型value_type組合在一起，value_type是組合key和value的鍵值對 :typedef pair<const Key, T> value_type;
3. 在內部，multimap中的元素總是通過其內部比較對象，按照指定的特定嚴格弱排序標準對key進行排序的。
4. multimap通過key訪問單個元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍歷multimap中的元素可以得到關于key有序的序列。
5. multimap在底層用二叉搜索樹(紅黑樹)來實現。
注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重復的。
