用一个哈希桶封装出 myunordered_map 和 myunordered_set：解耦与迭代器设计

#include <iostream>
#include <string>
using namespace std;
 
// 默认的哈希仿函数：把关键字强转成 size_t 当哈希值
// K 是整数、指针、枚举等"整型友好"类型时够用
template<class K>
struct HashFunc
{
    size_t operator()(const K& key) const   // const 保证"算哈希"不改变任何状态
    {
        return (size_t)key;                 // (size_t) 强转：把 K 直接当成无符号整数
    }
};
 
int main()
{
    // 算几个 int 关键字的哈希值看看
    cout << HashFunc<int>()(42) << endl;          // 输出 42
    cout << HashFunc<int>()(-7) << endl;          // 输出 18446744073709551609（负数转无符号的补码）
    // cout << HashFunc<string>()(string("hi"));  // 错误：string 不能强转成 size_t
    return 0;
}

// hash_set 内部：value_type 和 key 都是 K，即"单值"
typedef hashtable<K, K, HashFcn, identity<K>, EqualKey, Alloc> ht;
 
// hash_map 内部：value_type 是整个 pair<const K, T>，key 是 K
typedef hashtable<pair<const K, T>, K, HashFcn,
                  select1st<pair<const K, T> >, EqualKey, Alloc> ht;

// identity：从 K 身上提取 K，即"原样返回自己"
template <class T>
struct identity
{
    const T& operator()(const T& x) const { return x; }
};
 
// select1st：从一个 pair 里掏出 first，即"取第一个字段"
template <class Pair>
struct select1st
{
    const typename Pair::first_type& operator()(const Pair& x) const
    { return x.first; }
};

#include <vector>
#include <string>
#include <utility>
#include <algorithm>   // lower_bound 用（取质数时）
#include <iostream>
using namespace std;
 
/*********** 1. 哈希仿函数：默认 + string 特化 ***********/
template<class K>
struct HashFunc
{
    size_t operator()(const K& key) const
    {
        return (size_t)key;   // 默认只对"能强转整数"的 K 有效
    }
};
 
// string 不能强转整数，单独特化一套"字符串哈希"算法
// 思路：逐个字符加权累加，得一个大整数。131 是经验常数
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key) const
    {
        size_t hash = 0;
        for (char c : key)
            hash = hash * 131 + (size_t)c;
        return hash;
    }
};
 
/*********** 2. 哈希桶的命名空间 ***********/
namespace hash_bucket
{
    // 哈希桶的结点：T 是"真正存进桶里的元素类型"
    // 对 set 来说 T 就是 K；对 map 来说 T 就是 pair<const K, V>
    template<class T>
    struct HashNode
    {
        T _data;                // 结点里存的数据
        HashNode<T>* _next;     // 指向桶内链表的下一个结点
 
        HashNode(const T& data) // 构造：只负责存数据，next 置空
            : _data(data)
            , _next(nullptr)
        {}
    };
}

namespace hash_bucket
{
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable
    {
        // 声明自己是迭代器的朋友：迭代器的 operator++ 要访问私有的 _tables
        template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
        friend struct HTIterator;
 
        typedef HashNode<T> Node;    // 给"结点类型"起个别名，后面写起来短
 
    public:
        // 普通迭代器：*it 返回 T&，可读可改
        typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
        // const 迭代器：*it 返回 const T&，只读
        typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;
 
    private:
        vector<Node*> _tables;       // 桶数组：每个元素是指向链表头的指针
        size_t _n = 0;               // 当前表里存的数据个数
    };
}

