【C++ 第十七章】封装 unordered_map / unordered_set

---

声明：上一章讲授了 哈希结构的原理与实现，本章告急将上一章学过的拉链法的哈希结构封装进 unordered_map / unordered_set，以是须要先学过相干知识，才气更好吸取本章知识
上一章的链接：【C++ 第十六章】哈希




1. unordered_map / unordered_set 的 根本结构

之前封装 map 和 set 时，由于 map 的数据范例为 pair<key, value>，set 的数据范例为 key
则底层红黑树节点的数据范例为 T：T 可以是 pair<key, value>，也可以是 key，以此同时适配 map 和 set
在比力步调中，须要将节点数据的 key 和 其他节点的 key 比力，data < key
当 T 为 key 时，变量 T data，data 就是 key 范例数据：可以 data < key
当 T 为 pair<key, value> 时，变量 T data，data.first 才是 key 范例数据：不可以直接 data < key
因此须要各安闲 map 和 set 结构中，操持仿函数 KeyOfT

（1） unordered_set 的 根本结构

1. namespace my
2. {
3.         template<class K>
4.         class unordered_set
5.         {
6.                 // 仿函数：将 data 转换成 key
7.                 struct set_KeyOfT {
8.                         const K& operator()(const K& key) {
9.                                 return key;
10.                         }
11.                 };
13.         public:
14.        
16.         private:
17.                 hash_bucket::HashTable<K, K, set_KeyOfT> _ht;   // 直接封装一个哈希结构
18.         };
19. }

复制代码

（2） unordered_map 的 根本结构

1. namespace my
2. {
3.         template<class K, class V>
4.         class unordered_map
5.         {
6.                 // 仿函数：将 data 转换成 key
7.                 struct map_KeyOfT
8.                 {
9.                         const K& operator()(const pair<K, V>& kv) {
10.                                 return kv.first;
11.                         }
12.                 };
13.         public:
15.         private:
16.                 // 注意要加上类域指定，否则编译器报奇怪的错误
17.                 hash_bucket::HashTable<K, pair<K, V>, map_KeyOfT> _ht; m  // 直接封装一个哈希结构
18.         };
19. }

复制代码

2. 操持哈希表迭代器

由于我们哈希表利用 拉链法的结构，因此迭代器实际上是封装链表节点指针

2.1 前置++ 功能

实现思绪：哈希表迭代器 ++，即从当前有用数据节点到下一个有用数据节点，这有两种情况，一是当前链表节点不是尾节点，next 即为下一个有用数据节点；二是当前节点为尾节点，next为空，则须要今后遍历，跳到下一个单链表，继续探求有用数据节点
怎样从当前链表尾节点，到下一条链表？

---

---

我们这里接纳的方法：将 “哈希表” 传入迭代器类中，通过 除留余数法 获取当前哈希桶位置 hashi（这就是哈希表数组下标），hashi ++ 就可以直接跳到下一个哈希桶中了，

伪代码：讲授思绪

1. if (下一个节点不为空) {
2.         直接到下一个节点
3. }
4. else if (下一个节点为空) {
5.         除留余数法 获取当前哈希桶位置 hashi
6.         hashi++  跳到下一个桶
8.         while (hashi < 哈希表的size) {
9.                 如果下一个桶是空的，就需要一直循环，直到找到非空桶
10.         }
12.         if (hashi >= 哈希表的size：说明到最后都没有非空桶) {
13.                 指针直接指向 nullptr
14.         }
15.         else if(找到非空桶){
16.                 指针指向新链表
17.         }
18. }

复制代码

实际代码

