『 C++ - STL』map与set的封装 ( 万字 )

---

🎡 map与set介绍

map与set分别是STL中的两种序列式容器;

它们是一种树形数据结构的容器,且其的底层构造为一棵红黑树;

而在上一篇文章中提到,其实红黑树本身就是一棵二叉搜索树,是基于二叉搜索树的性质对其增加了平衡的属性来提高其综合性能(包括增删查改);

当然也提到了红黑树与AVL树的区别:

• AVL树

  AVL树是一棵高度平衡搜索二叉树,其特点即为在搜索二叉树的基础上根据控制结构达到了最终的属性;

  即为,每一个节点的左右子树的高度差不超过1;

• 红黑树

  红黑树是一棵近似平衡的二叉树,其特点为根据树的颜色 (红色或是黑色),以制定了一系列的规则使得树能够达到最终的效果;

  即为每条最长路径的长度不超过最短路径的2倍;

• 当然为什么map与set容器所使用的数据结构为红黑树而不是AVL树?

  最简单的原因其实是因为对于AVL树来说,既然要维持高度平衡,那么必定会在少次插入过后以特定的操作(旋转操作)来使得树在不符合规则时对其进行调整从而恢复平衡状态,虽然在查找方面有着绝对的优势,但是在大量的旋转操作后必定会使整体的效率变慢;

  而对于红黑树来说,红黑树虽然也是一棵平衡搜索二叉树,但是它允许树中的节点不为高度平衡而是为近似平衡最长路径的长度不超过最短路径的二倍,这使得红黑树允许多次进行插入而少量的进行旋转操作;

  • 那么既然相对AVL树在结构上的平衡高于红黑树,那么在整体效率当中谁更胜一筹?

    当然,以单单的查找为例;

    AVL树的最终深度保持在了logN,其中N为数中节点的个数;

    对于红黑树而言,红黑树允许了最长节点长度不超过最短节点的二倍的原因,其最终的深度控制在了2logN以内,其时间复杂度也相当(可以看作是logN);

    举个例子,假设两棵都存在10亿个节点,分别为AVL树与红黑树,当查找同一个节点时,AVL树只需要查找30次,而红黑树最多需要查找60次;

    然而由于当前CPU的性能而言,查找30次的速度可以与查找60次的速度相当;

    又因为红黑树在插入过程中需要处理的次数大大少于AVL树,故以综合性能而言,红黑树大于AVL树;

故在多数场景的使用中红黑树的使用频率要大于AVL树;

当然既然他们的底层都是平衡搜索二叉树,当然他们所对应的容器也必定有着对应的功能,即排序(搜索二叉树又被称为排序二叉树)与去重;

---

🎡 map与set的基础结构

在map与set的使用过程中,由于使用的过程当中由于set容器在使用过程当中只对key进行处理;

而对于map容器而言,map所返回的是一个键值对,即key,value;

所以可能会联想到在STL中的这两个容器是否使用的是不同的红黑树;

而实际在STL的源码中可以看到,对于这两个容器而言所使用的是同一个红黑树,并且利用泛型的特性来控制两个容器中所使用的对应的参数;

• map

  //...
  private:
    typedef rb_tree<key_type, value_type, 
                    select1st<value_type>, key_compare, Alloc> rep_type;
    rep_type t;  // red-black tree representing map
  

• set

  //...
  private:
    typedef rb_tree<key_type, value_type, 
                    identity<value_type>, key_compare, Alloc> rep_type;///模板参数传参
    rep_type t;  // red-black tree representing set
    /*template <class Key, class Value, class KeyOfValue, class Compare,
            class Alloc = alloc>//*/
  

以上的两段代码是来自STL源码中的关于set与map容器中的对红黑树的定义;

其中两个容器都使用了同一棵红黑树;

• 那么既然是同一棵红黑树,应该如何对这棵树进行修改使得该树能够满足对于map容器而言可以进行对应的key,value数据的存储与管理,而set容器可以进行单纯的key数据的存储与管理?

