怎样做网站优化 关键词,服装花型图案设计网站,wordpress怎么找到作者的分类标签,wordpress微信绑定域名前言#xff1a;本篇文章继续分享新的容器unordered_map和set。前边我们分享过map和set#xff0c;其底层为红黑树#xff0c;而unordered_map和set的底层则为哈希表#xff0c;因此在unordered_map和set的实现中#xff0c;我们可以效仿许多在map和set的中就分享过的一些…前言本篇文章继续分享新的容器unordered_map和set。前边我们分享过map和set其底层为红黑树而unordered_map和set的底层则为哈希表因此在unordered_map和set的实现中我们可以效仿许多在map和set的中就分享过的一些知识所以在本篇文章中就不对分享过的知识进行重复讲解。
而unordered_map和set与map和set的区别即为红黑树和哈希表的区别。 目录
一.修改hash
二.迭代器
三.完整代码
1.unordered_map
2.unordered_set
四.总结 一.修改hash
我们所实现的普通哈希表肯定是无法直接拿来作为unordered_map和set的底层代码的所以我们需要对其进行优化修改完整代码如下
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};struct HashStringFunc
{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash e;}return hash;}
};namespace hash_bucket
{templateclass Tstruct HashNode{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}};//前置声明templateclass K, class T, class KeyOfT, class Hashclass HashTable;templateclass K, class T, class KeyOfT, class Hashstruct __Iterator{typedef HashNodeT Node;typedef __IteratorK, T, KeyOfT, Hash Self;Node* _node;HashTableK, T, KeyOfT, Hash* _pht;__Iterator(Node* node, HashTableK, T, KeyOfT, Hash* pht):_node(node),_pht(pht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}Self operator(){if (_node-_next)//当前桶没走完找到下一个节点_node _node-_next;else{//当前桶走完了找下一个不为空的桶的第一个节点KeyOfT kot;Hash hs;size_t i hs(kot(_node-_data)) % _pht-_tables.size();i;for (; i _pht-_tables.size(); i){if (_pht-_tables[i])break;}if (i _pht-_tables.size())//所有桶都走完了置nullptr_node nullptr;else_node _pht-_tables[i];}return *this;}bool operator!(const Self s){return _node ! s._node;}};templateclass K, class T, class KeyOfT, class Hashclass HashTable{typedef HashNodeT Node;public://友元templateclass K, class T, class KeyOfT, class Hashfriend struct __Iterator;typedef __IteratorK, T, KeyOfT, Hash 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(){_tables.resize(10, nullptr);_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;}}//插入pairiterator,bool Insert(const T data){KeyOfT kot;Hash hs;//判断是否存在iterator it Find(kot(data));if (it ! end())return make_pair(it,false);//扩容if (_n _tables.size()){vectorNode* newtables(_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)) % newtables.size();cur-_next newtables[hashi];newtables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtables);}size_t hashi hs(kot(data)) % _tables.size();Node* newnode new Node(data);//头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return make_pair(iterator(newnode,this), false);}//寻找iterator Find(const K key){KeyOfT kot;Hash hs;size_t hashi hs(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;Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;while (cur){if (kot(cur-_data) key){//删除的是第一个节点if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;}else{prev cur;cur cur-_next;}}return false;}private:vectorNode* _tables;//指针数组size_t _n;};}
这其中包括只对key进行操作的修改以及当插入的元素为string型时对其进行的特殊处理。都是我们之前所分享过的知识。下面我们重点来看迭代器。 二.迭代器
先来看整体结构
templateclass K, class T, class KeyOfT, class Hashstruct __Iterator{typedef HashNodeT Node;typedef __IteratorK, T, KeyOfT, Hash Self;Node* _node;HashTableK, T, KeyOfT, Hash* _pht;__Iterator(Node* node, HashTableK, T, KeyOfT, Hash* pht):_node(node),_pht(pht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}Self operator(){if (_node-_next)//当前桶没走完找到下一个节点_node _node-_next;else{//当前桶走完了找下一个不为空的桶的第一个节点KeyOfT kot;Hash hs;size_t i hs(kot(_node-_data)) % _pht-_tables.size();i;for (; i _pht-_tables.size(); i){if (_pht-_tables[i])break;}if (i _pht-_tables.size())//所有桶都走完了置nullptr_node nullptr;else_node _pht-_tables[i];}return *this;}bool operator!(const Self s){return _node ! s._node;}};
其中最为重要的莫过于运算符的重载因为我们的哈希表是闭散列的哈希桶所以是以指针数组作为底层。
在执行操作时需要先判断当前节点的next是否存在存在就直接为next节点不存在就说明当前节点已经是其所属的桶里的最后一个节点那么接下来的操作就是去寻找下一个不为空的桶的第一个节点。
此时我们需要先计算出当前节点在数组中的位置然后通过循环判断其后边的位置是否存在桶如果存在就返回新桶的第一个节点不存在就说明所有的桶都走完了此时返回空指针nullptr。 三.完整代码
1.unordered_map
#includehash.h
namespace Myunordered_map
{templateclass K,class V, class Hash HashFuncKclass 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;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}pairiterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}private:hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;};
} 2.unordered_set
#includehash.h
namespace Myunordered_set
{templateclass K, class Hash HashFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const K key){return _ht.Insert(key);}private:hash_bucket::HashTableK, const K, SetKeyOfT, Hash _ht;};
} 四.总结
关于unordered_map和set就分享这么多通过前边的知识的分享和掌握unordered_map和set的实现也是如鱼得水。
喜欢本篇文章的小伙伴记得一键三连我们下期再见
