【C++ 第十五章】map 和 set 的封装（封装红黑树）

1. map 和 set 的介绍

⭐map 与 set 分别是STL中的两种序列式容器;

它们是一种树形数据结构的容器，且其的底层构造为一棵红黑树;

而在上一篇文章中提到,其实红黑树本身就是一棵二叉搜索树,是基于二叉搜索树的性质对其增加了平衡的属性来提高其综合性能

⭐当然也提到了红黑树与AVL树的区别：

1、AVL树保证了严格的平衡，其树高不会很高，使其查找效率较高，但是就是因为要不断旋转保证平衡，因此 当插入和删除时，较多的旋转会影响效率

2、红黑树不用保证严格的平衡，查找的时间复杂度为 O(logN) 级别（和AVL树）在 插入和删除 中，只需要较少的旋转，因此 插入和删除 效率较高

综合考虑 map 和 set 使用 红黑树作为底层容器

2. map 和 set 的结构

在 map 与 set 的使用过程中，由于 set 容器的底层树节点存储着数据为 key （T 类型）

而 map 的底层树节点存储着数据为一个键值对 key/value; （pair类型）

所以可能会联想到在STL中的这两个容器是否使用的是不同的红黑树？

而实际在 STL 的源码中可以看到，对于这两个容器而言所使用的是同一个红黑树（即调用同一棵红黑树），并且利用泛型的特性来控制两个容器中所使用的对应的参数;

那么既然是同一棵红黑树，应该如何对这棵树进行修改 使得该树能够同时兼容 map 的 key/value 键值对数据存储 和 set 的 key 数据存储  呢？

3、对红黑树的进一步修改

在我们的上一章节 讲解了红黑树的各种基础构造，本章对红黑树进一步修改，融入 迭代器 以及 泛型化使其更加适配 map 与 set

（1）修改一：将节点数据类型换成 T （泛型的思想）

将节点中数据变量 换成 类型T

当 T == key 类型时，该节点对应 set 容器

当 T == pair<key, value> 类型时，该节点对应 map 容器

这样就初步实现，同一节点类模板，可以对应 多种数据类型，适应 set 和 map

template<class T>
struct RBTreeNode
{T _data;  // 泛型化思想：_data 可以是 Key 类型，也可以是 pair<Key, Value> 类型// .....
};

先前 set 和 map 要设计两套 红黑树类

为了适应 set：

template<class Key>
class RBTree
{}

为了适应 map：

template<class Key, class Value>
class RBTree
{}

现在节点类泛型化了，红黑树类也要对应修改

template<class T>
class RBTree
{}

（2）修改二：应用仿函数 修改 插入函数 insert 内部比较逻辑

⭐之前没修改时，为了适应 set 和 map ，要设计两种传参类型

为了适应 set：

bool insert(const K& key)
{}

为了适应 map：

bool insert(const pair<K, V>& kv)
{}

---

⭐insert 函数内部比较键值大小的部分 也有两套设计

 当 T == key 时，对应 set，insert 函数内部比较键值大小的部分：直接比较键值 key

if (cur->_key < key) {// .....
}

当 T == key/value 时，对应 map，insert 函数内部比较键值大小的部分：还要指定键值对的 first

if (cur->_kv.first < kv.first) {// .....
}

现在 节点数据泛型为 T，函数 insert 传参类型和内部某些比较逻辑都需要做调整

⭐ 修改传参类型

bool insert(const T& data)
{}

⭐内部某些比较逻辑：使用仿函数

因为我们那里的就是要用 键值 key 比较，因此 set 可以直接用节点数据 key 比较，而 map 需要用 节点数据pair的first 比较，这里就有区别，因此需要仿函数“统一化”

（1）set ：

        使用仿函数时，当操作数类型为 K 类型，则直接识别使用 set 的仿函数 set_KeyOfT 中的 operator() 函数，返回 key（即返回一个键值）

template<class K>
class set
{// set 中的仿函数struct set_KeyOfT {const K& operator()(const K& key) {return key;}};// ....... 其他补充
private:RBTree<K, set_KeyOfT> _tree;   
};

（2）map

        当操作数类型为 pair<key, value> 键值对类型，则直接识别为 map 的仿函数 map_KeyOfT 中的 operator() 函数，返回 pair<key, value> 的 first （即也返回一个 键值)

