目錄

關(guān)聯(lián)式容器

概念

鍵值對

樹形關(guān)聯(lián)式容器

set

介紹

定義方式

使用

map

介紹

使用

?multiset

介紹

使用

multimap

介紹

使用

相關(guān)的OJ題

前K個高頻單詞

---

關(guān)聯(lián)式容器

概念

我們之前接觸過的一些容器，比如：vector、list、deque、forward_list(C++11)等，這些容器統(tǒng)稱為序列式容器，因為其底層為線性序列的數(shù)據(jù)結(jié)構(gòu)，里面存儲的是元素本身。
關(guān)聯(lián)式容器也是用來存儲數(shù)據(jù)的，與序列式容器不同的是，其里面存儲的是<key, value>結(jié)構(gòu)的鍵值對，在數(shù)據(jù)檢索時比序列式容器效率更高。
?

鍵值對

鍵值對是關(guān)聯(lián)式容器特殊的結(jié)構(gòu)。

SGI-STL中關(guān)于鍵值對的定義：

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

樹形關(guān)聯(lián)式容器

map、set、multimap、multiset。這些都是樹形關(guān)聯(lián)式容器，因為他們的底層都是平衡搜索樹（紅黑樹），容器中的元素都是有序的。

set

介紹

1. set是按照一定次序存儲元素的容器。
2. 在set中，元素的value也標(biāo)識它，并且每個value必須是唯一的。set中的元素不能在容器中修改（元素總是const，因為底層是平衡二叉樹，如果修改可能會破壞平衡二叉樹的性質(zhì)）。
3. 在內(nèi)部，set中的元素總是按照其內(nèi)部比較對象（類型比較）所指示的特定嚴格弱排序準則進行排序。
4. set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據(jù)順序?qū)ψ蛹M行直接迭代。
5. set在底層使用平衡二叉樹（紅黑樹）實現(xiàn)的。
6. 與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key,value>，set中只放value，但在底層實際存放的是由<value,value>構(gòu)成的鍵值對。
7. set中插入元素時，只需要插入value即可，不需要構(gòu)造鍵值對。
8. set中的元素不可以重復(fù)（因此可以使用set進行去重，不可以重復(fù)的原因也是底層是平衡二叉樹）。
9. 使用set中的元素默認按照小于來比較。
10. set中查找某個元素，時間復(fù)雜度為：log2 n
11. set中的元素不允許修改（因為底層是平衡二叉樹，如果修改的話很可能會破壞平衡二叉樹的結(jié)構(gòu)）。

注意：平衡二叉樹（AVL）是一種特殊的搜索二叉樹（BST）；

定義方式

//構(gòu)造空容器
set<int> s1;//拷貝構(gòu)造set容器
set<int> s2(s1);//使用迭代器拷貝某一段內(nèi)容
string str("abcdef");
set<char> s3(str.begin(),str.end());//比較方式指定為大于
set<int,greater<int>> s4;

使用

?Compare：比較容器，set默認按照小于來比較，如果要對自定義類型進行比較的時候可以傳入自定義的比較容器。

詳細見代碼：

void test_set1()
{set<int> s;//插入s.insert(3);s.insert(2);s.insert(1);s.insert(1);s.insert(6);s.insert(7);s.insert(4);//利用迭代器去遍歷set//set<int>::iterator it = s.begin();auto it = s.begin();while (it != s.end()){cout << *it << " ";it++;}cout << endl;//利用范圍for去遍歷for (auto e : s){cout << e << " ";}cout << endl;//查找->找到就返回該元素的迭代器 否則返回end//兩種find的查找方式是不一樣的//O(logN) 這個是根據(jù)樹的特殊結(jié)構(gòu)來查找的auto pos = s.find(3);//O(N) 暴力查找//auto pos = find(s.begin(), s.end(), 3);if (pos != s.end()){s.erase(pos);}//刪除 //有就刪沒有就不操作//s.erase(4)像這種是有返回值的//刪除成功就返回1刪除失敗返回0cout << s.erase(4) << endl;cout << s.erase(100) << endl;for (auto e : s){cout << e << " ";}cout << endl;//count 返回該值在set里面的個數(shù)//其實count對set意義不大//但是對multiset意義更大//cout << s.count(3) << endl;}

注意：這里只列舉一些常用的set的操作。

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)為平衡二叉搜索樹（紅黑樹）。

使用

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

int main()
{//定義一個空容器map<string, string> dict;//插入key和valuedict.insert(pair<string, string>("排序", "sort"));dict.insert(pair<string, string>("左邊", "left"));dict.insert(pair<string, string>("右邊", "right"));//operator[]dict["迭代器"] = "iterator";//插入+修改dict["insert"];//插入dict["insert"] = "插入";//修改cout << dict["insert"] << endl;//查找，如果不在就是插入//插入失敗因為已經(jīng)有key對應(yīng)的值了//dict.insert(pair<string, string>("右邊", "xxx"));//make_pair是一個函數(shù)模板 可以根據(jù)你傳入的值來推斷具體的類型dict.insert(make_pair("字符串", "string"));//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;it++;}cout << endl;for (const auto& kv : dict){cout << kv.first << ": " << kv.second << endl;}//可以用來統(tǒng)計次數(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));//第一次遇見這個水果直接給對應(yīng)的key的value值插入1}else{it->second++;}}//用for循環(huán)進行遍歷for (const auto& kv : countMap){cout << kv.first << ": " << kv.second << endl;}return 0;
}

