视差设计网站无锡高端网站定制

当前位置： 首页 > news >正文

视差设计网站,无锡高端网站定制,如何申请域名建网站,网站怎么做视频文章目录 一、unordered 系列关联式容器二、unordered_map1.1 unordered_map 介绍1.2 unordered_map 的接口说明1.2.1 unordered_map 的构造1.2.2 unordered_map 的容量1.2.3 unordered_map 的迭代器1.2.4 unordered_map 的元素访问1.2.5 unorderedmap 的查询1.2.6 unordered… 文章目录 一、unordered 系列关联式容器二、unordered_map1.1 unordered_map 介绍1.2 unordered_map 的接口说明1.2.1 unordered_map 的构造1.2.2 unordered_map 的容量1.2.3 unordered_map 的迭代器1.2.4 unordered_map 的元素访问1.2.5 unordered_map 的查询1.2.6 unordered_map 的修改操作1.2.7 unordered_map 的桶操作 三、底层结构3.1 哈希概念3.2 哈希冲突3.3 哈希函数3.3.1 直接定值法—-(常用)3.3.2 除留余数法—-(常用)3.3.3 平方取中法—-(了解)3.3.4 折叠法—-(了解3.3.5 随机数法—-(了解)3.3.6 数学分析法—-(了解) 3.4 哈希冲突解决3.4.1 闭散列3.4.1.1 线性探测3.4.1.2 闭散列开放定址法模拟实现3.4.1.3 二次探测 3.4.2 开散列3.4.2.1 开散列模拟实现 四、模拟实现 unordered_set 和 unordered_map4.1 哈希表的改造4.1.1 模板参数列表的改造4.1.2 增加迭代器操作4.1.3 修改后的哈希表 4.2 unordered_set 模拟实现4.3 unordered_map 模拟实现 五、结语 一、unordered 系列关联式容器 在 C98 中STL 提供了底层为红黑树结构的一些列关联式容器在查询时效率可以达到 O ( l o g 2 N ) O(log2^N) O(log2N)即最差情况下需要比较红黑树高度次当树中的结点非常多的时候查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在 C11 中STL 又提供了4个 unordered 系列的关联式容器这四个容器与红黑树结构的关联式容器使用方法基本类似只是其底层结构不同本文中只对 unordered_map 和 unordered_set 进行介绍unordered_multimap 和 unordered_multiset 感兴趣的小伙伴可以自行查阅文档。 二、unordered_map 1.1 unordered_map 介绍 unordered_map 是存储 keyvalue 键值对的关联式容器其允许通过 key 快速的索引到与其对应的 value。 在 unordered_map 中键值通常用于唯一的标识元素而映射值是一个对象其内容与此键值关联。键和映射值的类型可能不同。 在内部unordered_map 没有对 keyvalue 按照任何特定的顺序排序为了能在常数范围内找到 key 所对应的 valueunordered_map 将相同哈希值的键值放在相同的桶中。 unordered_map 容器通过 key 访问单个元素要比 map 快但它通常在遍历元素子集的范围迭代方面效率较低。 unordered_map 实现了直接访问操作符operator[ ]它允许使用 key 作为参数直接访问 value。 它的迭代器至少是前向迭代器单向迭代器。
1.2 unordered_map 的接口说明 1.2.1 unordered_map 的构造 函数声明功能介绍unordered_map构造不同格式的 unordered_map 对象 1.2.2 unordered_map 的容量 函数声明功能介绍bool empty() const检测 unordered_map 是否为空size_t size() const获取 unordered_map 有效元素的个数 1.2.3 unordered_map 的迭代器 函数声明功能介绍begin()返回 unordered_map 第一个元素的迭代器end()返回 unordered_map 最后一个元素下一个位置的迭代器cbegin()返回 unordered_map 第一个元素的 const 迭代器cend()返回 unordered_map 最后一个元素下一个位置的 const 迭代器 1.2.4 unordered_map 的元素访问 函数声明功能介绍operator[ ]返回与 key 对应的 value没有一个默认值 小Tips该函数中实际调用哈希桶的插入操作用参数 key 与 V() 构造一个默认值往底层哈希桶中插入如果 key 不在哈希桶中插入成功返回 V()。插入失败说明 key 已经在哈希桶中将 key 对应的 value 返回。 1.2.5 unordered_map 的查询 函数声明功能介绍iterator find(const K key)返回 key 在哈希桶中的位置size_t count(const K key)返回哈希桶中关键码为 key 的键值对的个数 小Tipsunordered_map 中 key 是不能重复的因此 count 函数的返回值最大为1。 1.2.6 unordered_map 的修改操作 函数声明功能介绍insert向容器中插入键值对erase删除容器中的键值对void clear()清空容器中有效元素个数void swap(unordered_map ump)交换两个容器中的元素 1.2.7 unordered_map 的桶操作 函数声明功能介绍size_t bucket_count() const返回哈希桶中桶的总个数size_t bucket_size(size_t n) const返回 n 号桶中有效元素的总个数size_t bucket(const K key)返回元素 key 所在的桶号 三、底层结构 unordered 系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构。 3.1 哈希概念 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为 O ( N ) O(N) O(N)平衡树中为树的高度即 O ( l o g 2 N ) O(log2^N) O(log2N)搜索的效率取决于搜索过程中关键码的比较次数。 理想的搜索方法可以在不经过任何比较一次直接从表中得到要搜索的元素。如果构造一种存储结构通过某种函数hashFunc使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。在结构中 插入元素根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。 搜索元素对元素的关键码进行相同的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜素成功。
该方式即为哈希散列方法哈希方法中使用的转换函数称为哈希散列函数构造出来的结构称为哈希表Hash Table或者散列表 小Tips用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快。但是也会出现问题以上图为例再向集合中插入44计算出来的哈希函数值是4但是下标为4的位置已经存储的有值了。 3.2 哈希冲突 对于两个数据元素的关键字 k_i 和 k_j i ! j有 k_i ! k_j但有Hash(k_i) Hash(k_j)即不同的关键字通过相同的哈希函数计算出相同的哈希值该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 3.3 哈希函数 引起哈希冲突的一个原因可能是哈希函数设计不够合理。设计哈希函数应该遵循以下原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有 m 个地址时其值域必须在 0~m-1 之间。 哈希函数计算出来的地址能均匀分布在整个空间中。 哈希函数应该比较简单。
下面给大家列举一些常见的哈希函数。 3.3.1 直接定值法—-(常用) 取关键字的某个线性函数为散列地址 H a s h ( K e y ) A ∗ K e y B Hash(Key) A*Key B Hash(Key)A∗KeyB 小Tips此方法的优点是简单、均匀。但是需要事先知道关键字的分布情况。适合查找比较小且连续的情况。 3.3.2 除留余数法—-(常用) 设散列表中允许的地址数为 m取一个不大于 m但最接近或者等于 m 的质数 p 作为除数按照哈希函数 H a s h ( K e y ) K e y % p ( p m ) Hash(Key) Key \% p(p m) Hash(Key)Key%p(pm) 3.3.3 平方取中法—-(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址再比如关键字为4321对它的平方就是18671041抽取中间的3位671或710作为哈希地址。平方取中法适合于不知道关键字的分布而位数又不是很大的情况。 3.3.4 折叠法—-(了解 折叠法是将关键字从左到右分割成位数相等的几部分最后一部分位数可以短一些然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。 3.3.5 随机数法—-(了解) 选择一个随机数取关键字的随机函数值为它的哈希地址即 H a s h ( K e y ) r a n d o m ( k e y ) Hash(Key) random(key) Hash(Key)random(key) 小Tips其中 random 为随机数函数。 3.3.6 数学分析法—-(了解) 设有 n 个d 位数每一位可能有 r 种不同的符号在各个位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。例如 假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前7位都是 相同的那么我们可以选择后面的四位作为散列地址如果这样的抽取工作还容易出现 冲突还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成123446)等方法。 小Tips数学分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。 注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突。 3.4 哈希冲突解决 解决哈希冲突的两种常见方法是闭散列和开散列。 3.4.1 闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被填满说明在哈希函数表中必然还有空位置那么可以把 Key 对应的元素存放到冲突位置中的下一个空位置中去。那如何寻找下一个空位置呢 3.4.1.1 线性探测 从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入 通过哈希函数获取待插入元素在哈希表中的位置。 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。 查找 通过哈希函数获取待查找元素在哈希表中的位置。 看该位置的值是否是我们要查找的值如果不是从当前位置依次往后进行比较找到就结束如果遇到空还没有找到说明当前待查找的元素不在哈希表中。
小Tips这里简介反映出哈希表中的元素不能太满了如果太满那么它的查找效率有可能就变成了 O ( N ) O(N) O(N)。 删除采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其它元素的搜索。比如上图中删除元素24如果直接删掉54查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。 扩容散列表的载荷因子定义为 α 填入表中的元素个数 / 散列表的长度 α 填入表中的元素个数 / 散列表的长度 α填入表中的元素个数/散列表的长度 α α α 是散列表装满成都的标志因子。由于表长是定值 α α α 与“填入表中的元素个数”成正比所以 α α α 越大表明填入表中的元素越多产生冲突的可能性就越大但是空间利用率越高反之 α α α 越小表明填入表中的元素越少产生冲突的可能性就越小但是空间浪费会比较多。实际上散列表的平均查找长度是载荷因子 α α α 的函数只是不同处理冲突的方式有不同的函数。 对于闭散列开放定址法载荷因子是特别重要的因素应严格限制在 0.7 − 0.8 0.7-0.8 0.7−0.8以下。超过 0.8 0.8 0.8查表时的 CPU 缓存不命中按照指数曲线上升。因此一些曹勇开放定址法的 hash 库如 Java 的系统库限制了载荷因子为 0.75超过此值将 resize 散列表。 小Tips扩容后元素的映射关系会发生变化所以我们需要重新建立映射即重新计算元素对应的存储位置。原来冲突的现在不一定冲突了原来不冲突的现在可能冲突了因此扩容后需要对原来表中的元素重新走一遍插入逻辑。 3.4.1.2 闭散列开放定址法模拟实现 enum STATE {EXIST,EMPTY,DELETE };//存储元素的结点 templateclass K, class V struct HashData {pairK, V _kv;STATE _state EMPTY; };//哈希表 templateclass K, class V class HashTable { public:HashTable(){_table.resize(10);}bool Insert(const pairK, V kv){//检查负载因子扩容/if ((double)_n / _table.size() 0.7){}/if (_n * 10 / _table.size() 7){size_t newsize _table.size() * 2;//重新建立映射关系//vectorHashDataK, V tmp;//tmp.resize(newsize);//for (const auto e : _table)//{// if (e._state EXIST)// {// size_t hashi e._kv.first % tmp.size();// while (tmp[hashi]._state EXIST)// {// hashi;// //当hashi size 的时候要让它从 0 开始继续找。// /if (hashi _table.size())// {// hashi 0;// }/// hashi % _table.size();// }// tmp[hashi] e;// }// //}//std::swap(tmp, _table);HashTableK, V newHT;newHT._table.resize(newsize);//遍历旧表的数据插入到新表即可for (size_t i 0; i _table.size(); i){if (_table[i]._state EXIST){newHT.Insert(_table[i]._kv);}}_table.swap(newHT._table);}//线性探测size_t hashi kv.first % _table.size();//注意这里//如果下标为hashi的地方没有存元素那么就可以直接在hashi进行插入//如果下标为hashi的地方存的有元素就需要进行线性探测//EMPTY、DELETE都可存储元素while (_table[hashi]._state EXIST){hashi;//当hashi size 的时候要让它从 0 开始继续找。/if (hashi _table.size()){hashi 0;}/hashi % _table.size();}//注意方括号访问底层会去断言下标必须小于size所以上面模的是size。_table[hashi]._kv kv;_table[hashi]._state EXIST;_n;return true;}HashDataconst K, V* Find(const K key){//线性探测size_t hashi key % _table.size();//注意这里//如果下标为hashi的地方没有存元素那么就可以直接在hashi进行插入//如果下标为hashi的地方存的有元素就需要进行线性探测//EMPTY、DELETE都可存储元素while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._kv.first key){return (HashDataconst K, V)_table[hashi];//这里会涉及类型转化有的编译器可能不支持所以这里最好自己强转一下}hashi;hashi % _table.size();}return nullptr;}bool Erase(const K key){HashDataconst K, V ret Find(key);if (ret){ret-_state DELETE;–_n;return true;}return false;} private:vectorHashDataK, V _table;size_t _n 0;//因为数据是分散存储的所以不能用vector中的size去计算哈希表中元素的数量这个_n存储的就是哈希表中有效数据的个数 };小Tips线性探测的优点是实现起来非常简单。缺点是一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。可以利用下面的二次探测来解决该问题。 3.4.1.3 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 H i H_i Hi​ ( H 0 H_0 H0​ i 2 i^2 i2 )% m 或者 H i H_i Hi​ ( H 0 H_0 H0​ - i 2 i^2 i2 )% m。其中i 1,2,3… H 0 H_0 H0​是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置m是表的大小。 研究表明当表的长度为质数且表装载因子 α α α 不超过 0.5 时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表满的情况但在插入时必须确保表的装载因子 α α α 不超过 0.5如果超出必须考虑增容。因此闭散列最大的缺陷局势空间利用率比较低这也是哈希的缺陷。 3.4.2 开散列 开散列又叫拉链法首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 小Tips从上图中可以看出开散列中每个桶中放的都是发生哈希冲突的元素。 3.4.2.1 开散列模拟实现 templateclass K, class V struct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv pairK, V()):_kv(kv),_next(nullptr){}};templateclass K, class V, class HashFunc DefaultHasFuncKclass HashTable{typedef HashNodeK, V Node;private:void swap(HashTableK, V, HashFunc hbt){std::swap(hbt._table, this-_table);std::swap(hbt._n, this-_n);}public:HashTable(size_t size 10){_table.resize(size, nullptr);}//拷贝构造HashTable(const HashTableK, V, HashFunc htb){_table.resize(htb._table.size());for (size_t i 0; i htb._table.size(); i){Node* cur htb._table[i];while (cur){Insert(cur-_kv);cur cur-_next;}}/* HashTableK, V, HashFunc tmp;tmp._table htb._table;//这里现代写法行不通因为_table里面存的是指针属于内置类型进行的是浅拷贝。tmp._n htb._n;swap(tmp);*/}bool Insert(const pairK, V kv){//HashFunc hf;//先检查哈希桶中是否有这个元素有就不能插入if (Find(kv.first)){return false;}//不扩容不断插入某些桶会越来越长效率得不到保证//因此还是需要进行适当的扩容//这里一般把负载因子控制在1//这样在理想状态下平均每个桶一个数据if (_n _table.size()){//扩容 方法一会去创建新节点然后还要把旧结点释放效率低下/*HashTableK, V, HashFunc newTable(_table.size() * 2);for (size_t i 0; i _table.size(); i){if (_table[i] ! nullptr){Node* cur _table[i];while (cur){newTable.Insert(cur-_kv);cur cur-_next;}}}_table.swap(newTable._table);///扩容 方法二vectorNode newtable;newtable.resize(_table.size() * 2, nullptr);for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;size_t hashi hf(cur-_kv.first) % newtable.size();cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newtable);}size_t hashi hf(kv.first) % _table.size();//检查当前桶里面是否已经有该元素Node* cur _table[hashi];while (cur){if (cur-_kv.first kv.first){return false;}cur cur-_next;}//到这里说明当前桶里没有该元素可以插入Node* newnode new Node(kv);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}//打印哈希桶void Print(){for (size_t i 0; i _table.size(); i){printf(Hash[%d]:, i);Node* cur _table[i];while (cur){cout cur-_kv.first : cur-_kv.second —;cur cur-_next;}cout nullptr endl;}}//查找Node* Find(const K key){size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}//删除bool erase(const K key){size_t hashi hf(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;cur nullptr;–_n;return true;}prev cur;cur cur-_next;}return false;}~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}private:vectorNode* _table;//指针数组//这里的_table属于自定义类型如果我们不写析构函数编译器会去调用vector自己的析构函数//对于vector的析构函数来说Node* 是一个指针属于内置类型//因此vector的析构函数不会对 Node* 做任何处理//因此这里我们需要自己写析构函数去释放哈希桶中的结点size_t _n 0;//记录存储的有效数据个数HashFunc hf;};四、模拟实现 unordered_set 和 unordered_map 4.1 哈希表的改造 这里我们使用开散列的方法来实现 unordered_set 和 unordered_map。 4.1.1 模板参数列表的改造 //哈希表 templateclass K, class T, class KeyOfT, class HashFunc DefaultHasFuncK//K的作用是为了方便查找和删除 class HashTable小Tips K关键码类型。 T不同容器 T 的类型不同如果是 unordered_mapT 代表一个键值对如果是 unordered_setV 为 K。 KeyOfT因为 T 的类型不同通过 value 取 key 的方式就不同详细代码参考下面 unordered_set/map 的实现。 HashFunc哈希函数仿函数对象类型哈希函数使用除留余数法需要将 key 转换为整形数字才能取模。
4.1.2 增加迭代器操作 //HashTable.h //哈希桶的迭代器templateclass K, class T, class Ptr, class Ref, class KeyOfT, class HashFuncstruct HTIterator{typedef HashNodeT Node;typedef HTIteratorK, T, Ptr, Ref, KeyOfT, HashFunc Self;typedef HashTableK, T, KeyOfT, HashFunc Ht;typedef HTIteratorK, T, T, T, KeyOfT, HashFunc iterator;Node _node;const Ht* _pht;HTIterator(Node* node nullptr, const Ht* pht nullptr):_node(node),_pht(pht){}HTIterator(const iterator it)//如果是普通迭代器这里就是拷贝构造函数:_node(it._node) //如果是 const 迭代器这里就是用一个普通迭代器来构造一个 const 迭代器。, _pht(it._pht){}Self operator(){if (_node-_next){_node _node-_next;}else{//如果_node-_next nullptr//说明要到下一个桶去因此迭代器类里面需要一个哈希表的指针指向当前迭代器维护的哈希表//这样才能找到下一个桶//先找到我当前在那个桶KeyOfT kot;HashFunc hf;size_t hashi hf(kot(_node-_data)) % _pht-_table.size();//从下一个位置开始查找下一个不为空的桶hashi;while (hashi _pht-_table.size()){if (_pht-_table[hashi]){_node _pht-_table[hashi];return *this;}else{hashi;}}_node nullptr;}return this;}bool operator ! (const Self s) const{return _node ! s._node;}Ref operator() const{return _node-_data;}Ptr operator-() const{return (_node-_data);}};小Tips因为哈希表本质上是由一个个哈希桶组成迭代器走完当前桶需要跳到下一个桶迭代器要能指向下一个哈希桶最简单的做法就是在迭代器里面存一份哈希表。实际代码中我们在迭代器中增加了一个哈希表类型的指针指向当前迭代器维护的哈希表又因为该指针会去访问哈希表里面的成员变量数组所以该迭代器类必须是哈希表的友元类关于友元类的具体声明参考下面修改后的哈希表。这里还有一个问题迭代器里面使用了哈希表类型哈希表里面又实用的迭代器类型这里就会涉及到谁先谁后的问题我这里的解决方法是将迭代器类定义在哈希表的前面然后在迭代器的前面对哈希表的类做一个前置声明。其次因为哈希桶在底层是单链表结构所以哈希桶的迭代器不需要 - - 操作。 4.1.3 修改后的哈希表 //HashTable.h //哈希表templateclass K, class T, class KeyOfT, class HashFunc DefaultHasFuncK//K的作用是为了方便查找和删除class HashTable{//模板的友元templateclass K, class T, class Ptr, class Ref, class KeyOfT, class HashFuncfriend struct HTIterator;typedef HashNodeT Node;private:void swap(HashTableK, T, HashFunc hbt){std::swap(hbt._table, this-_table);std::swap(hbt._n, this-_n);}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){if (_table[i]){return iterator(_table[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{//找第一个桶for (size_t i 0; i _table.size(); i){if (_table[i]){return const_iterator(_table[i], this);}}return const_iterator(nullptr, this);}const_iterator end() const{return const_iterator(nullptr, this);}HashTable(size_t size 10){_table.resize(size, nullptr);}//拷贝构造HashTable(const HashTableK, T, HashFunc htb){_table.resize(htb._table.size());for (size_t i 0; i htb._table.size(); i){Node* cur htb._table[i];while (cur){Insert(cur-_data);cur cur-_next;}}/* HashTableK, T, HashFunc tmp;tmp._table htb._table;//这里现代写法行不通因为_table里面存的是指针属于内置类型进行的是浅拷贝。tmp._n htb._n;swap(tmp);/}pairiterator, bool Insert(const T data){HashFunc hf;KeyOfT kt;//HashFunc hf;//先检查哈希桶中是否有这个元素有就不能插入if (Find(kt(data)) ! end()){return make_pair(Find(kt(data)), false);}//扩容if (_n _table.size()){vectorNode newtable;newtable.resize(_table.size() * 2, nullptr);for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;size_t hashi hf(kt(cur-_data)) % newtable.size();cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newtable);}size_t hashi hf(kt(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)const{HashFunc hf;KeyOfT kt;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (kt(cur-_data) key){return iterator(cur, this);}cur cur-_next;}return iterator(nullptr, this);}//删除bool erase(const K key){HashFunc hf;KeyOfT kt;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (kt(cur-_data) key){if (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;cur nullptr;–_n;return true;}prev cur;cur cur-_next;}return false;}~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}private:vectorNode* _table;//指针数组//这里的_table属于自定义类型如果我们不写析构函数编译器会去调用vector自己的析构函数//对于vector的析构函数来说Node* 是一个指针属于内置类型//因此vector的析构函数不会对 Node* 做任何处理//因此这里我们需要自己写析构函数去释放哈希桶中的结点size_t _n 0;//记录存储的有效数据个数};小Tips哈希表的修改主要体现在增加通过 key 获取 value 的操作。 4.2 unordered_set 模拟实现 //unorderedset.h #include HashTable.htemplateclass K, class HashFunc DefaultHasFuncK class unordered_set { private:struct SetKeyOfT{const K operator()(const K key){return key;}}; public:typedef typename HashTableK, K, SetKeyOfT, HashFunc::const_iterator iterator;typedef typename HashTableK, K, SetKeyOfT, HashFunc::const_iterator const_iterator;iterator begin() const{return _ht.begin();}iterator end() const{return _ht.end();}pairiterator, bool insert(const K key){/pairtypename HashTableK, K, SetKeyOfT, HashFunc::iterator, bool ret _ht.Insert(key);return make_pair(iterator(ret.first._node, ret.first._pht), ret.second);/return _ht.Insert(key);//这种写法如果编译器检查的严格可能过不了//上面两种插入方法都可以这一块是精华好好品味}K operator{pairtypename HashTableK, K, SetKeyOfT, HashFunc::iterator, bool ret _ht.Insert(key);return *(ret.first);}private:HashTableK, K, SetKeyOfT, HashFunc _ht; };小Tipsunordered_set 是一种 key 结构所以它的普通迭代器和 const 迭代器都是不允许被修改的。因此 unordered_set 中的普通迭代器本质上还是 HashTable 中的 const 迭代器。此时就会出现一个问题插入调用的是 HashTable 中的 Insert其返回值是一个 pair其中 first 是一个普通迭代器而在 unordered_set 这一层insert 的返回值也是一个 pair它的 first 看起来是一个普通迭代器但本质上是用 HashTable 中的 const 迭代器进行封装的因此这里涉及到从普通迭代器转换成 const 迭代器随然普通迭代器和 const 迭代器共用同一个类模板但是它们的模板参数不同所以普通迭代器和 const 迭代器本质上属于两种不同类型。因此要将一个普通迭代器转化成 const 迭代器本质上涉及类型转换。要用一个 A 类型的对象去创建一个 B 类型的对象 可以在 A 类里面增加一个构造函数该构造函数的参数是 B 类型。因此这里我们需要在迭代器类里面增加一个用普通迭代器构造 const 迭代器的构造函数。除了这种方法外上面我还提供了一种方法即先用 HashTable 中的普通迭代器创建一个 pair 对象 ret 接收 HashTable 中 Insert 的返回值然后再去取出 pair 里面迭代器中的成员变量用取出来的成员变量去构造一个 const 迭代器然后再用这个 const 迭代器去构建一个 pair最后返回这个 pair。这种方法的前提是迭代器类中的成员变量是 public否则就不能再迭代器类的外面拿到其成员变量。 4.3 unordered_map 模拟实现 templateclass K, class V, class HashFunc DefaultHasFuncK class unordered_map { private:struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}}; public:typedef typename HashTableK, pairconst K, V, MapKeyOfT, HashFunc::iterator iterator;typedef typename HashTableK, pairconst K, V, MapKeyOfT, HashFunc::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);}V operator{pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;} private:HashTableK, pairconst K, V, MapKeyOfT, HashFunc _ht; };小Tips对 unordered_map 结构来说无论是普通迭代器还是 const 迭代器它的 key 永远都不能被修改。这里的解决方案是在 unordered_map 中用 paircons K, V 去实例化出一个哈希表的模板此时哈希表的节点中存的就是 pairconst K, V _data;此时无论是普通迭代器还是 const 迭代器去解引用该结点返回的 _data它里面的 key 是 const K 类型是不支持修改的这样以来问题就解决了。由于这里我们是用 paircons K, V 去实例化的模板所以 unordered_map 中的哈希表本质上存的就是 paircons K, V但是在用户层我们插入的是 pairK, V这是两种不同的类型和上面的普通迭代去创建 const 迭代器一样这里还是需要通过构造函数来解决但是这里不需要我们自己来解决因为 pair 是库中的内容库中已经帮我们实现好啦所以这里我们无需做任何处理。这里本质上会去调用下面这个构造函数。 五、结语 今天的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下春人的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是春人前进的动力