网站开发 jsp加密,太原百度快速排名,小程序商城多少钱,北京王府井半岛酒店W...Y的主页 #x1f60a;
代码仓库分享#x1f495; 前言#xff1a;我们已经认识并实现了哈希底层的逻辑#xff0c;创建出了其开散列。现在我们要进行封装#xff0c;类比STL中的unordered_set 与 unordered_map。
目录
1. 模拟实现
1.1 哈希表的改造
1.2 unorde…
W...Y的主页
代码仓库分享 前言我们已经认识并实现了哈希底层的逻辑创建出了其开散列。现在我们要进行封装类比STL中的unordered_set 与 unordered_map。
目录
1. 模拟实现
1.1 哈希表的改造
1.2 unordered_set 与 unordered_map的封装 1. 模拟实现
1.1 哈希表的改造
1. 模板参数列表的改造
unordered_set 与 unordered_map的泛型与map与set的泛型有些类似unordered_set 与 unordered_map比map与set多一个仿函数他们都取key值并且需要一个hash值作为映射点。所以需要两个仿函数。
K:关键码类型 V: 不同容器V的类型不同如果是unordered_mapV代表一个键值对如果是 unordered_set,V 为 K KeyOfValue: 因为V的类型不同通过value取key的方式就不同我们必须使用一个仿函数进行才能实现unordered_map/set。 Hash: 哈希函数仿函数对象类型哈希函数使用除留余数法需要将Key转换为整形数字才能 取模
templateclass K, class V, class KeyOfValue, class Hash DefHashFT
class HashBucket;
只有我们调用unordered_set 与 unordered_map时编译器会识别关键字进行操作所以我们定义的仿函数可以使用类部类中
//unodered_set
templateclass K, class Hash HashFuncK
class unordered_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::iterator iterator;
};//unorder_map
templateclass K, class V, class Hash HashFuncK
class 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;
}; 所以我们HashNode中的泛型应该修改
templateclass T
struct HashNode
{HashNodeT* _next;T _data;HashNode(const T data):_next(nullptr), _data(data){}
};
2. 增加迭代器操作
我们要实现迭代器的、*、!等等因为HashNode中为单链表所以我们不需要实现--操作。
那我们应该如何实现呢 上图是散列表结构迭代器的底层就是指针所以我们就要使用指针指向桶中的元素。所以我们就要HashNode的指针与HashTable的指针作为迭代器成员。
struct __HTIterator
{typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash HT;typedef __HTIteratorK, T, KeyOfT, Hash Self;Node* _node;HT* _ht;__HTIterator(Node* node, HT* ht):_node(node), _ht(ht){}
};
begin()与end()函数非常简单begin就找vector中第一个不为空的指针返回其值即可。
iterator begin()
{for (size_t i 0; i _tables.size(); i){// 找到第一个桶的第一个节点if (_tables[i]){return iterator(_tables[i], this);}}return end();
}
end就是返回空即可
iterator end()
{return iterator(nullptr, this);
}
其实是最难实现的因为当给予一个指针时我们要桶的下一个节点如果这个桶的所以节点全部走完就要寻找下一个不为空的桶即可。
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()){if (_ht-_tables[hashi]){_node _ht-_tables[hashi];break;}hashi;}// 后面没有桶了if (hashi _ht-_tables.size()){_node nullptr;}}return *this;
} 迭代器中剩余函数
bool operator!(const Self s)
{return _node ! s._node;
}T operator*()
{return _node-_data;
}
1.2 unordered_set 与 unordered_map的封装
//unordered_set
namespace why
{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();}bool insert(const K key){return _ht.Insert(key);}private:hash_bucket::HashTableK, const K, SetKeyOfT, Hash _ht;}; //unordered_map
namespace why
{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();}bool insert(const pairK, V kv){return _ht.Insert(kv);}private:hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;}; 以上就是unordered_set 与 unordered_map的封装的全部内容具体代码在我的gitee代码库中想要的可以自行去取
