当前位置: 首页 > news >正文

set和map(二)详解

文章目录

  • map
    • operator[ ]的底层
    • operator[ ]使用的实例
  • multimap
    • equal_range
  • 两道题目
    • 题目解析
    • 算法原理
    • 代码
    • 题目解析
    • 算法原理
    • 代码

map

map和set大部分都相似,只有insert插入键值对不同,insert要插入pair,pair中有key和value。erase和find只与key有关,其实insert也只与key有关,只是插入时要插入pair
在这里插入图片描述
在这里插入图片描述
删除一个pos位置,用find去找然后删除
删除一个数k,有就删除,没有也不报错
删除一段迭代器区间
在这里插入图片描述

operator[ ]的底层

mapped_type - > value
key_type->key
value_type->pair
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

  • operator[ ]支持 插入,修改,查找
  • 插入:没有的key就插入,不会报错
  • 查找:insert插入成功返回新插入值所在的迭代器
    pair<新插入值所在的迭代器,true>
    insert插入失败返回已经存在跟key相等值的迭代器
    pair<已经存在跟key相等值的迭代器,false>
  • 那么也就意味着insert插入失败时充当了查找的功能,正是因为这一点,insert可以用来实现operator[ ]
  • 需要注意的是这里有两个pair,不要混淆了,一个是map底层红黑树节点中存的pair<key, T>,另一个是insert返回值pair<iterator,bool>
int main()
{// 利⽤find和iterator修改功能,统计⽔果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){countMap[str]++;// 先查找⽔果在不在map中// 1、不在,说明⽔果第⼀次出现,则插⼊{⽔果, 1}// 2、在,则查找到的节点中⽔果对应的次数++//auto ret = countMap.find(str); 找到返回对应的位置 没找到返回end()//if (ret == countMap.end())//{//	countMap.insert({ str, 1 });//}//else//{//	ret->second++;//}}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}
// operator的内部实现
mapped_type& operator[] (const key_type& k)
{
// 1、如果k不在map中,插入+修改
// 2、如果k在map中,查找+修改
pair<iterator, bool> ret = insert({ k, mapped_type() });
iterator it = ret.first;
return it->second;
}

ret是返回值的迭代器,通过这个迭代器去修改底层红黑树的value,达到修改的效果
在这里插入图片描述

operator[ ]使用的实例

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在插入{"insert",string()}// 如果value是内置类型并且不给值,默认它的值是0// key不存在插入dict["string"];// key不存在->插入+修改dict["left"] = "左边";// key存在修改dict["left"] = "右边";// key存在查找,只有存在才能这么用,否则就是插入了cout << dict["left"] << endl;// 插入,因为right不存在cout << dict["right"] << endl;return 0;
}

multimap

允许插入相同的key,find查找的是中序的第一个,erase从中序的第一个开始删除(一直++),multimap不支持operator[ ],因为有多个相同的key,不知道用哪个

int main()
{multimap<string, string> dict;dict.insert({ "string","字符串1" });dict.insert({ "string", "字符串2" });dict.insert({"string", "字符串3"});dict.insert({ "string", "字符串4" });dict.insert({ "string", "字符串" });dict.insert({ "sort", "排序" });dict.erase("string");return 0;
}

在这里插入图片描述

equal_range

找一段相等值的迭代器区间
在这里插入图片描述
[ )左闭右开的区间去找
在这里插入图片描述
在这里插入图片描述

两道题目

题目解析

题目链接
在这里插入图片描述

算法原理

  • 建立这整个节点和拷贝出来的节点的映射关系,cur-copytail
    思路:先将原链表拷贝一份放入新的链表中,在这其中也建立cur节点和拷贝链表的映射关系(nodeMap[cur] = copytail)
    然后开一个新的指针遍历链表,将random指针进行链接,copy->random = nodeMap[cur->random]

代码

class Solution 
{
public:Node* copyRandomList(Node* head) {// val和next,random这个节点是key,copytail是value// 构建key-value的映射关系map<Node*,Node*> nodeMap;Node* copytail = nullptr;Node* copyhead = nullptr;Node* cur = head;    while(cur){if(copytail == nullptr){copyhead = copytail = new Node(cur->val);}else{copytail->next = new Node(cur->val);copytail = copytail->next;}// 建立映射关系 k-valuenodeMap[cur] = copytail;cur = cur->next;}cur = head;Node* copy = copyhead;while(cur){if(cur->random == nullptr){copy->random = nullptr;}else{copy->random = nodeMap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};

题目解析

题目链接
在这里插入图片描述

算法原理

pair比较的是first,second,其中一个小就小,先比较的是first,相等是两个相等才相等
map比较的是string的字典序,sort比较的是出现次数

代码

class Solution 
{
public:struct Compare{bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2){return kv1.second > kv2.second;}// bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2)// {//     return kv1.second > kv2.second||(kv1.second == kv2.second&&kv1.first < kv2.first);// }};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;// 字典序排序 + 统计次数for(auto& s : words){countMap[s]++;}vector<pair<string,int>> v(countMap.begin(),countMap.end());// 仿函数比较实现次数的降序// sort排序是不稳定的stable_sort(v.begin(),v.end(),Compare());//  sort(v.begin(),v.end(),Compare());vector<string> ret;for(int i = 0;i < k;i++){ret.push_back(v[i].first);}return ret;}
};
http://www.lryc.cn/news/525232.html

相关文章:

  • 第4章:Python TDD消除重复与降低依赖实践
  • 【语言处理和机器学习】概述篇(基础小白入门篇)
  • vue3+uniapp开发鸿蒙初体验
  • Android四种方式刷新View
  • 【数学建模美赛速成系列】O奖论文绘图复现代码
  • 【27】Word:徐雅雯-艺术史文章❗
  • web端ActiveMq测试工具
  • 2025年最新深度学习环境搭建:Win11+ cuDNN + CUDA + Pytorch +深度学习环境配置保姆级教程
  • FPGA中场战事
  • [Computer Vision]实验二:图像特征点提取
  • TCP状态转移图详解
  • curl简介与libcurl开源库的使用总结
  • Win10系统部署RabbitMQ Server
  • uniapp APP端页面触发调用webview(页面为uniapp开发的H5)里的方法
  • 嵌入式知识点总结 C/C++ 专题提升(七)-位操作
  • 新星杯-ESP32智能硬件开发--ESP32的I/O组成
  • 航空航天混合动力(7)航空航天分布式电推进系统
  • AIGC视频生成明星——Emu Video模型
  • Cyber Security 101-Security Solutions-Firewall Fundamentals(防火墙基础)
  • 备赛蓝桥杯之第十五届职业院校组省赛第一题:智能停车系统
  • Docker核心命令与Yocto项目的高效应用
  • idea plugin插件开发——入门级教程(IntelliJ IDEA Plugin)
  • 61,【1】BUUCTF WEB BUU XSS COURSE 11
  • 开发环境搭建-1:配置 WSL (类 centos 的 oracle linux 官方镜像)
  • Spring Boot MyBatis Plus 版本兼容问题(记录)
  • 26. 【.NET 8 实战--孢子记账--从单体到微服务】--需求更新--用户注销、修改用户名、安全设置
  • 神经网络|(一)加权平均法,感知机和神经元
  • OpenHarmony OTA升级参考资料记录
  • 在 Kubernetes 上快速安装 KubeSphere v4.1.2
  • 【回忆迷宫——处理方法+DFS】