建设网站的目的和意义,帮人做网站 怎么收费,wordpress创意博客主题,热点新闻最新消息【C笔记】unordered_map/set的哈希封装 #x1f525;个人主页#xff1a;大白的编程日记
#x1f525;专栏#xff1a;C笔记 文章目录 【C笔记】unordered_map/set的哈希封装前言一. 源码及框架分析二.迭代器三.operator[]四.使用哈希表封装unordered_map/set后言 前言 哈…【C笔记】unordered_map/set的哈希封装 个人主页大白的编程日记
专栏C笔记 文章目录 【C笔记】unordered_map/set的哈希封装前言一. 源码及框架分析二.迭代器三.operator[]四.使用哈希表封装unordered_map/set后言 前言 哈喽各位小伙伴大家好!上期我们讲了哈希表的底层实现。今天我们来讲一下unordered_map/set的哈希封装。话不多说我们进入正题向大厂冲锋 一. 源码及框架分析 SGI-STL30版本源代码中没有unordered_map和unordered_setSGI-STL30版本是C11之前的STL版本这两个容器是C11之后才更新的。但是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 hashValue,class EqualKey equal_toValue,class Alloc alloc
class hash_set
{
private:typedef hashtableValue, Value, HashFcn, identityValue,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 hashKey,class EqualKey equal_toKey,class Alloc alloc
class hash_map
{
private:typedef hashtablepairconst Key, T, Key, HashFcn,select1stpairconst 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_nodeValue node;vectornode*, Alloc buckets;size_type num_elements;
public:typedef __hashtable_iteratorValue, Key, HashFcn, ExtractKey, EqualKey,Alloc iterator;pairiterator, 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;
};框架分析 这里我们就不再画图分析了通过源码可以看到结构上hash_map和hash_set跟map和set的完全类似复用同一个hashtable实现key和key/value结构通过一个参数T来封装map和set,hash_set传给hash_table的是keyhash_map传给hash_table的是pairconst key, value。通过仿函数取出T中的key。同时哈希表还要多传一个哈希函数的仿函数。
二.迭代器
iterator实现的大框架跟list的iterator思路是一致的用⼀个类型封装结点的指针再通过重载运算符实现迭代器像指针⼀样访问的行为要注意的是哈希表的迭代器是单向迭代器。这里的难点是operator的实现。iterator中有⼀个指向结点的指针如果当前桶下面还有结点则结点的指针指向下⼀个结点即可。如果当前桶走完了则需要想办法计算找到下⼀个桶。这里的难点是反而是结构设计的问题参考上面的源码我们可以看到iterator中除了有结点的指针还有哈希表对象的指针这样当前桶走完了要计算下一个桶就相对容易多了用key值计算出当前桶位置依次往后找下⼀个不为空的桶即可。begin()返回第⼀个不为空的桶中第⼀个节点指针构造的迭代器这里end()返回迭代器可以用空表示。unordered_set的iterator也不支持修改我们把unordered_set的第⼆个模板参数改成const K即 可 HashTableK, const K, SetKeyOfT, Hash _ht;unordered_map的iterator不支持修改key但是可以修改value我们把unordered_map的第二个模板参数pair的第⼀个参数改成const K即可 HashTableK, pairconst K, V,MapKeyOfT, Hash _ht;
三.operator[]
unoredered_map实现operator[]主要是通过insert支持。 通过insert返回的pair中的迭代器再返回迭代器中数据即可
v operator[](const k key)
{pairiterator, bool ret insert({ key,v()});return ret.first._node-_data.second;
}四.使用哈希表封装unordered_map/set
其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂⼀点但是 大框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K还是pairK, V 那么insert内部进行插入时要用K对象转换成整形取模和K比较相等因为pair的value不参与计算取模且默认支持的是key和value⼀起比较相等我们需要时的任何时候只需要比较K对象所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象再转换成整形取模和K比较相等具体细节参考如下代码实现。 templateclass Tstruct HashData{HashDataT* _next;T _data;HashData(const T key):_next(nullptr),_data(key){}};templateclass k, class T, class KeyofT, class HashFunclass HashTable;//前置声明,解决相互依赖templateclass k, class T, class Ref, class Ptr, class KeyofT, class HashFunstruct HashIterator{using node HashDataT;using self HashIteratork, T, Ref, Ptr, KeyofT, HashFun;using ht HashTablek, T, KeyofT, HashFun;const ht* _ht;node* _node;HashIterator(const ht* const HT,node* node):_ht(HT), _node(node){}Ref operator*(){return _node-_data;}Ptr operator(){return _node-_data;}bool operator(const self tmp) const{return _node tmp._node;}bool operator!(const self tmp) const{return _node ! tmp._node;}self operator(){KeyofT kot;HashFun hash;if (_node-_next){_node _node-_next;}else{size_t hash0 hash(kot(_node-_data)) % _ht-_table.size();hash0;while (hash0_ht-_table.size()){if (_ht-_table[hash0]){break;}else{hash0;}}if (hash0 _ht-_table.size()){_node nullptr;}else{_node _ht-_table[hash0];}}return *this;}};templateclass k, class T, class KeyofT, class HashFunclass HashTable{templateclass k, class T, class Ref, class Ptr, class KeyofT, class HashFunfriend struct HashIterator;//友元声明public:HashTable():_table(__stl_next_prime(0)), _n(0){}using node HashDataT;using Iterator HashIteratork, T, T, T*, KeyofT, HashFun;using Const_IteratorHashIteratork, T, const T, const T*, KeyofT, HashFun;Iterator End(){return Iterator(this, nullptr);}Iterator Begin(){for (int i 0; i _table.size(); i){if (_table[i]){return Iterator(this, _table[i]);}}return End();}Const_Iterator End() const{return Const_Iterator(this, nullptr);}Const_Iterator Begin() const{for (int i 0; i _table.size(); i){if (_table[i]){return Const_Iterator(this, _table[i]);}}return End();}pairIterator,bool Insert(const T kv){HashFun hash;KeyofT kot;Iterator it Find(kot(kv));if (it!End()){return { it,false };}if (_n * 10 / _table.size() 7){vectornode* newtable;newtable.resize(__stl_next_prime(newtable.size() 1));for (auto x : _table){node* cur x;x nullptr;while (cur){size_t hash0 hash(kot(cur-_data)) % newtable.size();node* next cur-_next;cur-_nextnewtable[hash0];newtable[hash0] cur;cur next;}}_table.swap(newtable);}size_t hash0 hash(kot(kv)) % _table.size();node* cur new node(kv);cur-_next _table[hash0];_table[hash0] cur;_n;return { Iterator(this,cur),true};}Iterator Find(const k key){HashFun hash;KeyofT kot;size_t hash0 hash(key) % _table.size();node* cur _table[hash0];while (cur){if (kot(cur-_data) key){return Iterator(this, cur);}cur cur-_next;}return End();}bool Erase(const k key){HashFun hash;KeyofT kot;size_t hash0 hash(key) % _table.size();node* cur _table[hash0];node* pre nullptr;while (cur){if (kot(cur-_data) key){if (cur _table[hash0]){_table[hash0] cur-_next;}else{pre-_next cur-_next;}return true;}else{pre cur;cur cur-_next;}}return false;}private:vectornode* _table;size_t _n;}; 后言 这就是unordered_map/set的哈希封装。大家自己好好消化今天就分享到这感谢各位的耐心垂阅咱们下期见拜拜~
