C++——map和set的基本使用

news/2024/2/23 14:52:02/文章来源:https://blog.csdn.net/aaqq800520/article/details/135504119

目录

一,关联式容器

二,键值对

三,set的使用

3.1 set介绍

3.2 set的插入和删除

3.3 set的pair

3.4 multiset

四,map的使用

4.1 map介绍

4.2 map实现简易字典

 4.3 map实现统计次数

4.4 map的[]

五,使用map或set解决部分OJ题

5.1 复杂链表的复制

5.2 前K个高频单词

5.2.1 解法一:使用sort算法排序

5.2.2 使用multimap解决

 5.2.3 使用set的特性加仿函数解决

 5.3 两个数组的交集


一,关联式容器

在前面的文章里,我们以及接触过STL的部分容器,包括:vector,list,deque等,这些容器同称为序列式容器,因为其底层为线性序列的数据结构,里面存的是元素本身。

关联式容器也是用来存储数据的,与序列式容器不同,里面存储的式<key,value>结构的键值对,在数据检索时比序列式容器效率更高,关于键值对请看下面的内容

二,键值对

键值对是用来表示居于一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value。key代表监事,value表示与key对应的信息。比如建一个英汉互译的字典,所以这个字典中,英语单词与其含义是一一对应的关系,即通过该单词可以在字典中找到对应的中文含义

下面是STL中关于键值对pair的定义

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()){}pair(const T1& a, const T2& b) : first(a), second(b){}
};

三,set的使用

3.1 set介绍

①set是按照一定次序存储元素的容器

②在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的

③在内部,set中的元素总是按照其内部比较对象所指示的特点排序准则进行排序

④set在底层是用红黑树实现的

3.2 set的插入和删除

void test_set1()
{//set<int> s = {1,2,1,6,3,8,5};//列表初始化int a[] = { 1,2,1,6,3,8,5 };set<int> s(a, a + sizeof(a) / sizeof(int));//set支持通过迭代器区间初始化//set<int,greater<int>> s(a, a + sizeof(a) / sizeof(int));可以自行控制这颗树//set间接完成了  排序+去重,因为set底层是一个搜索二叉树set<int>::iterator it = s.begin();while (it != s.end()){//搜索树不允许修改key,可能会破坏搜索的规则//*it += 1;cout << *it << " ";it++;}cout << endl;//删除//方法1s.erase(1);for (auto e : s){cout << e << " ";}cout << endl;//方法2set<int>::iterator pos = s.find(2);if (pos != s.end())//判断有没有找到{s.erase(pos);}for (auto e : s){cout << e << " ";}cout << endl;//count()返回数据个数,但由于set默认去重只能返回0或1,所以一般用作判断该数是否存在cout << s.count(3) << endl;  //判断在不在,并且返回个数cout << s.count(30) << endl;
}

 

void test_set2()
{set<int> myset;set<int>::iterator itlow, itup;for (int i = 0; i < 10; i++)myset.insert(i * 10);  //10 20 30 40 50 60 70 80 90itlow = myset.lower_bound(25);//返回的是>=val的第一个值,此处返回30itup = myset.upper_bound(60);//返回的是>val的第一个值,此处返回70cout << "[" << *itlow << "," << *itup << "]" << endl;myset.erase(itlow, itup);//删除这两个值所代表的范围之间的数
}

 

3.3 set的pair

void test_set3()//pair用来记录一对数据
{set<int> myset;for (int i = 1; i <= 5; i++)myset.insert(i * 10);//10 20 30 40 50 pair<set<int>::const_iterator, set<int>::const_iterator> ret;ret = myset.equal_range(40);cout << "the lower bound points to : " << *ret.first << endl;cout << "the upper bound points to : " << *ret.second << endl;
}

 

3.4 multiset

void test_multiset()//multiset与set不一样的是,multiset允许有重复值
{int a[] = { 3,1,2,1,6,3,8,3,5,3,1 };multiset<int> s(a, a + sizeof(a) / sizeof(int));for (auto e : s){cout << e << " ";}cout << endl;cout << s.count(1) << endl;//这里的count就是记录个数了auto pos = s.find(3);//find时如果有多个值,返回中序的第一个位置,如果想找第二个3,把迭代器++一下就是第二个3while (pos != s.end()){cout << *pos << " ";++pos;}cout << endl;s.erase(3);//如果要删除的值有多个,删除所有的值for (auto e : s){cout << e << " ";}
}

四,map的使用

4.1 map介绍

①map是关联容器,它按照特点的次序(按照key来比较)存储由简直key和value组合而成的元素

②在map中,键值key通常用于排序和唯一的标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair

③在内部,map中的元素总是按照键值key进行比较排序的

