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

这篇具有很好参考价值的文章主要介绍了【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:C++从入门到精通⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你学习C++
  🔝🔝


【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

1. 前言

在学习了二叉搜索树后,现在
就可以来学习map和set了,虽然
它们的底层是红黑树结构,但是红黑树
的本质也是一颗二叉搜索树!

本质重点:

本篇文章着重讲解map和set的
使用方法以及一些特性,以及讲解
muti为前缀的map/set和普通map/set
的区别,其中会学到一个重要的结构
pair,它会伴随我们很久


2. map和set介绍

set是key模型,本质是确定一个
元素在不在此容器中,也就是说
set中存储的是一个单一数据

map和set的区别就是,map中存储
的并不是一个单一数据,而是存储了
一个pair结构!(后面会讲解)

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

map的模板参数中有key和T
而set的模板参数只有T

set和map结构中遍历出来是
数据有序并且去重的!

map和set都只支持增删查,不支持改!


3. pair结构介绍

pair结构实际上是一个键值对
以下是对于键值对的介绍:

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

这个类的代码大概是这样的:

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结构详解

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

先看set的第二个模板参数是less
是不是很熟悉?set默认情况下遍历
出来是升序,但是如果定义对象时显示
传参greater,就是降序!

set<int,greater<int>> s;

set的插入函数insert
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

插入我们需要关心三点:
一是插入可以不用写pos,直接插入
二是可以插入一段迭代器区间
三是插入的返回值也是一个pair结构
pair中存储了布尔类型和迭代器,分别
代表此次插入是否成功,若成功则返回
被插入元素迭代器的位置

set的查找和删除函数find,erase
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构


5. map结构详解

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

set是没有支持方括号的
而map支持了,所以先讲解方括号的使用

map的方括号用法:
先看文档:
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

map的方括号设计的十分巧妙
它的参数的pair中的first,返回值
是pair中的second,并且它返回的是
引用,可以根据first修改second
它可以用来计数,请看如下demo代码:

统计水果的数量:

string arr[]={"苹果","西瓜","香蕉","苹果","西瓜","西瓜","西瓜","苹果"};
map<string,int> countmap;
for(auto str : arr)
{
	countmap[str]++;
}

请再看文档的详细信息:

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

也就是说,方括号自带插入功能,当
出现第一个"西瓜"时,会自动把"西瓜"
插入到map中,第二次遇见"西瓜"时,
会将西瓜的计数++变成2

map的删除和查找:
由于map的插入在前面已经讲解过了
这里只讲解删除和查找

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

erase和find传参只用传pair中的first
类型的参数,即可完成任务,并且find的
返回值和set的find是一样的,一个意思


6. multimap和multiset

map和set的遍历是有序并且去重的
也就是说里面没有相同的元素,但是
STL提供了multimap和multiset
它们允许存在相同的元素!

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

由于支持元素冗余
所以multimap不支持方括号了!

当我们插入相同的数据时,它也会保存

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构


7. map和set实战演练

请看下面的力扣题目:

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

力扣692题

大家先思考一下对策吧

题目解析:

本题目不仅仅要找出前k个高频的单词
并且还要按照字典序来排序,也就是说,
要满足两个排序的条件:字符串出现的次数
和字符串在字典中的顺序!

想到要计数,当然是用map啦!

map<string,int> mpcount;
for(auto str : words)
	mpcount[str]++;

两个细节问题以及结论

  • map计数后,只需以map中的second
    作为基准来排序即可得到前k个高频

  • map本身的遍历就是有序的,并且此
    顺序刚好是字典序(以first排序的)

结论:只需使用一个排序算法,在不打乱
map原本排序的情况下,以map中的
second为基准排个序,即可得到我们
想要的答案,所以关键是要使用稳定
的排序算法!

库中稳定的排序算法:stable_sort

【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构,C++从入门到精通,c++,开发语言,数据结构

下面是所有的代码,不懂可以私信我

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,但是它们的
使用方法基本一致,学到就是赚到!文章来源地址https://www.toymoban.com/news/detail-754635.html


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

