【c++丨STL】基于红黑树模拟实现set和map（附源码）-阿里云开发者社区

前言

之前我们学习了红黑树以及STL中的set和map两种容器，本篇文章，基于之前实现的红黑树代码，我们将仿照SGI STL的实现方式，尝试对同一棵红黑树进行封装和一系列适配修改，模拟实现set和map两种容器。

建议大家掌握了红黑树以及set和map的使用之后，再来阅读本文，否则部分内容可能较难理解。

一、红黑树源码

之前实现的红黑树源代码如下：

#include <iostream>
#include <utility>
using namespace std;

enum Color
{
   
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode
{
   
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Color _col;
    RBTreeNode(const pair<K, V>& kv)
        :_kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _col(RED)
    {
   }
};

template<class K, class V>
class RBTree
{
   
    typedef RBTreeNode<K, V> Node;
public:
    RBTree() = default;
    RBTree(const RBTree<K, V>& t)
    {
   
        _root = _Copy(t._root);
    }
    ~RBTree()
    {
   
        _Destroy(_root);
    }
    bool Insert(const pair<K, V>& kv)
    {
   
        if (_root == nullptr)
        {
   
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
   
            if (kv.first < cur->_kv.first)
            {
   
                parent = cur;
                cur = cur->_left;
            }
            else if (kv.first > cur->_kv.first)
            {
   
                parent = cur;
                cur = cur->_right;
            }
            else
            {
   
                return false;
            }
        }
        cur = new Node(kv);
        if (kv.first < parent->_kv.first)
        {
   
            parent->_left = cur;
        }
        else
        {
   
            parent->_right = 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)
                {
   
                    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 true;
    }
    Node* Find(const K& key)
    {
   
        Node* cur = _root;
        while (cur)
        {
   
            if (key < cur->_kv.first)
            {
   
                cur = cur->_left;
            }
            else if (key > cur->_kv.first)
            {
   
                cur = cur->_right;
            }
            else
            {
   
                return cur;
            }
        }
        return nullptr;
    }
private:
    void RotateR(Node* parent)
    {
   
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;
        Node* ppNode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
        if (parent == _root)
        {
   
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
   
            if (ppNode->_left == parent) ppNode->_left = subL;
            else ppNode->_right = subL;
            subL->_parent = ppNode;
        }
    }
    void RotateL(Node* parent)
    {
   
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;
        Node* ppNode = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;
        if (parent == _root)
        {
   
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
   
            if (ppNode->_left == parent) ppNode->_left = subR;
            else ppNode->_right = subR;
            subR->_parent = ppNode;
        }
    }
    Node* _Copy(Node* root, Node* parent = nullptr)
    {
   
        if (root == nullptr) return nullptr;
        Node* NewRoot = new Node(root->_kv);
        NewRoot->_col = root->_col;
        NewRoot->_parent = parent;
        NewRoot->_left = _Copy(root->_left, NewRoot);
        NewRoot->_right = _Copy(root->_right, NewRoot);
        return NewRoot;
    }
    void _Destroy(Node* root)
    {
   
        if (root == nullptr) return;
        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }
    Node* _root = nullptr;
};

二、set和map的模拟实现

1. 数据类型的设置

由于set元素类型是键(key)，而map是键值对(key_value)，它们底层的数据类型是不同的，那么如何通过封装同一棵红黑树实现两种不同数据类型的容器呢？解决方法：通过传入不同的模板参数类型决定红黑树的数据类型。

template<class K>
class Set
{
   
public:
private:
    RBTree<K, const K> _rbtree;
};

template<class K, class V>
class Map
{
   
public:
private:
    RBTree<K, pair<const K, V>> _rbtree;
};

我们将红黑树作为set和map的成员，在红黑树的第二个模板参数处，set传入const K（加const保证K不被修改）；map传入pair，这样红黑树就能根据不同的类型实例化出不同对象，以适应set和map的不同需求。

相应地，我们需要对红黑树节点结构和红黑树的模板参数名进行修改：

template<class T>
struct RBTreeNode
{
   
    T _data;
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Color _col;
    RBTreeNode(const T& data)
        :_data(data)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _col(RED)
    {
   }
};

template<class K, class T>
class RBTree
{
   
