C++(map和set）

目录

前言

正文 

1.预备知识 

1.1序列式容器

 1.2关联式容器

1.3键值对 

2.set 

2.1概念 

​编辑 2.2set的使用

 2.3set总结

2.4multiset 

3.map 

3.1概念 

3.2、map的使用 

3.3map中operator[] 

3.4map总结 

 3.5multimap

前言

  s et 和  map 是  STL 中的容器之一，不同于普通容器，它俩的查找速度极快，常用来存储各种经常被检索的数据，因为这俩容器的底层是平衡二叉搜索树中的红黑树。 根据应用场景的不同， STL 总共实现了两种不同结构的管理式容器：树型结构与哈希结构。 树型结 构的关联式容器主要有四种： map 、 set 、 multimap 、 multiset。这四种容器的共同点是：使 用平衡搜索树 ( 即红黑树 )作为其底层结果，容器中的元素是一个有序的序列。哈希结构的容器也有四种 unordered_map、unordered_set、unordered_multimap、unordered_multiset，容器中的元素是无序的序列。如下图所示：

 

正文 

1.预备知识 

在进行map和set容器的学习之前我们先对关联式容器和序列式容器做个知识补充。

1.1序列式容器

         序列式容器 比如 string、vector、list、deque 等，序列式容器的特点就是底层为线性序列的数据结构，就比如 list，其中的节点是 线性存储的，一个节点存储一个元素，其中存储的元素都可序，但未必有序。

 1.2关联式容器

        关联式容器 则比较特殊，其中存储的是 <key, value> 的 键值对，这就意味着可以按照 键值大小 key 以某种特定的规则放置于适当的位置，关联式容器没有首尾的概念，因此没有头插尾插等相关操作，本文中学习的 set 和 map 就属于 关联式容器 

 

1.3键值对 

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value ， key 代
表键值， value 表示与 key 对应的信息 。比如：现在要建立一个英汉互译的字典，那该字典中必然
有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应
该单词，在词典中就可以找到与其对应的中文含义。

在标准库中（SGI） 专门提供了这种结构pair

//SGI 版 STL 中的实现
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) {}

#ifdef __STL_MEMBER_TEMPLATES
  template <class U1, class U2>
  pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};

 pair 中的 first 表示 键值，second 则表示 实值，在给 关联式容器 中插入数据时，可以构建 pair 对象比如下面就构建了一个 键值 key 为 string，实值 value 为 int 的匿名 键值对 pair 对象

pair<string, int>("apple", 4);

 可以将此匿名对象传入 关联式容器 中，当然这样写未免过于麻烦了，于是库中设计了一个函数模板 make_pair，可以根据传入的参数，去调用 pair 构建对象并返回

make_pair("apple", 4);	//构建出的匿名对象与上面的一致

 make_pair 的定义如下所示：

 

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
  return ( pair<T1,T2>(x,y) );
}

注：该函数实际会被编译器优化为 内联函数，因此不会造成过多消耗，可以放心使用 

2.set 

2.1概念 

  • set是按照一定次序存储元素的容器 
  • set在底层是用二叉搜索树(红黑树)实现的

 其中的 T 就是 set 的实值（键值），参数2 Compare 为存储依据，默认为升序，即符合 二叉搜索树 中序遍历的结果：升序，参数3 Alloc 是空间配置器

 作为 STL 中的容器，set 当然少不了迭代器，树型关联式容器迭代器的遍历结果为有序，所以迭代器遍历的本质是 中序遍历，同时 set 的迭代器还是一个 双向迭代器，支持 ++ 和 -- 操作

 2.2set的使用

set的构造函数

 可以直接创建一个空 set 使用，也可以根据迭代器区间创建 set

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 8,5,6,7,3,1,1,3 };

	set<int> s1;	//默认构造
	set<int> s2(arr.begin(), arr.end());	//迭代器区间构造

	cout << "s1: ";
	for (auto e : s1)
		cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (auto e : s2)
		cout << e << " ";
	cout << endl;

	return 0;
}

 

 

 set 中的常用功能

  count 也可以用来查找元素是否存在，对于 set 来说，键值 key 就是 实值 value，并且因为不允许冗余，所以只有一个 键值，count 统计 键值 数量不就相当于 查找 