1. // HT 是 哈希表指针
2. Self& operator++() {
3.         assert(_pNode);
5.         // 逻辑是 ++ 到下一个有效元素位置：因此需要判断下一个位置是否是空节点
6.         if (_pNode->_next != nullptr) {
7.                 _pNode = _pNode->_next;
8.         }
9.         else {
10.                 // 因为一个链表遍历完，需要重新到另一个哈希桶，因此还需要重新更新迭代器指向，需要获取哈希表信息，则传一个哈希表指针过来
11.                 KeyOfT kot;
12.                 Hash hash;
13.                 size_t hashi = hash(kot(_pNode->_data)) % (HT->_table.size());
14.                 hashi++;  // 这样就跳到下一个桶了
16.                 // 如果下一个桶是空的，就继续跳
17.                 while (hashi < (HT->_table.size())) {
18.                         if (HT->_table[hashi]) break;
19.                         hashi++;  // 这样就跳到下一个桶了
20.                 }
22.                 if (hashi >= (HT->_table.size())) {
23.                         _pNode = nullptr;
24.                 }
25.                 else {
26.                         _pNode = HT->_table[hashi];
27.                 }
28.         }
29.         return *this;
30. }

复制代码

2.2 迭代器 完备代码

一些根本的功能接口这里就不赘诉，告急是明确 前置++ 函数

1. // 前置声明，迭代器类中使用哈希表，程序会向上查找是否有哈希表代码实现，否则识别不了，需要提前声明
2. template<class K, class T, class KeyOfT, class Hash>
3. class HashTable;
6. // 迭代器
7. template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash = HashFunc<K>>
8. class HashIterator
9. {
10.         typedef HashNode<T> Node;
11.         typedef HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
13. public:
14.         Node* _pNode;   // 链表节点指针
15.         HashTable<K, T, KeyOfT, Hash>* HT; // 获取哈希表指针
17.        
18.         // 基本的功能接口
19.         Ref operator*() {
20.                 return _pNode->_data;
21.         }
22.         Ptr operator->() {
23.                 return &(_pNode->_data);
24.         }
26.         bool operator!=(const Self& it) {
27.                 return _pNode != it._pNode;
28.         }
29.         bool operator==(const Self& it) {
30.                 return _pNode == it._pNode;
31.         }
34.         // 前置++
35.         Self& operator++() {
36.                 assert(_pNode);
38.                 // 逻辑是 ++ 到下一个有效元素位置：因此需要判断下一个位置是否是空节点
39.                 // 因为一个链表遍历完，需要重新到另一个哈希桶，因此还需要重新更新迭代器指向，需要获取哈希表信息，则传一个哈希表指针过来
40.                 if (_pNode->_next != nullptr) {
41.                         _pNode = _pNode->_next;
42.                 }
43.                 else {
44.                         KeyOfT kot;
45.                         Hash hash;
46.                         size_t hashi = hash(kot(_pNode->_data)) % (HT->_table.size());
47.                         hashi++;  // 这样就跳到下一个桶了
49.                         // 如果下一个桶是空的，就继续跳
50.                         while (hashi < (HT->_table.size())) {
51.                                 if (HT->_table[hashi]) break;
52.                                 hashi++;  // 这样就跳到下一个桶了
53.                         }
55.                         if (hashi >= (HT->_table.size())) {
56.                                 _pNode = nullptr;
57.                         }
58.                         else {
59.                                 _pNode = HT->_table[hashi];
60.                         }
61.                 }
62.                 return *this;
63.         }
65.         HashIterator(Node* pNode, HashTable<K, T, KeyOfT, Hash>* pHT)
66.                 :_pNode(pNode)
67.                 , HT(pHT)
68.         {}
69. };

复制代码

3. 在哈希表中封装与应用迭代器

1. template<class K, class T, class KeyOfT, class Hash>
2. class HashTable
3. {
4.         // 将迭代器类设置成 友元，以便迭代器类可以访问该类的私有：迭代器类的 operator++ 函数实现中，需要访问哈希表类的 私有成员_table
5.         template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
6.         friend class HashIterator;
9.         typedef HashNode<T> Node;
10. public:
12.     // 定义迭代器类型 Iterator 和  Const_Iterator
13.         typedef HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
14.         typedef HashIterator<K, T, const T&, const T*, KeyOfT, Hash> Const_Iterator;
18.         // 迭代器
19.         Iterator begin() {
20.                 // 先找到有效数据节点：不是每个哈希桶都有数据的
21.                 for (size_t i = 0; i < _table.size(); ++i) {
22.                         if (_table[i]) return Iterator(_table[i], this);
23.                 }
24.         }
26.         Iterator end() {
27.                 return Iterator(nullptr, this);
28.         }
30.         Const_Iterator begin() const {
31.                 // 先找到
32.                 for (size_t i = 0; i < _table.size(); ++i) {
33.                         if (_table[i]) return Const_Iterator(_table[i], this);
34.                 }
35.         }
37.         Const_Iterator end() const {
38.                 return Const_Iterator(nullptr, this);
39.         }
41.         // ..... 其他函数
44. private:
45.         //也可以使用 list：双向带头循环链表
46.         //vector<list<pair<K, V>>> _table;  
47.         vector<Node*> _table;
48.         size_t _n = 0; // 负载因子
50.         Hash hash;
51.         KeyOfT kot;
52. };

