前面我们已经了解过红黑树如何实现，和map与set的基本用法；要继续深入了解map，set中的库函数的用法，与细节那么我们就可以试着简单用语言封装模拟实现一下map与set； 这里就分享一下我的思路；
若没了解过红黑树如何实现，和map与set的基本用法建议先去了解一下哦；我之前的文章中就有。
源码及框架分析
这里参考的是SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等几个个头文件中
通过看SGI的源代码我们可以发现，map和set是利用的同一个红黑树stl_tree.h，但它们的value参数根本不同，如何实现呢？
- 通过下图对框架的分析，我们可以看到源码中rb_tree用了⼀个巧妙的泛型思想实现，rb_tree无论是实现key的搜索场景，还是key/value的搜索场景不是直接写死的，二是由第二个模板参数Value决定_rb_tree_node中存储的数据类型。
- set实例化rb_tree时第二个模板参数给的是key，map实例化rb_tree时第二个模板参数给的是pair<const key, T>，这样一颗红黑树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。
- 这样写，解释了为什么set map利用的红黑树的value 根部不同但是却能使用同一个红黑树的原因
简化的源代码展示：
- 要注意⼀下，源码里面模板参数是用T代表value，而内部写的value_type不是我们我们日常key/value场景中说的value（不是关键字，内部值的意思），源码中的value_type反而是红黑树结点中存储的真实的数据的类型（参考上图 __rb_tree_node 参数和map的 模板参数T）。
- rb_tree第二个模板参数Value已经控制了红黑树结点中存储的数据类型，为什么还要传第一个模板参数Key呢？尤其是set，两个模板参数是一样的，这是很多同学这时的一个疑问。要注意的是对于map和set，find/erase时的函数参数都是Key（所以，也不能说加上这个key是冗余的），所以第一个模板参数是传给find/erase等函数做形参的类型的。对于set而言两个参数是⼀样的，但是对于map而言就完全不一样了，map insert的是pair对象，但是find和ease的是Key对象。
也可以这样说，set加模板参数key，是多余的；但是为了代码可读性，与map同用一个红黑树，set才加上了模板参数key
吐槽⼀下，这里源码命名风格比较乱，set模板参数用的Key命名，map用的是Key和T命名，而rb_tree用的又是Key和Value，可见⼤佬有时写代码也不规范。
模拟实现map和set
实现步骤大致如下：
- 实现红黑树
- 封装map和set框架，解决KeyOfT
- iterator
- const_iterator
- key不支持修改的问题
- operator[]
实现出复用红黑树的框架，并支持insert
- 参考源码框架，map和set复用之前我们实现的红黑树（忘记的的可以看完之前红黑树文章复习一下哦~）
- 这里相比源码调整⼀下，key参数就用K，value参数就用V，红黑树中的数据类型，我们使用T。
- 其次因为RBTree实现了泛型不知道T参数导致是K，还是pair<K, V>，那么insert内部进行插入逻辑比较时，就没办法进行比较，因为pair的默认支持的是key和value一起参与比较，我们需要时的任何时候只比较key，
所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进行比较。
自己实现的：
- 具体细节参考如下代码实现
//MYset.H #include"RBTree.h" namespace xryq { template<class K> class set { struct KeyofV { const K& operator()(const K& key) { return key; } }; public: /*typedef RBTreeNode<K, K> rbt;*/ pair<iterator, bool> Insert(const K& k) { return _t.Insert(k); } private: RBTree<K, K, KeyofV> _t; }; }MYmap.h #include"RBTree.h" namespace xryq { template<class K, class V> class map { struct KeyofV { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: //typedef RBTree<K, pair<K, V>, KeyOfV> rbt; pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); } private: RBTree<K, pair<const K, V>, KeyofV> _t; }; }#pragma once using namespace std; // 枚举值表⽰颜⾊ enum Color { Red, Black }; // 这⾥我们默认按key/value结构实现 template<class V> struct RBTreeNode { // 这⾥更新控制平衡也要加⼊parent指针 Color _col; V _kv; RBTreeNode<V>* _right; RBTreeNode<V>* _left; RBTreeNode<V>* _parent; RBTreeNode(V kv) :_kv(kv) , _right(nullptr) , _left(nullptr) , _parent(nullptr) {} }; template<class K, class V, class KeyOfValue> class RBTree { typedef RBTreeNode<V> Node; public: bool Insert(V value) { if (_root == nullptr) { _root = new Node(value); return true; } Node* parent = nullptr; Node* cur = _root; KeyOfValue kot; while (cur) { if (kot(cur->_kv) > kot(value)) { parent = cur; cur = cur->_left; } else if (kot(cur->_kv) < kot(value)) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(value); //需要记录，要返回插入的迭代器；cur在之后会变 Node* newnode = cur; cur->_col = Red; if (kot(cur->_kv) > kot(parent->_kv)) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; // 父亲是红色，出现连续的红色节点，需要处理 while (parent && parent->_col == Red) { Node* grandfather = parent->_parent; // g // p u if (grandfather->_left == parent) { // g // p u Node* uncle = grandfather->_right; if (uncle && uncle->_col == Red) { //改色 parent->_col = Black; uncle->_col = Black; grandfather->_col = Red; //循环 cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_left) { // g // p u // c RotateR(grandfather); parent->_col = Black; grandfather->_col = Red; } else if (cur == parent->_right) { // g // p u // c RotateL(parent); RotateR(grandfather); parent->_col = Black; grandfather->_col = Red; } //这种情况 p 是直接是黑 肯定是已经满足要求了 break; } } else if (grandfather->_right == cur->_parent) { // g // u p Node* uncle = grandfather->_left; if (uncle && uncle->_col == Red) { //改色 parent->_col = Black; uncle->_col = Black; grandfather->_col = Red; //循环 cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right) { // g // u p // c RotateL(grandfather); parent->_col = Black; grandfather->_col = Red; } else if (cur == parent->_left) { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = Black; grandfather->_col = Red; } //_root->_col = Black; //这种情况 p 是直接是黑 肯定是已经满足要求了 break; } } } _root->_col = Black; return true; } void RotateL(Node* grand) { Node* subR = grand->_right; Node* subRL = subR->_left; Node* pparent = grand->_parent; if (grand == _root) { _root = subR; subR->_parent = nullptr; } else { //subR节点 if (pparent->_left == grand) { pparent->_left = subR; } else { pparent->_right = subR; } subR->_parent = pparent; } //parent 节点 subR->_left = grand; if (subRL) subRL->_parent = grand; grand->_right = subRL; grand->_parent = subR; //subR->_col = Black; //grand->_col = Red; } void RotateR(Node* grand) { Node* subL = grand->_left; Node* subLR = subL->_right; Node* pparent = grand->_parent; grand->_left = subLR; if (subLR) subLR->_parent = grand; //parent 节点 subL->_right = grand; grand->_parent = subL; if (grand == _root) { _root = subL; subL->_parent = nullptr; } else { //subR节点 if (pparent->_left == grand) { pparent->_left = subL; } else { pparent->_right = subL; } subL->_parent = pparent; } //subL->_col = Black; //grand->_col = Red; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->_right; } else { return cur; } } return nullptr; } //bool Check(Node* root, int blackNum, const int refNum) //{ // if (root == nullptr) // { // if (blackNum == refNum) // return true; // else // { // cout << "存在黑色结点的数量不相等的路径" << endl; // return false; // } // } // // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了 // if (root->_col == Red && root->_parent->_col == Red) // { // return false; // } // if (root->_col == Black) // { // blackNum++; // } // return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); //} //bool IsBalance() //{ // //特殊情况不要忘记 // if (_root == nullptr) // { // return true; // } // if (_root->_col == Red) // { // return false; // } // // 参考值 // int refNum = 0; // Node* cur = _root; // while (cur) // { // if (cur->_col == Black) // { // refNum++; // } // cur = cur->_left; // } // return Check(_root, 0, refNum); //} //void InOrder() //{ // return _InOrder(_root); // cout << endl; //} //int Height() //{ // return _Height(_root); //} private: //void _InOrder(Node* root) //{ // if (root == nullptr) // { // return; // } // _InOrder(root->_left); // cout << root->_kv.first << ":" << root->_kv.second << endl; // _InOrder(root->_right); //} //int _Height(Node* root) //{ // if (root == nullptr) // return 0; // int HeightL = _Height(root->_left); // int HeightR = _Height(root->_right); // return HeightL > HeightR ? HeightL + 1 : HeightR + 1; //} Node* _root = nullptr; };
支持iterator的实现
- 在模拟实现map，set的iterator的时候，我建议大家可以回想，复习一下list的iterator是怎么实现的；如果一点都想不起来的话，我建议还是复习一下为好，因为这次实现的和list的模拟十分相似，而且我也不会在这多说细节~
- 基本的方法都是：模板会自动实现所传的值；也就是模板会传自己所映射的值；
如果想复习的话可以参考我之前关于list模拟的文章哦！
首先，大致看看源代码是如何实现的；
基本框架已经了解，那么这些重定义是怎么实现的？
iterator实现思路分析
- iterator实现的大框架跟list的iterator思路是⼀致的，用一个类型封装结点的指针（iterator），再通过重载运算符实现，迭代器像指针一样访问的行为。
- 这里的难点是operator++和operator--的实现。之前使用部分，我们分析了，map和set的迭代器走的是中序遍历，左子树->根结点->右子树，那么begin()会返回中序第一个结点的iterator也就是10所在结点的迭代器。
以这个图为例子分析：
- 迭代器++的核新逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点
- 迭代器++时，如果it指向的结点的右子树不为空，代表当前结点已经访问完了，要访问下⼀个结点是右子树的中序第一个，⼀棵树中序第一个是最左结点，所以直接找右子树的最左结点即可。
- 迭代器++时，如果it指向的结点的右子树空，代表当前结点已经访问完了且当前结点所在的子树也访问完了，要访问的下一个结点在当前结点的祖先里面，所以要沿着当前结点到根的祖先路径向上找。
如果当前结点是父亲的左，根据中序左子树->根结点->右子树，那么下一个访问的结点就是当前结点的父亲；
如图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。
如果当前结点是父亲的右，根据中序左子树->根结点->右子树，当前当前结点所在的子树访问完了，当前结点所在父亲的子树也访问完了，那么下一个访问的需要继续往根的祖先中去找，直到找到孩子是父亲左的那个祖先就是中序要问题的下一个结点。也就是循环思想（也可以递归，不过太麻烦），直到找到合适的关系为止。
如图：it指向15，15右为空，15是10的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个访问的结点就是18
- 总结的来说就是，++是找比他正好大的值；所以先看右子树是不是为空；
若右子树不为空：找右子树的最左节点，也就是右子树的最小值；
若右子树为空：从cur当前节点找parent节点，若找到parent->left == cur （也就是当前节点是父节点的左节点）那么 ++结果就是parent；若没有找到parent->left == cur，继续cur = parent寻找合适的节点满足这个关系；
- end()如何表示呢？
当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18到根没有父亲，没有找到孩子是父亲左的那个祖先，这是父亲为空了，那我们就把it中的结点指针置为nullptr，我们用nullptr去充当end。
需要注意的是stl源码空，红黑树增加了⼀个哨兵位头结点做为end()，这哨兵位头结点和根互为父亲，左指向最左结点，右指向最右结点。
解释：
这段代码就是stl源码中实现的哨兵位；和头节点同为父子关系；虽然看着能解决节点为end --和 ++ 成为end的问题；但是你要想，这个node哨兵位的实现，虽然实现了node->right为begin，node为end；但是如何维护呢？当我删除和添加节点时需要维护这层关系，所以为了简便，我们这里还是用nullptr作为end()。
相比我们用nullptr作为end()，差别不大，他能实现的，我们也能实现。只是--end()判断到结点时空，特殊处理⼀下，让迭代器结点指向最右结点。具体参考下面代码的迭代器--实现部分。
- 迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右子树->根结点->左子树，具体参考下面代码实现。
- 总结的来说就是，--是找比他正好大的值；所以先看左子树是不是为空；
若左子树不为空：找左子树的最右节点，也就是右子树的最大值；
若左子树为空：从cur当前节点找parent节点，若找到parent->right == cur （也就是当前节点是父节点的右节点）那么 --结果就是parent；若没有找到parent->right == cur，继续cur = parent寻找合适的节点满足这个关系；
- 实现的相关细节
- set的iterator也不支持修改，我们把set的第二个模板参数改成const K即可， RBTree<K,const K, SetKeyOfT> _t;
（要注意 在重定义iterator时，会用到 RBTree<K,const K, SetKeyOfT> 这个类型模板，不要忘记加const 例如：typedef typename RBTree<K,const K, KeyofV>::Iterator iterator;）
否则会报错
- map的iterator不支持修改key但是可以修改value，我们把map的第二个模板参数pair的第一个参数改成const K即可， RBTree<K, pair<const K, V>, MapKeyOfT> _t;
- 支持完整的迭代器还有很多细节需要修改，具体参考下面的代码。
- typename类型
map支持 [ ]
参考map的【】
- map要支持[ ]主要需要修改insert返回值支持，修改RBtree中的insert返回值为pair<Iterator, bool> Insert(const T& data)
- 有了insert⽀持[]实现就很简单了，具体参考下面代码实现
xyrq::map和xryq::set代码实现
Mymap.h
//Mymap.h
#pragma once
#include"RBTree.h"
namespace xryq
{
template<class K, class V>
class map
{
struct KeyofV
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typedef RBTree<K, pair<K, V>, KeyOfV> rbt;
typedef typename RBTree<K, pair<const K, V>, KeyofV>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, KeyofV>::ConstIterator const_iterator;
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, KeyofV> _t;
};
}
Myset.h
//Myset.h
#pragma once
#include"RBTree.h"
namespace xryq {
template<class K>
class set
{
struct KeyofV
{
const K& operator()(const K& key)
{
return key;
}
};
public:
/*typedef RBTreeNode<K, K> rbt;*/
/*typedef typename RBTree<K, K, KeyofV>::Iterator iterator;*/
typedef typename RBTree<K, K, KeyofV>::Iterator iterator;
typedef typename RBTree<K,const K, KeyofV>::ConstIterator const_iterator;
pair<iterator, bool> Insert(const K& k)
{
return _t.Insert(k);
}
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
private:
RBTree<K,const K, KeyofV> _t;
};
}RBTree.h
#pragma once
using namespace std;
// 枚举值表⽰颜⾊
enum Color {
Red,
Black
};
// 这⾥我们默认按key/value结构实现
template<class V>
struct RBTreeNode {
// 这⾥更新控制平衡也要加⼊parent指针
Color _col;
V _kv;
RBTreeNode<V>* _right;
RBTreeNode<V>* _left;
RBTreeNode<V>* _parent;
RBTreeNode(V kv)
:_kv(kv)
, _right(nullptr)
, _left(nullptr)
, _parent(nullptr)
{}
};
template<class V, class Ref, class Ptr>
struct RBTreeIterator {
typedef RBTreeNode<V> Node;
typedef RBTreeIterator<V, Ref, Ptr> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node, Node* root)
:_node(node)
, _root(root)
{}
Ref operator*()
{
return _node->_kv;
}
Ptr operator->()
{
return &(_node->_kv);
}
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 != nullptr)
{
// 右不为空，中序下一个访问的节点是右子树的最左(最小)节点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
//返回self 级 *this ++ 是自身也要改变的；
//self* ret = new self(cur);
//return ret;
_node = cur;
}
else
{
// 右为空，祖先里面孩子是父亲左的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left != cur)
{
cur = cur->_parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator--()
{
// end() 的值；
if (_node == nullptr)
{
//必须增加一个 root值，不如无法对 末迭代器 --
Node* cur = _root;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
return *this;
}
//左不为空 找左树的最大值， 左树的最右边
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->_right = cur)
{
cur = cur->_parent;
parent = cur->_right;
}
_node = parent;
}
return *this;
}
};
template<class K, class V, class KeyOfValue>
class RBTree {
typedef RBTreeNode<V> Node;
public:
typedef RBTreeIterator<V, V&, V*> Iterator;
typedef RBTreeIterator<V, const V&, const V*> ConstIterator;
Iterator Begin()
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
//Iterator it(cur, root);
//return it;
return Iterator(cur, _root);
}
Iterator End()
{
return Iterator(nullptr, _root);
}
ConstIterator Begin() const
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
//Iterator it(cur, root);
//return it;
return ConstIterator(cur, _root);
}
ConstIterator End() const
{
return ConstIterator(nullptr, _root);
}
pair<Iterator, bool> Insert(V value)
{
if (_root == nullptr)
{
_root = new Node(value);
return { Iterator(_root, _root) ,true };
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfValue kot;
while (cur)
{
if (kot(cur->_kv) > kot(value))
{
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_kv) < kot(value))
{
parent = cur;
cur = cur->_right;
}
else {
return { Iterator(cur,_root), false };
}
}
cur = new Node(value);
//需要记录，要返回插入的迭代器；cur在之后会变
Node* newnode = cur;
cur->_col = Red;
if (kot(cur->_kv) > kot(parent->_kv))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 父亲是红色，出现连续的红色节点，需要处理
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
// g
// p u
if (grandfather->_left == parent)
{
// g
// p u
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == Red)
{
//改色
parent->_col = Black;
uncle->_col = Black;
grandfather->_col = Red;
//循环
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
// g
// p u
// c
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
else if (cur == parent->_right)
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
//这种情况 p 是直接是黑 肯定是已经满足要求了
break;
}
}
else if (grandfather->_right == cur->_parent)
{
// g
// u p
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == Red)
{
//改色
parent->_col = Black;
uncle->_col = Black;
grandfather->_col = Red;
//循环
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
else if (cur == parent->_left)
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
//_root->_col = Black;
//这种情况 p 是直接是黑 肯定是已经满足要求了
break;
}
}
}
_root->_col = Black;
return make_pair(Iterator(newnode, _root), true );
}
void RotateL(Node* grand)
{
Node* subR = grand->_right;
Node* subRL = subR->_left;
Node* pparent = grand->_parent;
if (grand == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else {
//subR节点
if (pparent->_left == grand)
{
pparent->_left = subR;
}
else {
pparent->_right = subR;
}
subR->_parent = pparent;
}
//parent 节点
subR->_left = grand;
if (subRL)
subRL->_parent = grand;
grand->_right = subRL;
grand->_parent = subR;
//subR->_col = Black;
//grand->_col = Red;
}
void RotateR(Node* grand)
{
Node* subL = grand->_left;
Node* subLR = subL->_right;
Node* pparent = grand->_parent;
grand->_left = subLR;
if (subLR)
subLR->_parent = grand;
//parent 节点
subL->_right = grand;
grand->_parent = subL;
if (grand == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else {
//subR节点
if (pparent->_left == grand)
{
pparent->_left = subL;
}
else {
pparent->_right = subL;
}
subL->_parent = pparent;
}
//subL->_col = Black;
//grand->_col = Red;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else {
return cur;
}
}
return nullptr;
}
//bool Check(Node* root, int blackNum, const int refNum)
//{
// if (root == nullptr)
// {
// if (blackNum == refNum)
// return true;
// else
// {
// cout << "存在黑色结点的数量不相等的路径" << endl;
// return false;
// }
// }
// // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了
// if (root->_col == Red && root->_parent->_col == Red)
// {
// return false;
// }
// if (root->_col == Black)
// {
// blackNum++;
// }
// return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
//}
//bool IsBalance()
//{
// //特殊情况不要忘记
// if (_root == nullptr)
// {
// return true;
// }
// if (_root->_col == Red)
// {
// return false;
// }
// // 参考值
// int refNum = 0;
// Node* cur = _root;
// while (cur)
// {
// if (cur->_col == Black)
// {
// refNum++;
// }
// cur = cur->_left;
// }
// return Check(_root, 0, refNum);
//}
//void InOrder()
//{
// return _InOrder(_root);
// cout << endl;
//}
//int Height()
//{
// return _Height(_root);
//}
private:
//void _InOrder(Node* root)
//{
// if (root == nullptr)
// {
// return;
// }
// _InOrder(root->_left);
// cout << root->_kv.first << ":" << root->_kv.second << endl;
// _InOrder(root->_right);
//}
//int _Height(Node* root)
//{
// if (root == nullptr)
// return 0;
// int HeightL = _Height(root->_left);
// int HeightR = _Height(root->_right);
// return HeightL > HeightR ? HeightL + 1 : HeightR + 1;
//}
Node* _root = nullptr;
};
参考测试用例
void test1()
{
xryq::set<int> s;
s.Insert(5);
s.Insert(1);
s.Insert(3);
s.Insert(2);
s.Insert(6);
xryq::set<int>::iterator sit = s.begin();
*sit += 10;
while (sit != s.end())
{
cout << *sit << " ";
++sit;
}
cout << endl;
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;
}
void test2()
{
xryq::map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
dict["left"] = "左边，剩余";
dict["insert"] = "插入";
dict["string"];
xryq::map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
// 不能修改first，可以修改second
//it->first += 'x';
it->second += 'x';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
}