---

🎡 红黑树的再修改

在上文之中提到,若是以上一篇文章为例子来实现红黑树的话,则对于map与set两个容器的封装而言就可能使用到两个红黑树;

而实际上在STL中用来实现两个容器的是同一棵红黑树;

• 那么如何对红黑树进行修改来使得其能够通过泛型来同时作用于(封装)两个容器?

  struct __rb_tree_node_base
  {
     //红黑树节点的定义
    typedef __rb_tree_color_type color_type;
    typedef __rb_tree_node_base* base_ptr;
  
    color_type color; 
    base_ptr parent;
    base_ptr left;
    base_ptr right;
      /*...*/
  }
  
  template <class Value>
  struct __rb_tree_node : public __rb_tree_node_base
  {
      //定义一个新的类为__rb_tree_node_base,并且继承原先节点的定义__rb_tree_node
    typedef __rb_tree_node<Value>* link_type;
    Value value_field; 
      /*...*/
  };
  
  template <class Key, class Value, class KeyOfValue, class Compare,
            class Alloc = alloc>//
  class rb_tree {
        typedef rb_tree_node* link_type;
  protected:
    //...
    link_type header;  
      //整棵树的定义
      /*...*/
  };
  
  
  

  该段代码为在STL中的红黑树与其的定义,其中可以看出对于红黑树节点的定义来说使用的是一种继承的方法,主要是定义一个基类 __rb_tree_node_base并用派生类__rb_tree_node继承该基类;

  同时再继承过后通过tytpedef重命名了派生类__rb_tree_node*的节点指针为link_type,并设置头节点为header;

  从整棵树的定义中可以看到,一共有五个模板参数,分别为Key, Value,KeyOfValue,Compare,Alloc = alloc;

  这五个模板参数分别对应的是:

  • Key

    该模板参数参数用于传递key数据的类型;

  • Value

    该模板参数用于传递value数据的类型;

  • KeyOfValue

    该模板参数为一个仿函数,通过该仿函数可以达到使得map与set间虽然所存的数据不同但是能在一些场景下(例如比较)使其能够进行相同的操作;

    这个模板参数也是该问题中的核心部分;

  • Alloc

    该模板参数用来传入一个内存分配器,在此不做过多说明;

那么可以根据这个模板参数来从两个容器的源码当中来追溯参数的传递:

• map

  #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
  #else
  template <class Key, class T, class Compare, class Alloc = alloc>
  #endif
  class map {
  public:
  
  // typedefs:
  
    typedef Key key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef pair<const Key, T> value_type;
    typedef Compare key_compare;
      
    //...
    };
  
  private:
    typedef rb_tree<key_type, value_type, 
                    select1st<value_type>, key_compare, Alloc> rep_type;
    rep_type t;  // red-black tree representing map
  

  从该段代码当中可以看到对于map而言其对于key,value模型中传递了对应的参数分别为key_type, value_type;

  且从中可以看出对于其中的value_type而言,map容器所传递给红黑树的参数为一个pair<const Key, T>;

  而其中的Key与T即为所传递的参数;

  map将所传递的参数用于两个用途,其中一个是封装为一个pair<const Key ,T>传递给红黑树用于数据的管理;

  另一个直接将Key作为单独的参数(key_type)传递给红黑树当中的Key用于其他部分中可能出现的其他操作(例如查找);