复制代码

参考STL库的写法，以及为了后续实现 operator[] ，将 find 函数的返回值改成 Iterator，将 insert 函数的返回值改成 pair<Iterator, bool> ，而且两个函数内部一些步调对应轻微修改，这里不赘述

哈希表类完备代码

实现函数：封装迭代器 begin / end 、const_begin / const_end 、插入 insert、删除 erase、查询 find 

1. template<class K, class T, class KeyOfT, class Hash>
2. class HashTable
3. {
4.         // 将迭代器类设置成 友元，以便迭代器类可以访问该类的私有：迭代器类的 operator++ 函数实现中，需要访问哈希表类的 私有成员_table
5.         template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
6.         friend class HashIterator;
8.         typedef HashNode<T> Node;
9. public:
10.         typedef HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
11.         typedef HashIterator<K, T, const T&, const T*, KeyOfT, Hash> Const_Iterator;
13.         HashTable() {
14.                 // 一开始vector里面是随机值，不是 nullptr!! 要自己初始化
15.                 _table.resize(10, nullptr);
16.         }
18.         // 本哈希桶需要显式写析构：因为 Node* 是内置类型，只会默认析构成 nullptr，链表节点不会被处理
19.         ~HashTable() {
20.                 Node* cur = nullptr;
21.                 Node* next = nullptr;
22.                 for (size_t i = 0; i < _table.size(); ++i) {
23.                         cur = _table[i];
24.                         while (cur) {
25.                                 next = cur->_next;
26.                                 delete cur;
27.                                 cur = next;
28.                         }
29.                 }
30.         }
32.         // 迭代器
33.         Iterator begin() {
34.                 // 先找到
35.                 for (size_t i = 0; i < _table.size(); ++i) {
36.                         if (_table[i]) return Iterator(_table[i], this);
37.                 }
38.         }
39.         Iterator end() {
40.                 return Iterator(nullptr, this);
41.         }
42.         Const_Iterator begin() const {
43.                 // 先找到
44.                 for (size_t i = 0; i < _table.size(); ++i) {
45.                         if (_table[i]) return Const_Iterator(_table[i], this);
46.                 }
47.         }
48.         Const_Iterator end() const {
49.                 return Const_Iterator(nullptr, this);
50.         }
52.         Iterator find(const K& key) {
53.                 size_t hashi = hash(key) % _table.size();
55.                 Node* cur = _table[hashi];
56.                 while (cur) {
57.                         if (kot(cur->_data) == key) return Iterator(cur, this);
58.                         cur = cur->_next;
59.                 }
60.                 return end();
61.         }
63.         pair<Iterator, bool> insert(const T& data) {
64.                 // 考虑冗余
65.                 Iterator ret = find(kot(data));
66.                 if (ret != end()) {
67.                         cout << "该数据已存在" << '\n';
68.                         return make_pair(ret, false);
69.                 }
72.                 // 考虑扩容：当负载比率为 1 时，扩容（即 n == size）
73.                 // 甚至可以大于 1，即理想情况下，就是平均每个桶有 1个以上
74.                 if (_n == _table.size()) {
75.                         HashTable<K, T, KeyOfT, Hash> newTable;
76.                         newTable._table.resize(2 * _table.size());
79.                         // 若直接遍历每个节点，取数值 data insert 插入新表，会导致频繁的 new 节点，造成一定消耗
80.                         // 我们可以直接将旧表的节点 直接转接到 新表，省去new节点的消耗
81.                         for (size_t i = 0; i < _table.size(); ++i) {
82.                                 Node* cur = _table[i];
83.                                 /*while (cur) {
84.                                         newTable.insert(cur->_data);
85.                                         cur = cur->_next;
86.                                 }*/
87.                                 while (cur) {
88.                                         Node* Next = cur->_next;
89.                                         size_t hashi = hash(kot(cur->_data)) % newTable._table.size();
90.                                         cur->_next = newTable._table[hashi];
91.                                         newTable._table[hashi] = cur;
92.                                         cur = Next;
93.                                 }
94.                                 _table[i] = nullptr;
95.                         }
96.                         _table.swap(newTable._table);
97.                 }
100.                 size_t hashi = hash(kot(data)) % _table.size();
102.                 // 头插和尾插都行：头插最方便
103.                 Node* newNode = new Node(data);
105.                 newNode->_next = _table[hashi];
106.                 _table[hashi] = newNode;
108.                 _n++;
110.                 return make_pair(Iterator(newNode, this), true);
111.         }
113.         bool erase(const K& key) {
114.                 Iterator ret = find(kot(data));
115.                 if (ret._pNode == nullptr) {
116.                         cout << "该节点不存在" << '\n';
117.                         return false;
118.                 }
120.                 // 删除函数需要自己找目标节点，因为底层是单链表，没有prev，删除不好搞
121.                 size_t hashi = hash(key) % _table.size();
122.                 Node* cur = _table[hashi];
123.                 Node* prev = nullptr;
124.                 while (cur) {
125.                         if (kot(cur->_data) == key) {
126.                                 if (prev == nullptr) _table[hashi] = cur->_next;
127.                                 else prev->_next = cur->_next;
128.                                 delete cur;
129.                                 cur = nullptr;
130.                                 --_n;
131.                                 return true;
132.                         }
133.                         prev = cur;
134.                         cur = cur->_next;
135.                 }
137.                 return false;
138.         }
140. private:
141.         //也可以使用 list：双向带头循环链表
142.         //vector<list<pair<K, V>>> _table;  
143.         vector<Node*> _table;
144.         size_t _n = 0; // 负载因子
146.         Hash hash;
147.         KeyOfT kot;
148. };

