【C++】set和map的封装

可以看到，我们看到的set只用传递一个类型就可以了，我们之前常说的Key类型，而map则需要传递两个类型，即我们之前说的Key_Value类型。但是实际上并不是这样，其实在库中实现的set和map的底层其实都是Key_Vaule类型的，底层都是通过一颗Key_Vaule类型的红黑树实现的，如下所示，库中的一些关键代码;

通过这个图，我们可以知道：库中的set和map都是通过库中Key_Vaule类型的红黑树实现的：

其中set虽然在外面是一个Key型（即set<Key>），但实际实现的时候，是通过一个红黑树的 rb_tree<Key，Key> 结构封装实现的；
而map则是在外面接收两个类型（即map<Key, Value>），但实际上是通过红黑树的rb_tree<Key，pair<Key, Vaule>> 结构封装实现的。

简化一下就是这样的：

二、修改红黑树

通过上面我们知道，set和map使用的都是同一种树，只是传递的第二个模板参数不同而已，set是<Key,Key>，而map是<Key, pair<Key, Value>>。

其中第一个模板参数Key的主要作用是用于确定查找类型。
而第二个模板参数是用于确定我们的存储类型，我们在树中插入数据的时候比较的就是第二个参数。

1. 节点定义

由于set存储的是Key类型，而map存储的是pair<Key, Value> 类型，所以我们在定义红黑树时，需要将它修改为都可以存储，这我们可以将红黑树节点的模板实现一个泛型存储，代码如下：

enum Colour { RED,BLACK }; template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col; T _data; // 不论是Key还是pair类型都可以存储 RBTreeNode(const T& data) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) //新节点的默认颜色是红色 { } };

在树中，定义也要改变，如下所示：

