用一个红黑树封装出 mymap 和 myset：容器与底层解耦的设计课

// 红黑树的底层结点：只存颜色和三个指针，数据另放
struct __rb_tree_node_base
{
    typedef bool color_type;                // 颜色类型：红/黑
    typedef __rb_tree_node_base* base_ptr;  // 结点指针的别名
    color_type color;                       // 结点是红还是黑
    base_ptr parent;                        // 父结点指针
    base_ptr left;                          // 左孩子指针
    base_ptr right;                         // 右孩子指针
};
 
// 继承了基类结点，再额外多存一份"真实的数据"
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
    typedef __rb_tree_node<Value>* link_type; // 指向本类型结点的指针
    Value value_field;                        // 结点真正存的值，Value 是个模板参数
};

// insert 用的是第二个模板参数的左形参
pair<iterator, bool> insert_unique(const value_type& x);
 
// erase 和 find 用第一个模板参数做形参
size_type erase(const key_type& x);
iterator find(const key_type& x);

// 结点颜色枚举
enum Colour
{
    RED,      // 红色，新插入的结点默认都是红的
    BLACK     // 黑色，根结点必须是黑的
};
 
// 红黑树结点模板：T 是结点里真正要存的数据类型
template<class T>
struct RBTreeNode
{
    T _data;                    // 结点真正存的数据，T 可以是 key，也可以是 pair
    RBTreeNode<T>* _left;       // 左孩子指针
    RBTreeNode<T>* _right;      // 右孩子指针
    RBTreeNode<T>* _parent;     // 父结点指针，方便向上调整和迭代器++
    Colour _col;                // 结点颜色
 
    // 构造函数：数据由外部传入，三个指针置空，颜色取默认值
    RBTreeNode(const T& data)
        : _data(data)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _col(RED)             // 默认染红，后面插入时根再单独染黑
    {}
};

// K    : 检索时用的 key 类型（find/erase 的形参类型）
// T    : 结点里真正存的那个数据（map 是 pair，set 是 key）
// KeyOfT: 从 T 里取出 K 的仿函数，树靠它只比较 key
template<class K, class T, class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;   // 结点类型别名，把一长串模板写短
    Node* _root = nullptr;        // 整棵树的根
    // 其余成员函数（Insert、Find、Begin、End、RotateL、RotateR 等）
    // 都会在后续各节中补全
};