到了这里,关于【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++高级编程——STL:list容器、set容器和map容器

    本专栏记录C++学习过程包括C++基础以及数据结构和算法,其中第一部分计划时间一个月,主要跟着黑马视频教程,学习路线如下, 不定时更新,欢迎关注 。 当前章节处于: ---------第1阶段-C++基础入门 ---------第2阶段实战-通讯录管理系统, ---------第3阶段-C++核心编程, -----

    2024年01月25日
    浏览(44)
  • 【C++】STL——用一颗红黑树封装出map和set

    我们都知道set是K模型的容器,而map是KV模型的容器,但是它俩的底层都是用红黑树实现的,上篇博文中我们模拟实现了一颗红黑树,接下来将对其进行改造,继而用一颗红黑树封装出map和set。 本质上map和set其内部的主要功能都是套用了红黑树现成的接口,只是稍作改动即可

    2023年04月15日
    浏览(32)
  • 【C++练级之路】【Lv.17】【STL】set类和map类的模拟实现

    快乐的流畅:个人主页 个人专栏:《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火,在为久候之人燃烧! STL库中的set类和map类,其底层原理都是 通过红黑树来实现 的。尽管set和map可以各自实现一棵红黑树,但是为了提高代码的复用率,STL库中将红黑树进行了一定

    2024年04月16日
    浏览(36)
  • C++:stl中set(multiset)和map(multimap)的介绍和使用

    本文主要从概念、常用接口和使用方法方面介绍set(multiset)和map(multimap)。 目录 一、概念介绍 1.关联式容器 2.键值对 3. 树形结构的关联式容器 二、set和multiset 1.set的介绍 2.set使用 1. set模板参数列表 2. set构造 3. set迭代器 4. set容量 5. set修改操作 6.set使用举例 3.multiset介绍 4.mul

    2024年02月08日
    浏览(39)
  • 【C++进阶04】STL中map、set、multimap、multiset的介绍及使用

    vector/list/deque… 这些容器统称为 序列式容器 因为其底层为线性序列的数据结构 里面存储的是元素本身 map/set… 这些容器统称为 关联式容器 关联式容器也是用来存储数据的 与序列式容器不同的是 其里面存储的是key, value结构的键值对 在数据检索时比序列式容器效率更高 “键

    2024年02月03日
    浏览(46)
  • 【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]

    欢迎各位大佬们的关顾,本文将介绍unordered系列容器以及其中的两个重要成员: unordered_map 和 unordered_set 。unordered_map是一种无序的关联容器,它使用哈希表来存储键值对,并提供高效的插入、查找和删除操作。在本文中,我们将首先介绍unordered_map的基本概念和特点,然后详

    2024年02月08日
    浏览(42)
  • 【C++】STL——用一个哈希表封装出unordered_map和unordered_set

    根据先前对unordered_map和unordered_set的学习,我们得知其底层是借助哈希表来实现的,接下来我们会使用上篇博客实现的开散列哈希表来模拟实现unordered_map和unordered_set,哈希表源代码链接: Hash/Hash/HashBucket.h · wei/cplusplus - 码云 - 开源中国 (gitee.com) 下面我们对哈希表进行改造,

    2023年04月18日
    浏览(46)
  • 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题

    更多算法例题链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 什么是迭代器(iterator) 迭代器(iterator)的定义: 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。 容器

    2024年04月14日
    浏览(48)
  • 【高阶数据结构】封装Map和Set

    (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是 Scort 目前状态:大三非科班啃C++中 🌍博客主页:张小姐的猫~江湖背景 快上车🚘,握好方向盘跟我有一起打天下嘞! 送给自己的一句鸡汤🤔: 🔥真正的大师永远怀着一颗学徒的心 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏 🎉🎉

    2024年01月20日
    浏览(47)
  • 【高阶数据结构】Map 和 Set(详解)

    (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是 Scort 目前状态:大三非科班啃C++中 🌍博客主页:张小姐的猫~江湖背景 快上车🚘,握好方向盘跟我有一起打天下嘞! 送给自己的一句鸡汤🤔: 🔥真正的大师永远怀着一颗学徒的心 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏 🎉🎉

    2024年01月23日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包