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<class K, class V>
class unordered_set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;typedef typename hash_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<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);return pair<const_iterator, bool>(ret.first, ret.second);}
private:hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};

🚩unordered_map：

template<class K, class V>
class unordered_map
{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};
public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename hash_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<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{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;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(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<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);return pair<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;
}