// 这就是标准库 pair 提供的 operator< 的语义：
// 先比 first，first 相等才比 second
template <class T1, class T2>
bool operator<(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
{
    return lhs.first < rhs.first
           || (!(rhs.first < lhs.first) && lhs.second < rhs.second);
}

// 在 map 这一层实现：从 pair<K, V> 里把 key 取出来
struct MapKeyOfT
{
    // 接收一个 pair 对象，返回它的 key（也就是 first）
    const K& operator()(const pair<K, V>& kv) const
    {
        return kv.first;   // pair 的第一个成员就是 key
    }
};
 
// 在 set 这一层实现：set 的 data 本身就是 key
struct SetKeyOfT
{
    // 接收一个 key，原样返回即可
    const K& operator()(const K& key) const
    {
        return key;        // 数据就是 key 本人，不用取
    }
};

template<class K, class T, class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
    Node* _root = nullptr;
 
public:
    // 插入：返回 pair<指向"新结点或已存在结点"的迭代器, 是否真的插入了>
    // 第二个元素为 false 表示 key 重复，插入失败
    pair<Iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)              // 树为空，第一个结点直接当根
        {
            _root = new Node(data);        // 创建新结点（颜色已在构造函数里给 RED）
            _root->_col = BLACK;           // 根必须染成黑色（红黑树性质一）
            return make_pair(Iterator(_root, _root), true);
        }
 
        KeyOfT kot;                        // 实例化仿函数，用来取 key
        Node* parent = nullptr;            // 记录查找路径上的父结点
        Node* cur = _root;                 // 从根开始往下找插入位置
 
        // 第一步：按 key 找到应该挂载的位置（标准的 BST 向下搜索）
        while (cur)
        {
            if (kot(cur->_data) < kot(data))     // 当前 key 比待插 key 小
            {
                parent = cur;                    // 往右子树走
                cur = cur->_right;
            }
            else if (kot(cur->_data) > kot(data)) // 当前 key 更大
            {
                parent = cur;                    // 往左子树走
                cur = cur->_left;
            }
            else
            {
                // key 已存在：取消插入，返回那个已存在的结点 + false
                return make_pair(Iterator(cur, _root), false);
            }
        }
 
        // 第二步：把新结点挂到 parent 的孩子位置
        cur = new Node(data);              // 新结点默认红色（构造函数保证）
        Node* newnode = cur;               // 记住新结点，最后要返回它
        if (kot(parent->_data) < kot(data))
            parent->_right = cur;          // 比父大，挂右边
        else
            parent->_left = cur;           // 比父小，挂左边
        cur->_parent = parent;             // 设置父指针，形成双向链接
 
        // 第三步：调整颜色、必要时旋转，维持红黑树五条性质
        while (parent && parent->_col == RED)  // 只可能出现"父子双红"的违规
        {
            Node* grand = parent->_parent;     // 祖父结点
            if (parent == grand->_left)        // 父是祖父的左孩子
            {
                Node* uncle = grand->_right;   // 叔叔是祖父的右孩子
                if (uncle && uncle->_col == RED)
                {
                    // 情况一：叔叔存在且为红，直接变色，然后向上继续
                    parent->_col = BLACK;      // 父变黑
                    uncle->_col = BLACK;       // 叔变黑
                    grand->_col = RED;         // 祖父变红，作为新的 cur
                    cur = grand;               // 问题转移到祖父头上
                    parent = cur->_parent;     // 继续检查上一层
                }
                else
                {
                    // 情况二/三：叔叔为黑或不存在，旋转 + 变色
                    if (cur == parent->_left)
                    {
                        RotateR(grand);        // cur 也在左，做一次右单旋
                        parent->_col = BLACK;
                        grand->_col = RED;
                    }
                    else
                    {
                        RotateL(parent);       // cur 在右，先对父左旋
                        RotateR(grand);        // 再对祖父右旋，形成左右双旋
                        cur->_col = BLACK;
                        grand->_col = RED;
                    }
                    break;                     // 旋转后子树已平衡，结束
                }
            }
            else                                // 父是祖父的右孩子，镜像对称
            {
                Node* uncle = grand->_left;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grand->_col = RED;
                    cur = grand;
                    parent = cur->_parent;
                }
                else
                {
                    if (cur == parent->_right)
                    {
                        RotateL(grand);        // 右单旋
                        parent->_col = BLACK;
                        grand->_col = RED;
                    }
                    else
                    {
                        RotateR(parent);       // 右左双旋
                        RotateL(grand);
                        cur->_col = BLACK;
                        grand->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;                   // 循环结束，把根强制染黑
        return make_pair(Iterator(newnode, _root), true); // 返回新结点迭代器
    }
 
private:
    // 左单旋：把 parent 作为旋转轴向下旋转，提升它的右孩子
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;          // 待提升的右孩子
        Node* subRL = subR->_left;            // 右孩子的左子树，要转嫁
        parent->_right = subRL;               // 把 subRL 挂到 parent 右边
        if (subRL)
            subRL->_parent = parent;          // 更新 subRL 的父指针
 
        Node* parentParent = parent->_parent; // 记下 parent 的原父
        subR->_left = parent;                 // parent 变成 subR 的左孩子
        parent->_parent = subR;               // parent 的父指向 subR
 
        if (parentParent == nullptr)          // parent 原本是根
        {
            _root = subR;                     // subR 晋升为根
            subR->_parent = nullptr;
        }
        else                                  // parent 原本不是根
        {
            if (parent == parentParent->_left)
                parentParent->_left = subR;    // 挂到祖父左边
            else
                parentParent->_right = subR;   // 挂到祖父右边
            subR->_parent = parentParent;
        }
    }
 
    // 右单旋：与左单旋镜像对称
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;
 
        Node* parentParent = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
 
        if (parentParent == nullptr)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (parent == parentParent->_left)
                parentParent->_left = subL;
            else
                parentParent->_right = subL;
            subL->_parent = parentParent;
        }
    }
};

