小伙伴们大家好，本片文章将会讲解map和set之用红黑树来封装map、set容器的相关内容。


如果看到最后您觉得这篇文章写得不错，有所收获，麻烦点赞👍、收藏🌟、留下评论📝。您的支持是我最大的动力，让我们一起努力，共同成长！

---

0. 前言

首先借用某位大佬的一句话：学习制造轮子不是为了打造更出色的轮子，而是为了汲取大师们卓越的思想，以此启迪我们的认知与创造力。

---

1. map、set底层源码一览

我们在模拟红黑树的时候一律用了pair的KV模型来进行实现。但是由于map是KV模型的而set是K型的，但是底层都是用的红黑树，那么应该如何进行调整呢？

⌛底层查看⏳

可以看到，对于K类型的set，模板传入了两个相同的K类型给RBTree；对于KV类型的map，模板传入了一个K，还有一个pair<K, V>类型给RBTree。

在RBTree类中将第二个模板参数传入给RBTreeNode，data的数据类型为就是此类型，这样就解决了此问题。

---

2. 改造红黑树

⏳map类和set类⌛

我们先按照底层的思路实现以下map类和set类：

// mymap.h
#pragma once
#include "RBTtree.h"namespace dsj
{template<class K, class V>class map{public:private:// pair<K, V> 为节点中的参数类型RBTree<K, pair<K, V>> rt;};
}// myset.h
#pragma once
#include "RBTtree.h"namespace dsj
{template<class K>class set{public:private:// 第二个 K 为节点中的参数类型RBTree<K, K> rt;};
}

💻RBTreeNode的修改

💻RBTree的修改

这样一改，问题就来了，在我们插入数据的时候，如何根据插入节点的K值来判断他插入所在的位置呢？如何进行比较？

可以用仿函数来进行比较。

⏳仿函数，这思想很重要⌛

虽然在RBTree中并不知道如何进行比较，但是在map和set类中知道如何进行比较，即map用pair的first进行比较，set直接用K值进行比较，实现方法如下：

// mymap.h
namespace dsj
{// 仿函数template <class K, class V>struct mapKeyOfT{// 取pair的firstconst K& operator()(const pair<K, V>& kv){return kv.first;}};template<class K, class V>class map{public:private:// 多加一个仿函数模板参数，对于map，取pair的first进行比较RBTree<K, pair<K, V>, mapKeyOfT<K, V>> rt;};
}// myset.h
namespace dsj
{// 仿函数template <class K>struct setKeyOfT{// 取出keyconst K& operator()(const K& key){return key;}};template<class K>class set{public:private:// 多加一个仿函数模板参数，对于set，直接对K值进行比较RBTree<K, K, setKeyOfT<K>> rt;};
}

⏳第一个K的作用⌛

有一个问题，给红黑树传模板参数的时候，第一个参数K类型的作用是什么呢？

1. 对于insert来说，set和map都可以不要第一个模板参数K，因为set中第二个模板参数是K，可以用来进行插入时的比较，对于map，也是用第二个模板参数来进行比较；

2. 但是对于find接口，他就需要K；

---

3. 迭代器的模拟实现

通过list的迭代器，我们知道如果原生指针的效果达不到我们想要的效果，就通过封装迭代器，再用运算符重载来达到我们预期的效果。

模拟实现：

template<class T>
struct __RBTIterator
{typedef RBTNode<T> Node;typedef __RBTIterator<T> Self;Node* _node;__RBTIterator(Node* node):_node(node){}T operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}
};

我们在模拟实现list的迭代器的时候讲过，对于const迭代器和普通迭代器，他们只有解引用和->的的返回值不一样，其他都相同，如果重新写一遍那么代码肯定非常冗余，因此我们这里还用类似的方法来实现（传入模板参数）。

改造后：

template<class T, class Ref, class Ptr>
struct __RBTIterator
{typedef RBTNode<T> Node;typedef __RBTIterator<T, Ref, Ptr> Self;Node* _node;__RBTIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}
};

RBTree中：

