map和set

通过观察stl的底层我们可以看见，map和set是通过红黑树实现的。

通过观察这些typedef就可以看到，map和set的封装基本都是套用的红黑树的迭代器来封装实现的，所以我们的map和set也可以通过完成的红黑树来进行封装。

map

map的框架

通过看stl的框架，我们可以看到set实际传递了两个key，但是两个key的重命名是不一样的，map也传递了两个key，第一个key是key，第二个key是pair，所以这里我们在搭建框架的时候，我们可以根据stl的底层的框架进行搭建。

namespace lyrics
{template<class K,class V>class map{public:private:RBTree<K, pair<const K, V>> _t;};
}

根据stl的源代码，map的框架可以简化为上面这种。
为什么要传递第一个参数呢？

因为虽然只传递一个参数，对于set来说没什么影响，但是如果我们想用一个红黑树来封装两个容器的话，这其实是有影响的，因为在比较的时候，set确实不会有影响，但是map在比较的时候，比较逻辑是通过k来比较而并非通过pair来比较，还有就是查找的话，查找set也可以通过一个模版参数来办到，但是对于map来说，查找也是通过pair的first来查找的，所以这里我们应该传递两个参数，第一个参数用于查找和比较，第二个参数用于插入。

迭代器

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T,Ref,Ptr> Self;//迭代器Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root) :_node(node), _root(root) {}
};

先创建一个迭代器类，由于这里我们取不到原本红黑树中的root所以我们这里初始化的时候多传递一个参数，在这个迭代器类中多了一个参数root就是用来取原本红黑树中的root的。

operator++()

