一、關聯式容器

在初階階段，我們已經接觸過STL中的部分容器，比如: vector、list、deque、forward_list(C++11)等，這些容器統稱為序列式容器，因為其底層為線性序列的數據結構，里面存儲的是元素本身(單純的用來存儲數據, 且數據可以存在容器的任意位置, 數據之間沒有關聯)。那什么是關聯式容器呢?它與序列式容器有什么區別?

🍅關聯式容器也是用來存儲數據的，與序列式容器不同的是，其里面存儲的是 <key, value> 結構的鍵值對，在數據檢索時比序列式容器效率更高。

二、鍵值對

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

三、樹形結構的關聯式容器

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

3.1 set類的簡介

C++官網set類文檔：set類

(1) set是按照一定次序存儲元素的容器。
(2) 在set中，元素的value也標識它(value就是key，類型為T)，并且每個value必須是唯一的。set中的元素不能在容器中被修改(元素總是const)，但是可以從容器中插入或刪除它們。
(3) 在內部，set中的元素總是按照其內部比較對象(類型比較)所指示的特定嚴格弱排序準則進行排序。
(4) set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據順序對子集進行直接迭代。
(5) set在底層是用二叉搜索樹(紅黑樹)實現的。

🍑注意: 🍑
1.與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key, value>，set中只放value；但在底層實際存放的是由<value,value>構成的鍵值對。
2.set中插入元素時，只需要插入value即可，不需要構造鍵值對。
3.set中的元素不可以重復(因此可以使用set進行去重)。
4.使用set的迭代器遍歷set中的元素，可以得到有序序列。
5.set中的元素默認按照小于來比較。
6.set中查找某個元素，時間復雜度為: O(log₂n)。
7.set中的元素不允許修改(為什么?)
8.set類的底層使用二叉搜索樹(紅黑樹)來實現。

3.2 set的接口

3.2.1 set的模版參數列表

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

3.2.2 set的構造

Construct set:

函數聲明	功能介紹
set(const Compare& comp = Compare(), const Allocator& = Allocator());	構造空的set
set(InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator());	用[first, last)區間中的元素構造set
set(const set<Key,Compare,Allocator>& x);	set的拷貝構造

3.2.3 set的迭代器

Iterators:

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

3.2.4 set的容量

Capacity:

函數聲明	功能介紹
bool empty( ) const	檢測set是否為空，空返回true，否則返回true
size_type size() const	返回set中有效元素的個數

3.2.5 set的修改操作

Modifiers:

函數聲明	功能介紹
pair<iterator,bool> insert(const value_type& x)	在set中插入元素x，實際插入的是<x, x>構成的鍵值對，如果插入成功，返回<該元素在set中的位置，true>，如果插入失敗，說明x在set中已經存在，返回<x在set中的位置，false>
iterator insert(iterator position, const value_type& val);	在set中插入一個元素val，并返回一個迭代器，該迭代器指向新插入的元素 或 在集合中已經具有相同值的元素。
void erase(iterator position)	刪除set中position位置上的元素
size_type erase(const key_type& x)	刪除set中值為x的元素，返回刪除的元素的個數
void erase(iterator first, iterator last)	刪除set中[first, last)區間中的元素
void swap(set<Key,Compare,Allocator>& st);	交換set中的元素
void clear( )	將set中的元素清空
iterator find(const key_type& x) const	返回set中值為x的元素的位置
size_type count(const key_type& x) const	返回set中值為x的元素的個數

3.3 set的使用案例

(1) set類的簡單增刪查操作：

#include<iostream>
#include<set>
using namespace std;void test_set1()
{set<int> s;s.insert(5);s.insert(1);s.insert(3);pair<set<int>::iterator,bool> ret1 = s.insert(4);cout << ret1.second << endl;s.insert(2);pair<set<int>::iterator, bool> ret2 = s.insert(5);cout << ret2.second << endl;s.insert(6);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;s.erase(2);for (auto e : s){cout << e << " ";}cout << endl;it = s.find(4);if (it != s.end()){s.erase(4);}for (auto e : s){cout << e << " ";}cout << endl;
}
int main()
{test_set1();return 0;
}