namespace hash_bucket
{
    template<class K, class T, class KeyOfT, class Hash>
    inline unsigned long __stl_next_prime(unsigned long n)
    {
        // 一份精心挑选的质数序列：53, 97, 193, ... 由一个翻倍再加的逻辑生成，
        // 保证"扩容后桶数仍为质数"，避免取模聚集
        static const unsigned long __stl_prime_list[] =
        {
            53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul,
            12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul,
            786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul,
            25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul,
            805306457ul, 1610612741ul, 3221225473ul
        };
 
        const unsigned long* first = __stl_prime_list;
        const unsigned long* last = __stl_prime_list +
                                     sizeof(__stl_prime_list) / sizeof(unsigned long);
        // 二分查找：找到第一个不小于 n 的质数
        const unsigned long* pos = lower_bound(first, last, n);
        return pos == last ? *(last - 1) : *pos;   // 都没有就不小于的最大质数
    }
}

// 在哈希表里按关键字查找，找到返回指向该结点的迭代器，找不到返回 end
Iterator Find(const K& key)
{
    KeyOfT kot;                                  // 造一个"提 key 工具"出来
    Hash hs;                                     // 造一个"哈希工具"出来
    size_t hashi = hs(key) % _tables.size();     // 算目标关键字该在哪个桶
    Node* cur = _tables[hashi];                  // 从该桶的链表头开始
    while (cur)                                  // 链表没走完就继续
    {
        if (kot(cur->_data) == key)              // 取结点里的 K 与要找的 key 比相等
        {
            return Iterator(cur, this);          // 命中，返回该结点的迭代器
        }
        cur = cur->_next;                        // 没命中，顺着链表往下走
    }
    return End();                                // 整条链都走完还没找到，返回 end
}

// set 的"提 key 工具"：元素本身就是 K，原样返回
struct SetKeyOfT
{
    const K& operator()(const K& key) const
    {
        return key;        // 自己就是自己，打平返回（对应 SGI 的 identity）
    }
};
 
// map 的"提 key 工具"：从 pair 里掏出 first 当作关键字
struct MapKeyOfT
{
    const K& operator()(const pair<K, V>& kv) const
    {
        return kv.first;   // 一只抓手伸进 pair，把 first 捞出来（对应 SGI 的 select1st）
    }
};

// 插入：返回 (指向已存在/新插入元素的迭代器, 本次是否真正插入)
pair<Iterator, bool> Insert(const T& data)
{
    KeyOfT kot;                        // 提 key 工具
    Iterator it = Find(kot(data));     // 先查这个元素的关键字在不在
    if (it != End())                   // 在，说明重复了
        return make_pair(it, false);   // 直接返回已存在位置，插入失败（去重）
 
    Hash hs;
    size_t hashi = hs(kot(data)) % _tables.size();   // 算该放哪个桶
 
    // 负载因子 == 1（数据个数 == 桶个数）就扩容，避免冲突越积越深
    if (_n == _tables.size())
    {
        // 新表挑一个更大的质数桶数
        vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
        for (size_t i = 0; i < _tables.size(); i++)
        {
            Node* cur = _tables[i];
            while (cur)    // 每个桶里的链表结点全部搬走
            {
                Node* next = cur->_next;              // 先记录下一个，防止搬丢
                size_t h = hs(kot(cur->_data)) % newtables.size();  // 在新表里重新算桶
                cur->_next = newtables[h];            // 头插到新表的对应桶
                newtables[h] = cur;
                cur = next;
            }
            _tables[i] = nullptr;                     // 旧桶清空，防悬垂毛边
        }
        _tables.swap(newtables);                      // 换成全新的桶数组（旧数组随局部变量析构释放）
    }
 
    Node* newnode = new Node(data);   // 造新结点（堆上分配，拷贝一份 data）
    newnode->_next = _tables[hashi];  // 头插：新结点指向原链表头
    _tables[hashi] = newnode;         // 桶头更新为新结点
    ++_n;                             // 计数 +1
    return make_pair(Iterator(newnode, this), true);  // 返回新结点，插入成功
}

