一、關(guān)聯(lián)式容器與鍵值對

1.1關(guān)聯(lián)式容器（之前學(xué)的都是序列容器）

在C++初階的時候，我們已經(jīng)接觸了 STL 中的部分容器并進行了模擬實現(xiàn)，比如 vector、list、stack、queue 等，這些容器統(tǒng)稱為序列式容器，因為其底層為線性序列的數(shù)據(jù)結(jié)構(gòu)，里面存儲的是元素本身；

同樣，關(guān)聯(lián)式容器也是用來存儲數(shù)據(jù)的，但與序列式容器不同的是，關(guān)聯(lián)式容器里面存儲的是 <key, value> 結(jié)構(gòu)的鍵值對，因此**在數(shù)據(jù)檢索時比序列式容器效率更高**。

1.2鍵值對pair

鍵值對是用來表示具有一一對應(yīng)關(guān)系的一種結(jié)構(gòu)，該結(jié)構(gòu)中一般只包含兩個成員變量 – key 和 value；其中 key 代表鍵值，value 代表與 key 對應(yīng)的信息。

我們利用英漢互譯的字典來理解：該字典中必然有英文單詞與其對應(yīng)的中文含義，而且，英文單詞與其中文含義是一一對應(yīng)的關(guān)系，即通過該應(yīng)該單詞，在詞典中就可以找到與其對應(yīng)的中文含義。

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;   //keyT2 second;  //valuepair() : first(T1()), second(T2())  //默認(rèn)構(gòu)造{}pair(const T1& a, const T2& b) : first(a), second(b){}
};

可以看到，C++ 中的鍵值對是通過 pair 類來表示的，pair 類中的 first 就是鍵值 key，second 就是 key 對應(yīng)的信息 value；那么以后我們在設(shè)計 KV 模型的容器時只需要在容器/容器的每一個節(jié)點中定義一個 pair 對象即可；

問題：為什么不直接在容器中定義 key 和 value 變量，而是將 key、value 合并到 pair 中整體作為一個類型來使用呢？

答：這是因為 C++ 一次只能返回一個值，如果我們將 key 和 value 單獨定義在容器中，那么我們就無法同時返回 key 和 value；而如果我們將 key、value 定義到另一個類中，那我們就可以直接返回 pair，然后再到 pair 中分別去取 first 和 second 即可

make_pair函數(shù)（map在插入的時候會很方便）

由于 pair 是類模板，所以我們通常是以 顯式實例化 + 匿名對象 的方式來進行使用，但是由于顯式實例化比較麻煩，所以 C++ 還提供了make_pair 函數(shù)，其定義如下：

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{return (pair<T1, T2>(x, y));
}

如上，make_pair 返回的是一個 pair 的匿名對象，匿名對象會自動調(diào)用 pair 的默認(rèn)構(gòu)造完成初始化；但由于 make_pair 是一個函數(shù)模板，所以模板參數(shù)的類型可以根據(jù)實參來自動推導(dǎo)完成隱式實例化，這樣我們就不用每次都顯式指明參數(shù)類型了。

小羊注：對于這個返回的是不是匿名對象，我有點不理解。

注：由于 make_pair 使用起來比 pair 方便很多，所以我們一般都是直接使用 make_pair，而不使用 pair

1.3樹形結(jié)構(gòu)的關(guān)聯(lián)式容器

根據(jù)應(yīng)用場景的不同，STL 總共實現(xiàn)了兩種不同結(jié)構(gòu)的關(guān)聯(lián)式容器

樹型結(jié)構(gòu)與哈希結(jié)構(gòu)；樹型結(jié)構(gòu)的關(guān)聯(lián)式容器主要有四種：

map、set、multimap、multiset

這四種容器的共同點是使用平衡二叉搜索樹作為其底層結(jié)構(gòu)，容器中的元素是一個有序的序列；本文將介紹這四個容器的使用

---

二、set

2.1set的基本介紹

set 是按照一定次序存儲元素的容器，其底層是一棵平衡二叉搜索樹 (紅黑樹)，由于二叉搜索樹的每個節(jié)點的值滿足左孩子 < 根 < 右孩子，并且二叉搜索樹中沒有重復(fù)的節(jié)點，所以 set 可以用來排序、去重和查找，同時由于這是一棵平衡樹，所以 set 查找的時間復(fù)雜度為 O(logN)，效率非常高