程序運行結果：

注意：insert的返回類型是一個鍵值對pair<iterator, bool>，所以如果插入成功則pair的second就為true；而且set不能插入重復的值，所以插入失敗時second就為false。
(2) lower_bound和upper_bound的使用

void test_set2()
{set<int> myset;set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++){myset.insert(i * 10);}itlow = myset.lower_bound(30); //lower_bound返回指向第一個大于等于(>=)給定鍵值的元素的迭代器itup = myset.upper_bound(60);  //upper_bound返回指向第一個大于(>)給定鍵值的元素的迭代器myset.erase(itlow, itup);  //執行以后的結果:10 20 70 80 90 即刪除[itlow,itup)區間里的元素for (auto e : myset){cout << e << " ";}cout << endl;
}
int main()
{test_set2();return 0;
}

程序運行結果：

(3) equal_range和count接口

void test_set3()
{set<int> myset;for (int i = 1; i < 5; i++){myset.insert(i * 10);}pair<set<int>::const_iterator, set<int>::const_iterator> ret = myset.equal_range(30);cout << *ret.first << endl;  //指向第一個>=給定值的元素(即lower_bound的結果)cout << *ret.second << endl; //指向第一個>給定值的元素(即upper_bound的結果)myset.erase(30);//count是用來確定指定元素在集合中是否存在//count返回值類型為size_t//count返回值的含義是:返回集合中與給定鍵值相等的元素數量(即1或者0)if (myset.count(30))  {cout << "30在" << endl;}else{cout << "30不在" << endl;}
}
int main()
{test_set3();return 0;
}

程序運行結果：

所以set類的作用歸結下來就是： 🍆排序+去重 🍆；而且set是不支持修改的。但是在multiset類里就支持插入重復的元素。

3.4 multiset類的介紹

c++官網multiset類文檔：multiset
(1) multiset是按照特定順序存儲元素的容器，其中元素是可以重復的。
(2) 在multiset中，元素的value也會識別它(因為multiset中本身存儲的就是<value,value>組成的鍵值對，因此value本身就是key，key就是value，類型為T)。multiset元素的值不能在容器中進行修改(因為元素總是const的)，但可以從容器中插入或刪除。
(3) 在內部，multiset中的元素總是按照其內部比較規則(類型比較)所指示的特定嚴格弱排序準則進行排序。
(4) multiset容器通過key訪問單個元素的速度通常比unordered_multiset容器慢，但當使用迭代器遍歷時會得到一個有序序列。
(5) multiset底層結構為二叉搜索樹(紅黑樹)。

🍑注意: 🍑
1.multiset在底層中存儲的是<value,value>的鍵值對。
2.mtltiset的插入接口中只需要插入即可。
3.與set的區別是，multiset中的元素可以重復，set是中value是唯一的。
4.使用迭代器對multiset中的元素進行遍歷，可以得到有序的序列。

3.5 multiset的使用案例

此處只簡單演示set與multiset的不同，其他接口與set相同，感興趣的小伙伴可自行參考set類的介紹。

void test_set4()
{multiset<int> s;s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(4);s.insert(2);s.insert(5);s.insert(2);s.insert(1);s.insert(6);multiset<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;//equal_range在set中的意義不大,但在multiset中的作用就比較明顯auto ret = s.equal_range(2);//刪除[ret.first,ret.second)區間中的元素，即刪除所有的2s.erase(ret.first, ret.second); for (auto e : s){cout << e << " ";}cout << endl;cout << s.count(1) << endl; //這里count用來確定二叉樹中1的個數//erase刪除的是二叉樹中所有的5,返回值是5的個數size_t n = s.erase(5); cout << n << endl;for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{test_set4();return 0;
}

程序運行結果：

與set類相比，multiset類中的equal_range、erase和count接口的作用就比較直觀明顯了。

3.6 map類的簡介

