C++ STL 核心容器模拟：unordered_set 与 unordered_map 实现

stl_hash_set

/*-------------------------- stl_hash_set --------------------------*/
template<class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, class Alloc = alloc>
class hash_set {
private:
    typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
    ht rep;
public:
    typedef typename ht::key_type key_type;
    typedef typename ht::value_type value_type;
    typedef typename ht::hasher hasher;
    typedef typename ht::key_equal key_equal;
    typedef typename ht::const_iterator iterator;
    typedef typename ht::const_iterator const_iterator;
    hasher hash_funct() const { return rep.hash_funct(); }
    key_equal key_eq() const { return rep.key_eq(); }
};

stl_hash_map

/*-------------------------- stl_hash_map --------------------------*/
template<class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc>
class hash_map {
private:
    typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht;
    ht rep;
public:
    typedef typename ht::key_type key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef typename ht::value_type value_type;
    typedef typename ht::hasher hasher;
    typedef typename ht::key_equal key_equal;
    typedef typename ht::iterator iterator;
    typedef typename ht::const_iterator const_iterator;
};

代码实现

容器结构设计

头文件实现

HashTable.h

这是底层哈希表的核心实现，包含节点定义、迭代器逻辑及扩容策略。

#pragma once
#include <iostream>
#include <vector>
using namespace std;

/*------------------ 任务：定义哈希表函数的'通用类模板'------------------*/
template<class K>
struct HashFunc {
    // 重载 () 运算符 ---> 作用：将 K 类型转化为 size_t 类型，用于计算哈希值
    size_t operator()(const K& key) {
        return (size_t)key; // 默认为直接转换，适用于 int、long 等整数类型
    }
};

/*------------------ 任务：定义哈希函数的'模板特化'------------------*/
template<>
struct HashFunc<string> {
    // 实现：'() 运算符的重载' ---> 作用：将 string 类型的变量转化为哈希值
    size_t operator()(const string& s) {
        // 定义 size_t 类型变量记录 string 类型的变量计算的哈希值
        size_t hash = 0;
        // 使用范围 for 循环遍历字符串并用 BKDR 算法计算其哈希值
        for (auto it : s) {
            // 先将字符的 ASCII 值累加到哈希值中
            hash += it;
            // 再让哈希值乘以质数 131（BKDR 哈希算法认为：131 可有效减少冲突）
            hash *= 131;
        }
        // 返回最终计算的哈希值
        return hash;
    }
};

/*------------------ 任务：实现'获取下一个 >=n 的质数的函数'---> '用于哈希表扩容'------------------*/
inline unsigned long _stl_next_prime(unsigned long n) {
    // 指定素数表的大小
    static const int _stl_num_primes = 28;
    // 定义素数表覆盖常见哈希表大小
    static const unsigned long _stl_prime_list[_stl_num_primes] = {
        53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241,
        786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
        402653189, 805306457, 1610612741, 3221225473, 4294967291
    };
    // 使用二分查找找到第一个 >=n 的素数
    const unsigned long* first = _stl_prime_list;
    const unsigned long* last = _stl_prime_list + _stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    // 适合作为哈希表容量的质数
    return pos == last ? *(last - 1) : *pos;
}

/*------------------ 任务：使用'链地址法'实现哈希表------------------*/
namespace hash_bucket {
    /*------------------ 任务：定义'哈希表节点的结构体模板'------------------*/
    template<class T>
    struct HashNode {
        T _data;
        HashNode<T>* _next;
        HashNode(const T& data) : _data(data), _next(nullptr) {}
    };

    /*------------------ 任务：定义'哈希表的迭代器的结构体模板'------------------*/
    template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
    struct HTIterator {
        HashNode<T>* _node;
        const HashTable<K, T, KeyOfT, Hash>* _ht;

        typedef HashNode<T> Node;
        typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
        typedef HashTable<K, T, KeyOfT, Hash> HT;

        HTIterator(Node* node, const HT* ht) : _node(node), _ht(ht) {}

        Ref operator*() { return _node->_data; }
        Ptr operator->() { return &_node->_data; }
        bool operator!=(const Self& ht) { return _node != ht._node; }
        bool operator==(const Self& ht) { return _node == ht._node; }

        Self& operator++() {
            if (_node->_next) {
                _node = _node->_next;
            } else {
                KeyOfT kot;
                Hash hashFunc;
                size_t hash_i = hashFunc(kot(_node->_data)) % _ht->_tables.size();
                ++hash_i;
                while (hash_i < _ht->_tables.size()) {
                    _node = _ht->_tables[hash_i];
                    if (_node) break;
                    ++hash_i;
                }
                if (hash_i == _ht->_tables.size()) {
                    _node = nullptr;
                }
            }
            return *this;
        }
    };

