做网站 信科网站建设便宜,做网站公司未来的发展方向,wordpress cookie伪造,网站建设工程结算方式unordered_map与unordered_set的实现 文章目录 unordered_map与unordered_set的实现前言一、问题一HashTable.h 二、问题二问题三1.封装时如何取出key2.不同类型key如何建立对应关系 三、问题四问题五问题四问题五 四、实现代码MyUnorderedSet.hMyUnorderedMap.hHash…unordered_map与unordered_set的实现 文章目录 unordered_map与unordered_set的实现前言一、问题一HashTable.h 二、问题二问题三1.封装时如何取出key2.不同类型key如何建立对应关系 三、问题四问题五问题四问题五 四、实现代码MyUnorderedSet.hMyUnorderedMap.hHashTable.h 前言
在C11中新增了两个很好用的容器分别是unordered_map与unordered_set和map和set有不同之处
map与set的底层实现是平衡树——红黑树并且采取中序遍历时默认有序
而本文的unordered_map与unordered_set底层实现是哈希思想拉链法并且他的存储方式不支持排序所以是unordered
两者的查找效率综合比较会发现unordered_map与unordered_set的效率综合会更高所以在C11中支持了unordered_map与unordered_set
本文中是用哈希桶的拉链法来封装unordered_map与unordered_set 这里的封装与红黑树封装map和set的封装相似但此处会更难
具体通过解决问题来实现
HashTable的迭代器实现封装时HashTable如何取出map的key和set的key取出key后如何针对不同类型key建立映射关系如何解决Set中key不能被修改Map中key不能被修改value能被修改的问题Insert插入返回值问题以及Map[]的重载实现
关于哈希思想及其具体实现细节看我的上篇文章数据结构之哈希表 一、问题一
这里就一步步先实现iterator再实现const_iterator版本了而是直接放出能适配iterator与const_iterator的版本本质上就是用类模板泛型编程需要什么就调用什么是什么类型就返回什么类型的迭代器
这里尤为注意的一点是这里的迭代器是单向迭代器只支持而由于底层是哈希表的拉链法实现的是数组与链表结合的方式 在实现运算符重载时本质上就是在逐个遍历哈希桶而当前桶走完的时候需要进入下一个桶那么如何判断当前桶的位置以及如何找到下一个桶就需要把这个数组或者整个哈希表传过来这里我们做的是把整个哈希表传过来
注意其实将数组传过来会更简单些传哈希表会有一些问题
我们将哈希表传过来是可能要访问哈希表内的私有变量来获得下一个桶而直接在_HTIterator这个类内使用哈希表内的私有变量是不可取的所以需要在哈希表内声明友元此处还涉及编译问题由于编译器是从上往下编译代码我们将迭代器写在哈希表代码的上面而迭代器中有哈希表这里编译器并不认识哈希表因为哈希表的定义还未出现所以还需要哈希表对应的类的声明 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct _HTIterator;templateclass K, class T, class KeyOfT, class Hashclass HashTable;至于class KeyOfT 与 class Hash这两个类模板的作用则在下文中解答
HashTable.h
namespace hash_bucket
{templateclass Tstruct HashNode{HashNode(const T data):_data(data),_next(nullptr){}T _data;HashNode* _next;};templateclass K, class T, class KeyOfT, class Hashclass HashTable;templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashstruct _HTIterator{typedef HashNodeT Node;typedef _HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;typedef _HTIteratorK, T, T, T*, KeyOfT, Hash iterator;_HTIterator(Node* node, HashTableK, T, KeyOfT, Hash* pht):_node(node),_pht(pht){}_HTIterator(Node* node, const HashTableK, T, KeyOfT, Hash* pht):_node(node), _pht(pht){}_HTIterator(const iterator x):_node(x._node), _pht(x._pht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){Hash hf;KeyOfT kot;size_t hashi hf(kot(_node-_data)) % _pht-_t.size();if (_node-_next ! nullptr){_node _node-_next;}else{hashi;while (hashi _pht-_t.size()){if (_pht-_t[hashi]){_node _pht-_t[hashi];break;}hashi;}}if (hashi _pht-_t.size()){_node nullptr;}return *this;}bool operator(const Self it){return _node it._node;}bool operator!(const Self it){return _node ! it._node;}const HashTableK, T, KeyOfT, Hash* _pht;Node* _node;};templateclass K, class T, class KeyOfT, class Hashclass HashTable{typedef HashNodeT Node;templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct _HTIterator;public:HashTable(size_t n 10){_t.resize(n);}typedef _HTIteratorK, T, T, T*, KeyOfT, Hash iterator;typedef _HTIteratorK, T, const T, const T*, KeyOfT, Hash const_iterator;iterator begin(){size_t hashi 0;while (hashi _t.size()){if (_t[hashi]){break;}hashi;}if (hashi _t.size()){return iterator(nullptr, this);}return iterator(_t[hashi], this);}iterator end(){return iterator(nullptr, this);}const_iterator begin()const{size_t hashi 0;while (hashi _t.size()){if (_t[hashi]){break;}hashi;}if (hashi _t.size()){return iterator(nullptr, this);}return iterator(_t[hashi], this);}const_iterator end()const{return iterator(nullptr, this);}pairiterator,bool Insert(const T data){KeyOfT kot;Hash hf;iterator ret Find(kot(data));if (ret ! end()){return make_pair(ret, false);}//扩容if (_n / _t.size() 1){size_t newsize _t.size() * 2;HashTable newtable(newsize);for (int i 0; i _n; i){Node* cur _t[i];while (cur){Node* next cur-_next;size_t hashi hf(kot(cur-_data)) % newsize;cur-_next newtable._t[hashi];newtable._t[hashi] cur;cur next;}_t[i] nullptr;}swap(_t, newtable._t);}size_t hashi hf(kot(data)) % _t.size();Node* newnode new Node(data);newnode-_next _t[hashi];_t[hashi] newnode;_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K key){Hash hf;KeyOfT kot;size_t hashi hf(key) % _t.size();Node* cur _t[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur, this);}cur cur-_next;}return iterator(nullptr, this);}bool Erase(const K key){Hash hf;KeyOfT kot;size_t hashi hf(key) % _t.size();Node* cur _t[hashi];Node* prev nullptr;if (kot(cur-_data) key){_t[hashi] cur-_next;delete cur;return true;}while (cur){if (kot(cur-_data) key){prev-_next cur-_next;delete cur;_n--;return true;}prev cur;cur cur-_next;}return false;}private:vectorHashNodeT* _t;size_t _n 0;};
}二、问题二问题三
1.封装时如何取出key
首先解释一下问题我们的目的是将unordered_map与unordered_set用哈希表封装实现map中存的是pairset中存的是key而如何用一份哈希表适配两种结构呢
在封装的时候解决这个问题在unordered_map与unordered_set中写一个内部类这个类之中实现了一个仿函数用来返回key并且将其传给哈希表内 templateclass K, class V, class Hash HashFuncKclass unordered_map{public:struct KeyOfT{const K operator()(const pairK, V kv){return kv.first;}};private:hash_bucket::HashTableK, pairconst K, V, KeyOfT, Hash _ht;};
templateclass K, class Hash HashFuncKclass unordered_set{public:struct KeyOfT{const K operator()(const K key){return key;}};private:hash_bucket::HashTableK, K, KeyOfT, Hash _ht;};2.不同类型key如何建立对应关系
本文的拉链法中使用的哈希函数是除留余数法如果key是int类型的话那正好可以直接用key除但如果key是string或者自定义类型那么就不能够直接除了则需要将其转换成int类型另外一个模板参数Hash则是将其转换方式传给哈希表
如果是内置类型的floatdouble之类的我们可以直接强转成size_t返回 如果是string类型由于string比较常用我们可以为string搞个特化默认支持string
上面两个都是默认支持的用默认缺省值就行不需要手动传Hash
而如果是自定义类型则需要使用者通过接口手动传Hash因为默认的缺省值用不了
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash * 13;hash e;}return hash;}
};三、问题四问题五
问题四与问题五与set与map用红黑树封装的问题相同
问题四
set的iterator和const_iterator都是红黑树的const_iterator复用而来 map中的iterator是红黑树的iterator复用而来const_iterator是红黑树的const_iterator复用而来 既然set中的迭代器都是const_iterator所以key自然不能被修改 typedef typename hash_bucket::HashTableK, K, KeyOfT, Hash::const_iterator iterator;typedef typename hash_bucket::HashTableK, K, KeyOfT, Hash::const_iterator const_iterator;map解决key不能被修改value能被修改的原理也很简单就是在实例化的时候声明第二个模板参数——在map中也就是pairpair的first是const类型 private:hash_bucket::HashTableK, pairconst K, V, KeyOfT, Hash _ht;问题五
unordered_map与unordered_set与map和set的红黑树封装相同insert的返回值都是一个键值对
first是一个迭代器second是一个bool类型
基于此性质引出了map的计数功能可以通过insert返回的迭代器查看是否有key值如果不存在则插入将value值赋值为1如果key已经存在则通过insert返回的迭代器将value以此实现计数功能所以map实现了operator[]用来计数 V operator[](const K key){return _ht.Insert(make_pair(key, V())).first-second;}四、实现代码
MyUnorderedSet.h
#include HashTable.hnamespace Tlzns
{templateclass K, class Hash HashFuncKclass unordered_set{public:struct KeyOfT{const K operator()(const K key){return key;}};typedef typename hash_bucket::HashTableK, K, KeyOfT, Hash::const_iterator iterator;typedef typename hash_bucket::HashTableK, K, KeyOfT, Hash::const_iterator const_iterator;iterator begin()const{return _ht.begin();}iterator end()const{return _ht.end();}pairiterator, bool Insert(const K key){auto ret _ht.Insert(key);return pairiterator, bool(iterator(ret.first._node, ret.first._pht), ret.second);}bool Erase(const K key){return _ht.Erase(key);}iterator Find(const K key){return _ht.Find(key);}private:hash_bucket::HashTableK, K, KeyOfT, Hash _ht;};void test_set(){unordered_setint us;us.Insert(5);us.Insert(15);us.Insert(52);us.Insert(3);unordered_setint::iterator it us.begin();while (it ! us.end()){//*it 5;cout *it ;it;}cout endl;for (auto e : us){cout e ;}cout endl;}
}
MyUnorderedMap.h
#include HashTable.hnamespace Tlzns
{templateclass K, class V, class Hash HashFuncKclass unordered_map{public:struct KeyOfT{const K operator()(const pairK, V kv){return kv.first;}};typedef typename hash_bucket::HashTableK, pairconst K, V, KeyOfT, Hash::iterator iterator;typedef typename hash_bucket::HashTableK, pairconst K, V, 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();}pairiterator, bool Insert(const pairK, V kv){return _ht.Insert(kv);}bool Erase(const K key){return _ht.Erase(key);}iterator Find(const K key){return _ht.Find(key);}V operator[](const K key){return _ht.Insert(make_pair(key, V())).first-second;}private:hash_bucket::HashTableK, pairconst K, V, KeyOfT, Hash _ht;};void test_map(){unordered_mapstring, string dict;dict.Insert(make_pair(sort, ));dict.Insert(make_pair(string, ));dict.Insert(make_pair(insert, ));unordered_mapstring, string::const_iterator it dict.begin();for (auto kv : dict){//kv.first x;kv.second x;cout kv.first : kv.second endl;}cout endl;string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };unordered_mapstring, int count_map;for (auto e : arr){count_map[e];}for (auto kv : count_map){cout kv.first : kv.second endl;}cout endl;}
}HashTable.h
#include iostream
#include vectorusing namespace std;templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash * 13;hash e;}return hash;}
};namespace hash_bucket
{templateclass Tstruct HashNode{HashNode(const T data):_data(data),_next(nullptr){}T _data;HashNode* _next;};templateclass K, class T, class KeyOfT, class Hashclass HashTable;templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashstruct _HTIterator{typedef HashNodeT Node;typedef _HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;typedef _HTIteratorK, T, T, T*, KeyOfT, Hash iterator;_HTIterator(Node* node, HashTableK, T, KeyOfT, Hash* pht):_node(node),_pht(pht){}_HTIterator(Node* node, const HashTableK, T, KeyOfT, Hash* pht):_node(node), _pht(pht){}_HTIterator(const iterator x):_node(x._node), _pht(x._pht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){Hash hf;KeyOfT kot;size_t hashi hf(kot(_node-_data)) % _pht-_t.size();if (_node-_next ! nullptr){_node _node-_next;}else{hashi;while (hashi _pht-_t.size()){if (_pht-_t[hashi]){_node _pht-_t[hashi];break;}hashi;}}if (hashi _pht-_t.size()){_node nullptr;}return *this;}bool operator(const Self it){return _node it._node;}bool operator!(const Self it){return _node ! it._node;}const HashTableK, T, KeyOfT, Hash* _pht;Node* _node;};templateclass K, class T, class KeyOfT, class Hashclass HashTable{typedef HashNodeT Node;templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct _HTIterator;public:HashTable(size_t n 10){_t.resize(n);}typedef _HTIteratorK, T, T, T*, KeyOfT, Hash iterator;typedef _HTIteratorK, T, const T, const T*, KeyOfT, Hash const_iterator;iterator begin(){size_t hashi 0;while (hashi _t.size()){if (_t[hashi]){break;}hashi;}if (hashi _t.size()){return iterator(nullptr, this);}return iterator(_t[hashi], this);}iterator end(){return iterator(nullptr, this);}const_iterator begin()const{size_t hashi 0;while (hashi _t.size()){if (_t[hashi]){break;}hashi;}if (hashi _t.size()){return iterator(nullptr, this);}return iterator(_t[hashi], this);}const_iterator end()const{return iterator(nullptr, this);}pairiterator,bool Insert(const T data){KeyOfT kot;Hash hf;iterator ret Find(kot(data));if (ret ! end()){return make_pair(ret, false);}//扩容if (_n / _t.size() 1){size_t newsize _t.size() * 2;HashTable newtable(newsize);for (int i 0; i _n; i){Node* cur _t[i];while (cur){Node* next cur-_next;size_t hashi hf(kot(cur-_data)) % newsize;cur-_next newtable._t[hashi];newtable._t[hashi] cur;cur next;}_t[i] nullptr;}swap(_t, newtable._t);}size_t hashi hf(kot(data)) % _t.size();Node* newnode new Node(data);newnode-_next _t[hashi];_t[hashi] newnode;_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K key){Hash hf;KeyOfT kot;size_t hashi hf(key) % _t.size();Node* cur _t[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur, this);}cur cur-_next;}return iterator(nullptr, this);}bool Erase(const K key){Hash hf;KeyOfT kot;size_t hashi hf(key) % _t.size();Node* cur _t[hashi];Node* prev nullptr;if (kot(cur-_data) key){_t[hashi] cur-_next;delete cur;return true;}while (cur){if (kot(cur-_data) key){prev-_next cur-_next;delete cur;_n--;return true;}prev cur;cur cur-_next;}return false;}private:vectorHashNodeT* _t;size_t _n 0;};
}
