红黑树进阶：手撕 STL 源码，封装 RB-tree 实现 map 与 set

关键问题：为什么 rb_tree 需要两个模板参数 Key 和 Value？

• Value：决定了节点中存储的数据类型（set 是 Key，map 是 pair）
• Key：用于查找和删除操作的参数类型（find/erase 的参数类型）

对于 set 而言，Key 和 Value 是相同的；对于 map 而言，Key 是键的类型，Value 是 pair 类型。这种设计使得一棵红黑树既能处理 set 场景，也能处理 map 场景。

二、模拟实现 map 和 set（实现复用红黑树的框架）

2.1 红黑树节点的定义

// RBTree.h
#pragma once
enum Colour { RED, BLACK };

template<class T>
struct RBTreeNode {
    T _data; // 节点存储的数据（泛型 T）
    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) {}
};

2.2 红黑树的基本框架

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); _root = nullptr; }

    // 插入接口
    pair<Iterator, bool> Insert(const T& data);
    // 查找接口
    Iterator Find(const K& key);
    // 迭代器相关
    Iterator Begin();
    Iterator End();
    ConstIterator Begin() const;
    ConstIterator End() const;

private:
    // 旋转操作
    void RotateL(Node* parent);
    void RotateR(Node* parent);
    // 销毁树
    void Destroy(Node* root);
    Node* _root = nullptr; // 根节点
};

2.3 解决 Key 的比较问题：KeyOfT 仿函数

问题：红黑树在插入时需要比较键的大小，但 T 可能是 Key 类型，也可能是 pair 类型。pair 的比较规则是 first 和 second 一起比较，不符合我们的需求（我们只想比较 key）。

解决方案：使用仿函数 KeyOfT，从 T 对象中取出 Key 进行比较。

// Mymap.h - map 中定义的 KeyOfT 仿函数
namespace bit {
template<class K, class V>
class map {
    // 仿函数：从 pair 中取出 key
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) {
            return kv.first; // 返回 pair 的 first（键）
        }
    };
    // ... 其他代码
};
}

// Myset.h - set 中定义的 KeyOfT 仿函数
namespace bit {
template<class K>
class set {
    // 仿函数：直接返回 key 本身
    struct SetKeyOfT {
        const K& operator()(const K& key) {
            return key; // 直接返回 key
        }
    };
    // ... 其他代码
};
}

2.4 支持 insert 插入

RBTree 中的 Insert 实现（关键部分是使用 KeyOfT 进行比较）

template<class K, class T, class KeyOfT>
pair<typename RBTree<K, T, KeyOfT>::Iterator, bool>
RBTree<K, T, KeyOfT>::Insert(const T& data) {
    // 1. 空树情况
    if (_root == nullptr) {
        _root = new Node(data);
        _root->_col = BLACK; // 根节点必须是黑色
        return make_pair(Iterator(_root, _root), true);
    }

    // 2. 查找插入位置
    KeyOfT kot; // 创建仿函数对象
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        // 使用 kot 取出 key 进行比较
        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);
        }
    }

    // 3. 创建新节点并链接
    cur = new Node(data);
    Node* newnode = cur;
    cur->_col = RED; // 新节点默认红色
    if (kot(parent->_data) < kot(data))
        parent->_right = cur;
    else
        parent->_left = cur;
    cur->_parent = parent;

    // 4. 红黑树性质修复（与之前实现的插入逻辑相同）
    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        if (parent == grandfather->_left) {
            Node* uncle = grandfather->_right;
            // 情况 1：叔叔存在且为红
            if (uncle && uncle->_col == RED) {
                // 变色处理
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                // 继续向上处理
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // 情况 2/3：叔叔不存在或为黑
                if (cur == parent->_left) {
                    // 左左：右单旋
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    // 左右：左右双旋
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        } else {
            // 对称情况：parent 是 grandfather 的右孩子
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED) {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                if (cur == parent->_right) {
                    // 右右：左单旋
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    // 右左：右左双旋
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    // 确保根节点为黑色
    _root->_col = BLACK;
    return make_pair(Iterator(newnode, _root), true);
}

2.5 map 和 set 的 insert 封装

// Mymap.h - map 的 insert
namespace bit {
template<class K, class V>
class map {
    // ... 前面的代码
public:
    pair<iterator, bool> insert(const pair<K, V>& kv) {
        return _t.Insert(kv); // 直接调用 RBTree 的 Insert
    }
private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

// Myset.h - set 的 insert
namespace bit {
template<class K>
class set {
    // ... 前面的代码
public:
    pair<iterator, bool> insert(const K& key) {
        return _t.Insert(key); // 直接调用 RBTree 的 Insert
    }
private:
    RBTree<K, const K, SetKeyOfT> _t;
};
}

三、迭代器的实现

3.1 迭代器结构设计

迭代器需要支持：

• operator++：前往中序下一个节点
• operator--：前往中序上一个节点
• operator*：解引用，获取节点数据
• operator->：通过指针访问成员
• operator==/!=：比较两个迭代器是否相等

// RBTree.h
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++();
    // 前置--
    Self& operator--();
    // 解引用
    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; }
};

3.2 迭代器的++操作

中序遍历的顺序是：左子树 → 根 → 右子树

template<class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::Self& 
RBTreeIterator<T, Ref, Ptr>::operator++() {
    if (_node == nullptr) return this->this; // end() 不能++
    if (_node->_right) {
        // 情况 1：右子树不为空
        // 中序下一个是右子树的最左节点
        Node* leftMost = _node->_right;
        while (leftMost->_left) {
            leftMost = leftMost->_left;
        }
        _node = leftMost;
    } else {
        // 情况 2：右子树为空
        // 向上找：孩子是父亲左的那个祖先
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_right) {
            cur = parent;
            parent = cur->_parent;
        }
        _node = parent; // 可能是 nullptr（到达 end）
    }
    return *this;
}

3.3 迭代器的–操作

template<class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::Self& 
RBTreeIterator<T, Ref, Ptr>::operator--() {
    if (_node == nullptr) // --end() 特殊处理
    {
        // end() 应该走到中序最后一个节点（整棵树的最右节点）
        Node* rightMost = _root;
        while (rightMost && rightMost->_right) {
            rightMost = rightMost->_right;
        }
        _node = rightMost;
    } else if (_node->_left) {
        // 情况 1：左子树不为空
        // 中序上一个节点是左子树的最右节点
        Node* rightMost = _node->_left;
        while (rightMost->_right) {
            rightMost = rightMost->_right;
        }
        _node = rightMost;
    } else {
        // 情况 2：左子树为空
        // 向上找：孩子是父亲右的那个祖先
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_left) {
            cur = parent;
            parent = cur->_parent;
        }
        _node = parent; // 可能是 nullptr（到达 rend？）
    }
    return *this;
}

–end() 的特殊处理：

• end() 迭代器指向 nullptr
• 当对 end() 执行–操作时，应该得到最后一个有效节点（最右节点）
• 所以需要记录_root 来找到最右节点

3.4 RBTree 中的迭代器接口

template<class K, class T, class KeyOfT>
class RBTree {
    // ... 前面的代码
public:
    typedef RBTreeIterator<T, T&, T*> Iterator;
    typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

    // begin() -> 最左节点
    Iterator Begin() {
        Node* leftMost = _root;
        while (leftMost && leftMost->_left) {
            leftMost = leftMost->_left;
        }
        return Iterator(leftMost, _root);
    }
    // end() -> 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);
    }
};