// 删除：按关键字删除，找到并删掉返回 true，没找到返回 false
bool Erase(const K& key)
{
    KeyOfT kot;                          // 提 key 工具
    Hash hs;
    size_t hashi = hs(key) % _tables.size();   // 定位桶
    Node* prev = nullptr;                // 前驱指针，初始为"头结点之前"（即没有前驱）
    Node* cur = _tables[hashi];          // 从链表头开始
    while (cur)
    {
        if (kot(cur->_data) == key)      // 命中
        {
            if (prev == nullptr)         // 要删的是链表头
                _tables[hashi] = cur->_next;     // 直接把桶头换成下一个
            else                         // 要删的是中间/尾部结点
                prev->_next = cur->_next;        // 让前驱跳过它
            delete cur;                  // 释放堆结点，此时指向它的迭代器"悬垂"了
            --_n;                        // 计数 -1
            return true;
        }
        prev = cur;                      // 没命中，前驱走到当前，当前走到下一个
        cur = cur->_next;
    }
    return false;                        // 整条链都没有，返回 false
}

namespace hash_bucket
{
    // 前置声明：迭代器里要用到哈希表类型，先打个招呼
    template<class K, class T, class KeyOfT, class Hash> class HashTable;
 
    // 哈希表的迭代器（单向迭代器，只能 ++）
    // Ptr/Ref 用来区分"普通迭代器"和"const 迭代器"（一鱼两吃，见下方说明）
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
    struct HTIterator
    {
        typedef HashNode<T> Node;                          // 结点类型别名
        typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;  // 自己的类型
 
        Node* _node;                                       // 指向当前结点
        const HashTable<K, T, KeyOfT, Hash>* _pht;         // 指向哈希表，用于桶间跳转
 
        HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
            : _node(node)
            , _pht(pht)                                    // 两个指针都要带上
        {}
 
        Ref operator*()      // 解引用：返回当前结点的数据
        { return _node->_data; }
 
        Ptr operator->()     // 箭头：返回数据的地址，方便 it->first 这种写法
        { return &_node->_data; }
 
        bool operator!=(const Self& s) const   // 比较：只看结点指针是否相同
        { return _node != s._node; }
        bool operator==(const Self& s) const
        { return _node == s._node; }
 
        Self& operator++();                    // 前向 ++ 的实现单独拎出来写，见下
    };
 
    // operator++ 的实现：核心难点在"桶走完了要跨桶"
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
    HTIterator<K, T, Ptr, Ref, KeyOfT, Hash>&
    HTIterator<K, T, Ptr, Ref, KeyOfT, Hash>::operator++()
    {
        if (_node->_next)
        {
            // 情况一：当前桶里还有下一个结点，直接往后挪（桶内前进，跟单链表一样）
            _node = _node->_next;
        }
        else
        {
            // 情况二：当前桶走完了，需要跳到下一个非空桶
            KeyOfT kot;
            Hash hs;
            // 用当前结点的关键字反推出"我原本呆在哪个桶"
            size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
            ++hashi;                 // 从下一个桶开始找
            while (hashi < _pht->_tables.size())
            {
                if (_pht->_tables[hashi])   // 找到第一个非空桶
                    break;
                ++hashi;
            }
            if (hashi == _pht->_tables.size())
                _node = nullptr;            // 所有桶都扫完也没有非空的 → 设成 end() 哨兵
            else
                _node = _pht->_tables[hashi];   // 跳到那个非空桶的链表头
        }
        return *this;
    }
}

// 普通迭代器版本：能读能改
Iterator Begin()
{
    if (_n == 0)                       // 表空，直接返回 end
        return End();
    for (size_t i = 0; i < _tables.size(); i++)   // 从头找第一个非空桶
    {
        Node* cur = _tables[i];
        if (cur)                       // 桶非空，它的链表头就是起点
            return Iterator(cur, this);
    }
    return End();
}
 
Iterator End()
{
    return Iterator(nullptr, this);    // 空指针作为结束标记
}
 