    typedef RBTreeNode<T> Node;

如此，当我们创建set对象时，传入模板参数const K，底层红黑树接收到的参数T就是K（键），节点存放的数据类型就是K；创建map对象时，传入模板参数pair，红黑树接收到的参数T就是（键值对），节点存放的数据类型就是。

既然第二个模板参数就可以决定红黑树的数据类型，那么是否可以取消第一个模板参数呢？

其实不然。虽然set和map的数据元素类型不同，但查找或删除操作都是按键查找/删除，函数的参数必须传入K类型。如果只是实现set容器，那么第二个参数的作用就完全可以替代第一个参数；但对于map容器，则K类型的第一个模板参数无法省去。所以第一个模板参数存在的意义是为了保证查找和删除操作的参数正确性。

2. 键值比较的适配

我们都知道，set和map是关联式容器，在进行插入或查找操作时，难免要和其他元素进行比较。虽然两者的数据类型不同，但比较的对象都是键Key。

但之前我们已经对红黑树节点的数据类型进行了修改：set为K，map为。怎么使它们在进行元素比较时都按照Key值进行比较呢？解决方法：针对不同容器实现不同仿函数，对数据类型进行适配转化。

对于set，数据类型就是K，返回原值即可：

struct SetKeyOfT
{
   
    const K& operator()(const K& key)
    {
   
        return key;
    }
};

而对于map而言，获取到的数据类型是pair，需要返回其第一个成员K，用作比较。

struct MapKeyOfT
{
   
