做设计在哪个网站上找高清图,jsp网站开发教学视频,建设食品网站,旅游网站建设和开发文章目录#x1f4d6; 前言1. 复用同一个哈希桶⚡1.1 #x1f300;修改后结点的定义1.2 #x1f300;两个容器各自模板参数类型#xff1a;2. 改造之后的哈希桶⛳3. 哈希桶的迭代器#x1f525;3.1 #x1f4a5;哈希桶的begin#xff08;#xff09;和 end#xff08;…
文章目录 前言1. 复用同一个哈希桶⚡1.1 修改后结点的定义1.2 两个容器各自模板参数类型2. 改造之后的哈希桶⛳3. 哈希桶的迭代器3.1 哈希桶的begin和 end的定义3.2 operator* 和 operator-3.3 operator3.4 operator 和 operator!4. 封装unordered_map和unordered_set⭕前言
与学习红黑树和map、set的思路一样我们在学unordered_map和unordered_set时也是先学底层结构在用模拟的底层结构来自己封装一下该容器动手实践来让我们更好的学习和理解底层逻辑。
前情回顾哈希桶 传送门
这里用到的封装思路和封装map、set的思路相同都是更高维度的泛型编程。
思路复习封装map和set 传送门 1. 复用同一个哈希桶⚡
如何复用同一个哈希桶我们就需要对哈希桶进行改造将哈希桶改造的更加泛型一点既符合Key模型也符合Key_Value模型。
1.1 修改后结点的定义 所以我们这里还是和封装map和set时一样无论是Key还是Key_Value都用一个类型T来接收这里高维度的泛型哈希表中实现还是用的是Kye_Value模型K是不能省略的同样的查找和删除要用。
1.2 两个容器各自模板参数类型 如何取到想要的数据
我们给每个容器配一个仿函数各传不同的仿函数拿到想要的不同的数据
同时我们再给每个容器配一个哈希函数。
2. 改造之后的哈希桶⛳
//K -- 键值KeyT -- 数据
//unordered_map -HashTableK, pairK, V, MapKeyOfT _ht;
//unordered_set -HashTableK, K, SetKeyOfT _ht;
templateclass K, class T, class KeyOfT, class HashFunc
class HashTable
{templateclass K, class T, class KeyOfT, class HashFuncfriend class __HTIterator;typedef HashNodeT Node;
public:typedef __HTIteratorK, T, KeyOfT, HashFunc iterator;iterator begin(){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);}~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;}}size_t GetNextPrime(size_t prime){const int PRIMECOUNT 28;static const size_t primeList[PRIMECOUNT] {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};//获取比prime大那一个素数size_t i 0;for (i 0; i PRIMECOUNT; i){if (primeList[i] prime)return primeList[i];}return primeList[i];}pairiterator, bool Insert(const T data){HashFunc hf;KeyOfT kot;iterator pos Find(kot(data));if (pos ! end()){return make_pair(pos, false);}//负载因子 1 扩容 -- 平均每个桶挂一个结点if (_tables.size() _n){//size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;size_t newSize GetNextPrime(_tables.size());if (newSize ! _tables.size()){vectorNode* newTable;newTable.resize(newSize, nullptr);//遍历旧表for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];//再对每个桶挨个遍历while (cur){Node* next cur-_next;size_t hashi hf(kot(cur-_data)) % newSize;//转移到新的表中cur-_next newTable[hashi];newTable[hashi] cur;cur next;}//将原表置空_tables[i] nullptr;}newTable.swap(_tables);}}size_t hashi hf(kot(data));hashi % _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){if (_tables.size() 0){return iterator(nullptr, this);}KeyOfT kot;HashFunc hf;size_t hashi hf(key);//size_t hashi HashFunc()(key);hashi % _tables.size();Node* cur _tables[hashi];//找到指定的桶之后顺着单链表挨个找while (cur){if (kot(cur-_data) key){return iterator(cur, this);}cur cur-_next;}//没找到返回空return iterator(nullptr, this);}bool Erase(const K key){if (_tables.size() 0){return false;}HashFunc hf;KeyOfT kot;size_t hashi hf(key);hashi % _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;return true;}prev cur;cur cur-_next;}return false;}
private://指针数组vectorNode* _tables;size_t _n 0;
};研究表明除留余数法最好模一个素数
通过查STL官方库我们也发现其提供了一个取素数的函数所以我们也提供了一个直接拷贝过来 这样我们在扩容时就可以每次给素数个桶 在扩容时加了一条判断语句是为了防止素数值太大过分扩容容易直接把空间堆干崩了 3. 哈希桶的迭代器
3.1 哈希桶的begin和 end的定义 以第一个桶中第一个不为空的结点为整个哈希桶的开始结点以空结点为哈希桶的结束结点
3.2 operator* 和 operator- 同之前operator-的连续优化一样不再赘述……
3.3 operator 备注
这里要在哈希桶的类外面访问其私有成员我们要搞一个友元类迭代器类是哈希桶类的朋友这样就可以访问了 思路
判断一个桶中的数据是否遍历完 如果所在的桶没有遍历完在该桶中返回下一个结点指针 如果所在的桶遍历完了进入下一个桶 判断下一个桶是否为空 非空返回桶中第一个节点 空的话就遍历一个桶
后置和之前一眼老套路不赘述
注意
unordered_map和unordered_set是不支持反向迭代器的从底层结构我们也能很好的理解单链表找不了前驱所以不支持实现迭代器的operator- -
3.4 operator 和 operator! templateclass K, class T, class KeyOfT, class HashFunc
class HashTable;//哈希桶的迭代器
templateclass K, class T, class KeyOfT, class HashFunc
class __HTIterator
{typedef HashNodeT Node;typedef __HTIteratorK, T, KeyOfT, HashFunc Self;
public:Node* _node;__HTIterator() {};//编译器的原则是向上查找定义必须在前面否则必须先声明HashTableK, T, KeyOfT, HashFunc* _pht;__HTIterator(Node* node, HashTableK, T, KeyOfT, HashFunc* pht):_node(node), _pht(pht){}Self operator(){if (_node-_next){ _node _node-_next;}else//当前桶已经走完了要走下一个桶{KeyOfT kot;HashFunc hf;size_t hashi hf(kot(_node-_data)) % _pht-_tables.size();hashi;//找下一个不为空的桶 -- 访问到了哈希表中私有的成员友元for (; hashi _pht-_tables.size(); hashi){if (_pht-_tables[hashi]){_node _pht-_tables[hashi];break;}}//没有找到不为空的桶用nullptr去做end标识if (hashi _pht-_tables.size()){_node nullptr;}}return *this;}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s) const{return _node ! s._node;}bool operator(const Self s) const{return _node s._node;}
};编译器的原则是向上查找定义必须在前面否则必须先声明 4. 封装unordered_map和unordered_set⭕
有了上面的哈希桶的改装我们这里的对map和set的封装就显得很得心应手了。
unordered_map的封装
templateclass K, class V, class HashFunc DefaultHashK
class unordered_map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
public:typedef typename Bucket::HashTableK, pairK, V, MapKeyOfT, HashFunc::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){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 insert(make_pair(key, V()));return ret.first-second;}private:Bucket::HashTableK, pairK, V, MapKeyOfT, HashFunc _ht;
};这里unordered_map中的operator[ ]我们知道其原理之后模拟实现就非常方便直接调用插入函数控制好参数和返回值即可。
对unordered_set的封装
templateclass K, class HashFunc DefaultHashK
class unordered_set
{//SteKeyOfT是set专用的就用内部类struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename Bucket::HashTableK, K, SetKeyOfT, HashFunc::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){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:Bucket::HashTableK, K, SetKeyOfT, HashFunc _ht;
};
