【c++】map和set的模拟实现

个人主页：Quitecoder

专栏：c++笔记仓

不断完善红黑树功能，最后封装模拟实现

目录

• 1.红黑树的改造
• • 由insert更改模版参数
  • set和map的insert函数：
  • 2.红黑树的迭代器
  • • ++的实现：
    • set迭代器：
    • map迭代器
    • find函数：

      1.红黑树的改造

      在前面的学习中我们知道

      set和map是基于红黑树实现的，但是传的参数不一样，如果硬要按上面的参数匹配，我们需要两个红黑树，我们前面实现的红黑树都是pair实现的，下面我们看库中的实现方法：

      库的实现取决于第二个模版参数value，这里与前面不一样，这里第二个传参如果是pair，意味着是map类型，传参是key，意味着是set类型

      set构架：

      namespace myown {templateclass set{private:RBTree _t;};}

      map构架：

      namespace myown {templateclass map{private:RBTree _t;};}

      节点定义：

      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){}};

      红黑树结构如下：

      templateclass RBTree{typedef RBTreeNode Node;public:bool Insert(const T& data){-----------}};

      上面的第二个模版参数与以前是不一样的

      对于set，_data就是K，对于map，_data就是pair

      用红黑树实现set和map，又要存储K，又要存储pair，通过上面实现，set插入K，map插入pair，用第二个模版参数T

      这里的第一个模版参数并不多余，在Find中，我们寻找的是K，对于map而言，不是找的键值对，查找的是K

      由insert更改模版参数

      这里我插入的是data，有可能是key，有可能是pair，以前这里确定是pair，我们用pair的first来比较

      树里面比较就是让K去比较，如果是set，这里的data类型就是K，但如果是map，这里data就是pair，pair的比较规则不符合我们的要求，我们希望还是比较K部分，这里就需要设置仿函数了

      我们这里设置函数想办法吧data里面的K取出来：

      templateclass set{struct SeTKetOfT{const K& operator()(const K& key){return key;}};private:RBTree _t;};templateclass map{struct MapKetOfT{const K& operator()(const pair& key){return key.first;}};private:RBTree _t;};

      data不知道是pair还是K，但是我的map和set是知道的，函数内部构建仿函数取出K的值，在这里加入第三个仿函数模版参数：

      templateclass RBTree{typedef RBTreeNode Node;public:

      这里用仿函数来取data中的K值

      set和map的insert函数：

      templateclass set{struct SeTKetOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}private:RBTree _t;};

      直接调用封装的红黑树的插入函数

      templateclass map{struct MapKetOfT{const K& operator()(const pair& key){return key.first;}};public:bool insert(const pair& kv){return _t.Insert(kv);}private:RBTree _t;};

      2.红黑树的迭代器

      这里的迭代器++到下一个节点需要我们自己手动封装重载实现

      基本结构如下：

      templatestruct _RBTreeIterator{typedef RBTreeNode Node;typedef _RBTreeIterator self;Node* _node;_RBTreeIterator(Node* node):_node(node){}};

      ref是引用，ptr是指针

      templateclass RBTree{typedef RBTreeNode Node;public:typedef _RBTreeIterator iterator;typedef __RBTreeIterator constiterator;

      解引用：

      Ref operator*(){return _node->_data;}

      operator->

      Ptr operator->(){return &_node->_data;}

      不等于：

      bool operator!=(const Self& s){return _node != s._node;}

      RBTree中的begin：

      iterator Begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}

      返回中序遍历第一个节点，即最左节点

      RBTree中的end:

      Iterator End(){return Iterator(nullptr);}

      返回最后一个节点的下一个位置，这里用空代替

      ++的实现：

      it如果现在在根的位置，++寻找的是右树的最左节点

      如果右树不为空，找到右树最左节点

      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;

      如果我是父亲的左，就访问父亲，是右边，说明已经遍历过父亲了，继续往上找，这里按照中序遍历的规则

      set迭代器：

      templateclass set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}typedef typename RBTree::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}private:RBTree _t;};

      测试代码：

      void test_set(){set 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);set::iterator it = s.begin();while (it != s.end()){//*it += 5;cout cout struct MapKeyOfT{const K& operator()(const pairreturn key.first;}};public:typedef typename RBTreereturn _t.Begin();}iterator end(){return _t.End();}bool insert(const pairreturn _t.Insert(kv);}private:RBTreeNode* cur = _root;while (cur){if (cur-_key  
      完整代码：
       
      RBTree.h
       
      #pragma once#includeenum Colour{RED,BLACK};using namespace std;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 __RBTreeIterator{typedef RBTreeNode Node;typedef __RBTreeIterator 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;}};templateclass RBTree{typedef RBTreeNode Node;public:typedef __RBTreeIterator Iterator;typedef __RBTreeIterator ConstIterator;RBTree() = default;RBTree(const RBTree& t){_root = Copy(t._root);}// t2 = t1RBTree& operator=(RBTree 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 End() const{return ConstIterator(nullptr);}ConstIterator Begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);}Iterator Find(const K& key){Node* cur = _root;while (cur){if (cur->_key _right;}else if (cur->_key > key){cur = cur->_left;}else{return Iterator(cur);}}return End();}pair Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root), true);}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){// K// pair// kot对象，是用来取T类型的data对象中的keyif (kot(cur->_data) _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) _right = cur;}else{parent->_left = cur;}cur->_parent = 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;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 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 cout //cout blackNum++;}return Check(root-_left, blackNum, refNum)&& Check(root-_right, blackNum, refNum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout _kv.first struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTreereturn _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);}pairreturn _t.Insert(key);}private:RBTreestruct MapKeyOfT{const K& operator()(const pairreturn kv.first;}};public:typedef typename RBTreereturn _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);}pairreturn _t.Insert(kv);}V& operator[](const K& key){pairsecond;}private:RBTree _t;};