map和set的模拟实现

一.内容介绍

1.set采用Key的搜索场景，map采用Key/Value的搜索场景，二者的底层均可以用红黑树实现，为了降低代码的冗余量可以通过对红黑树模板的参数做少许改动达到一棵红黑树的基层实现set和map两个派生类的目的。

一些问题：

1>在红黑树的模板中用第二个模板参数T来泛型表示红黑树的节点内存储的内容。在set类中，T表示K，而在map类中T表示pair<K,V>，因为set不允许修改K的值，所以T应该表示const K;map不允许修改pair的第一个参数，但可以修改第二个参数，所以T应该表示成pair<const K,V>

2>为什么红黑树的模板要传第一个模板参数Key呢？

对于map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就不⼀样了，map的insert的是pair对象，但是find和erase的是Key对象，为了方便使用就选择将Key单独拿出来。

2.数值比较问题：对于set和map针对的使用搜索场景不同，可以通过仿函数获取set和map进行比较时的数值

3.iterator中的++：访问顺序：左子树->根->右子树

1>在红黑树中实现begin()和end()

begin():由于红黑树的是根据中序遍历的思想打印数据的，所以迭代器的初始数据应该是红黑树最左边的数据的节点指针

end():按照要求去寻找下一个要访问的节点时，若发现某个节点的父亲为空，则说明已经遍历完整棵树，这时用nullptr充当end

2>当前节点的右子树不为空时，中序遍历访问的下一个节点是右子树的最左节点

3>当前节点的右子树为空时，中序遍历访问的下一个节点是祖先里孩子是父亲左的那一个祖先

注：--与++的思想一致，逻辑相反，访问顺序为：右子树->根->左子树

当前节点的左子树不为空，中序遍历访问的下一个节点是左子树的最右节点

当前节点的左子树为空时，中序遍历访问的下一个节点是祖先里面孩子是父亲右的那一个祖先

二.红黑树模板的模拟实现

enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _parent;RBTreeNode<T>* _left;RBTreeNode<T>* _right;Colour _col;RBTreeNode(const T& data):_data(data),_parent(nullptr),_left(nullptr),_right(nullptr){}
};template<class K,class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> ConstIterator;public:Iterator Begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur);}Iterator End(){return Iterator(nullptr);}ConstIterator Begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return ConstIterator(cur);}ConstIterator End() const{return ConstIterator(nullptr);}bool Insert(const T& data){//空树，新增节点为黑色if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}//寻找插入位置KeyOfT kot;Node* parent = nullptr;Node * cur = _root;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);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* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//uncle存在且为红色，只变色{//parent，uncle变黑，grandfather变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新cur = grandfather;parent = grandfather->_parent;}else//uncle不存在或者存在且为黑色，旋转+变色{if (cur == parent->_left)//cur为parent的左孩子，单旋+变色{//     g//  p     u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur为parent的右孩子，双旋+变色{//     g//  p     u//    cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//uncle存在且为红色，只变色{//parent，uncle变黑，grandfather变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新cur = grandfather;parent = grandfather->_parent;}else//uncle不存在或者存在且为黑色，旋转+变色{if (cur == parent->_left)//cur为parent的左孩子，双旋+变色{//     g//  u     p//     cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}else//cur为parent的右孩子，单旋+变色{//     g//  u     p//          cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}break;}}}//防止因向上更新导致根节点不是黑色_root->_col = BLACK;return true;}Node* Find(const K key){Node* cur = _root;while (cur){if (cur->_data < key){cur = cur->_right;}else if (cur->_data > key){cur = cur->_left;}else{return cur;}}return nullptr;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//修改指向subR->_left = parent;parent->_right = subRL;if (subRL)//b子树可以为空树{subRL->_parent = parent;}Node* PParent = parent->_parent;if (PParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == PParent->_left){PParent->_left = subR;}else{PParent->_right = subR;}subR->_parent = PParent;}parent->_parent = subR;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//修改指向subL->_right = parent;parent->_left = subLR;if (subLR)//b子树可能为空树{subLR->_parent = parent;}Node* PParent = parent->_parent;if (PParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == PParent->_left){PParent->_left = subL;}else{PParent->_right = subL;}subL->_parent = PParent;}parent->_parent = subL;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}
private:int _Height(Node* root){if (root == nullptr) return 0;int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);return LeftHeight > RightHeight ? LeftHeight +1: RightHeight + 1;}int _Size(Node* root){if (root == nullptr) return 0;return _Size(root->_left) + _Size(root->_right) + 1;}
private:Node* _root = nullptr;
};

三.迭代器模板的模拟实现

1.返回节点内的数据

2.返回节点内的数据指针

3.判断两个节点是否相等

template<class T,class Ref,class Rtr>
class RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T,Ref,Ptr> Self;Node* _node;public:RBTreeIterator(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;}
};

4.operator++

Self operator++(){if (_node->_right != nullptr){//右子树不为空，中序遍历下一个访问的是去找右子树的最左节点Node* min = _node->right;while (min){min = min->_left;}_node = min;}else{//右子树为空，中序遍历下一个访问的是祖先里面孩子是父亲左的那一个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}

5.operator--

Self operator--(){if (_node->_left){//当前节点的左子树不为空，中序遍历访问的下一个节点是左子树的最右节点Node* max = _node->_left;while (max){max = max->_right;}_node = max;}else{//当前节点的左子树为空时，中序遍历访问的下一个节点是祖先里面孩子是父亲右的那一个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parnet = cur->_parent;}_node = parent;}return *this;}

四.map的模拟实现

namespace fdd
{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;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}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);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};}

五.set的模拟实现

namespace fdd
{template<class K>class Set{//获取可以用于比较的红黑树节点内存储的值struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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();}bool Insert(const K& key){return _t.Insert(key);}private:RBTree<K, const K,SetKeyOfT> _t;};}

补：关于set和map的源代码里使用了哨兵位来用于记录红黑树的最左节点和最右节点，它与红黑树的根节点互为对方的父节点，有兴趣可以自行查看