// const 迭代器版本：只读
ConstIterator Begin() const
{
    if (_n == 0)
        return End();
    for (size_t i = 0; i < _tables.size(); i++)
    {
        Node* cur = _tables[i];
        if (cur)
            return ConstIterator(cur, this);
    }
    return End();
}
 
ConstIterator End() const
{
    return ConstIterator(nullptr, this);
}

// 普通迭代器：*it → T&，-> 返回 T*
typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
// const 迭代器：*it → const T&，-> 返回 const T*
typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

mystl::myunordered_set<int> s;
for (int i = 0; i < 53; i++)            // 塞满 53 个，桶数正好 53
    s.insert(i);
cout << s.BucketCount() << endl;        // 输出 153（第一个质数桶数，真实实现会各异，仅演示思路）
 
// 危险示范：把老的 begin 迭代器先存下来
auto old_it = s.begin();
// 再插入大量元素，这次插入会触发多次扩容
for (int i = 53; i < 200; i++)
    s.insert(i);
// 此时 old_it 代表的"下一个"在扩容后可能早已不是它以为的位置了
// ++old_it;   // ← 不要这么干！可能跳过元素、可能重复、甚至越界，属于未定义行为

namespace mystl
{
    template<class K, class Hash = HashFunc<K>>
    class myunordered_set
    {
        // set 的提 key 仿函数：元素就是 K，原样返回
        struct SetKeyOfT
        {
            const K& operator()(const K& key) const { return key; }
        };
 
    public:
        // 从哈希桶里借用迭代器类型（依赖类型必须加 typename）
        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(); }
 
        // 插入：去重由底层哈希表负责，传入单个 K
        pair<iterator, bool> insert(const K& key)
        { return _ht.Insert(key); }
 
        iterator find(const K& key)
        { return _ht.Find(key); }
 
        bool erase(const K& key)
        { return _ht.Erase(key); }
 
        size_t size() const { return _ht.Size(); }
 
    private:
        // 关键！元素类型用 const K —— 迭代器解引用得到 const K&，想改都改不了
        hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
    };
}

void test_set()
{
    mystl::myunordered_set<int> s;                    // K 是 int，用默认哈希
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 15 };
    for (auto e : a)
        s.insert(e);                                  // 重复的 15 会被底层去重
 
    // 用范围 for 遍历（底层其实走的就是迭代器）
    for (auto e : s)
        cout << e << " ";                             // 无序输出所有不重复的元素
    cout << endl;
 
    mystl::myunordered_set<int>::iterator it = s.begin();
    while (it != s.end())                             // 手动迭代
    {
        // *it += 1;              // 错误！元素类型是 const K，禁止修改
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

namespace mystl
{
    template<class K, class V, class Hash = HashFunc<K>>
    class myunordered_map
    {
        // map 的提 key 仿函数：从 pair 里掏出 first 作为关键字
        struct MapKeyOfT
        {
            const K& operator()(const pair<K, V>& kv) const
            { return kv.first; }
        };
 
    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(); }
 
        // 插入一个键值对
        pair<iterator, bool> insert(const pair<K, V>& kv)
        { return _ht.Insert(kv); }
 
        iterator find(const K& key)
        { return _ht.Find(key); }
 
        bool erase(const K& key)
        { return _ht.Erase(key); }
 
        size_t size() const { return _ht.Size(); }
 
        // operator[] 的具体实现见下方"第三点"详解
        V& operator[](const K& key);
 
    private:
        // 元素类型是 pair<const K, V>：first 不可改，second 可改
        hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
    };
}

// operator[]：要么返回已有值的引用，要么"造一个默认值插进去再返回引用"
V& myunordered_map<K, V, Hash>::operator[](const K& key)
{
    // 用"默认构造的 V"作为值去插入；插不成功说明 key 已存在，反正都能拿到位置
    pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
    return ret.first->second;   // 返回这个位置上的值（引用）
}

