C++封裝紅黑樹實現(xiàn)mymap和myset完整代碼

更新時間：2026年04月19日 09:51:54 作者：鳳年徐

紅黑樹作為一種自平衡的二叉搜索樹,是C++標準庫中map和set容器的底層實現(xiàn),下面這篇文章主要介紹了C++封裝紅黑樹實現(xiàn)mymap和myset的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

一、源碼及框架分析

在 SGI-STL 30 版本中，map 和 set 的實現(xiàn)巧妙地復用了同一棵紅黑樹（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 通過模板參數(shù)實現(xiàn)泛型，使其既能用于 set（存儲 Key），也能用于 map（存儲 pair<const Key, T>）。其結(jié)點定義如下：

template <class Value>
struct __rb_tree_node : public __rb_tree_node_base {
    typedef __rb_tree_node<Value>* link_type;
    Value value_field; // 存儲的實際數(shù)據(jù)
};

rb_tree 的模板參數(shù)：

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
    // ...
};

Key：鍵的類型，用于 find、erase 等接口的參數(shù)類型。
Value：結(jié)點中存儲的數(shù)據(jù)類型，在 set 中為 Key，在 map 中為 pair<const Key, T>。
KeyOfValue：仿函數(shù)，用于從 Value 中提取 Key，因為紅黑樹在比較時只比較鍵。

1.3 為何需要兩個模板參數(shù)Key和Value？

set 的兩個模板參數(shù)相同，map 則不同。這是因為：

Value 決定了結(jié)點存儲的內(nèi)容。
Key 決定了 find、erase 等函數(shù)接受的參數(shù)類型。

map 中 Value 是 pair<const Key, T>，但查找時只需傳入 Key 類型的值，因此兩個模板參數(shù)缺一不可。

注：源碼中命名風格略有混亂，set 使用 Key，map 使用 Key 和 T，rb_tree 又使用 Key 和 Value，但設計思路清晰。

二、模擬實現(xiàn) map 和 set

接下來，我們將基于自己實現(xiàn)的紅黑樹，封裝出 map 和 set。

2.1 實現(xiàn)紅黑樹框架，支持插入

我們首先實現(xiàn)一個紅黑樹 RBTree，它通過 KeyOfT 仿函數(shù)提取鍵值進行比較。

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;
        // 后續(xù)平衡處理（旋轉(zhuǎn)、變色）省略，完整代碼見文末
        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--，實現(xiàn)中序遍歷的步進邏輯。

迭代器實現(xiàn)思路

begin()：返回中序第一個結(jié)點（最左結(jié)點）。
end()：返回 nullptr（或源碼中的哨兵頭結(jié)點）。
operator++()：
- 若右子樹非空，找右子樹的最左結(jié)點。
- 若右子樹為空，向上找第一個“當前結(jié)點是左孩子”的祖先結(jié)點。
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); }
    // 同理實現(xiàn) ConstIterator
private:
    Node* _root = nullptr;
};

2.3 支持operator[]

map 的 [] 需要借助 insert 的返回值實現(xiàn)。因此，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

完整代碼請參考文末總結(jié)部分，或結(jié)合上述片段整合。核心包括：

結(jié)點定義
插入與平衡（旋轉(zhuǎn)、變色）
迭代器實現(xiàn)
Find、Begin、End 等接口

三、總結(jié)

通過封裝紅黑樹實現(xiàn) map 和 set，我們深入理解了 STL 中容器復用的設計思想：

泛型設計：紅黑樹通過 Value 模板參數(shù)決定存儲內(nèi)容，通過 KeyOfT 仿函數(shù)提取鍵值進行比較。
迭代器實現(xiàn)：中序遍歷的步進邏輯是迭代器實現(xiàn)的核心，需同時處理左右子樹與祖先關(guān)系。
map 的 [] 實現(xiàn)：依賴于 insert 的返回值，簡潔高效。
權(quán)限控制：set 的迭代器不允許修改鍵值，通過將 Value 模板參數(shù)設為 const K 實現(xiàn)；map 則通過 pair<const K, V> 保護鍵不被修改。

這種復用方式不僅減少了代碼量，還體現(xiàn)了面向?qū)ο笈c泛型編程的強大結(jié)合。

到此這篇關(guān)于C++封裝紅黑樹實現(xiàn)mymap和myset完整代碼的文章就介紹到這了,更多相關(guān)封裝紅黑樹mymap和myset內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

C++封裝紅黑樹實現(xiàn)mymap和myset完整代碼

目錄

一、源碼及框架分析

1.1 框架核心代碼

1.2 紅黑樹的泛型設計

1.3 為何需要兩個模板參數(shù)Key和Value？

二、模擬實現(xiàn) map 和 set

2.1 實現(xiàn)紅黑樹框架，支持插入

RBTree.h

Mymap.h

Myset.h

2.2 支持迭代器

迭代器實現(xiàn)思路

迭代器代碼

在 RBTree 中集成迭代器

2.3 支持operator[]

2.4 完整代碼

最終版Myset.h

最終版Mymap.h

最終版RBTree.h

三、總結(jié)

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

C++封裝紅黑樹實現(xiàn)mymap和myset完整代碼

目錄

一、源碼及框架分析

1.1 框架核心代碼

1.2 紅黑樹的泛型設計

1.3 為何需要兩個模板參數(shù)Key和Value？

二、模擬實現(xiàn) map 和 set

2.1 實現(xiàn)紅黑樹框架，支持插入

RBTree.h

Mymap.h

Myset.h

2.2 支持迭代器

迭代器實現(xiàn)思路

迭代器代碼

在 RBTree 中集成迭代器

2.3 支持operator[]

2.4 完整代碼

最終版Myset.h

最終版Mymap.h

最終版RBTree.h

三、總結(jié)

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

一、源碼及框架分析

1.3 為何需要兩個模板參數(shù)Key和Value？

二、模擬實現(xiàn) map 和 set

2.1 實現(xiàn)紅黑樹框架，支持插入