1.序列式容器和關聯式容器

前?我們已經接觸過STL中的部分容器如：string、vector、list、deque、array、forward_list等，這些容器統稱為序列式容器，因為邏輯結構為線性序列的數據結構，兩個位置存儲的值之間?般沒有緊密的關聯關系，?如交換?下，他依舊是序列式容器。順序容器中的元素是按他們在容器中的存儲位置來順序保存和訪問的。
關聯式容器也是?來存儲數據的，與序列式容器不同的是，關聯式容器邏輯結構通常是?線性結構，兩個位置有緊密的關聯關系，交換?下，他的存儲結構就被破壞了。順序容器中的元素是按關鍵字來保存和訪問的。關聯式容器有map/set系列unordered_map/unordered_set系列。
本章節講解的map和set底層是紅?樹，紅?樹是?顆平衡?叉搜索樹。set是key搜索場景的結構，map是key/value搜索場景的結構。

2.set系列的使用

2.1set類的介紹

? set的聲明如下，T就是set底層關鍵字的類型

? set默認要求T?持?于?較，如果不?持或者想按??的需求?可以??實現仿函數傳給第?個模 版參數

? set底層存儲數據的內存是從空間配置器申請的，如果需要可以??實現內存池，傳給第三個參 數。

? ?般情況下，我們都不需要傳后兩個模版參數。

? set底層是?紅?樹實現，增刪查效率是，迭代器遍歷是?的搜索樹的中序，所以是有序 的。 O(logN)

? 前?部分我們已經學習了vector/list等容器的使?，STL容器接?設計，?度相似，所以這?我們 就不再?個接??個接?的介紹，?是直接帶著?家看?檔，挑?較重要的接?進?介紹。

template < class T, // set::key_type/value_typeclass Compare = less<T>, // set::key_compare/value_compareclass Alloc = allocator<T> // set::allocator_type> class set;

2.2set的構造和迭代器

set的構造我們關注以下?個接?即可。?set?持正向和反向迭代遍歷，遍歷默認按升序順序，因為底層是?叉搜索樹，迭代器遍歷?的中序；?持迭代器就意味著?持范圍for，set的iterator和const_iterator都不?持迭代器修改數據，修改 關鍵字數據，破壞了底層搜索樹的結構。

// empty (1) ?參默認構造 
explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器區間構造 
template <class InputIterator>set (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());// copy (3) 拷?構造 
set (const set& x);// initializer list (5) initializer 列表構造 
set (initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// 迭代器是?個雙向迭代器 
iterator -> a bidirectional iterator to const value_type// 正向迭代器 
iterator begin();
iterator end();// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

#include<iostream>
#include<set>
#include<vector>
using namespace std;int main()
{// 1.無參構造set<int> s1;// 2.迭代器區間構造vector<int> v1 = { 1,2,2,3,4,5 };set<int> s2(v1.begin(), v1.end());// 3.拷貝構造set<int> s3(s2);// 4.鏈表構造set<int> s4({ 1,2,3,4,5,1,2 });return 0;
}

2.3set的增刪改

set的增刪查關注以下?個接?即可：

Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)// 單個數據插?，如果已經存在則插?失敗 
pair<iterator,bool> insert (const value_type& val);// 列表插?，已經在容器中存在的值不會插? 
void insert (initializer_list<value_type> il);// 迭代器區間插?，已經在容器中存在的值不會插? 
template <class InputIterator>
void insert (InputIterator first, InputIterator last);// 查找val，返回val所在的迭代器，沒有找到返回end() 
iterator find (const value_type& val);// 查找val，返回Val的個數 
size_type count (const value_type& val) const;// 刪除?個迭代器位置的值 
iterator erase (const_iterator position);// 刪除val，val不存在返回0，存在返回1 
size_type erase (const value_type& val);// 刪除?段迭代器區間的值 
iterator erase (const_iterator first, const_iterator last);// 返回?于等val位置的迭代器 
iterator lower_bound (const value_type& val) const;// 返回?于val位置的迭代器 
iterator upper_bound (const value_type& val) const;

2.4insert和迭代器遍歷使用案例