set 從1000個數(shù)據(jù)找查找某個數(shù)據(jù)最多找10次，從100萬個數(shù)據(jù)中找某一個數(shù)據(jù)最多找20次，從10億個數(shù)據(jù)中找某一個數(shù)據(jù)最多找30次；我們中國現(xiàn)在人口總數(shù)估計已經(jīng)大于10億了，那么如果想查找是不是得費很多次數(shù)？并不是，2^31=20億直接解決問題，所以最多31次可以精確定位到一個人。

同時，set 是一種 K模型 的容器，也就是說，set 中只有鍵值 key，而沒有對應(yīng)的 value，并且每個 key 都是唯一的 ；set 中的元素也不允許修改，因為這可能會破壞搜索樹的結(jié)構(gòu)，但是 set 允許插入和刪除。

T: set中存放元素的類型，實際在底層存儲<value, value>的鍵值對。
Compare：仿函數(shù)，set中元素默認(rèn)按照小于來比較
Alloc：set中元素空間的管理方式，使用STL提供的空間配置器管理

特點：

1. set 是K模型的容器，所以 set 中插入元素時，只需要插入 key 即可，不需要構(gòu)造鍵值對
2. set中的元素不可以重復(fù)，因此可以使用set進行去重（multiset相反）
3. 由于 set 底層是搜索樹，所以使用 set 的迭代器遍歷 set 中的元素，可以得到有序序列，即 set 可以用來排序
4. set 默認(rèn)使用的仿函數(shù)為 less，所以 set 中的元素默認(rèn)按照小于來比較
5. 由于 set 底層是平衡樹搜索樹，所以 set 中查找某個元素，時間復(fù)雜度為 O(logN)
6. set 中的元素不允許修改，因為這可能破壞搜索樹的結(jié)構(gòu)
7. set 中的底層使用平衡二叉搜索樹 (紅黑樹) 來實現(xiàn)

set 文檔：set - C++ Reference (cplusplus.com)

2.1默認(rèn)構(gòu)造、迭代器區(qū)間構(gòu)造、拷貝構(gòu)造（深拷貝）

