引言：
上次我們學習了第一個高階數據結構—二叉搜索樹，趁熱打鐵，今天我們就再來學習兩個數據結構—map和set。
一：序列式容器和關聯式容器
前面我們已經接觸過STL中的部分容器如：string、vector、list、deque、array、forward_list等，這些容器統稱為序列式容器，因為邏輯結構為線性序列的數據結構，兩個位置存儲的值之間一般沒有緊密的關聯關系，比如交換一下，他依舊是序列式容器。順序容器中的元素是按他們在容器中的存儲位置來順序保存和訪問的。
關聯式容器也是用來存儲數據的，與序列式容器不同的是，關聯式容器邏輯結構通常是非線性結構，兩個位置有緊密的關聯關系，交換一下，他的存儲結構就被破壞了。順序容器中的元素是按關鍵字來保存和訪問的。關聯式容器有map/set系列和unordered_map/unordered_set系列。
本章節我們要學習的map和set底層是紅黑樹，紅黑樹是一顆平衡二叉搜索樹。set是key搜索場景的結構，map是key/value搜索場景的結構。
二：set系列的使用
1. set和multiset 的參考文檔：
set / multiset的參考文檔：
2. set類的介紹：
set的聲明如下，T就是set底層關鍵字的類型
set默認要求T?持小于比較，如果不支持或者想按自己的需求走可以自行實現仿函數傳給第二個模版參數。
2.·set底層存儲數據的內存是從空間配置器申請的，如果需要可以自己實現內存池，傳給第三個參數。- 一般情況下，我們都不需要傳后兩個模版參數。
set底層是用紅黑樹實現，增刪查效率是O(logN)，迭代器遍歷是走的搜索樹的中序，所以是有序的。- 前面部分我們已經學習了
vector/list等容器的使用，STL容器接口設計，高度相似，所以這里我們就不再一個接口一個接口的介紹，只是挑比較重要的接口進行介紹。
template < class T,
class Compare = less<T>,
class Alloc = allocator<T> > class set;
3. set的構造和迭代器
（1）構造函數：
介紹文檔：
set的構造我們關注以下幾個接口即可。
set支持正向和反向迭代遍歷，遍歷默認按升序順序，因為底層是二叉搜索樹，迭代器遍歷走的中序，支持迭代器就意味著支持范圍for，set的iterator和const_iterator都不支持迭代器修改數據，修改關鍵字數據，破壞了底層搜索樹的結構。
代碼演示：
(1) 無參默認構造
explicit set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
(2) 迭代器區間構造
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
(3) 拷貝構造
set (const set& x);
(5) initializer 列表構造
set (initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
(2) 迭代器：
begin():返回指向第一個數據的迭代器。
end():返回最后一個數據下一個位置的迭代器。
cbegin():返回最后一個元素的迭代器。
cend():返回第一個數據的前一個位置的迭代器。
set的迭代器是一個雙向迭代器
iterator -> a bidirectional iterator to const value_type
- 正向迭代器
iterator begin();
iterator end(); - 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
4. set的增刪查：
（1）插入：
insert函數
代碼演示：
（2）查找：
- find(): 查找val，返回val所在的迭代器，沒有找到返回end()。
- count():查找val，返回Val的個數。
代碼演示：
（3）刪除：
- iterator erase (const_iterator position): 刪除一個迭代器位置的值。
- size_type erase (const value_type& val):刪除val，不存在返回0，存在返回1。
- iterator erase (const_iterator first, const_iterator last):刪除一段迭代器區間的值。
代碼演示：
（4） lower_bound 和 upper_bound
- lower_bound:返回大于等val位置的迭代器。
- upper_bound:返回大于val位置的迭代器。
注：因此借助這兩個接口就可以得到一段左閉右開的區間。
代碼演示：
5. insert 和迭代器遍歷使用樣例：
注：這里的范圍for我們寫成了引用的形式，是為了提高效率。
6. find和erase的使用樣例：
注：這是我們借助count間接實現的查找。
算法庫中的find和set中的find對比：
7. multiset和set的差異
multiset和set的使用基本完全類似，主要區別點在于multiset支持值冗余，那么
insert/find/count/erase都圍繞著支持值冗余有所差異，具體參看下面的樣例代碼理解:
8. 牛刀小試：
（1）題目描述：
代碼解決：
方法一-暴力匹配：
先將兩個數組通過set來去重，之后遍歷其中一個來借助count來判斷是否有交集。
方法二-雙指針：
該解法的思路是在去重＋升序排序后的基礎上來遍歷兩個容器
定義兩個指針p1，p2分別遍歷兩個set
- 小的那個
++。 - 相等的話就存下來，
p1++，p2++。 - 當其中一個容器遍歷完之后，就結束、
為什么這樣是對的呢？
因為如果其中一個小的話，由于數據是升序的，因此當前必不可能為交集，若存在交集的話只可能在它之后，因此往后走。
題目傳送門：349. 兩個數組的交集
三： map系列的使用
1. map 和multimap的介紹文檔：
map 和multimap的介紹文檔:
2. map類的介紹：
map的聲明如下，Key就是map底層關鍵字的類型，T是map底層value的類型，map默認要求Key支持小于比較，如果不支持或者需要的話可以自行實現仿函數傳給第二個模版參數，map底層存儲數據的內存是從空間配置器申請的。一般情況下，我們都不需要傳后兩個模版參數。map底層是用紅黑樹實現，增刪查改效率是，迭代器遍歷是走的中序，所以是按key有序順序遍歷的。O(logN） ，迭代器遍歷是走的中序，所以是按key有序順序遍歷的。
template < class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key,T> > > class map;
3. pair類型介紹：
map底層的紅黑樹節點中的數據，使用pair<Key,T>存儲鍵值對數據。
pair:
typedef pair<const Key, T> value_type;
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)
{}
template<class U, class V>
pair (const pair<U,V>& pr): first(pr.first), second(pr.second)
{}
};
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}
上面是pair的底層結構，實質上就是一個類模版的結構體。先這么理解即可。
思考：為什么map里面要用pair呢？
這是因為map里面是存儲兩個數據，如果你單獨分開存兩個數據的話，是沒辦法解引用的，因為解引用只能拿到一個數據，用pair的話，解引用會拿到pair類型的數據，之后可以通過pair類型的性質來拿到兩個數據。
4. map的構造和迭代器：
(1) 構造函數：
map的構造函數介紹文檔：
map的構造我們關注以下幾個接口即可。
map的支持正向和反向迭代遍歷，遍歷默認按key的升序順序，因為底層是二叉搜索樹，迭代器遍歷走的中序；支持迭代器就意味著支持范圍for，map支持修改value數據，不支持修改key數據，修改關鍵字數據，破壞了底層搜索樹的結構。
(1) 無參默認構造
explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
(2) 迭代器區間構造
template <class InputIterator>
map (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
(3) 拷貝構造
map (const map& x);
(4) initializer 列表構造
map (initializer_list<value_type> il,
（2）迭代器：
- begin():返回指向第一個數據的迭代器。
- end():返回最后一個數據下一個位置的迭代器。
- cbegin():返回最后一個元素的迭代器。
- cend():返回第一個數據的前一個位置的迭代器。
map的迭代器也是?個雙向迭代器
iterator -> a bidirectional iterator to const value_type
- 正向迭代器
iterator begin();
iterator end(); - 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
5. map 的增刪查
（1）插入：
insert介紹文檔：
代碼演示：
（2）查找：
- find():查找k，返回k所在的迭代器，沒有找到返回end()。
- count():查找k，返回k的個數。
代碼演示：
（3） 刪除：
- iterator erase (const_iterator position):刪除?個迭代器位置的值。
- size_type erase (const key_type& k):刪除k，k存在返回0，存在返回1。
- iterator erase (const_iterator first, const_iterator last:刪除一段迭代器區間的值。
（4） lower_bound 和 upper_bound
- lower_bound:返回大于等k位置的迭代器。
- upper_bound:返回大于k位置的迭代器。
代碼演示：
注：這里默認是按照第一個關鍵字來比較的。
6. map的數據修改
前面提到map支持修改mapped_type數據，不支持持修改key數據，修改關鍵字數據，破壞了底層搜索樹的結構。
map第一個支持修改的方式是通過迭代器，迭代器遍歷時或者find返回key所在的iterator修改，map還有一個非常重要的修改接口operator[]，但是operator[]不僅僅支持修改，還支持插入數據和查找數據，所以他是一個多功能復合接口
需要注意從內部實現角度，map這里把我們傳統說的value值，給的是T類型
typedef為mapped_type。而value_type是紅黑樹結點中存儲的pair鍵值對值。日常使用我們還是習慣將這里的T映射值叫做value。
7.map的迭代器和[]功能樣例：
其實這里的代碼還可以這樣寫：
這樣寫的話，對于已經存在的數據的修改大家都沒問題，但是一些同學可能會疑惑數據第一次出現的時候是怎么統計的呢？
其實在數據第一次出現的時候，會先將這個數據插入，這時候第二個參數就是一個默認值0，之后在進行修改。
operator[] 底層解釋：
要搞清楚operator[]的底層就需要先從insert入手。
可以看到insert的第一個實現形式的返回值是pair類型，由迭代器和bool值組成。
我們再來看第一種形式的返回值的解讀：
這里說的是當該數據是第一次插入的話，就會返回指向這個新插入數據的迭代器，否則就會返回map中指向該數據的迭代器，第二個bool值，如果數據是第一次插入的新數據就會返回true，否則就是返回false。
因此operator[]其實大概就是這樣實現的：
V& operator[](const K& key)
{
pair<iteraotr,bool> ret = insert(key);
return ret.first->second;
}
8. multimap和map的差異
multimap和map的使用基本完全類似，主要區別點在于multimap支持關鍵值key冗余，那么insert/find/count/erase都圍繞著支持關鍵值key冗余有所差異，這里跟set和multiset完全?樣，比如find時，有多個key，返回中序第一個。其次就是multimap不支持[]，因為支持key冗余，[]就只能支持插入了，不能支持修改。
9. 牛刀小試：
（1）題目描述：
（2）思路分析：
首先從題目就能知道這是一個經典的TopK問題，但是與之前不同的是這個是雙元素的，因此我們就得用pair來存儲，所以我們的思路就是先用map來統計各單詞的出現次數，再創建小根堆來維護前k個出現次數最多的單詞，之后用vector來存儲結果，但由于我們創建的是小根堆，因此在返回結果的時候還需要進行逆置。
（3）代碼實現：
（4）題目傳送門：
692. 前K個高頻單詞
-工廠模式)