    const K& operator()(const pair<const K, V>& _kv)
    {
   
        return _kv.first;
    }
};

接下来，我们需要给红黑树新增一个模板参数KeyOfT，用于接收两种不同的仿函数：

template<class K, class T, class KeyOfT>
class RBTree

在set和map中传入各自的仿函数给第三个模板参数：

RBTree<K, const K, SetKeyOfT> _rbtree;
RBTree<K, pair<const K, V>, MapKeyOfT> _rbtree;

最后，修改红黑树的Insert和Find代码，以适配Key值比较：

（注：所有需要进行键值比较的位置都需要进行仿函数转化。）

KeyOfT _kot;//红黑树中新增一个仿函数对象便于调用

bool Insert(const T& data)
{
   
    if (_root == nullptr)
    {
   
        _root = new Node(data);
        _root->_col = BLACK;
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
   
        if(_kot(data) < _kot(cur->_data))
        {
   
            parent = cur;
            cur = cur->_left;
        }
        else if(_kot(data) > _kot(cur->_data))
        {
   
            parent = cur;
            cur = cur->_right;
        }
        else
        {
   
            return false;
        }
    }
    cur = new Node(data);
    if (_kot(data) < _kot(parent->_data))
    {
   
        parent->_left = cur;
    }
    else
    {
   
        parent->_right = 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)
            {
   
                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 true;
}

Node* Find(const K& key)
{
   
    Node* cur = _root;
    while (cur)
    {
   
        if(key < _kot(cur->_data))
        {
   
            cur = cur->_left;
        }
        else if(key > _kot(cur->_data))
        {
   
            cur = cur->_right;
        }
        else
        {
   
            return cur;
        }
    }
    return nullptr;
}

这样，尽管数据类型不同，但set和map传入各自的仿函数，然后对所有需要进行比较的data值进行适当的转化，就能保证插入和查找时进行比较的是Key值。

3. 迭代器实现

set和map的迭代器是双向迭代器，由于红黑树特殊的物理结构，我们实现迭代器的方式与list相同，也是对原生指针进行封装，然后通过重载运算符实现指针的各种行为。

为减少代码冗余，本次的迭代器实现当中，两种容器也将封装同一份迭代器代码。

迭代器类型定义如下：

template<class T, class Ref, class Ptr>
struct rbtree_iterator
{
   
    typedef RBTreeNode<T> Node;
    typedef rbtree_iterator<T, Ref, Ptr> Self;
    Node* _ptr;
    Node* _root;
};

接下来实现迭代器的各种操作接口：

迭代器的构造函数

rbtree_iterator(Node* ptr, Node* root)
    :_ptr(ptr)
    ,_root(root)
{
   }

*重载和->重载

这两种运算符重载的实现方式与list相同，返回_ptr指向data的值以及地址。

Ref operator*()
{
   
    return _ptr->_data;
}
Ptr operator->()
{
   
    return &(_ptr->_data);
}

前置++

由于set和map的正向遍历遵循二叉树的中序遍历原则，因此实现operator++时，需要找到当前节点在中序遍历中的下一个节点，然后移动指针。有两种情况需要讨论：

情况一：当前节点的右子树不为空

如图，当前节点是2时，其右子树不为空，中序需要访问的下一个节点就是3；当前节点是4时，中序的下一个节点是5；当前节点是6，中序的下一个节点就是7。所以当前节点的右子树不为空时，寻找右子树的最小值（也就是右子树的最左节点）。

情况二：当前节点的右子树为空

由图可知，当前节点的右子树为空时，下一个节点不外乎在其祖先当中。所以要让cur沿着祖先路径向上寻找。寻找过程中，若cur是其父亲的左孩子，则父亲就是下一个访问的节点；若cur已经走到根节点处，则说明已经遍历完成。

如上图所示：

当前节点是3，右子树为空，则向上寻找。3是2的右孩子，继续向上寻找。2是4的左孩子，则4是中序的下一个节点。

当前节点是9，右子树为空，向上寻找。直到找到根节点4，也没有出现左孩子，说明遍历完成。

代码实现：

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

前置--

前置--的实现逻辑与前置++基本相似（遵循 “ 反向中序遍历 ” ），但需要考虑已经遍历结束（_ptr指向空）的情况：

当_ptr指向空时，--操作需要找到前一个节点（也就是中序遍历的最后一个节点），即整颗树的最右节点。

其余实现逻辑与++操作刚好对称：

若当前节点左子树不为空，则寻找左子树最右节点。

若左子树为空，则向上寻找，直到cur是父亲的右孩子或走到根节点处。

代码实现：

Self& operator--()
{
   
    if (_ptr == nullptr)
    {
   
        Node* cur = _root;
        while (cur && cur->_right)
        {
   
            cur = cur->_right;
        }
        _ptr = cur;
    }
    else if (_ptr->_left)
    {
   
        Node* leftMax = _ptr->_left;
        while (leftMax->_right)
        {
   
            leftMax = leftMax->_right;
        }
        _ptr = leftMax;
    }
    else
    {
   
        Node* cur = _ptr;
        Node* parent = cur->_parent;
        while(parent && parent->_left == cur)
        {
   
            cur = parent;
            parent = parent->_parent;
        }
        _ptr = parent;
    }
    return *this;
}

后置++和--

后置++/--直接调用前置++/--，然后记录中间变量即可。

Self operator++(int)
{
   
    Self tmp(*this);
    ++(*this);
    return tmp;
}
Self operator--(int)
{
   
    Self tmp(*this);
    --(*this);
    return tmp;
}

operator!=

判断它们的_ptr指针是否相等。

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

迭代器全部实现代码：

template<class T, class Ref, class Ptr>
struct rbtree_iterator
{
   
    typedef RBTreeNode<T> Node;
    typedef rbtree_iterator<T, Ref, Ptr> Self;
    Node* _ptr;
    Node* _root;
    rbtree_iterator(Node* ptr, Node* root)
        :_ptr(ptr)
        ,_root(root)
    {
   }
    Ref operator*()
    {
   
        return _ptr->_data;
    }
    Ptr operator->()
    {
   
        return &(_ptr->_data);
    }
    Self& operator++()
    {
   
        if (_ptr->_right)
        {
   
            Node* rightMin = _ptr->_right;
            while (rightMin->_left)
            {
   
                rightMin = rightMin->_left;
            }
            _ptr = rightMin;
        }
        else
        {
   
            Node* cur = _ptr;
            Node* parent = cur->_parent;
            while (parent && parent->_right == cur)
            {
   
                cur = parent;
                parent = parent->_parent;
            }
            _ptr = parent;
        }
        return *this;
    }
    Self& operator--()
    {
   
        if (_ptr == nullptr)
        {
   
            Node* cur = _root;
            while (cur && cur->_right)
            {
   
                cur = cur->_right;
            }
            _ptr = cur;
        }
        else if (_ptr->_left)
        {
   
            Node* leftMax = _ptr->_left;
            while (leftMax->_right)
            {
   
                leftMax = leftMax->_right;
            }
            _ptr = leftMax;
        }
        else
        {
   
            Node* cur = _ptr;
            Node* parent = cur->_parent;
            while(parent && parent->_left == cur)
            {
   
                cur = parent;
                parent = parent->_parent;
            }
            _ptr = parent;
        }
        return *this;
    }
    Self operator++(int)
    {
   
        Self tmp(*this);
        ++(*this);
        return tmp;
    }
    Self operator--(int)
    {
   
        Self tmp(*this);
        --(*this);
        return tmp;
    }
    bool operator!=(const Self& it)
    {
   
        return _ptr != it._ptr;
    }
};

4. set和map迭代器接口实现和适配

首先在红黑树以及set和map内部声明迭代器类型：

typedef rbtree_iterator<T, T&, T*> Iterator;
typedef rbtree_iterator<T, const T&, const T*> ConstIterator;

typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;

注意：这里typename的作用是告诉编译器Iterator和ConstIterator是类型名，缺失会编译报错。

然后在红黑树内部实现迭代器接口：

Iterator Begin()
{
   
    Node* cur = _root;
    while (cur && cur->_left)
    {
   
        cur = cur->_left;
    }
    return Iterator(cur, _root);
}

Iterator End()
{
   
    return Iterator(nullptr, _root);
}

ConstIterator Begin() const
{
   
    Node* cur = _root;
    while (cur && cur->_left)
    {
   
        cur = cur->_left;
    }
    return ConstIterator(cur, _root);
}

ConstIterator End() const
{
   
    return ConstIterator(nullptr, _root);
}

在set和map中，对以上接口进行封装调用：

iterator begin()
{
   
    return _rbtree.Begin();
}

iterator end()
{
   
    return _rbtree.End();
}

const_iterator begin() const
{
   
    return _rbtree.Begin();
}

const_iterator end() const
{
   
    return _rbtree.End();
}

迭代器实现完成之后，我们再对Insert和Find函数的返回值进行迭代器适配修改：

pair<Iterator, bool> Insert(const T& data)
{
   
    if (_root == nullptr)
    {
   
        _root = new Node(data);
        _root->_col = BLACK;
        return {
    Iterator(_root,_root),true };
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
   
        if(_kot(data) < _kot(cur->_data))
        {
   
            parent = cur;
            cur = cur->_left;
        }
        else if(_kot(data) > _kot(cur->_data))
        {
   
            parent = cur;
            cur = cur->_right;
        }
        else
        {
   
            return {
    Iterator(cur, _root), false };
        }
    }
    cur = new Node(data);
    if (_kot(data) < _kot(parent->_data))
    {
   
        parent->_left = cur;
    }
    else
    {
   
        parent->_right = 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)
            {
   
                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 {
    Iterator(cur,_root),true };
}

Iterator Find(const K& key)
{
   
    Node* cur = _root;
    while (cur)
    {
   
        if(key < _kot(cur->_data))
        {
   
            cur = cur->_left;
        }
        else if(key > _kot(cur->_data))
        {
   
            cur = cur->_right;
        }
        else
        {
   
            return Iterator(cur, _root);
        }
    }
    return Iterator(nullptr, _root);
}

5. set和map功能实现

之前我们已经实现了封装实现了set和map的迭代器接口，最后封装Insert和Find接口，以及实现map的operator[ ]接口。

insert和find

直接对红黑树的Insert和Find函数进行封装调用即可：

pair<iterator, bool> insert(const K& key)
{
   
    return _rbtree.Insert(key);
}

iterator find(const K& key)
{
   
    return _rbtree.Find(key);
}

pair<iterator, bool> insert(const pair<K, V>& kv)
{
   
    return _rbtree.Insert(kv);
}

iterator find(const K& key)
{
   
    return _rbtree.Find(key);
}

map的operator[ ]

operator既支持元素插入，也支持修改，是因为其底层封装了insert方法，并且返回了Value值的引用。代码实现如下：

V& operator
{
   
    pair<iterator, bool> ret = insert({
    key,V() });
    return ret.first->second;
}

至此，通过对同一棵红黑树进行封装和适配，两种容器的基本功能已经实现完成。

三、测试

写一段代码测试我们实现的set和map：

void test_set()
{
   
    Set<int> s;
    s.insert(5);
    s.insert(3);
    s.insert(1);
    s.insert(7);
    s.insert(0);
    s.insert(9);
    s.insert(6);
    s.insert(4);
    for (auto& e : s)
    {
   
        cout << e << ' ';
    }
    cout << endl;
}

运行结果：

void test_map()
{
   
    string arr[] = {
    "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    Map<string, int> m;
    for (auto& str : arr)
    {
   
        m[str]++;
    }
    for (auto& kv : m)
    {
   
        cout << kv.first << ':' << kv.second << endl;
    }
}

运行结果：

四、程序全部代码

set和map实现相关的全部代码如下：

RBTree.h

#include <iostream>
#include <utility>
using namespace std;

#pragma once
enum Color
{
   
    RED,
    BLACK
};

template<class T>
struct RBTreeNode
{
   
    T _data;
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Color _col;
    RBTreeNode(const T& data)
        :_data(data)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _col(RED)
    {
   }
};

template<class T, class Ref, class Ptr>
struct rbtree_iterator
{
   
    typedef RBTreeNode<T> Node;
    typedef rbtree_iterator<T, Ref, Ptr> Self;
    Node* _ptr;
    Node* _root;
    rbtree_iterator(Node* ptr, Node* root)
        :_ptr(ptr)
        , _root(root)
    {
   }
    Ref operator*()
    {
   
        return _ptr->_data;
    }
    Ptr operator->()
    {
   
        return &(_ptr->_data);
    }
    Self& operator++()
    {
   
        if (_ptr->_right)
        {
   
            Node* rightMin = _ptr->_right;
            while (rightMin->_left)
            {
   
                rightMin = rightMin->_left;
            }
            _ptr = rightMin;
        }
        else
        {
   
            Node* cur = _ptr;
            Node* parent = cur->_parent;
            while (parent && parent->_right == cur)
            {
   
                cur = parent;
                parent = parent->_parent;
            }
            _ptr = parent;
        }
        return *this;
    }
    Self& operator--()
    {
   
        if (_ptr == nullptr)
        {
   
            Node* cur = _root;
            while (cur && cur->_right)
            {
   
                cur = cur->_right;
            }
            _ptr = cur;
        }
        else if (_ptr->_left)
        {
   
            Node* leftMax = _ptr->_left;
            while (leftMax->_right)
            {
   
                leftMax = leftMax->_right;
            }
            _ptr = leftMax;
        }
        else
        {
   
            Node* cur = _ptr;
            Node* parent = cur->_parent;
            while (parent && parent->_left == cur)
            {
   
                cur = parent;
                parent = parent->_parent;
            }
            _ptr = parent;
        }
        return *this;
    }
    Self operator++(int)
    {
   
        Self tmp(*this);
        ++(*this);
        return tmp;
    }
    Self operator--(int)
    {
   
        Self tmp(*this);
        --(*this);
        return tmp;
    }
    bool operator!=(const Self& it)
    {
   
        return _ptr != it._ptr;
    }
};

template<class K, class T, class KeyOfT>
class RBTree
{
   
    typedef RBTreeNode<T> Node;
public:
    typedef rbtree_iterator<T, T&, T*> Iterator;
    typedef rbtree_iterator<T, const T&, const T*> ConstIterator;
    RBTree() = default;
    RBTree(const RBTree<K, T, KeyOfT>& t)
    {
   
        _root = _Copy(t._root);
    }
    ~RBTree()
    {
   
        _Destroy(_root);
    }
    Iterator Begin()
    {
   
        Node* cur = _root;
        while (cur && cur->_left)
        {
   
            cur = cur->_left;
        }
        return Iterator(cur, _root);
    }
    Iterator End()
    {
   
        return Iterator(nullptr, _root);
    }
    ConstIterator Begin() const
    {
   
        Node* cur = _root;
        while (cur && cur->_left)
        {
   
            cur = cur->_left;
        }
        return ConstIterator(cur, _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 {
    Iterator(_root,_root),true };
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
   
            if (_kot(data) < _kot(cur->_data))
            {
   
                parent = cur;
                cur = cur->_left;
            }
            else if (_kot(data) > _kot(cur->_data))
            {
   
                parent = cur;
                cur = cur->_right;
            }
            else
            {
   
                return {
    Iterator(cur, _root), false };
            }
        }
        cur = new Node(data);
        if (_kot(data) < _kot(parent->_data))
        {
   
            parent->_left = cur;
        }
        else
        {
   
            parent->_right = 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)
                {
   
                    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 {
    Iterator(cur,_root),true };
    }
    Iterator Find(const K& key)
    {
   
        Node* cur = _root;
        while (cur)
        {
   
            if (key < _kot(cur->_data))
            {
   
                cur = cur->_left;
            }
            else if (key > _kot(cur->_data))
            {
   
                cur = cur->_right;
            }
            else
            {
   
                return Iterator(cur, _root);
            }
        }
        return Iterator(nullptr, _root);
    }
private:
    void RotateR(Node* parent)
    {
   
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;
        Node* ppNode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
        if (parent == _root)
        {
   
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
   
            if (ppNode->_left == parent) ppNode->_left = subL;
            else ppNode->_right = subL;
            subL->_parent = ppNode;
        }
    }
    void RotateL(Node* parent)
    {
   
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;
        Node* ppNode = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;
        if (parent == _root)
        {
   
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
   
            if (ppNode->_left == parent) ppNode->_left = subR;
            else ppNode->_right = subR;
            subR->_parent = ppNode;
        }
    }
    Node* _Copy(Node* root, Node* parent = nullptr)
    {
   
        if (root == nullptr) return nullptr;
        Node* NewRoot = new Node(root->_kv);
        NewRoot->_col = root->_col;
        NewRoot->_parent = parent;
        NewRoot->_left = _Copy(root->_left, NewRoot);
        NewRoot->_right = _Copy(root->_right, NewRoot);
        return NewRoot;
    }
    void _Destroy(Node* root)
    {
   
        if (root == nullptr) return;
        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }
    Node* _root = nullptr;
    KeyOfT _kot;
};

Set.h

#include "RBTree.h"
#pragma once
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 _rbtree.Begin();
    }
    iterator end()
    {
   
        return _rbtree.End();
    }
    const_iterator begin() const
    {
   
        return _rbtree.Begin();
    }
    const_iterator end() const
    {
   
        return _rbtree.End();
    }
    pair<iterator, bool> insert(const K& key)
    {
   
        return _rbtree.Insert(key);
    }
    iterator find(const K& key)
    {
   
        return _rbtree.Find(key);
    }
private:
    RBTree<K, const K, SetKeyOfT> _rbtree;
};

Map.h

#include "RBTree.h"
#pragma once
template<class K, class V>
class Map
{
   
    struct MapKeyOfT
    {
   
        const K& operator()(const pair<const 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 _rbtree.Begin();
    }
    iterator end()
    {
   
        return _rbtree.End();
    }
    const_iterator begin() const
    {
   
        return _rbtree.Begin();
    }
    const_iterator end() const
    {
   
        return _rbtree.End();
    }
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
   
        return _rbtree.Insert(kv);
    }
    iterator find(const K& key)
    {
   
        return _rbtree.Find(key);
    }
    V& operator
    {
   
        pair<iterator, bool> ret = insert({
    key,V() });
        return ret.first->second;
    }
private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _rbtree;
};

总结

本篇文章我们基于之前实现的红黑树模拟实现了set和map两种容器。不难发现，加入了模板和仿函数之后，两种容器能共用同一份红黑树代码，大大减少了代码冗余。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

【c++丨STL】基于红黑树模拟实现set和map（附源码）

前言

一、红黑树源码

二、set和map的模拟实现

1. 数据类型的设置

2. 键值比较的适配

3. 迭代器实现

迭代器的构造函数

*重载和->重载

前置++

前置--

后置++和--

operator!=

4. set和map迭代器接口实现和适配

5. set和map功能实现

insert和find

map的operator[ ]

三、测试

四、程序全部代码

总结

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【c++丨STL】基于红黑树模拟实现set和map（附源码）

前言

一、红黑树源码

二、set和map的模拟实现

1. 数据类型的设置

2. 键值比较的适配

3. 迭代器实现

迭代器的构造函数

*重载和->重载

前置++

前置--

后置++和--

operator!=

4. set和map迭代器接口实现和适配

5. set和map功能实现

insert和find

map的operator[ ]

三、测试

四、程序全部代码

总结

热门文章

最新文章

相关课程

相关电子书