php部署网站,衡阳营养师报考网站,免费入驻的卖货平台,个人可以建设哪些网站unordered_map和unordered_set的底层结构用到的都是在哈希表模拟实现中的哈希桶的实现方式#xff0c;哈希桶的具体实现我已经在哈希表的模拟实现里做过详细的介绍#xff0c;这边会引用里面的代码进行改造和封装#xff0c;同时为了方便操作#xff0c;同样我采用二倍扩容… unordered_map和unordered_set的底层结构用到的都是在哈希表模拟实现中的哈希桶的实现方式哈希桶的具体实现我已经在哈希表的模拟实现里做过详细的介绍这边会引用里面的代码进行改造和封装同时为了方便操作同样我采用二倍扩容的方式。
一、哈希桶的基本结构 首先对哈希桶的模版参数进行改造原本我们是直接采用K_V的结构来定义这个哈希桶但是在封装的过程中unordered_map和unordered_set的存储数据是不一样的unordered_set只存一个Key值unordered_map存储的是key_value的键值对但是他们在增删查改的中间的行为又是一样的所以我们给哈希桶多传入几个参数T表示的是我们要存储的数据让上层的容器传入决定这样就能让unordered_map和unordered_set分别存储不同的数据类型。 KeyOfT的模版参数是一个仿函数因为我们并不知道T里存储的数据究竟是一个Key还是一个Key、Value所以我要让上层的结构自己实现出怎么从T中取出Key的方法。这里也有人会疑惑那既然有了KeyOfT的这个仿函数那为什么还要传入K的模版参数呢 比如在使用查找的功能的时候我们是需要用Key找到对应的Value值如果我们只有KeyOfT的仿函数的话我们就必须要求用户传入一个完整的数据才能使用查找功能这样使用起来就会非常的不方便所以还要让上层的容器确定它的Key的类型是什么。 templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};templatestruct HashFuncstring{size_t operator()(const string s){size_t hashi 0;//BKDRfor (auto e : s){hashi e;hashi * 131;}return hashi;}};templateclass Tstruct HashNode{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}};// K 为 T 中key的类型// T 可能是键值对也可能是K// KeyOfT: 从T中提取key// Hash将key转化为整形因为哈希函数使用除留余数法templateclass K, class T, class KeyOfT, class Hashclass HashTable{typedef HashNodeT Node;public: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;}}// 插入值为data的元素如果data存在则不插入bool Insert(const T data){KeyOfT kot;Hash hs;//插入的数据已经存在if (it ! End())return false;//负载因子为1时扩容if (_n _tables.size()){vectorNode* newHT(_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)) % newHT.size();cur-_next newHT[hashi];newHT[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newHT);}size_t hashi hs(kot(data)) % _tables.size();//头插Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}// 在哈希桶中查找值为key的元素存在返回true否则返回falsebool Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();//在对应的桶里查找数据Node* cur _tables[hashi];KeyOfT kot;while (cur){if (kot(cur-_data) key)return true;cur cur-_next;}return false;}// 哈希桶中删除key的元素删除成功返回true否则返回falsebool Erase(const K key){Hash hs;KeyOfT kot;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;}else{prev cur;cur cur-_next;}}return false;}private:vectorNode* _tables; // 指针数组size_t _n 0; // 表中存储数据个数};
二、迭代器 这里的迭代器看似要传入很多的模版参数但是其实和我们在实现list时实现的迭代器没有什么本质上的区别只不过多套了几个模版参数同时这里的迭代器是一个单向迭代器所以只需要实现的功能即可。这里需要细讲的其实也就只有这个的操作。 第一种情况当前桶里还有数据那么直接接着访问下一个结点即可。 第二种情况当前桶里的数据都被访问过了但是哈希表并没有被遍历完此时我们就要去到哈希表的下一个位置去找元素这里我们就需要用到这个哈希表的数据了这里和之前实现过的迭代器都不同的地方就在这里了。我们需要使用到哈希表里的数据最重要的是我们需要去访问哈希表底层的那个数组我们不可能因为这个在迭代器里开一个数组来存储哈希表里每个头结点的信息这样不仅浪费空间还会多出很多不必要的操作这里的解决方案其实很简单给迭代器增加一个指向哈希表的指针即可。其实这样又引出了两个问题一个是这样做其实不能完全解决问题因为我们要访问的是哈希表里底层的数组这个数组是一个私有的成员变量我们在外部是没办法访问的所以我们要把这个迭代器声明成HashTable的友元类这样我们的迭代器就能访问HashTable的数组了带模版参数的友元类的声明和之前声明的友元类有一些不同点我们在声明的时候要把它的类型完整的声明出来第二个问题就是会出现报错HashTable是在迭代器后续实现的一个类编译器在编译的时候是从上往下的顺序进行的编译进行到HTIterator这里时它发现在前面的代码中没有发现HashTable也就是说编译器不认识这个类型所以就出现了这个报错这里解决这个问题的办法也很简单我们只要在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 HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;typedef HashTableK, T, KeyOfT, Hash HT;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;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-_next)_node _node-_next;else{KeyOfT kot;Hash hs;size_t hashi hs(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()){_node _ht-_tables[hashi];if (_node)break;elsehashi;}}return *this;}Node* _node;const HT* _ht;};templateclass K, class T, class KeyOfT, class Hashclass HashTable{templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct HTIterator;};
三、哈希表里的迭代器调用 这里其实很简单,就是简单的去找哈希表里的第一个数据就是Begin函数需要做的功能而End其实就是空主要是我们可以通过迭代器去改造Find函数和Insert的函数这样不仅能通过这个Insert函数实现后续unordered_map的重载[]还能方便操作。但是其实这里的ConstIterator版本的Begin函数还出现了一个问题会在后续说明。 templateclass K, class T, class KeyOfT, class Hashclass HashTable{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);}}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);}}ConstIterator End() const{return ConstIterator(nullptr, this);}pairIterator, bool Insert(const T data){KeyOfT kot;Hash hs;Iterator it Find(kot(data));//插入的数据已经存在if (it ! End())return { it ,false };//负载因子为1时扩容if (_n _tables.size()){vectorNode* newHT(_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)) % newHT.size();cur-_next newHT[hashi];newHT[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newHT);}size_t hashi hs(kot(data)) % _tables.size();//头插Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return { Iterator(newnode,this),true };}// 在哈希桶中查找值为key的元素存在返回true否则返回falseIterator Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();//在对应的桶里查找数据Node* cur _tables[hashi];KeyOfT kot;while (cur){if (kot(cur-_data) key)return Iterator(cur,this);cur cur-_next;}return End();}};
四、封装容器 其实到这里就没有什么可说的了也没有什么难点了无非就是实现一个KeyOfT的仿函数然后再对我们实现好的哈希表和迭代的功能进行调用罢了unordered_set里的细节只有一个就是在给哈希表传参的时候我们可以直接给第二个参数直接加上的const的第二个模版参数对应的是Tunordered_set存储的本来就只有一个Key值本身就是不支持修改的加上const修饰也可以防止误操作。 还有一个细节点就是我们在给迭代器传参以及定义指向哈希表的指针的时候一定要用const修饰不然就会引发第三点中说的问题ConstIterator版本的Begin和End都是被const修饰的表示Begin和End中this指针指向的对象是被const的修饰的这样原来的哈希表就变成了一个被const修饰的哈希表边此时在调用ConstIterator版本的迭代器的时候就会出现参数类型不匹配的问题但是如果用const修饰以后普通版本的迭代器传入的this指向的对象是没有被const修饰的但是权限是能给缩小的所以也不会出现错误。 templateclass K, class Hash HashFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename HashTableK, const K, SetKeyOfT, Hash::Iterator iterator;typedef typename 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:HashTableK, const K, SetKeyOfT, Hash _ht;}; unordered_map这里要多实现一个重载[]的功能这里这个写法的意思就是利用Insert的功能去找出这个Key值是否在哈希表中存在如果存在就返回它对应的结点如果不存在就会直接插入这个结点这个结点对应Value值是V类型的默认构造出来的。 return ret.first-second;的第一个.first是取到pair这个对里的第一个类型是这个一个迭代器-second的意思是我们的迭代器重载了-这个操作符这个操作符的作用是取出迭代器指向结点存储的内容也就是T类型在unordered_mapT类型是我们的pairK,V所以它的second就是我们对应的V这样就能做到Key存在时进行修改操作Key不存在时进行插入和修改的操作了。 templateclass K, class V, class Hash HashFuncKclass unordered_map{public:struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};typedef typename HashTableK, pairconst K, V, MapKeyOfT, Hash::Iterator iterator;typedef typename 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);}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}V operator[](const K key){pairiterator, bool ret _ht.Insert({ key,V() });return ret.first-second;}private:HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;};