• set

  #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  template <class Key, class Compare = less<Key>, class Alloc = alloc>
  #else
  template <class Key, class Compare, class Alloc = alloc>
  #endif
  class set {
  public:
    // typedefs:
  
    typedef Key key_type;
    typedef Key value_type;
    typedef Compare key_compare;
    typedef Compare value_compare;
  private:
    typedef rb_tree<key_type, value_type, 
                    identity<value_type>, key_compare, Alloc> rep_type;///模板参数传参
    rep_type t;  // red-black tree representing set
    /*template <class Key, class Value, class KeyOfValue, class Compare,
            class Alloc = alloc>//*/
  

  而对于set而言,传递给红黑树当中的 Key, Value时传递的参数同样为key_type与value_type;

  但唯一有一点不同的是,对于set而言,其中的key_type与value_type都是由Key进行typedef重命名而来,以此可以得知,实际上为了实现两个容器共用同一棵红黑树,对于set而言其传递一个冗余的参数;

• 那么当需要进行比较操作时,红黑树如何以泛型的属性来达到既可以比较map中的key,value,又能够比较set中的key?

  在上文中提到了一个仿函数为KeyOfValue,该仿函数是从map与set容器中传递给红黑树当中的;

  当然其定义也在对应的容器定义当中;

  • set

    typedef rb_tree<key_type, value_type, 
                      identity<value_type>, key_compare, Alloc> rep_type;///模板参数传参
    

    对于set而言它的仿函数为 identity<value_type>,它的底层实现类似于:

    template <class T>
    struct identity {
        const T& operator()(const T& x) const {
            return x;
        }
    };
    

    即返回对应的key值即可;

  • map

    typedef rb_tree<key_type, value_type, 
                      select1st<value_type>, key_compare, Alloc> rep_type;
    

    而对于map容器来说它的仿函数为select1st<value_type>;

    其底层的实现类似于:

    template <class Pair>
    struct select1st {
        const typename Pair::first_type& operator()(const Pair& x) const {
            return x.first;
        }
    };
    

    由于其传值对应的Value中传递的是一个pair类型,所以可以使map容器通过仿函数来获取pair数据结构中的key值;

    这也使得两个容器可以适用于同一棵红黑树;

当然在实际过程中map,set中的很多接口都是通过复用其中红黑树的接口,例如插入查找迭代器实现等等;

---

🎠节点及树的定义

在上文中提到,若是需要实现两个容器同时使用同一棵红黑树就得对先前的红黑树进行对应的修改;

首先是节点以及树的定义;

对于节点与树的定义来说可修改的内容不是特别的多,需要修改的为:

• KeyOfValue

  在STL的红黑树当中新增了一个模板参数为KeyOfValue使得两个容器都能获取到其对应的key值;

• 节点的模板参数

  在原先的红黑树的模板参数当中所传递的是一个Key,Value的模型,而在该处需要修改为对应的T,根据T来传递对应的参数,若是set对应所传递的即为其中的Key;若是map,所传递的即为对应的pair<key,value>;

enum COLOR{
    RED,
    BLACK
};



template<class T>
struct RBTreeNode{

    RBTreeNode<T> *_left;
    RBTreeNode<T> *_right;
    RBTreeNode<T> *_parent;
    T _data; 
    COLOR _col;

    RBTreeNode(const T& data)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_data(data)
    ,_col(RED)
    {}
};

template<class K,class T,class KeyOfT>
class RBTree{
    public:
    KeyOfT kot; // KeyOfT
    typedef RBTreeNode<T> Node;
    //....
    private:
    Node* _root = nullptr;
};

而对于其KeyOfValue的实现来说可以参照上文中两个容器中的仿函数实现进行;

---

🎠KeyOfValue的使用

KeyOfValue的使用贯穿于整棵红黑树当中大部分需要用到key值的位置;

只需要对其进行实例化并且在需要的地方进行使用即可;

    KeyOfT kot; // KeyOfT

---

🎠插入函数

在STL中,无论是map容器还是set容器而言,其插入函数Insert()函数的返回值都是为一个pair<iterator,bool>;

若是插入成功则返回新插入节点的迭代器(迭代器的实现将在下文中提到)位置与true;

若是插入失败则返回需要插入的数据相同的节点位置与false;

当然其对于插入时需要进行的旋转逻辑以及变色逻辑都不变;

 pair<iterator,bool> Insert(const T &data) {
        if(_root == nullptr){
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root),true);
        }
        
        Node *cur = _root;
        Node *parent = nullptr;

        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), false);
            }
        }

         Node* newnode = new Node(data);
         cur = newnode;
          if (kot(parent->_data) < kot(data)) {
           parent->_right = cur;
           cur->_parent = parent;
         }
        else{
            parent->_left = cur;
            cur->_parent = parent;
        }

        while(parent && parent->_col == RED){
        
            Node *grandfather = parent->_parent;
            if(grandfather->_left == parent){
                Node *uncle = grandfather->_right;
                
                if(uncle && uncle->_col == RED){
                   
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }

                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     
                    if(cur == parent->_left){
                        RotateR(grandfather);

                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else{ // cur == parent->_left
                        RotateL(parent);
                        RotateR(grandfather);

                       cur->_col = BLACK;
                       grandfather->_col = RED;
                    }
                    break;
                }
            }

            else{ 
                // if(grandfather->_right == parent){
                Node *uncle = grandfather->_left;
                if (uncle && uncle->_col == RED){
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     if(cur == parent->_right){
                        RotateL(grandfather);

                  
                        grandfather->_col = RED;
                        parent->_col = BLACK;

                     }
                     else{
                         RotateR(parent);
                         RotateL(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                     }
                     break;
                }
            }
        }
        _root->_col = BLACK;

        return make_pair(iterator(newnode), true);
    }