// 红黑树迭代器模板
// T 是数据类型，Ref 是解引用后的引用类型（T& 或 const T&），Ptr 是指针类型
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
    typedef RBTreeNode<T> Node;               // 结点类型别名
    typedef RBTreeIterator<T, Ref, Ptr> Self; // 自身类型别名
 
    Node* _node;                              // 迭代器当前指向的结点
    Node* _root;                              // 树根，--end() 时找最右结点要用
 
    // 构造函数：用结点指针和树根初始化
    RBTreeIterator(Node* node, Node* root)
        : _node(node)
        , _root(root)
    {}
 
    // ++：走到中序的下一个结点
    Self& operator++()
    {
        if (_node->_right)                    // 右子树不为空
        {
            // 下一个是中序第一个 -> 右子树最左结点
            Node* leftMost = _node->_right;
            while (leftMost->_left)
                leftMost = leftMost->_left;
            _node = leftMost;
        }
        else                                  // 右子树为空，往上找祖先
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            // 只要是父的右孩子就继续爬，直到找到"是父左孩子"的结点
            while (parent && cur == parent->_right)
            {
                cur = parent;
                parent = cur->_parent;
            }
            _node = parent;                   // 那个祖父就是中序下一个（可能为 nullptr 即 end）
        }
        return *this;
    }
 
    // --：走到中序的前一个结点
    Self& operator--()
    {
        if (_node == nullptr)                 // 针对 --end() 的特例
        {
            // end 的前一个是最右结点
            Node* rightMost = _root;
            while (rightMost && rightMost->_right)
                rightMost = rightMost->_right;
            _node = rightMost;
        }
        else if (_node->_left)                // 左子树不为空
        {
            // 前一个是左子树中序最后一个 -> 最右结点
            Node* rightMost = _node->_left;
            while (rightMost->_right)
                rightMost = rightMost->_right;
            _node = rightMost;
        }
        else                                  // 左子树为空，往上找祖先
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            // 只要是父的左孩子就继续爬，直到找到"是父右孩子"的结点
            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = cur->_parent;
            }
            _node = parent;
        }
        return *this;
    }
 
    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; } // 相等
};

// 在 RBTree 类里补充的类型别名
typedef RBTreeIterator<T, T&, T*>          Iterator;      // 普通迭代器，可修改
typedef RBTreeIterator<T, const T&, const T*> ConstIterator; // 常量迭代器，只读
 
// 中序遍历起点：最左结点
Iterator Begin()
{
    Node* leftMost = _root;
    while (leftMost && leftMost->_left)
        leftMost = leftMost->_left;
    return Iterator(leftMost, _root);
}
 
// 中序遍历终点：用 nullptr 表示
Iterator End()
{
    return Iterator(nullptr, _root);      // 哨兵，指向空
}
 
// const 版本：返回只读迭代器
ConstIterator Begin() const
{
    Node* leftMost = _root;
    while (leftMost && leftMost->_left)
        leftMost = leftMost->_left;
    return ConstIterator(leftMost, _root);
}
 
ConstIterator End() const
{
    return ConstIterator(nullptr, _root);
}

#include <iostream>
#include <string>
using namespace std;
 
// 自定义类型：学生。我们要让它能进树，需要给它定义 <
struct Student
{
    int    _id;      // 学号，决定排序
    string _name;    // 姓名，不影响排序
 
    Student(int id, const string& name) : _id(id), _name(name) {}
};
 
// 关键：重载 operator<，只按学号比
bool operator<(const Student& lhs, const Student& rhs)
{
    return lhs._id < rhs._id;
}
 
int main()
{
    // 用 std::set 演示读者最熟悉的形态，同一套思路适用于我们的 myset
    set<Student> s;
    s.insert(Student(3, "小红"));
    s.insert(Student(1, "小明"));
    s.insert(Student(2, "小刚"));
 
    // 按学号从小到大输出：小明->小刚->小红
    for (const Student& st : s)
        cout << st._id << ":" << st._name << " ";
    cout << endl;
    return 0;
}

