引言：

上次我们学习了第一个高阶数据结构—二叉搜索树，趁热打铁，今天我们就再来学习两个数据结构—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.pswp.cn/pingmian/86369.shtml
繁体地址，请注明出处：http://hk.pswp.cn/pingmian/86369.shtml
英文地址，请注明出处：http://en.pswp.cn/pingmian/86369.shtml

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

相关文章

PostgreSQL（二十六）分区表管理

PostgreSQL（二十六）分区表管理

目录 一、分区表特点 1、概念&#xff1a; 2、好处&#xff1a; 3、特点&#xff1a; 二、范围分区介绍 1、简介 2、范围分区实验&#xff1a; 三、list分区介绍 1、简介 2、list分区表实验 四、hash分区介绍 1、简介 2、hash分区表实验 五、混合分区介绍 1、简…
阅读更多...
概率论中的生日问题，违背直觉？如何计算? 以及从人性金融的角度分析如何违背直觉的？

概率论中的生日问题，违背直觉？如何计算? 以及从人性金融的角度分析如何违背直觉的？

一、生日问题的概率计算&#xff1a;为何23人就有50%概率撞生日&#xff1f; 1. 问题背景与直觉矛盾 生日问题指&#xff1a;在n个人中&#xff0c;至少有两人生日相同的概率超过50%时&#xff0c;n的最小值是多少&#xff1f; 直觉判断&#xff1a;因一年有365天&#xff0c…
阅读更多...
Qt for WebAssembly官方说明文档

Qt for WebAssembly官方说明文档

链接 Qt for WebAssembly | Qt 5.15
阅读更多...
前端自主实现将vue页面转为pdf文件下载

前端自主实现将vue页面转为pdf文件下载

1.vue 转 PDF 在 Vue 项目中将 HTML 页面转换为 PDF 文件是一个常见需求&#xff0c;特别是在需要生成报告或打印页面时。本文将介绍如何使用 html2canvas 和 jspdf 库实现这一功能。 2.安装依赖 首先&#xff0c;我们需要安装两个库&#xff1a;html2canvas 和 jspdf 。可以…
阅读更多...
TCP 坚持定时器详解：原理、配置与最佳实践​

TCP 坚持定时器详解：原理、配置与最佳实践​

一、TCP 坚持定时器基础原理 1.1 坚持定时器的设计目的 TCP 坚持定时器 (TCP Persist Timer) 是 TCP 协议中用于处理接收窗口为零情况的重要机制&#xff0c;其核心设计目的是防止 TCP 连接在窗口更新 ACK 丢失时陷入死锁状态。当 TCP 连接的接收方通告一个窗口大小为 0 的 A…
阅读更多...
大厂测开实习和小厂开发实习怎么选

大厂测开实习和小厂开发实习怎么选

先说选择&#xff0c;这个可以百分百确定选大厂&#xff0c;title很重要。 要想弄清楚那个选择对自己最有利&#xff0c;可以思考下实习的意义是什么&#xff1f; 实习无非就是给简历加分&#xff0c;拿到好offer&#xff0c;高薪offer。 那这就需要思考&#xff0c;简历怎么让…
阅读更多...
Unity中的urp和普通的标准渲染管线区别在哪

Unity中的urp和普通的标准渲染管线区别在哪

Unity中的URP&#xff08;Universal Render Pipeline&#xff09;与内置标准渲染管线&#xff08;Built-in Render Pipeline&#xff09;的区别深刻反映了Unity渲染技术的演进方向。以下从架构、性能、功能、工作流等多个维度进行深度分析&#xff1a; 1. 底层架构与设计哲学 标…
阅读更多...
Vscode 编写Markdown支持 plantuml书写

Vscode 编写Markdown支持 plantuml书写

1&#xff1a; 下载PlantUml 插件&#xff1a; 2&#xff1a; 安装java https://www.oracle.com/java/technologies/downloads/ 3&#xff1a; 安装Graphviz https://graphviz.org/download/ 4&#xff1a; 下载plantuml.jar https://plantuml.com/zh/download 5&…
阅读更多...
设计模式(C++/Qt)-工厂模式

设计模式(C++/Qt)-工厂模式

在软件开发中&#xff0c;对象创建是基础但关键的任务——工厂模式提供了一种优雅的解决方案&#xff0c;让您的代码摆脱硬编码的依赖关系 一、为什么需要工厂模式&#xff1f; 在C/Qt开发中&#xff0c;我们经常面临这样的困境&#xff1a; 对象创建逻辑分散在代码各处新增…
阅读更多...
Pydantic 模型

Pydantic 模型

本文将详细介绍 Pydantic 模型 和 BaseModel 的核心概念&#xff0c;并通过实际代码示例如何从零开始编写自己的 Pydantic 模型。 1. Pydantic 是什么&#xff1f; Pydantic 是一个 Python 库&#xff0c;主要用于&#xff1a; 数据验证&#xff1a;确保输入数据符合预期的类…
阅读更多...
【Unity智能模型系列】MediaPipeUnityPlugin 实现人脸数据获取