---

🎠析构函数

红黑树的析构函数与普通二叉树的析构函数相同,只需要创建一个_Destroy()的子函数以后序遍历的方式对节点逐个进行释放即可,再在析构函数当中调用该函数即可;

    void _Destory(Node* &root){
        if(root == nullptr){
            return ;
        }

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;

        root = nullptr;
    }

   ~RBTree() { 
        _Destory(_root); 
        }

---

🎠红黑树完整代码(供参考)

#include<iostream>

#include<vector>

enum COLOR{
    RED,
    BLACK
};



template<class T>
struct RBTreeNode{

    RBTreeNode<T> *_left;
    RBTreeNode<T> *_right;
    RBTreeNode<T> *_parent;
    T _data; 
    COLOR _col;

    RBTreeNode(const T& data)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_data(data)
    ,_col(RED)
    {}
};


protected:
private:
    Node *_node;
};

template<class K,class T,class KeyOfT>
class RBTree{

public:
    KeyOfT kot; // KeyOfT
    typedef RBTreeNode<T> Node;
    typedef __RBTree_Iterator<T, T &, T *> iterator;
    typedef __RBTree_Iterator<T, const T &, const T *> const_iterator;

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


    iterator end(){
        return iterator(nullptr);
    }

    ~RBTree() { 
        _Destory(_root); 
        }

    Node *Find(const K &key){
        Node* cur = _root;
        while(cur){
            if(key>kot(cur->_data)){
                cur = cur->_right;
            }
            else if (key < kot(cur->_data))
            {
                cur = cur->_left;
            }
            else{
                return cur;
            }
        }
        return nullptr;
    }