#include <iostream>
#include <vector>
#include <set>
using namespace std;


int main()
{
	vector<int> arr = { 7,3,6,9,3,1,6,2 };
	set<int> s1(arr.begin(), arr.end());

	for (int i = 0; i < 10; i++)
	{
		if (s1.count(i))
			cout << i << ":[存在]" << endl;
		else
			cout << i << ":[不存在] " << endl;
	}

	return 0;
}

 同时，也可以通过修改模板参数中的compare 改变默认排序顺序

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 7,3,6,9,3,1,6,2 };
	set<int, greater<int>> s1(arr.begin(), arr.end());

	for (auto e : s1)
		cout << e << " ";

	return 0;
}

 

 2.3set总结

  • 只有键值，键值就是实值，所以传参只需要传递key值
  • 自带去重机制，不允许数据冗余
  • 迭代器遍历默认为升序（底层平衡搜索树中序） 
  • 不可以修改键值（const保护）

2.4multiset 

 除此之外，multiset 和 set 的操作没什么区别，一模一样

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 3,5,3,4,5,9,2,3 };
	multiset<int> ms1(arr.begin(), arr.end());

	for (auto e : ms1)
		cout << e << " ";
	cout << endl;

	return 0;
}

 

 值得一提的是，当在 multiset 中查找冗余的数据时，返回的是 中序遍历中，第一次出现的元素

 

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 3,5,3,4,5,9,2,3 };
	multiset<int> ms1(arr.begin(), arr.end());

	auto it = ms1.begin();
	while (it != ms1.end())
	{
		cout << *it << " | " << &*(it) << endl;
		++it;
	}

	cout << "================" << endl;

	cout << "ms1.find(3): " << &*(ms1.find(3)) << endl;

	return 0;
}

 

 count在multiset中起到了作用

#include <iostream>
#include <vector>
#include <set>
using namespace std;


int main()
{
	vector<int> arr = { 3,5,3,4,5,9,2,3 };
	multiset<int> ms1(arr.begin(), arr.end());

	for (int i = 0; i < 10; i++)
		cout << i << "在 multiset 中的数量: " << ms1.count(i) << endl;

	return 0;
}

 

3.map 

3.1概念 

  • map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元
  • 素。
  • 在内部，map中的元素总是按照键值key进行比较排序的。
  • map支持下标访问符，即在[]中放入key，就可以找到与key对应的value
  • map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

 

 其中两个模版参数：

  1. Key 就是键值对中的 键值
  2. T 则是键值对中的 实值

在 map 中会用到前面提到过的 pair 结构，其中 first 表示键值，second 表示实值map 也有迭代器，也是 双向迭代器。

 

3.2、map的使用 

 构造函数

 

 

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
	vector<pair<string, int>> arr = { make_pair("apple", 4), make_pair("origine", 7), make_pair("banna", 5) };

	map<string, int> m1;	//创建一个空的 map
	map<string, int> m2(arr.begin(), arr.end());	//创建包含数据的 map

	cout << "a: " << endl;
	for (auto &a : m1)
		cout << a.first << ":" << a.second << endl;
	cout << "b: " << endl;
	for (auto b : m2)
		cout << b.first << ":" << b.second << endl;

	return 0;
}

map常用功能

 map插入的返回值比set略微复杂，要完成是否插入成功，同时还要表示插入成功的迭代器，所以需要返回一个pair

 

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<string, int> m1;
	auto ret = m1.insert(make_pair("a", 97));
	cout << "<" << ret.first->first << ":" << ret.first->second << ">" << " | " << ret.second << endl;

	ret = m1.insert(make_pair("a", 100));
	cout << "<" << ret.first->first << ":" << ret.first->second << ">" << " | " << ret.second << endl;

	return 0;
}

 