复制代码

4. 美满 unordered_map / unordered_set 结构

前面实现了 哈希表迭代器 与 哈希表
因此，在 unordered_map / unordered_set 类中添加这些相干利用以美满。  【迭代器 begin/end、const_begin/const_end、插入insert、删除erase、查询find  】



4.1 u_map 的 operator[] 功能

前面实现了 insert 函数的返回值为 pair<iterator, bool>
（1）若插入乐成，则返回的 pair<iterator, bool> 中的 iterator 迭代器指向 新元素，bool == true
（2）若插入失败，则返回的 pair<iterator, bool> 中的 iterator 迭代器指向 已存在且数值雷同的谁人元素，bool == false

operator[] 返回迭代器 iterator 指向节点中数据 data.second == value

1. // operator[]
2. V& operator[](const K& key) {
3.         pair<iterator, bool> ret = _ht.insert({ key, V() });
4.         return ret.first->second;
5. }

复制代码

4.2 关于处理处罚 u_map / u_set 的 key 值不能修改

由于 unordered_map / unordered_set 底层利用 拉链法的哈希结构，须要通过 除留余数法 盘算 key 值映射的下标位置，确定该数据的存放位置
假如修改了 u_map / u_set 的 key，则 删除或查询利用时，通过 除留余数法 盘算 key 值映射的下标位置 就会出现严肃错误！！好比原来 key == 19，映射的位置 hashi == 19/10 == 9，将key修改，key == 23，映射的位置就厘革 hashi == 23/10 == 3，位置就变了！！

操持步调：将参数 key 利用 const 修饰，从源头上限定该范例的参数不能被修改
对于 unordered_set，须要将 哈希表 模板范例参数修改成 const K

1. HashTable<K, const K, set_KeyOfT, Hash> _ht;

复制代码

对于 unordered_map，须要将 哈希表 模板范例参数修改成 pair<const K, V>  

1. HashTable<K, pair<const K, V>, map_KeyOfT, Hash> _ht;

复制代码