c++官網map類文檔：map
(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通常被實現為二叉搜索樹(更準確的說: 🍎平衡二叉搜索樹🍎(紅黑樹))。

3.7 map的接口

3.7.1 map的模版參數說明

key: 鍵值對中key的類型
T : 鍵值對中value的類型
Compare: 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下(內置類型元素)該參數不需要傳遞，如果無法比較時(自定義類型)，需要用戶自己顯式傳遞比較規則(一般情況下按照函數指針或者仿函數來傳遞)
Alloc: 通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標準庫提供的空間配置器
注意: 在使用map時，需要包含頭文件。

3.7.2 map的構造

函數聲明	功能介紹
map()	構造一個空的map

3.7.3 map的迭代器

函數聲明	功能介紹
begin()和end()	begin:首元素的位置，end:最后一個元素的下一個位置
cbegin()和cend()	與begin和end意義相同，但cbegin和cend所指向的元素不能修改
rbegin()和rend()	反向迭代器，rbegin在end位置，rend在begin位置，其++和- -操作與begin和end操作移動相反
crbegin()和crend()	與rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改

3.7.4 map的容量與元素訪問

函數聲明	功能介紹
bool empty() const	檢測map中的元素是否為空，是返回true，否則返回false
size_type size() const	返回map中有效元素的個數
mapped_type& operator[] (const key_type& k)	返回與key對應的value

問題: 當key不在map中時，通過operator[ ]獲取對應value時會發生什么問題呢? 下面是官網給出的operator[ ]解釋：

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

3.7.5 map中元素的修改

函數聲明	功能介紹
pair<iterator,bool> insert(const value_type& x)	在map中插入鍵值對x，注意x是一個鍵值對，返回值也是鍵值對：iterator代表新插入元素的位置，bool代表是否插入成功
void erase(iterator position)	刪除position位置上的元素
size_type erase(const key_type& x)	刪除鍵值為x的元素
void erase(iterator first, iterator last)	刪除[first, last)區間中的元素
void swap(map<Key,T,Compare,Allocator>& mp)	交換兩個map中的元素
void clear()	將map中的元素清空
iterator find(const key_type& x)	在map中插入key為x的元素，找到返回該元素位置的迭代器，否則返回end
const_iterator find(const key_type& x) const	在map中插入key為x的元素，找到返回該元素位置的const迭代器，否則返回cend
size_type count(const key_type& x) const	返回key為x的鍵值在map中的個數，注意map中key是唯一的，因此該函數的返回值要么為0，要么為1，因此也可以用該函數來檢測一個key是否在map中

3.8 map的使用案例

(1) map的元素插入是用pair進行插入的！通常使用函數模版make_pair進行map的元素插入：

void test_map1()
{map<string, string> dict;//用pair類模板的匿名對象插入dict.insert(pair<string, string>("sort", "排序"));dict.insert(pair<const char*, const char*>("tree", "樹"));//用make_pair進行插入dict.insert(make_pair("left", "左邊"));string s1("right"), s2("右邊");dict.insert(make_pair(s1, s2));map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (auto& kv : dict){//kv.first += "x"; //map的key不支持修改kv.second += "y";  //map的value支持修改cout << kv.first << ":" << kv.second << endl;}
}
int main()
{test_map1();return 0;
}

程序運行結果：

💡make_pair是一個函數模版，其聲明如下：

(2) 統計水果出現的次數：主要使用的就是operator[ ]操作符重載，后面也會重點學習：

void test_map2()
{string arr[] = { "西瓜","蘋果","香蕉","西瓜","西瓜","蘋果","香蕉","蘋果","香蕉","香蕉","蘋果","蘋果" };map<string, int> countMap;for (auto& str : arr){//auto it = countMap.find(str);//if (it == countMap.end())//{//	//樹中沒有,說明第一次出現//	countMap.insert(make_pair(str, 1));//}//else//{//	//樹中有,則++value(統計次數)//	it->second++;//}countMap[str]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}

程序運行結果：

在map中operator[ ]用來返回key對應的value的引用。它具有插入修改查找的功能：

void test_map3()
{map<string, string> dict;dict.insert(make_pair("left", "左邊"));dict.insert(make_pair("right", "右邊"));dict["erase"]; //插入dict["erase"] = "刪除"; //修改cout << dict["erase"] << endl; //查找dict["test"] = "測試"; //插入+修改dict["right"] = "右邊,權利"; //修改
}

程序運行結果：

🔥🔥可以通過官網簡單了解一下map的operator[ ]的實現：

后面在實現map時，會重點講解operator[ ]的實現。

3.9 multimap類的介紹

c++官網multimap類文檔：multimap
🍓multimap和map的唯一不同就是: map中的key是唯一的，而multimap中的key是可以重復的。

(1) multimap是關聯式容器，它按照特定的順序，存儲由key和value映射成的鍵值對<key,value>，其中多個鍵值對之間的key是可以重復的。
(2) 在multimap中，通常按照key排序和唯一地標識元素，而映射的value存儲與key關聯的內容。key和value的類型可能不同，通過multimap內部的成員類型value_type組合在一起value_type是組合key和value的鍵值對:
typedef pair<const Key,T> value_type;
(3) 在內部，multimap中的元素總是通過其內部比較對象，按照指定的特定嚴格弱排序標準對key進行排序的。
(4) multimap通過key訪問單個元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍歷multimap中的元素可以得到關于key有序的序列。
(5) multimap在底層用二叉搜索樹(紅黑樹)來實現。

multimap中的接口可以參考map的，功能都是類似的，這里就不再展開講解multimap的使用案例了。感興趣的同學可以參考multimap的官網進行了解。
🍋注意:🍋

1. multimap中的key是可以重復的
2. multimap中的元素默認將key按照小于來比較
3. multimap中沒有重載operator[ ]操作(思考一下為什么?)
4. 使用時與map包含的頭文件相同

上述map和set類的接口使用的代碼倉庫：Map_Set

四、關聯式容器在OJ中的使用

4.1 前K個高頻單詞

題目鏈接：Top-KFrequentWords




這道題要用到map容器，因為要統計單詞出現的次數，所以要用到key_value模型的容器。其次是要返回前K個出現次數最多的單詞，這里有點像Top_K問題，但是這里Top_K模型的堆結構解決不了這里的問題！因為題目中有一點就是：如果前K個高頻單詞中，有出現相同次數的單詞，就要按照字典順序排序。所以沒有這么簡單，解決這題的一個簡單思路就是：構造一個仿函數來定義比較的規則。

class Solution 
{struct kvCom{bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2){return kv1.second > kv2.second || ((kv1.second == kv2.second) && (kv1.first < kv2.first));}};
public:vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;for(auto& str:words){countMap[str]++;  //插入+修改}//將countMap中的元素插入到sortV中(迭代器遍歷出來的map類元素是有序的)vector<pair<string,int>> sortV(countMap.begin(),countMap.end());     sort(sortV.begin(),sortV.end(),kvCom());vector<string> v;for(size_t i = 0; i<k; i++){v.push_back(sortV[i].first);}return v;}
};

這樣將仿函數kvCom傳給sort函數，sort就會按照我們自己定義的規則進行比較排序啦。

4.2 兩個數組的交集Ⅰ

題目鏈接：IntersectionOfTwoArrays



💡這里分享一個找交集或差集的小算法：假設就拿上面的示例2來講解：


找交集或者差集在實踐中都是有應用的，比如：自動備份，同步數據(網盤同步)等其實都會用到找交集和差集。所以該題的代碼實現如下：

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());set<int>::iterator it1 = s1.begin();set<int>::iterator it2 = s2.begin();vector<int> v;while(it1 != s1.end() && it2 != s2.end()){if(*it1 < *it2){it1++;}else if(*it1 > *it2){it2++;}else{v.push_back(*it1);it1++;it2++;}}return v;}
};

結束啦！🍂🍂