find 和 count 跟 set 中的一样，可以用来判断元素是否存在，不过 find 返回的是 迭代器，count 返回的则是 键值数

map 是支持修改 实值 value 的，因此 可以根据普通迭代器修改 实值

 

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<string, int> m1;
	m1.insert(make_pair("a", 97));
	auto it = m1.find("a");
	cout << "<" << it->first << ":" << it->second << ">" << endl;

	it->second = 668;
	cout << "<" << it->first << ":" << it->second << ">" << endl;

	return 0;
}

3.3map中operator[] 

operator[] 返回的是当前 键值 对应的 实值，如果当前 键值 不存在，则会插入新的 键值对 

 

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	vector<string> word = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };
	map<string, int> table;

	for (auto& e : word)
		table[e]++;

	for (auto e : table)
		cout << "<" << e.first << ":" << e.second << ">" << endl;

	return 0;
}

 

显然，map 中的 operator[] 是一个非常强大的功能

 

 

operator[] 的返回值为 mapped_type，即 实值 value 的引用，参数 key_type 是 键值 key

重点在于 operator[] 的实现：如何凭借 键值 返回对应的 实值，并且做到新键值对的插入

(*((this->insert(make_pair(k, mapped_type()))).first)).second

 

 注意：

operator的三步骤：

  • 插入一个新的键值对 this->insert( make_pair(k, mapped_type()) )
  • 获取 insert 返回值中的 键值 返回值.first 即迭代器 iterator
  • 最后通过迭代器获取 实值 (*iterator).second

3.4map总结 

  •  既包含键值，也包含实值，插入时候，需要传递键值对：pair对象（make_pair）
  • 自动去重，不允数据冗余
  • 迭代器遍历默认升序
  • 普通迭代器允许修改实值，不允许修改键值 

 3.5multimap

 

multimap 中允许出现多个 重复的键值，这就意味着 operator[] 无法确认调用者的意图 -> 不知道要返回哪个 键值 对应的 实质

所以 multimap 中没有提供 operator[]

 

 

除了 允许键值冗余 和 没有 operator[] 这个两个特点外，multimap 和 map 在操作上没有区别

当然，查找 find 时，返回的是中序遍历中第一次出现元素的迭代器；计数 count 返回的则是当前 键值 的数量。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

matlab自定义函数实现图像小波变换

matlab自定义函数实现图像小波变换

matlab中提供了小波变换函数lwt和ilwt&#xff0c;可以方便地实现提升小波变换。 我们按照小波变换的定义&#xff0c;粗糙地实现一个针对图像的小波变换&#xff0c;如下&#xff1a; % 使用方法&#xff1a; img imread(lena256.bmp); % 假设lena.png是灰度图像 subplot(2…
阅读更多...
单细胞转录组数据分析的10大软件/流程

单细胞转录组数据分析的10大软件/流程

单细胞数据分析现在已经有上千个软件工具可供使用了&#xff0c;这为用户带来便利的同时也造成了选择困难。就像时间一样&#xff0c;一个表&#xff0c;没问题&#xff0c;但如果有两个表&#xff0c;时间还不一样&#xff0c;该信谁的呢&#xff1f; 正好我们前面一篇文章介绍…
阅读更多...
Windows10更新失败 错误 0x80070643、KB5034441的解决方法之二

Windows10更新失败 错误 0x80070643、KB5034441的解决方法之二

Windows10更新失败 错误 0x80070643、KB5034441 在知乎Windows10更新失败 错误 0x80070643、KB5034441的原因分析和几个解决方法 - 知乎 参考文章进行操作&#xff0c;更详细信息自己看上面链接。 我电脑的硬盘是mbr格式&#xff0c;而且没有划分恢复分区。 Microsoft Windo…
阅读更多...
JS(react)图片压缩+图片上传

