C++:模拟实现STL的map和set_模仿stl实现map
目录
一.红黑树的改造
二.模拟实现set
三.模拟实现map
四.整体代码
1.RBTree.h
2.MySet.h
3.MyMap.h
4.Test.cpp
一.红黑树的改造
map和set底层都是通过红黑树实现的,但是set中存放是key,map中为key,value,我们不会去写两棵红黑树来实现他们,因为代码会重复,我们需要对红黑树内部进行改造
template为了可以同时处理set和map,我们传一个T过去,是set的时候为key,map为pair
对于set和map他们的排序,set可以直接通过key来排序,而map的排序规则与set不同,先比较key,如果相同比较value,所以我们传一个KOfT
struct SetKeyOfT{const K& operator()(const K& k){return k;}};struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};通过KOfT来分别处理set和map的排序
红黑树的迭代器
iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}operator++与operator--
Self& operator++(){//如果右不为空,中序的下一个就是右子树的最左节点//如果右为空,表示_node所在子树访问完,下一个节点在他的祖先中找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--(){//与++基本相反return *this;}set和map的实现都是对红黑树的复用,所以理解红黑树是关键
二.模拟实现set
set的实现通过对红黑树的复用即可完成
templateclass set{struct SetKeyOfT{const K& operator()(const K& k){return k;}};public:typedef typename RBTree::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair Insert(const K& k){return _t.Insert(k);}private:RBTree _t;};三.模拟实现map
templateclass map{struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};public:typedef typename RBTree<K, pair, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair Insert(const pair& kv){return _t.Insert(kv);}V& operator[](const K& key){pair ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair, MapKeyOfT> _t;};四.整体代码
1.RBTree.h
#pragma onceenum Colour{BLACK,RED,};templatestruct RBTreeNode{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;Colour _col;RBTreeNode(const T& data) :_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) { };};templatestruct __TreeIterator{typedef RBTreeNode Node;typedef __TreeIterator Self;Node* _node;__TreeIterator(Node* node) :_node(node) { }Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){//如果右不为空,中序的下一个就是右子树的最左节点//如果右为空,表示_node所在子树访问完,下一个节点在他的祖先中找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--(){//与++基本相反return *this;}bool operator !=(const Self& s){return _node != s._node;}bool operator ==(const Self& s){return _node == s._node;}};templateclass RBTree{typedef RBTreeNode Node;public:typedef __TreeIterator iterator;typedef __TreeIterator const_terator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}pair Insert(const T& data){//按照搜索树的规则插入if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}KOfT koft;Node* parent = nullptr;Node* cur = _root;while (cur){if (koft(cur->_data) _right;}else if (koft(cur->_data) > koft(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);Node* newnode = cur;if (koft(parent->_data) _data)){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//新增节点红的cur->_col = RED;while (parent && parent->_col == RED){//红黑树的关键看叔叔Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//情况一:uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}//情况二或情况三:uncle不存在或者uncle存在且为黑else{//情况三:双旋->变为单旋if (cur == parent->_right){RotateL(parent);swap(parent, cur);}//第二种情况(有可能为第三种情况变化而来)RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}else{Node* uncle = grandfather->_left;//情况一:uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}//情况二或情况三:uncle不存在或者uncle存在且为黑else{//情况三:双旋->变为单旋if (cur == parent->_left){RotateR(parent);swap(parent, cur);}//第二种情况(有可能为第三种情况变化而来)RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;//原来parent为根,现在subR为根//parent为树的子树,sunR替代parentif (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_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;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout <_kv.first << \":\" <_kv.second <_right);}void InOrder(){_InOrder(_root);}bool IsValidRBTree(){Node* pRoot = _root;// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BLACK != pRoot->_col){cout << \"违反红黑树性质：根节点必须为黑色\" <_col)blackCount++;pCur = pCur->_left;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);}bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount){//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << \"违反性质：每条路径中黑色节点的个数必须相同\" <_col)k++;// 检测当前节点与其双亲是否都为红色Node* pParent = pRoot->_parent;if (pParent && RED == pParent->_col && RED == pRoot->_col){cout << \"违反性质：没有连在一起的红色节点\" <_left, k, blackCount) &&_IsValidRBTree(pRoot->_right, k, blackCount);}iterator Find(const K& data){KOfT koft;Node* cur = _root;while (cur){if (koft(cur->_data) _right;}else if (koft(cur->_data) > koft(data)){cur = cur->_left;}else{return iterator(cur);}}return iterator(nullptr);}private:Node* _root = nullptr;};2.MySet.h
#pragma once#include\"RBTree.h\"namespace wzyl{templateclass set{struct SetKeyOfT{const K& operator()(const K& k){return k;}};public:typedef typename RBTree::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair Insert(const K& k){return _t.Insert(k);}private:RBTree _t;};void test_set(){set s;s.Insert(1);s.Insert(3);s.Insert(2);s.Insert(4);s.Insert(5);set::iterator it = s.begin();while (it != s.end()){cout << *it << \" \";++it;}cout << endl;for (auto e : s){cout << e << \" \";}cout << endl;}}3.MyMap.h
#pragma once#include\"RBTree.h\"namespace wzyl{templateclass map{struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};public:typedef typename RBTree<K, pair, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair Insert(const pair& kv){return _t.Insert(kv);}V& operator[](const K& key){pair ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair, MapKeyOfT> _t;};void test_map(){map m;m.Insert(make_pair(1, 1));m.Insert(make_pair(2, 2));m.Insert(make_pair(4, 4));m.Insert(make_pair(3, 3));m.Insert(make_pair(5, 5));map::iterator it = m.begin();while (it != m.end()){cout <first << \":\" <second << endl;++it;}cout << endl;for (auto e : m){cout << e.first << \":\" << e.second << endl;}cout << endl;string strs[] = { \"西瓜\",\"苹果\" ,\"西瓜\", \"葡萄\", \"西瓜\", \"橘子\", \"西瓜\", \"苹果\", \"西瓜\", \"橘子\" };map countmap;for (auto& str : strs){countmap[str]++;}for (auto kv : countmap){cout << kv.first << \":\" << kv.second << endl;}cout << endl;}}4.Test.cpp
#includeusing namespace std;#include\"MyMap.h\"#include\"MySet.h\"int main(){wzyl::test_map();wzyl::test_set();return 0;}
