• [C++](21)set和map的模拟实现

    文章目录

    改造红黑树

    上一章我们已经实现了一个简易的红黑树

    本章在其基础上封装 set 和 map

    • 将 RBTreeNode 的模板参数改成 class T，表示存放数据的类型

    • 将 Rbtree 的模板参数改成 class K, class T，T 表示红黑树的每个结点存放的数据的类型，K 单独表示键值类型。

    • set 存放的是 K 类型数据，map 存放的 pair 类型数据。查找时，set 的 K 类型可以直接用来比较，而 map 的 pair 虽然也支持比较，但是比较方式不是我们需要的。

    库中 pair 的 < 运算符重载，先比较 first，first 相同则比较 second：

    template <class T1, class T2>
  bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }

    • 1
    • 2
    • 3

    但是我们只需要比较 first，pair 的比较不符合我们的要求。

    • 所以需要仿函数 KeyOfT，set 和 map 分别实现取出自己的 K。
    • 另外 insert 返回一个键值对，与库统一
    enum Colour
{
	RED,
	BLACK
};

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

	Colour _col;

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

// T决定红黑树存什么类型的数据
// set RBTree
// map RBTree>
// KeyOfT 支持取出T对象中key的仿函数
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
    pair<iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root), 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 make_pair(iterator(cur), 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;

        // 有父亲，且父亲为红才处理
        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 make_pair(iterator(newnode), true);
    }

private:

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL) subRL->_parent = parent; // subRL有可能是空树，需要if判断

        Node* ppNode = parent->_parent; // 提前记录祖先，后面用来连接新的parent
        subR->_left = parent;
        parent->_parent = subR;

        if (parent == _root) // 如果parent就是根结点，那么新的根是subR
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else // 否则需要祖先来连接新的parent(即subR)，注意判断左右
        {
            if (parent == ppNode->_left)
            {
                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;

        Node* ppNode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (parent == ppNode->_left)
            {
                ppNode->_left = subL;
            }
            else
            {
                ppNode->_right = subL;
            }
            subL->_parent = ppNode;
        }
    }

private:
	Node* _root;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209

    set 实现自己的仿函数，只需要取出key，顺便实现插入

    template<class K>
class Set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	pair<iterator, bool> insert(const K& key)
	{
		pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
		return pair<iterator, bool>(iterator(ret.first._node), ret.second);
	}
private:
	RBTree<K, K, SetKeyOfT> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    map 的仿函数要取出键值对中的key

    template<class K, class V>
class Map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	pair<iterator, bool> insert(const pair<K, V>& kv)
	{
		return _t.Insert(kv);
	}