JS(react)图片压缩+图片上传

上传dome var fileNodeTakeStock: any createRef();<inputref{fileNodeTakeStock}onChange{showPictureTakeStock}style{{ display: "none" }}id"fileInpBtn"type"file"accept"image/*" //限制上传格式multiple{false}capture&qu…
阅读更多...
C++继承与多态

C++继承与多态

一&#xff0c;继承 1&#xff0c;继承定义 继承是C三大特性之一。C有类型的复用&#xff1a;类型模板&#xff0c;函数的复用&#xff1a;函数重载。而继承其本质是一种类的复用&#xff0c;使得程序员可以在原有类特性之上进行扩展来产生新的类&#xff0c;原有的类称为父类…
阅读更多...
【深度学习】全连接神经网络

【深度学习】全连接神经网络

全连接神经网络 全连接神经网络的结构 整体结构 神经网络：类似神经元，前一层可以不断地传递给下一层。 神经网络模型由多个单元结构组成。 单元结构 单元结构的数学公式： a = h ( w x + b ) a=h(wx+b) a=h(wx+b) h(x)：激活函数 比如sigmoid就是激活函数之一隐藏层大多…
阅读更多...
Collections集合工具类-JAVA

Collections集合工具类-JAVA

java.util.Collections:是个集合工具类它不是集合&#xff0c;而是集合的工具类 常用 API&#xff1a;注意 binarySearch 方法要求元素有序 方法实现&#xff1a; public class Test01 {public static void main(String[] args) {ArrayList<String>list1new ArrayList…
阅读更多...
TPH-YOLOv5:基于Transformer预测头改进的YOLOv5开发构建麦穗检测计数分析系统

TPH-YOLOv5:基于Transformer预测头改进的YOLOv5开发构建麦穗检测计数分析系统

关于小麦麦穗或者是麦粒相关的开发实践不多&#xff0c;但前文也有所涉及&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《基于轻量级yolov5nCBAM开发构建全球小麦麦穗智能检测计数系统》 《基于YOLOv5[n/s/m/l/x]全系列参数模型开发构建小麦麦穗颗粒智能化精准检…
阅读更多...
TRIZ经典矛盾矩阵.exe

TRIZ经典矛盾矩阵.exe

TRIZ经典矛盾矩阵.exe 一、概要二、技术细节I&#xff0e;函数open_dialog&#xff08;&#xff09;和open_version_dialog&#xff08;&#xff09;II&#xff0e;函数resolvent&#xff08;&#xff09;III&#xff0e;函数Invention_Principle_Content&#xff08;&#xff…
阅读更多...
svn 安装路径

svn 安装路径

SVN客户端安装&#xff08;超详细&#xff09; 一、SVN客户端安装 1、下载安装包地址&#xff1a;https://tortoisesvn.net/downloads.html 此安装包是英文版的&#xff0c;还可以下载一个语言包&#xff0c;在同界面的下方 一直点击下一步&#xff0c;直到弹出选择红框 然…
阅读更多...
You Only Look Once

You Only Look Once

You Only Look Once 真方便, 一行代码, 直接输出超炫效果图_哔哩哔哩_bilibili使用yolov8中等模型对视频进行分割, 视频播放量 465、弹幕量 0、点赞数 7、投硬币枚数 4、收藏人数 3、转发人数 2, 视频作者 宝安钢铁侠, 作者简介 一个分享国产电子DIY的阿婆主，啥也不会，就想分…
阅读更多...
qt5-入门-信号槽理解+QMainWindow

qt5-入门-信号槽理解+QMainWindow

参考&#xff1a; Qt 深入了解信号槽_w3cschool https://www.w3cschool.cn/learnroadqt/wz3t1j47.html Qt MainWindow_w3cschool https://www.w3cschool.cn/learnroadqt/uqjl1j4b.html 本地环境&#xff1a; win10专业版&#xff0c;64位 信号槽 最简单的例子&#xff1a;写一…
阅读更多...
spring cache的使用（Redis）