template<class K, class V>
class map
{struct map_KeyOfT {const K& operator()(const pair<K, V>& kv) {return kv.first;}};// ....... 其他补充private:RBTree<pair<const K, V>, map_KeyOfT> _tree;
};

在 红黑树类模板中添加 仿函数的类型：class KeyOfT

template<class T, class KeyOfT>
class RBTree
{}

仿函数的应用

KeyOfT kot; // 创建一个仿函数类对象
if (kot(cur->_data) < kot(data)) // data 可能是 key类型，可能是 pair<key, value> 类型
// 使用仿函数，调用operator() 自动识别 data 的类型，放回 键值 key 进行比较

（3）修改三：给 红黑树类模板 再加一个 类型 class K

        我们实现 find 和 insert 函数时，insert 函数参数类型是 T ，表示 data 可以是 key 类型，也可以是 pair< key, value > 类型

但是 find 函数参数可以是 T 类型吗？？

不可以！，无论是 map or set，find 函数都是查找 键值 key，固定要用 key

        若 find 的参数是 T 类型，当 T == key 时，直接可以使用，当 T == pair< key, value > 时，就不能直接使用 T 来查找，就要使用 T.first，就使得两个类型造就两种使用逻辑

因此 我们可以额外传一个 键值（既然是固定要用的，就多传一个）

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

---

至此，我们红黑树类模板中 第一个参数 K 用于传键值key，第二个参数 T 为泛型用于 接收两种类型（兼容set 和 map 两种），第三个参数为 仿函数 

---

（4）修改四：插入函数 insert 的 返回值 改为 pair 类型

在STL中,无论是 map 容器还是 set 容器，其插入函数Insert()函数的返回值都是为一个pair<iterator,bool>；

1、若是插入成功则返回新插入节点的迭代器位置 与 true； (迭代器的实现将在下文中提到)

2、若是插入失败则返回与需要插入的数据相同的节点位置 与 false；

例如 STL 库中的 map 的 insert 函数源码

pair<iterator,bool> insert (const value_type& val);

value_type 就是 pair< K, V>

pair 是一个类模板

我们的 插入函数 返回值修改为：

pair<iterator, bool> insert(const T& data)

4. 迭代器

因为需要将 红黑树封装进容器 map 和 set 中，容器会涉及各种操作，需要迭代器

因此我们先实现 红黑树的迭代器

因为 map 和 set 的底层是 红黑树，因此 他们的 迭代器就是将一个树节点指针封装成一个类

1.1 基础类框架和函数

基础函数：重载点操作符、重载箭头操作符、重载不等于操作符、构造函数

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _p;Ref operator*() {return _p->_data;}Ptr operator->() {return &(_p->_data);}// 两个迭代器比较相等 就是直接比较 两个指针bool operator!=(const Self& x) {return _p != x._p;}RBTreeIterator(Node* p):_p(p){}
};

1.2 重载前置++ 和 前置--

关于前置++

在 二叉搜索树中 前置++，需要使迭代器指向 中序遍历的 下一个位置

因此，设计前置++ 就需要模拟中序遍历找到下一个节点

---

中序遍历顺序是：左孩子 --->  根  --->  右孩子

若当前节点为 节点 5，按照中序，下一个位置是 节点 7，即 根节点（从左孩子到根节点）

若当前节点为 节点 7，按照中序，下一个位置是 节点 9，即 右孩子（从根节点到右孩子）

若当前节点为 节点 9，按照中序，右孩子为 空，证明已经走完一个中序（左根右），应该回溯到 祖先节点，寻找 当前节点为 父亲的左孩子的关系，即 从节点9 一直到 节点 7，此时 节点7 是父亲节点 11 的左孩子（这样满足 从左孩子到根节点 ，即节点 9 的下一个位置就是 节点 11）

若当前节点为 节点 11，按照中序，下一个位置是 节点 12，即右子树的 最左节点（在右子树，循环向下找到右子树的最左节点）

综合上面几种情况，可以得出以下逻辑

1、右不为空，则 自己就是 根：右子树最左节点就是中序下一个，while() 循环 找 右子树的 最左节点

2、右为空，则 cur 和 parent 沿着到根节点的路径向上查找，直到 孩子 cur 是父亲 parent 的 left

此时 parent 就是中序的下一个节点

伪代码：

定义 cur = 当前位置

if（cur 的 右不为空）

        循环找右子树的最左节点

