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

用哈希表封装myunordered_map/_set--C++

文章目录

  • 一、源码及框架分析
  • 二、模拟实现unordered_map和unordered_set
    • 1、实现出复用哈希表的框架,并支持insert
    • 2、支持iterator的实现
    • 3、map支持[]
    • 4、xz::unordered_map和xz::unordered_set代码实现

一、源码及框架分析

SGI-STL30版本源代码中没有unordered_map和unordered_set,SGI-STL30版本是C++11之前的STL版本,这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表,只容器的名字是hash_map和hash_set,他是作为非标准的容器出现的,非标准是指非C++标准规定必须实现的,源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中 hash_map和hash_set的实现结构框架核心部分截取出来如下:

// stl_hash_set
template <class Value, class HashFcn = hash<Value>,class EqualKey = equal_to<Value>,class Alloc = alloc>
class hash_set
{ 
private:typedef hashtable<Value, Value, HashFcn, identity<Value>,EqualKey, Alloc> ht;ht rep;
public:typedef typename ht::key_type key_type;typedef typename ht::value_type value_type;typedef typename ht::hasher hasher;typedef typename ht::key_equal key_equal;typedef typename ht::const_iterator iterator;typedef typename ht::const_iterator const_iterator;hasher hash_funct() const { return rep.hash_funct(); }key_equal key_eq() const { return rep.key_eq(); }
};// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>,class EqualKey = equal_to<Key>,class Alloc = alloc>
class hash_map
{ 
private:typedef hashtable<pair<const Key, T>, Key, HashFcn,select1st<pair<const Key, T> >, EqualKey, Alloc> ht;ht rep;
public:typedef typename ht::key_type key_type;typedef T data_type;typedef T mapped_type;typedef typename ht::value_type value_type;typedef typename ht::hasher hasher;typedef typename ht::key_equal key_equal;typedef typename ht::iterator iterator;typedef typename ht::const_iterator const_iterator;
};// stl_hashtable.h
template <class Value, class Key, class HashFcn,class ExtractKey, class EqualKey,class Alloc>
class hashtable 
{
public:typedef Key key_type;typedef Value value_type;typedef HashFcn hasher;typedef EqualKey key_equal;
private:hasher hash;key_equal equals;ExtractKey get_key;typedef __hashtable_node<Value> node;vector<node*,Alloc> buckets;size_type num_elements;
public:typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,Alloc> iterator;pair<iterator, bool> insert_unique(const value_type& obj);const_iterator find(const key_type& key) const;
};
template <class Value>
struct __hashtable_node
{__hashtable_node* next;Value val;
};
  1. 这里我们就不再画图分析了,通过源码可以看到,结构上hash_map和hash_set跟map和set的完全类似,复用同一个hashtable实现key和key/value结构,hash_set传给hash_table的是两个key,hash_map传给hash_table的是pair<const key, value>
  2. 需要注意的是源码里面跟map/set源码类似,命名风格比较乱,这里比map和set还乱,hash_set模板参数居然用的Value命名,hash_map用的是Key和T命名。下面我们模拟一份自己的出来,就按自己的风格走了。

二、模拟实现unordered_map和unordered_set

1、实现出复用哈希表的框架,并支持insert

  1. 参考源码框架,unordered_map和unordered_set复用之前我们实现的哈希表。
  2. 我们这里相比源码调整一下,key参数就用K,value参数就用V,哈希表中的数据类型,我们使用T。
  3. 其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂一点,但是大框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K,还是pair<K, V>,那么insert内部进行插入时要用K对象转换成整形取模和K比较相等,因为pair的value不参与计算取模,且默认支持的是key和value一起比较相等,我们需要时的任何时候只需要比较K对象,所以我们在unordered_map和unordered_set层分别实现一个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT,然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象,再转换成整形取模和K比较相等,具体细节参考如下代码实现。
//MyUnorderedSet.h
namespace xz
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _ht.Insert(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};
}
// MyUnorderedMap.h
namespace xz
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool insert(const pair<K, V>& kv){return _ht.Insert(key);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};
}
// HashTable.h
emplate<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
namespace hash_bucket
{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};// 实现步骤:// 1、实现哈希表// 2、封装unordered_map和unordered_set的框架 解决KeyOfT// 3、iterator// 4、const_iterator// 5、key不⽀持修改的问题// 6、operator[]template<class K, class T, class KeyOfT, class Hash>class HashTable{typedef HashNode<T> Node;inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {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};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}public:HashTable(){_tables.resize(__stl_next_prime(_tables.size()), nullptr);} ~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;}}bool Insert(const T& data){KeyOfT kot;if (Find(kot(data)))return false;Hash hs;size_t hashi = hs(kot(data)) % _tables.size();// 负载因⼦==1扩容if (_n == _tables.size()){vector<Node*> newtables(__stl_next_prime(_tables.size()),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);} // 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 表中存储数据个数};
}

