關聯式容器

我們已經知道STL中的部分容器，比如：vector、list、deque、
list等，這些容器統稱為序列式容器，因為其底層為線性序列的數據結構，里面存儲的是元素本身。那什么是關聯式容器？它與序列式容器有什么區別？
關聯式容器也是用來存儲數據的，與序列式容器不同的是，其里面存儲的是<key, value>結構的鍵值對，在數據檢索時比序列式容器效率更高。

鍵值對

用來表示具有一一對應關系的一種結構，該結構中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應的信息。比如：現在要建立一個英漢互譯的字典，那該字典中必然有英文單詞與其對應的中文含義，而且，英文單詞與其中文含義是一一對應的關系，即通過該應該單詞，在詞典中就可以找到與其對應的中文含義。

SGI-STL中關于鍵值對(pair)的定義：

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a), second(b){}
};

樹形結構的關聯式容器

根據應用場景的不同，STL總共實現了兩種不同結構的管理式容器：樹型結構與哈希結構。樹型結構的關聯式容器主要有四種：map、set、multimap、multiset。這四種容器的共同點是：使用平衡搜索樹(即紅黑樹)作為其底層結果，容器中的元素是一個有序的序列。

set的使用

1. set的模板參數列表

2. set的構造

3. set的迭代器

4. set的容量

5. set修改操作

6. set的使用舉例

#include <set>
void TestSet()
{// 用數組array中的元素構造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));cout << s.size() << endl;// 正向打印set中的元素，從打印結果中可以看出：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的元素出現了幾次cout << s.count(3) << endl;
}

map

1. map的簡介

mapd的介紹文檔
閱讀map容器中的函數時三個重要的typedef的變量：

翻譯：

1. map是關聯容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。
2. 在map中，鍵值key通常用于排序和惟一地標識元素，而值value中存儲與此鍵值key關聯的內容。鍵值key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，為其取別名稱為pair::typedef pair<const key, T> value_type;
3. 在內部，map中的元素總是按照鍵值key進行比較排序的。
4. map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據順序對元素進行直接迭代(即對map中的元素進行迭代時，可以得到一個有序的序列)。
5. map支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。
6. map通常被實現為二叉搜索樹(更準確的說：平衡二叉搜索樹(紅黑樹))。

2. map的模板參數說明

3. map的構造

4. map的迭代器

5. map的容量與元素訪問

問題：當key不在map中時，通過operator獲取對應value時會發生什么問題？

注意：在元素訪問時，有一個與operator[]類似的操作at()(該函數不常用)函數，都是通過key找到與key對應的value然后返回其引用，不同的是：當key不存在時，operator[]用默認value與key構造鍵值對然后插入，返回該默認value，at()函數直接拋異常。

6. map的元素修改

---

---

返回值：

#include <iostream>
using namespace std;
#include <string>
#include <map>
void TestMap()
{map<string, string> m;// 向map中插入元素的方式：// 將鍵值對<"peach","桃子">插入map中，用pair直接來構造鍵值對m.insert(pair<string, string>("peach", "桃子"));// 將鍵值對<"peach","桃子">插入map中，用make_pair函數來構造鍵值對m.insert(make_pair("banan", "香蕉"));// 借用operator[]向map中插入元素/*operator[]的原理是：用<key, T()>構造一個鍵值對，然后調用insert()函數將該鍵值對插入到map中如果key已經存在，插入失敗，insert函數返回該key所在位置的迭代器如果key不存在，插入成功，insert函數返回新插入元素所在位置的迭代器operator[]函數最后將insert返回值鍵值對中的value返回*/// 將<"apple", "">插入map中，插入成功，返回value的引用，將“蘋果”賦值給該引// 用結果，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中, 已經插入" << endl;elsecout << "鍵值為peach的元素已經存在：" << ret.first->first << "--->"<< ret.first->second << " 插入失敗" << endl;// 刪除key為"apple"的元素m.erase("apple");if (1 == m.count("apple"))cout << "apple還在" << endl;elsecout << "apple被吃了" << endl;
}

---

【map總結】

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

multimap和multiset的使用

multimap和multiset的使用

（本章完）