#include<iostream>
#include<set>
using namespace std;int main()
{// 去重+升序排序set<int> s1;// 去重+降序排序,給一個大于的仿函數//set<int,greater<int>> s1;s1.insert(1);s1.insert(1);s1.insert(2);s1.insert(3);//set<int>::iterator it1 = s1.begin();auto it1 = s1.begin();while (it1 != s1.end()){// error C3892: “it”: 不能給常量賦值 //*it1 = 1;cout << *it1 << " ";it1++;}cout << endl;// 插??段initializer_list列表值，已經存在的值插?失敗s1.insert({ 1,2,3,4 });for (auto e : s1){cout << e << " ";}cout << endl;set<string> strset = { "sort","insert","add" };// 遍歷string比較ascll碼大小順序遍歷的for (auto e : strset){cout << e << " ";}cout << endl;return 0;
}

2.5find和erase使用案例

#include<iostream>
#include<set>
using namespace std;int main()
{set<int> s1 = { 4,2,7,2,8,5,9 };for (auto e : s1){cout << e << " ";}cout << endl;// 刪除最小值s1.erase(s1.begin());for (auto e : s1){cout << e << " ";}cout << endl;// 直接刪除xint x;cin >> x;int num = s1.erase(x);if (num == 0){cout << x << "不存在!" << endl;}for (auto e : s1){cout << e << " ";}cout << endl;// 直接查找再利用迭代器刪除xcin >> x;auto pos = s1.find(x);if (pos != s1.end()){s1.erase(pos);}else{cout << x << "不存在!" << endl;}for (auto e : s1){cout << e << " ";}cout << endl;// 算法庫的查找O(N)auto pos1 = find(s1.begin(), s1.end(), x);// set自身實現的查找O(logN)auto pos2 = s1.find(x);// 利用count間接實現快速查找cin >> x;if (s1.count(x)){cout << x << "在!" << endl;}else{cout << x << "不在!" << endl;}return 0;
}

2.6multiset和set的差異

multiset和set的使?基本完全類似，主要區別點在于multiset?持值冗余，那么 insert/find/count/erase都圍繞著?持值冗余有所差異，具體參看下?的樣例代碼理解。

find：

#include<iostream>
#include<set>
using namespace std;int main()
{// 相?set不同的是，multiset是排序，但是不去重 multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };for (auto e : s){cout << e << " ";}cout << endl;// 相?set不同的是，x可能會存在多個，find查找中序的第?個 int x;cin >> x;auto pos = s.find(x);while (pos != s.end() && *pos == x){cout << *pos << " ";pos++;}cout << endl;// 相?set不同的是，count會返回x的實際個數 cout << s.count(x) << endl;// 相?set不同的是，erase給值時會刪除所有的xs.erase(x);for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

3.map系列的使用

3.1map類型介紹

map的聲明如下，Key就是map底層關鍵字的類型，T是map底層value的類型，set默認要求Key?持 ?于?較，如果不?持或者需要的話可以??實現仿函數傳給第?個模版參數，map底層存儲數據的 內存是從空間配置器申請的。?般情況下，我們都不需要傳后兩個模版參數。map底層是?紅?樹實 現，增刪查改效率是 O(logN) ，迭代器遍歷是?的中序，所以是按key有序順序遍歷的。

template < class Key, // map::key_type key類型class T, // map::mapped_type value類型class Compare = less<Key>, // map::key_compare 數據比較class Alloc = allocator<pair<const Key,T> > //map::allocator_type 空間配置器> class map;

3.2pair類型介紹

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) );
}

// empty (1) ?參默認構造
explicit map (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器區間構造
template <class InputIterator>
map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());// copy (3) 拷?構造
map (const map& x);// initializer list (5) initializer 列表構造
map (initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// 迭代器是?個雙向迭代器
iterator -> a bidirectional iterator to const value_type// 正向迭代器
iterator begin();
iterator end();// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

#include<iostream>
#include<map>
using namespace std;int main()
{// 無參默認構造map<int, int> m1;// 傳參構造pair<string, int> p1 = { "英語",90 };pair<string, int> p2 = { "數學",95 };pair<string, int> p3 = { "語文",80 };map<string, int> m2 = { p1,p2,p3 };// 匿名對象初始化map<string, string> m3 = { pair<string, string>("insert", "插入") };// make_pair可自動推導模板參數類型，也可指定類型，make_pair<string,string>map<string, string> m4 = { make_pair("string","字符串") };// initializer_list構造map<string, string> m5 = { {"left", "左邊"}, {"right", "右邊"},
{"insert", "插?"},{ "string", "字符串" } };// 迭代器區間初始化map<string, string> m6(m5.begin(), m5.end());// 拷貝構造map<string, string> m7(m6);return 0;
}

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>// 單個數據插?，如果已經key存在則插?失敗,key存在相等value不相等也會插?失敗
pair<iterator,bool> insert (const value_type& val);// 列表插?，已經在容器中存在的值不會插?
void insert (initializer_list<value_type> il);// 迭代器區間插?，已經在容器中存在的值不會插?
template <class InputIterator>
void insert (InputIterator first, InputIterator last);// 查找k，返回k所在的迭代器，沒有找到返回end()
iterator find (const key_type& k);// 查找k，返回k的個數
size_type count (const key_type& k) const;// 刪除?個迭代器位置的值
iterator erase (const_iterator position);// 刪除k，k存在返回0，存在返回1
size_type erase (const key_type& k);// 刪除?段迭代器區間的值
iterator erase (const_iterator first, const_iterator last);