    /*------------------ 任务：定义'哈希表的类模板'------------------*/
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
    private:
        vector<HashNode<T>*> _tables;
        size_t _n;
        typedef HashNode<T> Node;

        friend struct HTIterator<K, T, T&, T*, KeyOfT, Hash>;
        friend struct HTIterator<K, T, const T&, const T*, KeyOfT, Hash>;

    public:
        typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
        typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

        Iterator Begin() {
            if (_n == 0) return End();
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* current = _tables[i];
                if (current) return Iterator(current, this);
            }
        }

        Iterator End() { return Iterator(nullptr, this); }

        ConstIterator Begin() const {
            if (_n == 0) return End();
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* current = _tables[i];
                if (current) return ConstIterator(current, this);
            }
        }

        ConstIterator End() const { return ConstIterator(nullptr, this); }

        HashTable() : _tables(_stl_next_prime(0)), _n(0) {}

        ~HashTable() {
            for (size_t i = 0; i < _tables.size(); ++i) {
                Node* current = _tables[i];
                while (current) {
                    Node* next = current->_next;
                    delete current;
                    current = next;
                }
                _tables[i] = nullptr;
            }
        }

        Iterator Find(const K& key) {
            KeyOfT kot;
            Hash hashFunc;
            size_t hash_i = hashFunc(key) % _tables.size();
            Node* current = _tables[hash_i];
            while (current) {
                if (kot(current->_data) == key) return Iterator(current, this);
                current = current->_next;
            }
            return End();
        }

        bool Erase(const K& key) {
            KeyOfT kot;
            Hash hashFunc;
            size_t hash_i = hashFunc(key) % _tables.size();
            Node* curr = _tables[hash_i];
            Node* prev = nullptr;
            while (curr) {
                if (kot(curr->_data) == key) {
                    if (prev == nullptr) _tables[hash_i] = curr->_next;
                    else prev->_next = curr->_next;
                    delete curr;
                    --_n;
                    return true;
                }
                prev = curr;
                curr = curr->_next;
            }
            return false;
        }

        pair<Iterator, bool> Insert(const T& data) {
            KeyOfT kot;
            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 };
        }
    };
}

Myunordered_set.h

封装无序集合，通过仿函数适配底层哈希表。

#pragma once
#include "HashTable.h"
namespace Myunordered_set {
    enum State { EXIST, EMPTY, DELETE };

    template<class K, class V>
    struct HashData {
        pair<K, V> _kv;
        State _state = EMPTY;
    };

    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:
        typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
        typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator 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(); }
        iterator find(const K& key) { return _ht.Find(key); }
        bool erase(const K& key) { return _ht.Erase(key); }
        pair<iterator, bool> insert(const K& key) { return _ht.Insert(key); }
    };
}

Myunordered_map.h

封装无序映射，支持 [] 运算符重载。

#pragma once
#include "HashTable.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:
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator 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(); }
        iterator find(const K& key) { return _ht.Find(key); }
        bool erase(const K& key) { return _ht.Erase(key); }
        pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
        V& operator[](const K& key) {
            pair<iterator, bool> ret = insert({ key, V() });
            return ret.first->second;
        }
    };
}

测试文件：Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include "Myunordered_set.h"
#include "Myunordered_map.h"
using namespace std;

void test01() {
    cout << "=== 测试 unordered_set 基本功能 ===" << endl;
    Myunordered_set::unordered_set<int> s;
    s.insert(3); s.insert(1); s.insert(4); s.insert(1);
    s.insert(2); s.insert(5);
    cout << "遍历元素：";
    for (auto it = s.begin(); it != s.end(); ++it) cout << *it << " ";
    cout << endl;
    int key = 3;
    auto find_ret = s.find(key);
    if (find_ret != s.end()) cout << "找到元素：" << *find_ret << endl;
    key = 4;
    bool erase_ret = s.erase(key);
    if (erase_ret) cout << "删除元素 " << key << " 成功" << endl;
    cout << "删除后遍历：";
    for (auto val : s) cout << val << " ";
    cout << endl << endl;
}

void test02() {
    cout << "=== 测试 unordered_set 字符串类型 ===" << endl;
    Myunordered_set::unordered_set<string> str_set;
    str_set.insert("apple"); str_set.insert("banana"); str_set.insert("cherry");
    cout << "字符串集合元素：";
    for (const auto& str : str_set) cout << str << " ";
    cout << endl;
    string target = "banana";
    auto it = str_set.find(target);
    if (it != str_set.end()) cout << "找到字符串：" << *it << endl;
    str_set.erase("cherry");
    cout << "删除 cherry 后：";
    for (const auto& str : str_set) cout << str << " ";
    cout << endl << endl;
}

