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

二、红黑树的迭代器

为了实现 map/set 的遍历，我们需要模拟实现红黑树的迭代器。迭代器封装了节点的指针，模拟指针行为。

1. 改进红黑树模板参数为 template<typename K, typename T>，其中 K 表示 Key，T 表示节点存储的实际类型（Type）。
2. 节点结构体中增加 _data 成员变量存储 T 类型数据。
3. 迭代器类模板 __RBTree_iterator 封装节点指针 _node，重载 operator*、operator->、operator++、operator-- 等操作符。
4. operator++ 逻辑：若右子树存在，则找右子树的最左节点；否则向上寻找父节点，直到当前节点是其父节点的左孩子。
5. operator-- 逻辑：若左子树存在，则找左子树的最右节点；否则向上寻找父节点，直到当前节点是其父节点的右孩子。

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

template<typename T,typename Ptr,typename Ref>
struct __RBTree_iterator {
    typedef RBTreeNode<T> Node;
    typedef __RBTree_iterator<T, Ptr, Ref> Self;
    typedef __RBTree_iterator<T, T*, T&> Iterator;
    Node* _node;

    __RBTree_iterator(Node* root):_node(root){}
    __RBTree_iterator(const Iterator& it):_node(it._node){}

    Ref operator*(){ return _node->_data; }
    Ptr 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;
    }
};

三、红黑树的插入

插入时需要找到合适的位置。由于红黑树节点存储的是 T 类型，而我们需要根据 Key 进行比较，因此引入 KeyOfT 仿函数。

1. KeyOfT 是一个类模板，重载 operator()，用于从存储的数据中提取 Key。
2. 插入时利用 kot(data) 获取 Key 进行比较，从而适配 map 和 set 的不同存储结构。
3. 保持原有的旋转和变色逻辑不变，确保红黑树性质。

template<typename K,typename T,typename KeyOfT>
class RBTree {
    typedef RBTreeNode<T> Node;
    // ... 其他成员
    KeyOfT kot;
    
    bool Insert(const T& data) {
        if(_root == nullptr) {
            _root = new Node(data);
            _root->_col = BLACK;
            return true;
        }
        // ... 查找位置及插入逻辑
        // 旋转与变色逻辑保持不变
        return true;
    }
};

四、map/set 的封装

set 的封装

1. 命名空间避免冲突，模板参数仅需 K。
2. 实现 SetKeyOfT 仿函数，直接返回 data。
3. 迭代器需添加 typename 关键字以告知编译器这是类型而非变量。
4. 注意 Set 的 key 不可修改，因此迭代器返回 const 引用。

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

map 的封装

1. 模板参数 K, V。
2. 实现 MapKeyOfT 仿函数，返回 kv.first。
3. 存储类型为 pair<const K, V>，确保 key 不可变。

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

五、测试

编写测试代码验证基本功能，包括插入、遍历以及 key/value 的可修改性检查。

#include<iostream>
#include"MyMap.h"
#include"MySet.h"
using namespace std;

int main() {
    wzx::set<int> s;
    s.Insert(5); s.Insert(2); s.Insert(9); s.Insert(1);
    wzx::set<int>::iterator it = s.begin();
    while(it != s.end()) {
        cout << *it << ' ';
        ++it;
    }
    cout << endl;

    wzx::map<int,int> m;
    m.Insert(make_pair(3,3)); m.Insert(make_pair(1,1));
    wzx::map<int,int>::iterator mit = m.begin();
    while(mit != m.end()) {
        cout << mit->first << ':' << mit->second << endl;
        ++mit;
    }
    return 0;
}

六、学习 STL 库中的实现

set 如何保证 key 不被修改

STL 中 set 的普通迭代器实际上是由 const 迭代器重命名而来的。这意味着即使使用普通迭代器访问，也无法修改 key 的值。

map 如何保证 key 不被修改

map 中通过将 pair 的 key 成员定义为 const K，即 pair<const K, V>。这样在编译期就限制了 key 的修改，同时允许 value 被修改。

八、set 的改进

红黑树的 const 迭代器

通过模板参数控制 operator* 返回引用的类型。const 迭代器返回 const T&，普通迭代器返回 T&。