// 课件里截取的源码声明：模板里多出 Compare（默认 less）与 Alloc 两个参数
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set;

// 等价且只依赖 < 的写法（标准库语义一致）
if (kot(cur->_data) < kot(data))          // cur 的 key 小 -> 往右走
    cur = cur->_right;
else if (kot(data) < kot(cur->_data))     // data 的 key 小 -> 往左走
    cur = cur->_left;
else
    break;                                // 既不小也不大 -> 视为 key 重复

// 按 key 查找：返回指向该结点的迭代器，找不到返回 End()
// 注意：这是在 RBTree 类内部，所以使用的是本类的 Iterator（大写）别名
Iterator Find(const K& key)
{
    KeyOfT kot;                     // 取 key 的仿函数
    Node* cur = _root;
    while (cur)
    {
        if (kot(cur->_data) < key)          // cur 的 key 比要找的小
            cur = cur->_right;
        else if (key < kot(cur->_data))     // cur 的 key 比要找的大
            cur = cur->_left;
        else
            return Iterator(cur, _root);    // 相等，找到了
    }
    return End();                           // 走到空，没找到
}

// 迷你 set：只支持插入、查找、遍历
template<class K>
class set
{
    // 仿函数：set 的 data 就是 key，原样取出
    struct SetKeyOfT
    {
        const K& operator()(const K& key) const
        {
            return key;      // 数据本身就是 key，直接返回
        }
    };
 
public:
    // 从底层红黑树导出迭代器类型给外部用
    typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
    typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;
 
    iterator begin()               { return _t.Begin(); }
    iterator end()                 { return _t.End(); }
    const_iterator begin() const   { return _t.Begin(); }
    const_iterator end() const     { return _t.End(); }
 
    // 插入单个 key
    pair<iterator, bool> insert(const K& key)
    {
        return _t.Insert(key);     // 转发给底层树
    }
 
    // 按 key 查找
    iterator find(const K& key)
    {
        return _t.Find(key);       // 转发给底层树
    }
 
private:
    // 关键：第二个模板参数用 const K，保证 set 元素只读
    RBTree<K, const K, SetKeyOfT> _t;   // 底层就是一棵通用红黑树
};

typedef RBTreeIterator<const K, const K&, const K*> Iterator;        // 底层实际展开
typedef RBTreeIterator<const K, const K&, const K*> ConstIterator;   // 完全一样

// 迷你 map：key 带映射 value
template<class K, class V>
class map
{
    // 仿函数：从 pair 里把 key（first）取出来
    struct MapKeyOfT
    {
        const K& operator()(const pair<K, V>& kv) const
        {
            return kv.first;   // pair 的 first 就是 key
        }
    };
 
public:
    // 导出迭代器类型
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;
 
    iterator begin()               { return _t.Begin(); }
    iterator end()                 { return _t.End(); }
    const_iterator begin() const   { return _t.Begin(); }
    const_iterator end() const     { return _t.End(); }
 
    // 插入一个 key -> value 的映射
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
        return _t.Insert(kv);      // 底层树只认这个 pair
    }
 
    // 按 key 查找
    iterator find(const K& key)
    {
        return _t.Find(key);
    }
 
    // 用 [] 访问或修改：不存在就插入，存在就返回 value 引用
    V& operator[](const K& key)
    {
        // 先尝试插入一个"key 配默认构造的 value"
        pair<iterator, bool> ret = insert(make_pair(key, V()));
        // ret.first 指向 key 所在的结点（刚插入的或已存在的）
        return ret.first->second;   // 取出并返回它的 value 引用
    }
 
private:
    // 关键：pair 的 first 是 const K，保证 key 不可改、value 可改
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;  // 底层同样是那棵通用树
};

dict["left"] = "左边，剩余";   // key 已存在：拿到它的 value 引用并覆盖
dict["insert"] = "插入";       // key 不存在：先插入空 value，再赋新值
dict["string"];                // key 不存在：只插入一个空 value，不做赋值

