💓博主CSDN主页:杭电码农-NEO💓
⏩专栏分类:C++从入门到精通⏪
🚚代码仓库:NEO的学习日记🚚
🌹关注我🫵带你学习C++
🔝🔝
map和set
- 1. 前言
- 2. map和set介绍
- 3. pair结构介绍
- 4. set结构详解
- 5. map结构详解
- 6. multimap和multiset
- 7. map和set实战演练
- 8. 总结
1. 前言
在学习了二叉搜索树后,现在
就可以来学习map和set了,虽然
它们的底层是红黑树结构,但是红黑树
的本质也是一颗二叉搜索树!
本质重点:
本篇文章着重讲解map和set的
使用方法以及一些特性,以及讲解
muti为前缀的map/set和普通map/set
的区别,其中会学到一个重要的结构
pair,它会伴随我们很久
2. map和set介绍
set是key模型,本质是确定一个
元素在不在此容器中,也就是说
set中存储的是一个单一数据
map和set的区别就是,map中存储
的并不是一个单一数据,而是存储了
一个pair结构!(后面会讲解)
map的模板参数中有key和T
而set的模板参数只有T
set和map结构中遍历出来是
数据有序并且去重的!
map和set都只支持增删查,不支持改!
3. pair结构介绍
pair结构实际上是一个键值对
以下是对于键值对的介绍:
这个类的代码大概是这样的:
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)
{}
};
它实际上就是封装了两个可以是不同
类型的数,它可以用作中英字典,存储
pair<string,string>的结构,first存储中文
second存储对应的英文解释,非常好用!
map中存储的就是pair结构,所以
map也叫存储的KV模型,因为first和
second对应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结构详解
先看set的第二个模板参数是less
是不是很熟悉?set默认情况下遍历
出来是升序,但是如果定义对象时显示
传参greater,就是降序!
set<int,greater<int>> s;
set的插入函数insert
插入我们需要关心三点:
一是插入可以不用写pos,直接插入
二是可以插入一段迭代器区间
三是插入的返回值也是一个pair结构
pair中存储了布尔类型和迭代器,分别
代表此次插入是否成功,若成功则返回
被插入元素迭代器的位置
set的查找和删除函数find,erase
5. map结构详解
set是没有支持方括号的
而map支持了,所以先讲解方括号的使用
map的方括号用法:
先看文档:
map的方括号设计的十分巧妙
它的参数的pair中的first,返回值
是pair中的second,并且它返回的是
引用,可以根据first修改second
它可以用来计数,请看如下demo代码:
统计水果的数量:
string arr[]={"苹果","西瓜","香蕉","苹果","西瓜","西瓜","西瓜","苹果"};
map<string,int> countmap;
for(auto str : arr)
{
countmap[str]++;
}
请再看文档的详细信息:
也就是说,方括号自带插入功能,当
出现第一个”西瓜”时,会自动把”西瓜”
插入到map中,第二次遇见”西瓜”时,
会将西瓜的计数++变成2
map的删除和查找:
由于map的插入在前面已经讲解过了
这里只讲解删除和查找
erase和find传参只用传pair中的first
类型的参数,即可完成任务,并且find的
返回值和set的find是一样的,一个意思
6. multimap和multiset
map和set的遍历是有序并且去重的
也就是说里面没有相同的元素,但是
STL提供了multimap和multiset
它们允许存在相同的元素!
由于支持元素冗余
所以multimap不支持方括号了!
当我们插入相同的数据时,它也会保存
7. map和set实战演练
请看下面的力扣题目:
力扣692题
大家先思考一下对策吧
题目解析:
本题目不仅仅要找出前k个高频的单词
并且还要按照字典序来排序,也就是说,
要满足两个排序的条件:字符串出现的次数
和字符串在字典中的顺序!
想到要计数,当然是用map啦!
map<string,int> mpcount;
for(auto str : words)
mpcount[str]++;
两个细节问题以及结论
-
map计数后,只需以map中的second
作为基准来排序即可得到前k个高频 -
map本身的遍历就是有序的,并且此
顺序刚好是字典序(以first排序的)
结论:只需使用一个排序算法,在不打乱
map原本排序的情况下,以map中的
second为基准排个序,即可得到我们
想要的答案,所以关键是要使用稳定
的排序算法!
库中稳定的排序算法:stable_sort
下面是所有的代码,不懂可以私信我
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. 总结
熟悉map和set的使用在平常做题
时会有大用处,虽然平时用的更多的
是unordered_map/set,但是它们的
使用方法基本一致,学到就是赚到!
文章出处登录后可见！