四、map 和 set 对迭代器的封装

4.1 set 的迭代器封装

// Myset.h
namespace bit {
template<class K>
class set {
    // ... 前面的代码
public:
    // 类型重命名：从 RBTree 中取出迭代器类型
    typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
    typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

    // begin/end 接口
    iterator begin() { return _t.Begin(); }
    iterator end() { return _t.End(); }
    const_iterator begin() const { return _t.Begin(); }
    const_iterator end() const { return _t.End(); }
private:
    RBTree<K, const K, SetKeyOfT> _t;
};
}

4.2 map 的迭代器封装

// Mymap.h
namespace bit {
template<class K, class V>
class map {
    // ... 前面的代码
public:
    // 类型重命名
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;

    // begin/end 接口
    iterator begin() { return _t.Begin(); }
    iterator end() { return _t.End(); }
    const_iterator begin() const { return _t.Begin(); }
    const_iterator end() const { return _t.End(); }
private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

4.3 测试迭代器

// 测试 set
void test_set() {
    bit::set<int> s;
    int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    for (auto e : a) {
        s.insert(e);
    }
    // 范围 for 测试（依赖 begin/end）
    for (auto e : s) {
        cout << e << " "; // 输出：1 2 3 4 5 6 7 14 15 16
    }
    cout << endl;
}

五、map 的 operator[] 实现

5.1 operator[] 的原理

map 的 operator[] 是一个非常方便的特性：

• 如果 key 存在，返回对应的 value 引用
• 如果 key 不存在，插入一个默认 value 并返回其引用

5.2 实现步骤

1. 修改 RBTree 的 Insert，返回 pair<Iterator, bool>
2. 在 map 的 operator[] 中调用 insert
3. 根据返回的迭代器访问 second

5.3 代码实现

// Mymap.h
namespace bit {
template<class K, class V>
class map {
    // ... 前面的代码
public:
    V& operator[](const K& key) {
        // 尝试插入：如果 key 不存在，插入{key, V()}
        // V() 会调用 V 类型的默认构造函数（内置类型为 0）
        pair<iterator, bool> ret = insert(make_pair(key, V()));
        // ret.first 是插入位置（新节点或已存在节点）的迭代器
        // 返回该节点的 second（value）的引用
        return ret.first->second;
    }
};
}

5.4 测试 operator[]

void test_map() {
    bit::map<string, string> dict;
    // 插入操作
    dict.insert({"sort", "排序"});
    dict.insert({"left", "左边"});
    dict.insert({"right", "右边"});
    
    // operator[] 的三种用法
    dict["left"] = "左边，剩余"; // 修改已存在 key 的 value
    dict["insert"] = "插入";     // 插入新 key-value
    dict["string"];              // 插入新 key，value 为默认值（空字符串）
    
    // 遍历输出
    for (auto& kv : dict) {
        // 不能修改 first，可以修改 second
        // kv.first += 'x'; // 错误！
        kv.second += 'x'; // 正确：value 可以修改
        cout << kv.first << ":" << kv.second << endl;
    }
}

输出结果：

insert:插入 x
left:左边，剩余 x
right:右边 x
sort:排序 x
string:x

六、const 迭代器和 const 正确性

6.1 const 迭代器的使用场景

// 接收 const 引用的函数
void Print(const bit::set<int>& s) {
    // 这里只能用 const_iterator，因为 s 是 const 的
    bit::set<int>::const_iterator it = s.begin();
    while (it != s.end()) {
        // *it += 10; // 错误！const 迭代器不允许修改
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

6.2 为什么要支持 const 迭代器？

• const 对象只能用 const 迭代器：保证 const 对象的内容不会被修改
• 语义清晰：表明这段代码只读不写
• 编译器检查：帮助捕获意外的修改

6.3 set 中 key 不可修改的保证

在 set 中，key 是不可修改的。实现方式：

// Myset.h
template<class K>
class set {
private:
    // RBTree 第二个模板参数传入 const K
    RBTree<K, const K, SetKeyOfT> _t;
};

这样，迭代器解引用得到的是 const K&，无法修改。

6.4 map 中 key 不可修改，value 可修改

// Mymap.h
template<class K, class V>
class map {
private:
    // RBTree 第二个模板参数传入 pair<const K, V>
    // key 是 const 的，value 是可修改的
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

• 迭代器解引用得到 pair<const K, V>&
• first 是 const，不能修改
• second 不是 const，可以修改

七、完整代码实现

7.1 RBTree.h（完整版）

#pragma once
#include <utility>
using namespace std;

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 == nullptr) return *this;
        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;
        }
        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); _root = nullptr; }

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