【Unity智能模型系列】MediaPipeUnityPlugin 实现人脸数据获取

目录 一、MediaPipeUnity 简介 二、MediaPipeUnity 的核心组成 1. Graph 构建系统 2. 解决方案类（Solution） 3. 解释注释Annotation 系统 三、MediaPipeUnity 的典型使用流程 四、典型示例解析 1、案例 Face Detection图形人脸检测 2、案例 Face Detection图形人脸检…
阅读更多...
iOS App 上架步骤解析：适合资源有限团队的上架流程与注意事项

iOS App 上架步骤解析：适合资源有限团队的上架流程与注意事项

对于不少创业型或初创阶段的开发团队来说&#xff0c;人员配置紧凑、设备有限是常态。在这种背景下&#xff0c;完成一次合规、高效的iOS应用发布往往不是技术难点&#xff0c;而是流程协同与资源调配的问题。 我们是一支5人团队&#xff0c;开发一款社交类工具型App&#xff…
阅读更多...
Redis雪崩、穿透、击穿原理及解决方案

Redis雪崩、穿透、击穿原理及解决方案

以下是 Redis 缓存穿透、击穿与雪崩的原理及解决方案的深度解析&#xff0c;结合工业级实践整理&#xff1a; &#x1f50d; ‌一、问题原理与区别‌ ‌问题类型‌‌触发条件‌‌核心特征‌‌危害‌‌缓存穿透‌查询‌不存在的数据‌绕过缓存直击数据库&#xff0c;导致无效查…
阅读更多...
DFX 动态重构的概念和实现

DFX 动态重构的概念和实现

DFX 动态重构的概念和实现 背景介绍 本文内容当前仅限于XILINX或者和XILINX具有相同结构的FPGA器件。 FPGA 技术提供了在现场进行编程和重新编程的灵活性&#xff0c;而无需通过重新制造流程来实现设计修改。动态功能交换&#xff08;Dynamic Function eXchange, DFX&#x…
阅读更多...
hutool 导出数据报错：org.apache.poi.openxml4j.exceptions.OpenXML4JRuntimeException

hutool 导出数据报错：org.apache.poi.openxml4j.exceptions.OpenXML4JRuntimeException

Excel 导出报错 org.apache.poi.openxml4j.exceptions.OpenXML4JRuntimeException: Fail to save: an error occurs while saving the package : The part /docProps/core.xml failed to be saved in the stream with marshaller org.apache.poi.openxml4j.opc.internal.marsh…
阅读更多...
【学习】win 本地部署qwen3

【学习】win 本地部署qwen3

这里写自定义目录标题 环境搭建下载Ollama安装olama修改模型下载位置&#xff08;可以不设置&#xff09;通过ollama下载/启动模型常用命令其他 环境搭建 下载Ollama 安装olama 默认安装位置是c盘 安装到指定位置使用以下命令 OllamaSetup.exe /DIR"d:\Ollama"修改…
阅读更多...
python的__init__.py

python的__init__.py

在此之前先确认一个概念是否弄清 模块命名空间 1. 目录结构 假设你有以下结构&#xff1a; testpkg/__init__.pyfool.pymaybe.py内容如下&#xff1a; fool.py # testpkg/fool.py class Fool:passmaybe.py # testpkg/maybe.py class Maybe:pass__init__.py &#xff08…
阅读更多...
四核 A53+工业级存储：移远 SC200L 与 pSLC SD NAND 如何重构 T-BOX 性能边界？

四核 A53+工业级存储：移远 SC200L 与 pSLC SD NAND 如何重构 T-BOX 性能边界？

博客目录 一、移远 SC200L&#xff1a;T-BOX 的 “智慧大脑”二、米客方德 MKDN064GIL-ZA T-BOX&#xff1a;数据安全的坚固堡垒三、深度协同&#xff1a;拓展 T-BOX 应用边界 在车联网浪潮席卷而来的当下&#xff0c;T-BOX 作为汽车与外界交互的核心枢纽&#xff0c;其性能优劣…
阅读更多...
JavaEE-统一功能处理

JavaEE-统一功能处理

拦截器 实现强制登录的功能, 后端程序根据Session来判断⽤⼾是否登录, 但是实现⽅法是⽐较⿇烦的 需要修改每个接⼝的处理逻辑 需要修改每个接⼝的返回结果 接⼝定义修改, 前端代码也需要跟着修改 有没有更简单的办法, 统⼀拦截所有的请求, 并进⾏Session校验呢, 这⾥我们学…
阅读更多...
vscode运行c++文件和插件的方法

vscode运行c++文件和插件的方法

1.运行c文件全过程 VSCode运行C全教程-CSDN博客 按照以上的操作即可完成正常的配置流程。但是在运行我的文件时&#xff0c;总是出现终端和输出混乱的情况&#xff0c;我想要在终端中进行输入输出的话&#xff0c;需要加一个改动&#xff1a;设置--输入Run In Terminal--勾选…
阅读更多...
最新文章

Copyright @ 2022~2023