C++：对set和map的封装

将红黑树封装为泛型

我们现有如下结构的红黑树：

enum Colour
{
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode
{
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    pair<K, V> _kv;
    Colour _col;

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

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:

private:
    Node* _root = nullptr;
};

这颗红黑树有一个问题，在于它的节点，存储的值是pair<K, V> _kv;，也就是键值对的形式来存储数据。但是在STL中，set是只存储key值的，只有map存储键值对。如果我们要使得红黑树可以同时作为map和set的底层，那么我们就要想办法让这个红黑树的节点可以存储多种类型的数据。也就是让节点RBTreeNode内部存储泛型：

template<class T>
struct RBTreeNode
{
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Colour _col;
    T _data;

    RBTreeNode(const T& data)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _data(data)
        , _col(RED)
    {}
};

我们把原先的模板template<class K, class V>换成了template<class T>，并把pair<K, V> _kv;改为了T _data;，此时我们存储的数据就不一定是键值对的格式了。

当我们需要存储键值对，那么T就是pair<K, V>
当我们只存储key值，那么T就是K 

相应的，我们的RBTree主体也要修改一下：

template<class T>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:

private:
    Node* _root = nullptr;
};

mySet.h：

template<class K>
class set
{
public:
private:
    RBTree<const K> _t;
};

myMap.h：

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

---

Find接口

到此为止，我们仅完成了基本框架的搭建，接下来我们看看红黑树的Find接口：

Node* Find(const K& key)
{
    Node* cur = _root;

    while (cur)
    {
        if (cur->_kv.first < key)
            cur = cur->_right;
        else if (cur->_kv.first > key)
            cur = cur->_left;
        else
            return cur;
    }

    return nullptr;
}

1. 我们已经把模板从template<class K, class V>换成了template<class T>，此时已经没有K这个类型了，我们在给Find传参的时候，不可以直接传const K& key

 但是我们既然要在红黑树中查找，一定是要查key的，也就是说，我们不可以遗漏K这个类型，因此我们的模板参数要再加一个K，变成：template<class K, class T>。前面的K用于传入key的类型，后面的T用于传入红黑树存储的数据类型。

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

private:
    Node* _root = nullptr;
};

2.cur->_kv.first这个过程是有问题的，其意图通过找到key值，然后比较当前节点与查找节点的大小，来决定下一步去左子树还是右子树找节点。但是我们对RBTreeNode改造后，其内部存储的已经不是_kv了，而是_data，对于set而言，这个_data是没有first这个成员的，因此我们不能直接通过_kv.first这种方式来访问key。

这个问题的关键在于，我们想要拿到红黑树节点中的key值，但是对于map而言，这个key是_data中的成员变量first；而对于set而言，这个key就是_data。

也就是map和set取用key值的方式不同，我们无法统一处理。

为了解决这个问题，我们就要想办法，用统一的方式从_data中获得map和set的key。此时可以在红黑树的外部写仿函数，然后在仿函数的内部返回key值。对于红黑树而言，不论是什么类型，只需要向仿函数传入_data，然后接受返回值就可以拿到key。

template<class K, class T, class keyOfT>//keyOfT仿函数，取出T对象中的key
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
private:
    Node* _root = nullptr;
};

接着就是set的仿函数：

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

map的仿函数：

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

然后我们再对Find接口进行改造，把所有需要取用key的地方都改用仿函数：

bool Find(const K& key)
{
    keyOfT kot;
    Node* cur = _root;

    while (cur)
    {
        if (kot(cur->_data) < key)
            cur = cur->_right;
        else if (kot(cur->_data) > key)
            cur = cur->_left;
        else
            return true;
    }

    return false;
}

其中kot就是仿函数keyOfT 实例化出的对象。 

---

迭代器

先搭建出一个迭代器iterator的基本框架：

template<class T, class Ptr, class Ref>
struct RBTreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef RBTreeIterator<T, Ptr, Ref> Self;

    Node* _node;

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

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

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

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

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

迭代器移动的情况：

如果迭代器当前节点的右子树不为空，遍历右子树（找到右子树的最左节点）
如果迭代器当前节点的右子树为空，向上找前一个节点是当前节点的左子树的节点

 代码如下：

Self& operator++()
{
    if (_node->_right)//右不为空，找右子树最左节点
    {
        Node* subLeft = _node->_right;

        while (subLeft->_left)
        {
            subLeft = subLeft->_left;
        }

        _node = subLeft;
    }
    else//右为空
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_right)
        {
            cur = parent;
            parent = cur->_parent;
        }

        _node = parent;//parent前一个节点cur是其左子树
    }

    return *this;
}

operator--同理，只是相反的：

如果迭代器当前节点的左子树不为空，遍历左子树（找到左子树的最右节点）
如果迭代器当前节点的左子树为空，向上找前一个节点是当前节点的右子树的节点

Self& operator--()
{
    if (_node->_left)//左不为空
    {
        Node* subRight = _node->_left;

        while (subRight->_right)
        {
            subRight = subRight->_right;
        }

        _node = subRight;
    }
    else//左为空
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_left)
        {
            cur = parent;
            parent = cur->_parent;
        }

        _node = parent;//第一个为cur右子树的祖先
    }

    return *this;
}

首先定义出iterator和const_iterator：

typedef RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeIterator<T, const T*, const T&> const_iterator;

直接拿空指针构造end接口：

iterator end()
{
    return iterator(nullptr);
}

begin接口不是直接拿_root去构造iterator，中序遍历的第一个节点是整棵树的最左侧节点，所以要先找到最左侧节点，再构造：

iterator begin()
{
    Node* subLeft = _root;
    while (subLeft && subLeft->_left)
    {
        subLeft = subLeft->_left;
    }

    return iterator(subLeft);
}

