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, pair<K, V>>。这种设计复用了哈希表的底层逻辑，只通过 KeyExtractor 来区分存储内容。

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

    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) {
    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[] 的实现。它本质上是在尝试插入一个默认构造的 Value，如果 Key 已存在则返回引用，不存在则插入新元素并返回该 Value 的引用。理解这一点对于避免意外修改数据至关重要。