其他某些部门也要对应修改，自行调解（通常会报错来提示你，假如不改 doge）



4.3 unordered_map 的完备代码

1. #pragma once#include"HashTable.h"namespace my{        template<class K, class V, class Hash = hash_bucket::HashFunc<K>>        class unordered_map        {                struct map_KeyOfT                {                        const K& operator()(const pair<K, V>& kv) {                                return kv.first;                        }                };        public:                // 重定名哈希表的迭代器                typedef typename hash_bucket::HashTable<K, pair<const K, V>, map_KeyOfT, Hash>::Iterator iterator;                typedef typename hash_bucket::HashTable<K, pair<const K, V>, map_KeyOfT, Hash>::Const_Iterator 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();                }                // 其他利用：插入删除+查找                pair<iterator, bool> insert(const pair<K, V>& kv) {                        return _ht.insert(kv);                }                bool erase() {                        return _ht.erase();                }                iterator find(const K& key) {                        return _ht.find();                }                // operator[]                V& operator[](const K& key) {                        pair<iterator, bool> ret = _ht.insert({ key, V() });                        return ret.first->second;                }        private:                // 注意要加上类域指定，否则编译器报希奇的错误                hash_bucket::HashTable<K, pair<const K, V>, map_KeyOfT, Hash> _ht;        };}

复制代码

4.4 unordered_set 的完备代码

1. #pragma once#include"HashTable.h"namespace my{        template<class K, class Hash = hash_bucket::HashFunc<K>>        class unordered_set        {                struct set_KeyOfT {                        const K& operator()(const K& key) {                                return key;                        }                };        public:                typedef typename hash_bucket::HashTable<K, const K, set_KeyOfT, Hash>::Iterator iterator;                typedef typename hash_bucket::HashTable<K, const K, set_KeyOfT, Hash>::Const_Iterator 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();                }                // 其他利用：插入删除+查找                pair<iterator, bool> insert(const K& key) {                        return _ht.insert(key);                }                bool erase() {                        return _ht.erase();                }                iterator find(const K& key) {                        return _ht.find();                }        private:                hash_bucket::HashTable<K, const K, set_KeyOfT, Hash> _ht;        };}

复制代码

5. 哈希表结构 完备代码：节点+迭代器+哈希函数+哈希表

