🐱1. 红黑树的泛型

我们通过查看源码，发现map和set的底层都是红黑树，用的同一个类模板，通过控制传不同的模板参数，从而实例化出不同的类

🐈1.1 红黑树节点

因为要对map和set进行封装，set是K模型，map是KV模型，所以采用模板来对数据类型进行控制

enum Colour
{RED,BLACK
};
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};

🐈1.2 红黑树迭代器

STL库里面红黑树设置了一个头节点，这样在而我们采用的不是库里面方式，用的自己手搓的红黑树，所以在迭代器++或--的时候，采用遍历树的方式
在这里插入图片描述

迭代器结构：

这里有三个模板参数，Ptr和Ref可以通过传过来的是普通参数还是const参数来控制采用什么样的迭代器（普通迭代器或者const迭代器）；同时也为map中pair的两个参数通过了很好的访问方式Ref operator*()、Ptr operator->()

template<class T,class Ptr,class Ref>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;typedef __TreeIterator<T, T*, T&> Iterator;Node* _node;//根据实例化的迭代器选择是构造还是拷贝构造__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* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{//右为空Node* cur = _node;Node* parent = cur->_parent;//孩子是父亲左的祖先节点while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}else{//孩子是父亲右的节点Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
};

迭代器：

template<class K,class T,class KeyOfT>
struct 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* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return leftMin;}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return leftMin;}const_iterator end() const{return const_iterator(nullptr);}// ... ...// ... ...
}

🐈1.3 仿函数

当对元素进行插入或者查找的时候，都要进行比较，而map的pair无法直接比较，所以我们设置了仿函数，用来提取key值
这里以Find接口为例，具体可以看代码仓库的完整代码

Node* Find(const K& key)
{Node* cur = _root;//仿函数KeyOfT kot;while (cur){//提出key值if (kot(cur->_data) > key){cur = cur->_left;}else if (kot(cur->_data) < key){cur = cur->_right;}elsereturn cur;}return nullptr;
}

🐯2. 对set的封装

对于set的封装相对简单，在整个设计中，set由于只有一个K值，所以很多模板参数对于set而已作用并不大

set的K值是不允许修改的，所以不管是普通迭代器还是const迭代器，都是采用的const迭代器

这里关于插入的操作，本质上也是为了兼容map，放到下面和map一起说

namespace My_map_set
{template<class K>class set{//仿函数struct SetKeyOfT{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;const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& key){pair < typename RBTree<K, K, SetKeyOfT>::iterator, bool > ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyOfT> _t;};
}

我们在封装的时候，采用了一个仿函数SetKeyOfT，这是因为在数据比较的时候，map是pair需要取出里面的key值，为了保持统一，我们对set也使用了仿函数

🦄3. 对map的封装

map的key值是不允许修改的，而value是允许修改的，使用有const修饰pair里面的key值
map是支持[]的，而[]底层又是调用的insert，所以对于insert的返回值需要进行更改，而map有普通迭代器和const迭代器，不需要指定调用树里面的

set的迭代器都是const迭代器，所以我们直接调用树里面的迭代器，库里面就是这么实现的：

当这个类被实例化成const迭代器的时候，是一个构造函数，支持了普通迭代器构造const迭代器；

当这个类被实例化为普通迭代器，那就是拷贝构造

namespace My_map_set
{template<class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<const 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_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}