Self& operator++()
{//要找到当前节点的右子树的最左节点，因为遍历到当前节点说明左子树已经走完了if (_node->_right){Node* leftMost = _node->_right;while (leftMost->_left)leftMost = leftMost->_left;_node = leftMost;}//右为空，代表这棵树已经访问完了，所以应该找到父亲，因为当前节点是父亲的左子树//所以左 中 右//下一个访问的节点应该是访问祖先else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

我们可以通过上面的红黑树来观察，假设当前遍历到的节点就是13，由于红黑树的遍历是中序遍历，所以可是知道，当前左子树已经遍历完了，所以所以下一个节点只看能在右子树，++求的是下一个节点，肯定是求右子树最小的节点，所以就是当前节点的右子树的最左节点。

如果右子树为空，我们来看看这种情况假设我们当前节点是66，右子树是空的节点，再假设，当前节点是父亲的右子树，如果当前节点是父亲的右子树，那么说明当前节点连带父亲的左子树和右子树都已经访问完了，所以应该向上进行遍历，将当前节点移动到父亲的位置，继续向上遍历，当当前节点是父亲的左子树的节点的时候就不需要在遍历了，因为遍历顺序是左中右，所以左的下一个节点就是右就是当前的父亲节点

operator–()

Self& operator--()
{//_node是空，代表是endif (_node == nullptr){//end--，则取的就是最右节点，也就是整棵树的最大节点Node* rightMost = _root;//找到左子树的最右节点while (rightMost && rightMost->_right)rightMost = rightMost->_right;_node = rightMost;}//--是左子树的最右节点else if (_node->_left){Node* rightMost = _node->_left;//找到左子树的最右节点while (rightMost->_right) rightMost = rightMost->_right;_node = rightMost;}//如果左为空else{Node* cur = _node;Node* parent = cur->_parent;//因为是反过来的，所以是右根左while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

–的操作其实是和++相似的，但是需要注意的是：

–的顺序是右中左，而不是左中右，如果是右中左的话，我们假设当前节点是13，那么–的话上一个节点就是11，–应该是求的是比当前节点小的最大的一个节点，所以比当前节点小，所以应该是当前节点的左子树，又是最大的，所以应该是当前节点的左子树的最右的节点。

但是有可能左子树是空树，所以我们我们拿上面的那个红黑树的图来举例，当节点是22的时候，可以看见左子树是空的，所以所以这时候应该去找父节点，如果当前节点是父节点的左节点，那么继续向上找，因为是左节点，由于是右中左，所以左节点访问完之后，连同当前节点的父节点和右子树的节点已经访问完了，所以应该将当前节点遍历到父节点继续向上找，如果当前节点是父节点的右节点的话，那么就可以停下来不用找了，因为遍历的顺序是右中左，当前节点是父节点的右节点，说明下一个节点是父节点，所以不用找了，直接返回父节点就可以了。

==注意：这里有一个特殊情况，当节点是end()的时候，需要特殊处理，因为对于第一段逻辑来说，我们需要去访问node的left，这里我们访问空指针的成员已经报错了，所以这里要对空指针进行特殊处理：

这里就体现出来我们在初始化迭代器的时候传递root的重要性了，这里空指针的情况，我们直接取最右节点，也就是整棵树最大的节点。

operator==()和operator!=()

//！=
bool operator!=(const Self& s) const
{return _node != s._node;//迭代器比较就是两个指针相不相等
}
//==
bool operator==(const Self& s) const
{return _node == s._node;
}

operator*()

//返回节点中的data
Ref operator*()
{return _node->_data;//data是T&
}

operator->()

//pair的迭代器可以访问first和second
Ptr operator->()
{return &(_node->_data);
}

insert

我们先看看之前的insert的代码：

首先可以看见的是我们之前的红黑树是写的比较死的，适用的范围很小，为了，让其更模版话，我们可以将实际需要插入的类型用一个模版类型T来表示。

修改之后可以看见，这种形式，在传参的时候只需要根据是map或者是set来看传递pair还是传递K。

但是我们接着来看红黑树的代码，可以发现，我们之前写的比较逻辑都是通过pair的比较逻辑去比较的，这里就涉及到一个问题，我们现在的data换成T了，所以之前比较的逻辑就不符合语法了。

可以看看之前的部分的比较逻辑，上面的比较逻辑是基于值是pair的时候成立的，但是现在我们需要的是能适用于map和set的两个容器的比较，所以这里我们必须进行修改，最好的办法就是我们需要传递一个类仿函数，我们将他以模版参数的形式传递，在map和set中写一个类仿函数，然后分别传递到红黑树中，这里就多出来了第三个模版参数。

namespace lyrics
{template<class K,class V>class map{public:private:RBTree<K, pair<const K, V>，MapKeyOfT> _t;};
}

这里第三个参数传递的是一个类仿函数，所以这里我们先写一个仿函数，这里我们写的目的就是要得到map中的pair的first。

struct MapKeyOfT
{const K& operator()(const pair < K, V>& kv){return kv.first;}
};

这样我们就可以取到map中pair的第一个了。
接下来比较就方便多了，我们只需要创建一个对象即可，然后调用operator()()即可，接下来我们尝试改写一个insert的逻辑

将下面的代码的比较逻辑用这种方式进行修改之后的insert就适用于map和set了，但是在我们查看官方文档之后可以看到官方文档中的insert的返回值是pair<iterator,bool>，所以这里我们也应该修改成和官方文档相同的返回值，这样有利于我们后面封装operator[] ()，所以改完之后整体就是下面的：

pair<Iterator,bool> Insert(const T& data)
{//根节点是空时，判断一下if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root,_root), true);}//遍历节点,找到插入位置Node* cur = _root;Node* parent = nullptr;KeyOfT kot;while (cur){//比当前节点大小就去左子树if (kot(cur->_data) > kot(data))//这里调用operator(){parent = cur;cur = cur->_left;}//比当前节点大就去右子树else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}//插入失败返回falseelse return make_pair(Iterator(cur, _root), false);}cur = new Node(data);Node* newnode = cur;cur->_col = RED;//新增节点颜色给红色if (kot(parent->_data) < kot(data)) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;//父亲是红色继续向上改变颜色while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;//叔叔存在为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//改变指向cur = grandparent;parent = cur->_parent;}//叔叔不存在或者叔叔存在且为黑else{//单旋加变色if (cur == parent->_left){RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//双旋else{//双旋RotateL(parent);RotateR(grandparent);//双旋之后cur和parent是交换了，所以cur充当根cur->_col = BLACK;grandparent->_col = RED;}//第一个节点是黑色节点，所以可以直接结束break;}}else{Node* uncle = grandparent->_left;//叔叔存在为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//改变指向,向上更新cur = grandparent;parent = cur->_parent;}//叔叔不存在或者叔叔存在且为黑else{//单旋加变色if (cur == parent->_right){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//双旋else{//双旋RotateR(parent);RotateL(grandparent);//双旋之后cur和parent是交换了，所以cur充当根cur->_col = BLACK;grandparent->_col = RED;}//第一个节点是黑色节点，所以可以直接结束break;}}}//暴力处理根节点的颜色_root->_col = BLACK;//父亲的颜色是黑色直接结束return make_pair(Iterator(newnode, _root), true);
}

map的insert：

pair<iterator,bool> Insert(const pair<K, V>& kv)
{return _t.Insert(kv);
}

begin()

Iterator Begin()
{Node* leftSub = _root;//最左节点就是第一个while (leftSub && leftSub->_left != nullptr)//找到最左节点leftSub = leftSub->_left;return Iterator(leftSub, _root);//用最左节点构造一个begin
}
ConstIterator Begin() const
{Node* leftSub = _root;//最左节点就是第一个while (leftSub && leftSub->_left != nullptr)//找到最左节点leftSub = leftSub->_left;return ConstIterator(leftSub, _root);//用最左节点构造一个begin
}

begin需要封装两个一个是const的begin一个是非const的迭代器。
begin很简单，begin就是取到最小的，如果当前节点不是nullptr直接访问这棵树的最左节点返回最左节点即可。
对map封装：

iterator begin()
{return _t.Begin();
}
const_iterator begin()const
{return _t.Begin();
}

end()

//用空代表end
ConstIterator End()const 
{return ConstIterator(nullptr, _root);//引用nullptr构造一个迭代器
}
Iterator End()
{return Iterator(nullptr, _root);//引用nullptr构造一个迭代器
}

end()我们可以直接返回nullptr。

对map进行封装：

iterator end()
{return _t.End();
}
const_iterator end()const
{return _t.End();
}

operator[] ()

这个我们查看官方文档可以看见：

这个operator[] ()是用insert来封装的，所以我们接下来不管三七二十一先取出来当前key对应的值

V& operator[](const K& key)
{pair<iterator, bool> ret = Insert(make_pair(key, V()));//这里第二个参数给缺省值，有可能插入成功，有可能插入失败return ret.first->second;
}

map的所有代码：

namespace lyrics
{template<class K,class V>class map{struct MapKeyOfT{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>::ConstIterator const_iterator;//这里底层取的是const key//这里取const，上层就不能修改，set也可以用两个const迭代器iterator begin(){return _t.Begin();}iterator end(){return _t.End();}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);}iterator find(const K& key){return _t.Find();}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;};
}

set的封装

set的封装和map的如出一辙，甚至比map的简单

namespace lyrics
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://因为类模版没有被实例化，所以没有被实例化//加上typename就表示等实例化之后去里面将其替换掉typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;//第二个K是给给底层的data用的，所以data不能修改，所以只用给第二个模版参数加上const就可以了typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;iterator begin(){return _t.Begin();//调用RBTree的begin，只是套一层壳子而已}const_iterator begin()const{return _t.Begin();//调用RBTree的begin，只是套一层壳子而已}iterator end(){return _t.End();}const_iterator end()const{return _t.End();}pair<iterator,bool> Insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};
}

迭代器的封装

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T,Ref,Ptr> Self;//迭代器Node* _node;Node* _root;//返回节点中的dataRef operator*(){return _node->_data;//data是T&}//pair的迭代器可以访问first和secondPtr operator->(){return &(_node->_data);}//构造函数,通过节点的指针进行构造RBTreeIterator(Node* node, Node* root) :_node(node), _root(root) {}//！=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* leftMost = _node->_right;while (leftMost->_left)leftMost = leftMost->_left;_node = leftMost;}//右为空，代表这棵树已经访问完了，所以应该找到父亲，因为当前节点是父亲的左子树//所以左 中 右//下一个访问的节点应该是访问祖先else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){//_node是空，代表是endif (_node == nullptr){//end--，则取的就是最右节点，也就是整棵树的最大节点Node* rightMost = _root;//找到左子树的最右节点while (rightMost && rightMost->_right)rightMost = rightMost->_right;_node = rightMost;}//--是左子树的最右节点else if (_node->_left){Node* rightMost = _node->_left;//找到左子树的最右节点while (rightMost->_right) rightMost = rightMost->_right;_node = rightMost;}//如果左为空else{Node* cur = _node;Node* parent = cur->_parent;//因为是反过来的，所以是右根左while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}
};

总结

通过对 map 和 set 的封装，我们可以简化代码的使用方式，增强数据操作的安全性和可维护性，同时根据具体需求扩展功能。这不仅提高了代码的可读性和复用性，还在多线程环境下提供了更好的保障。尽管封装需要额外的设计和实现工作，但它带来的长远收益是显而易见的。未来，我们可以进一步探索封装的优化方向，如支持更多类型的容器或集成其他数据结构，以适应更复杂的应用场景。在实际项目中，合理地利用封装技术，将使我们的C++开发工作更加高效和灵活。