1. namespace hash_bucket
2. {
3.         template<class T>
4.         struct HashNode {
5.                 typedef HashNode<T> Node;
6.                 T _data;
7.                 Node* _next;
9.                 HashNode(const T& data)
10.                         :_data(data)
11.                         ,_next(nullptr)
12.                 {}
13.         };
15.         template<class K>
16.         class HashFunc
17.         {               
18.         public:
19.                 size_t operator()(const K& key) {
20.                         return (size_t)key;
21.                 }
22.         };
23.         template<>
24.         class HashFunc<string>
25.         {
26.         public:
27.                 size_t operator()(const string& s) {
28.                         size_t n = 0;
29.                         for (auto& ch : s) {
30.                                 n += ch;  // 将字符串的每个字符的ASCLII码值相加起来，但这样还是不可完全避免冲突，如 abc 和 cba 的 ASCII码值总和是相等的，则 n 相等，取模之后也就冲突
31.                                 // 缓解冲突的一个方法：每一个字符都相乘一个 31
32.                                 n *= 31;
33.                         }
34.                         return n;
35.                 }
36.         };
39.         // 前置声明，迭代器类中使用哈希表，会向上查找是否有哈希表，否则不匹配，需要提前声明
40.         template<class K, class T, class KeyOfT, class Hash>
41.         class HashTable;
44.         // 迭代器
45.         template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash = HashFunc<K>>
46.         class HashIterator
47.         {
48.                 typedef HashNode<T> Node;
49.                 typedef HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
51.         public:
52.                 Node* _pNode;
53.                 HashTable<K, T, KeyOfT, Hash>* HT; // 获取哈希表指针
55.                 Ref operator*() {
56.                         return _pNode->_data;
57.                 }
58.                 Ptr operator->() {
59.                         return &(_pNode->_data);
60.                 }
62.                 bool operator!=(const Self& it) {
63.                         return _pNode != it._pNode;
64.                 }
65.                 bool operator==(const Self& it) {
66.                         return _pNode == it._pNode;
67.                 }
69.                 Self& operator++() {
70.                         assert(_pNode);
72.                         // 逻辑是 ++ 到下一个有效元素位置：因此需要判断下一个位置是否是空节点
73.                         // 因为一个链表遍历完，需要重新到另一个哈希桶，因此还需要重新更新迭代器指向，需要获取哈希表信息，则传一个哈希表指针过来
74.                         if (_pNode->_next != nullptr) {
75.                                 _pNode = _pNode->_next;
76.                         }
77.                         else {
78.                                 KeyOfT kot;
79.                                 Hash hash;
80.                                 size_t hashi = hash(kot(_pNode->_data)) % (HT->_table.size());
81.                                 hashi++;  // 这样就跳到下一个桶了
82.                                
83.                                 // 如果下一个桶是空的，就继续跳
84.                                 while (hashi < (HT->_table.size())) {
85.                                         if (HT->_table[hashi]) break;
86.                                         hashi++;  // 这样就跳到下一个桶了
87.                                 }
89.                                 if (hashi >= (HT->_table.size())) {
90.                                         _pNode = nullptr;
91.                                 }
92.                                 else {
93.                                         _pNode = HT->_table[hashi];
94.                                 }
95.                         }
96.                         return *this;
97.                 }
99.                 HashIterator(Node* pNode, HashTable<K, T, KeyOfT, Hash>* pHT)
100.                         :_pNode(pNode)
101.                         , HT(pHT)
102.                 {}
103.         };
105.         template<class K, class T, class KeyOfT, class Hash>
106.         class HashTable
107.         {
108.                 // 将迭代器类设置成 友元，以便迭代器类可以访问该类的私有
109.                 template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
110.                 friend class HashIterator;
112.                 typedef HashNode<T> Node;
113.         public:
114.                 typedef HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
115.                 typedef HashIterator<K, T, const T&, const T*, KeyOfT, Hash> Const_Iterator;
116.        
117.                 HashTable() {
118.                         // 一开始vector里面是随机值，不是 nullptr!! 要自己初始化
119.                         _table.resize(10, nullptr);
120.                 }
122.                 // 本哈希桶需要显式写析构：因为 Node* 是内置类型，只会默认析构成 nullptr，链表节点不会被处理
123.                 ~HashTable() {
124.                         Node* cur = nullptr;
125.                         Node* next = nullptr;
126.                         for (size_t i = 0; i < _table.size(); ++i) {
127.                                 cur = _table[i];
128.                                 while (cur) {
129.                                         next = cur->_next;
130.                                         delete cur;
131.                                         cur = next;
132.                                 }
133.                         }
134.                 }
136.                 // 迭代器
137.                 Iterator begin() {
138.                         // 先找到
139.                         for (size_t i = 0; i < _table.size(); ++i) {
140.                                 if (_table[i]) return Iterator(_table[i], this);
141.                         }
142.                 }
143.                 Iterator end() {
144.                         return Iterator(nullptr, this);
145.                 }
146.                 Const_Iterator begin() const {
147.                         // 先找到
148.                         for (size_t i = 0; i < _table.size(); ++i) {
149.                                 if (_table[i]) return Const_Iterator(_table[i], this);
150.                         }
151.                 }
152.                 Const_Iterator end() const {
153.                         return Const_Iterator(nullptr, this);
154.                 }
156.                 Iterator find(const K& key) {
157.                         size_t hashi = hash(key) % _table.size();
158.                          
159.                         Node* cur = _table[hashi];
160.                         while (cur) {
161.                                 if (kot(cur->_data) == key) return Iterator(cur, this);
162.                                 cur = cur->_next;
163.                         }
164.                         return end();
165.                 }
167.                 pair<Iterator, bool> insert(const T& data) {
168.                         // 考虑冗余
169.                         Iterator ret = find(kot(data));
170.                         if (ret != end()) {
171.                                 cout << "该数据已存在" << '\n';
172.                                 return make_pair(ret, false);
173.                         }
176.                         // 考虑扩容：当负载比率为 1 时，扩容（即 n == size）
177.                         // 甚至可以大于 1，即理想情况下，就是平均每个桶有 1个以上
178.                         if (_n == _table.size()) {
179.                                 HashTable<K, T, KeyOfT, Hash> newTable;
180.                                 newTable._table.resize(2 * _table.size());
183.                                 // 若直接遍历每个节点，取数值 data insert 插入新表，会导致频繁的 new 节点，造成一定消耗
184.                                 // 我们可以直接将旧表的节点 直接转接到 新表，省去new节点的消耗
185.                                 for (size_t i = 0; i < _table.size(); ++i) {
186.                                         Node* cur = _table[i];
187.                                         /*while (cur) {
188.                                                 newTable.insert(cur->_data);
189.                                                 cur = cur->_next;
190.                                         }*/
191.                                         while (cur) {
192.                                                 Node* Next = cur->_next;
193.                                                 size_t hashi = hash(kot(cur->_data)) % newTable._table.size();
194.                                                 cur->_next = newTable._table[hashi];
195.                                                 newTable._table[hashi] = cur;
196.                                                 cur = Next;
197.                                         }
198.                                         _table[i] = nullptr;
199.                                 }
200.                                 _table.swap(newTable._table);
201.                         }
204.                         size_t hashi = hash(kot(data)) % _table.size();
206.                         // 头插和尾插都行：头插最方便
207.                         Node* newNode = new Node(data);
209.                         newNode->_next = _table[hashi];
210.                         _table[hashi] = newNode;
212.                         _n++;
214.                         return make_pair(Iterator(newNode, this), true);
215.                 }
217.                 bool erase(const K& key) {
218.                         Iterator ret = find(kot(data));
219.                         if (ret._pNode == nullptr) {
220.                                 cout << "该节点不存在" << '\n';
221.                                 return false;
222.                         }
224.                         // 删除函数需要自己找目标节点，因为底层是单链表，没有prev，删除不好搞
225.                         size_t hashi = hash(key) % _table.size();
226.                         Node* cur = _table[hashi];
227.                         Node* prev = nullptr;
228.                         while (cur) {
229.                                 if (kot(cur->_data) == key) {
230.                                         if (prev == nullptr) _table[hashi] = cur->_next;
231.                                         else prev->_next = cur->_next;
232.                                         delete cur;
233.                                         cur = nullptr;
234.                                         --_n;
235.                                         return true;
236.                                 }
237.                                 prev = cur;
238.                                 cur = cur->_next;
239.                         }
241.                         return false;
242.                 }
244.         private:
245.                 //也可以使用 list：双向带头循环链表
246.                 //vector<list<pair<K, V>>> _table;  
247.                 vector<Node*> _table;
248.                 size_t _n = 0; // 负载因子
250.                 Hash hash;
251.                 KeyOfT kot;
252.         };
255. }

