移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——14.哈希(1)

移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——14.哈希(1)

unordered系列关联式容器

在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到== l o g 2 N log_2 N log2N==,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好 的查询是,进行很少的比较次数就能够将元素找到,因此在C++11中,STL又提供了4个 u n o r d e r m a p \color{red}{unordermap} unordermap系列的关联式容器,这四个容器与红黑树结构的关联式容器使用方式基本类似,只是 其**底层结构不同**

unordered map 的图像结果

1. unordered_map

​ unordermap文档

unordered_map

unordered_map是一种关联容器,它存储的是键值对(key-value pairs),并且键是唯一的。它使用哈希表来快速查找键。

特点:
  • 键值对存储:每个元素是一个std::pair<const Key, T>,其中Key是键,T是对应的值。
  • 无序存储:元素在哈希表中是无序存储的,插入的顺序不保证元素的顺序。
  • 唯一键:同一个键只能存在一个,如果插入相同键,会覆盖原有键对应的值。
  • 时间复杂度:查找、插入、删除的平均时间复杂度是O(1),但在最坏情况下,复杂度可能退化为O(n),比如在哈希冲突严重的情况下。
常用操作:
  • 插入umap.insert({key, value})umap[key] = value
  • 查找umap.find(key) 返回迭代器,如果找不到则返回umap.end()
  • 删除umap.erase(key)umap.erase(迭代器)
  • 访问元素umap[key] 如果键不存在,会自动插入该键并赋值为T()(默认构造值)
  • 大小umap.size() 返回元素个数
适用场景

unordered_map适合需要频繁进行键值对查找、插入、删除的场景,特别是在不关心元素顺序的情况下。比如统计元素频次、缓存(cache)实现等。

2. unordered_map的接口说明

1.unordered_map的构造

函数声明功能介绍
unordered_map构造不同格式的unordered_map对象

2.unordered_map的容量

函数声明功能介绍
bool empty() const检测unordered_map是否为空
size_t size() const获取unordered_map的有效元素个数

3. unordered_map的迭代器

begin返回unordered_map第一个元素的迭代器
end返回unordered_map最后一个元素下一个位置的迭代器
cbegin返回unordered_map第一个元素的const迭代器
cend返回unordered_map最后一个元素下一个位置的const迭代器

4.unordered_map的元素访问!!!

函数声明功能介绍
operator[]返回与key对应的value,若没有key则插入一个,并返回value默认值

在这里插入图片描述

5.unordered_map的查询

iterator find(constK& key)返回key在哈希桶中的位置
size_t count(constK& key)返回哈希桶中关键码为key的键值对的个数

注意:**key是不能重复**的,因此count函数的返回值最大为1

6.unordered_map的修改操作

insert向容器中插入键值对
erase删除容器中的键值对
clear清空容器中有效元素个数
void swap(unordered map&)交换两个容器中的元素

在这里插入图片描述

3. unordered_set

unordered_set也是一个哈希容器,但它只存储唯一的键(没有值),也就是说它只关心元素是否存在,而不关心元素的具体值。

特点:
  • 元素唯一:集合中的每个元素是唯一的,不能包含重复元素。
  • 无序存储:元素以无序的方式存储,插入顺序不影响元素的排列顺序。
  • 哈希表实现:与unordered_map一样,unordered_set基于哈希表实现。
  • 时间复杂度:查找、插入、删除的平均时间复杂度是O(1),但在最坏情况下也可能退化为O(n)。
常用操作:
  • 插入uset.insert(element) 插入元素
  • 查找uset.find(element) 查找元素,返回迭代器,如果找不到则返回uset.end()
  • 删除uset.erase(element)uset.erase(迭代器)
  • 判断是否存在uset.count(element) 返回元素是否存在,存在返回1,不存在返回0
  • 大小uset.size() 返回集合中元素的个数
适用场景

unordered_set适合需要频繁进行集合操作的场景,比如元素去重、快速查找某个元素是否存在等。

4.小习题

https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/description/

class Solution {
public:int repeatedNTimes(vector<int>& nums) {int length = nums.size()/2;unordered_map<int, int> it;for (auto& e : nums) {it[e]++;}for (auto e : it) {if (e.second == length) {return e.first;}}return 1;//这里只是象征性地写一个return 1,不然会报错}
};

https://leetcode.cn/problems/uncommon-words-from-two-sentences/description/

在这里插入图片描述

class Solution {
public:vector<string> uncommonFromSentences(string s1, string s2) {vector<string> arr;vector<string> brr;vector<string> crr;string it;it.clear();for(auto e:s1){if(e==' '||e=='\0'){arr.push_back(it);it.clear();}elseit+=e;}arr.push_back(it);it.clear();map<string,int> a1;for(auto e:arr){a1[e]++;}for(auto e:s2){if(e==' '||e=='\0'){brr.push_back(it);it.clear();}elseit+=e;}brr.push_back(it);it.clear();map<string,int> a2;for(auto e:brr){a2[e]++;}auto it1=a1.begin();auto it2=a2.begin();while(it1!=a1.end()&&it2!=a2.end()){if(it1->first!=it2->first){if(it1->first<it2->first){if(it1->second==1)crr.push_back(it1->first);it1++;}else{if(it2->second==1)crr.push_back(it2->first);it2++;}}else{it1++;it2++;}}while(it1!=a1.end())
{if(it1->second==1)crr.push_back(it1->first);it1++;
}while(it2!=a2.end())
{if(it2->second==1)crr.push_back(it2->first);it2++;
}return crr;}
};

5.底层结构

unordered系列的关联式容器之所以效率比较高,是因为其底层使用了哈希结构

哈希概念:

顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素 时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即 O( l o g 2 N log_2 N log2N),搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一**映射**的关系,那么在查找时通过该函数可以很快找到该元素。

当向该结构中:

