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

set和map的使用

目录

1.关联式容器

2.键值对

3.set

3.1set的模版参数列表

3.2对set的修改

 3.2.1insert

3.2.2 erase

3.2.3clear

3.2.4swap

3.2.5 find

3.3set的迭代器

3.4set的容量

4.map

4.1对map的修改

4.1.1insert

 4.1.2erase

 4.1.3swap

4.1.4clear

4.2map的迭代器

 4.3operator[ ] 

4.4map容量查询 

4.5利用map统计个数的三种方法 

4.5.1方法一

4.5.2方法二

4.5.3方法三

5.multiset和multimap 


1.关联式容器

我们之前学的string,vector,deque,list等,其底层都是线性序列的数据结构,统称为序列式容器,里面存储的是元素本身。而set和map的底层是平衡搜索树,平衡搜索树中存储的是<key,val>结构的键值对,通过key才可找寻到存储的val,属于关联式容器。

相比序列式容器,关联式容器在数据检索时速度更快

2.键值对

键值对是一一对应的一种结构,里面存储着两个变量key和val,key代表键值,val表示的是key对应的信息

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)
{}
};

通过阅读pair的源码我们发现,在pair中key被命名为first,val被命名为second。

3.set

set就类似我们之前学到的k型的搜索树,只存储val,但是其底层实际上也是存储着键值对,不过是<val,val>类型。

3.1set的模版参数列表

第一个参数代表着val的类型;compare:set中的元素默认按照小于来比较 ;alloc:set中元素的空间管理方式,采用的STL提供的空间进行管理

3.2对set的修改

 3.2.1insert

set<int> s;
s.insert(5);
pair<set<int>::iterator, bool> p = s.insert(10);
cout << p.second << endl; //输出1(true)
cout << *p.first;//输出iterator指向的10

3.2.2 erase

3.2.3clear

将set中的元素全部清空 

3.2.4swap

将两个set交换,实际上就是交换头节点。

void set_text2()
{set<int> s;s.insert(9);s.insert(8);s.insert(3);s.insert(2);set<int> s1;s1.insert(8);s1.insert(7);s1.insert(5);s1.insert(4);s1.insert(0);s1.swap(s);
}

3.2.5 find

根据要找的val值,如果有则返回其对应的迭代器,如果没有则返回迭代器end();与algorithm中的find的区别是,时间复杂度的区别。因为是二叉搜索树,所以这里的find时间复杂度是O(logN)

3.3set的迭代器

set也支持迭代器遍历和范围for遍历

set<int> s;
s.insert(9);
s.insert(8);
s.insert(3);
s.insert(2);
set<int>::iterator it = s.begin();
while (it != s.end())
{cout << *it << " ";++it;
}
cout << endl;
for (auto& x : s)
{cout << x << " ";
}

值得注意的是,它的遍历都是走的中序遍历,因此排出的是有序的,且能去重。因此set的一个功能就是排列和去重。

3.4set的容量

 值得注意的是,set中不允许修改它的val值,因为这可能会使二叉搜索树被破坏掉。

4.map

map的底层是KV模型,但是其节点是打包成pair键值对来进行存储的,pair中的first成员存储的就是key,pair成员的second存储的就是val值。我们是通过pair中的key来进行排序,查找的

4.1对map的修改

4.1.1insert

如图可以看见insert插入的其实是pair键值对,返回的也是一个pair键值对。如果插入成功那么返回的pair键值对的first存储的是成功插入位置pair的迭代器,second是bool值的1;如果插入失败,那么返回的pair健值对的first存储的是map中已经存储的相同key值的pair的迭代器,second是bool值的0。

map<int, int> m;
m.insert(pair<int, int>(1, 1));
m.insert(make_pair(2, 2));

上述的第一个插入实际上是一个匿名构造了一个pair,但过于复杂。我们通常用第二个make_pair模版函数进行构造,实际效果相同。

 4.1.2erase

 4.1.3swap

交换两个map的数据

4.1.4clear

清空一个map的所有数据

4.2map的迭代器

map支持迭代器就意味着它也支持范围for,迭代器中存储的实际上是pair键值对的指针

