《map和set的使用介绍》

引言：

上次我们学习了第一个高阶数据结构—二叉搜索树，趁热打铁，今天我们就再来学习两个数据结构—map和set。

一：序列式容器和关联式容器

前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本章节我们要学习的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

二：set系列的使用

1. set和multiset 的参考文档：

set / multiset的参考文档：

2. set类的介绍：

set的声明如下，T就是set底层关键字的类型

  1. set默认要求T⽀持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数。
    2.·set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
  2. 一般情况下，我们都不需要传后两个模版参数。
  3. set底层是用红黑树实现，增删查效率是O(logN) ，迭代器遍历是走的搜索树的中序，所以是有序的。
  4. 前面部分我们已经学习了vector/list等容器的使用，STL容器接口设计，高度相似，所以这里我们就不再一个接口一个接口的介绍，只是挑比较重要的接口进行介绍。
    template < class T,
    class Compare = less<T>,
    class Alloc = allocator<T> > class set;

3. set的构造和迭代器

（1）构造函数：

介绍文档：
set的构造我们关注以下几个接口即可。
set支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序，支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

代码演示：

(1) 无参默认构造
explicit set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
(2) 迭代器区间构造
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
(3) 拷贝构造
set (const set& x);
(5) initializer 列表构造
set (initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());

(2) 迭代器：

begin():返回指向第一个数据的迭代器。
end():返回最后一个数据下一个位置的迭代器。
cbegin():返回最后一个元素的迭代器。
cend():返回第一个数据的前一个位置的迭代器。
set的迭代器是一个双向迭代器
iterator -> a bidirectional iterator to const value_type

  1. 正向迭代器
    iterator begin();
    iterator end();
  2. 反向迭代器
    reverse_iterator rbegin();
    reverse_iterator rend();

4. set的增删查：

（1）插入：

insert函数

代码演示：

在这里插入图片描述

（2）查找：
  1. find(): 查找val，返回val所在的迭代器，没有找到返回end()。
  2. count():查找val，返回Val的个数。
代码演示：

在这里插入图片描述

（3）删除：
  1. iterator erase (const_iterator position): 删除一个迭代器位置的值。
  2. size_type erase (const value_type& val):删除val，不存在返回0，存在返回1。
  3. iterator erase (const_iterator first, const_iterator last):删除一段迭代器区间的值。
代码演示：

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

（4） lower_bound 和 upper_bound
  1. lower_bound:返回大于等val位置的迭代器。
  2. upper_bound:返回大于val位置的迭代器。

注：因此借助这两个接口就可以得到一段左闭右开的区间。

代码演示：

在这里插入图片描述

5. insert 和迭代器遍历使用样例：

在这里插入图片描述

在这里插入图片描述
注：这里的范围for我们写成了引用的形式，是为了提高效率。

6. find和erase的使用样例：

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

在这里插入图片描述
注：这是我们借助count间接实现的查找。

算法库中的find和set中的find对比：

在这里插入图片描述

7. multiset和set的差异

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，那么
insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

8. 牛刀小试：

（1）题目描述：

在这里插入图片描述

代码解决：
方法一-暴力匹配：

先将两个数组通过set来去重，之后遍历其中一个来借助count来判断是否有交集。
在这里插入图片描述

方法二-双指针：

该解法的思路是在去重＋升序排序后的基础上来遍历两个容器
定义两个指针p1，p2分别遍历两个set

  1. 小的那个++。
  2. 相等的话就存下来，p1++，p2++。
  3. 当其中一个容器遍历完之后，就结束、
    为什么这样是对的呢？
    因为如果其中一个小的话，由于数据是升序的，因此当前必不可能为交集，若存在交集的话只可能在它之后，因此往后走。
    在这里插入图片描述
题目传送门：349. 两个数组的交集

三： map系列的使用

1. map 和multimap的介绍文档：

map 和multimap的介绍文档:

2. map类的介绍：

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，map默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是，迭代器遍历是走的中序，所以是按key有序顺序遍历的。O(logN） ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。

template < class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key,T> > > class map;

3. pair类型介绍：

map底层的红黑树节点中的数据，使用pair<Key,T>存储键值对数据。
pair:
typedef pair<const Key, T> value_type;
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)
{}
template<class U, class V>
pair (const pair<U,V>& pr): first(pr.first), second(pr.second)
{}
};
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}
上面是pair的底层结构，实质上就是一个类模版的结构体。先这么理解即可。

思考：为什么map里面要用pair呢？

这是因为map里面是存储两个数据，如果你单独分开存两个数据的话，是没办法解引用的，因为解引用只能拿到一个数据，用pair的话，解引用会拿到pair类型的数据，之后可以通过pair类型的性质来拿到两个数据。

