c++ unordered_set和unordered_map

std::unordered_set

std::unordered_set 是一个哈希表实现的集合，用于存储唯一的元素。

特点

  • 唯一性：集合中的每个元素都是唯一的。
  • 无序：元素的存储顺序不按照插入顺序，也不按照大小排序。
  • 快速查找：插入、删除和查找操作的时间复杂度平均为 O(1)。

核心原理

(1) 数据存储结构

  • 使用 哈希表（Hash Table） 存储元素。
  • 哈希表的每个位置称为 桶（Bucket），由哈希函数将元素映射到某个桶中。

(2) 哈希函数

  • 使用一个哈希函数 std::hash 将元素的值转换为哈希值。

  • 哈希值通过 取模操作 映射到桶索引，即：

    • bucket_index=hash(value)%bucket_count

  • 哈希函数确保相同值的元素总是映射到同一桶。

(3) 冲突处理

  • 如果多个元素映射到同一个桶（称为哈希冲突），使用链地址法（Separate Chaining）解决冲突。
  • 每个桶内部使用链表存储冲突的元素。

(4) 插入和查找

  • 插入：计算元素的哈希值，找到桶索引，将元素插入链表中（如果不重复）。
  • 查找：计算元素的哈希值，找到桶索引，遍历链表查找目标值。

内部成员

(1) 哈希函数

  • 默认使用 std::hash<T> 提供的哈希函数。

  • 可以通过模板参数自定义哈希函数：

    std::unordered_set<int, CustomHashFunction> mySet;

(2) 负载因子

  • 负载因子（Load Factor） 是当前元素个数与桶数的比值：
    • load_factor = size / bucket_count
  • 当负载因子超过指定的上限（默认值为 1.0），哈希表会 自动扩容。

(3) 再散列

  • 再散列（Rehashing）会创建一个更大的哈希表，并重新分配所有元素到新的桶中。
  • 再散列的触发条件：
    • 插入新元素后，负载因子超过 max_load_factor。
    • 手动调用 rehash() 或 reserve()。

工作流程

插入流程

  1. 使用哈希函数计算元素的哈希值。
  2. 根据哈希值找到桶索引。
  3. 检查目标桶中的链表是否已经存在该元素：
    • 如果不存在，插入元素。
    • 如果存在，不插入（确保元素唯一）。

查找流程

  1. 使用哈希函数计算元素的哈希值。
  2. 根据哈希值找到桶索引。
  3. 遍历目标桶的链表，查找是否存在目标元素。

常用成员函数

  • insert：插入元素。
  • find：查找元素。
  • erase：删除元素。
  • size：获取集合的大小。
  • count：检查某个元素是否存在。

示例

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset;// 插入元素uset.insert(10);uset.insert(20);uset.insert(30);// 插入重复元素（不会生效）uset.insert(20);// 遍历集合std::cout << "Unordered Set Elements: ";for (int val : uset) {std::cout << val << " ";}std::cout << std::endl;// 查找元素if (uset.find(20) != uset.end()) {std::cout << "Element 20 found in the set." << std::endl;}// 删除元素uset.erase(10);// 检查元素是否存在if (uset.count(10) == 0) {std::cout << "Element 10 is not in the set." << std::endl;}return 0;
}

std::unordered_map

特点

  • 键唯一：每个键是唯一的。
  • 无序：键值对的存储顺序无关插入顺序或键的大小。
  • 快速操作：插入、删除和查找操作的时间复杂度平均为 O(1)。

核心原理

(1) 数据存储结构

  • 使用 哈希表（Hash Table） 作为底层数据结构。
  • 哈希表由若干个 桶（Bucket） 组成，每个桶负责存储一组键值对。

(2) 哈希函数

  • 使用默认的哈希函数 std::hash<T> 或用户自定义的哈希函数，将键值（key）转换为哈希值。
  • 哈希值通过取模操作，映射到具体的桶索引：
    • bucket_index=hash(key)%bucket_count

(3) 冲突处理

  • 如果多个键映射到同一个桶（哈希冲突），使用 链地址法（Separate Chaining） 来解决。
  • 每个桶内部以链表或其他结构存储冲突的键值对。

(4) 键值对存储

  • 键值对以 std::pair<const Key, Value> 的形式存储。
  • 键（Key）是唯一的，值（Value）可以重复。

