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

可以看到，两者内部都持有一个 _ht 成员变量，通过不同的 KeyOfT 策略函数来提取键信息，从而复用底层的哈希表逻辑。

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;
    // Iterator 用于 Insert 操作，涉及普通迭代器创建 const 迭代器
    typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
    
    Node* _node;
    const HashTable<K, T, KeyOfT, HashFunc>* _pht;

    HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
        :_node(node), _pht(pht) {}

    // 普通迭代器拷贝构造
    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; }
};

这里有个细节值得注意：关于权限转化。有人可能会问，能否通过权限转化来实现？实际上，权限转化通常只涉及引用和指针类型，而这里是模板参数之间的转化，需要显式定义构造函数来完成从 Iterator 到 HTIterator 的转换。

3. const 迭代器

对于 unordered_set 而言，无论是普通迭代器还是 const 迭代器，最终都被 typedef 为 const_iterator，因为集合中的元素本身不可变。

而在 unordered_map 中，情况稍微复杂些。key 是不允许改变的，但 value 可以修改。如果像 set 那样直接写，会导致 key 和 value 都不能修改。因此，我们在 pair 的 key 上加 const，即 pair<const K, V>，这样就能精确控制 value 的可变性。

4. insert 返回值与 operator[]

插入操作的返回值设计非常实用，它告诉我们要不要做额外处理。

unordered_set：

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

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

这里的类型转换比较关键，特别是 operator[] 的实现。当 key 不存在时，它会先插入一个默认构造的 value，然后返回该 value 的引用。这种机制虽然方便，但也意味着调用 operator[] 会改变容器状态，使用时需注意性能开销。

理解这些底层细节，有助于我们在实际开发中更合理地选择容器，并避免一些常见的陷阱。