④map支持下标访问符,即在[]中放入key,就可以找到与key对应的value

4.2 map实现简易字典

void test_map1()
{map<string, string> dict;pair<string, string> kv1("sort","排序");//隐式类型转换dict.insert(kv1);//但是上面有点麻烦,所以这时候“匿名对象”就排上用场了dict.insert(pair<string, string>("test", "测试"));dict.insert(pair<string, string>("string", "字符串"));typedef pair<string, string> DictkV;dict.insert(DictkV("string", "xxx"));//只看king相不相同,所以这里不用xxx替换“字符串”,king已经有了,所以直接插入失败//大家也不喜欢用typedef,喜欢用下面这个东东dict.insert(make_pair("left", "左边"));/*template<class T1,class T2>pair<T1, T2> make_pair(T1 x, T2 y){return (pair<T1, T2>(x, y));}*///map遍历//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//cout << *it << endl;//报错,pair不支持流插入,迭代器的解引用是去调用operator*,set只有king就返回king的引用,pair有两个值first和secong,一个函数的调用用不允许返回两个值//cout << (*it).first << (*it).second << endl;虽然这样可以排序,但是map不喜欢这样搞cout << it->first << it->second << endl;//这里的it是指针,->经过重载,it->返回pari*,然后再->就可以找到first,但是就变成了it->->太难看了,所以编译器优化掉了一个->++it;}cout << endl;for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}
}

 

 4.3 map实现统计次数

void test_map2()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };//统计次数//map<string, int> countMap;//for(auto & str : arr)//{//	//map<string, int>::iterator it = countMap.find(str);//	//if (it != countMap.end()) //找到了//	//{//	//	//说明该水果是有的//	//	//(*it).second++;//	//	it->second++;//	//}//	//else //没找到//	//{//	//	//说明是一个新水果,插入一个//	//	countMap.insert(make_pair(str, 1));//	//}//}//上面的是常规的统计次数的方法,但是太麻烦了,我们一般用[]将查找插入修改一并完成map<string, int> countMap;for (auto& str : arr){countMap[str]++; //重载的operator[]//1,str不在countMap中,插入pair(str,int()),然后再返回++                                   key已经在map中,返回pair(key_iterator,false);//2,str在countMap中,直接返回value的引用再++                                              key不在map中,返回pair(new_key_iterator,true);}map<string, int>::iterator it = countMap.begin();while (it != countMap.end()){cout << it->first << ":" << it->second << endl;++it;}/*V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()); //insert完成了查找,bool表示插入是否成功return ret.first->second}*/
}

 

4.4 map的[]

void test_map3()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("count", "计数"));dict["left"];                   //插入 dict["right"] = "右边";         //插入+修改dict["string"] = "(字符串)";  //修改cout << dict["string"] << endl; //查找,打印 "(字符串)"map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}
}

五,使用map或set解决部分OJ题

5.1 复杂链表的复制

题目出处:LCR 154. 复杂链表的复制 - 力扣(LeetCode)