operator[]內部調用insert，insert的返回值是pair<iterator,bool>,如果插入成功，返回的pair的first是新插入key所在節點的迭代器，second是true。如果插入失敗，返回的pair的first是已經存在的key所在節點的迭代器，second是false。mapped_type()是value的默認構造，對于自定義成員會調用其默認構造，對于內置類型，如int，會初始化成0，double會初始化成0.0

插入成功的時候，operator[]具備了插入+修改的功能。

插入失敗的時候，operator[]具備了查找+修改的功能。

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>// 查找k，返回k所在的迭代器，沒有找到返回end()，如果找到了通過iterator可以修改key對應的
mapped_type值
iterator find (const key_type& k);// ?檔中對insert返回值的說明
// The single element versions (1) return a pair, with its member pair::first
set to an iterator pointing to either the newly inserted element or to the
element with an equivalent key in the map. The pair::second element in the pair
is set to true if a new element was inserted or false if an equivalent key
already existed.// insert插??個pair<key, T>對象
// 1、如果key已經在map中，插?失敗，則返回?個pair<iterator,bool>對象，返回pair對象
first是key所在結點的迭代器，second是false
// 2、如果key不在在map中，插?成功，則返回?個pair<iterator,bool>對象，返回pair對象
first是新插?key所在結點的迭代器，second是true
// 也就是說?論插?成功還是失敗，返回pair<iterator,bool>對象的first都會指向key所在的迭
代器
// 那么也就意味著insert插?失敗時充當了查找的功能，正是因為這?點，insert可以?來實現
operator[]
// 需要注意的是這?有兩個pair，不要混淆了，?個是map底層紅?樹節點中存的pair<key, T>，另
?個是insert返回值pair<iterator,bool>pair<iterator,bool> insert (const value_type& val);
mapped_type& operator[] (const key_type& k);// operator的內部實現
mapped_type& operator[] (const key_type& k)
{// 1、如果k不在map中，insert會插?k和mapped_type默認值，同時[]返回結點中存儲mapped_type值的引?，那么我們可以通過引?修改返映射值。所以[]具備了插?+修改功能// 2、如果k在map中，insert會插?失敗，但是insert返回pair對象的first是指向key結點的迭代器，返回值同時[]返回結點中存儲mapped_type值的引?，所以[]具備了查找+修改的功能pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

3.6構造遍歷及增刪查使用樣例

#include<iostream>
#include<map>
using namespace std;int main()
{// initializer_list構造及迭代遍歷map<string, string> dict = { {"left", "左邊"}, {"right", "右邊"},
{"insert", "插入"},{ "string", "字符串" } };auto it = dict.begin();while (it != dict.end()){//cout << (*it).first <<":"<<(*it).second << endl;// map的迭代基本都使?operator->,這?省略了?個->// 第一個->是迭代器運算符重載，返回pair*，第二個箭頭是結構指針解引?取pair數據//cout << it.operator->()->first << ":" << it.operator->()-> second << endl;cout << it->first << ":" << it->second << endl;it++;}cout << endl;// insert插?pair對象的4種?式，對?之下，最后?種最?便pair<string, string> kv1("first", "第一個");dict.insert(kv1);dict.insert(pair<string, string>("second", "第二個"));dict.insert(make_pair("sort", "排序"));dict.insert({ "auto","自動的" });// map不允許鍵值冗余，已經存在的key會插入失敗dict.insert({ "left", "左邊，剩余" });for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;// 查找string str;while (cin >> str){auto ret = dict.find(str);if (ret != dict.end()){cout << "->" << ret->second << endl;}else{cout << "查無此單詞" << endl;}}// erase等接?跟set完全類似return 0;
}

3.7map的迭代器和[]功能樣例

#include<iostream>
#include<map>
using namespace std;int main()
{// 1.利用find和iterator修改功能，統計水果出現次數string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜",
"蘋果", "香蕉", "蘋果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// 先查找?果在不在map中// 1、不在，說明?果第?次出現，則插?{?果, 1}// 2、在，則查找到的節點中?果對應的次數++auto ret = countMap.find(str);if (ret == countMap.end()){countMap.insert({str,1});}else{ret->second++;}}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;// 2.利?[]插?+修改功能，巧妙實現統計?果出現的次數map<string, int> countMap2;for (const auto& str : arr){// []先查找?果在不在map中// 1、不在，說明?果第?次出現，則插?{?果, 0}，同時返回次數的引?，++?下就變成1次了// 2、在，則返回?果對應的次數++// 不在的時候[]具有查找+修改功能// 在的時候[]具有插入+修改功能countMap2[str]++;}for (const auto& e : countMap2){cout << e.first << ":" << e.second << endl;}// 3.[]的功能map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在->插? {"insert", string()}dict["insert"];// 插?+修改dict["left"] = "左邊";// 修改dict["left"] = "左邊、剩余";// key存在->查找cout << dict["left"] << endl;return 0;
}

3.8multimap和map的差異

multimap和map的使?基本完全類似，主要區別點在于multimap?持關鍵值key冗余，那么

insert/find/count/erase都圍繞著?持關鍵值key冗余有所差異，這?跟set和multiset完全?樣，?如 find時，有多個key，返回中序第?個。其次就是multimap不?持[]，因為?持key冗余，[]就只能? 持插?了，不能?持修改。

4.兩道相關題

4.1隨機鏈表的復制

https://leetcode.cn/problems/copy-list-with-random-pointer/description/

// 1.隨機鏈表的復制
/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/// 1.
// 利用原鏈表的節點做key，新鏈表對應的節點做value
// 后續新鏈表的random就是nodeMap[cur->random]
// 通過原鏈表的random節點，找到新鏈表的random節點
class Solution {
public:Node* copyRandomList(Node* head) {map<Node*, Node*> nodeMap;Node* copyhead = nullptr, * copytail = nullptr;Node* cur = head;while (cur){if (copytail == nullptr){// 空鏈表copyhead = copytail = new Node(cur->val);}else{//尾插copytail->next = new Node(cur->val);copytail = copytail->next;}// 原鏈表節點做key，新鏈表節點做valuenodeMap[cur] = copytail;cur = cur->next;}cur = head;Node* copyCur = copyhead;while (cur){if (cur->random == nullptr){copyCur->random = nullptr;}else{copyCur->random = nodeMap[cur->random];}cur = cur->next;copyCur = copyCur->next;}return copyhead;}
};// 2.在原節點后面尾接新的相同的節點，然后copy->random=cur->random->next,然后在從原鏈表上分離
class Solution {
public:Node* copyRandomList(Node* head) {if (head == nullptr)return nullptr;Node* cur = head;while (cur){Node* newNode = new Node(cur->val);newNode->next = cur->next;cur->next = newNode;cur = cur->next->next;}cur = head;Node* copyCur = cur->next;while (cur){if (cur->random == nullptr){copyCur->random = nullptr;}else{copyCur->random = cur->random->next;}cur = cur->next->next;if (cur != nullptr)copyCur = copyCur->next->next;}Node* copyhead = nullptr, * copytail = nullptr;cur = head;while (cur){Node* nextNode = cur->next->next;if (copyhead == nullptr){copyhead = copytail = cur->next;}else{copytail->next = cur->next;copytail = copytail->next;}cur->next = nextNode;cur = nextNode;}return copyhead;}
};

4.2前k個高頻單詞

https://leetcode.cn/problems/top-k-frequent-words/submissions/661053571/

class Solution {
public:// 將words里的數據放入map中統計個數順便排序// 再把map里的數據轉入vectror中讓sort排序，// 因為sort只支持隨機迭代器容器的排序// 在寫個仿函數指定比較規則struct kvCompare{bool operator()(const pair<string, int>& p1, const pair<string, int>& p2) const{return p1.second > p2.second ||(p1.second == p2.second && p1.first < p2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for (const auto& e : words){countMap[e]++;}vector<pair<string, int>> v(countMap.begin(), countMap.end());sort(v.begin(), v.end(), kvCompare());//stable_sort(v.begin(), v.end(), kvCompare());// stable_sort是穩定排序，不會破壞順序，只寫return p1.second > p2.second即可vector<string> ret;for (int i = 0; i < k; i++){ret.push_back(v[i].first);}return ret;}
};