C++ - set 和 map详解

目录

0. 引言

1. 关联式容器 

2. 键值对

 3. 树形结构

4. set

4.1 set 的定义

4.2 set 的构造 

4.3 set 的常用函数 

4.4 set 的特点 

5. multiset 

5.1 multiset 插入冗余数据

5.2 multiset - count 的使用 

6. map 

6.1 map 的定义 

6.2 map 的构造

6.3 map的常用函数 

6.4 map - operator[ ]

7. multimap 


0. 引言

在之前的博客中,我们已经介绍过 STL 中的部分容器,例如:vector,list,deque等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。而本节我们介绍的 map 以及set 属于关联式容器,那什么是关联式容器?它与序列式容器有什么区别?

关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是结构的键值对,在数据检索时比序列式容器效率更高。

那么接下来我们一起逐步开始学习吧!

1. 关联式容器 

我们之前学习过的序列式容器底层为线性序列的数据结构,例如 list ,其节点是线性存储的,一个节点存储一个数据,但这些数据未必有序。而关联式容器则比较特殊,存储的是 <key, value>  的键值对, 这意味着可以按照键值大小 key 以某种规则放置在适当的位置,因此,关联式容器没有首位的概念,因此没有头插尾插等相关操作。

那什么是键值对呢?我们接着来看。

2. 键值对

键值对是用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代 表键值,value表示与key对应的信息。

比如:现在要建立一个英汉互译的字典,那该字典中必然 有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应 该单词,在词典中就可以找到与其对应的中文含义。  

在标准库中,专门定义了键值对 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 对象。 

例如,下面构建了一个键值 keystring,实值 value int 的匿名键值对 pair 对象。 

pair<string, int>("hello", 123);

 此外,库中还设计了一个函数模板 make_pair, 可以根据传入的参数,去调用 pair 构建对象并返回。make_pair 实际会被编译器优化为 内联函数,因此不会造成过多消耗,可以放心使用

//make_pair 定义:
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
  return ( pair<T1,T2>(x,y) );
}
make_pair("hello", 123)

 3. 树形结构

在 C++ 中提供了四种树形结构的关联式容器。set / multiset / map / multimap。 

基于哈希表的,我们将在后续详细介绍。 

4. set

4.1 set 的定义

 set 实则是二叉搜索树中的 key 模型。key 模型主要的应用场景是判断在不在,例如:门禁系统,车库系统,检查文章中单词拼写是否正确等。

set 只包含实值 value,或者说, 实值就是键值,键值就是实值。

其参数的解释如下: 

template < class T,                        // 实值(键值)
           class Compare = less<T>,        // 存储依据,默认为升序
           class Alloc = allocator<T>      // 空间配置器
           > class set;

接着我们来看 set 的使用。 

4.2 set 的构造 

我们首先来看构造函数:

在这里我们创建时,需要指定实值的类型。 

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

int main()
{
	vector<int> arr = {1,4,5,6,8,8,5,3,2,9};
	set<int> s1;//创建一个空的 set
	set<int> s2(arr.begin(), arr.end());//创建包含数据的 set

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

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

	return 0;
}

 

 与二叉搜索树一样, set 不支持数据冗余,冗余数据则无法插入,如果需要插入冗余数据,则需要使用 multiset,我们后续会讲到。

4.3 set 的常用函数 

功能作用
迭代器遍历容器
empty判断容器是否为空
size当前容器中的元素个数
max_set容器的最大容量
insert将元素插入到特定位置
erase删除指定元素
swap交换两个容器
clear清空容器中的所有元素
find查找实值是否存在并返回迭代器位置
count统计容器中指定键值的数量

下面我们实际演示相关函数的使用,代码如下: 

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

int main()
{
	vector<int> arr = {1,4,5,6,8,3,2,9};
	set<int> s1(arr.begin(), arr.end());//创建包含数据的 set
	
	//迭代器遍历
	cout << "迭代器遍历结果: ";
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	cout << endl;
	cout << "empty(): " << s1.empty() << endl;
	cout << "size(): " << s1.size() << endl;
	cout << "max_size(): " << s1.max_size() << endl;

	//插入元素7
	cout << endl;
	cout << "insert(7): ";
	s1.insert(7);
	for (auto e : s1) cout << e << " ";
	cout << endl;

	//删除元素9
	cout << endl;
	cout << "erase(9): ";
	s1.erase(9);
	for (auto e : s1) cout << e << " ";
	cout << endl;

	//交换 查找 清理
	cout << endl;
	set<int> s2(arr.begin() + 3, arr.end());
	s1.swap(s2);
	cout << "s1: ";
	for (auto e : s1) cout << e << " ";
	cout << endl;
	cout << "s2: ";
	for (auto e : s2) cout << e << " ";
	cout << endl;

	cout << endl;
	cout << "s1.find(3): ";
	cout << (s1.find(3) != s1.end()) << endl;

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

	return 0;
}