private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    迭代器

    下面实现了基本的 * -> == != 运算符重载

    template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef __RBTreeIterator<T, Ref, Ptr> Self;
    Node* _node;

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

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

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    ++就是找中序的下一个结点，具体思路就是判断当前位置的右子树是否为空

    1. 非空：右子树的最左结点就是下一个
    2. 空：向上找，祖先中第一个孩子是左的结点

    最后一个结点的下一个就设为空。

    Self& operator++()
{
    if (_node->_right == nullptr)
    {
        // 找祖先中，孩子是父亲左的父亲
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && parent->_right == cur)
        {
            cur = cur->_parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
    else
    {
        // 右子树的最左结点
        Node* subLeft = _node->_right;
        while (subLeft->_left)
        {
            subLeft = subLeft->_left;
        }
        _node = subLeft;
    }
    return *this;
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    –就是和++反着来，判断当前位置的左子树是否为空

    1. 非空：左子树的最右结点就是上一个
    2. 空：向上找，祖先中第一个孩子是右的结点
    Self& operator--()
{
    if (_node->_left == nullptr)
    {
        Node* cur = _node;
        Node* parent = _node->_parent;
        while (parent && parent->_left == cur)
        {
            cur = cur->_parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
    else
    {
        Node* subRight = _node->_left;
        while (subRight->_right)
        {
            subRight = subRight->_right;
        }
        _node = subRight;
    }
    return *this;
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    接下来在红黑树里面实现 begin 和 end，begin 是最左结点，end 为空，依然是一个左闭右开。

    //RBTree
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);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    //Set
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
    return _t.Begin();
}

iterator end() const
{
    return _t.End();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    //Map
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
    return _t.Begin();
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    查找

    iterator Find(const K& key)
{
    Node* cur = _root;
    KeyOfT kot;
    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();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    map::operator[]

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

    • 1
    • 2
    • 3
    • 4
    • 5

    完整代码

    RBTree.h

    #pragma once
#include 
using namespace std;

enum Colour
{
	RED,
	BLACK
};

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

	Colour _col;

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

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef __RBTreeIterator<T, Ref, Ptr> Self;
    Node* _node;

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

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

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

    Self& operator++()
    {
        if (_node->_right == nullptr)
        {
            // 找祖先中，孩子是父亲左的父亲
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && parent->_right == cur)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        else
        {
            // 右子树的最左结点
            Node* subLeft = _node->_right;
            while (subLeft->_left)
            {
                subLeft = subLeft->_left;
            }
            _node = subLeft;
        }
        return *this;
    }

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

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

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

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

// T决定红黑树存什么类型的数据
// set RBTree
// map RBTree>
// KeyOfT 支持取出T对象中key的仿函数
template<class K, class T, class KeyOfT>
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);
        }

        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 make_pair(iterator(cur), 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;

        // 有父亲，且父亲为红才处理
        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 make_pair(iterator(newnode), true);
    }

    iterator Find(const K& key)
    {
        Node* cur = _root;
        KeyOfT kot;
        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();
    }

private:

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL) subRL->_parent = parent; // subRL有可能是空树，需要if判断

        Node* ppNode = parent->_parent; // 提前记录祖先，后面用来连接新的parent
        subR->_left = parent;
        parent->_parent = subR;

        if (parent == _root) // 如果parent就是根结点，那么新的根是subR
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else // 否则需要祖先来连接新的parent(即subR)，注意判断左右
        {
            if (parent == ppNode->_left)
            {
                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;

        Node* ppNode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (parent == ppNode->_left)
            {
                ppNode->_left = subL;
            }
            else
            {
                ppNode->_right = subL;
            }
            subL->_parent = ppNode;
        }
    }

private:
	Node* _root;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365

    Set.h

    #pragma once
#include "RBTree.h"

template<class K>
class Set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
	iterator begin() const
	{
		return _t.Begin();
	}

	iterator end() const
	{
		return _t.End();
	}

	pair<iterator, bool> insert(const K& key)
	{
		pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
		return pair<iterator, bool>(iterator(ret.first._node), ret.second);
	}

	iterator find(const K& key)
	{
		return _t.Find(key);
	}
private:
	RBTree<K, K, SetKeyOfT> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    Map.h

    #pragma once
#include "RBTree.h"

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<K, V>, MapKeyOfT>::iterator iterator;
	typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
	iterator begin()
	{
		return _t.Begin();
	}

	iterator end()
	{
		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<K, V>, MapKeyOfT> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
  • 相关阅读:
    Stable Diffusion 本地部署教程
    docker的基础命令&docker镜像和docker容器操作
    埋点日志解决方案——Golang+Gin+Sarama VS Java+SpringCloudGateway+ReactorKafka
    静态顺序表及基本操作具体实现
    企业工程项目管理系统源码（三控：进度组织、质量安全、预算资金成本、二平台：招采、设计管理）
    LeetCode 0174. 地下城游戏
    视频剪辑素材哪里找？这个几个网站就够了。
    【JavaSE】String类总结，StringBuilder、StringBuffer、String的区别讲解
    Fibonacci 数列与黄金分割
    使用华为RH2288服务器搭建iSCSI共享存储（含ESXi映射步骤）
  • 原文地址：https://blog.csdn.net/CegghnnoR/article/details/126212844