else if（cur 的 右为空） 

        定义 parent 

        while（parent 不为 空 且 parent 的左 不为 cur）

        循环结束，parent 就是 中序的写一个节点       

 

实际代码：

Self& operator++() {Node* cur = _p;if (cur->_right) {cur = cur->_right;while (cur->_left) {  // 注意这里是 cur->_left 我们目的是到最左节点，不是 空节点！cur = cur->_left;}}else {Node* parent = cur->_parent;while (parent && parent->_left != cur) {cur = parent;parent = parent->_parent;}cur = parent;}_p = cur;return *this;
}

关于前置--

重载前置-- 也 同理，就是倒着中序遍历（右 根 左）

注意：前置-- 的第一个节点可能为 end()，本文中我们将 end() 设置为 最后一个节点的下一个节点，即为 NULL

当对 end() == NULL 前置-- 时，可能导致空指针访问的错误，因此需要特殊处理

end() 的前一个即为 二叉树的 最后一个节点（中序遍历的最后一个：右子树的最右节点） 

Node* cur = _p;
// 如果 cur 为 nullptr 代表现在指向 end()
// 特殊处理
if (cur == nullptr) {cur = _root;while (cur && cur->_right) {cur = cur->_right;}//_p = cur;
}

前置-- 的代码：

// 减减 和 加加的 逻辑刚好相反
Self& operator--() {Node* cur = _p;// 如果 cur 为 nullptr 代表现在指向 end()// 特殊处理if (cur == nullptr) {cur = _root;while (cur && cur->_right) {cur = cur->_right;}//_p = cur;}// 下面的逻辑和 前置++ 差不多：镜像反转理解即可else if (cur->_left) {cur = cur->_left;while (cur->_right) {cur = cur->_right;}}else {Node* parent = cur->_parent;while (parent && parent->_right != cur) {cur = parent;parent = parent->_parent;}cur = parent;}_p = cur;return *this;
}

1.3 将 迭代器封装进 红黑树

这里定义了：begin() / end() （且为 iterator 和 const_iterator 两个版本）

此处：红黑树的 begin 是整棵二叉搜索树的 最左边的节点（即中序遍历的第一个节点），因此需要循环操作

template<class K, class T, class KeyOfT>
class RBTree
{
public:typedef RBTreeNode<T> Node;// 定义迭代器typedef RBTreeIterator<T, T&, T*> iterator;typedef RBTreeIterator<T, const T&, const T*> const_iterator;// 迭代器iterator begin() {Node* cur = _root;while (cur && cur->_left) {cur = cur->_left;}return iterator(cur, _root);}iterator end() {return iterator(nullptr, _root);}const_iterator begin() const {Node* cur = _root;while (cur && cur->_left) {cur = cur->_left;}return const_iterator(cur, _root);}const_iterator end() const {return const_iterator(nullptr, _root);}private:Node* _root = nullptr;
};

就是上面这一部分封装了迭代器，其他的红黑树代码部分上一章都实现了，这里暂不赘述

1.4 ⭐ 迭代器类 完整代码

注释都有解释了，若不明白，可以评论区讨论或私信

// T ：节点中的数据类型
// Ref：引用类型 T&  或  const T&
// Ptr：指针类型 T*  或  const T*
template<class T, class Ref , class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;    // 重定义节点类命名typedef RBTreeIterator<T, Ref, Ptr> Self;  // 对自己的迭代器类型重命名Node* _p;  // 迭代器中指向节点的指针Ref operator*() {return _p->_data;}Ptr operator->() {return &(_p->_data);}// 两个迭代器比较相等 就是直接比较 两个指针bool operator!=(const Self& x) {return _p != x._p;}bool operator==(const Self& x) const {return _p == x._p;}// 我写的函数 cur 有点冗余，其实代码可以更加精简Self& operator++() {Node* cur = _p;if (cur->_right) {cur = cur->_right;while (cur->_left) {  // 注意这里是 cur->_left 我们目的是到最左节点，不是 空节点！cur = cur->_left;}}else {Node* parent = cur->_parent;while (parent && parent->_left != cur) {cur = parent;parent = parent->_parent;}cur = parent;}_p = cur;return *this;}// 减减 和 加加的 逻辑刚好相反Self& operator--() {Node* cur = _p;// 如果 cur 为 nullptr 代表现在指向 end()// 特殊处理if (cur == nullptr) {cur = _root;while (cur && cur->_right) {cur = cur->_right;}//_p = cur;}// 下面的逻辑和 前置++ 差不多：镜像反转理解即可else if (cur->_left) {cur = cur->_left;while (cur->_right) {cur = cur->_right;}}else {Node* parent = cur->_parent;while (parent && parent->_right != cur) {cur = parent;parent = parent->_parent;}cur = parent;}_p = cur;return *this;}RBTreeIterator(Node* p, Node* root):_p(p){}
};

5. ⭐红黑树 完全体（含迭代器+适配 map 和 set 的泛型）
 

含有

红黑树节点类

迭代器类

红黑树类：拷贝构造、赋值运算符重载、析构、插入函数、4种旋转函数、查找 find、中序遍历、求树的高度、求树的节点个数、判断树是否平衡

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;// 设置颜色枚举值
enum Colour {RED,BLACK
};template<class T>
struct RBTreeNode
{typedef RBTreeNode<T> Node;T _data;  // 泛型化思想：_data 可以是 Key 类型，也可以是 pair<Key, Value> 类型Node* _left;Node* _right;Node* _parent;Colour _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};// T ：节点中的数据类型
// Ref：引用类型 T&  或  const T&
// Ptr：指针类型 T*  或  const T*
template<class T, class Ref , class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;    // 重定义节点类命名typedef RBTreeIterator<T, Ref, Ptr> Self;  // 对自己的迭代器类型重命名Node* _p;  // 迭代器中指向节点的指针Node* _root;  Ref operator*() {return _p->_data;}Ptr operator->() {return &(_p->_data);}// 两个迭代器比较相等 就是直接比较 两个指针bool operator!=(const Self& x) {return _p != x._p;}bool operator==(const Self& x) const {return _p == x._p;}// 我写的函数 cur 有点冗余，其实代码可以更加精简Self& operator++() {Node* cur = _p;if (cur->_right) {cur = cur->_right;while (cur->_left) {  // 注意这里是 cur->_left 我们目的是到最左节点，不是 空节点！cur = cur->_left;}}else {Node* parent = cur->_parent;while (parent && parent->_left != cur) {cur = parent;parent = parent->_parent;}cur = parent;}_p = cur;return *this;}// 减减 和 加加的 逻辑刚好相反Self& operator--() {Node* cur = _p;// 如果 cur 为 nullptr 代表现在指向 end()// 特殊处理if (cur == nullptr) {cur = _root;while (cur && cur->_right) {cur = cur->_right;}//_p = cur;}// 下面的逻辑和 前置++ 差不多：镜像反转理解即可else if (cur->_left) {cur = cur->_left;while (cur->_right) {cur = cur->_right;}}else {Node* parent = cur->_parent;while (parent && parent->_right != cur) {cur = parent;parent = parent->_parent;}cur = parent;}_p = cur;return *this;}RBTreeIterator(Node* p, Node* root):_p(p),_root(root){}
};template<class K, class T, class KeyOfT>
class RBTree
{
public:typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T&, T*> iterator;typedef RBTreeIterator<T, const T&, const T*> const_iterator;RBTree() = default;~RBTree() {destory(_root);_root = nullptr;}// 拷贝构造RBTree(const RBTree<K, T, KeyOfT>& t) {_root = CopyTree(t._root);}// 赋值重载RBTree<K, T, KeyOfT>& operator=(const RBTree<K, T, KeyOfT>& t) {RBTree tmp(t);std::swap(_root, tmp._root);return *this;}// 迭代器iterator begin() {Node* cur = _root;while (cur && cur->_left) {cur = cur->_left;}return iterator(cur, _root);}iterator end() {return iterator(nullptr, _root);}const_iterator begin() const {Node* cur = _root;while (cur && cur->_left) {cur = cur->_left;}return const_iterator(cur, _root);}const_iterator end() const {return const_iterator(nullptr, _root);}// 查找iterator find(const K& key) const {Node* cur = _root;while (cur) {if ((cur->_data).first < key) {cur = cur->_right;}else if ((cur->_data).first > key) {cur = cur->_left;}else return iterator(cur, _root);}return end();}// 插入// 插入成功就是 true，迭代器指向新插入的节点// 插入失败就是 false，迭代器指向已存在的那个节点pair<iterator, bool> insert(const T& data) {if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK; // 根节点一定是黑的return make_pair(iterator(_root, _root), true);}// 利用仿函数KeyOfT kot;Node* cur = _root;Node* parent = cur;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, _root), false);}// 在 cur 的位置插入该节点cur = new Node(data);cur->_col = RED;  // 新增节点给 红的Node* newNode = cur;  // 这里记录以下初始的 cur，避免下面各种操作改变 cur// 父连子，子连父if (kot(parent->_data) > kot(data)) parent->_left = cur;else  parent->_right = cur;cur->_parent = parent;// 变色调整：while (parent && parent->_col == RED) {Node* Grandfather = parent->_parent;/*gp     u*/// 父亲是  爷爷 的左孩子if (parent == Grandfather->_left) {Node* Uncle = Grandfather->_right;// 叔叔是 红色：三人变色，cur指爷if (Uncle && Uncle->_col == RED) {parent->_col = BLACK;Uncle->_col = BLACK;Grandfather->_col = RED;cur = Grandfather;parent = cur->_parent;}// 叔叔是 黑色：旋转后变色else if (Uncle == nullptr || Uncle->_col == BLACK) {// 看 cur 的位置：决定单旋 or 双旋if (cur == parent->_left) { /*  右单旋 + 变色gp       uc*/rotateLL(Grandfather);// 爷变红，父变黑Grandfather->_col = RED;parent->_col = BLACK;}else if (cur == parent->_right) {/*  双旋（先左旋后右旋） + 变色gp        uc*/rotateRR(parent);  // p 先 左旋rotateLL(Grandfather);  //  g 再右旋// 爷变红，cur 变黑Grandfather->_col = RED;cur->_col = BLACK;}break;}}// 父亲是  爷爷 的右孩子else if (parent == Grandfather->_right) {Node* Uncle = Grandfather->_left;// 叔叔是 红色：三人变色，cur指爷if (Uncle && Uncle->_col == RED) {parent->_col = BLACK;Uncle->_col = BLACK;Grandfather->_col = RED;cur = Grandfather;parent = cur->_parent;}// 叔叔是 黑色：旋转后变色else if (Uncle == nullptr || Uncle->_col == BLACK) {// 看 cur 的位置：决定单旋 or 双旋if (cur == parent->_right) {/*  左单旋 + 变色gu       pc*/rotateRR(Grandfather);// 爷变红，父变黑Grandfather->_col = RED;parent->_col = BLACK;}else if (cur == parent->_left) {/*  双旋（先右旋后左旋） + 变色gu         pc*/rotateLL(parent);  // p 先 右旋rotateRR(Grandfather);  //  g 再左旋// 爷变红，cur 变黑Grandfather->_col = RED;cur->_col = BLACK;}break;}}}// 修改一：根节点强制变色_root->_col = BLACK;return make_pair(iterator(newNode, _root), true);}// RR型：左单旋void rotateRR(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;// 1、subRL变成parent的右孩子parent->_right = subRL;// subRL 是有可能为 空的if (subRL) {subRL->_parent = parent;}// 2、parent变成subR的左孩子subR->_left = parent;parent->_parent = subR;// 3、subR变成当前子树的根// parentParent 是指 刚开始的 parent 的父亲：若 parent 是 _root 则 parentParent 为空，否则不为空，则该树就是子树if (parentParent) {if (parent == parentParent->_right)parentParent->_right = subR;else parentParent->_left = subR;subR->_parent = parentParent;}// 如果 parentParent == nullptr：说明 parent 是该树的 _root，_root 的 parent 是空else {_root = subR;subR->_parent = nullptr;}}// LL型：右单旋void rotateLL(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;// 1、subLR变成parent的左孩子parent->_left = subLR;// subRL 是有可能为 空的if (subLR) {subLR->_parent = parent;}// 2、parent变成subL的右孩子subL->_right = parent;parent->_parent = subL;// 3、subL 变成当前子树的根// parentParent 是指 刚开始的 parent 的父亲：若 parent 是 _root 则 parentParent 为空，否则不为空，则该树就是子树if (parentParent) {if (parent == parentParent->_right)parentParent->_right = subL;else parentParent->_left = subL;subL->_parent = parentParent;}// 如果 parentParent == nullptr：说明 parent 是该树的 _root，_root 的 parent 是空else {_root = subL;subL->_parent = nullptr;}}// LR 型：subL 先 左旋， parent 右旋void rotateLR(Node* parent) {rotateRR(parent->_left);rotateLL(parent);}// RL 型：subR 先 右旋， parent 左旋void rotateRL(Node* parent) {rotateLL(parent->_right);rotateRR(parent);}// 中序遍历void InOrder() {_InOrder(_root);cout << '\n';}// 获取根节点Node* GetRoot() {return _root;}// 获取该树的高度int Height() {return _Height(_root);}// 获取节点个数int Size() {return _Size(_root);}// 判断是否是 红黑树bool IsValidRBTree() {if (_root == nullptr) return false;else if (_root && _root->_col == RED) return false;// 遍历一条路，记录一条路上一共固定有多少个黑色节点int cnt = 0;Node* cur = _root;while (cur) {if (cur->_col == BLACK) cnt++;cur = cur->_left;}return _IsValidRBTree(_root, 0, cnt);}private://  判断是否是 红黑树bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount){// 1、看根节点是否是 黑的// 2、看每条路径的 黑色节点数量是否相同// 3、检查是否有连续的红节点：遇到一个红节点就判断其父亲是否是 红的//走到null之后，判断 k 和 blackCount 是否相等：即一条路径上的 黑色节点数量是否为固定值if (pRoot == nullptr){if (k != blackCount){cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (pRoot->_col == BLACK)k++;// 检测当前节点与其双亲是否都为红色Node* pParent = pRoot->_parent;if (pParent && pParent->_col == RED && pRoot->_col == RED){cout << "违反性质三：没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_left, k, blackCount) && _IsValidRBTree(pRoot->_right, k, blackCount);}int _Size(Node* pRoot) {if (pRoot == nullptr) return 0;//if (pRoot->_left == nullptr && pRoot->_right == nullptr) return 1;return 1 + _Size(pRoot->_left) + _Size(pRoot->_right);}int _Height(Node* pRoot) {if (pRoot == nullptr)return 0;return 1 + max(_Height(pRoot->_left), _Height(pRoot->_right));}// 销毁一棵树：后序遍历void destory(Node* root) {if (root == nullptr) {return;}destory(root->_left);destory(root->_right);delete root;}// 拷贝一棵树Node* CopyTree(const Node* root) {if (root == nullptr) {return nullptr;}Node* newRoot = new Node(root->_kv);newRoot->_left = CopyTree(root->_left);newRoot->_right = CopyTree(root->_right);return newRoot;}void _InOrder(const Node* root) {if (root == nullptr) {return;}_InOrder(root->_left);cout << (root->_kv).first << " : " << (root->_kv).second << '\n';_InOrder(root->_right);}Node* _root = nullptr;
};

6. ⭐封装 set 完整代码

红黑树的代码 前面已经实现，在 set 中直接调用一个红黑树即可（记得在 set.h 要放入 红黑树的头文件 ）

template<class K>
class set
{struct set_KeyOfT {const K& operator()(const K& key) {return key;}};
public:typedef typename RBTree<K, const K, set_KeyOfT>::iterator iterator;typedef typename RBTree<K, const K, set_KeyOfT>::const_iterator const_iterator;// 直接调用红黑树的 插入函数pair<iterator, bool> insert(const K& key) {return _tree.insert(key);}// 迭代器：都是直接调用底层红黑树的 函数iterator begin() {return _tree.begin();}iterator end() {return _tree.end();}const_iterator begin() const {return _tree.begin();}const_iterator end() const {return _tree.end();}iterator find(const K& key) {return _tree.find(key);}private:RBTree<K, const K, set_KeyOfT> _tree;
};

7. ⭐封装 map 完整代码

红黑树的代码 前面已经实现，在 map 中直接调用一个红黑树即可（记得在 map .h 要放入 红黑树的头文件 ）

template<class K, class V>
class map
{struct map_KeyOfT {const K& operator()(const pair<K, V>& kv) {return kv.first;}};
public:typedef typename RBTree<K, pair<const K, V>, map_KeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, map_KeyOfT>::const_iterator const_iterator;pair<iterator, bool>  insert(const pair<K, V>& kv) {return _tree.insert(kv);}// 迭代器iterator begin() {return _tree.begin();}iterator end() {return _tree.end();}const_iterator begin() const {return _tree.begin();}const_iterator end() const {return _tree.end();}iterator find(const K& key) {return _tree.find(key);}V& operator[](const K& key) {pair<iterator, bool> pr = insert(make_pair(key, V()));return pr.first->second;}private:RBTree<K, pair<const K, V>, map_KeyOfT> _tree;
};