??博主CSDN主頁:杭電碼農(nóng)-NEO??
?
?專欄分類:C++從入門到精通?
?
??代碼倉庫:NEO的學(xué)習(xí)日記??
?
??關(guān)注我??帶你學(xué)習(xí)C++
? ????
1. 前言
在學(xué)習(xí)了二叉搜索樹后,現(xiàn)在
就可以來學(xué)習(xí)map和set了,雖然
它們的底層是紅黑樹結(jié)構(gòu),但是紅黑樹
的本質(zhì)也是一顆二叉搜索樹!
本質(zhì)重點(diǎn):
本篇文章著重講解map和set的
使用方法以及一些特性,以及講解
muti為前綴的map/set和普通map/set
的區(qū)別,其中會學(xué)到一個重要的結(jié)構(gòu)
pair,它會伴隨我們很久
2. map和set介紹
set是key模型,本質(zhì)是確定一個
元素在不在此容器中,也就是說
set中存儲的是一個單一數(shù)據(jù)
map和set的區(qū)別就是,map中存儲
的并不是一個單一數(shù)據(jù),而是存儲了
一個pair結(jié)構(gòu)!(后面會講解)
map的模板參數(shù)中有key和T而set的模板參數(shù)只有T
set和map結(jié)構(gòu)中遍歷出來是
數(shù)據(jù)有序并且去重的!
map和set都只支持增刪查,不支持改!
3. pair結(jié)構(gòu)介紹
pair結(jié)構(gòu)實(shí)際上是一個鍵值對
以下是對于鍵值對的介紹:
這個類的代碼大概是這樣的:
template <class T1, class T2>
struct pair
{
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};
它實(shí)際上就是封裝了兩個可以是不同
類型的數(shù),它可以用作中英字典,存儲
pair<string,string>的結(jié)構(gòu),first存儲中文
second存儲對應(yīng)的英文解釋,非常好用!
map中存儲的就是pair結(jié)構(gòu),所以map也叫存儲的KV模型,因?yàn)閒irst和second對應(yīng)key和value
map的三種常見使用方法:
1. 方法一: 定義pair對象后插入
map<string,string> dict;
pair<string,string> kv1("排序","sort");
pair<string,string> kv2("左邊","left");
dict.insert(kv1);
dict.insert(kv2);
2. 方法二: 使用匿名對象插入
map<string,string> dict;
dict.insert(pair<string,string>("排序","sort"));
dict.insert(pair<string,string>("左邊","left"));
3. 方法三: 使用make_pair插入
map<string,string> dict;
dict.insert(make_pair("排序","sort"));
dict.insert(make_pair("左邊","left"));
make_pair是最好用的方法!
4. set結(jié)構(gòu)詳解
先看set的第二個模板參數(shù)是less
是不是很熟悉?set默認(rèn)情況下遍歷
出來是升序,但是如果定義對象時顯示
傳參greater,就是降序!
set<int,greater<int>> s;
set的插入函數(shù)insert
插入我們需要關(guān)心三點(diǎn):
一是插入可以不用寫pos,直接插入
二是可以插入一段迭代器區(qū)間
三是插入的返回值也是一個pair結(jié)構(gòu)
pair中存儲了布爾類型和迭代器,分別
代表此次插入是否成功,若成功則返回
被插入元素迭代器的位置
set的查找和刪除函數(shù)find,erase
5. map結(jié)構(gòu)詳解
set是沒有支持方括號的
而map支持了,所以先講解方括號的使用
map的方括號用法:先看文檔:
map的方括號設(shè)計(jì)的十分巧妙
它的參數(shù)的pair中的first,返回值
是pair中的second,并且它返回的是
引用,可以根據(jù)first修改second
它可以用來計(jì)數(shù),請看如下demo代碼:
統(tǒng)計(jì)水果的數(shù)量:
string arr[]={"蘋果","西瓜","香蕉","蘋果","西瓜","西瓜","西瓜","蘋果"};
map<string,int> countmap;
for(auto str : arr)
{
countmap[str]++;
}
請?jiān)倏次臋n的詳細(xì)信息:
也就是說,方括號自帶插入功能,當(dāng)
出現(xiàn)第一個"西瓜"時,會自動把"西瓜"
插入到map中,第二次遇見"西瓜"時,
會將西瓜的計(jì)數(shù)++變成2
map的刪除和查找:由于map的插入在前面已經(jīng)講解過了這里只講解刪除和查找
erase和find傳參只用傳pair中的first
類型的參數(shù),即可完成任務(wù),并且find的
返回值和set的find是一樣的,一個意思
6. multimap和multiset
map和set的遍歷是有序并且去重的
也就是說里面沒有相同的元素,但是
STL提供了multimap和multiset
它們允許存在相同的元素!
由于支持元素冗余所以multimap不支持方括號了!
當(dāng)我們插入相同的數(shù)據(jù)時,它也會保存
7. map和set實(shí)戰(zhàn)演練
請看下面的力扣題目:
力扣692題
大家先思考一下對策吧
題目解析:
本題目不僅僅要找出前k個高頻的單詞
并且還要按照字典序來排序,也就是說,
要滿足兩個排序的條件:字符串出現(xiàn)的次數(shù)
和字符串在字典中的順序!
想到要計(jì)數(shù),當(dāng)然是用map啦!
map<string,int> mpcount;
for(auto str : words)
mpcount[str]++;
兩個細(xì)節(jié)問題以及結(jié)論
-
map計(jì)數(shù)后,只需以map中的second
作為基準(zhǔn)來排序即可得到前k個高頻 -
map本身的遍歷就是有序的,并且此
順序剛好是字典序(以first排序的)
結(jié)論:只需使用一個排序算法,在不打亂
map原本排序的情況下,以map中的
second為基準(zhǔn)排個序,即可得到我們
想要的答案,所以關(guān)鍵是要使用穩(wěn)定
的排序算法!
庫中穩(wěn)定的排序算法:stable_sort
下面是所有的代碼,不懂可以私信我文章來源：http://www.zghlxwxcb.cn/news/detail-754635.html
class Solution {
public:
struct _compare
{
bool operator()(pair<string,int> p1,pair<string,int> p2)
{
return p1.second>p2.second;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string,int> mpcount;
for(auto str : words)
mpcount[str]++;
vector<pair<string,int>> tmp;
auto it = mpcount.begin();
while(it!=mpcount.end())
{
tmp.push_back(*it);
it++;
}
_compare com;
vector<string> ret;
stable_sort(tmp.begin(),tmp.end(),com);
for(int i=0;i<k;i++)
ret.push_back(tmp[i].first);
return ret;
}
};
8. 總結(jié)
熟悉map和set的使用在平常做題
時會有大用處,雖然平時用的更多的
是unordered_map/set,但是它們的
使用方法基本一致,學(xué)到就是賺到!文章來源地址http://www.zghlxwxcb.cn/news/detail-754635.html
到了這里，關(guān)于【C++高階(二)】熟悉STL中的map和set --了解KV模型和pair結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【C++入門到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入門 ]](https://imgs.yssmx.com/Uploads/2024/02/714971-1.jpeg)
