C++之unordered封装

目录

一、哈希表的修改

1.1、哈希表节点结构

1.2、迭代器

1.3、哈希表结构

1.4、完整代码

二、unordered_map的实现

二、unordered_set的实现

---

一、哈希表的修改

注意：这里我们使用哈希桶来封装unordered_map和unordered_set。

1.1、哈希表节点结构

template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};

因为我们要复用哈希表，即使用同一份哈希表代码来封装unordered_map和unordered_set，所以这里将模版参数改为T，T即要存储的数据类型，对于unordered_set而言，T直接就是要存储的数据类型；对于unordered_map而言，T是pair类型的。

在插入方法中，我们使用有参构造，在创建节点时直接将数据通过构造函数赋值进去，所以这里还实现了一个构造函数。

1.2、迭代器

iterator核心源码：

template <class Value, class Key, class HashFcn,class ExtractKey, class EqualKey, class Alloc>struct __hashtable_iterator {typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>hashtable;typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>iterator;typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>const_iterator;typedef __hashtable_node<Value> node;typedef forward_iterator_tag iterator_category;typedef Value value_type;node* cur;hashtable* ht;__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}__hashtable_iterator() {}reference operator*() const { return cur->val; }#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }#endif /* __SGI_STL_NO_ARROW_OPERATOR */
iterator& operator++();iterator operator++(int);bool operator==(const iterator& it) const { return cur == it.cur; }bool operator!=(const iterator& it) const { return cur != it.cur; }
};template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{const node* old = cur;cur = cur->next;if (!cur) {size_type bucket = ht->bkt_num(old->val);while (!cur && ++bucket < ht->buckets.size())cur = ht->buckets[bucket];}return *this;
}

iterator实现思路分析：

• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算 符实现，迭代器像指针⼀样访问的⾏为，要注意的是哈希表的迭代器是单向迭代器。
• 这⾥的难点是operator++的实现。iterator中有⼀个指向结点的指针，如果当前桶下⾯还有结点， 则结点的指针指向下⼀个结点即可。如果当前桶⾛完了，则需要想办法计算找到下⼀个桶。这⾥的难点是反⽽是结构设计的问题，参考上面源码，我们可以知道iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶⾛完了，要计算下⼀个桶就相对容易多了，⽤key值计算出当前桶位置，依次往后找下⼀个不为空的桶即可。
• begin()返回第⼀个不为空的桶中第⼀个节点指针构造的迭代器，这⾥end()返回迭代器可以⽤空指针表⽰。
• unordered_map的iterator不⽀持修改key但是可以修改value，我们把unordered_map的第⼆个模板参数pair的第⼀个参数改成const K即可，HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;（不允许修改Key是因为数据在哈希表中存储的地址是通过Key映射的，如果修改Key，破坏了哈希表的结构）。
• unordered_set的iterator也不⽀持修改，我们把unordered_set的第⼆个模板参数改成const K即可，HashTable<K, const K, SetKeyOfT, Hash> _ht;（和unordered_map同理）。

具体代码：

	// 前置声明template<class K, class T, class KeyOfT, class Hash>class HashTable;template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>struct HTIterator{typedef HashNode<T> Node;typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;Node* _node;const HashTable<K, T, KeyOfT, Hash>* _pht;HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}Self& operator++(){if (_node->_next){//当前桶还有节点_node = _node->_next;}else{//当前桶走完了，找下一个不为空的桶KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();++hashi;while (hashi < _pht->_tables.size()){if (_pht->_tables[hashi]){break;}++hashi;}if (hashi == _pht->_tables.size()){_node = nullptr; //end()}else{_node = _pht->_tables[hashi];}}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}};

注意：这里需要对哈希表进行前置声明，因为在迭代器中用到了哈希表，但是编译器编译时是向上查找，而哈希表在下面，会因为找不到而报错，将哈希表放到上面也不行，因为哈希表里也会封装迭代器，如果哈希表在上面向上查找时就会找不到迭代器，总之必须有一个进行前置声明。另外，迭代器中重载++运算符时为了确定当前节点的位置访问了哈希表的私有成员，所以后面在哈希表中还需要进行友元声明。

