C++效率掌握之STL库：unordered_map && unordered_set底层剖析
文章目录
- 1.unordered_map、unordered_set的基本结构
- 2.普通迭代器
- 3.const迭代器
- 4.insert返回值 operator[]
- 希望读者们多多三连支持
- 小编会继续更新
- 你们的鼓励就是我前进的动力！
看了前面的底层封装后，其实封装的过程及方法都大差不差，unordered_map && unordered_set 也是如此，所以本篇就简单提及一些细节，具体最详细的一些部分可以去看前面的文章
传送门：C++效率掌握之STL库：list底层剖析及迭代器万字详解
传送门：C++效率掌握之STL库：map && set底层剖析及迭代器万字详解
1.unordered_map、unordered_set的基本结构
🚩unordered_set：
template<classK,classV>classunordered_set{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:typedeftypenamehash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;typedeftypenamehash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator; const_iterator begin()const{return _ht.begin();} const_iterator end()const{return _ht.end();} pair<const_iterator,bool>insert(const K& key){ pair<typenamehash_bucket::HashTable<K, K, SetKeyOfT>::iterator,bool> ret = _ht.Insert(key);returnpair<const_iterator,bool>(ret.first, ret.second);}private: hash_bucket::HashTable<K, K, SetKeyOfT> _ht;};🚩unordered_map：
template<classK,classV>classunordered_map{structMapKeyOfT{const K&operator()(const pair<const K, V>& kv){return kv.first;}};public:typedeftypenamehash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedeftypenamehash_bucket::HashTable<K, pair<const 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();} pair<iterator,bool>insert(const pair<K, V>& kv){return _ht.Insert(kv);} V&operator[](const K& key){ pair<iterator,bool> ret = _ht.Insert(make_pair(key,V()));return ret.first->second;}private: hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;};unordered_set 虽然事 k-k 类型，unordered_map 是 k-v 类型，但是实际上这两个类共用一个哈希表，准确来说是共用同一个模板类型，unordered_set 是 <K，K>，unordered_map 是 <K，pair<K，V>>
2.普通迭代器
template<classK,classT,classPtr,classRef,classKeyOfT,classHashFunc>structHTIterator{typedef HashNode<T> Node;typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator; Node* _node;const HashTable<K, T, KeyOfT, HashFunc>* _pht;/*HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht) :_node(node) ,_pht(pht) {}*/HTIterator(Node* node,const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}// 普通迭代器时，他是拷贝构造// const迭代器时，他是构造HTIterator(const Iterator& it):_node(it._node),_pht(it._pht){} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;} Self&operator++(){if(_node->_next){// 当前桶还没完 _node = _node->_next;}else{ 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;}booloperator!=(const Self& s){return _node != s._node;}booloperator==(const Self& s){return _node == s._node;}};typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator 和构造函数是为 Insert 操作准备的，因为涉及到普通迭代器创建 const 迭代器
🔥值得注意的是： 有人说不是可以通过权限转化吗？但是权限转化是只有涉及引用和指针的类型时才会生效，而这里是模板参数之间的转化
3.const迭代器
unordered_set 本身无论是 const 迭代器还是普通迭代器都会被 typedef 为 const_iterator
对于 unordered_map 来说，key 是不允许改变的，value 是可以改变的，但是如果像 set 那样写的话 key 和 value 都不能修改了，所以直接在 pair 的 key 加 const ，控制 value 即可
4.insert返回值 operator[]
🚩unordered_set：
pair<const_iterator,bool>insert(const K& key){//return _ht.Insert(key); pair<typenamehash_bucket::HashTable<K, K, SetKeyOfT>::iterator,bool> ret = _ht.Insert(key);returnpair<const_iterator,bool>(ret.first, ret.second);}🚩unordered_map：
pair<iterator,bool>insert(const pair<K, V>& kv){return _ht.Insert(kv);} V&operator[](const K& key){ pair<iterator,bool> ret = _ht.Insert(make_pair(key,V()));return ret.first->second;}这里的转化尤为复杂，一定要看之前文章的详细解析
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
