C++ STL 进阶：unordered_set 与 unordered_map 模拟实现

注意：迭代器是单向的，且 operator++ 在链表末尾时需重新计算哈希位置以定位下一桶，避免死循环。

3. 插入与扩容机制

当负载因子达到 1 时触发扩容。扩容过程包括：

1. 创建新的桶数组（容量为原大小的 2 倍或下一个质数）。
2. 将旧表中所有节点重新计算哈希值并头插到新表对应桶中。
3. 交换新旧表指针。

pair<Iterator, bool> Insert(const T& data) {
    Iterator it = Find(kot(data));
    if (it != End()) return {it, false};

    if (_n == _tables.size()) {
        vector<Node*> newVector(_tables.size() * 2);
        for (size_t i = 0; i < _tables.size(); ++i) {
            Node* current = _tables[i];
            while (current) {
                Node* next = current->_next;
                size_t hash_i = hashFunc(kot(current->_data)) % newVector.size();
                current->_next = newVector[hash_i];
                newVector[hash_i] = current;
                current = next;
            }
            _tables[i] = nullptr;
        }
        _tables.swap(newVector);
    }

    Node* newNode = new Node(data);
    size_t hash_i = hashFunc(kot(data)) % _tables.size();
    newNode->_next = _tables[hash_i];
    _tables[hash_i] = newNode;
    ++_n;
    return {Iterator(newNode, this), true};
}

4. 封装 unordered_set 与 unordered_map

通过定义仿函数 SetKeyOfT 和 MapKeyOfT 提取键，将底层哈希表实例化为具体容器。

// Myunordered_set.h
namespace Myunordered_set {
template<class K, class Hash = HashFunc<K>>
class unordered_set {
private:
    struct SetKeyOfT {
        const K& operator()(const K& key) { return key; }
    };
    hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
public:
    pair<iterator, bool> insert(const K& key) {
        return _ht.Insert(key);
    }
    // ... begin, end, find, erase
};
}

对于 unordered_map，键值对中的 key 设为 const，确保迭代器只能修改 value 而不能修改 key，符合标准库规范。

// Myunordered_map.h
namespace Myunordered_map {
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map {
private:
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) { return kv.first; }
    };
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
public:
    V& operator[](const K& key) {
        pair<iterator, bool> ret = insert({key, V()});
        return ret.first->second;
    }
};
}

测试验证

测试覆盖基本功能、字符串类型支持、边界情况（空容器、删除不存在元素）以及 [] 运算符的特殊场景。重点验证了重复插入不生效、扩容后数据完整性以及迭代器遍历顺序的正确性。

总结

本次实现完整展示了无序容器的底层逻辑。关键在于哈希函数的设计、冲突解决策略（链地址法）、迭代器的跨桶遍历逻辑以及扩容时的重哈希处理。通过模板特化和仿函数，实现了高度泛化的底层数据结构，上层容器只需关注业务逻辑即可。