结果如下: 

那么,count 在 set 中只能用作查找,因为 set 键值就是实值,因为其不允许冗余,因此只有一个键值。

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

int main()
{
	vector<int> arr = { 1,4,5,6,8,3,2,9 };
	set<int> s1(arr.begin(), arr.end());
	for (int i = 0; i < 10; i++)
	{
		if (s1.count(i))
			cout << i << " 在 set 中" << endl;
		else
			cout << i << " 不在 set 中" << endl;
	}
	return 0;
}

我们也可以根据 set 的构造函数将其排为降序。 

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

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

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

	return 0;
}

最后需要注意的是,键值 key 不允许修改,因为如果改变了,会破坏二叉搜索树的原则,set 中的普通迭代器在本质上也是 const 迭代器。

4.4 set 的特点 

最后,我们总结一下 set 的特点: 

5. multiset 

multisetset 的唯一区别就在于 multiset 插入冗余数据时,不会失败。

由于 multiset 的操作与 set 基本相同,在这里我们主要演示区别。

5.1 multiset 插入冗余数据

先看代码,从中我们可以发现,multiset 允许数据冗余。

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

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

	return 0;
}

此外,multiset 查找冗余的数据时,返回的是中序遍历中,第一次出现的元素 :

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

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

	cout << endl << endl;

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

	return 0;
}

5.2 multiset - count 的使用 

cout 在 multiset中。真正发挥了统计键值数的效果。 

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

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

	return 0;
}

6. map 

6.1 map 的定义 

map 是二叉搜索树改造后的 key / value 模型,是真正意义上的键值对,存在关于应用搜索的应用场景,例如:中英文互译字典,电话号码查询快速信息,电话号码+验证码等。

key / value 模型除了可以用来查找之外,还可以用来统计,其实就是哈希的思想,建立映射关系

模板中 key 就是键值对中的键值T 为键值对中的实值。 所以 map 也会使用到 pair 结构,其中first 表示键值second 表示实值。map 也存在迭代器,且为双向迭代器。

6.2 map 的构造

map 有以下构造方法: 

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

int main()
{
	vector<pair<string, int>> arr = { make_pair("A", 65), make_pair("B", 66), make_pair("C", 67), make_pair("D", 68) };

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

	cout << "m1: " << endl;
	for (auto e : m1)
		cout << e.first << " | " << e.second << endl;

	cout << endl;

	cout << "m2: " << endl;
	for (auto e : m2)
		cout << e.first << " | " << e.second << endl;

	return 0;
}

这里在访问 map 中的键值和实值时,需要通过 pair 指定对象访问,例如这里的:e.first 。

6.3 map的常用函数 

功能作用
迭代器遍历容器
empty判断容器是否为空

size

当前容器中的元素数
max_size容器的最大容量
operator[ ]按照键值,访问实值,如果没有,则新插入
insert元素插入,根据特定条件插入至合适位置
erase删除指定元素
swap交换两个容器
clear清空容器中的所有元素
find查找实值是否存在并返回迭代器位置
count统计容器中指定键值的数量

这里函数的使用方法与 set 基本相同,但新增了一个 operator[ ]。 下面我们来看演示:

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

