C++ STL 容器：基于红黑树模拟实现 map 与 set

二、红黑树的迭代器实现

为了让 map 和 set 支持遍历，我们需要封装红黑树的迭代器。迭代器本质上是对节点指针的封装，模拟指针行为。

1. 迭代器结构

我们将红黑树节点存储的内容统一抽象为 T。如果是 map，T 对应 pair<K,V>；如果是 set，T 对应 K。

template<typename T>
struct RBTreeNode {
    T _data;
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Colour _col;
    // ... 构造函数略
};

template<typename K, typename T>
class RBTree {
    typedef RBTreeNode<T> Node;
    // ... 成员变量略
};

2. 运算符重载

迭代器需要支持解引用、箭头访问、自增自减及比较操作。

• operator*：返回节点数据的引用。
• operator->：返回节点数据的地址。
• operator++/--：遵循中序遍历逻辑。若右子树存在，找右子树最左节点；否则向上寻找父节点，直到当前节点是其父节点的左孩子。

template<typename T>
struct __RBTree_iterator {
    typedef RBTreeNode<T> Node;
    typedef __RBTree_iterator<T> Self;
    Node* _node;

    __RBTree_iterator(Node* node) : _node(node) {}

    T& operator*() { return _node->_data; }
    T* operator->() { return &_node->_data; }

    bool operator!=(const Self& it) { return _node != it._node; }

    Self& operator++() {
        Node* cur = _node;
        Node* parent = cur->_parent;
        if (cur->_right) {
            Node* RightMin = cur->_right;
            while (RightMin->_left) RightMin = RightMin->_left;
            _node = RightMin;
        } else {
            while (parent && cur == parent->_right) {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    Self& operator--() {
        Node* cur = _node;
        Node* parent = cur->_parent;
        if (cur->_left) {
            Node* LeftMax = cur->_left;
            while (LeftMax->_right) LeftMax = LeftMax->_right;
            _node = LeftMax;
        } else {
            while (parent && cur == parent->_left) {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
};

三、红黑树的插入与 KeyOfT 仿函数

由于红黑树节点存储的是通用类型 T，插入时需要知道如何提取 Key 进行比较。我们引入第三个模板参数 KeyOfT，这是一个仿函数对象。

• set 场景：T 本身就是 Key，仿函数直接返回数据。
• map 场景：T 是 pair<K,V>，仿函数返回 kv.first。

这样，红黑树内部无需关心具体存储结构，只需调用 kot(data) 获取比较用的 key 即可。

template<typename K, typename T, typename KeyOfT>
class RBTree {
    // ... 省略部分成员
    bool Insert(const T& data) {
        if (_root == nullptr) {
            _root = new Node(data);
            _root->_col = BLACK;
            return true;
        }
        // ... 查找位置、插入、旋转调整逻辑
        // 关键点：使用 kot(data) 进行比较
        while (parent && parent->_col == RED) {
            // 变色与旋转逻辑...
        }
        return true;
    }
    KeyOfT kot;
};

四、map 与 set 的封装

1. Set 封装

set 将 Key 作为模板参数，红黑树存储类型也是 Key。为了防止修改 key，迭代器需特殊处理。

namespace wzx {
template<typename K>
class set {
private:
    struct SetKeyOfT {
        const K& operator()(const K& data) { return data; }
    };
public:
    typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    iterator begin() { return _t.begin(); }
    iterator end() { return _t.end(); }
    bool Insert(const K& key) { return _t.Insert(key); }
private:
    RBTree<K, K, SetKeyOfT> _t;
};
}

2. Map 封装

map 存储 pair<const K, V>。注意 pair 中的 key 必须加 const，以保证外部无法修改键值。

namespace wzx {
template<typename K, typename V>
class map {
private:
    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;
    iterator begin() { return _t.begin(); }
    iterator end() { return _t.end(); }
    bool Insert(const pair<const K, V> kv) { return _t.Insert(kv); }
private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

五、Const 正确性保障

STL 要求 set 的 key 不可修改，map 的 key 不可修改但 value 可修改。

1. Set：利用 const_iterator 转换。普通迭代器由 const_iterator 重命名而来，因此 operator* 返回 const K&，禁止修改。
2. Map：直接在 pair 类型定义中将 key 设为 const (pair<const K, V>)。这样无论通过何种迭代器访问，key 部分都是只读的。

六、进阶功能完善

1. 迭代器的 Const 版本

为了支持 const 容器和 const 迭代器，红黑树需提供 const_iterator。通过模板参数控制 operator* 返回 const T& 还是 T&。

template<typename T, typename Ptr, typename Ref>
struct __RBTree_iterator {
    // ... 成员
    Ref operator*() { return _node->_data; }
    Ptr operator->() { return &_node->_data; }
};
// 实例化
typedef __RBTree_iterator<T, T*, T&> iterator;
typedef __RBTree_iterator<T, const T*, const T&> const_iterator;

2. Insert 返回值优化

STL 的 insert 返回 pair<iterator, bool>，指示是否插入成功及位置。这需要我们在红黑树插入逻辑中保存新节点指针，并在旋转调整后返回正确的迭代器。

pair<iterator, bool> Insert(const T& data) {
    if (_root == nullptr) {
        _root = new Node(data);
        _root->_col = BLACK;
        return make_pair(iterator(_root), true);
    }
    // ... 查找过程
    // 若已存在，返回 false
    // 若不存在，保存新节点指针 newnode，执行旋转调整
    return make_pair(iterator(newnode), true);
}

3. operator[] 实现

map 的 operator[] 通常用于取值或插入。其实现依赖于 insert：

1. 调用 insert(make_pair(key, V()))。
2. 返回 pair 中迭代器指向的 second 成员引用。

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

七、测试验证

编写测试用例验证以下场景：

1. 基本插入与遍历。
2. 尝试修改 set 中的 key（编译应报错）。
3. 尝试修改 map 中的 key（编译应报错），但修改 value 允许。
4. 验证 operator[] 的自动插入与赋值功能。

通过上述步骤，我们完成了从红黑树底层到 STL 标准容器接口的完整模拟，实现了内存管理、平衡调整及类型安全的核心逻辑。