void test_set()
{int arr[] = { 1,2,3,4,5 };set<int> s;//默認(rèn)構(gòu)造set<int> s1(arr, arr + 5);//區(qū)間構(gòu)造set<int> s2(s1);//拷貝構(gòu)造for (auto e : s1) cout << e << " "; cout << endl;for (auto e : s2) cout << e << " "; cout << endl;}

2.2set的迭代器

函數(shù)聲明	功能介紹
iterator begin()/end()	返回set中起始位置元素的迭代器返回set中最后一個元素后面的迭代器
const_iterator cbegin() cend() const	返回set中起始位置元素的const迭代器返回set中最后一個元素后面的const迭代器
reverse_iterator rbegin() rend()	返回set第一個元素的反向迭代器，即end，返回set最后一個元素下一個位置的反向迭代器，即 rbegin
const_reverse_iterator crbegin() ，crend() const	返回set第一個元素的反向const迭代器，即cend，返回set最后一個元素下一個位置的反向const迭代器， 即crbegin

我們簡單來看一看代碼：

void test_set1()
{//輸入121345
set<int> s;
s.insert(1);
s.insert(2);
s.insert(1);
s.insert(3);
s.insert(4);
s.insert(5);
//排序+去重
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}

2.3set的插入與刪除

1.insert（有時候插入會直接改變樹的結(jié)構(gòu)）

使用起來一定要小心，這個是set不是map，只插入一個值就可以了！

2.find&&erase

為什么這個庫自己寫find？？別忘了上面講的算法復(fù)雜度，正常的查找都是暴力O（N），set可是妥妥的O（logN）效率相差很大！

在這里erase有一個小細節(jié)我想聊聊：

erase的第一個函數(shù)是迭代器參數(shù)+find函數(shù)就可以實現(xiàn)第二個重載的樣子

erase的第二個函數(shù)有一個小“漏洞”：即使沒有這個值，刪除也不會報錯

（但是我們可以通過接收返回值來判斷是否成功刪除，這也就是我為什么說：第二個erase有find的能力）

為此，我還去找了vector的erase，畢竟之前想要精確的刪除一個值都得加find，而這里有一個獨立的直接可以刪除值的函數(shù)，豈不美哉？！

果然，vector的erase返回值并沒有size_t這個類型的，畢竟別的序列化容器的find可沒有這么優(yōu)秀的find接口，怎敢被隨便調(diào)用？

#include<iostream>
#include<set>
using namespace std;
int main()
{set<int> s;s.insert(1); s.insert(2);s.insert(3);for(auto it:s){cout << it << " ";}cout << endl;s.erase(4);for(auto it:s){cout << it << " ";}cout << endl;cout << s.erase(4);return 0;
}

接下來我們來看erase的第一個構(gòu)造的用法：

void test_set3()
{set<int> s;s.insert(1);s.insert(2);s.insert(3);set<int>::iterator it = s.begin();while (it != s.end()){  cout << *it << " ";++it;}cout << endl;//1 2 3auto pos = s.find(3);//誰用后面這個函數(shù)我笑話誰：auto pos = find(s.begin(), s.end(), 3);if (pos != s.end()){s.erase(pos);}for (auto e : s) cout << e << " ";cout << endl;//1 2
}

3.count：返回個數(shù)，可以判斷一個值是否存在

是不是感覺和erase的第二個感覺效果挺像的，只不過不刪除數(shù)據(jù)捏，這個接口和find類似，那么是不是冗余接口捏？？

count不是為此設(shè)計的！是為了和multiset容器保持接口的一致性。

三、multiset

1. multiset是按照特定順序存儲元素的容器，其中元素是可以重復(fù)的。

2. 在multiset中，元素的value也會識別它(因為multiset中本身存儲的就是<value, value>組成的鍵值對，因此value本身就是key，key就是value，類型為T). multiset元素的值不能在容器中進行修改(因為元素總是const的)，但可以從容器中插入或刪除。

3. 在內(nèi)部，multiset中的元素總是按照其內(nèi)部比較規(guī)則(類型比較)所指示的特定嚴(yán)格弱排序準(zhǔn)則進行排序。

4. multiset容器通過key訪問單個元素的速度通常比unordered_multiset容器慢，但當(dāng)使用迭代器遍歷時會得到一個有序序列。

5. multiset底層結(jié)構(gòu)為二叉搜索樹(紅黑樹)

上面說了這么多的內(nèi)容，其實就是與set的區(qū)別是👉：multiset中的元素可以重復(fù)，set是中value是唯一的

void test_multiset()
{int arr[] = {1,2,3,1,1,6,8};multiset<int> s(arr, arr + sizeof(arr) / sizeof(int));for (auto& e : s){cout << e << " ";} cout << endl;
}

另外，如果有多個值相同，find返回的值是中序的第一個：

void multiset_test2()
{// 用數(shù)組array中的元素構(gòu)造multisetint array[] = {1,2,3,3,3,5,1,2,3,4,3};multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));//如果查找的key在multiset中有多個，則返回中序遍歷中遇到的第一個節(jié)點的迭代器multiset<int>::iterator pos = s.find(3);while (pos != s.end()) {cout << *pos << " ";++pos;} cout << endl;// 查找+刪除//輸出key為3的節(jié)點的個數(shù)cout << s.count(3) << endl;//節(jié)點3個數(shù)pos = s.find(3);if (pos != s.end()){s.erase(pos);}cout << s.count(3) << endl;//節(jié)點3個數(shù)
}

四、map（知識點多）

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

4.1map的模板參數(shù)

key: 鍵值對中key的類型

T：鍵值對中value的類型

Compare: 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下(內(nèi)置類型元素)該參數(shù)不需要傳遞，如果無法比較時(自定義類型)，需要用戶自己顯式傳遞比較規(guī)則(一般情況下按照函數(shù)指針或者仿函數(shù)來傳遞)

Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標(biāo)準(zhǔn)庫提供的空間配置器

4.2map的構(gòu)造

這一塊是用范圍for最得注意的一部分，由于其數(shù)據(jù)的龐大性，所以我們的**auto后面常常需要增加引用**，如果輸出的話，加上const更好

void test_map()
{map<int, int> m;int arr[] = { 1,1,1,2,3,4,5,6 };for (auto& e : arr)//引用記得加上{m.insert(make_pair(e, e));//m.insert(pair<int,int>(e,e));}map<int, int>m1(m.begin(), m.end());//迭代器區(qū)間構(gòu)造for(const auto& e : m1){cout << e.first<<":"<<e.second << " "; }cout << endl;map<int, int> m2(m1);//拷貝構(gòu)造for (const auto& e : m2){cout << e.first << ":" << e.second << " ";}cout << endl;
}

4.3map的修改（[]的完整用法是最難理解的）

1.insert插入（make_pair(x,y)別忘了寫）

void test_map1()
{map<string, string> dict;dict.insert(pair<string, string>("排序", "sort"));dict.insert(pair<string, string>("左邊", "left"));dict.insert(pair<string, string>("右邊","right"));//make_pair()dict.insert(make_pair("字符串", "string"));//輸出查看結(jié)果map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first<<":"<<it->second << endl;//訪問元素這么訪問，一定要注意了++it;}cout << endl;
}

make_pair:函數(shù)模板，不需要像pair一樣顯示聲明類型，而是通過傳參自動推導(dǎo),相比于typedef更好用一些

2.引入[]之統(tǒng)計次數(shù)

統(tǒng)計不同水果出現(xiàn)的個數(shù)

第一種方法：迭代器

void test_map_total()
{
//統(tǒng)計水果出現(xiàn)的次數(shù)string arr[] = { "蘋果", "西瓜", "香蕉", "草莓", "蘋果", "西瓜", "蘋果","蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };map<string, int> countMap;for (auto& e : arr){map<string, int>:: iterator it = countMap.find(e);if (it == countMap.end())//如果沒找到，就插入{countMap.insert(make_pair(e, 1));}else{it->second++;//如果找到了，就給這個水果次數(shù)+1}
}map<string, int>::iterator it=countMap.begin();while(it!=countMap.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;
}

第二種方法：map[]的使用：

void test_map_total2()
{//統(tǒng)計水果出現(xiàn)的次數(shù)string arr[] = { "蘋果", "西瓜", "香蕉", "草莓", "蘋果", "西瓜", "蘋果","蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;//如果找不到就插入，找到就給第二個值++}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}

map的[]支持隨機訪問這個可以理解，但是為什么++就可以實現(xiàn)我們的任務(wù)呢？？

3.詳解[]的使用以及底層原理

[]的三個功能

1. 插入（本質(zhì)上operator中用了insert函數(shù)）
2. 修改（本質(zhì)是返回值是對象的second的引用）
3. 查找（本質(zhì)上是insert的第二個pair參數(shù)）

一句話解釋清楚：給一個key，可以查找在不在，如果不在則可以插入，在的話either可以查找or可以進行修改value

代碼解釋：

void test_insert_change_find()
{map<string, string> dict;dict.insert(make_pair("上", "up"));dict.insert(make_pair("下", "down"));dict.insert(make_pair("左", "left"));dict.insert(make_pair("右", "right"));//插入（前提是key不在）dict["迭代器"];//修改dict["迭代器"]= "iterator";//查找（前提是得key在，key要是不在可就成了插入了）cout << dict["上"] << endl; cout << endl;cout << endl;cout << "輸出map中的值" << endl;map<string, string>::iterator it=dict.begin();while (it != dict.end()){cout << it->first<<":"<<it->second << endl;++it;//老忘了寫}cout << endl;
}

map在輸出的時候，好像里面的key值也是從小到大排序的

注意：[]用的時候要小心，不在的話會偷偷給你插入

[]的底層原理

operator[]函數(shù)原型如下：

mapped_type& operator[] (const key_type& k);
//mapped_type: pair中第二個參數(shù)，即second
//key_type: pair中第一個參數(shù)，即first

operator[]函數(shù)定義如下：

mapped_type& operator[] (const key_type& k) 
{(*((this->insert(make_pair(k, mapped_type()))).first)).second;
}

拆分operator[]函數(shù)定義：（這個是核心）

V& operator[] (const K& k)//返回值是引用，所以外面可以修改eg:m[i]++
{pair<iterator, bool> ret = insert(make_pair(k, V()));//make_pair里面是匿名對象//return *(ret.first)->second;return ret.first->second;
}

insert函數(shù)定義如下：

pair<iterator,bool> insert (const value_type& val)
{//可以看到，insert的返回值是pair，pair的第一個參數(shù)是迭代器//bool：插入成功.....1，插入失敗.....0
}

insert函數(shù)的返回值：（因為operator[]函數(shù)中的ret參數(shù)接受insert返回值）

用我“高超”的英語功底翻譯之后，我們可得知：

• 若 key 相等：返回 key 位置迭代器+false
• 若 key 不相等：返回 key 新插入位置迭代器+true

接著我們目光轉(zhuǎn)移到拆分的[]函數(shù)當(dāng)中：

operator[] 會取出 pair 中的迭代器 (也就是ret.first)，然后對迭代器進行解引用得到一個 pair<k, v> 對象（但是這里編譯器進行優(yōu)化了，這個*不寫也是可以的），最后再返回 pair 對象中的 second 的引用，即 key 對應(yīng)的 value 的引用；所以我們可以在函數(shù)外部直接修改 key 對應(yīng)的 value 的值（如果不返回引用的話，那么一定是不可能++就改變值大小的）

map[]的總結(jié)

4.4綜合題之map利用字符串流統(tǒng)計出現(xiàn)次數(shù)

//一個經(jīng)典的期末考試題目
#include<iostream>
#include<map>
#include<string>
#include<sstream>
using namespace std;
int main()
{string s="1 2 3 4 5 6 7 8 9 1 2 1 2 3 4 5 6 4 2 3 4";//注意，這里一定是得有空格的,為了和之后的string stream對應(yīng)map<int,int>m;stringstream is(s);//把字符串構(gòu)造了is字符串流類對象while(is.eof()!=true) //如果到了文件尾部 則自動返回true 如果沒到 則返回false{int num;//num << is; is >> num ;//is的值流向num 此時num有1 因為后面有空格 無法接收更多的值m[num]++;//小心 不是m[num++];!!!!!!!//經(jīng)典的統(tǒng)計數(shù)字的方法 如果沒有就插入 如果有就將第二個值++ 而且還可以返回第二個值的大小 //V& operator(const key& k)}cout << m[2] << endl;//(*((this->insert(make_pair(k,mapped_type()))).first)).second 返回的是數(shù)字2的統(tǒng)計次數(shù)return 0;
}

---

五、multimap

和 set 與 multiset 的關(guān)系一樣，multimap 存在的意義是允許 map 中存在 key 值相同的節(jié)點，multimap 與map 的區(qū)別和 multiset 與 set 的區(qū)別一樣 – find 返回中序遍歷中遇到的第一個節(jié)點的迭代器，count 返回和 key 值相等的節(jié)點的個數(shù)：

需要注意的是，multimap 中并沒有重載 [] 運算符，因為 multimap 中的元素是可以重復(fù)的，如果使用 [] 運算符，會導(dǎo)致多個元素的 key 值相同，無法確定具體訪問哪一個元素

---

六、leetcode真題

6.1set之倆個數(shù)組的交集

兩個數(shù)組的交集（雙指針，而且出現(xiàn)一大一小，必須是小元素先++；出現(xiàn)相同就一起++）

給定兩個數(shù)組 nums1 和 nums2 ，返回 它們的交集 。輸出結(jié)果中的每個元素一定是 唯一 的。我們可以 不考慮輸出結(jié)果的順序。

利用set的排序+去重特性，然后去進行比對，找出兩個數(shù)組之間的交集：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {//排序＋去重set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());//比對算法邏輯auto it1 = s1.begin();auto it2 = s2.begin();vector<int> ret;while(it1!=s1.end()&&it2!=s2.end()){if(*it1==*it2){ret.push_back(*it1);it1++;it2++;}else if(*it1>*it2){it2++;}else{it1++;}}return ret;}
};

6.2map之前K個高頻單詞

前K個高頻單詞（與sort的穩(wěn)定性以及pair的大小比較規(guī)則有關(guān)，較難）

給定一個單詞列表 words 和一個整數(shù) k ，返回前 k 個出現(xiàn)次數(shù)最多的單詞。

返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率， 按字典順序 排序。

class Solution {
public:class greater{public:bool operator()(const pair<string,int>&l,const pair<string,int>& r){return l.second>r.second||(l.second==r.second&&l.first<r.first);}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> countMap;for(auto&e:words) countMap[e]++;priority_queue<pair<string,int>,vector<pair<string,int>>,greater> pq;for(auto it = countMap.begin();it!=countMap.end();it++){pq.push(*it);if(pq.size()>k)pq.pop();}vector<string> ret;ret.resize(k);for(int i = k-1;i>=0;i--){ret[i] = pq.top().first;pq.pop();}return ret;}
};

希望給大家?guī)韼椭?#xff01;！！