开家网站建设培训学校,熊掌号网站怎么做,专业网站定制哪家好,怎么建自己公司网站本文主要介绍unordered_map与unordered_set的封装#xff0c;此次封装主要用上文所说到的开散列,通过开散列的一些改造来实现unordered_map与unordered_set的封装 文章目录一、模板参数二、string的特化三、正向迭代器四、构造与析构五、[]的实现六、unordered_map的实现七、u…本文主要介绍unordered_map与unordered_set的封装此次封装主要用上文所说到的开散列,通过开散列的一些改造来实现unordered_map与unordered_set的封装 文章目录一、模板参数二、string的特化三、正向迭代器四、构造与析构五、[]的实现六、unordered_map的实现七、unordered_set的实现八、哈希表代码一、模板参数
由于unordered_set 是 K 模型的容器而 unordered_map 是 KV 模型的容器,所以需要对结点的参数进行改造unordered_set可以使用unordered_map也可以使用,改为T _data即可 templateclass Tstruct HashNode{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}};T模板参数可能是键值Key也可能是Key和Value构成的键值对。如果是unordered_map容器那么它传入底层哈希表的模板参数就是Key和Key和Value构成的键值对如果是unordered_set容器那么它传入底层哈希表的模板参数就是Key和Key templateclass K,class V,class HashHashFuncKclass unordered_map{private:buckethash::HashTableK, pairconst K, V, Hash, MapKeyOfT _ht;};templateclass K,class Hash HashFuncKclass unordered_set{private: buckethash::HashTableK, K, Hash, SetKeyOfT _ht;};如此就可以实现泛型了如果是unordered_set结点当中存储的是键值Key如果是unordered_map结点当中存储的就是Key, Value键值对 哈希表仿函数的支持KeyOfT
我们通过哈希计算出对应的哈希地址但是插入的时候就不能直接用data去进行比较了
对于unordered_set:data是key是可以比较的对于unordered_map:data是键值对,我们需要取出键值对的first。而data既可以是unordered_set的也可以是unordered_map的所以我们需要仿函数来实现不同容器所对应的需求然后传入
unordered_map返回kv.first
templateclass K,class V,class HashHashFuncKclass unordered_map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};}private:buckethash::HashTableK, pairconst K, V, Hash, MapKeyOfT _ht;};unordered_set返回key:
templateclass K,class Hash HashFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};private: buckethash::HashTableK, K, Hash, SetKeyOfT _ht;};这也就是Hashtable需要KeyOfT的原因所在。
二、string的特化
字符串无法取模在这里重新写一遍字符串无法取模的问题写库的大神们早就想到了 预留一个模板参数无论上层容器是unordered_set还是unordered_map我们都能够通过上层容器提供的仿函数获取到元素的键值
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 ch : key){hash * 131;//顺序abccbahash ch;}return hash;}
};string的特化符合string类型的优先走string类型
templateclass K,class V,class HashHashFuncK
class unordered_map
templateclass K,class Hash HashFuncK
class unordered_set三、正向迭代器
哈希表的正向迭代器对哈希表指针和结点指针进行了封装运算符重载可以访问下一个非空的桶所以每个正向迭代器里面存的是哈希表地址。
templateclass K, class T, class Hash, class KeyOfT
class HashTable;templateclass K,class T,class Hash,class KeyOfTstruct __HTIterator{typedef HashNodeT Node;typedef __HTIteratorK, T, Hash, KeyOfT Self;typedef HashTableK, T, Hash, KeyOfT HT;Node* _node;HT* _ht;}所以我们构造迭代器的时候需要知道节点的地址和哈希表的地址 __HTIterator(Node*node,HT*ht):_node(node),_ht(ht){}运算符重载的实现如果当前的桶还有节点那么就是当前桶下一个节点如果当前元素是所在的桶的最后一个元素那么就是下一个非空的桶了 如何去找下一个非空桶其实很简单通过当前节点的值算出当前桶的hashi然后hashi就是下一个桶了找到下一个非空桶即可 T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator !(const Self s) const{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();//当前桶的哈希地址hashi;while (hashi _ht-_tables.size()){if (_ht-_tables[hashi])//非空桶{_node _ht-_tables[hashi];break;}else{hashi;}}if (hashi _ht-_tables.size()){_node nullptr;}}return *this;}};–问题哈希表中的迭代器是单向迭代器并没有反向迭代器所以没有实现–-运算符的重载若是想让哈希表支持双向遍历可以考虑将哈希桶中存储的单链表结构换为双链表结构。
存在的小细节 templateclass K,class T,class Hash,class KeyOfTclass HashTable{typedef HashNodeT Node;templateclass K,class T,class Hash,class KeyOfTfriend struct __HTIterator;public:typedef __HTIteratorK, T, Hash, KeyOfT iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(_tables[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}private:vectorNode* _tables;size_t _n 0;};运算符重载去寻找下一个结点时会访问_tables,而_tables是哈希表中的私有成员所以我们需要把迭代器__HTIterator声明为哈希表的友元
正向迭代器__HTIterator的typedef放在了public,这是为了外部能够使用我们的typedef之后的正向迭代器
还需要注意的是哈希表的 const 迭代器不能复用普通迭代器的代码我们查看源码 这与我们之前所复用的不同上面stl源码中可以看到并没有用以前的复用
这是因为如果使用const版本那么_tables使用[]返回的就是const版本那么Node*就相当于是const Node*,就会导致权限放大无法构造;如果改成const HT* _ht; const Node* _node;又会导致[]不能修改的问题: 四、构造与析构
默认构造
HashTable():_n(0){_tables.resize(__stl_next_prime(0));}析构函数
哈希表当中存储的结点都是new出来的所以哈希表被析构时必须delete。在析构哈希表时我们只需要遍历取出非空的哈希桶遍历哈希桶当中的结点并进行释放即可 ~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;}}五、[]的实现
要想实现[]我们需要先把Insert的返回值修改成pairiterator,bool,最后的返回值也要一起修改
如果有重复的元素就返回这个找到it迭代器 没有重复的就返回newnode迭代器 pairiterator, bool Insert(const Tdata){KeyOfT kot;iterator it Find(kot(data));if (it ! end()){return make_pair(it, false);}if (_tables.size() _n){vectorNode* newTables;newTables.resize(__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 Hash()(kot(cur-_data))% newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi Hash()(kot(data)) % _tables.size();Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return make_pair(iterator(newnode,this),true);}六、unordered_map的实现
#pragma once#include HashTable.h
namespace hwc
{templateclass K,class V,class HashHashFuncKclass unordered_map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename buckethash::HashTableK, pairconst K, V, Hash, MapKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const pairK, V data){return _ht.Insert(data);}V operator[](const K key){pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}private:buckethash::HashTableK, pairconst K, V, Hash, MapKeyOfT _ht;};void test_unordered_map(){string arr[] { 苹果,香蕉,苹果,西瓜,哈密瓜};unordered_mapstring, int countMap;for (auto e : arr){countMap[e];}for (const auto kv : countMap){cout kv.first : kv.second endl;}}
}七、unordered_set的实现
#pragma once#include HashTable.hnamespace hwc
{templateclass K,class Hash HashFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename buckethash::HashTableK, K, Hash, SetKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const K key){return _ht.Insert(key);}private: buckethash::HashTableK, K, Hash, SetKeyOfT _ht;};void test_unordered_set(){unordered_setint us;us.insert(13);us.insert(3);us.insert(23);us.insert(5);us.insert(5);us.insert(6);us.insert(15);us.insert(223342);us.insert(22);unordered_setint::iterator it us.begin();while (it ! us.end()){cout *it ;it;}cout endl;for (auto e : us){cout e ;}cout endl;}
}八、哈希表代码
#pragma once
#pragma once#include iostream
#include string
#include vector
using 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 ch : key){hash * 131;//顺序abccbahash ch;}return hash;}
};//开散列
namespace buckethash
{templateclass Tstruct HashNode{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}};templateclass K, class T, class Hash, class KeyOfTclass HashTable;templateclass K,class T,class Hash,class KeyOfTstruct __HTIterator{typedef HashNodeT Node;typedef __HTIteratorK, T, Hash, KeyOfT Self;typedef HashTableK, T, Hash, KeyOfT HT;Node* _node;HT* _ht;__HTIterator(Node*node,HT*ht):_node(node),_ht(ht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator !(const Self s) const{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();hashi;while (hashi _ht-_tables.size()){if (_ht-_tables[hashi]){_node _ht-_tables[hashi];break;}else{hashi;}}if (hashi _ht-_tables.size()){_node nullptr;}}return *this;}};templateclass K,class T,class Hash,class KeyOfTclass HashTable{typedef HashNodeT Node;templateclass K,class T,class Hash,class KeyOfTfriend struct __HTIterator;public:typedef __HTIteratorK, T, Hash, KeyOfT iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(_tables[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}HashTable():_n(0){_tables.resize(__stl_next_prime(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;}}pairiterator, bool Insert(const Tdata){KeyOfT kot;iterator it Find(kot(data));if (it ! end()){return make_pair(it, false);}if (_tables.size() _n){vectorNode* newTables;newTables.resize(__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 Hash()(kot(cur-_data))% newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi Hash()(kot(data)) % _tables.size();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;size_t hashi Hash()(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur, this);}else{cur cur-_next;}}return end();}bool Erase(const K key){size_t hashi Hash()(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){if (cur _tables[hashi]){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_n;return true;}else{prev cur;cur cur-_next;}}return false;}inline unsigned long __stl_next_prime(unsigned long n){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};for (int i 0; i __stl_num_primes; i){if (__stl_prime_list[i] n){return __stl_prime_list[i];}}return __stl_prime_list[__stl_num_primes - 1];}private:vectorNode* _tables;size_t _n 0;};
}本篇到此结束…