class Solution
{
public:Node* copyRandomList(Node* head){map<Node*,Node*> copyNodeMap;Node* cur = head;Node* copyhead, *copytail;copyhead = copytail = nullptr;while (cur){Node* copy = new Node(cur->val);copyNodeMap[cur] = copy;if (copytail == nullptr){copytail = copyhead = copy;}else{copytail->next = copy;copytail = copytail->next;}cur = cur->next;}cur = head;Node* copy = copyhead;while (cur){if (cur->random == nullptr){copy->random = nullptr;}else{copy->random = copyNodeMap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};

5.2 前K个高频单词

题目出处:692. 前K个高频单词 - 力扣(LeetCode)

5.2.1 解法一:使用sort算法排序

class Solution {
public://比较大小仿函数struct Compare{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& str : words){countMap[str]++; //统计次数}//因为需要使用sort排序,而map是一个双向迭代器,不是随机迭代器也就是不能通过下标访问元素//所以我们先把值放进vector中排序vector<pair<string, int>> v(countMap.begin(), countMap.end());//stable_sort(v.begin(),v.end(),Compare()); //C++提供的稳定的排序函数sort(v.begin(), v.end(), Compare());vector<string> v1;for (size_t i = 0; i < k; i++){v1.push_back(v[i].first);}return v1;}
};

5.2.2 使用multimap解决

class Solution {
public:/*struct Compare{bool operator()(const int& key1, const int& key2) const{return key1 > key2;}};*/vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for (auto& str : words){countMap[str]++; //统计次数}//直接使用multimap进行排序//multimap<int, string, Compare> sortMap;multimap<int, string, greater<int>> sortMap; //巧合,题目给的测试用例插入的顺序刚好符合要求//当次数相同时,红黑树插入时插入在右边,如果插到左边就不行了for (auto& kv : countMap){sortMap.insert(make_pair(kv.second, kv.first));}vector<string> ret;auto it = sortMap.begin();while (k--){ret.push_back(it->second);++it;}return ret;}
};

 5.2.3 使用set的特性加仿函数解决

class Solution3 {
public:struct Compare{bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const{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& str : words){countMap[str]++; //统计次数}//这里默认是升序,暂时我们要降序,所以加仿函数set<pair<string, int>, Compare> sortSet(countMap.begin(), countMap.end());vector<string> ret;auto it = sortSet.begin();while (k--){ret.push_back(it->first);++it;}return ret;}
};

 5.3 两个数组的交集

题目出处:349. 两个数组的交集 - 力扣(LeetCode)

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2){//先去重set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());auto it1 = s1.begin();auto it2 = s2.begin();vector<int> ret;//前面完成了去重,不相等也就不是交集,小的值的迭代器++,相等,拿出相等值然后两个迭代器同时++while (it1 != s1.end() && it2 != s2.end()){if (*it1 < *it2){it1++;}else if (*it2 < *it1){it2++;}else{ret.push_back(*it1);it1++;it2++;}}return ret;//如果要找差集,那么相等时同时++,不相等,小的就是差集//如果一个走完了,另一个没有走完,那么没走完的剩下的值也是差集}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925345.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

TRB 2024论文分享:基于生成对抗网络和Transformer模型的交通事件检测混合模型

TRB&#xff08;Transportation Research Board&#xff0c;美国交通研究委员会&#xff0c;简称TRB&#xff09;会议是交通研究领域知名度最高学术会议之一&#xff0c;近年来的参会人数已经超过了2万名&#xff0c;是参与人数和国家最多的学术盛会。TRB会议几乎涵盖了交通领域…

【REST2SQL】07 GO 操作 Mysql 数据库

【REST2SQL】01RDB关系型数据库REST初设计 【REST2SQL】02 GO连接Oracle数据库 【REST2SQL】03 GO读取JSON文件 【REST2SQL】04 REST2SQL第一版Oracle版实现 【REST2SQL】05 GO 操作 达梦 数据库 【REST2SQL】06 GO 跨包接口重构代码 MySQL是一个关系型数据库管理系统&#xf…

系统性学习vue-vue核心

做了三年前端,但很多系统性的知识没有学习 还是从头系统学习一遍吧 课程是b站的Vue2.0Vue3.0课程 后续还会学习的如下,就重新开一篇了,不然太长,之后放链接 vue组件化编程 vue-cli 脚手架 vue中的ajax vue-router vuex element-ui vue3 老师推荐的vscode针对vue的插件: Vue 3…

在线项目实习|2024寒假项目实战火热报名中!

一、在线实习项目分类 二、在线实习项目流程 三、在线实习项目优惠及项目特色 1、师傅带练教学模式&#xff0c;手把手教你掌握 采用“师带徒”的教学模式&#xff0c;课程以“项目前置知识学习 师傅带练 项目实战”贯穿&#xff0c;强调动手实操&#xff0c;内容以代码落地为…

mp4文件全部转换为mp3

问题 今天突发奇想&#xff0c;想把mp4视频转换为mp3来收听&#xff0c;于是想到了ffmpeg工具 步骤 安装ffmpeg环境 要在 Windows 上配置 FFmpeg 环境&#xff0c;你可以按照以下步骤进行操作&#xff1a; 下载 FFmpeg&#xff1a; 首先&#xff0c;你需要下载 FFmpeg 的 W…

图像处理:孤立点的检测

图像处理-孤立点的检测 孤立点的检测在图像处理中通常涉及到检测图像中的突变或者边缘&#xff0c;而使用二阶导数是一种常见的方法。一阶导数可以帮助找到图像中的边缘&#xff0c;而二阶导数则有助于检测边缘上的峰值&#xff0c;这些峰值可能对应于孤立点或者特殊的图像结构…

如何在30秒内学会使用pprof分析Go

假设下面的代码是你要分析的 Go 代码&#xff1a; package mainimport ("fmt""sync""time" )// 模拟耗时操作 func hardWork(wg *sync.WaitGroup) {defer wg.Done()fmt.Printf("Start: %v\n", time.Now())// 模拟耗内存a : []string{…

[开发语言][c++]:Static关键字和全局变量

Static关键字和全局变量 1. 生命周期、作用域和初始化时机2. 全局变量3. Static 关键字3.1 面向过程3.1.1 静态全局变量3.1.2 静态局部变量&#xff08;单例中会使用&#xff09;3.1.3 静态函数 3.2 面向对象3.2.1 类内静态成员变量3.2.2 类内静态成员函数 Reference 写在前面&…

伪装目标检测模型论文阅读之:Zoom in and out

论文链接&#xff1a;https://arxiv.org/abs/2203.02688 代码;https://github.com/lartpang/zoomnet 1.摘要 最近提出的遮挡对象检测&#xff08;COD&#xff09;试图分割视觉上与其周围环境融合的对象&#xff0c;这在现实场景中是非常复杂和困难的。除了与它们的背景具有高…

C语言中关于指针的理解及用法

关于指针意思的参考&#xff1a;https://baike.baidu.com/item/%e6%8c%87%e9%92%88/2878304 指针 指针变量 地址 野指针 野指针就是指针指向的位置是不可知的&#xff08;随机的&#xff0c;不正确的&#xff0c;没有明确限制的&#xff09; 以下是导致野指针的原因 1.指针…

力扣每日一练(24-1-13)

如果用列表生成式&#xff0c;可以满足输出的型式&#xff0c;但是不满足题意&#xff1a; nums[:] [i for i in nums if i ! val]return len(nums) 题意要求是&#xff1a; 你需要原地修改数组&#xff0c;并且只使用O(1)的额外空间。这意味着我们不能创建新的列表&#xff…

【java八股文】之Spring系列篇

【java八股文】之JVM基础篇-CSDN博客 【java八股文】之MYSQL基础篇-CSDN博客 【java八股文】之Redis基础篇-CSDN博客 【java八股文】之Spring系列篇-CSDN博客 【java八股文】之分布式系列篇-CSDN博客 【java八股文】之多线程篇-CSDN博客 【java八股文】之JVM基础篇-CSDN博…

ES6(ECMAScript 6.0)

ES6 学习链接ES6什么是ES6&#xff1f;ECMAScript 和 JavaScript 的关系 ECMAScript各版本新增特性ES6 块级作用域 let 学习链接 ES6简介 ECMAScript简介及特性&#xff08;科普&#xff01;很详细&#xff01;&#xff01;&#xff01;&#xff01;&#xff09; 20分钟上手ES…

OpenHarmony基于HDF简单驱动开发实例

OpenHarmony基于HDF简单驱动开发实例 背景 OpenHarmony-3.0-LTS qemu_small_system_demo liteos_a qemu 添加配置 device/qemu/arm_virt/liteos_a/hdf_config/device_info/device_info.hcs device_info 新增&#xff1a; sample_host :: host {hostName "sample…

Docker 配置国内镜像源加速

1. 国内镜像源总览 名称路径中国官方镜像https://registry.docker-cn.com网易163镜像http://hub-mirror.c.163.com中科大镜像https://docker.mirrors.ustc.edu.cn阿里云镜像https://[xxx].mirror.aliyuncs.com 2. 阿里云镜像源 地址&#xff1a;https://cr.console.aliyun.c…

基于Java SSM框架实现医院管理系统项目【项目源码】计算机毕业设计

基于java的SSM框架实现医院管理系统演示 SSM框架 当今流行的“SSM组合框架”是Spring SpringMVC MyBatis的缩写&#xff0c;受到很多的追捧&#xff0c;“组合SSM框架”是强强联手、各司其职、协调互补的团队精神。web项目的框架&#xff0c;通常更简单的数据源。Spring属于…

尼科彻斯定理----C语言

大家好我是Beilef许久未见了&#xff0c;小弟学校考试刚结束。这个过程懂的都懂。痛------ 文章目录 目录 文章目录 前言(一不好懂可以直接跳到二&#xff09; 一、尼科彻斯定理是什么&#xff1f; 二、尼科彻斯定理解析 这是ai的回答 尼科彻斯定理&#xff08;Nikomačs theor…

计算机网络 —— 数据链路层

数据链路层 3.1 数据链路层概述 数据链路层把网络层交下来的数据构成帧发送到链路上&#xff0c;以及把收到的帧数据取出并上交给网络层。链路层属于计算机网络的底层。数据链路层使用的信道主要由以下两种类型&#xff1a; 点对点通信。广播通信。 数据链路和帧 链路&…

京东年度数据报告-2023全年度笔记本十大热门品牌销量(销额)榜单

2023年度&#xff0c;在电脑办公市场整体销售下滑的环境下&#xff0c;笔记本市场的整体销售也不景气。 根据鲸参谋平台的数据显示&#xff0c;京东平台上笔记本的年度销量为650万&#xff0c;同比下滑约16%&#xff1b;销售额约为330亿&#xff0c;同比下滑约19%。同时&#…

基于ssm的实验室排课系统论文

摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对信息管理混乱&#xff0c;出错率高&#xff0c;信息安全性差&#x…