?
目錄
1.序列式、關聯式容器
2.鍵值對
3.set
3.1set的簡介
3.2set的常用函數
4.multiset
5.map
5.1map的簡介
5.2map的常用函數
6.multimap
7.練習題
?
1.序列式、關聯式容器
vector、deque、list、forward_list、array等是C++STL中的序列式容器
其核心特性是?元素按插入順序存儲，支持高效的順序訪問或隨機訪問
set、map、multiset、multimap等是C++STL中的關聯式容器
其核心特性是?元素通過鍵（key）進行排序和快速查找，而不是像序列式容器那樣按插入順序存儲
2.鍵值對
鍵值對是一種數據結構，由唯一的鍵 Key?和對應的值 Value?組成
鍵 Key ：唯一標識符，用于快速定位數據且必須是不可變類型(如字符串、數字、元組等)值 Value? ：存儲的實際數據，可以是任意類型(字符串、數字、列表、字典等)
映射關系：一個鍵對應一個值，形成 key: value 的結構
鍵值對主要通過?標準模板庫（STL）?中的?
std::pair?和關聯容器（如?std::map、std::unordered_map）實現，下面是STL中的定義
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){}};容器更詳細的使用請參考cplusplus.com - The C++ Resources Network
3.set
3.1set的簡介
set容器實際上就是二叉搜索樹應用中說的 K模型
T: set中存放元素的類型(實際在底層存儲的鍵值對)
Compare(仿函數)：set中元素默認按照小于來比較
Alloc：set中元素空間的管理方式，使用STL提供的空間配置器管理(后續講解)
3.2set的常用函數
set自帶默認構造、迭代器區間構造、拷貝構造等成員函數
(1)insert
set支持單個元素插入、在特定位置后插入以及迭代器區間范圍內元素的插入
重點講講單個元素插入的返回值
插入元素不在set中，返回pair<插入元素在set中的迭代器，true>
插入元素在set中，返回pair<插入元素在set中的迭代器，false>
從上面我們可以得出結論
set中的每個元素只能出現一次(重復插入會被忽略)
(2)
set 是基于紅黑樹（一種平衡二叉搜索樹）實現的，遍歷方式是中序遍歷且由于元素默認是按小于比較的，迭代器打印序列就是升序序列
插入元素Key不可修改
(3)find
//查找高度次
s.find(5);
//暴力查找，最多N次
find(s.begin(), s.end(), 5);set中的find函數是根據元素大小比較查找的，最多查找樹高度次
算法庫中的find函數是遍歷查找的，最多查找元素個數次
兩者:找到了，返回該位置的迭代器，找不到返回 end()
(4)count
set 中的count 也可以用來查找，返回的是元素個數
找到了返回1，找不到返回0
if (s.count(5)){cout << "找到了" << endl;}(5)erase
set支持特定位置的刪除、特定元素的刪除以及迭代器區間范圍內元素的刪除
特定位置的刪除，傳入的 position 應屬于[ first，last )，否則系統會崩潰
正確做法
auto pos = s.find(50);//不能越界訪問 if (pos != s.end())s.erase(pos);特定元素的刪除，函數返回刪除的數量，這里當然是0或1啦
迭代器區間范圍內元素的刪除，范圍一定要準確，否則程序會崩潰或出現未定義行為
(6)lower_bound
iterator lower_bound (const value_type& val) const;該函數返回 大于等于val的第一個元素的迭代器，找不到時返回 end()
(7)upper_bound
iterator upper_bound (const value_type& val) const;該函數返回 大于val 的第一個元素的迭代器，找不到時返回 end()
set與multiset使用一致
(8)equal_range
pair<iterator,iterator> equal_range (const value_type& val) const;pair.fisrt 就是?lower_bound 的返回值
pair.second 就是?upper_bound 的返回值
set與multiset使用一致
4.multiset
multiset與set的最大區別就是 multiset可以存儲多個相同大小的元素
multiset的插入、查找、刪除等與set類似，這里不再贅述
5.map
5.1map的簡介
set容器實際上就是二叉搜索樹應用中說的 KV模型
key: 鍵值對中key的類型
T： 鍵值對中value的類型
Compare(仿函數): 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下(內置類型元素)該參數不需要傳遞，如果無法比較時(自定義類型)，需要用戶自己顯式傳遞比較規則(一般情況下按照函數指針或者仿函數來傳遞)
?Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標準庫提供的
空間配置器(后續講解)
注意：在使用map時，需要包含頭文件。
5.2map的常用函數
map自帶默認構造、迭代器區間構造、拷貝構造等成員函數
(1)insert
map插入的是一個鍵值對pair
map支持單個pair插入、在特定位置后插入以及迭代器區間范圍內pair的插入
重點講講單個pair插入的返回值
插入pair的pair.fistr不在map中，返回一個鍵值對pair<插入pair在map中的迭代器，true>
插入pair的pair.fistr在map中，返回一個鍵值對pair<插入pair在map中的迭代器，false>
map中存儲的是鍵值對pair，且pair.first均不相同
map<string, string> dict;
pair<string, string> kv("insert", "插入");
dict.insert(kv);
dict.insert(pair<string, string>("copy", "復制"));
dict.insert(make_pair("right", "右邊"));
dict.insert({ "pig", "豬" });以上4中方式都可以完成插入:有名鍵值對、匿名鍵值對、調用函數創建鍵值對、多參數構造函數創建鍵值對(C++11)
template <class T1,class T2>pair<T1,T2> make_pair (T1 x, T2 y){return ( pair<T1,T2>(x,y) );}make_pair 函數通常可成為內聯函數，消耗較小
(2)
map?是基于紅黑樹（一種平衡二叉搜索樹）實現的，遍歷方式是中序遍歷且由于元素默認是按小于比較的(比較的是鍵值對中的鍵值Key，即第一個元素)，迭代器打印序列就是升序序列
()map的其余函數與set類似，這里不再贅述，下面詳解map的operator[]函數
函數的類似實現
value& operator[](const Key& x)
{auto ret = insert(make_pair(x, value());return (ret.first)->second;
}ret接收鍵值對<x，value()>插入的返回值：
如果x不在map中，使用value的默認構造與x組成鍵值對并插入
如果x在map中，不插入
ret：<在map中指向x所在鍵值對的迭代器，true(插入成功)\false(插入失敗)>
(ret.first)->second就是x所在鍵值對中的value
這樣 [] 就可以實現插入和修改的功能
此時，統計次數就簡潔了起來
6.multimap
multimap與map的最大區別就是 multimap可以存儲多個key值相同的的鍵值對
除了沒有 operator[]，使用方法與map類似
因為operator[]可修改鍵值對中的value，多個Key值相同的的鍵值對存在時，無法確定修改哪一個鍵值對的value
7.練習題
349. 兩個數組的交集 - 力扣（LeetCode）
692. 前K個高頻單詞 - 力扣（LeetCode）
20. 有效的括號 - 力扣（LeetCode）
138. 隨機鏈表的復制 - 力扣（LeetCode）
map、set 去重+排序的特點，map的映射關系會使效率大大提升！