template<class K, class T> class RBTree { typedef RBTreeNode<T> Node; //结点中存储类型与第二个模板参数有关 public: //插入 bool Insert(const T& date) { // ...... } private: Node* _root = nullptr; };

注意：这里红黑树的类的模板参数虽然为两个，当时后面还会增加的。

2. 插入操作

由于我们节点中的存储类型是一个泛型的 T 类型，所以在树的插入操作中，当我们需要比较的时候，比较的应该是Key值，在set传递的第二个模板参数就是key，而map传递的第二个模板参数传递的应该是pair<key, value>，这时就需要取出pair中first的key来进行比较，要解决这个问题，我们可以通过在set和map这一层传递第三个模板参数给红黑树：

对于set，取出的就是key本身；
而对于map，取出的则是pair中的第一个参数key。

这第三个模板参数传递的是一个仿函数的类：重载了（）的类。

在 set 中实现一个内部类，用来获取 key 的本身：

#pragma once #include"RBTree.h" namespace MyCreate { template<class K> class set { struct SetKeyOfT { // 获取key中的key本身 const K& operator()(const K& key) { return key; } }; private: RBTree<K, K, SetKeyOfT> _t; }; }

在 map 中，树中的 T 是 pair ，这样我们需要取出 pair 中的 fist 作为 key ，代码如下：

#pragma once #include"RBTree.h" namespace MyCreate { template<class K, class V> class map { struct MapKeyOfT { // 获取pair<K,V>中的key const K& operator()(const pair<K, V>& kv) { return kv.first; } }; private: RBTree<K, pair<K,V>, MapKeyOfT> _t; }; }

最后，我们需要修改红黑树的插入操作：每当需要比较插入的值时，都需要定义第三个模板参数的类型，通过这个类型来获取 T 的 key 值进行比较，这样不论是set还是map，都可以成功插入数据了。如下所示：

template<class K, class T, class KetOfT> class RBTree { typedef RBTreeNode<T> Node; public: //插入 bool Insert(const T& date) { //1.树为空，直接插入 if (_root == nullptr) { _root = new Node(date); _root->_col = BLACK; return true; } KetOfT kot; // 定义取出T中的Key //2.树不为空，则寻找要插入的位置 Node* cur = _root; Node* parent = nullptr; 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 false; //已经存在，插入失败 } } cur = new Node(data); if (kot(parent->_data) < kot(parent->_data)) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; //但这里就,结点就在树中了 //插入红结点，需要判断和调整 while (parent && parent->_col == RED) // 如果父亲存在且为红，说明有两个连续的红结点，需要继续调整 { Node* grandparent = parent->_parent; if (parent == grandparent->_left) // parent在grandparent的左边 { Node* uncle = grandparent->_right; if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新 { //变色 parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //继续向上更新 cur = grandparent; parent = grandparent->_parent; } else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色 { if(cur == parent->_left) { // g(黑) // p(红) --> p(黑) // c(红) c(红) g(红) // 右单旋 RotateR(grandparent); //变色 parent->_col = BLACK; grandparent->_col = RED; } else { // g(黑) g(黑) // p(红) --> c(红) --> c(黑) // c(红) p(红) p(红) g(红) // 先左单旋，再右单旋 RotateL(parent); RotateR(grandparent); // 变色 grandparent->_col = RED; cur->_col = BLACK; } break; } } else // parent在grandparent的右边 { Node* uncle = grandparent->_left; if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新 { //变色 parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //继续向上更新 cur = grandparent; parent = grandparent->_parent; } else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色 { if (cur == parent->_right) { // g(黑) // p(红) --> p(黑) // c(红) g(红) c(红) // 左单旋 RotateL(grandparent); //变色 parent->_col = BLACK; grandparent->_col = RED; } else { // g(黑) g(黑) // p(红) --> c(红) --> c(黑) // c(红) p(红) g(红) p(红) // 先右单旋，再左单旋 RotateR(parent); RotateL(grandparent); // 变色 grandparent->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return true; } private: Node* _root = nullptr; };

这样我们红黑树的插入操作修改就大致完成了。但这里并不是最终的结构。因为返回值我们来没有修改。

注意：后续再实现重载 [ ] 的时候还需要修改一下它的返回值，因为这需要使用到我们实现的迭代器，所以就在实现重载 [ ] 的时候再说。

三、红黑树迭代器的实现

上一张我们没有实现红黑树的迭代器，这里我们就可以来实现一下。

1. 迭代器的定义

红黑树的迭代器，我们需要实现普通迭代器和const迭代器，所以首先我们就需要三个模板参数（用于方便实现const迭代器）。红黑树是树，所以其迭代器也就是节点指针，所以迭代器的基本定义如下所示：

//实现红黑树的迭代器 template<class T, class Ref, class Ptr> struct __TreeIterator { typedef RBTreeNode<T> Node; // 树的节点指针 typedef __TreeIterator<T, Ref, Ptr> Self; // 将该类型重定义一下,方便书写 __TreeIterator(Node* node) :_node(node) { } };

2. * 重载和 -> 重载

实现 * 重载的函数需要使用到第二个模板参数Ref ，这样可以保证：

当定义迭代器是传递的第二个模板参数是 T& 时，是普通迭代器；
如果第二个模板参数是 const T& 时，是const迭代器

所以 * 重载的代码如下所示：

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

实现 -> 重载的函数需要使用到第三个模板参数Ref ，这样可以保证：

当定义迭代器是传递的第三个模板参数是 T* 时，是普通迭代器；
如果第三个模板参数是const T*时，是const迭代器

-> 重载的代码如下所示：

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

3. 重载 != 和 ==

关于!=和==的重载很简单，只需要比较两个指针是否相等即可，实现代码如下所示：

// 迭代器与迭代器比较 bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; }

4. 重载 ++ 和 --

红黑树的自增就是：红黑树的中序遍历的顺序。而--则是反着中序遍历的顺序。

对于 ++ 的操作：

如果右孩子不为空，则访问右子树的最左节点；
如果右孩子为空，则需要向上找到：第一个孩子是父亲左孩子的节点，此时它的父亲就是下一个访问的节点。如果遇到其父亲为空时，此时parent就是根节点的父亲，则这就说明都访问完了。

所以前置++的函数重载实现代码如下所示：

Self& operator++() // 前置++ { if (_node->_right) { // 如果右孩子不为空，则访问右孩子最左节点 Node* cur = _node->_right; while (cur->_left) { cur = cur->_left; } _node = cur; } else { // 如果右孩子为空，则需要向上找到： // 第一个孩子是父亲左孩子的节点，其父亲就是下一个访问的节点 Node* cur = _node; Node* parent = cur-> _parent; while (parent && cur == parent->_right) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; }

如果是后置++，则需要添加一个int参数，实现的时候需要先保存在处理，最后返回的就是先保存的数据。

对于前置--，同理：

如果左孩子不为空，则访问左子树的最右节点；
如果左孩子为空，则需要向上找到：第一个孩子是父亲右孩子的节点，此时它的父亲就是下一个访问的节点。

则前置 -- 的代码实现如下所示：

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; }

5. 普通迭代器和const迭代器

我们实现了如实所示的迭代器操作之后，那么在红黑树中，我们就可以分别实现普通迭代器和const迭代器了，通过传递对应的模板参数，就可以实现对应的类型迭代器。如下所示：

template<class K, class T, class KetOfT> class RBTree { typedef __TreeIterator<T, T&, T*> iterator; // 普通迭代器 typedef __TreeIterator<T, const T&, const T*> const_iterator; // const迭代器 // ...... }；

然后实现红黑树迭代器的begin和end函数，代码如下所示：

// 普通迭代器 iterator begin() { // 红黑树的第一个节点是左子树的最左节点 Node* cur = _root; while (cur->_right) { cur = cur->_right; } return iterator(cur); } iterator end() { return iterator(nullptr); } // const迭代器 const_iterator begin() { // 红黑树的第一个节点是左子树的最左节点 Node* cur = _root; while (cur->_right) { cur = cur->_right; } return const_iterator(cur); } const_iterator end() { return const_iterator(nullptr); }

四、set和map的封装

1. 迭代器的封装

（1）set迭代器

对于set 而言，只有key，并且key是不能被修改的，所以，set的当前本质上还是const迭代器。我们先来看看库中是怎么实现的，如下图所示：

在stl库中，是将const迭代器也作为了普通迭代器来解决这个问题的：不管是普通还是const，使用的都是红黑树中的const迭代器。所以我们实现set的迭代器就可以如下所示（注意：这里的错误的代码）：

// MySet.h #pragma once #include"RBTree.h" namespace MyCreate { template<class K> class set { struct SetKeyOfT { // 获取key中的key本身 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() { return _t.begin(); } iterator end() { return _t.end(); } private: RBTree<K, K, SetKeyOfT> _t; }; }

但是如果真的这样写，就会出现一些问题，运行后，会报错，即：

原因如下：

要解决这个问题，我们可以在begin和end的后面都加上const修饰，这样就只会调用树里的const迭代器了（库里面也是这样实现的）。所以正确的代码实现如下所示：

// MySet.h #pragma once #include"RBTree.h" namespace MyCreate { template<class K> class set { struct SetKeyOfT { // 获取key中的key本身 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(); } bool insert(const K& key) { return _t.Insert(key); //对于set插入的就是key } private: RBTree<K, K, SetKeyOfT> _t; }; }

（2）map迭代器

map调用的时候是要传递两个参数，即<Key, Value> ，在我们使用的时候，map中的Key是不可以改变的，但Value是可以改变的。在实现map的这一层，我们是通过Key_Value型的红黑树实现的，而map中传递给红黑树的模板参数是<Key, pair<Key, Value>>型的。也就是说，我们要控制最外层的map的Key不能改变，但Value可以改变，就需要修改实现红黑树的时候，红黑树的第二个模板参数是pair型，要保证此时的pair型中的first不可以修改，但second可以改变。总结一下：

那么我们要如何实现这样呢？

实现这个，也很简单，要修改的有一些两点：

map的迭代器就和常规实现迭代器一样，普通迭代器（map层）就是普通迭代器（红黑树层），const迭代器（map层）就是const迭代器（红黑树层）。如下所示：

// MyMap.h #pragma once #include"RBTree.h" namespace MyCreate { template<class K, class V> class map { struct MapKeyOfT { // 获取pair<K,V>中的key 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(); } //const迭代器 const_iterator begin() const { return _t.begin(); } const_iterator end() const{ return _t.end(); } bool insert(const pair<K, V>& kv) { return _t.Insert(kv); //对于map插入的就是pair<k,v> } private: RBTree<K, pair<K,V>, MapKeyOfT> _t; }; }

只是这样当然不行，还需要修改一下其中的pair的K，将K改为const K，就可以了，即：pair<K, V>修改为pair<const K, V>即可。正确的代码实现如下所示：

// MyMap.h #pragma once #include"RBTree.h" namespace MyCreate { template<class K, class V> class map { struct MapKeyOfT { // 获取pair<K,V>中的key 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迭代器 const_iterator begin() const { return _t.begin(); } const_iterator end() const{ return _t.end(); } private: RBTree<K, pair<const K,V>, MapKeyOfT> _t; }; }

这样，那我们实现map后，如果是普通迭代器，则key不能修改，value可以修改，如果是const迭代器，则key和value都不能修改。

2. map的[ ] 重载实现

通过查看map文档，我们知道，map的[ ]重载需要先进行插入k的操作：

如果k已经在树里面了，这时插入的返回值ret就是pair<树里面的k所在节点的迭代器iterator, false>；
如果k不在树里面，这时插入的返回值ret就是pair<新插入k所在节点的迭代器iterator, false>；

然后再返回ret中的first迭代器对应的second的引用。

如下图所示：

分开就是：

所以，在实现 [ ] 重载函数之前，我们还需要实现返回值为pair<iterator，bool>类型的插入函数，只用修改上述红黑树的插入函数的返回值即可，实现代码如下所示：

//插入 pair<iterator, bool> Insert(const T& data) { //1.树为空，直接插入 if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } KetOfT kot; //2.树不为空，则寻找要插入的位置 Node* cur = _root; Node* parent = nullptr; 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(cur->_data)) { parent->_right = cur; } else { parent->_left = cur; } Node* newnode = cur; //保存一下插入节点的位置 cur->_parent = parent; //但这里就,结点就在树中了 //插入红结点，需要判断和调整 while (parent && parent->_col == RED) // 如果父亲存在且为红，说明有两个连续的红结点，需要继续调整 { Node* grandparent = parent->_parent; if (parent == grandparent->_left) // parent在grandparent的左边 { Node* uncle = grandparent->_right; if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新 { //变色 parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //继续向上更新 cur = grandparent; parent = grandparent->_parent; } else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色 { if(cur == parent->_left) { // g(黑) // p(红) --> p(黑) // c(红) c(红) g(红) // 右单旋 RotateR(grandparent); //变色 parent->_col = BLACK; grandparent->_col = RED; } else { // g(黑) g(黑) // p(红) --> c(红) --> c(黑) // c(红) p(红) p(红) g(红) // 先左单旋，再右单旋 RotateL(parent); RotateR(grandparent); // 变色 grandparent->_col = RED; cur->_col = BLACK; } break; } } else // parent在grandparent的右边 { Node* uncle = grandparent->_left; if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新 { //变色 parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //继续向上更新 cur = grandparent; parent = grandparent->_parent; } else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色 { if (cur == parent->_right) { // g(黑) // p(红) --> p(黑) // c(红) g(红) c(红) // 左单旋 RotateL(grandparent); //变色 parent->_col = BLACK; grandparent->_col = RED; } else { // g(黑) g(黑) // p(红) --> c(红) --> c(黑) // c(红) p(红) g(红) p(红) // 先右单旋，再左单旋 RotateR(parent); RotateL(grandparent); // 变色 grandparent->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return make_pair(iterator(newnode), true); }

最后，在MyMap.h中实现我们自己map的 [ ] 重载函数，实现代码如下所示：

#pragma once #include"RBTree.h" namespace MyCreate { template<class K, class V> class map { struct MapKeyOfT { // 获取pair<K,V>中的key 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; // [ ] 重载函数 V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.first->second; } private: RBTree<K, pair<const K,V>, MapKeyOfT> _t; }; }

3. 插入操作的封装

set和map的插入操作，都是只需要调用红黑树的插入成员函数就可以了。

但是由于我们之前实现 [ ] 重载函数时，将insert插入函数的返回值改成了pair<iterator, bool>，所以我们实现的set中的插入函数，就有一些细节需要考虑了，如下所示：如果我们调用红黑树的插入函数：

出现这种错误的原因是因为：在set实现层，所有的迭代器都是const迭代器，，所以这里的iterator也是const迭代器，而我们调用的红黑树中插入函数返回的pair第一个迭代器返回的是红黑树中的普通迭代器，所以，这里就会出现普通迭代器转换成const迭代器的情况，由于它们类型不同不可以转换，所以才会出错，因此我们的解决办法就是：先试用一个pair<普通迭代器，bool>类型的变量来接收返回值，再使用这个这个pair的普通迭代器fist和布尔值second来构造，实现代码如下所示：

// MySet.h #pragma once #include"RBTree.h" namespace MyCreate { template<class K> class set { struct SetKeyOfT { // 获取key中的key本身 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; pair<iterator, bool> insert(const K& key) { //对于set插入的就是key pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); // 使用普通迭代器的pair来接收 // 使用普通pair中的迭代器first来构造当前的const迭代器 return pair<iterator, bool>(ret.first, ret.second); } private: RBTree<K, K, SetKeyOfT> _t; }; }

要注意：如果我们这样使用，那么我们就需要对在红黑树中熟悉的迭代器添加一个构造函数，即：

五、最终代码

RBTree.h

#pragma once enum Colour { RED,BLACK }; template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col; T _data; // 不论是Key还是pair类型都可以存储 RBTreeNode(const T& data) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) //新节点的默认颜色是红色 { } }; //实现红黑树的迭代器 template<class T, class Ref, class Ptr> struct __TreeIterator { typedef RBTreeNode<T> Node; Node* _node; // 树的节点指针 typedef __TreeIterator<T, Ref, Ptr> Self; // 将该类型重定义一下,方便书写 typedef __TreeIterator<T, T&, T*> Iterator; //表示当前的普通迭代器 __TreeIterator(const Iterator& it) :_node(it._node) { } __TreeIterator(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; } Self& operator++() // 前置++ { if (_node->_right) { // 如果右孩子不为空，则访问右子树的最左节点 Node* cur = _node->_right; while (cur->_left) { cur = cur->_left; } _node = cur; } else { // 如果右孩子为空，则需要向上找到： // 第一个孩子是父亲左孩子的节点，此时它的父亲就是下一个访问的节点 Node* cur = _node; Node* parent = cur-> _parent; while (parent && cur == parent->_right) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } 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; } }; template<class K, class T, class KetOfT> class RBTree { typedef RBTreeNode<T> Node; public: typedef __TreeIterator<T, T&, T*> iterator; // 普通迭代器 typedef __TreeIterator<T, const T&, const T*> const_iterator; // const迭代器 // 普通迭代器 iterator begin() { // 红黑树的第一个节点是左子树的最左节点 Node* cur = _root; while (cur->_left) { cur = cur->_left; } return iterator(cur); } iterator end() { return iterator(nullptr); } // const迭代器 const_iterator begin() const { // 红黑树的第一个节点是左子树的最左节点 Node* cur = _root; while (cur->_left) { cur = cur->_left; } return const_iterator(cur); } const_iterator end() const { return const_iterator(nullptr); } //插入 pair<iterator, bool> Insert(const T& data) { //1.树为空，直接插入 if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } KetOfT kot; //2.树不为空，则寻找要插入的位置 Node* cur = _root; Node* parent = nullptr; 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(cur->_data)) { parent->_right = cur; } else { parent->_left = cur; } Node* newnode = cur; //保存一下插入节点的位置 cur->_parent = parent; //但这里就,结点就在树中了 //插入红结点，需要判断和调整 while (parent && parent->_col == RED) // 如果父亲存在且为红，说明有两个连续的红结点，需要继续调整 { Node* grandparent = parent->_parent; if (parent == grandparent->_left) // parent在grandparent的左边 { Node* uncle = grandparent->_right; if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新 { //变色 parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //继续向上更新 cur = grandparent; parent = grandparent->_parent; } else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色 { if(cur == parent->_left) { // g(黑) // p(红) --> p(黑) // c(红) c(红) g(红) // 右单旋 RotateR(grandparent); //变色 parent->_col = BLACK; grandparent->_col = RED; } else { // g(黑) g(黑) // p(红) --> c(红) --> c(黑) // c(红) p(红) p(红) g(红) // 先左单旋，再右单旋 RotateL(parent); RotateR(grandparent); // 变色 grandparent->_col = RED; cur->_col = BLACK; } break; } } else // parent在grandparent的右边 { Node* uncle = grandparent->_left; if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新 { //变色 parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //继续向上更新 cur = grandparent; parent = grandparent->_parent; } else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色 { if (cur == parent->_right) { // g(黑) // p(红) --> p(黑) // c(红) g(红) c(红) // 左单旋 RotateL(grandparent); //变色 parent->_col = BLACK; grandparent->_col = RED; } else { // g(黑) g(黑) // p(红) --> c(红) --> c(黑) // c(红) p(红) g(红) p(红) // 先右单旋，再左单旋 RotateR(parent); RotateL(grandparent); // 变色 grandparent->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return make_pair(iterator(newnode), true); } void RotateL(Node* parent) //左单旋 { Node* cur = parent->_right; Node* curleft = cur->_left; Node* ppnode = parent->_parent; // 判断parent是根结点的情况 parent->_right = curleft; if (curleft != nullptr) { curleft->_parent = parent; } cur->_left = parent; parent->_parent = cur; if (ppnode == nullptr) { //说明parent是根结点 _root = cur; cur->_parent = nullptr; } else { //parent是子树的情况 if (ppnode->_left == parent) { //是左子树 ppnode->_left = cur; } else { //是右子树 ppnode->_right = cur; } cur->_parent = ppnode; } } void RotateR(Node* parent) //右单旋 { Node* cur = parent->_left; Node* curright = cur->_right; Node* ppnode = parent->_parent; parent->_left = curright; if (curright != nullptr) { curright->_parent = parent; } cur->_right = parent; parent->_parent = cur; //判断是否parent为根结点 if (ppnode == nullptr) { //改变根结点 _root = cur; cur->_parent = nullptr; } else { //parent为子树 if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } } private: Node* _root = nullptr; };

MySet.h

#pragma once #include"RBTree.h" namespace MyCreate { template<class K> class set { struct SetKeyOfT { // 获取key中的key本身 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) { //对于set插入的就是key pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); // 使用普通迭代器的pair来接收 // 使用普通pair中的迭代器first来构造当前的const迭代器 return pair<iterator, bool>(ret.first, ret.second); } private: RBTree<K, K, SetKeyOfT> _t; }; }

MyMap.h

#pragma once #include"RBTree.h" namespace MyCreate { template<class K, class V> class map { struct MapKeyOfT { // 获取pair<K,V>中的key 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迭代器 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); //对于map插入的就是pair<k,v> } V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.first->second; } private: RBTree<K, pair<const K,V>, MapKeyOfT> _t; }; }

感谢各位观看！希望能多多支持