void test_map()
{
    bit::map<string, string> dict;              // 建立 string->string 的字典
    dict.insert({ "sort", "排序" });            // 用 insert 插入三个词条
    dict.insert({ "left", "左边" });
    dict.insert({ "right", "右边" });
 
    dict["left"] = "左边，剩余";                // key 存在：修改 value
    dict["insert"] = "插入";                    // key 不存在：插入新词条
    dict["string"];                             // key 不存在：只插空 value
 
    bit::map<string, string>::iterator it = dict.begin();
    while (it != dict.end())
    {
        // 你可以试试解开下面这行：改 key 会在编译期被拒
        // it->first += 'x';
        it->second += 'x';                      // 改 value 是允许的
        cout << it->first << ":" << it->second << endl; // 用 -> 访问 key 和 value
        ++it;                                   // 中序遍历推进
    }
    cout << endl;
}

void test_set()
{
    bit::set<int> s;                            // 建一个整数 set
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; // 乱序数据
    for (auto e : a)
        s.insert(e);                            // 逐个插入
 
    for (auto e : s)                            // 范围 for 遍历底层是中序
        cout << e << " ";                       // 会输出有序结果
    cout << endl;
}

#include <iostream>
#include <string>
#include <utility>
using namespace std;
 
namespace bit
{
    // ---------- 结点 ----------
    enum Colour { RED, BLACK };
 
    template<class T>
    struct RBTreeNode
    {
        T _data;
        RBTreeNode<T>* _left;
        RBTreeNode<T>* _right;
        RBTreeNode<T>* _parent;
        Colour _col;
 
        RBTreeNode(const T& data)
            : _data(data), _left(nullptr), _right(nullptr),
              _parent(nullptr), _col(RED) {}   // 新结点默认染红
    };
 
    // ---------- 迭代器 ----------
    template<class T, class Ref, class Ptr>
    struct RBTreeIterator
    {
        typedef RBTreeNode<T> Node;
        typedef RBTreeIterator<T, Ref, Ptr> Self;
 
        Node* _node;
        Node* _root;
 
        RBTreeIterator(Node* node, Node* root) : _node(node), _root(root) {}
 
        Self& operator++()
        {
            if (_node->_right)
            {
                Node* leftMost = _node->_right;
                while (leftMost->_left) leftMost = leftMost->_left;
                _node = leftMost;
            }
            else
            {
                Node* cur = _node;
                Node* parent = cur->_parent;
                while (parent && cur == parent->_right)
                {
                    cur = parent;
                    parent = cur->_parent;
                }
                _node = parent;   // 可能为 nullptr，即 end()
            }
            return *this;
        }
 
