C++中的STL数据结构

内容来自:代码随想录:哈希表理论基础

1.常见的三种哈希结构

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构
数组
set (集合)
map(映射)
在C++中,set 和 map 分别提供以下三种数据结构,其底层实现以及优劣如下表所示:
在这里插入图片描述
std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。
在这里插入图片描述

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。

当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

那么再来看一下map ,在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。

其他语言例如:java里的HashMap ,TreeMap 都是一样的原理。可以灵活贯通。

虽然std::set、std::multiset 的底层实现是红黑树,不是哈希表,std::set、std::multiset 使用红黑树来索引和存储,不过给我们的使用方式,还是哈希法的使用方式,即key和value。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。 map也是一样的道理。

这里在说一下,一些C++的经典书籍上 例如STL源码剖析,说到了hash_set hash_map,这个与unordered_set,unordered_map又有什么关系呢?

实际上功能都是一样一样的, 但是unordered_set在C++11的时候被引入标准库了,而hash_set并没有,所以建议还是使用unordered_set比较好,这就好比一个是官方认证的,hash_set,hash_map 是C++11标准之前民间高手自发造的轮子。
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

HTTPS(超文本传输安全协议)被恶意请求该如何处理。

HTTPS(超文本传输安全协议)端口攻击通常是指SSL握手中的一些攻击方式,比如SSL握手协商过程中的暴力破解、中间人攻击和SSL剥离攻击等。 攻击原理 攻击者控制受害者发送大量请求,利用压缩算法的机制猜测请求中的关键信息&#xf…

什么是SSD型云服务器?

​  SSD云服务器是一种使用固态硬盘代替传统HDD进行存储的虚拟机。SDD 使用闪存单元来存储数据,与云计算技术相结合,形成强大且高效的存储解决方案,可以随时随地访问。 SSD云服务器如何工作? SSD云服务器是利用虚拟化和云计算技术创建的。…

ElementUI table表格组件实现双击编辑单元格失去焦点还原,支持多单元格

在使用ElementUI table表格组件时有时需要双击单元格显示编辑状态,失去焦点时还原表格显示。 实现思路: 在数据中增加isFocus:false.控制是否显示在table中用cell-dblclick双击方法 先看效果: 上源码:在表格模板中用scope.row…

最新Unity游戏主程进阶学习大纲(2个月)

过完年了,很多同学开始重新规划自己的职业方向,找更好的机会,准备升职或加薪。今天给那些工作了1~5年的开发者梳理”游戏开发客户端主程”的学习大纲,帮助大家做好面试准备。适合Unity客户端开发者。进阶主程其实就是从固定的几个方面搭建好完整的知识体…

python编程中模块的调用方法

模块,就是制造大型程序的“零件"。这些零件可以是外购的也可以是“自造”的。它们的使用方法很简单,就是“拿来”——import. “拿来”模块的方法有from***import*** 和import***,宗旨就是“拿来”——import. 对不对?

Vision Transfomer系列第二节---Tricks测试

目录 学习式和固定式位置编码测试dropout的作用测试block深度的作用测试embeding维度大小的作用测试多头的作用测试Overlap Patch的作用 学习式和固定式位置编码测试 主要测试无位置编码\可学习位置编码和固定式位置编码的训练效果: 其中固定式位置编码采用之前博客的正余弦位…

架构设计:数据库扩展

引言 随着业务的发展和用户规模的增长,数据库往往会面临着存储容量不足、性能瓶颈等问题。为了解决这些问题,数据库扩展成为了一种常见的解决方案。在数据库扩展的实践中,有许多不同的策略和技术可供选择,其中包括水平拆分、垂直…

高通 Android 12 Settings不显示版本号问题

