网站流量工具,河北石家庄的大学,广告优化师培训,扬州服务器租用本文与对setmap的封装高度相似#xff0c;可以参考我之前的对setmap封装的文章#xff1a;
链接#xff1a;#xff08;没看过的话就点点我吧#x1f61a;#x1f61a;#x1f61a;#x1f61a;#x1f61a;#x1f61a;#x1f61a;#x1f61a;#x1f61a;可以参考我之前的对set·map封装的文章
链接没看过的话就点点我吧https://blog.csdn.net/Small_entreprene/article/details/143026089?fromshareblogdetailsharetypeblogdetailsharerId143026089sharereferPCsharesourceSmall_entreprenesharefromfrom_link正片开始
源码及框架分析
由于源码整体来说比较复杂我们截取框架部分
// 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
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
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的是pairconst key, value需要注意的是源码⾥⾯跟map/set源码类似命名⻛格⽐较乱这⾥⽐map和set还乱hash_set模板参数居然⽤的Value命名hash_map⽤的是Key和T命名可⻅⼤佬有时写代码也不规范乱弹琴。下⾯我们模拟⼀份⾃⼰的出来就按⾃⼰的⻛格⾛了。
模拟实现unordered_set·map
复用哈希表的框架的实现
复用的哈希表泛型化
参考源码框架unordered_map和unordered_set复⽤之前我们实现的哈希表我们这⾥相⽐源码调整⼀下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⽐较相等具体细节参考如下代码实现
框架仿函数这里实现XXXKeyofT后面会增添HashImitFunc仿函数等接口
unordered_set
templateclass K
class unordered_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:bool insert(const K key){return _ht.Insert(key);}
private:hash_bucket::HashTableK, K, SetKeyOfT _ht;
};
unordered_map
templateclass K, class V
class unordered_map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
public:bool insert(const pairK, V kv){return _ht.Insert(kv);}
private:hash_bucket::HashTableK, pairK, V, MapKeyOfT _ht;
};
支持iterator的实现 iterator核⼼源代码 template class Value, class Key, class HashFcn,class ExtractKey, class EqualKey, class Alloc
struct __hashtable_iterator {typedef hashtableValue, Key, HashFcn, ExtractKey, EqualKey, Allochashtable;typedef __hashtable_iteratorValue, Key, HashFcn,ExtractKey, EqualKey, Allociterator;typedef __hashtable_const_iteratorValue, Key, HashFcn,ExtractKey, EqualKey, Allocconst_iterator;typedef __hashtable_nodeValue 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_iteratorV, K, HF, ExK, EqK, A
__hashtable_iteratorV, 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_set的iterator也不⽀持修改我们把unordered_set的第⼆个模板参数改成const K即可HashTableK, const K, SetKeyOfT, Hash _ht; unordered_map的iterator不⽀持修改key但是可以修改value我们把unordered_map的第⼆个模板参数pair的第⼀个参数改成const K即可 HashTableK, pairconst K, V, MapKeyOfT, Hash _ht; ⽀持完整的迭代器还有很多细节需要修改具体参考下⾯题的代码
// 前置声明HTIterator会向前查找HashTable因为相互依赖
templateclass K, class T, class KeyOfT, class Hash
class HashTable;//告诉我是一个类模板上面是我的模板参数templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash
struct HTIterator
{typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash HT;typedef HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;//iterator的内容Node* _node;const HT* _ht;//const权限可以缩小为了实现const迭代器HTIterator(Node* node, const HT* ht):_node(node), _ht(ht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-_next){// 当前桶还有数据走到当前桶下一个节点_node _node-_next;}else{// 当前桶走完了找下一个不为空的桶KeyOfT kot;Hash hash;size_t hashi hash(kot(_node-_data)) % _ht-_tables.size();//_tables为私有成员需要友元声明hashi;while (hashi _ht-_tables.size()){_node _ht-_tables[hashi];if (_node)break;elsehashi;//记得不然就死循环了}// 所有桶都走完了end()给的空标识的_nodeif (hashi _ht-_tables.size()){_node nullptr;}}return *this;}
}; map⽀持[]的实现
unordered_map要⽀持[]主要需要修改insert返回值⽀持修改HashTable中的insert返回值为 pairIterator, bool Insert(const T data)有了insert⽀持[]实现就很简单了具体参考下⾯代码实现
V operator[](const K key)
{pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;
}
整体的代码实现
HashTable.h
#pragma once
#includeiostream
#includevector
#includestring
using namespace std;namespace open_address
{enum State{EXIST,//存在EMPTY,//停止DELETE//继续往后找避免删除冲突之后与其冲突的值找不到了造成误判};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};//哈希仿函数templateclass Kstruct HashImitFunc{size_t operator()(const K key){return (size_t)key;//对于自定义类型string等就不行了}};//特化//偏特化template struct HashImitFunc string{// 参考BKDR_Hash// 字符串转换成整形可以把字符ascii码相加即可// 但是直接相加的话类似abcd和bcad这样的字符串计算出是相同的// 这⾥我们使⽤BKDR哈希的思路⽤上次的计算结果去乘以⼀个质数再加上下一个字符的ASCLL码值这个质数⼀般是131等效果会⽐较好// 为了还是为了减少哈希冲突size_t operator()(const string key){size_t hash 0;for (auto e : key){hash * 131;hash e;}return hash;}};templateclass K, class V, class Hash HashImitFuncK//加一个仿函数Hash实现泛型编程解决float等的取模问题class HashTable{public:HashTable():_tables(__stl_next_prime(0)), _n(0){}//实现更好的扩容inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.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};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);return pos last ? *(last - 1) : *pos;}//插入bool Insert(const pairK, V kv){//实现不冗余if (Find(kv.first)){return false;}//负载因子0.7进行扩容操作//这里要注意一下整数/整数是向下取整应该将其中一个强制类型转换成浮点数//也可以前一个数*100.7改成7if (_n * 10 / _tables.size() 7){//vectorHashDataK, V newtables(_tables.size() * 2);//for (auto data : _tables)//{// //旧表的数据映射到新表// if (data._state EXIST)// {// size_t hash0 data.first % _tables.size();// //......// }//}//_tables.swap(newtables);//下面我们使用一个比较妙的扩容逻辑HashTableK, V, Hash newht;//sgi版本//要1不然有坑会造成扩容失败newht._tables.resize(__stl_next_prime(_tables.size() 1));//Jave版本/*_m;newht._tables.resize(pow(2, _m));*/for (auto data : _tables){//旧表的数据映射到新表if (data._state EXIST){newht.Insert(data._kv);//这样线性探测二次探测等的执行就可以一体化了,就是一种复用的思想}}_tables.swap(newht._tables);//赋值也可以但是赋值是一种深拷贝消耗比较高}Hash hash;size_t hash0 hash(kv.first) % _tables.size();size_t hashi hash0;size_t i 1;//但是如果这个表满了就会造成死循环所以进行了以上的扩容while (_tables[hashi]._state EXIST){//线性探测hashi (hash0 i) % _tables.size();i;}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}//查找HashDataK, V* Find(const K key){Hash hash;size_t hash0 hash(key) % _tables.size();size_t hashi hash0;size_t i 1;while (_tables[hashi]._state ! EMPTY){//注意细节if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}//线性探测hashi (hash0 i) % _tables.size();i;}return nullptr;}//删除bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;return true;}else{return false;}}private:vectorHashDataK, V _tables;//其实本质就是vectorpairK, V _table; 这看起来可行但是实际上在对于删除操作后的查找操作可能会造成查找失败需要再存一个状态标识size_t _n 0;//记录数据个数//从这体会//为什么哈希也叫散列//因为数据是由于哈希函数造成的分散状态的存放vector的size()并不能真正代表数据的个数};
}namespace hash_bucket
{templateclass Kstruct HashImitFunc{size_t operator()(const K key){return (size_t)key;}};templatestruct HashImitFuncstring{size_t operator()(const string s){// BKDRsize_t hash 0;for (auto ch : s){hash ch;hash * 131;}return hash;}};templateclass T//表下挂节点struct HashNode{T _data;//可以使用双向链表也可以使用单链表这里我们和库里面一样使用单链表//这也是为什么unordered_map的迭代器是单向迭代器HashNode* _next;HashNode(const T data):_data(data), _next(nullptr){}};// 前置声明HTIterator会向前查找HashTable因为相互依赖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 HashTableK, T, KeyOfT, Hash HT;typedef HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;//iterator的内容Node* _node;const HT* _ht;//const权限可以缩小为了实现const迭代器HTIterator(Node* node, const HT* ht):_node(node), _ht(ht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-_next){// 当前桶还有数据走到当前桶下一个节点_node _node-_next;}else{// 当前桶走完了找下一个不为空的桶KeyOfT kot;Hash hash;size_t hashi hash(kot(_node-_data)) % _ht-_tables.size();//_tables为私有成员需要友元声明hashi;while (hashi _ht-_tables.size()){_node _ht-_tables[hashi];if (_node)break;elsehashi;//记得不然就死循环了}// 所有桶都走完了end()给的空标识的_nodeif (hashi _ht-_tables.size()){_node nullptr;}}return *this;}};templateclass K, class T, class KeyOfT, class Hashclass HashTable{// 友元声明模板的友元要加上模板的所有参数类模板的前置声明还是友元声明都是要加上模板的所有参数templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct HTIterator;typedef HashNodeT Node;public:typedef HTIteratorK, T, T, T*, KeyOfT, Hash Iterator;typedef HTIteratorK, 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(__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;delete cur;cur next;}_tables[i] nullptr;}}//实现更好的扩容inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.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};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);return pos last ? *(last - 1) : *pos;}//插入pairIterator, 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()){vectorNode*newtables(__stl_next_prime(_tables.size()), 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 hash;size_t hashi hash(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;size_t hashi 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;}else{prev cur;cur cur-_next;}}return false;}private:vectorNode* _tables;//指针数组//vectorlistpairK,V _tables//其实也可以这样但是实现对应的迭代器就很复杂size_t _n 0;//表中存储数据得个数 };
}
Unordered_set.h
#pragma once
#includeHashTable.h
using namespace hash_bucket;
namespace rose
{templateclass K, class Hash HashImitFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename hash_bucket::HashTableK, const K, SetKeyOfT,Hash::Iterator iterator;typedef typename hash_bucket::HashTableK, 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();}pairiterator, 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::HashTableK, const K, SetKeyOfT, Hash _ht;};
}Unordered_map.h
#pragma once
#includeHashTable.h
using namespace hash_bucket;
namespace rose
{templateclass K, class V, class Hash HashImitFuncKclass unordered_map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename hash_bucket::HashTableK, pairconst K, V,MapKeyOfT, Hash::Iterator iterator;typedef typename hash_bucket::HashTableK, pairconst 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();}pairiterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}V operator[](const K key){pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}iterator Find(const K key){return _ht.Find(key);}bool Erase(const K key){return _ht.Erase(key);}private:hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;};
}
测试用例
#includeiostream
#includeUnordered_Set.h
#includeUnordered_Map.husing namespace std;
void test_set()
{rose::unordered_setint 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;rose::unordered_setint::iterator it s.begin();while (it ! s.end()){// 不⽀持修改//*it 1;cout *it ;it;}cout endl;
}
void test_map()
{rose::unordered_mapstring, string dict;dict.insert({ sort, 排序 });dict.insert({ left, 左边 });dict.insert({ right, 右边 });dict[left] 左边剩余;dict[insert] 插入;dict[string];rose::unordered_mapstring, 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;
}
int main()
{//test_set();test_map();return 0;
}