dict["hello"];            // 读：key 不存在 → 插一个 ("hello", "") 再返回空串引用
dict["hello"] = "你好";    // 写：key 不存在 → 插；已存在 → 覆盖值
dict["hello"] += "!";      // 读改写：拿到引用后自增拼接
cout << dict["hello"];     // 读：已存在 → 返回当前值（注意：若不存在会插空值！）

void test_map()
{
    mystl::myunordered_map<string, string> dict;    // 一个英文→中文的字典
    dict.insert(make_pair("sort", "排序"));
    dict.insert(make_pair("left", "左边"));
    dict["right"] = "右边";                          // 用 [] 插入
    dict["left"] = "左边，剩余";                      // key 已存在：是修改
    dict["insert"] = "插入";
    cout << dict["string"] << endl;                  // key 不存在：会插入空串 "" 再返回
 
    // 遍历：first 是 const 关键字，second 是可变值
    mystl::myunordered_map<string, string>::iterator it = dict.begin();
    while (it != dict.end())
    {
        it->second += 'x';                           // 修改值是允许的
        // it->first = "xxx";                        // 错误！first 是 const K，改不了
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
}

// 默认版本：只对"能强转成整数"的 K 适用（int、指针、枚举等）
template<class K>
struct HashFunc
{
    size_t operator()(const K& key) const { return (size_t)key; }
};
 
// 特化版本：专门为 string 写哈希算法
// 把每个字符加权累加，用 131 做乘数是"字符串哈希"里非常经典的套路
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key) const
    {
        size_t hash = 0;
        for (char c : key)                     // 遍历字符串每个字符
            hash = hash * 131 + (size_t)c;     // 累乘累加，让不同字符串尽量撞不同桶
        return hash;
    }
};

// 一个自定义类型做关键字，必须同时提供"等值比较"和"哈希函数"
struct Date
{
    int _year, _month, _day;
    Date(int y, int m, int d) : _year(y), _month(m), _day(d) {}
 
    // 必备一：等值比较——哈希表在同一个桶里靠它判断"找到没"
    bool operator==(const Date& d) const
    {
        return _year == d._year && _month == d._month && _day == d._day;
    }
};
 
// 必备二：针对 Date 特化哈希仿函数
// 把年月日三个数加权合并成一个整数，减少不同日期撞进同一桶
template<>
struct HashFunc<Date>
{
    size_t operator()(const Date& d) const
    {
        // 日乘小数 + 月乘大数，再加权年份，尽量让相邻日期也分散开
        return (size_t)((d._month * 31 + d._day) * 100 + d._year);
    }
};

void test_custom_type()
{
    mystl::myunordered_map<Date, string> holiday;   // 节假日表
    holiday.insert(make_pair(Date(2025, 10, 1), "国庆节"));
    holiday[Date(2025, 1, 1)] = "元旦";
    holiday[Date(2025, 6, 1)] = "儿童节";
 
    // 查询的关键字 Date(2025,10,1)：靠特化哈希定位桶，靠 == 在桶里锁定它
    mystl::myunordered_map<Date, string>::iterator it = holiday.find(Date(2025, 10, 1));
    if (it != holiday.end())
        cout << "10月1日是：" << it->second << endl;
 
    // 这里还有一层隐藏的含义：
    // Date(2025,10,1) 和 Date(2025,10,1) 是两个不同的临时对象，
    // 但因为 == 判定相等、哈希值也相同，哈希表便能把它们归到同一份上
}

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>   // lower_bound
using namespace std;
 
/********** 1. 哈希仿函数：默认 + 特化（string / Date） **********/
template<class K>
struct HashFunc
{
    size_t operator()(const K& key) const { return (size_t)key; }
};
 
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key) const
    {
        size_t hash = 0;
        for (char c : key)
            hash = hash * 131 + (size_t)c;
        return hash;
    }
};
 
