当前位置：首页 > news >正文

【C++/STL】map和set的封装（红黑树）

news 来源：原创 2024/9/19 5:00:34

🌈个人主页：秦jh_-CSDN博客
🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

key和pair

迭代器

const迭代器

完整代码

RBTree.h

Set.h

Map.h

前言

💬 hello! 各位铁子们大家好哇。

今日更新了map和set封装的相关内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

key和pair

上图是源码中的主要部分代码，可以看到，map里面存的是key和pair，而set里面存的是key和key。

上图是底层大概思路。根据传入的类型不同（key或者pair），变成相应的搜索模型。

我们插入的时候要进行比较，但是我们不知道插入的是K还是pair，所以不能直接用data。虽然pair支持比较，但是它的比较不符合我们的需要，所以不能用。

上图是解决思路，底层的RBTree不知道传入的是k还是pair，但是上层的map和set知道。所以在RBTree多传入一个模板参数KeyOfT，这样再在map和set中分别实现取出key的逻辑即可。

迭代器

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置。

底层实现好后，就可以封装到set和map上了，如下图：

set的迭代器不能修改，map的first不能修改，second可以修改。所以还需要改进，如下图：

const迭代器

上图是底层RBTree实现。

上图是封装到set中。

上图是封装到map中。

完整代码

set和map的底层都是红黑树

RBTree.h

#pragma once enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};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;}Self& operator++(){if (_node->_right)//当右不为空{//下一个，右树的最左节点Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else{//下一个，孩子等于父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};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;RBTree() = default; //强制生成构造函数RBTree(const RBTree<K, T, KeyOfT>& t) //拷贝构造，防止浅拷贝{_root = Copy(t._root);}//t2=t1RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}Iterator Begin(){Node* leftMin = _root;while (leftMin && leftMin->_left)//如果树是空，就直接返回空&&找到最左节点{leftMin = leftMin->_left;}return Iterator(leftMin);}Iterator End(){return Iterator(nullptr);}ConstIterator Begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left)//如果树是空，就直接返回空&&找到最左节点{leftMin = leftMin->_left;}return ConstIterator(leftMin);}ConstIterator End() const{return ConstIterator(nullptr);}Iterator Find(const K& key){KeyOfT kot;   Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return Iterator(cur);}}return End();}pair<Iterator,bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;  //根节点默认黑色return make_pair(Iterator(_root), true);}KeyOfT kot;Node* cur = _root;Node* parent = nullptr;while (cur){//K//pair<K,V>//kot对象，是用来取T类型的data对象中的keyif (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), 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;parent = cur->_parent;}else //叔叔不存在，或者存在且为黑{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{Node* 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), true);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) //节点可能为空subLR->_parent = parent;subL->_right = parent; //旧父节点变成subL的右节点Node* ppNode = parent->_parent;  //该不平衡节点可能不是根节点，所以要找到它的父节点parent->_parent = subL;if (parent == _root)   //如果该节点是根节点{_root = subL;_root->_parent = nullptr;}else  //不平衡节点只是一棵子树{if (ppNode->_left == parent)  //如果旧父节点等于爷爷节点的左节点，新父节点为爷爷节点的左节点{ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;	//新父节点指向爷爷节点。}}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;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){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);}private: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;}bool Check(Node* root,int blackNum,const int refNum){if (root == nullptr){//cout << blackNum << endl;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);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;size_t _size = 0;
};

Set.h

#pragma oncenamespace qjh
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://没有实例化的类模板typedef时要加typename，这样编译器就会在实例化后再找这个东西 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();}iterator find(const K& key){return _t.Find(key);}pair<iterator,bool> insert(const K& key){return	_t.Insert(key);}private:RBTree<K, const K, SetKeyOfT> _t; //set迭代器不能修改};void PrintSet(const set<int>& s){for (auto e : s){cout << e << endl;}}void test_set(){set<int> s;s.insert(4);s.insert(2);s.insert(5);s.insert(15);s.insert(7);s.insert(1);s.insert(5);s.insert(7);PrintSet(s);set<int>::iterator it = s.begin();while (it != s.end()){//*it += 5;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;set<int> copy = s;for (auto e : copy){cout << e << " ";}cout << endl;}
}

Map.h

#pragma oncenamespace qjh
{template<class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://first不能修改，second可以修改typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, const pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}iterator find(const K& key){return _t.Find(key);}pair<iterator, bool> insert(const pair<K, V>& kv){return	_t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K,V>, MapKeyOfT> _t;  //first不能修改，second可以修改};void test_map1(){map<string,int> m;m.insert({"苹果",1});m.insert({ "香蕉",1 });m.insert({ "梨",1 });m.insert({ "苹果",3 });map<string, int>::iterator it = m.begin();while (it != m.end()){//it->first += 'x';it->second += 1;//cout << it.operator->()->first << ":" << it->second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;}void test_map2(){string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉","苹果","草莓","苹果","草莓" };map<string, int> countmap;for (auto& e : arr){countmap[e]++;}for (auto& kv : countmap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}