4. map的构造和迭代器：

(1) 构造函数：

map的构造函数介绍文档：
map的构造我们关注以下几个接口即可。
map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

(1) 无参默认构造
explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
(2) 迭代器区间构造
template <class InputIterator>
map (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
(3) 拷贝构造
map (const map& x);
(4) initializer 列表构造
map (initializer_list<value_type> il,

（2）迭代器：
  1. begin():返回指向第一个数据的迭代器。
  2. end():返回最后一个数据下一个位置的迭代器。
  3. cbegin():返回最后一个元素的迭代器。
  4. cend():返回第一个数据的前一个位置的迭代器。

map的迭代器也是⼀个双向迭代器
iterator -> a bidirectional iterator to const value_type

  1. 正向迭代器
    iterator begin();
    iterator end();
  2. 反向迭代器
    reverse_iterator rbegin();
    reverse_iterator rend();

5. map 的增删查

（1）插入：

insert介绍文档：

代码演示：

在这里插入图片描述

（2）查找：
  1. find():查找k，返回k所在的迭代器，没有找到返回end()。
  2. count():查找k，返回k的个数。
代码演示：

在这里插入图片描述

（3） 删除：
  1. iterator erase (const_iterator position):删除⼀个迭代器位置的值。
  2. size_type erase (const key_type& k):删除k，k存在返回0，存在返回1。
  3. iterator erase (const_iterator first, const_iterator last:删除一段迭代器区间的值。
（4） lower_bound 和 upper_bound
  1. lower_bound:返回大于等k位置的迭代器。
  2. upper_bound:返回大于k位置的迭代器。
代码演示：

在这里插入图片描述
注：这里默认是按照第一个关键字来比较的。

6. map的数据修改

前面提到map支持修改mapped_type数据，不支持持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口
需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型
typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。

7.map的迭代器和[]功能样例：

在这里插入图片描述
其实这里的代码还可以这样写：
在这里插入图片描述
这样写的话，对于已经存在的数据的修改大家都没问题，但是一些同学可能会疑惑数据第一次出现的时候是怎么统计的呢？
其实在数据第一次出现的时候，会先将这个数据插入，这时候第二个参数就是一个默认值0，之后在进行修改。

operator[] 底层解释：

要搞清楚operator[]的底层就需要先从insert入手。
在这里插入图片描述
可以看到insert的第一个实现形式的返回值是pair类型，由迭代器和bool值组成。
在这里插入图片描述

我们再来看第一种形式的返回值的解读：
这里说的是当该数据是第一次插入的话，就会返回指向这个新插入数据的迭代器，否则就会返回map中指向该数据的迭代器，第二个bool值，如果数据是第一次插入的新数据就会返回true，否则就是返回false。
因此operator[]其实大概就是这样实现的：

V& operator[](const K& key)
{
pair<iteraotr,bool> ret = insert(key);
return ret.first->second;
}

8. multimap和map的差异

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全⼀样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。

9. 牛刀小试：

（1）题目描述：

在这里插入图片描述

（2）思路分析：

首先从题目就能知道这是一个经典的TopK问题，但是与之前不同的是这个是双元素的，因此我们就得用pair来存储，所以我们的思路就是先用map来统计各单词的出现次数，再创建小根堆来维护前k个出现次数最多的单词，之后用vector来存储结果，但由于我们创建的是小根堆，因此在返回结果的时候还需要进行逆置。

（3）代码实现：

在这里插入图片描述

（4）题目传送门：

692. 前K个高频单词

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

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

相关文章

C#学习日记

C#学习日记

命名空间 知识点一 命名空间基本概念 概念 命名空间是用来组织和重用代码的 作用 就像是一个工具包&#xff0c;类就像是一件一件的工具&#xff0c;都是申明在命名空间中的 知识点二 命名空间的使用 基本语法 namespace 命名空间名 {类类 } namespace MyGame {class GameO…
阅读更多...
OSI网络通信模型详解

OSI网络通信模型详解

OSI 模型就是把这整个过程拆解成了 7 个明确分工的步骤&#xff0c;每一层只负责自己那一摊事儿&#xff0c;这样整个系统才能顺畅运转&#xff0c;出了问题也容易找到“锅”在谁那。 核心比喻&#xff1a;寄快递 &#x1f4e6; 想象你要把一份重要的礼物&#xff08;你的数据…
阅读更多...
高并发网络通信Netty之空轮询问题

高并发网络通信Netty之空轮询问题

一、问题背景 在 NioEventLoop 事件循环中&#xff0c;Selector 一次次 select() 返回为 0&#xff0c;且没有事件被触发&#xff0c;形成空转&#xff0c;导致 CPU 占用 100%&#xff0c;系统资源白白浪费。这种情况尤其在 高并发、连接数多、IO事件少 的场景下更容易出现。 …
阅读更多...
Nginx+Tomcat负载均衡群集

Nginx+Tomcat负载均衡群集

一、NginxTomcat 负载均衡、动静分离 1、Tomcat 简介 名称由来&#xff1a;Tomcat 最初由 Sun 的软件构架师詹姆斯・邓肯・戴维森开发&#xff0c;后变为开源项目并由 Sun 贡献给 Apache 软件基金会。因 O’Reilly 开源项目常以动物命名相关书籍&#xff0c;他希望动物能自我照…
阅读更多...
Linux下nginx访问路径页面

Linux下nginx访问路径页面

第一步&#xff1a;通过Xshell在虚拟机中下载nginx sudo apt-get install nginx 第二步&#xff1a;进入nginx配置页面 cd /etc/nginx 我这里创建了一个html文件夹 在进入去创建页面并且重新加载 boahuboahu-VMware-Virtual-Platform:/$ cd /etc/nginx boahuboahu-VMware-Vir…
阅读更多...
python实战项目76:51job数据采集与分析

python实战项目76:51job数据采集与分析

python实战项目76:51job数据采集与分析 一、数据采集二、数据预处理2.1 导入相关库、读取数据2.2 查看数据2.3 处理数据、删除重复值、删除空值2.4 处理薪资水平字段数据三、数据可视化3.1 不同公司规模招聘岗位数量分布3.2 不同公司性质招聘岗位数量分布3.3 不同年限要求招聘岗…
阅读更多...
OPENGLPG第九版学习 - 纹理与帧缓存 part1

OPENGLPG第九版学习 - 纹理与帧缓存 part1

文章目录 6.1 纹理综述6.2 基木纹理类型6.3 创建并初始化纹理代理纹理 6.4 指定纹理数据6.4.1 显式设置纹理数据将静态数据载入到纹理对象 6.4.2 从缓存(目标对象GL_PIXEL_UNPACK_BUFFER)中加载纹理6.4.3 从文件加载图像(DDS为例)读取一个图像文件并返回内存中的纹素数据将纹素…
阅读更多...
Redis 持久化机制详解：RDB、AOF 原理与面试最佳实践（AOF篇）

Redis 持久化机制详解：RDB、AOF 原理与面试最佳实践（AOF篇）

在上一章我们深入学习了 Redis 中重要的数据持久化机制 ——RDB&#xff08;Redis Database&#xff09;&#xff0c;了解了其通过周期性快照将数据以二进制文件形式保存到磁盘的原理&#xff0c;包括触发条件、文件结构以及优缺点等核心内容。 Redis 持久化机制详解&#xff…
阅读更多...
NumPy数组操作详解

NumPy数组操作详解

在现代数据科学与工程计算领域&#xff0c;高效的数组操作是实现复杂算法的基础。NumPy作为Python的核心科学计算库&#xff0c;提供了一套强大的多维数组对象及操作机制。本文深入探讨NumPy数组的各种操作&#xff0c;旨在帮助读者全面掌握其功能与应用场景。 数组创建与属性查…
阅读更多...
ER图：数据库设计的可视化语言 - 搞懂数据关系的基石

ER图：数据库设计的可视化语言 - 搞懂数据关系的基石

在数据库设计和数据建模领域&#xff0c;ER图&#xff08;实体-关系图&#xff09; 绝对是最基础、最核心的可视化工具之一。它用最直观的方式描绘了现实世界中的数据及其关系&#xff0c;是构建可靠数据库的蓝图。今天&#xff0c;我们就来聊聊这个技术基石。 本文来自「大千A…
阅读更多...
图像特征检测算法ORB

图像特征检测算法ORB

ORB&#xff08;Oriented FAST and Rotated BRIEF&#xff09;是一种在计算机视觉领域广泛应用的特征检测与描述算法。 算法原理 特征点检测 &#xff1a;ORB 算法结合了 FAST&#xff08;Features from Accelerated Segment Test&#xff09;特征点检测方法和 Harris 特征点检…
阅读更多...
docker 目录更改，必须做数据迁移才能启动

docker 目录更改，必须做数据迁移才能启动

要修改 Docker 镜像的存储位置 并迁移数据&#xff08;如从 /var/lib/docker 迁移到 /mnt/data/docker&#xff09;&#xff0c;需要以下步骤&#xff1a; 1. 停止 Docker 服务 在修改配置和迁移数据前&#xff0c;先停止 Docker 服务&#xff1a; sudo systemctl stop docke…
阅读更多...
最新文章

Copyright @ 2022~2023