map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(2, 2));
m.insert(make_pair(3, 3));
m.insert(make_pair(4, 4));
m.insert(make_pair(5, 5));
m.insert(make_pair(8, 8));
m.insert(make_pair(10, 10));
map<int, int>::iterator it = m.begin();
while (it != m.end())
{cout << it->first << " " << it->second << endl;;++it;
}
cout << endl;
for (auto& x : m)
{cout << x.first << " " << x.second << endl;
}
cout << endl;

 4.3operator[ ] 

map中重载了operator[],如果传入的key值map中存在,则返回val的引用;如果传入的key不存在,则先insert,在返回默认的val。

其底层实现如下

   

operator[]的作用有插入,查找,修改val 

4.4map容量查询 

4.5利用map统计个数的三种方法 

例如一个string数组中存储了许多水果,统计不同水果重复出现的次数

4.5.1方法一

利用find查找判断是否在m内,如果不再则插入,在则++其second值

string s[] = { "苹果","香蕉","苹果","哈密瓜","凤梨","哈密瓜","苹果" };
map<string, int> m;
//方法一,利用find查找判断是否在m内,如果不再则插入,在则++其second值
for (auto& x : s)
{map<string, int>::iterator it = m.find(x);if (it == m.end()){m.insert(make_pair(x, 1));}else{it->second++;}
}

4.5.2方法二

利用insert的返回值进行操作

	string s[] = { "苹果","香蕉","苹果","哈密瓜","凤梨","哈密瓜","苹果" };map<string, int> m;for (auto& x : s){pair<map<string,int>::iterator,bool> p = m.insert(make_pair(x, 1));if (p.second == false){p.first->second++;}}

4.5.3方法三

利用operator[]

string s[] = { "苹果","香蕉","苹果","哈密瓜","凤梨","哈密瓜","苹果" };
map<string, int> m;
for (auto& x : s)
{m[x]++;//如果x在m中,就++其val值;如果x不再m中,先创建一个默认val值的pair,插入,然后++其val
}
for (auto& x : m)
{cout << x.first << " " << x.second << " ";
}

map中的key值是唯一的,不可修改。但是其val值并不是唯一的,且可修改

5.multiset和multimap 

set和map中的key值都是唯一的,而multiset和multimap中的key可以有重复的,但是mulitmap中没有重载operator[],因为可能有重复的key,那么就不知道该返回哪个val的引用

http://www.lryc.cn/news/478255.html

相关文章:

  • LCL三相并网逆变器simulink仿真+说明文档
  • 从0开始深度学习(24)——填充和步幅
  • CPU Study - Instructions Fetch
  • GJ Round (2024.9) Round 1~7
  • 【CMCL】多模态情感识别的跨模态对比学习
  • 输入/输出系统
  • asp.net+uniapp养老助餐管理系统 微信小程序
  • 部署istio应用未能产生Envoy sidecar代理
  • 使用YOLO 模型进行线程安全推理
  • ABAP 增强
  • vue使用方法创建组件
  • HTML 基础标签——链接标签 <a> 和 <iframe>
  • @SpringBootApplication源码解析
  • 【实战篇】requests库 - 有道云翻译爬虫 【附:代理IP的使用】
  • 法语动词变位
  • Excel:vba实现批量插入图片
  • Vue3的router和Vuex的学习笔记整理
  • 设置JAVA以适配华为2288HV2服务器的KVM控制台
  • 掌握Qt调试技术
  • 使用NVM自由切换nodejs版本
  • 同三维T610UHK USB单路4K60采集卡
  • Git超详细笔记包含IDEA整合操作
  • 摩尔线程嵌入式面试题及参考答案(2万字长文)
  • C++ 编程基础(3)数据类型 | 3.1、指针
  • nacos本地虚拟机搭建切换wiff问题
  • 打造完整 Transformer 编码器:逐步实现高效深度学习模块
  • 软件对象粒度控制与设计模式在其中作用的例子
  • 代码随想录算法训练营Day.3| 移除链表元素 设计链表 反转链表
  • 基于SSM的学生考勤管理系统的设计与实现
  • 制作gif动图并穿插到CSDN文章中