【C++】set map 的底层封装

在了解底层封装之前除了对set和map的使用情况要有一定了解，还需要先学习一下二叉搜索树，AVL树，红黑树这些数据结构。
【C++】二叉搜索树
【C++】AVL树 & 红黑树

RBTree.h

enum Colour
{RED,BLACK
};template<class T>
class RBTreeNode
{
public:RBTreeNode(const T& data): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;
};template<class T, class Ref, class Ptr>
// 红黑树的迭代器实现
class __RBTreeIterator
{
public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;
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;}Self& operator++(){// 右子树不为空if (_node->_right){// ++就是找右子树的最左节点Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}// 右子树为空else{// ++就是找不是其右孩子的祖先Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_right == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){// 左子树不为空if (_node->_left){// --就是找左子树的最右节点Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}// 左子树为空else{// --就是找不是其左孩子的祖先Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_left == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
public:Node* _node;
};// KeyOfT: 用于获取T中的key的一个仿函数类
template<class K, class T, class KeyOfT>
class RBTree
{
private:typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;RBTree(Node* root = nullptr): _root(root){}// begin() 就是找红黑树的最左节点iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}// 因为迭代器是左闭右开，所以end()的迭代器设置为空iterator end(){return iterator(nullptr);}pair<iterator, bool> Insert(const T& data){KeyOfT kot;if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);cur->_col = RED;// 保存cur用于返回Node* newnode = cur;if (kot(data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){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->_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->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}
private:void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}
private:Node* _root;
};

Set.h

#include "RBTree.h"namespace zs
{template<class K>class set{public:class SetKeyOfT{public:const K& operator()(const K& key){return key;}};typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:// set的底层就是一棵红黑树RBTree<K, K, SetKeyOfT> _t;};
}

Map.h

#include "RBTree.h"namespace zs
{template<class K, class V>class map{public:class MapKeyOfT{public:const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef typename RBTree<K, pair<K,V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}// map支持[]操作V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:// map的底层就是一棵红黑树RBTree<K, pair<K, V>, MapKeyOfT> _t;};}