常用的小企业网站建设,广告艺术设计专业学什么,无锡网站制作哪家正规,金华企业网站推广前言 unordered_set 和 unordered_map 两个容器的底层是哈希表实现的#xff0c;此处的封装使用的 上篇博客当中的哈希桶来进行封装#xff0c;相当于是在 哈希桶之上在套上了 unordered_set 和 unordered_map 。
哈希桶的逻辑实现#xff1a;
C - 开散列的拉链法…前言 unordered_set 和 unordered_map 两个容器的底层是哈希表实现的此处的封装使用的 上篇博客当中的哈希桶来进行封装相当于是在 哈希桶之上在套上了 unordered_set 和 unordered_map 。
哈希桶的逻辑实现
C - 开散列的拉链法哈希桶 介绍 和 实现-CSDN博客 在本篇博客当中的思路只是大体介绍这个封装过程哟点复杂如果有问题的可以参考下述 博客 对 map 和 set 两个容器的封装这两个容器是底层实现是 红黑树在这篇博客当中介绍更为详细是按照源代码当中的封装逻辑进行的模拟实现C - map 和 set 的模拟实现上篇 - 红黑树当中的仿函数 - 红黑树的迭代器实现-CSDN博客
C - set 和 map 的实现下篇- set 和 map 的迭代器实现_chihiro1122的博客-CSDN博客
基础封装 unordered_set 和 unordered_map unordered_set 基础结构
namespace unordered
{templateclass Kclass unordered_set{// set 当中从 T 当中取出 key 的仿函数struct SetKeyOfT{const K operator()(const K key){return key;}};public:bool insert(const K key){return _ht.Insert(key);}private:hash_bucket::hashK, K, SetKeyOfT _ht;};
}
unordered_map 基础结构
namespace unordered
{templateclass K, class Vclass unordered_map{// map 当中从 T 当中取出key 的仿函数struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:bool insert(const pairK, V kv){return _ht.Insert(kv);}private:hash_bucket::hashK, pairK, V, MapKeyOfT _ht;};
}
上述两个框架的实现逻辑在这里大体说明一下 在经过 unordered_set 和 unordered_map 包裹直线原本的 哈希桶在使用之上已经非常麻烦了所以一般是直接使用 在 哈希桶之上的 unordered_set 和 unordered_map 。
在 unordered_set 和 unordered_map 当中的 insert函数是直接复用 哈希桶当中的 Insert函数。
其中的 SetKeyOfT 和 MapKeyOfT 两个内部类是用来实现 在 两个容器当中的 不同取 key 逻辑的。其实 在 set 当中只有key 是不可以不写的但是在 map 当中就需要从 pair 当中的first 拿出所以为了在 哈希桶当中key 值的实现实现一份代码在 set 和 map 当中都可以使用的话就要 让 set 做出牺牲和 map 一样实现 从 T 当中 取 key 的仿函数。所以你才会看到 在 set 当中创建的 哈希桶要传入两个 K 作为哈希桶的模版参数。 而在哈希桶当中对 需要用 key 值的地方都用 set 和 map 当中实现的 仿函数来调用对 key 值的取出进行判断我们用 哈系统当中 Insert函数来做演示 bool Insert(const T data){HashFunc hf;KeyOfT kot;if (find(data)){return false;}// 负载因子 到 1 就扩容每一个桶当中都有数据if (_n _table.size()){size_t newsize _table.size() * 2;vectorNode* newTable;newTable.resize(newsize, nullptr);for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next; // 保存链表的下一个结点// 头插到新表当中size_t hashi hf(kot(cur-_data)) % newTable.size();cur-_next newTable[hashi];newTable[hashi] cur;// 向链表后迭代cur next;}}// 交换 两个表在 对象当中的指向让编译器 帮我们释放旧表的空间_table.swap(newTable); }
红黑树的参数模版 templateclass K, class T,class KeyOfT , class HashFunc DefaultHashFuncKclass hash{
·········
········
········
········
其中的 T 这模版参数在 set 当中传入的是 K而在 map 当中传入的是一个 pair这个pair 当中 存储的是一个结点的 key-value 键值对。而 KeyOfT 模版参数就是上述所说的在 set 和 map 当中实现不同 取 key 逻辑的 仿函数的类的类型。这里就是要和 set 和 map 都可以使用一个 哈希桶的代码实现泛型编程。
而 HashFunc 这个模版参数是为了 在哈希当中能以多种 类型 作为 key 值来实现的仿函数。在上一篇博客对哈希表的介绍当中有具体说明C - 开放地址法的哈希介绍 - 哈希表的仿函数例子_chihiro1122的博客-CSDN博客 哈希桶的迭代器实现 哈希桶的遍历非常的简单直接按照指针数组的顺序来遍历其中的 哈希桶就行了 但是遍历简单但是对于迭代器当中的 operator函数 和 operator--函数这两个函数的实现就要推敲一下。
比如 当it 迭代器遍历到其中某一个 结点那么 operator--如何找到上一个结点当 it 迭代器遍历到 某一个哈希桶的最后一个结点的时候operator函数如何找到下一个哈希桶的位置。
在 迭代器当中用 key 计算 hash 值也是需要用 set 和 map 当中的仿函数来调用不同的 key 值取出的方法的。
key 取出来了还有哈希桶当中的 不同类型的 key 值的计算方式也需要仿函数去计算。
首先每一个结点当中的值都是按照哈希桶的规则插入进去的我们可以计算出当前这个结点的key值计算出当前结点是在哪一个桶这样的话就可以直接从头开始遍历找到当前结点的上一个结点了也可以找到下一个桶和上一个桶。 operator()函数 在迭代器类当中存储的有当前结点的指针_node那么当 _node-_next 不为空的时候就继续遍历 这个哈希桶为空说明已经遍历到这个哈希桶的最后一个结点了就要找下一个哈希桶。
怎么找在上述已经说明了就是计算当前结点的 key 值计算当前哈希桶在指针数组的位置找到下一个 哈希桶的位置。
当找不到下一个桶
但是想找到下一个哈希桶的位置就要有 指针数组但是指着数组在 哈希桶类 内当中迭代器是另一个专门的类如果在迭代器当中取到 这个 指针数组呢
我们就在 迭代器类当中多一个 成员来存储一个 哈希桶对象的指针。这样就可以找到指针数组了。 Self operator(){if (_node-_next){// 当前桶还没完// 就继续遍历当前桶_node _node-_next;}else{// 两个仿函数类的实例化KeyOfT kot;HashFunc hf;// 计算当前结点的 hash值size_t hashi hf(kot(_node-_data)) % _pht-_table.size();// 从下一个位置查找查找下一个不为空的桶hashi;while (hashi _pht-_table.size()){// 如果遍历到的桶不为空if (_pht-_table[hashi]){// 把桶的第一个元素赋值给 _node_node _pht-_table[hashi];return *this;}else{// 如果桶为空 继续寻找下一个桶hashi;}}// 走到这说明 后面的桶都为空// 或者当前桶就是最后一个桶了_node nullptr;}return *this;}
类模板的有元 但是 哈希桶当中的 _table 这个 vector 容器是 private 的在 迭代器类当中不能访问所以此时我们就要把 迭代器 作为 哈希表的有元出现届时迭代器才能访问到 哈希表当中的 私有成员。
但是此处不是友元函数是一个类模板的 有元类模板的有元要在之前把模版参数加上
templateclass K, class T,class KeyOfT , class HashFunc DefaultHashFuncKclass hash{// 有元声明templateclass K, class T, class KeyOfT, class HashFuncfriend struct HTIterator;
··················
·················· };
哈希桶类当中的 begin和 end
找到第一个桶也很简单和上述 operator找下一个桶一样end 的话是最后一个结点的下一个位置也就是说 nullptr所以说直接构造一个空的迭代器返回就行了 iterator begin(){// 找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];// 当前桶的不为空if (cur){// 返回需要构造一个迭代器返回return iterator(cur, this);}}// 没找到就返回一个 空的迭代器return iterator(nullptr, this);}iterator end(){// 构造一个空的迭代器返回return iterator(nullptr, this);}
在 set 和 map 当中的 begin和 end也都是套用 哈希桶当中的 begin和end了
//unordered_set.htypedef typename hash_bucket::HashTableK, K, SetKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}// unordered_map.htypedef typename hash_bucket::HashTableK, pairK, V, MapKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}
哈希桶的迭代器类 和 哈希桶类的相互依赖问题
之前实现的迭代器都是 本类 当中有一个 迭代器 的 typedef那么 在本类当中就可以直接按照typedef 当中的模版参数在需要构造迭代器的地方按照这个模版参数来构造。也就是说要想用迭代器那么 本类就要在前面这样迭代器才能按照 本类来进行 定义。
但是我们本次实现的哈希表的 迭代器当中有哈希表的指针在哈希表当中还有 迭代器这是一个相互使用的场景。
当哈希表当中要用迭代器所以迭代器在 哈希表当中 最前处声明没问题。但是在 迭代器当中还有哈希表那么此时在迭代器当中的哈希表的类型编译器不认识。 所以此时就要把 哈希桶类在 迭代器上声明一下因为编译器在遇到类型的时候只会向上寻找定义那么我们在迭代器上声明一下高速编译器哈希表在下面定义了。 我们把这种方式称为 前置声明。 // 前置声明templateclass K, class T, class KeyOfT, class HashFuncclass HashTable;templateclass K, class T, class KeyOfT, class HashFuncstruct HTIterator{·············
·············
·············}templateclass K, class T,class KeyOfT , class HashFunc DefaultHashFuncKclass hash{
·············
·············
············· }
前置声明当中不用给模版的缺省参数。
const迭代器 上述实现之后虽然迭代器能够跑了但是还有一些问题在上述取出的迭代器可以修改 哈希桶的当中的key值。我们可以用 const 迭代器来解决这个问题在 以 红黑树为底层实现的 map 和 set 也使用了这样方法具体可以参考在前言当中给出的两篇博客。
const 迭代器 和 普通迭代器共用的是一个 迭代器的模版。而之所以 const 的迭代器在外部不能修改实际上也就是在 operator* 和 operator-这两个函数在返回值上做了处理返回一个 const 的 引用 或者 指针这个引用的对象 或者 指针指向的对象就不能修改了。
templateclass K, class T, class Ptr, class Ref, class KeyOfT, class HashFuncstruct HTIterator{typedef hash_bucket::HashNodeT Node;// 方便下述书写 迭代器的模版参数typedef HTIteratorK, T, Ptr, Ref, KeyOfT, HashFunc Self;Node* _node;hashtableK, T, KeyOfT, HashFunc* _pht;HTIterator(Node* node, hashtableK, T, KeyOfT, HashFunc* pht):_node(node), _pht(pht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}
····································
····································
····································}
所以我们只需要把 T* T 作为 普通迭代器operator* 和 operator-的返回值把 const T* const T 作为 普通迭代器operator* 和 operator-的返回值
因为 我们在 哈希表当中对 iterator 类 的模版参数进行了 typedef 所以我们只需要再在哈希表当中 typedef 出一个 const_iterator 而 iterator 和 const_iterator 的不同就在于 传入给迭代器模版类的 模版参数不同。
templateclass K, class T,class KeyOfT , class HashFunc DefaultHashFuncKclass hashtable{typedef HashNodeT Node;// 有元声明templateclass K, class T, class Ptr, class Ref, class KeyOfT, class HashFuncfriend struct HTIterator;public:typedef HTIteratorK, T, T*, T, KeyOfT, HashFunc iterator;typedef HTIteratorK, T, const T*, const T, KeyOfT, HashFunc const_iterator;·····················
·····················
····················· iterator begin(){// 找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];// 当前桶的不为空if (cur){// 返回需要构造一个迭代器返回return iterator(cur, this);}}// 没找到就返回一个 空的迭代器return iterator(nullptr, this);}iterator end(){// 构造一个空的迭代器返回return iterator(nullptr, this);}// const 的 begin和 endconst_iterator begin() const{// 找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];// 当前桶的不为空if (cur){// 返回需要构造一个迭代器返回return const_iterator(cur, this);}}// 没找到就返回一个 空的迭代器return const_iterator(nullptr, this);}const_iterator end() const{// 构造一个空的迭代器返回return const_iterator(nullptr, this);}}; 哈希桶迭代器的 const *this 问题 在哈希桶当中的 const 版本的 begin和 end当中返回的是一个 迭代器 此时我们调用了一个 迭代器的构造函数这个构造函数当中还传入了 当前哈希桶对象 的 this 指针。但是这个指针在 const 版本的begin和 end函数当中是被 const 修饰的但是 在构造函数当中接受 this 指针的 形参不是 const 的此时就会发生权限的放大就会报错。 当然最简单的方式就是 在构造函数的当中用一个 const 的形参去接受然后 构造函数对应初始化的成员也应该是 const 的这样才能正确接受 const 的 this 指针。
虽然在我们之前对 哈希桶当中的实现来看在迭代器当中我们并没有在迭代器当中使用哈希桶的指针来修改过 哈希桶当中的 _table 这个 vector 等等成员什么的只是从 _table 当中读数据所以是对于 const 的指针是没有问题的。
也就是说在 当前实现的 迭代器当中是不会通过 哈希表 指针修改到哈希表的在迭代器当中是使用 _node 当前迭代器指向的 结点指针来修改 到 哈希表的所以在当前是没有问题的。 而且构造函数只用写一个 const this指针的版本就足够了因为普通迭代器传过来的 普通 this 指针 转给 const 的形参是完全没有问题的是权限的缩小然后初始化给 const 的指针也是没有问题 修改之后的代码 templateclass K, class T, class Ptr, class Ref, class KeyOfT, class HashFuncstruct HTIterator{
·········const hashtableK, T, KeyOfT, HashFunc* _pht;HTIterator(Node* node, const hashtableK, T, KeyOfT, HashFunc* pht):_node(node), _pht(pht){}
·········} 库当中实现不是按照上述方式实现的他是 把 iteator 和 const_iterator 两个迭代器都实现了一遍 而且在const_iterator 当中不仅仅是 哈希桶指针是 const 的结点的指针也是 const 的。
哈希桶迭代器完整代码 // 前置声明templateclass K, class T, class KeyOfT, class HashFuncclass hashtable;// 在哈希表 的 iterator templateK, T, T* , T , KeyOfT , HashFunc// 在哈希表 的 const_iterator templateK, T, const T* , const T , KeyOfT , HashFunctemplateclass K, class T, class Ptr, class Ref, class KeyOfT, class HashFuncstruct HTIterator{typedef hash_bucket::HashNodeT Node;// 方便下述书写 迭代器的模版参数typedef HTIteratorK, T, Ptr, Ref, KeyOfT, HashFunc Self;Node* _node;hashtableK, T, KeyOfT, HashFunc* _pht;HTIterator(Node* node, hashtableK, T, KeyOfT, HashFunc* pht):_node(node), _pht(pht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){if (_node-_next){// 当前桶还没完// 就继续遍历当前桶_node _node-_next;}else{// 两个仿函数类的实例化KeyOfT kot;HashFunc hf;// 计算当前结点的 hash值size_t hashi hf(kot(_node-_data)) % _pht-_table.size();// 从下一个位置查找查找下一个不为空的桶hashi;while (hashi _pht-_table.size()){// 如果遍历到的桶不为空if (_pht-_table[hashi]){// 把桶的第一个元素赋值给 _node_node _pht-_table[hashi];return *this;}else{// 如果桶为空 继续寻找下一个桶hashi;}}// 走到这说明 后面的桶都为空// 或者当前桶就是最后一个桶了_node nullptr;}return *this;}bool operator!(const Self s){return _node ! s._node;}};// 哈希桶当中 begin 和 end 代码部分演示templateclass K, class T,class KeyOfT , class HashFunc DefaultHashFuncKclass hashtable{typedef HashNodeT Node;// 有元声明templateclass K, class T, class Ptr, class Ref, class KeyOfT, class HashFuncfriend struct HTIterator;public:typedef HTIteratorK, T, T*, T, KeyOfT, HashFunc iterator;typedef HTIteratorK, T, const T*, const T, KeyOfT, HashFunc const_iterator;hashtable(){_table.resize(10, nullptr);}iterator begin(){// 找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];// 当前桶的不为空if (cur){// 返回需要构造一个迭代器返回return iterator(cur, this);}}// 没找到就返回一个 空的迭代器return iterator(nullptr, this);}iterator end(){// 构造一个空的迭代器返回return iterator(nullptr, this);}// const 的 begin和 endconst_iterator begin() const{// 找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];// 当前桶的不为空if (cur){// 返回需要构造一个迭代器返回return const_iterator(cur, this);}}// 没找到就返回一个 空的迭代器return const_iterator(nullptr, this);}const_iterator end() const{// 构造一个空的迭代器返回return const_iterator(nullptr, this);}
·······················
·······················
·······················};
unordered_set 和 unordered_map 当中复用 哈希桶的迭代器 unordered_set set 当中只有 key 用户是不能对 这个 key 进行修改的所以在 unordered_set 当中 不管是 iterator 还是 const_iteartor 都是 const_iteartor。想实现这样的功能直接把 const_iteartor typedef 出 iterator 和 const_iteartor 就可以实现。
unordered_set 当中就只有 const 版本的 begin和 end函数实现 public:typedef typename hash_bucket::hashtableK, K, SetKeyOfT::const_iterator iterator;typedef typename hash_bucket::hashtableK, K, SetKeyOfT::const_iterator const_iterator;// 返回值是 iterator 还是 const_iterator 都一样都是 const_iteratoriterator begin() const{return _ht.begin();}iterator end() const{return _ht.end();} 如果只提供const 版本的迭代器的话不管是 const 对象还是 普通对象都可以调用它普通对象调用就是 权限的缩小const 调用就是 权限的平移。
#pragma once
#includehash.hnamespace unordered
{templateclass Kclass unordered_set{// set 当中从 T 当中取出 key 的仿函数struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename hash_bucket::hashtableK, K, SetKeyOfT::const_iterator iterator;typedef typename hash_bucket::hashtableK, K, SetKeyOfT::const_iterator const_iterator;iterator begin() const{return _ht.begin();}iterator end() const{return _ht.end();}pairiterator, bool insert(const K key){pairtypename hash_bucket::hashtableK, K, SetKeyOfT::iterator, bool pit _ht.Insert(key);return pairiterator, bool(pit.first, pit.second);}private:hash_bucket::hashtableK, K, SetKeyOfT _ht;};
} unordered_map
unordered_map 当中按照 map 和 set 当中一样的性质进行套用和封装在 unordered_map 当中的哈希桶构造的时候对 pair 当中的 key 就使用 const 的方式这样就可以修改到 value 而不修改到 key 了。 当然insert也不能再像直线一样返回一个 bool 值了得返回一个 迭代器和 bool 值pairiterator, bool。
而且 find函数也要返回一个 迭代器 修改如下
pairiterator, bool Insert(const T data){HashFunc hf;KeyOfT kot;iterator it find(kot(data));if (it ! end()){return make_pair(iterator, false);}// 负载因子 到 1 就扩容每一个桶当中都有数据if (_n _table.size()){size_t newsize _table.size() * 2;vectorNode* newTable;newTable.resize(newsize, nullptr);for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next; // 保存链表的下一个结点// 头插到新表当中size_t hashi hf(kot(cur-_data)) % newTable.size();cur-_next newTable[hashi];newTable[hashi] cur;// 向链表后迭代cur next;}}// 交换 两个表在 对象当中的指向让编译器 帮我们释放旧表的空间_table.swap(newTable); }// 计算hash值size_t hashi hf(data) % _table.size();Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;_n;return make_pair(iterator(newnode, this), true);} iterator find(const K key){HashFunc hf;KeyOfT kot;size_t hash hf(kot(key)) % _table.size();Node* cur _table[hash];while (cur){// 如果找到就返回 迭代器不在返回结点的指针if (kot(cur-_data) key)return iterator(cur, this);cur cur-_next;}return nullptr;} 在上述修改之后在 unordered_set 和 unordered_map 当中的 insert函数也要进行修改它的返回值也应该是一个 pairiterator, bool。但是在上述修改之后就会引发另一个问题如下所示
在 set 当中的insert函数的 pairiterator, bool 的iterator 是 const_iterator ; 哈希桶当中的pairiterator, bool 的 iterator 就是 iterator。就类似于 vectorint 和 vectordouble 的关系是两个模版实例化出的类型已经不是权限的放大和缩小了根本就不是一个类型了。vectorint 和 vectorconst int 两个也是不同的类型。
而 map 中不会因为map 当中的 iteartor 就是 iteratorconst_iterator 就是 const_iterator。
但是前提是 实现了 传入 iterator 就构造 const_iteartor 的const 的构造函数我们在 map 和 set 当中也就行了说明他是 一份函数代码在 iterator 和 const_iteartor 当中可以 实例化出两种函数在 iteartor 就是 传入 iterator 的拷贝构造函数在 const_iteartor 就是 传入 iterator 就构造 一个const_iteartor 的构造函数具体可以参考 map 和 set 的博客。
修改就是 增加一个 拷贝构造函数/const构造函数。 像上述的修改方式在 list 当中也支持如果用一个 iterator 取 构造 const_iterator 在 list 当中是支持的 我们可以看到it2 迭代器是 const 迭代器但是 it 是 普通 list 对象那么调用的迭代器的就是 普通迭代器像上述的方式是支持的。库当中是这样实现的 在以前的迭代器实现当中我们没有写这样的类似拷贝构造函数一样的 函数因为以前的迭代器的拷贝就是一个浅拷贝只需要拷贝迭代器当中的指针就行了而编译器自动生成的 浅拷贝的拷贝构造函数就已经够用了不需要我们在写了。而上述写了之后相当于是把 iterator 的不需要写的浅拷贝的拷贝构造函数写了把 const_iterator 的构造函数写了但是在 iterator 当中本来是不用写的编译器自己写的就够用了但是需要写一个 传入 iterator 构造 const_iterator 的构造函数写了这个函数也就相当于是把 iterator 的浅拷贝函数给写了。
而且这个函数的参数类型没有用 self 而是用的 iterator如果用 self 那么这个函数不管在哪都是一个拷贝构造函数但是用的是 iteratorT* 和 T 是写死的此处就是绝妙之处。 还需要注意的是 不同的对象但是类模版类型相同是可以访问到对方的private 对象的如果是不同累模版类型就不能了
比如 Aint, double 和 Aint, double 的两个对象是可以访问的但是如果是 Aint, double 和 Aint, const double 两个对象就不行了。在库当中可以实现是因为 人家不是类模板是 struct的。因为类有类域。 #pragma once
#includehash.hnamespace unordered
{templateclass K, class Vclass unordered_map{// map 当中从 T 当中取出key 的仿函数struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename hash_bucket::hashtableK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename hash_bucket::hashtableK, pairconst K, V, MapKeyOfT::const_iterator 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);}private:hash_bucket::hashtableK, pairconst K, V, MapKeyOfT _ht;};
}
