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

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

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,但是它们的

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


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


相关文章
|
3月前
|
存储 缓存 JavaScript
Set和Map有什么区别?
Set和Map有什么区别?
262 1
|
4月前
|
存储 JavaScript 前端开发
for...of循环在遍历Set和Map时的注意事项有哪些?
for...of循环在遍历Set和Map时的注意事项有哪些?
265 121
|
7月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
177 2
|
4月前
|
存储 C++ 容器
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器,其允许通过键值快速的索引到对应的元素。在unordered_set中,元素的值同时也是唯一地标识它的key。在内部,unordered_set中的元素没有按照任何特定的顺序排序,为了能在常数范围内找到指定的key,unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快,但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
184 0
|
4月前
|
编译器 C++ 容器
用一棵红黑树同时封装出map和set
再完成上面的代码后,我们的底层代码已经完成了,这时候已经是一个底层STL的红黑树了,已经已符合库里面的要求了,这时候我们是需要给他穿上对应的“衣服”,比如穿上set的“衣服”,那么这个穿上set的“衣服”,那么他就符合库里面set的要求了,同样map一样,这时候我们就需要实现set与map了。因此,上层容器map需要向底层红黑树提供一个仿函数,用于获取T当中的键值Key,这样一来,当底层红黑树当中需要比较两个结点的键值时,就可以通过这个仿函数来获取T当中的键值了。我们就可以使用仿函数了。
47 0
|
4月前
|
存储 编译器 容器
set、map、multiset、multimap的介绍及使用以及区别,注意事项
set是按照一定次序存储元素的容器,使用set的迭代器遍历set中的元素,可以得到有序序列。set当中存储元素的value都是唯一的,不可以重复,因此可以使用set进行去重。set默认是升序的,但是其内部默认不是按照大于比较,而是按照小于比较。set中的元素不能被修改,因为set在底层是用二叉搜索树来实现的,若是对二叉搜索树当中某个结点的值进行了修改,那么这棵树将不再是二叉搜索树。
202 0
|
8月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
4月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
95 0
|
4月前
|
存储 编译器 程序员
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
173 0