// 编译器自动推演，根据类型调用对应的迭代器
typedef __RBTIterator<T, T&, T*> Iterator;
typedef __RBTIterator<T, const T&, const T*> Const_Iterator;Iterator begin()
{Node* leftMin = _root;// 加上leftMin是为了预防_root为空的情况if (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);
}Iterator End()
{return Iterator(nullptr);
}Const_Iterator begin() const
{Node* leftMin = _root;if (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Const_Iterator(leftMin);
}Const_Iterator End() const
{return Const_Iterator(nullptr);
}

map和set中：

template<class K, class V>
class map
{
public:typedef typename RBTree<K, pair<K, V>, mapKeyOfT<K, V>>::Iterator iterator;typedef typename RBTree<K, pair<K, V>, mapKeyOfT<K, V>>::Const_Iterator const_iterator;const_iterator begin() const{return rt.Begin();}const_iterator end() const{return rt.End();}iterator begin(){return rt.Begin();}iterator end(){return rt.End();}private:RBTree<K, pair<K, V>, mapKeyOfT<K, V>> rt;
};template<class K>
class set
{
public:typedef typename RBTree<K, K, setKeyOfT<K>>::Iterator iterator;typedef typename RBTree<K, K, setKeyOfT<K>>::Const_Iterator const_iterator;const_iterator beign() const{return rt.Begin();}const_iterator end() const{return rt.End();}iterator beign(){return rt.Begin();}iterator end(){return rt.End();}
private:RBTree<K, K, setKeyOfT<K>> rt;
};

调用逻辑：

⏳迭代器++⌛

set和map迭代器的++按照中序遍历的顺序进行加加的，顺序为：左子树 根 右子树。

逻辑如下：

1. 右子树存在，下一个访问节点是右子树的最左节点；
2. 右子树不存在，向上找，找到孩子是父亲左节点的那个祖先节点。

代码：

Self& operator++()
{Node* cur = _node;if (cur->_right){Node* rightMin = cur->_right;while (rightMin->_left){rightMin = rightMin->_left;}_node = rightMin;}else{Node* parent = cur->_parent;// 这里加parent是为了预防访问最右节点后parent为空的情况while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

⏳迭代器- -⌛

思路同上，但是顺序相反：右子树 根 左子树。

逻辑如下：

1. 左子树存在，下一个访问节点是左子树的最右节点；
2. 左子树不存在，向上找，找到孩子是父亲右节点的那个祖先节点。

代码：

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

---

4. map的operator[]

map的operator[]的用法在之前的文章中讲过，它的作用是根据key的值进行查找，如果存在，那么就返回当前节点的value，如果不存在，就先插入此节点，然后再返回这个节点的value。

实现代码：

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

Insert函数修改逻辑：

Insert函数，我们要改变它的返回值，返回值是pair：

• 如果插入成功，返回插入节点所在的迭代器；
• 如果插入失败，返回K值相等的节点的迭代器。
• 如果要进行旋转，要先记录一下当前cur的节点，因为旋转后cur的节点可能就不是我们新插入的节点了。

---

5. 拷贝构造、析构、赋值重载

⏳析构函数⌛

析构函数要用后序，这样更为简单：

~RBTree()
{Destroy(_root);
}
void Destroy(Node* root)
{// 左右根的顺序进行析构if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;
}

⏳拷贝构造⌛

拷贝构造要用先序：

RBTree(const RBTree<K, T, KeyOfT>& t)
{_root = Copy(t._root);
}Node* Copy(Node* root)
{if (root == nullptr)return nullptr;Node* newroot = new Node(root->_data);newroot->_col = root->_col;newroot->_left = Copy(root->_left);if (newroot->_left)newroot->_left->_parent = newroot;newroot->_right = Copy(root->_right);if (newroot->_right)newroot->_right->_parent = newroot;return newroot;
}

⏳赋值重载⌛

下面是现代写法，之前讲过：

const RBTree<K, T, KeyOfT>& operator=(const RBTree<K, T, KeyOfT> t)
{swap(_root, t._root);return *this;
}