注意：map是支持[]操作符的。

operator[]的原理是：

用<key, T()>構(gòu)造一個鍵值對，然后調(diào)用insert()函數(shù)將該鍵值對插入到map中如果key已經(jīng)存在，插入失敗，insert函數(shù)返回該key所在位置的迭代器如果key不存在，插入成功，insert函數(shù)返回新插入元素所在位置的迭代器operator[]函數(shù)最后將insert返回值鍵值對中的value返回。
?

?multiset

介紹

1. multiset是按照特定順序存儲元素的容器，其中元素是可以重復(fù)的。
2. 在multiset中，元素的value也會識別它(因為multiset中本身存儲的就是<value, value>組成的鍵值對，因此value本身就是key，key就是value，類型為T). multiset元素的值不能在容器中進行修改(因為元素總是const的)，但可以從容器中插入或刪除。
3. 在內(nèi)部，multiset中的元素總是按照其內(nèi)部比較規(guī)則（類型比較）所指示的特定嚴格弱排序準則進行排序。
4. multiset底層結(jié)構(gòu)是一個平衡二叉樹（紅黑樹）。
5. 與set的區(qū)別是，multiset中的元素是可以重復(fù)的，set中value是唯一的。

使用

void test_set2()
{multiset<int> s;//插入 可以插入重復(fù)的值s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(3);s.insert(3);s.insert(3);s.insert(3);s.insert(3);s.insert(6);s.insert(7);s.insert(1);//set<int>::iterator it = s.begin();auto it = s.begin();while (it != s.end()){cout << *it << " ";it++;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;//注意：//用來驗證，如果有多個相同的值的時候//find找到是中序遍歷的第一個auto pos = s.find(3);while (pos != s.end()){cout << *pos << " ";pos++;}//兩種find的查找方式是不一樣的//O(logN)//auto pos = s.find(3);//O(N)/*auto pos = find(s.begin(), s.end(), 3);if (pos != s.end()){s.erase(pos);}*///有就刪沒有就不操作//s.erase(4)像這種是有返回值的//刪除成功就返回1刪除失敗返回0/*cout << s.erase(4) << endl;cout << s.erase(100) << endl;for (auto e : s){cout << e << " ";}cout << endl;*///count 返回該值在set里面的個數(shù)//其實count對set意義不大//但是對multiset意義更大cout << s.count(3) << endl;cout << s.count(1) << endl;
}

注意：multiset的find與set有所不同，由于multiset中允許鍵值冗余，所以multiset如果查找成功的話返回的是中序遍歷該元素所出現(xiàn)的第一次的迭代器。

set中的count沒什么意義，但是在multiset中count非常有意義，它能很好的計算出該元素在multiset容器中的具體數(shù)量。

multimap

介紹

multimap與set和multiset的區(qū)別非常相像，在這里不多介紹。

multimap不支持[]，因為multimap允許鍵值冗余，[]不能確切的知道我們要訪問的是哪個值。

multimap中的key是可以重復(fù)的。

使用

int main()
{multimap<string, string> dict;dict.insert(make_pair<string, string>("left", "左邊"));dict.insert(make_pair<string, string>("left", "左邊"));dict.insert(make_pair<string, string>("right", "右邊"));dict.insert(make_pair("string", "字符串"));for (const auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}
}

相關(guān)的OJ題

前K個高頻單詞

題目地址：

力扣https://leetcode.cn/problems/top-k-frequent-words/description/

?我們這里使用multimap非常契合，我們的思路就是，首先使用multimap特殊的性質(zhì)（允許鍵值冗余，并且有兩個鍵值）。兩個鍵值，一個存放單詞，一個存放次數(shù)。

記錄完畢數(shù)據(jù)之后使用次數(shù)進行排序，如果有相同的就設(shè)置特殊的比較容器具進行字典序排序。

最后輸出前十個。

class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k){//為stable_sort來創(chuàng)建比較容器struct Compare{bool operator()(const pair<int,string>&l,const pair<int,string>& r){return l.first>r.first;}};map<string,int> mapCount;//巧妙的使用了[] //不僅將words中的單詞給插入進map并且還統(tǒng)計了次數(shù)for(auto& kv: words){mapCount[kv]++;//訪問key對應(yīng)的value給value進行++}vector<pair<int,string>> v;//注意這里value與key換了位置為了保證排序的時候直接使用第一個鍵值進行排序for(auto& kv : mapCount){v.push_back(make_pair(kv.second,kv.first));}//切記不要使用sort 因為sort底層為快排（不穩(wěn)定）//然而stable_sort底層為歸并（穩(wěn)定）stable_sort(v.begin(),v.end(),Compare());vector<string> ret;for(size_t i=0;i<k;i++){ret.push_back(v[i].second);}return ret;}
};