  • 插入元素 根据待插入元素的关键码,以此函数==计算出该元素的存储位置==并按此位置进行存放
  • 搜索元素 对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置 取元素比较,若关键码相等,则搜索成功

储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一**映射**的关系,那么在查找时通过该函数可以很快找到该元素。


3. 二者的对比:

特性unordered_mapunordered_set
存储内容键值对(key-value pairs)唯一元素(unique elements)
键是否唯一
时间复杂度平均O(1)(最坏O(n))平均O(1)(最坏O(n))
顺序保证无序无序
适用场景键值对的快速查找、插入、删除元素集合的快速查找、插入、删除

4. 小结:

  • 如果需要存储键值对并希望能够通过键快速访问相应的值,unordered_map是更好的选择。
  • 如果仅需要存储唯一的元素并希望进行集合操作(如查找、插入、删除),unordered_set更为合适。

两者的核心思想都是通过哈希函数来定位元素,从而提供快速的访问和操作。

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

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

相关文章

prompt learning

prompt learning 对于CLIP&#xff08;如上图所示&#xff09;而言&#xff0c;对其prompt构造的更改就是在zero shot应用到下游任务的时候对其输入的label text进行一定的更改&#xff0c;比如将“A photo of a{obj}”改为“[V1][V2]…[Vn][Class]”这样可学习的V1-Vn的token…

利用配置错误的负载均衡器,通过XSS窃取Cookies

引言 在本文中&#xff0c;我们将探讨一个涉及负载均衡器漏洞利用和跨站脚本攻击&#xff08;XSS&#xff09;来劫取应用程序Cookies的实际场景。由于保密协议的限制&#xff0c;我们将省略具体名称和截图&#xff0c;但我们会详细分析攻击过程及其影响。通过将负载均衡器的主…

MySQL中 truncate、drop和delete的区别

MySQL中 truncate、drop和delete区别 truncate 执行速度快&#xff0c;删除所有数据&#xff0c;但是保留表结构不记录日志事务不安全&#xff0c;不能回滚可重置自增主键计数器 drop 执行速度较快&#xff0c;删除整张表数据和结构不记录日志事务不安全&#xff0c;不能回…

LabVIEW示波器通信及应用

基于LabVIEW平台开发的罗德与施瓦茨示波器通信与应用系统实现了示波器的远程控制及波形数据的实时分析&#xff0c;通过TCP/IP或USB接口与计算机通信&#xff0c;利用VISA技术进行指令传输&#xff0c;从而实现高效的数据采集与处理功能。 项目背景 随着现代电子测试需求的日益…

WordPress 禁用上传媒体图片自动生成缩略图及多尺寸图片教程

一、在 设置-媒体-媒体设置 中几个尺寸大小的设置不勾选或设置为 0&#xff0c;如下图&#xff1a; 二、找到主题文件 function.php 文件&#xff0c;打开后&#xff0c;在 <?php 后面添加如下代码&#xff1a; function.php 文件路径一般为&#xff1a;WordPress网站根目录…

使用标注工具并跑通官方yolov8分割segment自己的数据集

1.下载标注工具用于打标签 使用标注工具&#xff0c;后面会用到智能标注 点击 创建AI多边形后命令行就自动下载对应的模型 单机要选中的图像就行&#xff0c;就可以智能选中&#xff0c;双击设置标签 依次标注所有图片 &#xff0c;最后保存成json格式的文件 2.使用labelme2y…

量化投资学习

1:投资定义就是付出一定的代价&#xff0c;期望能够得到一定汇报&#xff0c;可能会出现没有回报 2&#xff1a;投资分析流派 2.1:宏观策略分析法&#xff1a;从宏观经济大方向入手&#xff0c;再应用到具体股票也叫自上而下的研究方法&#xff0c;需要理解这个趋势的核心驱动…

【AI系统】AI 学习方法与算法现状

在人工智能&#xff08;AI&#xff09;的漫长历史中&#xff0c;我们见证了从早期的规则驱动系统到现代的机器学习模型的转变。AI的学习方法是其进步的核心&#xff0c;而算法现状则反映了当前技术的高度和未来的发展方向。 Ⅰ.AI 学习方法 AI的工作原理基于深度神经网络&…

ELK:Elasticsearch、Logstash、Kibana Spring Cloud Sleuth和Spring Cloud Zipkin

〇、虚拟机中docker安装elasticsearch 、Kibana、Logstash elasticsearch导入中文分词器 Logstash修改es数据库ip及创建索引名配置 一、elasticsearch数据库的结构 和mysql作比较&#xff0c;mysql中的数据库的二维表相当于es数据库的index索引结构&#xff1b;mysql数据库的二…

电容器放电的方法

对于小容量电容&#xff0c;可以直接短接两根线进行放电对于大容量电容&#xff0c;需要串联灯泡或者用电器进行放电。 大容量电容千万不能短接&#xff0c;否则容易伤到自己。 电容器放电的方法有以下几种&#xff1a; 1. 利用自放电放电&#xff1a;有些电容器在放电后&…

ScriptViz – 斯坦福大学推出的剧本可视化AI辅助工具

ScriptViz是什么 ScriptViz是由斯坦福大学研究人员推出的一款剧本可视化辅助工具&#xff0c;基于大型电影数据库MovieNet&#xff0c;根据剧本文本和对话检索出相匹配的电影画面&#xff0c;将编剧的文字描述转换成具体的视觉图像。工具提供对视觉元素的精确控制&#xff0c;…

刷题训练之多源 BFS

> 作者&#xff1a;დ旧言~ > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;熟练掌握多源 BFS算法。 > 毒鸡汤&#xff1a;学习&#xff0c;学习&#xff0c;再学习 ! 学&#xff0c;然后知不足。 > 专栏选自&#xff1a;刷…

mybatisPlus对于pgSQL中UUID和UUID[]类型的交互

在PGSQL中&#xff0c;有的类型是UUID和UUID[]这种类型&#xff0c;在mybatis和这些类型交互的时候需要手动设置类型处理器才可以&#xff0c;这里记录一下类型处理器的设置 /*** UUID类型处理器*/ public class UUIDTypeHandler extends BaseTypeHandler<UUID> {/*** 获…

JavaWeb——Vue:打包部署(Nginx、目录介绍、部署及启动、访问 )

目录 打包 部署 Nginx 目录介绍 部署及启动 访问 前端 Vue 项目的最后一步是打包部署。在当前前后端分离的开发模式中&#xff0c;前端开发人员开发前端代码&#xff0c;后端开发人员开发后端代码。最终要将开发及测试完毕的前端 Vue 代码和后端代码分开部署在对应的服…

Android实现App内直接预览本地PDF文件

在App内实现直接预览pdf文件&#xff0c;而不是通过调用第三方软件&#xff0c;如WPS office等打开pdf。 主要思路&#xff1a;通过PhotoView将pdf读取为图片流进行展示。 一、首先&#xff0c;获取对本地文件读取的权限 在AndrooidManifest.xml中声明权限&#xff0c;以及页…

给定任意非空有向图 G,输出 G 中所有 K 顶点的算法,并返回 K 顶点的个数。

已知优先图 G 采用邻接矩阵存储是&#xff0c;其定义如下 typedef struct { // 图的定义 int numVertices, numEdges; // 图中实际的顶点数和边数 char VerticesList[MAXV]; // 顶点表&#xff0c;MAXV为已定义常量 int Edge[MAXV]…

champ模型部署指南

一、介绍 champ是由阿里巴巴、复旦大学和南京大学的研究人员共同提出的一种基于3D的将人物图片转换为视频动画的模型&#xff0c;该方法结合了3D参数化模型(特别是SMPL模型)和潜在扩散模型&#xff0c;能够精确地捕捉和再现人体的3D形状和动态&#xff0c;同时保持动画的时间一…

Nuxt.js 应用中的 modules:before 事件钩子详解

title: Nuxt.js 应用中的 modules:before 事件钩子详解 date: 2024/10/15 updated: 2024/10/15 author: cmdragon excerpt: modules:before 是 Nuxt.js 中一个重要的生命周期钩子,在 Nuxt 应用初始化期间被触发。该钩子允许开发者在安装用户定义的模块之前执行某些操作,如…

将 QT 应用程序打包成如意玲珑软件包

在上一篇文章《国产系统之如意玲珑》中&#xff0c;我为大家介绍了一款创新的国产软件包管理工具——如意玲珑&#xff08;Linyaps&#xff09;。该工具集致力于解决 Linux 系统下传统软件包格式带来的复杂性和依赖问题&#xff0c;提供了一种更独立、更简洁的打包和管理方式。…

论文 | Context-faithful Prompting for Large Language Models

主要内容&#xff1a; 这篇文章主要探讨了如何提高大型语言模型 (LLM) 在特定语境下的“忠诚度”&#xff0c;即模型是否能准确理解并提供与上下文相符的答案。文章关注了两个主要问题&#xff1a; 知识冲突&#xff1a; 当上下文中的事实与模型预训练数据中的事实不一致时&a…