        Self& operator--()
        {
            if (_node == nullptr)              // --end() 特例
            {
                Node* rightMost = _root;
                while (rightMost && rightMost->_right)
                    rightMost = rightMost->_right;
                _node = rightMost;
            }
            else if (_node->_left)
            {
                Node* rightMost = _node->_left;
                while (rightMost->_right) rightMost = rightMost->_right;
                _node = rightMost;
            }
            else
            {
                Node* cur = _node;
                Node* parent = cur->_parent;
                while (parent && cur == parent->_left)
                {
                    cur = parent;
                    parent = cur->_parent;
                }
                _node = parent;
            }
            return *this;
        }
 
        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; }
    };
 
    // ---------- 红黑树 ----------
    template<class K, class T, class KeyOfT>
    class RBTree
    {
        typedef RBTreeNode<T> Node;
 
    public:
        typedef RBTreeIterator<T, T&, T*>          Iterator;
        typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
 
        RBTree() = default;
        ~RBTree() { Destroy(_root); }            // 记得释放所有结点
 
        Iterator Begin()
        {
            Node* leftMost = _root;
            while (leftMost && leftMost->_left) leftMost = leftMost->_left;
            return Iterator(leftMost, _root);
        }
        Iterator End() { return Iterator(nullptr, _root); }
 
        ConstIterator Begin() const
        {
            Node* leftMost = _root;
            while (leftMost && leftMost->_left) leftMost = leftMost->_left;
            return ConstIterator(leftMost, _root);
        }
        ConstIterator End() const { return ConstIterator(nullptr, _root); }
 
        pair<Iterator, bool> Insert(const T& data)
        {
            if (_root == nullptr)
            {
                _root = new Node(data);
                _root->_col = BLACK;             // 根必须黑
                return make_pair(Iterator(_root, _root), true);
            }
 
            KeyOfT kot;
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (kot(cur->_data) < kot(data))       { parent = cur; cur = cur->_right; }
                else if (kot(cur->_data) > kot(data))  { parent = cur; cur = cur->_left;  }
                else
                    return make_pair(Iterator(cur, _root), false); // key 重复
            }
 
            cur = new Node(data);
            Node* newnode = cur;
            if (kot(parent->_data) < kot(data)) parent->_right = cur;
            else parent->_left = cur;
            cur->_parent = parent;
 
            while (parent && parent->_col == RED)      // 父子双红，需要调整
            {
                Node* grand = parent->_parent;
 
                if (parent == grand->_left)            // 父在祖父左边
                {
                    Node* uncle = grand->_right;
                    if (uncle && uncle->_col == RED)   // 情况一：叔红 -> 变色上提
                    {
                        parent->_col = BLACK;
                        uncle->_col = BLACK;
                        grand->_col = RED;
                        cur = grand;
                        parent = cur->_parent;
                    }
                    else                               // 情况二/三：叔黑或空 -> 旋转
                    {
                        if (cur == parent->_left)      // 左左：右单旋
                        {
                            RotateR(grand);
                            parent->_col = BLACK;
                            grand->_col = RED;
                        }
                        else                           // 左右：左旋+右旋
                        {
                            RotateL(parent);
                            RotateR(grand);
                            cur->_col = BLACK;
                            grand->_col = RED;
                        }
                        break;
                    }
                }
                else                                   // 父在祖父右边（镜像）
                {
                    Node* uncle = grand->_left;
                    if (uncle && uncle->_col == RED)
                    {
                        parent->_col = BLACK;
                        uncle->_col = BLACK;
                        grand->_col = RED;
                        cur = grand;
                        parent = cur->_parent;
                    }
                    else
                    {
                        if (cur == parent->_right)     // 右右：左单旋
                        {
                            RotateL(grand);
                            parent->_col = BLACK;
                            grand->_col = RED;
                        }
                        else                           // 右左：右旋+左旋
                        {
                            RotateR(parent);
                            RotateL(grand);
                            cur->_col = BLACK;
                            grand->_col = RED;
                        }
                        break;
                    }
                }
            }
            _root->_col = BLACK;                       // 最终根染黑
            return make_pair(Iterator(newnode, _root), true);
        }
 
        Iterator Find(const K& key)
        {
            KeyOfT kot;
            Node* cur = _root;
            while (cur)
            {
                if (kot(cur->_data) < key)        cur = cur->_right;
                else if (key < kot(cur->_data))   cur = cur->_left;
                else return Iterator(cur, _root);
            }
            return End();
        }
 
    private:
        void RotateL(Node* parent)
        {
            Node* subR  = parent->_right;
            Node* subRL = subR->_left;
            parent->_right = subRL;
            if (subRL) subRL->_parent = parent;
 
            Node* parentParent = parent->_parent;
            subR->_left = parent;
            parent->_parent = subR;
 
            if (parentParent == nullptr)
            {
                _root = subR;
                subR->_parent = nullptr;
            }
            else
            {
                if (parent == parentParent->_left) parentParent->_left = subR;
                else parentParent->_right = subR;
                subR->_parent = parentParent;
            }
        }
 
        void RotateR(Node* parent)
        {
            Node* subL  = parent->_left;
            Node* subLR = subL->_right;
            parent->_left = subLR;
            if (subLR) subLR->_parent = parent;
 
            Node* parentParent = parent->_parent;
            subL->_right = parent;
            parent->_parent = subL;
 
            if (parentParent == nullptr)
            {
                _root = subL;
                subL->_parent = nullptr;
            }
            else
            {
                if (parent == parentParent->_left) parentParent->_left = subL;
                else parentParent->_right = subL;
                subL->_parent = parentParent;
            }
        }
 
        void Destroy(Node* root)                    // 后序释放整棵树
        {
            if (root == nullptr) return;
            Destroy(root->_left);
            Destroy(root->_right);
            delete root;
        }
 
        Node* _root = nullptr;
    };
 
    // ---------- set ----------
    template<class K>
    class set
    {
        struct SetKeyOfT
        {
            const K& operator()(const K& key) const { return key; }
        };
 
    public:
        typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
        typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;
 
        iterator begin() { return _t.Begin(); }
        iterator end() { return _t.End(); }
        const_iterator begin() const { return _t.Begin(); }
        const_iterator end() const { return _t.End(); }
 
        pair<iterator, bool> insert(const K& key) { return _t.Insert(key); }
        iterator find(const K& key) { return _t.Find(key); }
 
    private:
        RBTree<K, const K, SetKeyOfT> _t;   // T 用 const K，set 元素只读
    };
 
    // ---------- map ----------
    template<class K, class V>
    class map
    {
        struct MapKeyOfT
        {
            const K& operator()(const pair<K, V>& kv) const { return kv.first; }
        };
 
    public:
        typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
        typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;
 
        iterator begin() { return _t.Begin(); }
        iterator end() { return _t.End(); }
        const_iterator begin() const { return _t.Begin(); }
        const_iterator end() const { return _t.End(); }
 
        pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); }
        iterator find(const K& key) { return _t.Find(key); }
 
        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = insert(make_pair(key, V()));
            return ret.first->second;
        }
 
    private:
        RBTree<K, pair<const K, V>, MapKeyOfT> _t;  // first 用 const K，key 不可改
    };
 
    // ---------- 测试 ----------
    void test_set()
    {
        set<int> s;
        int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
        for (auto e : a) s.insert(e);
        for (auto e : s) cout << e << " ";   // 中序 -> 升序
        cout << endl;
    }
 
    void test_map()
    {
        map<string, string> dict;
        dict.insert({ "sort", "排序" });
        dict.insert({ "left", "左边" });
        dict.insert({ "right", "右边" });
 
        dict["left"] = "左边，剩余";   // 改已有
        dict["insert"] = "插入";       // 新增
        dict["string"];                // 只插入空 value
 
        map<string, string>::iterator it = dict.begin();
        while (it != dict.end())
        {
            it->second += 'x';         // 改 value 允许
            cout << it->first << ":" << it->second << endl;
            ++it;
        }
        cout << endl;
    }
}
 