封装出map和set的迭代器，直接复用RBTree的迭代器接口即可 

typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, const 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();
}

有一个注意点，在typedef的时候，由于我们的RBTree是一个模板，我们到模板的域中访问了变量。编译器无法区分模板中const_iterator的是变量还是类型，所以编译器会默认把它视为一个变量。如果它是一个类型，那么我们要明确告诉编译器，即通过typename 关键词。不然const_iterator会被识别为一个变量，而不是一个类型。

---

insert接口

在map和set中，insert的返回值比较特殊，其会返回pair<iterator, bool>

如果插入值data原先存在，此时iterator指向原先的data节点，bool值返回false表示插入失败
如果插入值data原先不存在，此时iterator指向新插入的data节点，bool值返回true表示插入成功

如果插入成功：

return  make_pair(iterator(newNode), true);

如果插入失败：

return make_pair(iterator(cur), false);

---

map的operator[]接口

map还重载了[]，这个重载比较复杂，但是非常有用，我们先看到声明：

V& operator[] (const K& key);

其接收一个K类型的参数，也就是接受一个key，然后返回一个V&，也就是一个value的引用。其功能为：接受一个key值，然后返回这个key对应的value的引用。

---

总代码展示

RBTree.h：

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

enum Colour
{
    RED,
    BLACK
};

template<class T>
struct RBTreeNode
{
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Colour _col;
    T _data;

    RBTreeNode(const T& data)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _data(data)
        , _col(RED)
    {}
};

template<class T, class Ptr, class Ref>
struct RBTreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef RBTreeIterator<T, Ptr, Ref> Self;

    Node* _node;

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

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

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

    Self& operator++()
    {
        if (_node->_right)//右不为空
        {
            Node* subLeft = _node->_right;

            while (subLeft->_left)
            {
                subLeft = subLeft->_left;
            }

            _node = subLeft;
        }
        else//右为空
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right)
            {
                cur = parent;
                parent = cur->_parent;
            }

            _node = parent;//第一个为cur左子树的祖先
        }

        return *this;
    }

    Self& operator--()
    {
        if (_node->_left)//左不为空
        {
            Node* subRight = _node->_left;

            while (subRight->_right)
            {
                subRight = subRight->_right;
            }

            _node = subRight;
        }
        else//左为空
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = cur->_parent;
            }

            _node = parent;//第一个为cur右子树的祖先
        }

        return *this;
    }

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

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

template<class K, class T, class keyOfT>//keyOfT仿函数，取出T对象中的key
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    typedef RBTreeIterator<T, T*, T&> iterator;
    typedef RBTreeIterator<T, const T*, const T&> const_iterator;



    iterator begin()
    {
        Node* subLeft = _root;
        while (subLeft && subLeft->_left)
        {
            subLeft = subLeft->_left;
        }

        return iterator(subLeft);
    }

    iterator end()
    {
        return iterator(nullptr);
    }

    const_iterator begin() const
    {
        Node* subLeft = _root;
        while (subLeft && subLeft->_left)
        {
            subLeft = subLeft->_left;
        }

        return const_iterator(subLeft);
    }

    const_iterator end() const
    {
        return const_iterator(nullptr);
    }

    pair<iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;//保持根为黑节点
            return make_pair(iterator(_root), true);
        }

        Node* cur = _root;
        Node* parent = nullptr;

        keyOfT kot;
        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 make_pair(iterator(cur), false);
            }
        }

        cur = new Node(data);

        if (kot(parent->_data) > kot(data))
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;
        Node* newNode = cur;

        while (parent && parent->_col == RED)//只有parent为红，才更新 (parent可能不存在)
        {
            Node* grandfather = parent->_parent;
            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;

                //uncle存在且为红节点
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//uncle不存在或为黑节点 (旋转)
                {
                    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;

                //uncle存在且为红节点
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//uncle不存在或为黑节点 (旋转)
                {
                    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;//在循环内部不判断root情况，统一处理

        return  make_pair(iterator(newNode), true);
    }
    
    //左单旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL)
            subRL->_parent = parent;

        subR->_left = parent;
        Node* ppNode = parent->_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;
        }
    }

    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;

        subL->_right = parent;
        Node* ppNode = parent->_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;
        }
    }

    size_t Size()
    {
        return _Size(_root);
    }

    size_t _Size(Node* root)
    {
        if (root == nullptr)
            return 0;;

        return _Size(root->_left) + _Size(root->_right) + 1;
    }

    iterator Find(const K& key)
    {
        keyOfT kot;
        Node* cur = _root;

        while (cur)
        {
            if (kot(cur->_data) < key)
                cur = cur->_right;
            else if (kot(cur->_data) > key)
                cur = cur->_left;
            else
                return iterator(cur);
        }

        return end();
    }

    //--------------------------------------------------------------------------------------------------------------

    //中序
    void InOrder()
    {
        _InOrder(_root);
        cout << "end" << endl;
    }

private:
    //中序
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_kv.first << " - ";

        _InOrder(root->_right);
    }

    Node* _root = nullptr;
};

mySet.h：

#pragma once
#include "RBTree.h"

namespace mySet
{
    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>::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);
        }

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

    private:
        RBTree<K, const K, SetKeyOfT> _t;
    };
}

myMap.h：

#pragma once
#include "RBTree.h"

namespace myMap
{
    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>::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 pair<K, V>& kv)
        {
            return _t.Insert(kv);
        }

        V& operator[](const K& key)
        {
            pair<K, V>& ret = insert(make_pair(key, V()));

            return ret.first->second;
        }

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

    private:
        RBTree<K, pair<const K, V>, MapKeyOfT> _t;
    };
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

原文地址：https://blog.csdn.net/m0_61088872/article/details/140369766

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！