// 自定义类型：Date（做关键字要"可哈希 + 可等值比较"）
struct Date
{
    int _year, _month, _day;
    Date(int y, int m, int d) : _year(y), _month(m), _day(d) {}
    bool operator==(const Date& d) const
    { return _year == d._year && _month == d._month && _day == d._day; }
};
 
template<>
struct HashFunc<Date>
{
    size_t operator()(const Date& d) const
    { return (size_t)((d._month * 31 + d._day) * 100 + d._year); }
};
 
/********** 2. 哈希桶（分开链式哈希表） **********/
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 KeyOfT, class Hash> class HashTable;
 
    // 迭代器：结点指针 + 表指针，双线索
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
    struct HTIterator
    {
        typedef HashNode<T> Node;
        typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
 
        Node* _node;
        const HashTable<K, T, KeyOfT, Hash>* _pht;
 
        HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
            : _node(node), _pht(pht) {}
 
        Ref operator*()        { return _node->_data; }
        Ptr operator->()       { return &_node->_data; }
        bool operator!=(const Self& s) const { return _node != s._node; }
        bool operator==(const Self& s) const { return _node == s._node; }
 
        Self& operator++()
        {
            if (_node->_next)                    // 桶内还有下一个
            {
                _node = _node->_next;
            }
            else                                 // 桶走完了，跨桶
            {
                KeyOfT kot;
                Hash hs;
                size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
                ++hashi;
                while (hashi < _pht->_tables.size())
                {
                    if (_pht->_tables[hashi]) break;
                    ++hashi;
                }
                _node = (hashi == _pht->_tables.size())
                        ? nullptr
                        : _pht->_tables[hashi];
            }
            return *this;
        }
    };
 
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable
    {
        template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
        friend struct HTIterator;
 
        typedef HashNode<T> Node;
 
        static unsigned long __stl_next_prime(unsigned long n)
        {
            static const unsigned long list[] =
            {
                53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul,
                12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul,
                786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul,
                25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul,
                805306457ul, 1610612741ul, 3221225473ul
            };
            const unsigned long* first = list;
            const unsigned long* last = list + sizeof(list) / sizeof(unsigned long);
            const unsigned long* pos = lower_bound(first, last, n);
            return pos == last ? *(last - 1) : *pos;
        }
 
    public:
        typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
        typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;
 
        HashTable()
        {
            _tables.resize(__stl_next_prime(0), nullptr);
        }
 
        ~HashTable()
        {
            for (size_t i = 0; i < _tables.size(); i++)
            {
                Node* cur = _tables[i];
                while (cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }
 
        Iterator Begin()
        {
            if (_n == 0) return End();
            for (size_t i = 0; i < _tables.size(); i++)
                if (_tables[i]) return Iterator(_tables[i], this);
            return End();
        }
        Iterator End() { return Iterator(nullptr, this); }
 
        ConstIterator Begin() const
        {
            if (_n == 0) return End();
            for (size_t i = 0; i < _tables.size(); i++)
                if (_tables[i]) return ConstIterator(_tables[i], this);
            return End();
        }
        ConstIterator End() const { return ConstIterator(nullptr, this); }
 
        pair<Iterator, bool> Insert(const T& data)
        {
            KeyOfT kot;
            Iterator it = Find(kot(data));
            if (it != End()) return make_pair(it, false);   // 去重
 
            Hash hs;
            size_t hashi = hs(kot(data)) % _tables.size();
 
            if (_n == _tables.size())                        // 负载因子 == 1 → 扩容
            {
                vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
                for (size_t i = 0; i < _tables.size(); i++)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;
                        size_t h = hs(kot(cur->_data)) % newtables.size();
                        cur->_next = newtables[h];
                        newtables[h] = cur;
                        cur = next;
                    }
                    _tables[i] = nullptr;
                }
                _tables.swap(newtables);
            }
 
            Node* newnode = new Node(data);
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            ++_n;
            return make_pair(Iterator(newnode, this), true);
        }
 
        Iterator Find(const K& key)
        {
            KeyOfT kot;
            Hash hs;
            size_t hashi = hs(key) % _tables.size();
            Node* cur = _tables[hashi];
            while (cur)
            {
                if (kot(cur->_data) == key)
                    return Iterator(cur, this);
                cur = cur->_next;
            }
            return End();
        }
 
        bool Erase(const K& key)
        {
            KeyOfT kot;
            Hash hs;
            size_t hashi = hs(key) % _tables.size();
            Node* prev = nullptr;
            Node* cur = _tables[hashi];
            while (cur)
            {
                if (kot(cur->_data) == key)
                {
                    if (prev == nullptr)
                        _tables[hashi] = cur->_next;
                    else
                        prev->_next = cur->_next;
                    delete cur;
                    --_n;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }
 
        size_t Size() const            { return _n; }
        size_t BucketCount() const     { return _tables.size(); }   // 桶数（调试、演示扩容）
 
    private:
        vector<Node*> _tables;    // 指针数组：桶 → 链表头
        size_t _n = 0;            // 表中存储数据个数
    };
}
 
/********** 3. 外壳一：myunordered_set（单值，不可改） **********/
namespace mystl
{
    template<class K, class Hash = HashFunc<K>>
    class myunordered_set
    {
        struct SetKeyOfT
        {
            const K& operator()(const K& key) const { return key; }
        };
    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(); }
 
        pair<iterator, bool> insert(const K& key) { return _ht.Insert(key); }
        iterator find(const K& key)               { return _ht.Find(key); }
        bool erase(const K& key)                  { return _ht.Erase(key); }
        size_t size() const                       { return _ht.Size(); }
 
    private:
        hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
    };
}
 