内部成员

(1) 哈希函数

  • 默认使用

    std::hash<Key>

    提供的哈希函数：

    std::unordered_map<int, std::string> umap;

  • 用户可以自定义哈希函数：

    struct CustomHash {size_t operator()(const std::string& key) const {return std::hash<std::string>{}(key) ^ (key.length() << 1);}
};
std::unordered_map<std::string, int, CustomHash> custom_map;

(2) 负载因子

  • 负载因子（Load Factor）：当前元素数与桶数量的比值。
    • load_factor = size / bucket_count
  • 当负载因子超过 max_load_factor 时，哈希表会 自动扩容，并进行 再散列（Rehashing）。

(3) 再散列（Rehashing）

  • 再散列会分配一个更大的哈希表，并将原来的键值对重新分布到新桶中。
  • 再散列触发条件：
    • 插入新元素后，负载因子超过 max_load_factor。
    • 手动调用 rehash() 或 reserve()。

工作流程

插入元素

  1. 使用哈希函数计算键的哈希值。
  2. 根据哈希值找到桶索引。
  3. 遍历目标桶的链表，检查键是否存在：
    • 如果键存在，更新对应的值。
    • 如果键不存在，将键值对插入链表。

查找元素

  1. 使用哈希函数计算键的哈希值。
  2. 根据哈希值找到桶索引。
  3. 遍历目标桶的链表，查找目标键，返回对应的值。

删除元素

  1. 使用哈希函数计算键的哈希值。
  2. 根据哈希值找到桶索引。
  3. 遍历目标桶的链表，删除匹配的键值对。

常用成员函数

  • insert：插入键值对。
  • operator[]：通过键访问或插入值。
  • find：查找键是否存在。
  • erase：删除键值对。
  • size：获取字典的大小。

示例

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<std::string, int> umap;// 插入键值对umap["Alice"] = 25;umap["Bob"] = 30;umap["Charlie"] = 35;// 插入方式二umap.insert({"David", 40});// 遍历字典std::cout << "Unordered Map Elements:\n";for (const auto& pair : umap) {std::cout << pair.first << ": " << pair.second << std::endl;}// 查找键if (umap.find("Bob") != umap.end()) {std::cout << "Bob's age is " << umap["Bob"] << std::endl;}// 删除键值对umap.erase("Alice");// 检查键是否存在if (umap.find("Alice") == umap.end()) {std::cout << "Alice is not in the map." << std::endl;}return 0;
}

std::unordered_set和 std::unordered_map的比较

特性std::unordered_setstd::unordered_map
存储内容仅存储键，值为元素本身存储键值对
键的唯一性键必须唯一键必须唯一
存储顺序无序无序
访问复杂度平均 O(1)平均 O(1)
使用场景集合操作（如元素存在性检查）键值对操作（如映射关系）

高级实例

示例 1：使用 std::unordered_map 统计字符串中字符的频率

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::string str = "hello world";std::unordered_map<char, int> freq;// 统计每个字符的频率for (char c : str) {if (c != ' ') { // 忽略空格freq[c]++;}}// 输出结果std::cout << "Character Frequencies:\n";for (const auto& pair : freq) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

示例 2：使用 std::unordered_set 去除数组中的重复元素

#include <iostream>
#include <unordered_set>
#include <vector>int main() {std::vector<int> nums = {1, 2, 2, 3, 4, 4, 5};std::unordered_set<int> uniqueNums(nums.begin(), nums.end());std::cout << "Unique Elements: ";for (int num : uniqueNums) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

注意事项

  1. 无序性
    • std::unordered_set 和 std::unordered_map 中的元素顺序不可预测。
    • 如果需要有序容器，使用 std::set 或 std::map。
  2. 哈希函数的性能
    • 默认使用标准库的哈希函数，如果存储自定义类型，需要为其提供自定义哈希函数。
  3. 迭代器的稳定性
    • 删除元素时，指向已删除元素的迭代器会失效。

总结

  • std::unordered_set 和 std::unordered_map 是高效的容器，适合用于频繁查找、插入和删除操作的场景。

  • std::unordered_set 适用于集合操作，std::unordered_map 适用于键值对操作。

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

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

相关文章

PyQt学习笔记

PyQt学习笔记