2、支持iterator的实现

iterator核心源代码

template <class Value, class Key, class HashFcn,class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator 
{typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;typedef __hashtable_iterator<Value, Key, HashFcn,ExtractKey, EqualKey, Alloc>iterator;typedef __hashtable_const_iterator<Value, Key, HashFcn,ExtractKey, EqualKey, Alloc>const_iterator;typedef __hashtable_node<Value> node;typedef forward_iterator_tag iterator_category;typedef Value value_type;node* cur;hashtable* ht;__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}__hashtable_iterator() {}reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */iterator& operator++();iterator operator++(int);bool operator==(const iterator& it) const { return cur == it.cur; }bool operator!=(const iterator& it) const { return cur != it.cur; }
};template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{const node* old = cur;cur = cur->next;if (!cur) {size_type bucket = ht->bkt_num(old->val);while (!cur && ++bucket < ht->buckets.size())cur = ht->buckets[bucket];} return *this;
}

iterator实现思路分析

  1. iterator实现的大框架跟list的iterator思路是一致的,用一个类型封装结点的指针,再通过重载运算符实现,迭代器像指针一样访问的行为,要注意的是哈希表的迭代器是单向迭代器。
  2. 这里的难点是operator++的实现。iterator中有一个指向结点的指针,如果当前桶下面还有结点,则结点的指针指向下一个结点即可。如果当前桶走完了,则需要想办法计算找到下一个桶。这里的难点是反而是结构设计的问题,参考上面的源码,我们可以看到iterator中除了有结点的指针,还有哈希表对象的指针,这样当前桶走完了,要计算下一个桶就相对容易多了,用key值计算出当前桶位置,依次往后找下一个不为空的桶即可。
  3. begin()返回第一个桶中第一个节点指针构造的迭代器,这里end()返回迭代器可以用空表示。
  4. unordered_set的iterator也不支持修改,我们把unordered_set的第二个模板参数改成const K即可, HashTable<K, const K, SetKeyOfT, Hash> _ht;
  5. unordered_map的iterator不支持修改key但是可以修改value,我们把unordered_map的第二个模板参数pair的第一个参数改成const K即可, HashTable<K, pair<const K, V>,MapKeyOfT, Hash> _ht;
  6. 支持完整的迭代器还有很多细节需要修改,具体参考下面的代码。

在这里插入图片描述

3、map支持[]

  1. unordered_map要支持[]主要需要修改insert返回值支持,修改HashTable中的insert返回值为pair<Iterator, bool> Insert(const T& data)
  2. 有了insert支持[]实现就很简单了,具体参考下面4的代码实现
V& operator[](const K& key)
{pair<iterator, bool> ret = insert({ key,V() });return ret.first->second;
}

4、xz::unordered_map和xz::unordered_set代码实现

xz::unordered_map和xz::unordered_set代码实现


http://www.mrgr.cn/news/75142.html

相关文章:

  • 代码修改材质参数
  • Python 的 Pygame 库,编写简单的 Flappy Bird 游戏
  • 【GPT使用技巧】用AI出一门课
  • ctfshow-web入门-SSTI(web361-web368)上
  • Webpack 1.13.2 执行 shell 命令解决 打印时没有背景色和文字颜色的问题
  • 图形 2.7 LDR与HDR
  • 《Python网络安全项目实战》项目5 编写网站扫描程序
  • 20241113下载安装虚拟桌面工具VYSOR并连接中科创达的高通CM6125开发板
  • 深入理解ECDSA:椭圆曲线数字签名算法的原理与应用
  • 算法基础 -- 红黑树原理与插入伪代码
  • SpringCloud框架学习(第三部分:Resilience4j 与 Micrometer)
  • 关于我重生到21世纪学C语言这件事——指针详解(1)
  • 【计算机网络】Socket编程接口
  • 【MinIO】Python 运用 MinIO 实现简易文件系统
  • WLAN消失或者已连接但是访问不了互联网
  • SpringSecurity+jwt+captcha登录认证授权总结
  • 程序员的数学之进制与零
  • Flink1.19编译并Standalone模式本地运行
  • 保姆级教程,免费短链平台
  • cache缺失和关联度
  • sqlmap使用教程
  • Python 异常处理试卷
  • 【HarmonyOS】鸿蒙系统在租房项目中的项目实战(一)
  • 大语言模型LLM综述
  • GRU(门控循环单元)详解
  • Siggraph Asia 2024 | Adobe发布MagicClay:可通过文字引导去对3D模型中的特定部分进行雕刻