复制代码

 unordered_map / unordered_set 的 测试代码

1. void test_map() {
2.         my::unordered_map<string, string> dict;
3.         dict.insert({ "sort", "排序" });
4.         dict.insert({ "left", "左边" });
5.         dict.insert({ "right", "右边" });
7.         //dict["left"] = "左边，剩余";
8.         dict["insert"] = "插入";
9.         dict["string"];
11.         my::unordered_map<string, string>::iterator it = dict.begin();
12.         while (it != dict.end())
13.         {
14.                 // 不能修改first，可以修改second
15.                 //it->first += 'x';
16.                 it->second += 'x';
18.                 cout << it->first << ":" << it->second << endl;
19.                 ++it;
20.         }
21.         cout << endl;
22. }
25. void test_set() {
26.         my::unordered_set<string> st;
27.         st.insert({ "sort" });
28.         st.insert({ "left" });
29.         st.insert({ "right" });
31.         /*dict["left"] = "左边，剩余";
32.         dict["insert"] = "插入";
33.         dict["string"];*/
35.         my::unordered_set<string>::iterator it = st.begin();
36.         while (it != st.end())
37.         {
38.                 // 不能修改*it
39.                 //*it += 'x';
41.                 cout << *it <<  endl;
42.                 ++it;
43.         }
44.         cout << endl;
45. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金