一.PyQt5的安装 当我们安装好开发环境后&#xff0c;打开pycharm在其设置里面点击按钮自动安装即可。 安装完成后我们会在这里面看到这几个东西说明安装成功了。 二.PyQt5 GUI程序框架 1.一个简单的PyQt5应用程序 首先我们用pycharm创建一个demo.py的文件。 我们创建文件为s…
阅读更多...
HTML5好看的音乐播放器多种风格(附源码)

HTML5好看的音乐播放器多种风格(附源码)

文章目录 1.设计来源1.1 音乐播放器风格1效果1.2 音乐播放器风格2效果1.3 音乐播放器风格3效果1.4 音乐播放器风格4效果1.5 音乐播放器风格5效果 2.效果和源码2.1 动态效果2.2 源代码 源码下载万套模板&#xff0c;程序开发&#xff0c;在线开发&#xff0c;在线沟通 作者&…
阅读更多...
ReactPress（阮一峰推荐工具）：一款基于Next.js的免费开源博客CMS系统

ReactPress（阮一峰推荐工具）：一款基于Next.js的免费开源博客CMS系统

ReactPress Github项目地址&#xff1a;https://github.com/fecommunity/reactpress 欢迎Star。 此项目是用于构建博客网站的&#xff0c;包含前台展示、管理后台和后端。 此项目是基于 React antd NestJS NextJS MySQL 的&#xff0c;项目已经开源&#xff0c;项目地址在 …
阅读更多...
pytorch自定义算子导出onnx

pytorch自定义算子导出onnx

文章目录 1、为什么要自定义算子&#xff1f;2、如何自定义算子3、自定义算子导出onnx4、example1、重写一个pytorch 自定义算子&#xff08;实现自定义激活函数&#xff09;2、现有算子上封装pytorch 自定义算子&#xff08;实现动态放大超分辨率模型&#xff09; 1、为什么要…
阅读更多...
构建高效在线教育：SpringBoot课程管理系统

构建高效在线教育：SpringBoot课程管理系统

1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理在线课程管理系统的相关信息成为必然。开发…
阅读更多...
CSS3新特性——字体图标、2D、3D变换、过渡、动画、多列布局

CSS3新特性——字体图标、2D、3D变换、过渡、动画、多列布局

目录 一、Web字体 二、字体图标 三、2D变换 1.位移 &#xff08;1&#xff09;浮动 &#xff08;2&#xff09;相对定位 &#xff08;3)绝对定位和固定定位 &#xff08;4&#xff09;位移 用位移实现盒子的水平垂直居中 2.缩放 利用缩放调整字体到12px以下&#xff…
阅读更多...
python Flask指定IP和端口

python Flask指定IP和端口

from flask import Flask, request import uuidimport json import osapp Flask(__name__)app.route(/) def hello_world():return Hello, World!if __name__ __main__:app.run(host0.0.0.0, port5000)
阅读更多...
linux ubuntu的脚本知

linux ubuntu的脚本知

目录 一、变量的引用 二、判断指定的文件是否存在 三、判断目录是否存在 四、判断最近一次命令执行是否成功 五、一些比较符号 六、"文件"的读取和写入 七、echo打印输出 八、ubuntu切换到root用户 N、其它可以参考的网址 脚本功能强大&#xff0c;用起来也…
阅读更多...
C++（进阶) 第1章 继承

C++（进阶) 第1章 继承

C&#xff08;进阶) 第1章 继承 文章目录 前言一、继承1.什么是继承2.继承的使用 二、继承方式1.private成员变量的&#xff08;3种继承方式&#xff09;继承2. private继承方式3.继承基类成员访问⽅式的变化 三、基类和派生类间的转换1.切片 四、 继承中的作⽤域1.隐藏规则&am…
阅读更多...
Load-Balanced-Online-OJ（负载均衡式在线OJ）

Load-Balanced-Online-OJ（负载均衡式在线OJ）

负载均衡式在线OJ 前言1. 项目介绍2. 所用技术与环境所用技术栈开发环境 3. 项目宏观结构3.1 项目核心模块3.2 项目的宏观结构 4. comm公共模块4.1 日志&#xff08;log.hpp &#xff09;4.1.1 日志主要内容4.1.2 日志使用方式4.1.2 日志代码 4.2 工具&#xff08;util.hpp&…
阅读更多...
c++-＞内部类 匿名对象

