set和map简单模拟实现

红黑树

set和map的底层是红黑树,并且前面我们已经实现了。
但还是有点需要修改的地方，首先set是key模型，而map是key_val模型。因此红黑树是否需要实现两套？当然不是，我们只需通过模板操作，传入不同的类型即可实现。

成员变量

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

可以看到我们的模板参数从两个改成了一个，并且根据传入的类型不同转换为不同的模型。
例如set就只需传入key，map就可以传入pair<key,value>。

那么传入的参数不同，那该如何比较大小呢？这就涉及到我们之前讲过的仿函数，我们可以在RBTree里面传入一个仿函数，来获取不同T里面的key：

template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:
private:Node* _root = nullptr;
};

模板参数里面的KeyOfT就是我们想要的仿函数，因此insert被修改成如下：

Insert(第一次修改)

新版Insert：

bool Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}KeyOfT kot;//取出T类型的data中的keyNode* 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){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续处理cur = grandfather;//未必有parentparent = cur->_parent;}else//叔叔不存在或者为黑{if (cur == parent->_left){//RotateR(grandfather);Rotate(grandfather->_left);parent->_col = BLACK;grandfather->_col = RED;}else{//RotateL(parent);//RotateR(grandfather);Rotate(parent->_right);Rotate(grandfather->_left);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续处理cur = grandfather;//未必有parentparent = cur->_parent;}else//叔叔不存在或为黑{if (cur == parent->_right){//RotateL(grandfather);Rotate(grandfather->_right);parent->_col = BLACK;grandfather->_col = RED;}else{//RotateR(parent);//RotateL(grandfather);Rotate(parent->_left);Rotate(grandfather->_right);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//处理边界情况_root->_col = BLACK;return true;
}

Rotate:

void Rotate(Node* child)
{Node* parent = child->_parent;Node** childson[] = { &(child->_right),&(child->_left) };Node** parentson[] = { &(parent->_left),&(parent->_right) };bool IsRight = (child == parent->_right);*(parentson[IsRight]) = *(childson[IsRight]);if (*(childson[IsRight]))(*(childson[IsRight]))->_parent = parent;*(childson[IsRight]) = parent;child->_parent = parent->_parent;parent->_parent = child;if (parent == _root){_root = child;child->_parent = nullptr;}else{//Node* grandparent = parent->_parent; 千错万错Node* grandparent = child->_parent;if (parent == grandparent->_left) grandparent->_left = child;else grandparent->_right = child;}}

Iterator

我们知道set和map是有迭代器的，因此我们的底层红黑树需要实现迭代器。根据我们之前写链表迭代器的经验，红黑树迭代器当然也是手到擒来：

template<class T,class Ref,class Ptr>
struct _RBTreeIterator
{typedef RBTreeNode<T> Node;typedef _RBTreeIterator<T, Ref, Ptr> Self;Node* _node;_RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}
};

这样我们就简单实现了operator!=和operator*以及operator->。

operator++

这个迭代器的难点在于如何实现++。
红黑树的迭代器++自然是按照中序的顺序遍历的。

因此对于当前结点来说，比他大的下一个结点就是：右子树的最左结点。
如果右子树为空，并且当前结点为父结点的左子结点，那么比他大的下一个结点就是父结点。
如果右子树为空，并且当前结点为父结点的右子结点，那么就将当前结点改为父结点，重复这三个判断。

具体代码：

Self& operator++()
{//右不为空走右子树最小结点if (_node->_right){Node* rightMin = _node->_right;while (rightMin->_left){rightMin = rightMin->_left;}_node = rightMin;}else{//右为空，如果为左子树，走父亲//如果为右子树就一直向上走。Node* cur = _node;Node* parent = cur->_parent;while (parent&&cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

begin、end

实现了红黑树迭代器的封装，那么我们就能实现红黑树的迭代的一些基本功能：

typedef _RBTreeIterator<T, T&, T*> Iterator;
typedef _RBTreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin()
{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);
}Iterator End()
{return Iterator(nullptr);
}ConstIterator End() const
{return ConstIterator(nullptr);
}ConstIterator Begin() const
{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);
}

注意到我们的begin返回的是最小结点的迭代器，end返回的是空指针构造的迭代器。

Insert(第二次修改)

有了红黑树的迭代器后，我们就可以对Insert的返回值进行一定处理，应当返回的是pair<Iterator,bool>其中Iterator是插入结点的迭代器，bool为真代表插入成功，反之则插入失败。

pair<Iterator, bool> Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return { _root,true };}KeyOfT kot;//取出T类型的data中的keyNode* 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 { cur,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* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续处理cur = grandfather;//未必有parentparent = cur->_parent;}else//叔叔不存在或者为黑{if (cur == parent->_left){//RotateR(grandfather);Rotate(grandfather->_left);parent->_col = BLACK;grandfather->_col = RED;}else{//RotateL(parent);//RotateR(grandfather);Rotate(parent->_right);Rotate(grandfather->_left);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续处理cur = grandfather;//未必有parentparent = cur->_parent;}else//叔叔不存在或为黑{if (cur == parent->_right){//RotateL(grandfather);Rotate(grandfather->_right);parent->_col = BLACK;grandfather->_col = RED;}else{//RotateR(parent);//RotateL(grandfather);Rotate(parent->_left);Rotate(grandfather->_right);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//处理边界情况_root->_col = BLACK;return { newnode,true };
}

Find

Iterator Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return Iterator(cur);}}return End();
}

构造析构

显然我们的红黑树是需要深拷贝的，已经构造函数：

RBTree() = default;//强制编译器生成默认构造函数RBTree(const RBTree<K, T, KeyOfT>& t)
{_root = Copy(t._root);
}// t2 = t1
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
{swap(_root, t._root);return *this;
}~RBTree()
{Destroy(_root);_root = nullptr;
}Node* Copy(Node* root)
{if (root == nullptr)return nullptr;Node* newroot = new Node(root->_data);newroot->_col = root->_col;newroot->_left = Copy(root->_left);if (newroot->_left)newroot->_left->_parent = newroot;newroot->_right = Copy(root->_right);if (newroot->_right)newroot->_right->_parent = newroot;return newroot;
}void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;
}

set

成员变量

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;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;private://防止修改K，传入const KRBTree<K, const K, SetKeyOfT> _t;
};

begin、end

只需要简单的复用即可：

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

insert

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

find

iterator find(const K& key)
{return _t.Find(key);
}

map

成员变量

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, const K, MapKeyOfT>::ConstIterator const_iterator;
private://防止修改KRBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

begin、end

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

insert

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

find

iterator find(const K& key)
{return _t.Find(key);
}

operator[]

map的operator[]显然是一个比较特殊的函数，本质上他是调用一次insert然后返回插入位置的value的引用：

V& operator[](const K& key)
{pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;
}

事实上我们实现了红黑树的各种功能后，对于set和map的封装就显得轻松异常。