it编程 > 编程语言 > C/C++

C++封装红黑树实现mymap和myset完整代码

28人参与 • 2026-04-19 • C/C++

一、源码及框架分析

在 sgi-stl 30 版本中，map 和 set 的实现巧妙地复用了同一棵红黑树（rb_tree）。其核心代码主要位于 stl_tree.h、stl_map.h 和 stl_set.h 中。

1.1 框架核心代码

以下是 set 和 map 的简化定义：

// stl_set.h
template <class key, class compare = less<key>, class alloc = alloc>
class set {
public:
    typedef key key_type;
    typedef key value_type;
private:
    typedef rb_tree<key_type, value_type,
                    identity<value_type>, key_compare, alloc> rep_type;
    rep_type t; // 底层红黑树
};
// stl_map.h
template <class key, class t, class compare = less<key>, class alloc = alloc>
class map {
public:
    typedef key key_type;
    typedef t mapped_type;
    typedef pair<const key, t> value_type;
private:
    typedef rb_tree<key_type, value_type,
                    select1st<value_type>, key_compare, alloc> rep_type;
    rep_type t; // 底层红黑树
};

1.2 红黑树的泛型设计

rb_tree 通过模板参数实现泛型，使其既能用于 set（存储 key），也能用于 map（存储 pair<const key, t>）。其结点定义如下：

template <class value>
struct __rb_tree_node : public __rb_tree_node_base {
    typedef __rb_tree_node<value>* link_type;
    value value_field; // 存储的实际数据
};

rb_tree 的模板参数：

template <class key, class value, class keyofvalue, class compare, class alloc = alloc>
class rb_tree {
    // ...
};

1.3 为何需要两个模板参数key和value？

set 的两个模板参数相同，map 则不同。这是因为：

map 中 value 是 pair<const key, t>，但查找时只需传入 key 类型的值，因此两个模板参数缺一不可。

注：源码中命名风格略有混乱，set 使用 key，map 使用 key 和 t，rb_tree 又使用 key 和 value，但设计思路清晰。

二、模拟实现 map 和 set

接下来，我们将基于自己实现的红黑树，封装出 map 和 set。

2.1 实现红黑树框架，支持插入

我们首先实现一个红黑树 rbtree，它通过 keyoft 仿函数提取键值进行比较。

rbtree.h

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 k, class t, class keyoft>
class rbtree {
    typedef rbtreenode<t> node;
public:
    bool insert(const t& data) {
        if (_root == nullptr) {
            _root = new node(data);
            _root->_col = black;
            return 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 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;
        // 后续平衡处理（旋转、变色）省略，完整代码见文末
        return true;
    }
private:
    node* _root = nullptr;
};

mymap.h

namespace bit {
    template<class k, class v>
    class map {
        struct mapkeyoft {
            const k& operator()(const pair<k, v>& kv) {
                return kv.first;
            }
        };
    public:
        bool insert(const pair<k, v>& kv) {
            return _t.insert(kv);
        }
    private:
        rbtree<k, pair<k, v>, mapkeyoft> _t;
    };
}

myset.h

namespace bit {
    template<class k>
    class set {
        struct setkeyoft {
            const k& operator()(const k& key) {
                return key;
            }
        };
    public:
        bool insert(const k& key) {
            return _t.insert(key);
        }
    private:
        rbtree<k, k, setkeyoft> _t;
    };
}

2.2 支持迭代器

迭代器的核心是 operator++ 和 operator--，实现中序遍历的步进逻辑。

迭代器实现思路

迭代器代码

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) {}
    ref operator*() { return _node->_data; }
    ptr operator->() { return &_node->_data; }
    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;
        }
        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;
    }
    bool operator!=(const self& s) const { return _node != s._node; }
    bool operator==(const self& s) const { return _node == s._node; }
};

在 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;
    iterator begin() {
        node* leftmost = _root;
        while (leftmost && leftmost->_left) leftmost = leftmost->_left;
        return iterator(leftmost, _root);
    }
    iterator end() { return iterator(nullptr, _root); }
    // 同理实现 constiterator
private:
    node* _root = nullptr;
};

2.3 支持operator[]

map 的 [] 需要借助 insert 的返回值实现。因此，rbtree::insert 需返回 pair<iterator, bool>。

pair<iterator, bool> insert(const t& data) {
    // 插入逻辑，返回插入位置的迭代器及是否成功
}

然后在 map 中：

v& operator[](const k& key) {
    pair<iterator, bool> ret = insert(make_pair(key, v()));
    return ret.first->second;
}

2.4 完整代码

最终版myset.h

#include "rbtree.h"
namespace bit {
    template<class k>
    class set {
        struct setkeyoft {
            const k& operator()(const k& key) { 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;
    };
}

最终版mymap.h

#include "rbtree.h"
namespace bit {
    template<class k, class v>
    class map {
        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;
        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;
    };
}

最终版rbtree.h

完整代码请参考文末总结部分，或结合上述片段整合。核心包括：

三、总结

通过封装红黑树实现 map 和 set，我们深入理解了 stl 中容器复用的设计思想：

  1. 泛型设计：红黑树通过 value 模板参数决定存储内容，通过 keyoft 仿函数提取键值进行比较。
  2. 迭代器实现：中序遍历的步进逻辑是迭代器实现的核心，需同时处理左右子树与祖先关系。
  3. map 的 [] 实现：依赖于 insert 的返回值，简洁高效。
  4. 权限控制：set 的迭代器不允许修改键值，通过将 value 模板参数设为 const k 实现；map 则通过 pair<const k, v> 保护键不被修改。

这种复用方式不仅减少了代码量，还体现了面向对象与泛型编程的强大结合。

到此这篇关于c++封装红黑树实现mymap和myset完整代码的文章就介绍到这了,更多相关封装红黑树mymap和myset内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！

赞 (0)

您想发表意见！！点此发布评论

推荐阅读

C++17新特性编译期 if 语句 (if constexpr)详解

04-17

C 语言的fread 与 C++ 的 ifstream::read区别及设计理由

04-17

WPF通过 WM_COPYDATA 实现与Qt的进程间通信

04-21

C语言排序算法的几种实现过程

04-16

C语言之整数存储底层逻辑用法解读

04-22
从零实现一个轻量级C++线程池

从零实现一个轻量级C++线程池

04-16

猜你喜欢

版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站仅提供信息存储服务，不拥有所有权，不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 2386932994@qq.com 举报，一经查实将立刻删除。

发表评论