/********** 4. 外壳二：myunordered_map（键值对，[ ] 有则取无则建） **********/
namespace mystl
{
    template<class K, class V, class Hash = HashFunc<K>>
    class myunordered_map
    {
        struct MapKeyOfT
        {
            const K& operator()(const pair<K, V>& kv) const { return kv.first; }
        };
    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(); }
 
        pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
 
        V& operator[](const K& key)
        {
            // 有 key 则取，无 key 则插入默认值再取——"没有就建，有就取"
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }
 
        iterator find(const K& key)   { return _ht.Find(key); }
        bool erase(const K& key)      { return _ht.Erase(key); }
        size_t size() const           { return _ht.Size(); }
 
    private:
        hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
    };
}
 
/********** 5. 测试入口 **********/
int main()
{
    // --- set ---
    mystl::myunordered_set<int> s;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 15 };
    for (auto e : a) s.insert(e);              // 15 重复，会被去重
    for (auto e : s) cout << e << " ";         // 无序的、无重复的元素
    cout << endl;
    cout << "size = " << s.size() << ", bucket = " << 53 << endl;
 
    // --- map ---
    mystl::myunordered_map<string, string> dict;
    dict.insert(make_pair("sort", "排序"));
    dict["left"] = "左边";                       // 插入
    dict["right"] = "右边";
    dict["left"] = "左边，剩余";                  // 修改
    dict["insert"] = "插入";
    cout << "dict[\"string\"] = \"" << dict["string"] << "\"" << endl;  // 读也建空串
 
    for (auto& kv : dict)                        // 遍历：first 只读,second 可改
        cout << kv.first << ":" << kv.second << "  ";
    cout << endl;
 
    // --- 自定义类型关键字 ---
    mystl::myunordered_map<Date, string> holiday;
    holiday.insert(make_pair(Date(2025, 10, 1), "国庆节"));
    holiday[Date(2025, 1, 1)] = "元旦";
    holiday[Date(2025, 6, 1)] = "儿童节";
    auto it = holiday.find(Date(2025, 10, 1));
    if (it != holiday.end())
        cout << "10月1日是：" << it->second << endl;
 
    return 0;
}