        cur = new Node(data);
        Node* newnode = cur;
        cur->_col = RED;
        if (kot(parent->_data) < kot(data))
            parent->_right = cur;
        else
            parent->_left = cur;
        cur->_parent = parent;

        // 修复红黑树性质
        while (parent && parent->_col == RED) {
            Node* grandfather = parent->_parent;
            if (parent == grandfather->_left) {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED) {
                    // 情况 1：变色
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    if (cur == parent->_left) {
                        // 左左：右单旋
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        // 左右：左右双旋
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            } else {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    if (cur == parent->_right) {
                        // 右右：左单旋
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        // 右左：右左双旋
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_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 (kot(cur->_data) > key)
                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;
};

7.2 Myset.h（完整版）

#pragma once
#include "RBTree.h"

namespace bit {
template<class K>
class set {
    // 仿函数：从数据中取出 key
    struct SetKeyOfT {
        const K& operator()(const K& key) {
            return key;
        }
    };

public:
    // 迭代器类型（从 RBTree 中取出）
    typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
    typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

    // begin/end
    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;
};

// 测试函数
void Print(const set<int>& s) {
    set<int>::const_iterator it = s.begin();
    while (it != s.end()) {
        // *it += 2; // 错误！不能修改
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

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
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
    Print(s);
}
}

7.3 Mymap.h（完整版）

#pragma once
#include "RBTree.h"

namespace bit {
template<class K, class V>
class map {
    // 仿函数：从 pair 中取出 key
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) {
            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;

    // begin/end
    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);
    }

    // operator[]
    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;
};

void test_map() {
    map<string, string> dict;
    dict.insert({"sort", "排序"});
    dict.insert({"left", "左边"});
    dict.insert({"right", "右边"});
    dict["left"] = "左边，剩余";
    dict["insert"] = "插入";
    dict["string"];

    map<string, string>::iterator it = dict.begin();
    while (it != dict.end()) {
        // it->first += 'x'; // 错误！不能修改 key
        it->second += 'x'; // 可以修改 value
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
    cout << endl;
}
}

八、总结与思考

8.1 设计亮点

1. 泛型设计：一棵红黑树通过模板参数适配 set 和 map
2. 仿函数 KeyOfT：解决了不同类型中取 key 的问题
3. 迭代器抽象：封装了中序遍历的逻辑
4. const 正确性：通过模板参数 Ref 和 Ptr 支持 const 迭代器

8.2 与 STL 源码的对比

8.3 常见问题

Q1：为什么 set 的迭代器不能修改 key？

• set 中的元素本身就是 key，修改 key 会破坏 BST 的有序性
• 实现中通过 RBTree<K, const K, SetKeyOfT> 保证存储的是 const K

Q2：为什么 map 的迭代器能修改 value 但不能修改 key？

• map 存储的是 pair<const K, V>，key 是 const 的，value 不是 const
• 修改 key 会破坏有序性，修改 value 不会影响树的组织结构

Q3：为什么要实现 const_iterator？

• const 对象只能用 const_iterator 遍历
• 明确表达只读语义，帮助编译器检查

Q4：迭代器–操作中为什么要保存_root？

• 为了处理 --end() 的情况，需要找到最右节点
• 没有_root 无法从 nullptr 找到最右节点