目录
1.set和map的底层
2.迭代器
2.1 operator++()
2.2 operator--()
3. 实现代码
1.set和map的底层
set和map属于关联式容器，底层实现均为红黑树，set是K模型，map是KV模型，通过对上层的不同处理，使一份红黑树实现可以提供给set和map。
2.迭代器
2.1 operator++()
从树的最小节点出发，++的顺序与中序遍历的顺序相同，由于迭代器的下一个节点大于当前节点，所以迭代器++时分两种情况：
a. 右子树存在：查找右子树中最小的节点，即右子树的最左节点
b. 右子树不存在：向上查找，如果当前节点_node的parent存在且是parent的左孩子，下一个节点就是parent；如果当前节点_node的parent存在且是parent的右孩子，需要不断向上直到parent为nullptr（根的parent）
//左闭右开Self& operator++(){//++进行中序遍历//如果右子树不为空，找右子树最小的节点作为下一个节点if (_node->_right != nullptr){Node* leftMost = _node->_right;while (leftMost->_left != nullptr){leftMost = leftMost->_left;}//++转移到下一个中序遍历的节点_node = leftMost;}else{// _node是其父节点的左孩子，说明下一个中序遍历节点就是parentNode* cur = _node;Node* parent = cur->_parent;// parent存在且cur是parent的右孩子--回溯while (parent != nullptr && cur == parent->_right){cur = parent;parent = cur->_parent;}//包含没有回溯和cur是parent的左孩子--下一个节点直接是parent_node = parent;}return *this;}2.2 operator--()
从根的parent出发(nullptr)，--的顺序与逆序的中序遍历相同，由于迭代器的下一个节点大于当前节点，所以迭代器--时分两种情况：
a. 起始位end()，即nullptr，需要特殊处理，查找树的最大节点使下一个节点指向这个最大节点
a. 左子树存在：查找左子树中最大的节点，即左子树的最右节点
b. 左子树不存在：向上查找，如果当前节点_node的parent存在且是parent的右孩子，下一个节点就是parent；如果当前节点_node的parent存在且是parent的左孩子，需要不断向上直到parent为nullptr（根的parent）
//倒着的中序遍历
Self& operator--()
{//起始end()时为nullptrif (_node == nullptr){// --end()，特殊处理，走到中序最后一个节点--整棵树的最大节点Node* rightMost = _root;while (rightMost != nullptr && rightMost->_right != nullptr)rightMost = rightMost->_right;_node = rightMost;}//不是end()，_left不为空else if (_node->_left != nullptr){// 左子树不为空，中序左子树最后一个--左子树最大节点Node* rightMost = _node->_left;while (rightMost->_right != nullptr)rightMost = rightMost->_right;_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent != nullptr && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}3. 实现代码
//RBTree.h#pragma once
#include<iostream>
using namespace std;enum Color
{RED,BLACK
};
template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};template<class T, class Ref, class Ptr>//const与非const
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){}//左闭右开Self& operator++(){//++进行中序遍历//如果右子树不为空，找右子树最小的节点作为下一个节点if (_node->_right != nullptr){Node* leftMost = _node->_right;while (leftMost->_left != nullptr){leftMost = leftMost->_left;}//++转移到下一个中序遍历的节点_node = leftMost;}else{// _node是其父节点的左孩子，说明下一个中序遍历节点就是parentNode* cur = _node;Node* parent = cur->_parent;// parent存在且cur是parent的右孩子--回溯while (parent != nullptr && cur == parent->_right){cur = parent;parent = cur->_parent;}//包含没有回溯和cur是parent的左孩子--下一个节点直接是parent_node = parent;}return *this;}//倒着的中序遍历Self& operator--(){//起始end()时为nullptrif (_node == nullptr){// --end()，特殊处理，走到中序最后一个节点--整棵树的最大节点Node* rightMost = _root;while (rightMost != nullptr && rightMost->_right != nullptr)rightMost = rightMost->_right;_node = rightMost;}//不是end()，_left不为空else if (_node->_left != nullptr){// 左子树不为空，中序左子树最后一个--左子树最大节点Node* rightMost = _node->_left;while (rightMost->_right != nullptr)rightMost = rightMost->_right;_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent != nullptr && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!= (const Self& s){return _node != s._node;}bool operator== (const Self& s){return _node == s._node;}
};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin(){Node* leftMost = _root;//最左开始--闭区间while (leftMost && leftMost->_left)leftMost = leftMost->_left;return Iterator(leftMost, _root);}Iterator End(){//从nullptr开始--开区间return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* leftMost = _root;//最左开始--闭区间while (leftMost && leftMost->_left)leftMost = leftMost->_left;return ConstIterator(leftMost, _root);}ConstIterator End() const{//从nullptr开始--开区间return ConstIterator(nullptr, _root);}//生成默认构造函数RBTree() = default;RBTree(const RBTree& t){_root = Copy(t._root);}RBTree& operator=(RBTree t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}pair<Iterator, bool> Insert(const T& data){//空树插入时if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root, _root), true);}//提供仿函数的方式，进行比较，使得set的K模型和map的KV模型都可以使用同一份代码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 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* grandfather = parent->_parent;// g// p uif (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){// u存在且为红--变色再继续往上处理parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// u存在且为黑或不存在--旋转+变色if (cur == parent->_left){// g// p u//c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// c//双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// g// u pNode* uncle = grandfather->_left;// 叔叔存在且为红--变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(Iterator(newnode, _root), true);}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalance(){//空树符号if (_root == nullptr)return true;if (_root->_col == RED)return false;// 计算任意一条路径黑色节点的数量，用于后续检查各路黑色节点的数量是否相同int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++refNum;cur = cur->_left;}return Check(_root, 0, refNum);}Iterator Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key)cur = cur->_right;else if (cur->_kv.first > key)cur = cur->_left;elsereturn Iterator(cur, _root);}//没找到return End();}private:bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return max(leftHeight,rightHeight) + 1;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left)parentParent->_left = subR;elseparentParent->_right = subR;subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_kv);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;
};//set.h#pragma once#include "RBTree.h"namespace mySet
{template <class K>class set{//仿函数--提供比较的keystruct 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();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private://K模型只有一个K，这里第二个K需要constRBTree<K, const K, SetKeyOfT> _t;};test//void Print(const set<int>& s)//{// set<int>::const_iterator it = s.end();// while (it != s.begin())// {// --it;// cout << *it << ' ';// }// cout << endl;//}//void test_set()//{// set<int> s;// int a[] = { 3,4,5,243,5,523,45,234,5,234,52 };// for (auto e : a)// {// s.insert(e);// }// for (auto e : s)// {// cout << e << ' ';// }// cout << endl;// set<int>::iterator it = s.end();// while (it != s.begin())// {// --it;// cout << *it << ' ';// }// cout << endl;// // it = s.begin();// while (it != s.end())// {// cout << *it << ' ';// ++it;// }// cout << endl;// Print(s);//}
}
//map.h#pragma once
#include "RBTree.h"namespace myMap
{template<class K, class V>class map{//仿函数--提供比较的keystruct 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();}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}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;};//testvoid test_map(){map<string, string> dict;dict.insert({ "test","测试" });dict.insert({"sort","排序"});dict.insert({ "null","空" });dict.insert({ "left","左" });dict.insert({ "right","右" });dict.insert({ "error","错误" });//修改dict["left"] = "左边";dict["right"] = "右边";dict["int"];dict["double"];map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ':' << it->second << endl;++it;}cout << endl;}
}
)
