前言： map和set的底层是用红黑树实现的，红黑树的大框架，在我的上一篇博客： 红黑树的实现 中已经详细的讲解了，但是对于支持实现map和set还是欠缺的，比如 ：迭代器，模板参数等，还需要再继续完善。这样才能够 模拟实现 map和set。

---

1. 红黑树的框架

#include<iostream>
#include<assert.h>namespace RB_tree
{enum Color{Red,Black};template<class K, class V>struct RBtree_node{RBtree_node<K, V>* left_;RBtree_node<K, V>* right_;RBtree_node<K, V>* parents_;std::pair<K, V> kv_;Color col_;RBtree_node(const std::pair<K, V>& kv):left_(nullptr),right_(nullptr),parents_(nullptr),kv_(kv),col_(Red){}};template<class K, class V>class RBtree{typedef RBtree_node<K, V> Node;private:Node* _root;public:RBtree():_root(nullptr){}public:bool insert(const std::pair<K, V>& node){if (_root == nullptr){_root = new Node(node);_root->col_ = Black;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (node.first > cur->kv_.first){parent = cur;cur = cur->right_;}else if (node.first < cur->kv_.first){parent = cur;cur = cur->left_;}else{assert(false);}}cur = new Node(node);cur->col_ = Red;if (parent->kv_.first > cur->kv_.first){parent->left_ = cur;cur->parents_ = parent;}else{parent->right_ = cur;cur->parents_ = parent;}while (parent && parent->col_ == Red){Node* grand = parent->parents_;/// 插入到左树if (parent == grand->left_){Node* uncle = grand->right_;/// 情况一if (uncle && uncle->col_ == Red){parent->col_ = Black;uncle->col_ = Black;grand->col_ = Red;/// 往上更新cur = grand;parent = cur->parents_;}/// 情况二 或情况三else{ 右单旋if (cur == parent->left_){revolov_R(grand);parent->col_ = Black;grand->col_ = Red;}else{revolov_L(parent);revolov_R(grand);cur->col_ = Black;grand->col_ = Red;}break;}}/// 插入到右树else{Node* uncle = grand->left_;/// 情况一if (uncle && uncle->col_ == Red){parent->col_ = Black;uncle->col_ = Black;grand->col_ = Red;/// 往上更新cur = grand;parent = cur->parents_;}else{ 左单旋if (cur == parent->right_){revolov_L(grand);parent->col_ = Black;grand->col_ = Red;}else{revolov_R(parent);revolov_L(grand);cur->col_ = Black;grand->col_ = Red;}break;}}}_root->col_ = Black;return true;}private:void revolov_R(Node* issue_node){Node* issue_Lnode = issue_node->left_;Node* issue_Lnode_R = issue_Lnode->right_;Node* issue_node_parent = issue_node->parents_;issue_node->left_ = issue_Lnode_R;if (issue_Lnode_R){issue_Lnode_R->parents_ = issue_node;}issue_Lnode->right_ = issue_node;issue_node->parents_ = issue_Lnode;if (issue_node_parent == nullptr){_root = issue_Lnode;issue_Lnode->parents_ = nullptr;}else{if (issue_node_parent->left_ == issue_node)issue_node_parent->left_ = issue_Lnode;elseissue_node_parent->right_ = issue_Lnode;issue_Lnode->parents_ = issue_node_parent;}}void revolov_L(Node* issue_node){Node* issue_Rnode = issue_node->right_;Node* issue_Rnode_L = issue_Rnode->left_;Node* issue_node_parent = issue_node->parents_;issue_node->right_ = issue_Rnode_L;if (issue_Rnode_L){issue_Rnode_L->parents_ = issue_node;}issue_Rnode->left_ = issue_node;issue_node->parents_ = issue_Rnode;if (issue_node_parent == nullptr){_root = issue_Rnode;issue_Rnode->parents_ = nullptr;}else{if (issue_node_parent->left_ == issue_node)issue_node_parent->left_ = issue_Rnode;elseissue_node_parent->right_ = issue_Rnode;issue_Rnode->parents_ = issue_node_parent;}}public:void InOrder(){_InOrder(_root);}private:void _InOrder(Node* root){if (root == NULL)return;_InOrder(root->left_);std::cout << root->kv_.first << ":" << root->kv_.second << std::endl;_InOrder(root->right_);}};}

2. 模板参数的一些细节

底层 set中红黑树的节点 不是键值对，单一的一个类型；map中红黑树的节点 是一个键值对。所以需要创建两个版本的红黑树吗？答案是不需要，可以利用模板来支持泛型的。

我们需要对 红黑树的节点的 模板参数 做一下修改：
这样 就能够通过模板参树 来控制 节点的类型

    template<class T>struct RBtree_node{RBtree_node<T>* left_;RBtree_node<T>* right_;RBtree_node<T>* parents_;T kv_;Color col_;RBtree_node(const T & kv):left_(nullptr),right_(nullptr),parents_(nullptr),kv_(kv),col_(Red){}};

---

1. set的基本框架

template<class K>class set{private:RBtree<K,K,setketofT> t_;public:struct setketofT{const K& operator()(const K& k){return k;}};};

2. map的基本框架

template<class K,class V>class map{private:RBtree<K, std::pair<K, V>,mapkofT> t_;public:struct mapkofT{const K& operator()(const std::pair<K,V>& t){return t.first;}};};

可以看到在基本框架里面：给红黑树多传了一个模板参数 分别是setketofT，mapkofT。它们是仿函数，目的是 让红黑树顺利的取出，节点的类型，然后可以进行插入等操作。map传的是 pair的first；set传的是 k。这个有点难理解，下面还会讲到的。

• set的底层：RBtree<K,K,setketofT> t_;
• map的底层：RBtree<K, std::pair<K, V>,mapkofT> t_;

---

红黑树的模板参数 也需要变动：

   // 第三个模板参数用于接收 仿函数template<class K, class T,class keyofT>class RBtree{typedef RBtree_node<T> Node;}

keyofT就是用来接收 仿函数的，它的作用就是 拿出 构建红黑树 需要比较的那个值，比如 set就是 拿的 k 做比较，map拿的是 pair<>的first进行比较。

3. 红黑树支持迭代器

首先一般情况下迭代器是个指针，比如 vector，string的迭代器，但是对于某些容器，需要对迭代器进行封装，从而使得此迭代器达到类似指针的功能，比如list，链表 对它指针 执行 ++ 操作，它是不能够 指向 下一个节点的，所以 它的迭代器就不能是一个单纯的指针，需要封装出一个类(迭代器)，来实现 指针的操作，比如 ++ 迭代器 ，它就能指向list中下一个节点位置。

红黑树也是如此，我们也需要封装一个迭代器，实现 ++ ，- -，*，-> 的操作。红黑树迭代器走的是一个中序，这很关键，有了这个概念，我们才能开始 实现 迭代器的基本框架。

3.1 迭代器的实现

    template<class T,class Ref,class Ptr>struct RBtree_Iterator{typedef RBtree_node<T> Node;typedef RBtree_Iterator<T, Ref, Ptr> self;Node* node_;RBtree_Iterator(Node* node):node_(node){}self& operator++(){/// 如果右树不为空，那么下一个位置就是右树的最左节点if (node_->right_ != nullptr){Node* min = node_->right_;while (min->left_){min = min->left_;}node_ = min;}// 如果右树为空，那么有两种情况else{Node* cur = node_;Node* parent = cur->parents_;while (parent && cur == parent->right_){cur = parent;parent = cur->parents_;}node_ = parent;}return *this;}self& operator--(){/// 如果左树不为空，那么下一个位置就是左树的最右节点if (node_->left_ != nullptr){Node* max = node_->left_;while (max->right_){max=max->right_;}node_ = max;}// 如果左树为空，那么有两种情况else{Node* cur = node_;Node* parent = cur->parents_;while (parent && cur == parent->left_){cur = parent;parent = cur->parents_;}node_ = parent;}return *this;}Ref operator*(){return node_->kv_;}Ptr operator->(){return &node_->kv_;}bool operator ==(const self& n) const{return  n.node_ == node_;}bool operator !=(const self& n) const{return n.node_ != node_;}};

上面就是迭代器的实现，它的底层就是 个节点指针：

然后 实现具体的功能：

3.1.1 解引用

        Ref operator*(){return node_->kv_;}Ptr operator->(){return &node_->kv_;}

大家可能对 这个返回值 Ref 和 Ptr 有疑问，我们先来看个这个迭代器类的模板参数：
template<class T,class Ref,class Ptr>

第一个 模板参数T 是用来 定义迭代器中 底层指针 的类型的。
第二个模板参数Ref，以及第三个模板参数 Ptr是为了支持 const版本的迭代器所使用的。

如果 不需要支持 const版本，那么 就可以这样写：

        T& operator*(){return node_->kv_;}T* operator->(){return &node_->kv_;}

但是要求支持const迭代器，怎么办？有两种方式，可以在写个const版本的迭代器，但是代码冗余；或者通过模板参数传参，来控制这块的返回值。

于是红黑树中，定义迭代器可以这样：

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

3.1.2 == 和 !=

        bool operator ==(const self& n) const{return  n.node_ == node_;}bool operator !=(const self& n) const{return n.node_ != node_;}

这个比较简单，唯一有点需要理解的就是 self：
typedef RBtree_Iterator<T, Ref, Ptr> self;

这就是 迭代器 本身，所以 == ，!= 比较的是 两迭代器是否相等。

3.1.3 ++ 和 - -

self& operator++(){/// 如果右树不为空，那么下一个位置就是右树的最左节点if (node_->right_ != nullptr){Node* min = node_->right_;while (min->left_){min = min->left_;}node_ = min;}// 如果右树为空，那么有两种情况else{Node* cur = node_;Node* parent = cur->parents_;while (parent && cur == parent->right_){cur = parent;parent = cur->parents_;}node_ = parent;}return *this;}self& operator--(){/// 如果左树不为空，那么下一个位置就是左树的最右节点if (node_->left_ != nullptr){Node* max = node_->left_;while (max->right_){max=max->right_;}node_ = max;}// 如果左树为空，那么有两种情况else{Node* cur = node_;Node* parent = cur->parents_;while (parent && cur == parent->left_){cur = parent;parent = cur->parents_;}node_ = parent;}return *this;}

这是实现这个迭代器比较难的部分，当然应该都知道，map和set迭代器走的是中序，所以这里也得按照中序的规则，来进行迭代器的++ 、- -。

中序就是 左子树 根 右子树.

我们通过画图，来理解 ：

先是 ++ ：
(1) 如果当下节点的右树存在，那么 此节点的下一个节点就是 其右树的最左节点：

比如当下节点 是 6节点，那么它的右子树还存在，但是右子树的左子树 不存在，所以右子树就是它的下一个节点。

比如当下节点是 8节点，那么它的右子树还存在，右子树的最左节点是10节点，所以它的下一个节点是10节点。
(2) 如果当下节点的右树不存在，那么 此节点的下一个节点就是 孩子在父亲的左边的 第一个祖先

这句话有点绕口，不过 看例子也能明白：

比如 5节点 它的右树为空 ，它下一个节点 就是它的父亲，因为它在 父亲的左。
比如 7节点 它的右树为空，它的下一个节点是谁？是它的父亲吗?

7节点的下一个节点是 8节点，8节点是它的祖先，并且7节点在它的左。代码实现的话，靠的是更新 当下节点，一直等到 祖先为空，或者第一次出现 当下节点在父亲节点的左。

        self& operator++(){/// 如果右树不为空，那么下一个位置就是右树的最左节点if (node_->right_ != nullptr){Node* min = node_->right_;while (min->left_){min = min->left_;}node_ = min;}// 如果右树为空，那么有两种情况else{Node* cur = node_;Node* parent = cur->parents_;while (parent && cur == parent->right_){// 往上更新cur = parent;parent = cur->parents_;}node_ = parent;}return *this;}

然后看 - -：

其实它逻辑就是上面 ++ 反一下，它也分两种情况：

(1) 如果当下节点的左树存在，那么 此节点的 上一个节点就是 其左树的最右节点
(2) 如果当下节点的右树不存在，那么 此节点的上一个节点就是 孩子在父亲的右边的 第一个祖先

        self& operator--(){/// 如果左树不为空，那么下一个位置就是左树的最右节点if (node_->left_ != nullptr){Node* max = node_->left_;while (max->right_){max=max->right_;}node_ = max;}// 如果左树为空，那么有两种情况else{Node* cur = node_;Node* parent = cur->parents_;while (parent && cur == parent->left_){cur = parent;parent = cur->parents_;}node_ = parent;}return *this;}

---

3.2 红黑树封装迭代器

红黑树对迭代器进行封装，也就是说 要利用上面实现的迭代器 搞点事情：

template<class K, class T,class keyofT>struct RBtree{typedef RBtree_node<T> Node;public:typedef RBtree_Iterator<T, T&, T*> iterator;typedef RBtree_Iterator<T, const T&, const T*> const_iterator;private:Node* _root;public:iterator begin(){Node* cur = _root;while(cur && cur->left_){cur = cur->left_;}return iterator(cur);}iterator end(){return iterator(nullptr);}public:RBtree():_root(nullptr){}~RBtree(){destroy(_root);_root = nullptr;}RBtree(const RBtree<K,T,keyofT>& n){_root = copy(n->_root);}RBtree<K,T,keyofT>& operator = (RBtree<K,T,keyofT> n){std::swap(_root,n._root);return *this;}public:void destroy(Node* root){if (root == nullptr){return ;}destroy(root->left_);destroy(root->right_);delete root;}Node* copy(Node* root){if (_root == nullptr){return nullptr;}Node* newnode = new Node(root->kv_);newnode->col_ = root->col_;newnode->left_ = copy(root->left_);newnode->right_ = copy(root->right_);if (newnode->left_){newnode->left_->parents_ = newnode;}if (newnode->right_){newnode->right_->parents_ = newnode;}return newnode;}iterator find(const K& key){Node* cur = _root;keyofT kot;while (cur){if (key > kot(cur->kv_)){cur = cur->right_;}else if (key > kot(cur->kv_)){cur = cur->left_;}else{return iterator(cur);}}return end();}std::pair<iterator,bool> insert(const T& node){if (_root == nullptr){_root = new Node(node);_root->col_ = Black;return std::make_pair(iterator(_root),true);}keyofT kot;Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(node)> kot(cur->kv_)){parent = cur;cur = cur->right_;}else if (kot(node) < kot(cur->kv_)){parent = cur;cur = cur->left_;}else{return std::make_pair(iterator(cur), false);}}cur = new Node(node);Node* newnode = cur;cur->col_ = Red;if (kot(parent->kv_) > kot(cur->kv_)){parent->left_ = cur;cur->parents_ = parent;}else{parent->right_ = cur;cur->parents_ = parent;}while (parent && parent->col_ == Red){Node* grand = parent->parents_;/// 插入到左树if (parent == grand->left_){Node* uncle = grand->right_;/// 情况一if (uncle && uncle->col_ == Red){parent->col_ = Black;uncle->col_ = Black;grand->col_ = Red;/// 往上更新cur = grand;parent = cur->parents_;}/// 情况二 或情况三else{ 右单旋if (cur == parent->left_){revolov_R(grand);parent->col_ = Black;grand->col_ = Red;}else{revolov_L(parent);revolov_R(grand);cur->col_ = Black;grand->col_ = Red;}break;}}/// 插入到右树else{Node* uncle = grand->left_;/// 情况一if (uncle && uncle->col_ == Red){parent->col_ = Black;uncle->col_ = Black;grand->col_ = Red;/// 往上更新cur = grand;parent = cur->parents_;}else{ 左单旋if (cur == parent->right_){revolov_L(grand);parent->col_ = Black;grand->col_ = Red;}else{revolov_R(parent);revolov_L(grand);cur->col_ = Black;grand->col_ = Red;}break;}}}_root->col_ = Black;return std::make_pair(iterator(newnode),true);}};

这里 typedef 两个版本的迭代器。

3.2.1 修改一下insert

首先，用过map和set中的insert的朋友，应该知道 insert的返回类型是一个 pair<>,我之前的博客也有详细讲过，所以我们的insert也不例外，返回类型 pair<iterator,bool> 。

然后需要改动的地方就是 之前插入都是直接进行比较的那种，但是 set和map 的比较方式是不一样的，set是用 key直接比，map是用 pair<first,second>中的first来比，所以需要利用第三个模板仿函数来取中要比较的值。

定义一个 仿函数对象：

比较的时候：
if (kot(node)> kot(cur->kv_))
else if (kot(node) < kot(cur->kv_))

最后我们控制一下返回值：

• 在空树里面插入：
  return std::make_pair(iterator(_root),true);
• 插入相同key的节点
  return std::make_pair(iterator(cur), false);
  -插入成功
  return std::make_pair(iterator(newnode),true);

std::pair<iterator,bool> insert(const T& node){if (_root == nullptr){_root = new Node(node);_root->col_ = Black;return std::make_pair(iterator(_root),true);}keyofT kot;Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(node)> kot(cur->kv_)){parent = cur;cur = cur->right_;}else if (kot(node) < kot(cur->kv_)){parent = cur;cur = cur->left_;}else{return std::make_pair(iterator(cur), false);}}cur = new Node(node);Node* newnode = cur;if (kot(parent->kv_) > kot(cur->kv_)){parent->left_ = cur;cur->parents_ = parent;}else{parent->right_ = cur;cur->parents_ = parent;}while (parent && parent->col_ == Red){Node* grand = parent->parents_;/// 插入到左树if (parent == grand->left_){Node* uncle = grand->right_;/// 情况一if (uncle && uncle->col_ == Red){parent->col_ = Black;uncle->col_ = Black;grand->col_ = Red;/// 往上更新cur = grand;parent = cur->parents_;}/// 情况二 或情况三else{ 右单旋if (cur == parent->left_){revolov_R(grand);parent->col_ = Black;grand->col_ = Red;}else{revolov_L(parent);revolov_R(grand);cur->col_ = Black;grand->col_ = Red;}break;}}/// 插入到右树else{Node* uncle = grand->left_;/// 情况一if (uncle && uncle->col_ == Red){parent->col_ = Black;uncle->col_ = Black;grand->col_ = Red;/// 往上更新cur = grand;parent = cur->parents_;}else{ 左单旋if (cur == parent->right_){revolov_L(grand);parent->col_ = Black;grand->col_ = Red;}else{revolov_R(parent);revolov_L(grand);cur->col_ = Black;grand->col_ = Red;}break;}}}_root->col_ = Black;return std::make_pair(iterator(newnode),true);}

---

3.2.2 迭代器的 begin(),end()

这里的begin()，就是中序遍历红黑树的第一个节点，也就是最左节点。
end()，给空的迭代器就好了。

        iterator begin(){Node* cur = _root;while(cur && cur->left_){cur = cur->left_;}return iterator(cur);}iterator end(){return iterator(nullptr);}

3.2.3 修改一下find函数，返回迭代器

       iterator find(const K& key){Node* cur = _root;keyofT kot;while (cur){if (key > kot(cur->kv_)){cur = cur->right_;}else if (key > kot(cur->kv_)){cur = cur->left_;}else{return iterator(cur);}}return end();}

这个简单的很，玩的写。

4. 红黑树继续完善

4.1 红黑树的拷贝构造和赋值重载

默认情况下，是浅拷贝，这完全不能用于 封装map和set，会出大问题。所以需要我们自己来写 。

       RBtree(const RBtree<K,T,keyofT>& n){_root = copy(n._root);}RBtree<K,T,keyofT>& operator = (RBtree<K,T,keyofT> n){std::swap(_root,n._root);return *this;}Node* copy(Node* root){if (root == nullptr){return nullptr;}Node* newnode = new Node(root->kv_);newnode->col_ = root->col_;newnode->left_ = copy(root->left_);newnode->right_ = copy(root->right_);if (newnode->left_){newnode->left_->parents_ = newnode;}if (newnode->right_){newnode->right_->parents_ = newnode;}return newnode;}

这里最关键的是理解 copy函数，用递归完成的。

走的是一个前序，如果root为空，就返回。不为空就以root的数据构造一个新的节点，这里就是深拷贝，然后 它的左树深拷贝root的左树，它的右树深拷贝root的右树。但是 有个问题：红黑树是一个三叉链，它的父子关系也需要维护，怎么才能链接上父亲呢?

它递归结束 返回的上一层的newnode 就是它的父亲，这里还得判断 是否为空。

画个图：

假如我要拷贝上面那颗树：

1. 先是深拷贝根节点
   
2. 递归深拷贝它的左子树

3. 继续往下递归左子树，其左子树为空，然后返回空。然后递归右子树发现也为空，返回空

4. 然后检测其左右子树返回都是空，所以不需要维护父子关系，直接返回 这个节点

现在就返回到上一层了。

5. 递归这一层的右子树，和上面情况一样

6. 检查这一层的左子树和右子树，发现不为空，所以 管理父子关系。

也就是：

newnode->left_->parents_ = newnode;
newnode->right_->parents_ = newnode;

---

拷贝构造的话，直接调用 copy传入根就好了。

赋值重载的话，这里是有细节的，它是通过传参，这是形参的拷贝构造，然后交换一下 形参的root_ ，就完成了赋值，并且 出了函数调用结束后，它会释放形参，此时的形参中的数据是交换后的数据。

---

4.2 红黑树的析构函数

红黑树的析构，直接释放掉根节点 行吗？答案是不行，必须递归着 把所有节点都释放掉才可以。

        void destroy(Node* root){if (root == nullptr){return ;}destroy(root->left_);destroy(root->right_);delete root;}~RBtree(){destroy(_root);_root = nullptr;}

上面的递归删除，是一个后序。当然必须是后序。这个大家自行体会吧。

---

5. 封装红黑树的map和set

其实上文很重要，map和set的底层是红黑树，所以我们必须完善红黑树才能够支持map和set的一些操作。比如 迭代器，拷贝构造，赋值重载，析构等

就相当于 map和set的find，insert，迭代器都是对红黑树中的复用，下面就能很清楚的感觉到了。

5.1 map的模拟实现

template<class K,class V>class map{public:struct mapkofT{const K& operator()(const std::pair<K, V>& t){return t.first;}};typedef typename RBtree<K, std::pair<K, V>, mapkofT>::iterator iterator;iterator begin(){return t_.begin();}iterator end(){return t_.end();}std::pair<iterator,bool> insert(const std::pair<K,V> &i){return t_.insert(i);}iterator find(const K& key){return t_.find(key);}V& operator[](const K& key){auto i = t_.insert(std::make_pair(key, V()));return i.first->second;}private:RBtree<K, std::pair<K, V>,mapkofT> t_;};

对吧，真的比较简单，但是上面还有细节：
typedef typename RBtree<K, std::pair<K, V>, mapkofT>::iterator

必须加上 typename 否则就会报个错误：iterator 依赖名称不是类型。

这个报错说实话，开始我也一头雾水：

它的意思就是 不认为 RBtree<K, std::pair<K, V>, mapkofT>::iterator 是个类型，主要是为什么呢？还没来得及实例化，所以它不是个类型，必须得等到 实例化成功后，它才能算为类型。所以呢 加上个 typename ，告诉编译器，它是一个类型，先让我编译通过。

还有个[]的实现，我之前写了一篇博客，里面很详细的介绍了这个，但是 没有讲实现，现在模拟实现了一下，发现不是想象中的那么高级：

调用了insert，利用了它的返回值

        V& operator[](const K& key){auto i = t_.insert(std::make_pair(key, V()));return i.first->second;}

---

5.2 set的模拟实现

template<class K>class set{public:struct setketofT{const K& operator()(const K& k){return k;}};typedef typename RBtree<K, K, setketofT>::iterator itetator;// 迭代器itetator begin(){return t_.begin();}itetator end(){return t_.end();}std::pair<itetator, bool> insert(const K& key){return t_.insert(key);}itetator find(const K& key){return t_.find(key);}private:RBtree<K,K,setketofT> t_;};

---

6. 总结

有问题的私信，或评论。感觉有帮助的朋友，可以点一个小赞，支持一下。