template<typename T,typename Ptr,typename Ref>
struct __RBTree_iterator {
    // ... 成员
    typedef __RBTree_iterator<T, T*, T&> iterator;
    typedef __RBTree_iterator<T,const T*,const T&> const_iterator;
};

改进 set

将 set 的 iterator 定义为 const_iterator，并实现 const 版本的 begin/end。

namespace wzx {
template<typename K>
class set {
public:
    typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
    typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
    const_iterator begin() const { return _t.begin(); }
    const_iterator end() const { return _t.end(); }
    // ... 其他成员
};
}

九、map 的改进

1. 存储类型改为 pair<const K, V>。
2. 添加 const 迭代器支持。
3. 实现 operator[]，内部调用 insert，返回 value 引用。

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

十、完善 set 的 Insert

修改 Insert 返回值以匹配 STL 标准，返回 pair<iterator,bool>。由于 set 的 iterator 底层是 const 迭代器，需处理类型转换问题，通过构造函数重载完成浅拷贝。

十一、源代码

MyMap.h

#pragma once
#include"RBTree.h"
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;
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator 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(); }
    V& operator[](const K& key) {
        pair<iterator,bool> kv = Insert(make_pair(key,V()));
        return kv.first->second;
    }
    pair<iterator,bool> Insert(const pair<const K, V> kv) { return _t.Insert(kv); }
private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

MySet.h

#pragma once
#include"RBTree.h"
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>::const_iterator iterator;
    typedef typename RBTree<K, K, SetKeyOfT>::const_iterator 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); }
private:
    RBTree<K, K, SetKeyOfT> _t;
};
}

RBTree.h

#pragma once
#include<iostream>
using namespace std;
enum Colour { RED, BLACK };

template<typename 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<typename T,typename Ptr,typename Ref>
struct __RBTree_iterator {
    typedef RBTreeNode<T> Node;
    typedef __RBTree_iterator<T, Ptr, Ref> Self;
    typedef __RBTree_iterator<T, T*, T&> Iterator;
    Node* _node;
    __RBTree_iterator(Node* root):_node(root){}
    __RBTree_iterator(const Iterator& it):_node(it._node){}
    Ref operator*(){ return _node->_data; }
    Ptr operator->(){ return&_node->_data; }
    bool operator!=(const Self& it){ return _node != it._node; }
    Self& operator++();
    Self& operator--();
};

template<typename K,typename T,typename KeyOfT>
class RBTree {
    typedef RBTreeNode<T> Node;
public:
    RBTree():_root(nullptr){}
    typedef __RBTree_iterator<T, T*, T&> iterator;
    typedef __RBTree_iterator<T,const T*,const T&> const_iterator;
    iterator begin() {
        Node* cur = _root;
        while(cur->_left) cur = cur->_left;
        return iterator(cur);
    }
    iterator end() { return iterator(nullptr); }
    const_iterator begin() const {
        Node* cur = _root;
        while(cur->_left) cur = cur->_left;
        return const_iterator(cur);
    }
    const_iterator end() const { return const_iterator(nullptr); }
    KeyOfT kot;
    pair<iterator,bool> Insert(const T& data) {
        if(_root == nullptr) {
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root),true);
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while(cur) {
            if(kot(data)>kot(cur->_data)) { parent = cur; cur = cur->_right; }
            else if(kot(data)<kot(cur->_data)) { parent = cur; cur = cur->_left; }
            else { return make_pair(iterator(cur),false); }
        }
        cur = new Node(data);
        cur->_col = RED;
        Node* newnode = cur;
        cur->_parent = parent;
        if(kot(cur->_data)>kot(parent->_data)) parent->_right = cur;
        else parent->_left = cur;
        // 旋转与变色逻辑...
        return make_pair(iterator(newnode),true);
    }
private:
    Node* _root;
    void RotateL(Node* parent); // 左旋实现略
    void RotateR(Node* parent); // 右旋实现略
};

总结

本文详细讲解了 C++ STL 中 map 和 set 基于红黑树的模拟实现过程。从底层数据结构设计、迭代器封装、插入平衡调整到泛型封装技巧，涵盖了源码级实现的关键点。特别是针对 key 不可修改的约束机制以及 insert 接口的完善，提供了完整的参考代码，适合希望深入理解 C++ 容器源码的开发者阅读。