【STL】unordered_set 和 unordered_map的模拟实现

一、哈希表的改造

1. 模板参数列表的改造
2. 增加迭代器操作
3. 增加通过key获取value操作

#pragma once#include<iostream>
#include<vector>
#include<cassert>
#include<algorithm>
using namespace std;//状态
enum State
{Empty,Delete,Exit
};//哈希表中的数据
template<class T>
struct HashNode
{T _t;HashNode* next;HashNode(const T& t) :_t(t), next(nullptr) {}
};template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash>
struct HashIterator
{typedef HashNode<T> Node;typedef HashIterator self;Node* _node;vector<Node*> _ht;HashIterator(Node* node,const vector<Node*>&ht):_node(node),_ht(ht){}self& operator++(){//有下一个节点if (_node->next){_node = _node->next;}else{size_t hashi = Hash()(KeyOfT()(_node->_t)) % _ht.size();hashi++;while (hashi < _ht.size()){if (_ht[hashi])	break;hashi++;}if (hashi == _ht.size())_node = nullptr;else_node = _ht[hashi];}return *this;}self operator++(int){self temp(_node);++_node;return temp;}Ptr operator->(){return &_node->_t;}Ref operator*(){return _node->_t;}bool operator!=(const HashIterator& ht){return _node != ht._node;}bool operator==(const HashIterator& ht){return _node == ht._node;}
};template<class K, class T,class KeyOfT, class Hash>
class HashTable
{typedef HashNode<T> Node;
public://迭代器typedef HashIterator<K, T, T&,T*,KeyOfT, Hash> iterator;typedef HashIterator<K, T, const T&,const T*,KeyOfT, Hash> const_iterator;iterator begin(){if(_n==0)return end();size_t i = 0;while ( i<_ht.size()){if(_ht[i])return  iterator(_ht[i], _ht);i++;}return end();}const_iterator begin()const{if (_n == 0)return end();size_t i = 0;while (i < _ht.size()){if (_ht[i])return  iterator(_ht[i], _ht);i++;}return end();}iterator end(){return iterator(nullptr, _ht);}const_iterator end()const{return iterator(nullptr, _ht);}HashTable(){_ht.resize(10);_n = 0;}//查找iterator find(const K& key){size_t hashi = Hash()(key) % _ht.size();//定位Node* cur = _ht[hashi];while (cur){if (KeyOfT()(cur->_t) == key)return iterator(cur,_ht);cur = cur->next;}return iterator(nullptr, _ht);}pair<iterator,bool> insert(const T& t){iterator ret = find(KeyOfT()(t));if (ret._node)return {ret,false };//扩容if (_n == _ht.size()){vector<Node*> newht(_ht.size() * 2,nullptr);for (int i = 0; i < _ht.size(); i++){Node* cur = _ht[i];while (cur){Node* next = cur->next;size_t hashi = Hash()(KeyOfT()(_ht[i]->_t)) % newht.size();if (newht[i] == nullptr)newht[i] = cur;else{cur->next = newht[i];newht[i] = cur;}_ht[i] = next;}}_ht.swap(newht);}size_t hashi = Hash()(KeyOfT()(t)) % _ht.size();//定位Node* newnode = new Node(t);newnode->next = _ht[hashi];_ht[hashi] = newnode;_n++;return { {newnode,_ht},true };}iterator erase(const K& key){size_t hashi = Hash()(key) % _ht.size();//定位Node* prev = nullptr;Node* cur = _ht[hashi];Node* ret = nullptr;while (cur){if (KeyOfT()(cur->_t) == key){Node* temp = cur;ret = ++temp;if (prev == nullptr){					_ht[hashi] = nullptr;}else{prev->next = cur->next;}delete cur;cur = nullptr;_n--;return{ ret, _ht };}prev = cur;cur = cur->next;}return { nullptr,_ht };}
private:vector<Node*> _ht;size_t _n;
};

二、unordered_set 的模拟实现

#pragma once#include"HashBucket.h"
//对于int 、double、size_t 、int* 等类型
template<class K>
struct HashFunc_set
{size_t operator()(const K& key){return size_t(key);}
};//对于string 的特化处理
template<>
struct HashFunc_set<string>
{size_t operator()(const string& key){size_t ret = 0;for (const auto& e : key)ret = ret * 31 + e;return ret;}
};template<class K,class Hash = HashFunc_set<K>>
class unordered_set
{typedef K T;//和map相称struct KeyOfT{const K& operator()(const T& t){return t;}};typedef typename HashTable<K, T, KeyOfT, Hash>::iterator iterator;typedef typename HashTable<K, T, KeyOfT, Hash>::const_iterator const_iterator;
public:iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin()const{return _ht.begin();}const_iterator end()const{return _ht.end();}iterator find(const K& key){return _ht.find(key);}pair<iterator, bool> insert(const T& t){return _ht.insert(t);}iterator erase(const K& key){return _ht.erase(key);}
private:HashTable<K, T, KeyOfT, Hash> _ht;
};

三、unordered_map 的模拟实现

#pragma once#include"HashBucket.h"
//对于int 、double、size_t 、int* 等类型
template<class K>
struct HashFunc_map
{size_t operator()(const K& key){return size_t(key);}
};//对于string 的特化处理
template<>
struct HashFunc_map<string>
{size_t operator()(const string& key){size_t ret = 0;for (const auto& e : key)ret = ret * 31 + e;return ret;}
};template<class K,class V,class Hash= HashFunc_map<K>>
class unordered_map
{typedef pair<K, V> T;//和map相称struct KeyOfT{const K& operator()(const T& t){return t.first;}};typedef typename HashTable<K, T,KeyOfT, Hash>::iterator iterator;typedef typename HashTable<K, T,KeyOfT, Hash>::const_iterator const_iterator;
public:iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin()const{return _ht.begin();}const_iterator end()const{return _ht.end();}iterator find(const K& key){return _ht.find(key);}pair<iterator, bool> insert(const T& t){return _ht.insert(t);}iterator erase(const K& key){return _ht.erase(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert({ key,V() });return ret.first->second;}
private:HashTable<K, T,KeyOfT,Hash> _ht;
};