1.3、哈希表结构

	template<class K, class T, class KeyOfT, class Hash>class HashTable{// 友元声明template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>friend struct HTIterator;typedef HashNode<T> Node; //节点不想让外界访问public:typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; //迭代器需要让外界访问typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;Iterator Begin(){if (_n == 0) //没有有效数据{return End();}for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return Iterator(cur, this);}}return End();}Iterator End(){return Iterator(nullptr, this);}ConstIterator Begin() const{if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return ConstIterator(cur, this);}}return End();}ConstIterator End() const{return ConstIterator(nullptr, this);}HashTable(){_tables.resize(10, nullptr);}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}pair<Iterator,bool> Insert(const T& data){KeyOfT kot;Iterator it = Find(kot(data));//去重if (it != End()){return make_pair(it,false);}Hash hs;size_t hashi = hs(kot(data)) % _tables.size();//负载因子==1  扩容if (_n == _tables.size()){// 需要新建节点和释放旧节点，效率较低//	HashTable<K, V, Hash> newHT;//	for (size_t i = 0; i < _tables.size(); i++)//	{//		Node* cur = _tables[i];//		while (cur)//		{//			newHT.Insert(cur->_kv);//			cur = cur->_next;//		}//	}//	_tables.swap(newHT._tables);vector<Node*> newtables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//旧表中的节点重新映射在新表中的位置size_t hashi = hs(kot(cur->_data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}//节点都挪到新表上了，旧表置空_tables[i] = nullptr;}_tables.swap(newtables);}//头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(Iterator(newnode,this),true);}Iterator Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return Iterator(cur,this);}cur = cur->_next;}return End();}bool Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; //指针数组size_t _n; //表中存储数据个数};}

为什么需要KeyOfT模版参数：

跟map和set相⽐⽽⾔unordered_map和unordered_set的模拟实现类结构更复杂⼀点，但是⼤框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数是K，还是pair， 那么insert内部进⾏插⼊时要⽤K对象转换成整形取模和K⽐较相等(去重)，因为pair的value不需要参与计算取模，且pair默认⽀持的是key和value⼀起⽐较相等，但实际上我们需要的是任何时候只需要⽐较K对象，所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给 HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K⽐较相等。

返回值的修改：

这里为了符合unordered_map和unordered_set的使用将Find方法的返回值改为迭代器，为了实现unordered_map的 [ ] 运算符重载，将Insert方法的返回值该为pair类型，其中返回的pair对象的first属性的值是新插入节点/原有节点的迭代器，second属性的值是bool类型，代表是否插入成功。

1.4、完整代码

namespace hash_bucket
{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};// 前置声明template<class K, class T, class KeyOfT, class Hash>class HashTable;template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>struct HTIterator{typedef HashNode<T> Node;typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;Node* _node;const HashTable<K, T, KeyOfT, Hash>* _pht;HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}Self& operator++(){if (_node->_next){//当前桶还有节点_node = _node->_next;}else{//当前桶走完了，找下一个不为空的桶KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();++hashi;while (hashi < _pht->_tables.size()){if (_pht->_tables[hashi]){break;}++hashi;}if (hashi == _pht->_tables.size()){_node = nullptr; //end()}else{_node = _pht->_tables[hashi];}}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}};template<class K, class T, class KeyOfT, class Hash>class HashTable{// 友元声明template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>friend struct HTIterator;typedef HashNode<T> Node; //节点不想让外界访问public:typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; //迭代器需要让外界访问typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;Iterator Begin(){if (_n == 0) //没有有效数据{return End();}for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return Iterator(cur, this);}}return End();}Iterator End(){return Iterator(nullptr, this);}ConstIterator Begin() const{if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return ConstIterator(cur, this);}}return End();}ConstIterator End() const{return ConstIterator(nullptr, this);}HashTable(){_tables.resize(10, nullptr);}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}pair<Iterator,bool> Insert(const T& data){KeyOfT kot;Iterator it = Find(kot(data));//去重if (it != End()){return make_pair(it,false);}Hash hs;size_t hashi = hs(kot(data)) % _tables.size();//负载因子==1  扩容if (_n == _tables.size()){// 需要新建节点和释放旧节点，效率较低//	HashTable<K, V, Hash> newHT;//	for (size_t i = 0; i < _tables.size(); i++)//	{//		Node* cur = _tables[i];//		while (cur)//		{//			newHT.Insert(cur->_kv);//			cur = cur->_next;//		}//	}//	_tables.swap(newHT._tables);vector<Node*> newtables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//旧表中的节点重新映射在新表中的位置size_t hashi = hs(kot(cur->_data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}//节点都挪到新表上了，旧表置空_tables[i] = nullptr;}_tables.swap(newtables);}//头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(Iterator(newnode,this),true);}Iterator Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return Iterator(cur,this);}cur = cur->_next;}return End();}bool Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; //指针数组size_t _n; //表中存储数据个数};}

二、unordered_map的实现

这里的实现没有什么困难，就是直接套一层壳，所有的调用最终还是去调哈希表的方法，所以这里就不在赘述了，直接上代码。

#include"HashTable.h"namespace bit
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, 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();}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_map(){unordered_map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左边，剩余";dict["insert"] = "插入";dict["string"];unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first，可以修改second//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;++it;}cout << endl;}
}

二、unordered_set的实现

这里和unordered_map一样，就是直接套一层壳，所有的调用最终还是去调哈希表的方法，所以这里就不在赘述了，直接上代码。

#include"HashTable.h"namespace bit
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, 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();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};void Print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){// *it += 1;cout << *it << " ";++it;}cout << endl;}struct Date{int _year;int _month;int _day;bool operator==(const Date& d) const{return _year == d._year&& _month == d._month&& _day == d._day;}};struct HashDate{size_t operator()(const Date& key){// 112// 121return (key._year * 31 + key._month) * 31 + key._day;}};void test_set(){unordered_set<int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };for (auto e : a){s.insert(e);}for (auto e : s){cout << e << " ";}cout << endl;unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it += 1;cout << *it << " ";++it;}cout << endl;unordered_set<Date, HashDate> us;us.insert({ 2024, 7, 25 });us.insert({ 2024, 7, 26 });Print(s);}
}