1、最近项目遇到一个奇葩问题,编译系统版本号不见了? 2、一开始我想着可能是自己代码没有make clean结果编译几个小时,然后烧录固件发现还是未生效。 3、然后这时候我又去看git log review最近修改也没有太大发现(待定&#xff…

介绍 CI / CD

目录 一、介绍 CI / CD 1、为什么要 CI / CD 方法简介 1、持续集成 2、持续交付 3、持续部署 2、GitLab CI / CD简介 3、GitLab CI / CD 的工作原理 4、基本CI / CD工作流程 5、首次设置 GitLab CI / CD 6、GitLab CI / CD功能集 一、介绍 CI / CD 在本文档中&#x…

开源 - 一款可自定义的在线免杀平台|过x60、wd等

免责声明:本工具仅供安全研究和教学目的使用,用户须自行承担因使用该工具而引起的一切法律及相关责任。作者概不对任何法律责任承担责任,且保留随时中止、修改或终止本工具的权利。使用者应当遵循当地法律法规,并理解并同意本声明…

K线实战分析系列之二:伞形线

K线实战分析系列之二:伞形线 一、伞形线二、锤子线三、上吊线四、锤子线和上吊线的特征 一、伞形线 可以是看涨信号,也可以是看跌信号,具体要看它处于趋势的哪个位置 二、锤子线 出现在下行趋势中就叫锤子线锤子线是阳线看涨意义更大一点市…

petalinux_zynq7 驱动DAC以及ADC模块之四:python实现http_api

前文: petalinux_zynq7 C语言驱动DAC以及ADC模块之一:建立IPhttps://blog.csdn.net/qq_27158179/article/details/136234296petalinux_zynq7 C语言驱动DAC以及ADC模块之二:petalinuxhttps://blog.csdn.net/qq_27158179/article/details/1362…

【办公类-16-10-01】“2023下学期 中4班 自主游戏观察记录(python 排班表系列)

背景需求 上学期的周安排里,每班每周的自主游戏会轮到多个不同的内容 因此在每周的自主游戏观察有2次记录,观察的项目可以写不一样的, 如一位老师写沙水游戏,另一位写表演游戏 本学期,中班的自主游戏全部是户外的&am…

ApexRBp在线粒子传感器在电动汽车电池制造的应用

电动汽车电池的崛起与颗粒污染的挑战 随着电动汽车(EV)市场的迅速扩张,对高性能锂离子电池的需求也急剧增加。这些电池不仅是EV的心脏,更是推动其前行的核心动力。然而,在电池制造的每一个环节,都需要对多…

2024-02-21 作业

作业要求: 复习课上内容 //已完成结构体字节对齐,64位没做完的做完,32位重新都做一遍,课上指定2字节对齐的做一遍,自己验证 //已完成两种验证大小端对齐的代码写一遍复习指针内容 //已完成完善顺序表已写出的…

网络安全笔记总结

IAE引擎 1.深度检测技术--DFI和DPI技术 DFI和DPI都是流量解析技术,对业务的应用、行为及具体信息进行识别,主要应用于流量分析及流量检测。 DPI:深度包检测技术 DPI是一种基于应用层的流量检测和控制技术,对流量进行拆包&#x…

海外媒体发稿:链游媒体宣发推广7种有效策略解析-华媒舍

随着区块链技术的不断发展,链游(区块链游戏)已经成为了游戏市场中备受瞩目的一部分。仅仅开发出一款出色的链游并不足以成功,而有效的宣发推广策略则是不可或缺的。 本文将介绍7种有效的链游媒体宣发推广策略,帮助您了…

机器视觉【3】非线性求解相机几何参数

线性求解相机几何参数的缺点 上一章节介绍学习了(DLT)线性求解相机几何参数,了解到线性求解法当中比较明显的缺点: 没有考虑到镜头畸变的影响不能引入更多的约束条件融入到DLT算法当中优化最关键的是,代数距离并不是…

测试环境搭建整套大数据系统(六:搭建sqoop)

一:下载安装包 https://archive.apache.org/dist/sqoop/ 二:解压修改配置。 tar -zxvf sqoop-1.4.7.bin__hadoop-2.6.0.tar.gz -C /opt cd /opt mv sqoop-1.4.7.bin__hadoop-2.6.0/ sqoop-1.4.7修改环境变量 vi /etc/profile#SQOOP_HOME export SQOOP_…

Python 在Word中创建表格并填入数据、图片

在Word中,表格是一个强大的工具,它可以帮助你更好地组织、呈现和分析信息。本文将介绍如何使用Python在Word中创建表格并填入数据、图片,以及设置表格样式等。 Python Word库: 要使用Python在Word中创建或操作表格,需…