    pair<iterator,bool> Insert(const T &data) {
        if(_root == nullptr){
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root),true);
        }
        
        Node *cur = _root;
        Node *parent = nullptr;

        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), false);
            }
        }

         Node* newnode = new Node(data);
         cur = newnode;
          if (kot(parent->_data) < kot(data)) {
           parent->_right = cur;
           cur->_parent = parent;
         }
        else{
            parent->_left = cur;
            cur->_parent = parent;
        }

        while(parent && parent->_col == RED){
        
            Node *grandfather = parent->_parent;
            if(grandfather->_left == parent){
                Node *uncle = grandfather->_right;
                
                if(uncle && uncle->_col == RED){
                   
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }

                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     
                    if(cur == parent->_left){
                        RotateR(grandfather);

                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else{ // cur == parent->_left
                        RotateL(parent);
                        RotateR(grandfather);

                       cur->_col = BLACK;
                       grandfather->_col = RED;
                    }
                    break;
                }
            }

            else{ 
                // if(grandfather->_right == parent){
                Node *uncle = grandfather->_left;
                if (uncle && uncle->_col == RED){
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     if(cur == parent->_right){
                        RotateL(grandfather);

                  
                        grandfather->_col = RED;
                        parent->_col = BLACK;

                     }
                     else{
                         RotateR(parent);
                         RotateL(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                     }
                     break;
                }
            }
        }
        _root->_col = BLACK;

        return make_pair(iterator(newnode), true);
    }

    bool IsBalance(){
        if(_root == nullptr){
            return true;
        }

        if(_root && _root->_col == RED){
            return false;
        }
        
        std::pair<bool,std::vector<int>> ret ;
        ret.first = true;
        _Check(ret,_root,0);

        if(!ret.first){
            std::cout << "某一路径出现连续红色节点" << std::endl;
        }

        bool to_comp = true;
        size_t _comp = ret.second[0];
        for(auto &it : ret.second){
            if(it != _comp){
                to_comp = false;
                break;
            }

            std::cout << it << std::endl;
        }

        

        return to_comp && ret.first;
    }

    int getHeight()
    {
        return getHeight(_root);
    }