int main()
{
	vector<pair<string, int>> arr{ make_pair("C", 67),make_pair("B", 66), make_pair("E",69), make_pair("A", 65), make_pair("D", 68), };

	map<string, int> m1(arr.begin(), arr.end());

	//迭代器遍历
	cout << "迭代器遍历结果: ";
	map<string, int>::iterator it = m1.begin();
	while (it != m1.end())
	{
		cout << "<" << it->first << ":" << it->second << "> ";
		++it;
	}
	cout << endl;

	//判空、求大小、解引用
	cout << endl;
	cout << "empty(): " << m1.empty() << endl;
	cout << "size(): " << m1.size() << endl;
	cout << "max_size(): " << m1.max_size() << endl;
	cout << "m1[""A""]: " << m1["A"] << endl;
	cout << "m1[""B""]: " << m1["B"] << endl;

	//插入元素
	cout  << endl;
	cout << "insert(""F"", 69): ";
	m1.insert(make_pair("F", 69));
	for (auto e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	//删除元素
	cout << endl;
	cout << "erase(""C""): ";
	m1.erase("C");
	for (auto e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	//交换、查找、清理
	cout << endl;
	map<string, int> m2(arr.begin() + 1, arr.end()-1);
	m1.swap(m2);
	cout << "m1.swap(m2)" << endl;
	cout << "m1: ";
	for (auto e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

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

	cout << endl;
	cout << "m1.find(""B""): ";
	cout << (m1.find("B") != m1.end()) << endl;

	cout << endl;
	cout << "m2.clear()" << endl;
	m2.clear();

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

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

	return 0;
}

 map 依然不允许数据冗余,如果需要插入重复的数据,则需要使用 multimap

map 插入操作返回值是一个 pair ,因为既要表示是否成功,也要返回插入成功的迭代器 

map 中 find 和 count 跟 set 一样。 可以用来判断元素是否存在,find 返回迭代器,count 返回则是键值数。此外,map可以根据普通迭代器修改实值。

6.4 map - operator[ ]

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

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

operator[ ] 兼顾了这几种功能:插入、修改、插入+修改、查找。

6.5 map的特点

7. multimap 

multimap 允许键值出现冗余。 

由于 multimap 允许出现多个重复的键值,因此无法使用 operator[ ],因为 operator[ ] 无法确认调用者的意图 -> 不知道要返回哪个键 对应的实值。

除此此外 multimap  与 map 没有区别。

最后: 

想说明的是:multiset / multimap 用的较少,重点掌握 set / map 即可。


 

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

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

相关文章

dcoker+nginx解决前端本地开发跨域

步骤 docker 拉取nginx镜像跑容器 并配置数据卷nginx.conf nginx.conf文件配置 这里展示server server {listen 80;listen [::]:80;server_name localhost;#access_log /var/log/nginx/host.access.log main;location / {# 当我们访问127.0.0.1:8028就会跳转到ht…

软件2班20240415

快速引用类选择器 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevi…

二进制离散无记忆对称信道

目录 引言 二进制离散无记忆对称信道 引言 在无线通信中&#xff0c;信源与信宿是分开的&#xff0c;两者间的通信环境的复杂度通常会随着距离 的增加而提升。信道是用来连接信源与信宿的媒介。信源与信宿之间的信息传递则需要 借助于信道&#xff0c;因此信道质量的优劣通常…

移动端web适配方案

以下是移动端适配的多个方案&#xff0c;也可以说说你是怎么做的。 正文 自适应&#xff1a;根据不同的设备屏幕大小来自动调整尺寸、大小 响应式&#xff1a;会随着屏幕的实时变动而自动调整&#xff0c;是一种更强的自适应 为什么要做移动端适配&#xff1f; 目前市面上…

【深度剖析】曾经让人无法理解的事件循环,前端学习路线

先自我介绍一下&#xff0c;小编浙江大学毕业&#xff0c;去过华为、字节跳动等大厂&#xff0c;目前阿里P7 深知大多数程序员&#xff0c;想要提升技能&#xff0c;往往是自己摸索成长&#xff0c;但自己不成体系的自学效果低效又漫长&#xff0c;而且极易碰到天花板技术停滞…

Redis入门到通关之ZSet命令

文章目录 ⛄概述⛄常见命令有⛄RedisTemplate API❄️❄️ 向集合中插入元素&#xff0c;并设置分数❄️❄️向集合中插入多个元素,并设置分数❄️❄️按照排名先后(从小到大)打印指定区间内的元素, -1为打印全部❄️❄️获得指定元素的分数❄️❄️返回集合内的成员个数❄️❄…

最优算法100例之49-链表环-计算环的长度

专栏主页:计算机专业基础知识总结(适用于期末复习考研刷题求职面试)系列文章https://blog.csdn.net/seeker1994/category_12585732.html 题目描述 定义两个指针,一个指针走两步,一个指针走一步,第一次相遇时开始计数,第二次相遇时停止计数,最后计数器的值就是环的长度…

STM32H7上实现AD5758驱动

目录 概述 1 下载ADI 5758 Demo 2 AD5758驱动的移植 2.1 使用STM32CubeMX创建工程 2.2 接口函数实现 2.2.1 驱动接口列表 2.2.2 函数实现 2.2.3 修正ad5758驱动 3 AD5758应用程序 3.1 编写测试程序 3.1.1 配置参数结构 3.1.2 配置参数函数 3.1.3 读取参数函数 3.…

【max材质addtive叠加模式特效渲染不出通道的解决办法】

max材质addtive叠加模式特效渲染不出通道的解决办法 2021-12-22 18:15 max的scanline扫描线&#xff0c;vray渲染可以&#xff0c;红移不行(只支持它自己的材质&#xff0c;它自己的材质没有additive模式)。据说mr是可以的。 右侧的球体使用附加不透明度。 附加不透明度通过将…

CentOS:执行make命令时报错g++: Command not found

报错截图&#xff1a; 其实很简单只需要安装一下 yum -y install gcc automake autoconf libtool make yum install gcc gcc-c

​LeetCode解法汇总2924. 找到冠军 II

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 一场比赛中共有 n 支队伍&#xff0c;按从…

J垃圾回收

J垃圾回收 1 概述2 方法区的回收3 如何判断对象可以回收3.1 引用计数法3.2 可达性分析法 4 常见的引用对象4.1 软引用4.2 弱引用4.3 虚引用4.4 终结器引用 5 垃圾回收算法5.1 垃圾回收算法的历史和分类5.2 垃圾回收算法的评价标准5.3 标记清除算法5.4 复制算法5.5 标记整理算法…

【深入理解】width 的默认值,2024年最新面试复盘

先自我介绍一下&#xff0c;小编浙江大学毕业&#xff0c;去过华为、字节跳动等大厂&#xff0c;目前阿里P7 深知大多数程序员&#xff0c;想要提升技能&#xff0c;往往是自己摸索成长&#xff0c;但自己不成体系的自学效果低效又漫长&#xff0c;而且极易碰到天花板技术停滞…

如何使用pytorch进行图像分类

如何使用pytorch进行图像分类https://featurize.cn/notebooks/5a36fa40-490e-4664-bf98-aa5ad7b2fc2f

实时传输,弹性优先——物联网通讯打造数据上传新标杆

随着信息技术的飞速发展&#xff0c;物联网技术已经成为连接物理世界和数字世界的桥梁。在物联网领域&#xff0c;数据上传的速度、稳定性和灵活性是评价通讯技术优劣的重要指标。近年来&#xff0c;物联网通讯在实时传输、弹性优先方面取得了显著进展&#xff0c;为数据上传树…

224 基于matlab的优化工具箱优化函数

基于matlab的优化工具箱优化函数&#xff0c; 此工具箱中提供的算法包括&#xff1a; 灰狼优化器&#xff08;GWO&#xff09;&#xff0c;蚂蚁狮子优化器&#xff08;ALO&#xff09;&#xff0c;多功能优化器&#xff08;MVO&#xff09;&#xff0c;蜻蜓算法&#xff08;DA&…

4.15 网络编程

思维导图 #include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <pthread.h> #include <semaphore.h> #inclu…

定时器、PWM定时器、UART串口通信

我要成为嵌入式高手之4月15日ARM第八天&#xff01;&#xff01; ———————————————————————————— 定时器 S3C2440A 有 5 个 16 位定时器。其中定时器 0、1、2 和 3 具有脉宽调制&#xff08;PWM&#xff09;功能。定时器 4 是一个无 输出引脚的内部…

【无标题】系统思考—智慧共赢座谈会

第432期JSTO—“智慧共赢座谈会”精彩回顾 我们身处一个快速变化的世界&#xff0c;其中培训和咨询行业也不断面临新的挑战和机遇。为了紧跟这些变革&#xff0c;我们邀请了行业专家与合作伙伴深入探讨在培训、交付和销售过程中遇到的难题。 本次座谈会的亮点之一是我们科学上…

rhce day1

一 . 在系统中设定延迟任务要求如下 在系统中建立 easylee 用户&#xff0c;设定其密码为 easylee 延迟任务由 root 用户建立 要求在 5 小时后备份系统中的用户信息文件到 /backup 中 确保延迟任务是使用非交互模式建立 确保系统中只有 root 用户和 easylee 用户可以执行延…