void test03() {
    cout << "=== 测试 unordered_map 基本功能 ===" << endl;
    Myunordered_map::unordered_map<string, int> m;
    m.insert({"apple", 10}); m.insert({"banana", 20}); m.insert({"cherry", 30});
    m["date"] = 40; m["banana"] = 25;
    cout << "遍历键值对：" << endl;
    for (auto it = m.begin(); it != m.end(); ++it) cout << it->first << ": " << it->second << endl;
    string key = "cherry";
    auto it = m.find(key);
    if (it != m.end()) cout << "找到 " << key << ": " << it->second << endl;
    key = "banana";
    bool erase_ret = m.erase(key);
    if (erase_ret) cout << "删除 " << key << " 成功" << endl;
    cout << "删除后 " << key << " 是否存在：" << (m.find(key) != m.end() ? "是" : "否") << endl << endl;
}

void test04() {
    cout << "=== 测试 unordered_map [] 运算符 ===" << endl;
    Myunordered_map::unordered_map<int, string> m;
    m[1]; m[2] = "two"; m[2] = "second"; m[3] = "three";
    for (auto& kv : m) cout << kv.first << ": " << kv.second << endl;
    cout << endl;
}

void test05() {
    cout << "=== 测试边界情况 ===" << endl;
    Myunordered_set::unordered_set<int> s_empty;
    cout << "空 set 的 begin() == end(): " << (s_empty.begin() == s_empty.end() ? "true" : "false") << endl;
    cout << "删除空 set 中的元素：" << (s_empty.erase(100) ? "成功" : "失败") << endl << endl;
    Myunordered_map::unordered_map<int, int> mp_empty;
    cout << "空 map 的 begin() == end(): " << (mp_empty.begin() == mp_empty.end() ? "true" : "false") << endl;
    cout << "访问空 map 的 []: " << mp_empty[100] << endl;
}

int main() {
    test01(); test02(); test03(); test04(); test05();
    return 0;
}

运行结果

核心设计解析

仿函数适配

由于 HashTable 是泛型实现，无法确定模板参数 T 具体是 K（如 unordered_set 的元素类型），还是 pair<K, V>（如 unordered_map 的键值对类型）。在插入操作时，需要用 K 对象转换为整数取模以及进行相等性比较。但 pair 的 value 本就不参与取模计算，且默认比较逻辑是对 key 和 value 一起比较，而我们实际只需要比较 K 对象。

因此，在 unordered_set 和 unordered_map 这一层，我们分别实现 SetKeyOfT 和 MapKeyOfT 这两个仿函数，传递给 HashTable 的 KeyOfT 参数。这样 HashTable 就能通过 KeyOfT 仿函数，从 T 类型对象里提取出 K 对象，再完成转换为整数取模以及 K 相等性比较的操作。

迭代器实现

unordered_set 和 unordered_map 的 iterator 实现框架与 list 类似：用一个类型封装'结点指针'，再通过重载运算符，让迭代器能像指针一样完成访问操作。需要注意的是，哈希表的迭代器是单向迭代器（只能向后遍历，无法反向）。

关于可修改性：

• unordered_map 的迭代器不允许修改 key，但允许修改 value。只需把 unordered_map 的键值对中'第一个参数（key）'设为 const K 即可。
• unordered_set 的迭代器不支持修改 key，只需把 unordered_set 的第二个模板参数改为 const K 即可。

前置 ++ 运算符逻辑

迭代器内部维护一个'指向结点的指针'，operator++ 实现时，要分两种情况：

1. 如果当前桶还有后续结点，直接让指针指向下一个结点即可。
2. 如果当前桶已经遍历完毕，就需要'寻找下一个桶'。

这里的关键设计是：迭代器中除了存'结点指针'，还会存'哈希表对象的指针'。当当前桶遍历完时，可通过哈希表对象，结合 key 值计算当前桶位置，然后往后找'第一个不为空的桶'，就能拿到下一批结点。

begin() 和 end() 的设计

• begin()：返回'第一个非空桶的第一个结点指针'构造的迭代器。
• end()：返回一个代表'遍历结束'的空迭代器（可用空指针等方式表示）。

[] 运算符重载

要让 unordered_map 支持 [] 运算符，关键在于调整 insert 相关的返回值逻辑。需要修改 HashTable 中的 Insert 函数，使其返回值类型变为 pair<Iterator, bool>。这样 unordered_map 的 operator[] 可以调用 insert，如果键存在则返回引用，如果不存在则插入新键值对（值为默认构造）并返回引用。

V& operator[](const K& key) {
    pair<iterator, bool> ret = insert({ key, V() });
    return ret.first->second;
}