spring cache的使用（Redis）

要在Spring Boot应用中使用Redis作为缓存&#xff0c;你需要遵循一些步骤来配置和使用Redis。以下是使用Spring Cache抽象与Redis进行整合的详细说明&#xff1a; 1. 添加依赖 首先&#xff0c;需要在pom.xml中添加Spring Boot的Redis starter依赖以及缓存的starter依赖。这会…
阅读更多...
我的创作纪念日和前端碎碎念

我的创作纪念日和前端碎碎念

机缘 作为一个前端开发者&#xff0c;我一直热衷于将设计和技术相结合&#xff0c;尽可能提升用户体验。我最初成为创作者的初心源于学习记录&#xff0c;把创作当作一个笔记&#xff0c;希望把自己遇到的问题&#xff0c;以及学习到的实用技巧记录下来&#xff0c;方便学习回…
阅读更多...
新书速览|Docker与Kubernetes容器运维实战

新书速览|Docker与Kubernetes容器运维实战

帮助读者用最短的时间掌握Docker与K8s运维技能 内容简介 随着云计算和容器技术的发展&#xff0c;Docker与Kubernetes已经成为各个企业首选的部署工具&#xff0c;使用它们可以提高系统的部署效率和运维能力&#xff0c;降低运维成本。本书是一本为初学者量身定制的Docker与Kub…
阅读更多...
nodejs+vue+mysql校园失物招领网站38tp1

nodejs+vue+mysql校园失物招领网站38tp1

本高校失物招领平台是为了提高用户查阅信息的效率和管理人员管理信息的工作效率&#xff0c;可以快速存储大量数据&#xff0c;还有信息检索功能&#xff0c;这大大的满足了用户和管理员这两者的需求。操作简单易懂&#xff0c;合理分析各个模块的功能&#xff0c;尽可能优化界…
阅读更多...
nodejs+vue+ElementUi学生兼职招聘求职系统b8t93

nodejs+vue+ElementUi学生兼职招聘求职系统b8t93

浏览器&#xff1a;谷歌浏览器课题主要分为三大模块&#xff1a;即管理员模块和学生、企业模块&#xff0c;主要功能包括&#xff1a;学生、企业、岗位类型、招聘信息、应聘信息、投诉建议等&#xff1b; 运行软件:vscode 前端nodejsvueElementUi 语言 node.js 框架&#xff1…
阅读更多...
【MBtiles数据索引和服务发布】GeoServer改造Springboot番外系列二

【MBtiles数据索引和服务发布】GeoServer改造Springboot番外系列二

xyz地图服务访问示例&#xff1a;http://192.168.1.240:8081/gmserver/raster/xyz/firstWP:Imagery-raster/{z}/{x}/{y}.jpg 访问示例如下&#xff1a; mbtiles目录结构 根据z&#xff0c;x&#xff0c;y获取对应mbtiles文件路径的工具方法 说明&#xff1a;重点是使用getMb…
阅读更多...
STM32——I2C

STM32——I2C

通信协议见&#xff08;STM32——SPI&#xff09; 一、I2C协议 1.1 I2C协议介绍&#xff1b; I2C是&#xff08;Inter IC Bus&#xff09;是由Philips公司开发的一种通用数据总线&#xff1b; 有多根通信线&#xff1b; 一根SDA&#xff08;串行通信线&#xff09;&#xf…
阅读更多...
PySpark（一）Spark原理介绍、PySpark初体验及原理

PySpark（一）Spark原理介绍、PySpark初体验及原理

Spark简介 Apache Spark是用于大规模数据&#xff08;large-scala data&#xff09;处理的统一&#xff08;unified&#xff09;分析引擎&#xff0c;其特点就是对任意类型的数据进行自定义计算。 Spark VS Hadoop 尽管Spark相对于Hadoop而言具有较大优势&#xff0c;但Spark并…
阅读更多...
最新文章

Copyright @ 2022~2023