protected:


    void RotateL(Node *parent){


        Node *cur = parent->_right;
        Node *curleft = cur->_left;

        parent->_right = curleft;
        if (curleft)
        {
            curleft->_parent = parent;
        }

        cur->_left = parent;

        Node *ppnode = parent->_parent;

        parent->_parent = cur;

        if (parent == _root)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    void RotateR(Node *parent){
        

        Node *cur = parent->_left;
        Node *curright = cur->_right;

        parent->_left = curright;
        if (curright)
            curright->_parent = parent;

        Node *ppnode = parent->_parent;
        cur->_right = parent;
        parent->_parent = cur;

        if (ppnode == nullptr)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    void _Check(std::pair<bool,std::vector<int>> &ret,Node *root,size_t blackNum = 0){
        
        if(root == nullptr){
            ret.first = ret.first && true;
            ret.second.push_back(blackNum);
            return;
        }

        if(root->_col == RED && root->_parent->_col == RED){
            ret.first = ret.first && false;
            return ;
        }

        if(root->_col == BLACK){
            blackNum++;
        }

        _Check(ret, root->_left, blackNum);
        _Check(ret, root->_right, blackNum);
    }
    
    int getHeight(Node *root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int left = getHeight(root->_left);
        int right = getHeight(root->_right);

        return left > right ? left + 1 : right + 1;
    }

    void _Destory(Node* &root){
        if(root == nullptr){
            return ;
        }

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;

        root = nullptr;
    }

private:
    Node* _root = nullptr;
};

---

🎡 迭代器的实现

map与set中的迭代器与其他接口相同,都为调用其中红黑树的迭代器;

而红黑树的迭代器是单独进行封装的;

主要的接口即为:

• 需要对迭代器进行对应的遍历所需要的operator++()与operator--();
• 用于比较(可以用来终止遍历)的operator!=();
• 用于将节点的指针来构造出迭代器的构造函数;
• 将迭代器进行解引用的operator->()与operator*();

在该篇博客中的迭代器实现将着重以上述的几个接口作为主要接口进行实现;

---

🎠迭代器的定义

template <class T, class Ref /*数据的引用*/, class Ptr /*数据的地址*/> // 迭代器的实现
class __RBTree_Iterator
{
    typedef __RBTree_Iterator<T, Ref, Ptr> Self;
    typedef RBTreeNode<T> Node;

public:
    __RBTree_Iterator(Node *node)//构造函数
        : _node(node)
    {}

    Ref operator*();

    Ptr operator->();

    Self& operator++();

    Self operator++(int);
    
    Self& operator--();

    Self operator--(int);
    
    bool operator!=(const Self &s);

protected:
private:
    Node *_node;
};

红黑树的迭代器主要为封装其中红黑树的节点作为迭代器,并再封装之后对其设置其他的功能;

其构造函数只需要对其中的红黑树的节点进行初始化即可;

在该迭代器当中传入了几个模板参数分别为template <class T, class Ref /*数据的引用*/, class Ptr /*数据的地址*/>;

其中:

• Ref 为引用

  主要的功能是通过引用能够实现operator*()中能通过*来获取节点中的数据(可能为key也可能为pair);

• Ptr 为指针

  由于迭代器中具有->的功能,即为通过指针来指向节点中的值,能够实现通过迭代器的->来指向迭代器中的数据;

---

🎠迭代器中成员函数的实现

• Ref operator*()

  对于该函数而言,由于返回的是引用,所以只需要根据节点指针来返回其中对应的值即可;

  若是key则返回key,若是pair则返回对应的pair,当然这已经依靠泛型从而得到解决;

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

• Ptr operator->()

  对于该函数而言,其返回的是指针指向的数据,但是在C++中,若是重载其中的->符号时所得的依旧是个指针,则将会得到编译器的优化;

  编译器将会通过这个指针再去指向下一层的数据;

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

  以该函数而言,其取到的是节点中数据的地址;

  若是set时,该函数将返回的是其中key数据的地址,而经过编译器优化->将能够直接取到其中的值;

  对于map而言也是如此,将会取到其中pair的值;

• Self& operator++()与Self operator++(int)

  对该函数而言也是较为复杂的函数;

  该函数的思路即为手撕出红黑树的遍历方式;

  以中序遍历的思路而言,对于中序遍历来说,一棵树的最左侧节点即为一棵树中迭代器的begin位置;

  

  以该图为例,该图中的节点1即为该红黑树迭代器begin的位置;

  而对于++而言,需要思考如何通过该节点而去遍历下一个节点;

  最简单的思路即为:

  • 设置一个cur节点与parent节点,其中cur节点为当前节点,parent节点即为当前节点的父亲节点;

    以这两个节点进行遍历

  • cur节点的右子树存在

    当该节点的右子树存在时,下一个节点即为该节点右子树的最左侧节点;

    同时在遍历的过程中应该更新其节点;

  • cur节点的右子树不存在

    当cur节点的右子树不存在时则说明原先的右子树已经被遍历完毕;

    那么下一个节点即为cur节点不为parent节点右侧节点的情况中的parent节点,以此类推;

  • 代码片段:

    
        Self& operator++()//前置++
        {
            Node* cur = _node;
            if(cur->_right){
                cur = cur->_right;
                while (cur->_left){
                    cur = cur->_left;
                }
                _node = cur;
            }
            else{
                Node *parent = cur->_parent;
                while(parent && cur==parent->_right){
                    cur = cur->_parent;
                    parent = parent->_parent;
                }
                _node = parent;
            }
    
            return *this;
        }
    

  对于Self operator++(int)函数而言只需要调用operator++()即可;

  • 代码段

    	Self operator++(int){//后置++
            Node* cur = _node;
            ++*this;
            return Self(cur);
        }
    

• Self& operator--()与Self operator--(int)

  该函数的思路即为operator++()思路相反即可;

  在此不作过多赘述;

  • 代码段

    	Self& operator--()
        {
    
            Node* cur = _node;
            if(cur->_left){
                cur = cur->_left;
                while(cur->_right){
                    cur = cur->_right;
                }
                _node = cur;
            }
            else{
                Node *parent = cur->_parent;
                while(parent && cur == parent->_left){
                    cur = cur->_parent;
                    parent = parent->_parent;
                }
                _node = parent;
            }
            return *this;
        }
    
    
    	Self operator--(int)
        {
            Node *cur = _node;
            --*this;
            return Self(cur);
        }
    
    

• bool operator!=(const Self &s)

  该函数只需要判断其中的数据是否相同即可;

  • 代码段

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

---

🎠迭代器完整代码[不含迭代器] (供参考)

template <class T, class Ref /*数据的引用*/, class Ptr /*数据的地址*/> // 迭代器的实现
class __RBTree_Iterator
{
    typedef __RBTree_Iterator<T, Ref, Ptr> Self;
    typedef RBTreeNode<T> Node;

public:
    __RBTree_Iterator(Node *node)
        : _node(node)
    {}

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

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

    Self& operator++()//前置++
    {
        Node* cur = _node;
        if(cur->_right){
            cur = cur->_right;
            while (cur->_left){
                cur = cur->_left;
            }
            _node = cur;
        }
        else{
            Node *parent = cur->_parent;
            while(parent && cur==parent->_right){
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }

        return *this;
    }


    Self operator++(int){//后置++
        Node* cur = _node;
        ++*this;
        return Self(cur);
    }

    Self& operator--()
    {

        Node* cur = _node;
        if(cur->_left){
            cur = cur->_left;
            while(cur->_right){
                cur = cur->_right;
            }
            _node = cur;
        }
        else{
            Node *parent = cur->_parent;
            while(parent && cur == parent->_left){
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }


    Self operator--(int)
    {
        Node *cur = _node;
        --*this;
        return Self(cur);
    }

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

protected:
private:
    Node *_node;
};

---

🎡 set的封装及代码(供参考)

对于set而言在上文中提到,大部分的接口都是调用红黑树的接口,在此不进行赘述;

#include "RBTree.hpp"

enum COLOR;

namespace MYSTL
{
    template<class K>
    class Set
    {
        struct setKeyOfT
        {
            const K &operator()(const K &key)
            {
                return key;
            }
        };
        

    public:
        typedef typename RBTree<K, K, setKeyOfT>::iterator iterator;
        //typedef类模板的时候需要加上typename ,否则编译器不知道typedef的是类型还是成员变量

        std::pair<iterator,bool> Insert(const K& key){
            pair<iterator,bool> ret =  _rbt.Insert(key);
            return ret;
        }

        iterator begin(){
            return _rbt.begin();
        }

        iterator end(){
            return _rbt.end();
        }
    protected:

    private:
        RBTree<K , K , setKeyOfT> _rbt; 
        // 模板参数传入两个参数都为K
    };

---

🎡 map的封装及代码(供参考)

对于map而言,其封装手段与set相同;

唯独不同的是,在STL中的map中的[]具有两种功能:

• 插入功能

  若是该数据对应的key不存在,则将该数据进行插入,并返回其value;

• 读取功能

  若是该数据对应的key存在,则不对该数据进行插入,直接返回存在数据的value值;

要实现上述功能只需要在map中对[]进行重载即可;

• 代码段

  	V& operator[](const K& key){
              std::pair<iterator,bool> ret = _rbt.Insert(std::make_pair(key,V()));
              return ret.first->second;
          }
  

• 完整代码:

  #include "RBTree.hpp"
  
  enum COLOR;
  
  namespace MYSTL{
      template<class K,class V>
      class Map{
          struct mapKeyOfT{
              const K &operator()(const std::pair<const K, V> &kv)
              {
                  return kv.first;
              }
          };
      public:
          typedef typename RBTree<K, std::pair<const K, V>, mapKeyOfT>::iterator iterator;
          // typedef类模板的时候需要加上typename ,否则编译器不知道typedef的是类型还是成员变量
         
          pair<iterator, bool> Insert(const std::pair<const K, V> &kv) {
            pair<iterator,bool> ret = _rbt.Insert(kv);
            return ret;
          }
  
          iterator begin(){
              return _rbt.begin();
          }
  
          iterator end(){
              return _rbt.end();
          }
  
          V& operator[](const K& key){
              std::pair<iterator,bool> ret = _rbt.Insert(std::make_pair(key,V()));
              return ret.first->second;
          }
  
      protected:
  
      private:
          RBTree<K , std::pair<const K,V> , mapKeyOfT> _rbt;
          //模板参数传入两个参数分别为K类型的数据与pair
      };    
  

---