【C++：哈希表封装】哈希表封装 myunordered_map/myunordered_set 实战：底层原理 + 完整实现

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一. unordered_map/unordered_set源码及框架分析stl_hash_setstl_hash_mapstl_hashtable.h二、核心设计思路哈希表的泛型复用2.1 哈希表模板参数设计2.2 实现出复用哈希表的框架并支持insert2.3 实现迭代器支持哈希桶遍历2.4 map支持[]三、完整代码实现(附详细注释)HashTable.hunordered_set.hunordered_map.h测试代码(test .cpp)结束语前言STL 中的 unordered_map 和 unordered_set 以高效的增删查性能平均 O (1) 时间复杂度成为高频使用的关联式容器其底层核心是哈希表哈希桶。但很多朋友只知道如何使用这两个容器却不清楚究竟是怎么实现的 —— 如何基于哈希表封装出支持 key-value 存储和 key-only 存储的两种容器使用迭代器iterator在的时候是如何找到下一个位置如何保证 key 的唯一性在前面的文章中我们已经对哈希表的实现进行了详细的讲解其中已经讲解了哈希冲突如何解决、哈希函数如何实现等也是为本篇文章封装两个容器做铺垫。本文结合核心思路从哈希表的泛型设计入手一步步拆解 myunordered_map 和 myunordered_set 的封装逻辑包括哈希函数适配、迭代器实现、key 约束等关键细节附完整实现代码帮你吃透哈希表在容器封装中的实战应用。一. unordered_map/unordered_set源码及框架分析SGI-STL30版本源代码中没有unordered_map和unordered_setSGI-STL30版本是C11之前的STL版本这两个容器是C11之后才更新的。但是SGI-STL30实现了哈希表容器的名字是hash_map和hash_set他是作为非标准的容器出现的非标准是指非C标准规定必须实现的源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中hash_map和hash_set的实现结构框架核心部分截取出来如下stl_hash_set// stl_hash_set template class Value, class HashFcn hashValue, class EqualKey equal_toValue, class Alloc alloc class hash_set { private: typedef hashtableValue, Value, HashFcn, identityValue, EqualKey, Alloc ht; ht rep; public: typedef typename ht::key_type key_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::const_iterator iterator; typedef typename ht::const_iterator const_iterator; hasher hash_funct() const { return rep.hash_funct(); } key_equal key_eq() const { return rep.key_eq(); } };stl_hash_map// stl_hash_map template class Key, class T, class HashFcn hashKey, class EqualKey equal_toKey, class Alloc alloc class hash_map { private: typedef hashtablepairconst Key, T, Key, HashFcn, select1stpairconst Key, T , EqualKey, Alloc ht; ht rep; public: typedef typename ht::key_type key_type; typedef T data_type; typedef T mapped_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::iterator iterator; typedef typename ht::const_iterator const_iterator; };stl_hashtable.h// stl_hashtable.h template class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc class hashtable { public: typedef Key key_type; typedef Value value_type; typedef HashFcn hasher; typedef EqualKey key_equal; private: hasher hash; key_equal equals; ExtractKey get_key; typedef __hashtable_nodeValue node; vectornode*, Alloc buckets; size_type num_elements; public: typedef __hashtable_iteratorValue, Key, HashFcn, ExtractKey, EqualKey, Alloc iterator; pairiterator, bool insert_unique(const value_type obj); const_iterator find(const key_type key) const; }; template class Value struct __hashtable_node { __hashtable_node* next; Value val; };这里我们就不再画图分析了通过源码可以看到结构上 hash_map 和 hash_set 跟 map 和 set 的完全类似复用同一个 hashtable 实现 key 和 key/value 结构hash_set 传给hash_table 的是两个 keyhash_map 传给 hash_table 的是一个 key 和 一个 pairconst key,value(第一个key的作用和set/map的红黑树封装一样调用find/erase函数需要传key值)需要注意的是源码里面跟map/set源码类似命名风格比较乱这里比map和set还乱hash_set模板参数居然用的Value命名hash_map用的是Key和T命名。二、核心设计思路哈希表的泛型复用myunordered_map 和 myunordered_set 复用同一哈希表底层核心通过模板参数抽象和仿函数提取 key实现 “一颗哈希表适配两种存储场景”myunordered_set存储单个 key去重 无序需提取 key 本身进行哈希和比较myunordered_map存储 key-value 对key 去重 无序需提取 pair 中的 first 作为 key 进行哈希和比较。2.1 哈希表模板参数设计哈希表需支持三种核心抽象通过模板参数暴露接口适配不同容器需求templateclass K, class T, class KeyofT, class Hash class HashTable { // K哈希和查找时的key类型myunordered_set为Kmyunordered_map为K // T哈希表节点存储的实际数据类型myunordered_set为Kmyunordered_map为pairconst K, V // Hash哈希函数仿函数将K转为整形用于计算桶位置 // KeyOfT从T中提取K的仿函数适配T的不同类型如pair };2.2 实现出复用哈希表的框架并支持insert参考源码框架unordered_set 和 unordered_map 复用之前我们实现的哈希表。我们这里相比源码调整一下key参数就用Kvalue参数就用V哈希表中结点存储的实际数据类型我们使用T其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂一点但是大框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K还是pairK,V那么insert内部进行插入时要用K对象转换成整形取模和K比较相等因为pair的value不参与计算取模且默认支持的是key和value一起比较相等我们需要时的任何时候只需要比较K对象所以我们在unordered_map和unordered_set层分别实现一个MapKeyofT和SetKeyofT的仿函数传给HashTable的KeyofT然后HashTable中通过KeyofT仿函数取出T类型对象中的K对象再转换成整形取模和K比较相等。具体细节参考如下部分代码实现来进行理解// MyUnorderedSet.h namespace xiaoye { templateclass K, class Hash HashFuncK struct unordered_set { struct KeyofSet { const K operator()(const K key) { return key; } }; public: bool insert(const K key) { return _ht.Insert(key); } private: HashTableK, const K, KeyofSet, Hash _ht; }; }// MyUnorderedMap.h namespace xiaoye { templateclass K, class V, class Hash HashFuncK struct unordered_map { // 仿函数从Tpairconst K, V中提取key struct KeyofMap { const K operator()(const pairK, V kv) { return kv.first; } }; public: bool insert(const pairK, V kv) { return _ht.Insert(kv); } private: HashTableK, pairconst K, V, KeyofMap, Hash _ht; }; }这里讲一下为什么unordered_map和unordered_set的成员变量 _ht 类型 HashTable 中第二个参数都用 const 进行修饰首先 HashTable 类模板的第二个模板参数为 T说明我们是将哈希表节点存储的实际数据中的key值进行const修饰(也就是不允许修改key)因为哈希表存放数据就是依赖数据中key值在哈希表中桶位置的映射关系一旦修改了key值则映射关系就会出现问题。Insert实现// HashTable.h // 质数表(SGI STL 同款用于扩容) static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; // n const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } // 哈希函数仿函数 templateclass K struct HashFunc { size_t operator()(const K key) { return size_t(key); // 默认可支持直接转换 } }; // 特化string类型的哈希函数 template struct HashFuncstring { // BKDR字符串哈希算法 size_t operator()(const string key) { size_t hash 0; for (auto ch : key) { // 字符串转换成整形可以把字符ascii码相加即可 hash ch;// 累加字符ASCII码 hash * 131;// 乘质数131减少冲突 } return hash; } }; // 哈希桶节点结构链表节点 templateclass T struct HashNode { T _data; HashNode* _next; HashNode(const T data) :_data(data) , _next(nullptr) { } }; templateclass K, class T, class KeyofT, class Hash class HashTable { public: typedef HashNodeT Node; //构造函数 HashTable() :_tables(__stl_next_prime(0)) , _n(0) { } //析构函数 ~HashTable() { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; _tables[i] next; delete cur; cur next; } } _n 0; } // 插入key-value对头插法去重需先查找 bool Insert(const T data) { KeyofT kot; if (Find(kot(data))) { return false; } Hash hs; if (_n _tables.size()) { //迁移旧表节点到新表直接移动节点不新建效率更高 vectorNode* newtables(__stl_next_prime(_tables.size() 1)); for (int i 0; i _tables.size(); i) { // 遍历旧表旧表节点重新映射挪动到新表 Node* cur _tables[i]; while (cur) { //重新计算节点在新表的位置 size_t hashi hs(kot(cur-_data)) % newtables.size(); //头插入新表 Node* next cur-_next; cur-_next newtables[hashi]; newtables[hashi] cur; cur next; }//while循环结束说明第i位置的链表结点已经全部挪走了需要置空 _tables[i] nullptr; } _tables.swap(newtables); } //头插入当前节点 size_t hashi hs(kot(data)) % _tables.size(); Node* newnode new Node(data); newnode-_next _tables[hashi];//newnode的下一个位置指向hashi位置的头节点 _tables[hashi] newnode; //让newnode变为头节点 _n; return true; } private: vectorNode* _tables;// 指针数组存储每个链表头指针 size_t _n 0; };2.3 实现迭代器支持哈希桶遍历iterator实现思路分析iterator 实现的大框架跟 list 的 iterator 思路是⼀致的(因为哈希桶本质就是将结点通过指针像衣架挂起来)用⼀个类型封装结点的指针再通过重载运算符实现迭代器像指针⼀样访问的行为要注意的是哈希表的迭代器是单向迭代器。这里的难点是 operator 的实现。iterator 中有⼀个指向结点的指针如果当前桶下面还有结点则结点的指针指向下⼀个结点即可。如果当前桶走完了则需要想办法计算找到下⼀个桶。这里的难点是反而是结构设计的问题参考上面的源码我们可以看到 iterator 中除了有结点的指针还有哈希表对象的指针这样当前桶走完了要计算下一个桶就相对容易多了⽤ key 值计算出当前桶位置(这时候就需要利用哈希表对象的指针来获取桶的总个数)依次往后找下⼀个不为空的桶即可。begin()返回第一个不为空的桶中第⼀个节点指针构造的迭代器这⾥end()返回迭代器可以用空表示。unordered_set 的 iterator 不支持修改这也是为什么我们把 unordered_set 的第二个模板参数改成 const K 的原因之一HashTableK, const K, SetKeyofT, Hash _ht;unordered_map 的 iterator 不支持修改 key 但是可以修改 value这也是为什么我们把unordered_map 的第⼆个模板参数 pair 的第⼀个参数改成 const KHashTableK, pairconst K, V,MapKeyofT, Hash _ht;//哈希表迭代器 templateclass K, class T, class Res, class Ptr, class KeyofT, class Hash struct HashTableIterator { typedef HashTableIteratorK, T, Res, Ptr, KeyofT, Hash Self; typedef HashNodeT Node; typedef HashTableK, T, KeyofT, Hash HT; Node* _cur;// 当前指向的节点 const HT* _ht;// 指向哈希表通过获取桶的总个数来计算当前结点所在桶的位置以此进行桶切换 //由于const迭代器实现原因ConstIterator Begin() const 会修饰返回的this指针 //导致this指针指向对象的内容被const修饰但是传过来构造时如果是普通对象则权限放大了 //所以_ht需要加上const修饰 // 迭代器构造函数 HashTableIterator(Node* cur, const HT* ht) :_cur(cur) ,_ht(ht) { } // 解引用运算符返回节点数据引用 Res operator*() { return _cur-_data; } // 箭头运算符支持-访问成员如map的first/second Ptr operator-() { return _cur-_data; } bool operator!(const Self s) const { return _cur ! s._cur; } // 前置核心遍历当前桶所有节点后切换到下一个非空桶 Self operator() { if (_cur-_next) { //当前桶还有数据走到当前桶的下一个结点 _cur _cur-_next; } else { //当前桶已经走完了需要找到下一个不为空的桶 KeyofT kot; Hash ht; size_t hashi ht(kot(_cur-_data)) % _ht-_tables.size(); hashi;//先走到下一个桶进行判断是否为空 while (hashi _ht-_tables.size()) { _cur _ht-_tables[hashi]; if (_cur) { //当前走到的桶不为空cur就是当前桶的头节点位置直接返回 break; } hashi; } //这里的特殊处理情况为当_cur为最后一个桶的最后一个结点 //则上面的while循环会直接结束但_cur仍然有值需要特殊处理为空 if (hashi _ht-_tables.size()) { _cur nullptr; } } return *this; } };2.4 map支持[]unordered_map 要支持[]主要需要修改insert返回值支持修改 HashTable 中的 insert 返回值为pairIteratorbool Insert(const T data)有了insert支持[ ]实现就很简单了具体 insert 修改代码和 [ ] 实现会在最后全部进行展示。三、完整代码实现(附详细注释)HashTable.h#includeiostream #includevector #includestring using namespace std; // 质数表(SGI STL 同款用于扩容) static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; // n const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } // 哈希函数仿函数 templateclass K struct HashFunc { size_t operator()(const K key) { return size_t(key); // 默认可支持直接转换 } }; // 特化string类型的哈希函数 template struct HashFuncstring { // BKDR字符串哈希算法 size_t operator()(const string key) { size_t hash 0; for (auto ch : key) { // 字符串转换成整形可以把字符ascii码相加即可 hash ch;// 累加字符ASCII码 hash * 131;// 乘质数131减少冲突 } return hash; } }; // 哈希桶节点结构链表节点 templateclass T struct HashNode { T _data; HashNode* _next; HashNode(const T data) :_data(data) , _next(nullptr) { } }; //前置声明HashTable类模板因为HashTableIterator中operator需要哈希桶的长度如果不加则编译器找不到 templateclass K, class T, class KeyofT, class Hash class HashTable; //哈希表迭代器 templateclass K, class T, class Res, class Ptr, class KeyofT, class Hash struct HashTableIterator { typedef HashTableIteratorK, T, Res, Ptr, KeyofT, Hash Self; typedef HashNodeT Node; typedef HashTableK, T, KeyofT, Hash HT; Node* _cur;// 当前指向的节点 const HT* _ht;// 指向哈希表通过获取桶的总个数来计算当前结点所在桶的位置以此进行桶切换 //由于const迭代器实现原因ConstIterator Begin() const 会修饰返回的this指针 //导致this指针指向对象的内容被const修饰但是传过来构造时如果是普通对象则权限放大了 //所以_ht需要加上const修饰 // 迭代器构造函数 HashTableIterator(Node* cur, const HT* ht) :_cur(cur) ,_ht(ht) { } // 解引用运算符返回节点数据引用 Res operator*() { return _cur-_data; } // 箭头运算符支持-访问成员如map的first/second Ptr operator-() { return _cur-_data; } bool operator!(const Self s) const { return _cur ! s._cur; } // 前置核心遍历当前桶所有节点后切换到下一个非空桶 Self operator() { if (_cur-_next) { //当前桶还有数据走到当前桶的下一个结点 _cur _cur-_next; } else { //当前桶已经走完了需要找到下一个不为空的桶 KeyofT kot; Hash ht; size_t hashi ht(kot(_cur-_data)) % _ht-_tables.size(); hashi;//先走到下一个桶进行判断是否为空 while (hashi _ht-_tables.size()) { _cur _ht-_tables[hashi]; if (_cur) { //当前走到的桶不为空cur就是当前桶的头节点位置直接返回 break; } hashi; } //这里的特殊处理情况为当_cur为最后一个桶的最后一个结点 //则上面的while循环会直接结束但_cur仍然有值需要特殊处理为空 if (hashi _ht-_tables.size()) { _cur nullptr; } } return *this; } }; templateclass K, class T, class KeyofT, class Hash // K哈希、查找和删除时的key类型myunordered_set为Kmyunordered_map为K // T哈希表节点存储的实际数据类型myunordered_set为Kmyunordered_map为pairconst K, V // Hash哈希函数仿函数将K转为整形用于计算桶位置 // KeyOfT从T中提取K的仿函数适配T的不同类型如pair class HashTable { //友元声明类模板HashTableIterator为了_ht能使用私有成员_tables //友元声明和前置声明类模板都需要将模板参数带上 templateclass K, class T, class Res, class Ptr, class KeyofT, class Hash friend struct HashTableIterator; public: typedef HashNodeT Node; typedef HashTableIteratorK, T, T, T*, KeyofT, Hash Iterator; typedef HashTableIteratorK, T, const T, const T*, KeyofT, Hash ConstIterator; Iterator Begin() { for (size_t i 0; i _tables.size(); i) { if (_tables[i]) { return Iterator(_tables[i], this); } } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin() const { for (size_t i 0; i _tables.size(); i) { if (_tables[i]) { return ConstIterator(_tables[i], this); //由于Begin()被const修饰所以this指针指向对象的内容也不能进行修改 //此时this的类型完整表示为const HashTable* const this //所以如果上面迭代器构造中_ht(对应这里的this指针)不被const修饰则调用const迭代器时就会出现权限放大报错 } } return End(); } ConstIterator End() const { return ConstIterator(nullptr, this); } //构造函数 HashTable() :_tables(__stl_next_prime(0)) , _n(0) { } //析构函数 ~HashTable() { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; _tables[i] next; delete cur; cur next; } } _n 0; } //拷贝构造(深拷贝) HashTable(const HashTableK, T, KeyofT, Hash ht) { this-_tables.resize(ht._tables.size()); for (size_t i 0; i ht._tables.size(); i) { Node* cur ht._tables[i]; while (cur) { Insert(cur-_kv); cur cur-_next; } } } void Swap(HashTableK, T, KeyofT, Hash ht) { std::swap(_tables, ht._tables); std::swap(_n, ht._n); } //赋值重载operator(现代写法) HashTableK, T, KeyofT, Hash operator(HashTableK, T, KeyofT, Hash ht) { if (this ! ht) { Swap(ht); } return *this; } // 插入key-value对头插法去重需先查找 //bool Insert(const T data) pairIterator, bool Insert(const T data) { KeyofT kot; auto it Find(kot(data)); if (it ! End()) { return { it, true }; } Hash hs; if (_n _tables.size()) { //迁移旧表节点到新表直接移动节点不新建效率更高 vectorNode* newtables(__stl_next_prime(_tables.size() 1)); for (int i 0; i _tables.size(); i) { // 遍历旧表旧表节点重新映射挪动到新表 Node* cur _tables[i]; while (cur) { //重新计算节点在新表的位置 size_t hashi hs(kot(cur-_data)) % newtables.size(); //头插入新表 Node* next cur-_next; cur-_next newtables[hashi]; newtables[hashi] cur; cur next; }//while循环结束说明第i位置的链表结点已经全部挪走了需要置空 _tables[i] nullptr; } _tables.swap(newtables); } //头插入当前节点 size_t hashi hs(kot(data)) % _tables.size(); Node* newnode new Node(data); newnode-_next _tables[hashi];//newnode的下一个位置指向hashi位置的头节点 _tables[hashi] newnode; //让newnode变为头节点 _n; return { Iterator(newnode, this), true }; } //Node* Find(const K key) Iterator Find(const K key) { Hash hs; KeyofT kot; size_t hashi hs(key) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (kot(cur-_data) key) { return { cur, this }; } cur cur-_next; } return { nullptr, this }; } // 删除key链表节点删除 bool Erase(const K key) { Hash hs; size_t hashi hs(key) % _tables.size(); Node* cur _tables[hashi]; Node* prev nullptr; //提前获取链表当前结点的上一个结点 //用于判断删除的是头节点还是中间结点 while (cur) { if (kot(cur-_data) key) { if (prev nullptr) { //prev为空说明删除链表头节点 _tables[hashi] cur-_next; } else { //prev不为空说明删除中间结点 prev-_next cur-_next; } delete cur; _n--; return true; } else { prev cur; cur cur-_next; } } return false; } private: vectorNode* _tables;// 指针数组存储每个链表头指针 size_t _n 0; };unordered_set.h#include HashTable.h namespace xiaoye { templateclass K, class Hash HashFuncK struct unordered_set { struct KeyofSet { const K operator()(const K key) { return key; } }; public: typedef typename HashTableK, const K, KeyofSet, Hash::Iterator iterator; typedef typename HashTableK, const K, KeyofSet, Hash::ConstIterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } pairiterator, bool insert(const K key) { return _ht.Insert(key); } void print() { return _print(*this); } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } private: void _print(const unordered_setK, Hash s) { unordered_setK, Hash::const_iterator it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl; } HashTableK, const K, KeyofSet, Hash _ht; }; }unordered_map.h#include HashTable.h namespace xiaoye { templateclass K, class V, class Hash HashFuncK struct unordered_map { // 仿函数从Tpairconst K, V中提取key struct KeyofMap { const K operator()(const pairK, V kv) { return kv.first; } }; public: typedef typename HashTableK, pairconst K, V, KeyofMap, Hash::Iterator iterator; typedef typename HashTableK, pairconst K, V, KeyofMap, Hash::ConstIterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } pairiterator, bool insert(const pairK, V kv) { return _ht.Insert(kv); } void print() { return _print(*this); } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } V operator[](const K key) { pairiterator, bool ret _ht.Insert({ key, V() }); return ret.first-second; } private: void _print(const unordered_mapK, V, Hash s) { unordered_mapK, V, Hash::const_iterator it s.begin(); while (it ! s.end()) { cout it-first : it-second endl; it; } cout endl; } HashTableK, pairconst K, V, KeyofMap, Hash _ht; }; }测试代码(test .cpp)#includeUnorderedSet.h #includeUnorderedMap.h void test_unorderedset1() { int arr1[] { 63, 51, 16, 27, 68, 52, 1, 1, 45, 6, 17, 6 }; xiaoye::unordered_setint s1; for (auto e : arr1) { s1.insert(e); } xiaoye::unordered_setint::iterator it s1.begin(); while (it ! s1.end()) { cout *it ; it; } cout endl; s1.print(); } void test_unorderedmap1() { xiaoye::unordered_mapstring, string dict; dict.insert({ sort, 排序 }); dict.insert({ left, 左边 }); dict.insert({ right, 右边 }); /*for (auto e : dict) { cout e.first : e.second endl; } cout endl;*/ xiaoye::unordered_mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { //unordered_map允许修改second(value)但不允许修改first(key) //it-first x; cout it-first : it-second endl; it-second x; it; } cout endl; dict.print(); dict[left] 左边、剩余; dict[insert] 插入; dict[string]; dict.print(); } int main() { cout 测试unorderedset: endl; test_unorderedset1(); cout endl; cout 测试unorderedmap: endl; test_unorderedmap1(); cout endl; return 0; }结束语到此利用哈希表封装 myunordered_map/myunordered_set的实现就全部讲解完了。myunordered_map 和 myunordered_set 的封装核心是 “哈希表泛型复用 仿函数解耦”—— 通过模板参数抽象不同容器的存储需求用仿函数屏蔽 key 提取、哈希计算、相等比较的差异最终实现 “一套底层哈希表支撑两种容器功能”。掌握这套封装逻辑不仅能理解 STL unordered 系列容器的底层实现更能学会 “泛型编程 接口抽象” 的设计思想在实际开发中灵活适配不同存储场景。希望对大家学习C能有所收获C参考文档https://legacy.cplusplus.com/reference/https://zh.cppreference.com/w/cpphttps://en.cppreference.com/w/