int main()
{
    bit::test_set();
    bit::test_map();
    return 0;
}

// 非 const 版本：查不到抛 std::out_of_range
V& at(const K& key)
{
    iterator it = find(key);
    if (it == end())
        throw std::out_of_range("map::at: key not found");
    return it->second;
}
 
// const 版本：调用 const 版本的 find，返回只读引用
const V& at(const K& key) const
{
    const_iterator it = find(key);
    if (it == end())
        throw std::out_of_range("map::at: key not found");
    return it->second;
}

pair<Iterator, bool> InsertMulti(const T& data)
{
    KeyOfT kot;
    if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(Iterator(_root, _root), true); }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        parent = cur;
        if (kot(cur->_data) <= kot(data))   // 相等也往右：保持一致，允许重复
            cur = cur->_right;
        else
            cur = cur->_left;
    }
    cur = new Node(data);
    Node* newnode = cur;
    if (kot(parent->_data) <= kot(data)) parent->_right = cur;
    else parent->_left = cur;
    cur->_parent = parent;
    // ……从这里开始的红黑修复（while (parent && parent->_col == RED) { … }）与原来完全一致
    _root->_col = BLACK;
    return make_pair(Iterator(newnode, _root), true);  // 此时 second 恒为 true
}

struct Student
{
    int    _id;
    string _name;
    Student(int id, const string& name) : _id(id), _name(name) {}
};
bool operator<(const Student& a, const Student& b) { return a._id < b._id; }
 
bit::set<Student> s;
s.insert(Student(3, "小红"));