C++ STL 库：unordered_map 与 unordered_set 底层剖析

🚩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;
}

这里的转化尤为复杂，一定要看之前文章的详细解析。