c++-＞内部类 匿名对象

内部类&#xff1a;&#xff08;例如&#xff1a;b定义在a类中&#xff09; 注意事项&#xff1a; &#xff08;1&#xff09;内部类b可以直接使用外部类的static变量&#xff0c;但是并不属于外部类的友元&#xff01;&#xff01;&#xff01;&#xff01; #include <s…
阅读更多...
C++ std::unique_ptr的使用及源码分析

C++ std::unique_ptr的使用及源码分析

目录 1.简介 2.使用方法 2.1.创建 unique_ptr 2.2.删除对象 2.3.转移所有权 2.4.自定义删除器 2.5.从函数返回 std::unique_ptr 2.6.将 std::unique_ptr 作为函数参数 3.适用场景 4.与原始指针的区别 5.优缺点 6.源码分析 6.1.构造函数 6.2.存储分析 6.3.默认删…
阅读更多...
系统思考—关键决策

系统思考—关键决策

最近听到一句话特别扎心&#xff1a;“不是环境毁了企业&#xff0c;而是企业误判了环境。” 在大环境变化面前&#xff0c;很多企业的反应是快速调整&#xff0c;但这真的有效吗&#xff1f;其实&#xff0c;太快的动作&#xff0c;往往是误判的开始。 环境变化带来压力&…
阅读更多...
【Java 解释器模式】实现高扩展性的医学专家诊断规则引擎

【Java 解释器模式】实现高扩展性的医学专家诊断规则引擎

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…
阅读更多...
ES八股相关知识

ES八股相关知识

为什么要使用ElasticSearch&#xff1f;和传统关系数据库&#xff08;如 MySQL&#xff09;有什么不同&#xff1f; 典型回答 数据模型 Elasticsearch 是基于文档的搜索引擎&#xff0c;它使用 JSON 文档来存储数据。在 Elasticsearch 中&#xff0c;相关的数据通常存储在同…
阅读更多...
局域网与广域网：探索网络的规模与奥秘（3/10）

局域网与广域网：探索网络的规模与奥秘（3/10）

一、局域网的特点 局域网覆盖有限的地理范围&#xff0c;通常在几公里以内&#xff0c;具有实现资源共享、服务共享、维护简单、组网开销低等特点&#xff0c;主要传输介质为双绞线&#xff0c;并使用少量的光纤。 局域网一般是方圆几千米以内的区域网络&#xff0c;其特点丰富…
阅读更多...
EMD-KPCA-Transformer多变量回归预测！分解+降维+预测！多重创新！直接写核心！

EMD-KPCA-Transformer多变量回归预测！分解+降维+预测！多重创新！直接写核心！

EMD-KPCA-Transformer多变量回归预测&#xff01;分解降维预测&#xff01;多重创新&#xff01;直接写核心&#xff01; 目录 EMD-KPCA-Transformer多变量回归预测&#xff01;分解降维预测&#xff01;多重创新&#xff01;直接写核心&#xff01;效果一览基本介绍程序设计参…
阅读更多...
编程之路，从0开始：文件操作（2）

编程之路，从0开始：文件操作（2）

Hello大家好&#xff01;很高兴我们又见面啦&#xff01;给生活添点passion&#xff0c;开始今天的编程之路&#xff01; 今天我们来继续学习C语言的文件操作。 我的博客&#xff1a;<但凡. 我的专栏&#xff1a;编程之路 持续更新高质量内容&#xff0c;欢迎点赞、关注&…
阅读更多...
mybatis学习（三）

mybatis学习（三）

声明&#xff1a;该内容来源于动力节点&#xff0c;本人在学习mybatis过程中参考该内容&#xff0c;并自己做了部分笔记&#xff0c;但个人觉得本人做的笔记不如动力节点做的好&#xff0c;故使用动力节点的笔记作为后续mybatis的复习。 六、在WEB中应用MyBatis&#xff08;使…
阅读更多...
ES6 模块化语法

ES6 模块化语法

目录 ES6 模块化语法 分别暴露 统一暴露 ​编辑 默认暴露 ES6 模块化引入方式 ES6 模块化语法 模块功能主要由两个命令构成&#xff1a;export 和 import。 ⚫ export 命令用于规定模块的对外接口&#xff08;哪些数据需要暴露&#xff0c;就在数据前面加上关键字即可…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023