【C++高阶(二)】熟悉STL中的map和set –了解KV模型和pair结构

💓博主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 
struct pair
{
	T1 first;
	T2 second;
	pair(): first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b): first(a), second(b)
	{}
};

它实际上就是封装了两个可以是不同

类型的数,它可以用作中英字典,存储

pair的结构,first存储中文

second存储对应的英文解释,非常好用!

map中存储的就是pair结构,所以

map也叫存储的KV模型,因为first和

second对应key和value

map的三种常见使用方法:

1. 方法一: 定义pair对象后插入

map dict;
pair kv1("排序","sort");
pair kv2("左边","left");
dict.insert(kv1);
dict.insert(kv2);

2. 方法二: 使用匿名对象插入

map dict;
dict.insert(pair("排序","sort"));
dict.insert(pair("左边","left"));

3. 方法三: 使用make_pair插入

map dict;
dict.insert(make_pair("排序","sort"));
dict.insert(make_pair("左边","left"));

make_pair是最好用的方法!

4. set结构详解

先看set的第二个模板参数是less

是不是很熟悉?set默认情况下遍历

出来是升序,但是如果定义对象时显示

传参greater,就是降序!

set<int,greater> 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 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 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 p1,pair p2)
        {
            return p1.second>p2.second;
        }
    };
    vector topKFrequent(vector& words, int k) {
        map mpcount;
        for(auto str : words)
            mpcount[str]++;
        vector<pair> tmp;
        auto it = mpcount.begin();
        while(it!=mpcount.end())
        {
            tmp.push_back(*it);
            it++;
        }
        _compare com;
        vector 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,但是它们的

使用方法基本一致,学到就是赚到!

🔎
下期预告:AVL树深度剖析 🔍