C++ unordered_set unordered_map
上篇文章我们讲解了哈希表的实现，这节尝试使用哈希表来封装unordered_set/map
1. unordered_set/map的框架
封装的过程实际上与set/map类似，在unordered_set/map层传递一个仿函数，用于取出key值
由于我们平常使用的都是unordered_set/map，因此哈希函数应在unordered_set/map层作为参数传递给哈希表
// unordered_set.h
template<typename K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t ans = 0;for (auto& e : s){ans *= 131;ans += e;}return ans;}
};namespace byh
{template<typename K, typename Hash = HashFunc<K>>class unordered_set{struct KeyOfSet{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _table.insert(key);}private:hash_bucket::HashTable<K, K, KeyOfSet, Hash> _table;};
}// unordered_map.h
namespace byh
{template<typename K, typename V, typename Hash = HashFunc<K>>class unordered_map{struct KeyOfMap{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool insert(const pair<K, V>& kv){return _table.insert(kv);}private:hash_bucket::HashTable<K, pair<K, V>, KeyOfMap, Hash> _table;};
}
2. 迭代器
在unordered_set/map这里，迭代器是对哈希节点指针的封装
遍历过程中，如果当前节点的next不为空，则直接迭代到下一节点；如果当前节点的next为空，则迭代到下一个不为空的桶
因此，迭代器中仅仅有节点的指针还不够，还要有哈希表；迭代器在构造时将节点的指针和哈希表的指针作为参数传递
但由于table在哈希表中是私有成员，迭代器类中不能直接访问table，这里有两种解决方法
- 将迭代器类声明为哈希表的友元类
- 在哈希表中使用内部类创建迭代器类，内部类天然就是外部类的友元类
// 友元的做法
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable;template<typename K, typename T, typename Ref, typename Ptr, typename KeyOfT, typename Hash>
class __Iterator
{using Node = HashNode<T>;using Self = __Iterator<K, T, Ref, Ptr, KeyOfT, Hash>;
public:__Iterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}Self& operator++(){if (_node->_next) _node = _node->_next;else{KeyOfT kot;Hash hash;size_t pos = hash(kot(_node->_data)) % _pht->_table.size();int i = 0;for (i = pos + 1; i < _pht->_table.size(); i++){Node* cur = _pht->_table[i];if (cur){_node = cur;break;}}if(i == _pht->_table.size()) _node = nullptr;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}private:Node* _node;HashTable<K, T, KeyOfT, Hash>* _pht;
};template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable
{friend __Iterator<K, T, T&, T*, KeyOfT, Hash>;
public:using Node = HashNode<T>;using iterator = __Iterator<K, T, T&, T*, KeyOfT, Hash>;// ......
}
// 内部类的做法
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable
{template<typename Ref, typename Ptr>class __Iterator{using Node = HashNode<T>;using Self = __Iterator<Ref, Ptr>;public:__Iterator(Node* node, HashTable* pht):_node(node), _pht(pht){}Self& operator++(){if (_node->_next) _node = _node->_next;else{KeyOfT kot;Hash hash;size_t pos = hash(kot(_node->_data)) % _pht->_table.size();int i = 0;for (i = pos + 1; i < _pht->_table.size(); i++){Node* cur = _pht->_table[i];if (cur){_node = cur;break;}}if (i == _pht->_table.size()) _node = nullptr;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}private:Node* _node;HashTable* _pht;};public:using Node = HashNode<T>;using iterator = __Iterator<T&, T*>;// ......
}
内部类做法的好处时，内部类能直接使用外部类的模板参数，不用向友元方式那样传递很多模板参数，同时内部类能直接使用外部类而不用传递模板参数
哈希表的迭代器一旦设计好，unordered_set/map层无非就是封装，这里不再叙述
3. const迭代器
const迭代器的整体思路没难度，但有些细节地方需要注意
在哈希表层和unordered_set/map层添加完const迭代器后
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable
{template<typename Ref, typename Ptr>class __Iterator{using Node = HashNode<T>;using Self = __Iterator<Ref, Ptr>;public:__Iterator(Node* node, const HashTable* pht):_node(node), _pht(pht){}// ......private:Node* _node;const HashTable* _pht;};
关于unordered_map的operator[]，其设计思路与set/map相同
unordered_set/map层的插入、删除、查找操作也同样是简单的封装
4. 测试
void Print(const unordered_set<int>& s)
{unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;
}void Test_unordered_set()
{vector<int> v = { 1, 4, 2, 3, 5, 9, 11 };unordered_set<int> s;for (auto& e : v) s.insert(e);cout << "const迭代器: ";Print(s);cout << s.find(4) << endl;cout << s.find(54) << endl;s.erase(4);cout << s.find(4) << endl;
}
void Test_unordered_map()
{unordered_map<string, int> m;vector<string> v = { "apple", "apple", "banana", "watermelon", "banana" };for (auto& e : v) m[e] ++;unordered_map<string, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << " " << it->second << endl;++it;}cout << endl;cout << m.find("apple") << endl;cout << m.find("abdsaf") << endl;m.erase("apple");cout << m.find("apple") << endl;
}
相关文章：
C++ unordered_set unordered_map
上篇文章我们讲解了哈希表的实现，这节尝试使用哈希表来封装unordered_set/map 1. unordered_set/map的框架 封装的过程实际上与set/map类似，在unordered_set/map层传递一个仿函数，用于取出key值 由于我们平常使用的都是unordered_set/map&…...
第37课 绘制原理图——放置离页连接符
什么是离页连接符？ 前边我们介绍了网络标签（Net Lable），可以让两根导线“隔空相连”，使原理图更加清爽简洁。 但是网络标签的使用也具有一定的局限性，对于两张不同Sheet上的导线，网络标签就不…...
＜ 自用文 Texas style Smoker ＞ 美式德克萨斯烟熏炉 从设计到实现 （第一部分：烹饪室与燃烧室）
原因： 没钱还馋！ 但有手艺。 预计目标： 常见的两种偏置式烟熏炉（Offset Smoker） 左边边是标准偏置式（Standard Offset），右边是反向流动式（Reverse Flow Offset&#x…...
【现代深度学习技术】现代循环神经网络03：深度循环神经网络
【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈PyTorch深度学习 ⌋ ⌋ ⌋ 深度学习 (DL, Deep Learning) 特指基于深层神经网络模型和方法的机器学习。它是在统计机器学习、人工神经网络等算法模型基础上，结合当代大数据和大算力的发展而发展出来的。深度学习最重…...
AimRT从入门到精通 - 03Channel发布者和订阅者
刚接触AimRT的小伙伴可能会疑惑，这个Channel和RPC（后面讲的）到底是什么呢？ 但是当我们接触了之后，就会发现，其本质类似ROS的Topic通信！（其本质基于发布订阅模型） 接下来…...
MySQL初阶：数据库基础，数据库和表操作，数据库中的数据类型
1.数据库基础 数据库是一个客户端——服务器结构的程序。 服务器是真正的主体，负责保存和管理数据，数据都存储在硬盘上 数据库处理的主要内容是数据的存储，查找，修改，排序，统计等。 关系型数据库&#…...
AI 驱动的智能交通系统：从拥堵到流畅的未来出行
最近研学过程中发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击链接跳转到网站人工智能及编程语言学习教程。读者们可以通过里面的文章详细了解一下人工智能及其编程等教程和学习方法。下面开始对正文内容的…...
Python清空Word段落样式的方法
在 Python 中，你可以使用 python-docx 库来操作 Word 文档，包括清空段落样式。以下是几种清空段落样式的方法： 方法一：直接设置段落样式为"Normal" from docx import Documentdoc Document(your_document.docx) # 打…...
[javaEE]网络编程
目录 socket对tcp ServerSocket ServerSocket 构造方法： ServerSocket 方法： socket 实现回显服务器和客户端 由于我们之前已经写多了socket对udq的实现，所以我们这节，主要将重心放在Tcp之上 socket对tcp ServerS…...
组件通信-mitt
mitt：与消息订阅与发布（pubsub）功能类似，可以实现任意组件间通信。 第一步：安装mitt npm i mitt 第二步：新建文件：src\utils\emitter.ts // 引入mitt import mitt from "mitt"; //调…...
微软发布了最新的开源推理模型套件“Phi-4-Reasoning
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗？订阅我们的简报，深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同，从行业内部的深度分析和实用指南中受益。不要错过这个机会，成为AI领…...
Socat 用法详解：网络安全中的瑞士军刀
Socat 用法详解：网络安全中的强大工具 引言 socat（SOcket CAT）是一款功能强大的命令行工具，被誉为“网络瑞士军刀”，广泛应用于数据传输、端口转发和网络调试等场景。它支持多种协议和数据通道（如文件、管…...
精益数据分析（36/126）：SaaS商业模式的指标动态与实践案例
精益数据分析（36/126）：SaaS商业模式的指标动态与实践案例 在创业与数据分析的学习道路上，我们不断探索各种商业模式的核心要点。今天，依旧怀揣着和大家共同进步的想法，深入研读《精益数据分析》中SaaS商业…...
2.LED灯的控制和按键检测
目录 STM32F103的GPIO口 GPIO口的作用 GPIO口的工作模式 input输入检测 -- 向内检测 output控制输出 -- 向外输出 寄存器 寄存器地址的确定 配置GPIO口的工作模式 时钟的开启和关闭 软件编程驱动 LED 灯 硬件 软件 软件编程驱动 KEY 按键 硬件 软件 按键消抖 代码 STM32F…...
架构师面试（三十八）：注册中心架构模式
题目 在微服务系统中，当服务达到一定数量时，通常需要引入【注册中心】组件，以方便服务发现。 大家有没有思考过，注册中心存在的最根本的原因是什么呢？注册中心在企业中的最佳实践是怎样的？注册中心的服务…...
Go-web开发之帖子功能
帖子功能 route.go r.Use(middleware.JWTAuthMiddleware()){r.POST("/post", controller.CreatePostHandler)r.GET("/post/:id", controller.GetPostDetailHandler)}post.go 定义帖子结构 type Post struct {Id int64 json:"id" …...
MYSQL-设计表
一.范式 数据库的范式是⼀组规则。在设计关系数据库时，遵从不同的规范要求，设计出合理的关系型数 据库，这些不同的规范要求被称为不同的范式。 关系数据库有六种范式：第⼀范式（1NF）、第⼆范式（…...
动态思维——AI与思维模型【91】
一、定义 动态思维思维模型是一种强调在思考问题和分析情况时，充分考虑到事物的变化性、发展性和相互关联性，不局限于静态的、孤立的视角，而是以发展变化的眼光看待事物，能够根据不同时间、环境和条件的变化，灵活调整…...
文献阅读篇#7：5月一区好文阅读，BFA-YOLO，用于建筑信息建模！（下）
期刊简介：《Advanced Engineering Informatics》创刊于2002年，由Elsevier Ltd出版商出版，出版周期Quarterly。该刊已被SCIE数据库收录，在中科院最新升级版分区表中，该刊分区信息为大类学科工程技术1区，2023…...
【Linux网络编程】http协议的状态码，常见请求方法以及cookie-session
本文专栏：Linux网络编程 目录 一，状态码 重定向状态码 1，永久重定向（301 Moved Permanently） 2，临时重定向（302 Found） 二，常见请求方法 1，HTTP常见Hea…...
第六章：ARM 编程技巧与优化策略)
ARM 指令集(ubuntu环境学习)第六章：ARM 编程技巧与优化策略
在本章中，我们将介绍一些在 ARM 架构上编写高效代码的技巧和常见优化策略，帮助您在嵌入式系统中获得更低延迟、更高吞吐和更低功耗。 6.1 寄存器利用与最小化内存访问 多用寄存器 ARM 通用寄存器（r0–r12）数量充足，尽量将临时变量保留在寄存器中，减少对内存的读写。 避免…...
柔性超声耦合剂的选择与设计-可穿戴式柔性超声耦合剂面临的难题
柔性PZT压电薄膜：破解可穿戴式超声耦合剂难题的关键材料！ 随着可穿戴技术的快速发展，超声设备正朝着轻量化、柔性化和高集成度方向演进。在医学诊断、健康监测和智能穿戴领域，可穿戴式超声设备因其无创、实时、动态成像等优势受到…...
XCTF-pwn（二）
guess_num 看一下文件信息 利用gets函数将seed[0]给覆盖掉 距离0x20 我们需要输入十次随机数产生的值 写一个c程序先预判当seed是a的时候产生的随机数分别是多少 payload from pwn import* from ctypes import* context.log_leveldebugrremote("61.147.171.105", 6…...
AI外挂RAG：大模型时代的检索增强生成技术
目录 引言 一、RAG是什么？ 二、RAG为什么会出现？ 三、RAG的工作原理 四、RAG的技术优势 五、RAG的应用场景 六、RAG对AI行业的影响 七、RAG面临的挑战 引言 在人工智能领域，大型语言模型（LLM）如ChatGPT、DeepSe…...
SpringTask
Spring Task是Spring框架提供的任务调度工具，可以按照约定的时间自动执行某个代码逻辑 应用场景：信用卡每月还款提醒、火车票售票系统处理未支付订单 fixedDelay：上一次任务执行完成后多长时间（ms）执行下一次任务 fixe…...
Sphinx 文档图片点击放大
文章目录 问题描述解决方案步骤 1：创建 JavaScript 文件步骤 2：编写 JavaScript 代码步骤 3：更新 Sphinx 配置 高级定制为所有图片添加点击功能添加缩放控制 总结 在使用 Sphinx 生成技术文档时，我们经常需要在文档中嵌入截图和示…...
菜鸟之路Day29一一MySQL之DDL
菜鸟之路Day29一一MySQL之DDL 作者：blue 时间：2025.5.2 文章目录 菜鸟之路Day29一一MySQL之DDL0.概述1.DDL之数据库操作1.1查询1.2创建1.3使用1.4删除 2.DDL之表操作2.1创建表2.2数据类型2.3查询表2.4修改表结构2.5删除表 0.概述 文章内容学习自黑马程…...
架构师面试（三十七）：监控系统架构模式
题目 监控是在产品生命周期的运维环节，能对产品的关键指标数据进行【实时跟踪】并对异常数据进行【实时报警】。 一句话描述，监控系统可以帮我们【主动预防和发现】业务系统中的问题。 我们常说，监控系统是 “粮草”，业务系统是…...
【Redis】Hash哈希
文章目录 注意个问题hset命令（核心）hget命令（核心）hexists命令hdel命令hkeys和hvals命令hgetall和hmget命令hlen命令hsetnx命令hincrby命令哈希命令小结哈希编码方式使用场景1.关系型数据表保存用户的信息Redis三种缓存方式对比1.…...
【SpringBoot】Spring中事务的实现：声明式事务@Transactional、编程式事务
1. 准备工作 1.1 在MySQL数据库中创建相应的表 用户注册的例子进行演示事务操作，索引需要一个用户信息表 （1）创建数据库 -- 创建数据库 DROP DATABASE IF EXISTS trans_test; CREATE DATABASE trans_test DEFAULT CHARACTER SET utf8mb4;…...
从零开始讲DDR（9）——AXI 接口MIG 使用（2）
一、前言 在之前的文章中，我们介绍了官方DDR MIG AXI接口的例程的整体框架，在本文中，我们将着重介绍例程中关于数据产生，及驱动到AXI接口的相关逻辑实现。 二、data_gen 在例程中，有ddr4_v2_2_8_data_gen这样一个文件…...
组件通信-props
props 是使用频率最高的一种通信方式，父>子 子>父 父传子：属性值 是非函数子传父：属性值 是函数 父组件 <script setup lang"ts"> import { ref } from vue import Child from ./Child.vue const car ref(奥迪) c…...
纯原生Java实现：获取整个项目中指定接口所有的实现类
不使用第三方，不使用属性文件,不指定包名，获取整个系统中某一个接口所有的实现类，纯Java实现 /*** 类查找器，用于扫描类路径中的所有类，并找出指定类的实现类。* 该类通过递归扫描类路径下的所有 .class 文件…...
反射机制补充
不同对象实例的地址不同 在 Java 里，每当使用 new 关键字创建一个对象时，JVM 会在堆内存中为该对象分配一块新的内存空间，每个对象实例都有自己独立的内存地址。所以不同的对象实例，其内存地址是不同的。 以下是一个简单示例&am…...
计算机视觉的未来发展趋势
计算机视觉的未来发展趋势主要集中在以下几个方面： 1. 自监督学习与少样本学习 自监督学习：通过从无标签的数据中提取有用特征，克服对大量标注数据的依赖。2025年，基于大规模图像数据的自监督预训练模型将更加成熟，能…...
轻量级网页版视频播放器
用deepseek开发的轻量级，网页版视频播放器 可以选择本地文件 可以播放、暂停、全屏、有进度条和时间进度 代码如下： 新建.txt文本文档，把代码复制粘贴进去，把.txt文档后缀名改为.html，用浏览器打开即可使用 <!DO…...
18. LangChain分布式任务调度：大规模应用的性能优化
引言：从单机到万级并发的进化 2025年某全球客服系统通过LangChain分布式改造，成功应对黑五期间每秒12,000次的咨询请求。本文将基于LangChain的分布式架构，详解如何实现AI任务的自动扩缩容与智能调度。 一、分布式系统核心指标 1.1 性能基准…...
C/C++工程师使用 DeepSeek
一、使用 DeepSeek 生成 C/C 代码 在 C/C 开发中，很多时候需要编写一些常见功能的代码，如排序算法、文件读写操作、数据结构的实现等。借助 DeepSeek，工程师只需用自然语言清晰描述需求，它就能依据大量的代码数据和深度学习算法&a…...
数据结构-线性结构（链表、栈、队列）实现
公共头文件common.h #define TRUE 1 #define FALSE 0// 定义节点数据类型 #define DATA_TYPE int单链表C语言实现 SingleList.h #pragma once#include "common.h"typedef struct Node {DATA_TYPE data;struct Node *next; } Node;Node *initList();void headInser…...
：简单务实的概率性选手)
第 7 篇：跳表 (Skip List)：简单务实的概率性选手
前面几篇我们都在探讨各种基于“树”结构的有序表实现，它们通过精巧的平衡策略（高度、颜色、大小）和核心的“旋转”操作来保证 O(log N) 的性能。今天，我们要介绍一位画风完全不同的选手——跳表 (Skip List)。它不依赖树形结构&a…...
sys目录介绍
文章目录 1. 前言2. 目录层次3. 目录介绍3.1 devices 目录3.2 block 目录3.3 bus 目录3.4 class 目录3.5 dev 目录3.6 firmware目录3.7 fs 目录3.8 kernel目录3.9 module 目录3.10 power 目录 sys目录介绍 1. 前言 linux 下一切皆文件，文件的类型也很多，…...
基于DQN的自动驾驶小车绕圈任务
1.任务介绍 任务来源: DQN: Deep Q Learning ｜自动驾驶入门（？） ｜算法与实现 任务原始代码: self-driving car 最终效果： 以下所有内容，都是对上面DQN代码的改进&#…...
源码安装SRS4
Ubuntu20安装好SRS后，（源码安装） 注意：在trunk目录SRS ./objs/srs -c conf/srs.conf 以上为启动srs命令，-c 为指定配置文件， 查看SRS进程 ps aux | grep srs 查看端口： netstat -ano | gre…...
OrbitControls
OrbitControls 3D虚拟工厂在线体验 描述 Orbit controls（轨道控制器）可以使得相机围绕目标进行轨道运动。 Constructor OrbitControls( object : Camera, domElement : HTMLDOMElement ) 参数类型描述objectCamera（必须）将要…...
【数据库】四种连表查询：内连接，外连接，左连接，右连接
在数据库操作中，连表查询是处理多表关联的核心技术。以下是四种主要连接方式的详细介绍、快速掌握方法及实际应用指南： 目录 **一、四种连表查询详解****1. 内连接（INNER JOIN）****2. 左连接（LEFT JOIN / LEFT OUTER J…...
Redis怎么避免热点数据问题
使用 RedisTemplate 避免热点数据问题的解决方案、场景及示例： 1. 数据分片（Sharding） 场景：高频读写的计数器（如文章阅读量统计） 原理：将数据分散到多个子键，降低单个 Key 的压…...
完整的 VS Code + CMake + Qt + GCC 项目构建方案：EXE 程序与多个 DLL 库
完整的 VS Code CMake Qt GCC 项目构建方案：EXE 程序与多个 DLL 库 在本文中，我们将介绍如何构建一个包含 EXE 程序和多个 DLL 库的项目，适用于 VS Code CMake Qt GCC 开发环境。这个方案为一个模块化的项目结构，使得代码清…...
：智能流失预警 - 融合文本反馈)
Python 数据智能实战 (7)：智能流失预警 - 融合文本反馈
写在前面 —— 不再错过关键预警！结合用户行为与 LLM 文本洞察，构建更精准的流失预测模型 在之前的探索中，我们学习了如何利用大语言模型 (LLM) 对用户评论进行深度挖掘，提取情感、发现主题，并将非结构化的文本信息转化为有价值的特征 (如 Embeddings)。 现在，我们要将…...
Flutter - 概览
Hello world ⌘ shift p 选择 Empty Application 模板 // 导入Material风格的组件包 // 位置在flutter安装目录/packages/flutter/lib/material.dart import package:flutter/material.dart;void main() {// runApp函数接收MainApp组件并将这个Widget作为根节点runApp(cons…...
及Excel表格列名操作详细分享)
Python-pandas-操作Excel文件(读取数据/写入数据)及Excel表格列名操作详细分享
Python-pandas-操作Excel文件(读取数据/写入数据) 提示：帮帮志会陆续更新非常多的IT技术知识，希望分享的内容对您有用。本章分享的是pandas的使用语法。前后每一小节的内容是存在的有：学习and理解的关联性。【帮帮志系列文章】：每…...