STL 源码分析： RB_tree 红黑树（二）

￡神魔★判官ぃ 2023-06-19 15:28 4阅读 0赞

STL的红黑树在stl\_tree.h 头文件实现了。  
首先stl\_tree.h就有一段话：

> /*Red-black tree class, designed for use in implementing STL  
> associative containers (set, multiset, map, and multimap). The  
> insertion and deletion algorithms are based on those in Cormen,  
> Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),  
> except that  
> (1) the header cell is maintained with links not only to the root  
> but also to the leftmost node of the tree, to enable constant time  
> begin(), and to the rightmost node of the tree, to enable linear time  
> performance when used with the generic set algorithms (set\_union,  
> etc.);  
> (2) when a node being deleted has two children its successor node is  
> relinked into its place, rather than copied, so that the only  
> iterators invalidated are those referring to the deleted node.*/

意思是说，STL红黑树的实现是根据《算法导论》写的来的，只不过有一些特别注意的：STL的实现里面，头节点header就是算法导论里面说的那个T.nil节点，这个节点是红色的，它不但指向树根，它的左孩子还指向整个树的最小节点，右孩子指向整棵树的最大节点。用一个图直观来看就是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70]

# 红黑树节点非数据域的设计 #

typedef bool __rb_tree_color_type;
    const __rb_tree_color_type __rb_tree_red = false;
    const __rb_tree_color_type __rb_tree_black = true;
    
    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;
    
      static base_ptr minimum(base_ptr x)
      { 
        while (x->left != 0) x = x->left;
        return x;
      }
    
      static base_ptr maximum(base_ptr x)
      { 
        while (x->right != 0) x = x->right;
        return x;
      }
    };

非数据域由color,parent,left,right组成，分别维护一个节点的颜色、父节点指针、左右孩子指针。

同时，已该节点为根的子树的最大、最小值都是特别好获取的。最小值，只要一直往左走就可以，最大值只要一直向右走就行。

# 节点的定义 #

template <class Value>
    struct __rb_tree_node : public __rb_tree_node_base
    { 
      typedef __rb_tree_node<Value>* link_type;
      Value value_field;
    };

节点是一个从\_\_rb\_tree\_node\_base继承而来的模板类，多了一个数据域 value\_field。

# rb\_tree迭代器基类 #

红黑树提供了它自己元素的访问迭代器，rb\_tree为了复用方便，先写了它的基类。

struct __rb_tree_base_iterator
    { 
      typedef __rb_tree_node_base::base_ptr base_ptr;
      typedef bidirectional_iterator_tag iterator_category;
      typedef ptrdiff_t difference_type;
      base_ptr node;
    
      void increment()
      { 
        if (node->right != 0) { 
          node = node->right;
          while (node->left != 0)
            node = node->left;
        }
        else { 
          base_ptr y = node->parent;
          while (node == y->right) { 
            node = y;
            y = y->parent;
          }
          if (node->right != y)
            node = y;
        }
      }
    
      void decrement()
      { 
        if (node->color == __rb_tree_red &&
            node->parent->parent == node)
          node = node->right;
        else if (node->left != 0) { 
          base_ptr y = node->left;
          while (y->right != 0)
            y = y->right;
          node = y;
        }
        else { 
          base_ptr y = node->parent;
          while (node == y->left) { 
            node = y;
            y = y->parent;
          }
          node = y;
        }
      }
    };

在迭代器的基类里面，首先确定了红黑树的迭代器是双向的，可自增、自减，其次迭代器使用node指针来指向真正的节点。  
接下来，基类里面实现了自增和自减运算符需要调用的两个函数increment()和decrement()。  
对于红黑树来说，自增和自减是什么意思呢？  
**increment** 表示让迭代器指向当前红黑树里面下一个更大的数字，假设迭代器指向最小元素，那么一直调用increment()其实就是让迭代器单调的遍历整个红黑树。  
**decrement** 则表示让迭代器指向下一个更小的数字。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70 1]  
例如，假设当前迭代器指向20这个节点。那么它调用increment()一次，就会指向30。  
它decrement（）一次就会指向15。  
我们考虑两种特殊情况：当迭代器指向最小值5和最大值90的时候，对它increment()和decrement()会怎么样。

## 迭代器指向5 ##

### increment() ###

自增的话，按常规的，指向下一个更大的元素10.

### decrement() ###

此时，node->left为NULL,于是执行：

base_ptr y = node->parent;
          while (node == y->left) { 
            node = y;
            y = y->parent;
          }
          node = y;

它会一直沿着5->10->15->30向上走，直到node指向30的时候，node的父节点的left不等于node。  
此时，迭代器指向header了。说明，最小值的迭代器再减就到头了。

## 迭代器指向90 ##

### decrement() ###

常规的，指向下一个更小的元素80.

### increment() ###

也是一样的，走

base_ptr y = node->parent;
          while (node == y->right) { 
            node = y;
            y = y->parent;
          }
          if (node->right != y)
            node = y;

此时，迭代器指向最大值变成指向header了。

## 迭代器指向header ##

### increment() ###

如果从header开始，increment会怎么样呢？

void increment()
      { 
        if (node->right != 0) { 
          node = node->right;
          while (node->left != 0)
            node = node->left;
        }
        else { 
          base_ptr y = node->parent;
          while (node == y->right) { 
            node = y;
            y = y->parent;
          }
          if (node->right != y)
            node = y;
        }
      }

执行node->right!=0的分治，直接跳到最大值了。

### decrement() ###

void decrement()
      { 
        if (node->color == __rb_tree_red &&
            node->parent->parent == node)
          node = node->right;
        else if (node->left != 0) { 
          base_ptr y = node->left;
          while (y->right != 0)
            y = y->right;
          node = y;
        }
        else { 
          base_ptr y = node->parent;
          while (node == y->left) { 
            node = y;
            y = y->parent;
          }
          node = y;
        }
      }

第一个条件：`if (node->color == __rb_tree_red && node->parent->parent == node)` 真是检测当前迭代器指向的是不是header,只有header才满足颜色为红，同时header的父亲的父亲还是它自己。  
于是，node就从header跳到最大值去了。  
也就是说，如果当前迭代器指向header了，对它不管是增还是减，迭代器都会指向最大值。

# 迭代器类 #

template <class Value, class Ref, class Ptr>
    struct __rb_tree_iterator : public __rb_tree_base_iterator
    { 
      typedef Value value_type;
      typedef Ref reference;
      typedef Ptr pointer;
      typedef __rb_tree_iterator<Value, Value&, Value*>             iterator;
      typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
      typedef __rb_tree_iterator<Value, Ref, Ptr>                   self;
      typedef __rb_tree_node<Value>* link_type;
    
      __rb_tree_iterator() { }
      __rb_tree_iterator(link_type x) {  node = x; }
      __rb_tree_iterator(const iterator& it) {  node = it.node; }
    
      reference operator*() const {  return link_type(node)->value_field; }
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
      pointer operator->() const {  return &(operator*()); }
    #endif /* __SGI_STL_NO_ARROW_OPERATOR */
    
      self& operator++() {  increment(); return *this; }
      self operator++(int) { 
        self tmp = *this;
        increment();
        return tmp;
      }
        
      self& operator--() {  decrement(); return *this; }
      self operator--(int) { 
        self tmp = *this;
        decrement();
        return tmp;
      }
    };

对基类进行了继承，同时重载了取值，自增、自减等运算符。

迭代器的逻辑运算：看迭代器指向的对象是不是相等或不相等的。

inline bool operator==(const __rb_tree_base_iterator& x,
                           const __rb_tree_base_iterator& y) { 
      return x.node == y.node;
    }
    
    inline bool operator!=(const __rb_tree_base_iterator& x,
                           const __rb_tree_base_iterator& y) { 
      return x.node != y.node;
    }

# rb\_tree类的设计 #

template <class Key, class Value, class KeyOfValue, class Compare,
              class Alloc = alloc>
    class rb_tree { 
    protected:
      typedef void* void_pointer;
      typedef __rb_tree_node_base* base_ptr;
      typedef __rb_tree_node<Value> rb_tree_node;
      typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
      typedef __rb_tree_color_type color_type;
    public:
      typedef Key key_type;
      typedef Value value_type;
      typedef value_type* pointer;
      typedef const value_type* const_pointer;
      typedef value_type& reference;
      typedef const value_type& const_reference;
      typedef rb_tree_node* link_type;
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;
    protected:
      link_type get_node() {  return rb_tree_node_allocator::allocate(); }
      void put_node(link_type p) {  rb_tree_node_allocator::deallocate(p); }
    
      link_type create_node(const value_type& x) { 
        link_type tmp = get_node();
        __STL_TRY { 
          construct(&tmp->value_field, x);
        }
        __STL_UNWIND(put_node(tmp));
        return tmp;
      }
    
      link_type clone_node(link_type x) { 
        link_type tmp = create_node(x->value_field);
        tmp->color = x->color;
        tmp->left = 0;
        tmp->right = 0;
        return tmp;
      }
    
      void destroy_node(link_type p) { 
        destroy(&p->value_field);
        put_node(p);
      }
    
    protected:
      size_type node_count; // keeps track of size of tree
      link_type header;  
      Compare key_compare;
    
      link_type& root() const {  return (link_type&) header->parent; }
      link_type& leftmost() const {  return (link_type&) header->left; }
      link_type& rightmost() const {  return (link_type&) header->right; }
    
      static link_type& left(link_type x) {  return (link_type&)(x->left); }
      static link_type& right(link_type x) {  return (link_type&)(x->right); }
      static link_type& parent(link_type x) {  return (link_type&)(x->parent); }
      static reference value(link_type x) {  return x->value_field; }
      static const Key& key(link_type x) {  return KeyOfValue()(value(x)); }
      static color_type& color(link_type x) {  return (color_type&)(x->color); }
    
      static link_type& left(base_ptr x) {  return (link_type&)(x->left); }
      static link_type& right(base_ptr x) {  return (link_type&)(x->right); }
      static link_type& parent(base_ptr x) {  return (link_type&)(x->parent); }
      static reference value(base_ptr x) {  return ((link_type)x)->value_field; }
      static const Key& key(base_ptr x) {  return KeyOfValue()(value(link_type(x)));} 
      static color_type& color(base_ptr x) {  return (color_type&)(link_type(x)->color); }
    
      static link_type minimum(link_type x) {  
        return (link_type)  __rb_tree_node_base::minimum(x);
      }
      static link_type maximum(link_type x) { 
        return (link_type) __rb_tree_node_base::maximum(x);
      }
    
    public:
      typedef __rb_tree_iterator<value_type, reference, pointer> iterator;
      typedef __rb_tree_iterator<value_type, const_reference, const_pointer> 
              const_iterator;
    
    #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
      typedef reverse_iterator<const_iterator> const_reverse_iterator;
      typedef reverse_iterator<iterator> reverse_iterator;
    #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
      typedef reverse_bidirectional_iterator<iterator, value_type, reference,
                                             difference_type>
              reverse_iterator; 
      typedef reverse_bidirectional_iterator<const_iterator, value_type,
                                             const_reference, difference_type>
              const_reverse_iterator;
    #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
    private:
      iterator __insert(base_ptr x, base_ptr y, const value_type& v);
      link_type __copy(link_type x, link_type p);
      void __erase(link_type x);
      void init() { 
        header = get_node();
        color(header) = __rb_tree_red; // used to distinguish header from 
                                       // root, in iterator.operator++
        root() = 0;
        leftmost() = header;
        rightmost() = header;
      }
    public:
                                    // allocation/deallocation
      rb_tree(const Compare& comp = Compare())
        : node_count(0), key_compare(comp) {  init(); }
    
      rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) 
        : node_count(0), key_compare(x.key_compare)
      {  
        header = get_node();
        color(header) = __rb_tree_red;
        if (x.root() == 0) { 
          root() = 0;
          leftmost() = header;
          rightmost() = header;
        }
        else { 
          __STL_TRY { 
            root() = __copy(x.root(), header);
          }
          __STL_UNWIND(put_node(header));
          leftmost() = minimum(root());
          rightmost() = maximum(root());
        }
        node_count = x.node_count;
      }
      ~rb_tree() { 
        clear();
        put_node(header);
      }
      rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& 
      operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x);
    
    public:    
                                    // accessors:
      Compare key_comp() const {  return key_compare; }
      iterator begin() {  return leftmost(); }
      const_iterator begin() const {  return leftmost(); }
      iterator end() {  return header; }
      const_iterator end() const {  return header; }
      reverse_iterator rbegin() {  return reverse_iterator(end()); }
      const_reverse_iterator rbegin() const {  
        return const_reverse_iterator(end()); 
      }
      reverse_iterator rend() {  return reverse_iterator(begin()); }
      const_reverse_iterator rend() const {  
        return const_reverse_iterator(begin());
      } 
      bool empty() const {  return node_count == 0; }
      size_type size() const {  return node_count; }
      size_type max_size() const {  return size_type(-1); }
    
      void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& t) { 
        __STD::swap(header, t.header);
        __STD::swap(node_count, t.node_count);
        __STD::swap(key_compare, t.key_compare);
      }
        
    public:
                                    // insert/erase
      pair<iterator,bool> insert_unique(const value_type& x);
      iterator insert_equal(const value_type& x);
    
      iterator insert_unique(iterator position, const value_type& x);
      iterator insert_equal(iterator position, const value_type& x);
    
    #ifdef __STL_MEMBER_TEMPLATES 
      template <class InputIterator>
      void insert_unique(InputIterator first, InputIterator last);
      template <class InputIterator>
      void insert_equal(InputIterator first, InputIterator last);
    #else /* __STL_MEMBER_TEMPLATES */
      void insert_unique(const_iterator first, const_iterator last);
      void insert_unique(const value_type* first, const value_type* last);
      void insert_equal(const_iterator first, const_iterator last);
      void insert_equal(const value_type* first, const value_type* last);
    #endif /* __STL_MEMBER_TEMPLATES */
    
      void erase(iterator position);
      size_type erase(const key_type& x);
      void erase(iterator first, iterator last);
      void erase(const key_type* first, const key_type* last);
      void clear() { 
        if (node_count != 0) { 
          __erase(root());
          leftmost() = header;
          root() = 0;
          rightmost() = header;
          node_count = 0;
        }
      }      
    
    public:
                                    // set operations:
      iterator find(const key_type& x);
      const_iterator find(const key_type& x) const;
      size_type count(const key_type& x) const;
      iterator lower_bound(const key_type& x);
      const_iterator lower_bound(const key_type& x) const;
      iterator upper_bound(const key_type& x);
      const_iterator upper_bound(const key_type& x) const;
      pair<iterator,iterator> equal_range(const key_type& x);
      pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
    
    public:
                                    // Debugging.
      bool __rb_verify() const;
    };

这是一个模板类，它有五个模板参数。  
在rb\_tree里面，key和value是分离的。key是红黑树的内部节点用于比较偏序关系的值，换句话说，红黑树里面是根据节点的key来决定节点应该往左走还是往右查。

前两个参数，Key和Value分别表示Key和Value的类型。

通常key是通过一个映射函数  K e y O f V a l u e ( ) ( v a l u e ) KeyOfValue()(value) KeyOfValue()(value) 来实现从value到key的映射。如果value是个整数，那么keyOfValue可以是个恒等映射，而如果value是个字符串，那么keyOfValue就可以是个哈希函数了。在红黑树里面，对于每个节点都是给定value,而不给定key,key是通过KeyOfValue从value生成出来。第三个参数就是这个用处的。

第四个参数Compare则是个比较偏序关系的函数，用于比较两个key那个大，那个小。

第五个参数，内存分配器。

link_type get_node() {  return rb_tree_node_allocator::allocate(); } //获取一个节点所需的内存
      void put_node(link_type p) {  rb_tree_node_allocator::deallocate(p); }
    //释放一个节点所占用的内存
      link_type create_node(const value_type& x) { 
        link_type tmp = get_node();
        __STL_TRY { 
          construct(&tmp->value_field, x);
        }
        __STL_UNWIND(put_node(tmp));
        return tmp;
      }
    //创建一个节点，并设置它的value域
      link_type clone_node(link_type x) { 
        link_type tmp = create_node(x->value_field);
        tmp->color = x->color;
        tmp->left = 0;
        tmp->right = 0;
        return tmp;
      }
    //以一个节点为模板，克隆一个节点出来，主要是把颜色和值域拷贝处理。
      void destroy_node(link_type p) { 
        destroy(&p->value_field);
        put_node(p);
      }
      //释放一个节点

## 成员变量： ##

size_type node_count; // keeps track of size of tree
      link_type header;     //头结点，用于追踪树根、最大和最小节点。
      Compare key_compare;

为啥要使用header节点呢？原因有二：

1.  方便维护整个树的最大值、最小值。
2.  方便表示迭代器的尽头，header起一个哨兵的作用。

## 乱七八糟的杂函数 ##

这一部分主要是一些基础工具函数，用于提起某个节点的左、右孩子，父节点。

//根
      link_type& root() const {  return (link_type&) header->parent; }
      //最小元素
      link_type& leftmost() const {  return (link_type&) header->left; }
      //最大元素
      link_type& rightmost() const {  return (link_type&) header->right; }
    
      static link_type& left(link_type x) {  return (link_type&)(x->left); }
      static link_type& right(link_type x) {  return (link_type&)(x->right); }
      static link_type& parent(link_type x) {  return (link_type&)(x->parent); }
      static reference value(link_type x) {  return x->value_field; }
      //给一个某个元素，根据它的value求出它的key,keyOfValue()(value(x))是个映射。
      static const Key& key(link_type x) {  return KeyOfValue()(value(x)); }
      static color_type& color(link_type x) {  return (color_type&)(x->color); }
    
      static link_type& left(base_ptr x) {  return (link_type&)(x->left); }
      static link_type& right(base_ptr x) {  return (link_type&)(x->right); }
      static link_type& parent(base_ptr x) {  return (link_type&)(x->parent); }
      static reference value(base_ptr x) {  return ((link_type)x)->value_field; }
      static const Key& key(base_ptr x) {  return KeyOfValue()(value(link_type(x)));} 
      static color_type& color(base_ptr x) {  return (color_type&)(link_type(x)->color); }
    
      static link_type minimum(link_type x) {  
        return (link_type)  __rb_tree_node_base::minimum(x);
      }
      static link_type maximum(link_type x) { 
        return (link_type) __rb_tree_node_base::maximum(x);
      }

其中，需要比较关注key函数。

static const Key& key(link_type x) {  return KeyOfValue()(value(x)); }

它提供调用KeyofValue()(value(x))，先提取节点x的value值，然后再把value映射到key。

## 构造函数 ##

rb_tree(const Compare& comp = Compare())
        : node_count(0), key_compare(comp) {  init(); }
    
      rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) 
        : node_count(0), key_compare(x.key_compare)
      {  
        header = get_node();
        color(header) = __rb_tree_red;
        if (x.root() == 0) { 
          root() = 0;
          leftmost() = header;
          rightmost() = header;
        }
        else { 
          __STL_TRY { 
            root() = __copy(x.root(), header);
          }
          __STL_UNWIND(put_node(header));
          leftmost() = minimum(root());
          rightmost() = maximum(root());
        }
        node_count = x.node_count;
      }

两个构造函数，都会把node\_count设置为0，同时设置key\_compare对象。  
对于默认构造函数，会调用init():

void init() { 
        header = get_node();
        color(header) = __rb_tree_red; // used to distinguish header from 
                                       // root, in iterator.operator++
        root() = 0;
        leftmost() = header;
        rightmost() = header;
      }

init（）很简单，先是申请一个节点的内存，然后设置它的颜色为红色。再把树根设置为0，并让header的左右指针指向自己。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70 2]  
对于复制构造函数来说，它需要通过另外一颗红黑树来初始化。

rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) 
        : node_count(0), key_compare(x.key_compare)
      {  
        header = get_node();
        color(header) = __rb_tree_red;
        if (x.root() == 0) { 
          root() = 0;
          leftmost() = header;
          rightmost() = header;
        }
        else { 
          __STL_TRY { 
            root() = __copy(x.root(), header);
          }
          __STL_UNWIND(put_node(header));
          leftmost() = minimum(root());
          rightmost() = maximum(root());
        }
        node_count = x.node_count;
      }

它的主要逻辑是递归的遍历整个给定的红黑树，把它所有的节点都拷贝出来。而且拷贝的时候，是先拷贝右子树，再拷贝左子树。遍历方式有点像先序遍历，只不过是先访问根，再访问右子树，再访问左子树。

template <class K, class V, class KeyOfValue, class Compare, class Alloc>
    typename rb_tree<K, V, KeyOfValue, Compare, Alloc>::link_type 
    rb_tree<K, V, KeyOfValue, Compare, Alloc>::__copy(link_type x, link_type p) { 
                                    // structural copy. x and p must be non-null.
      link_type top = clone_node(x);
      top->parent = p;
     
      __STL_TRY { 
        if (x->right)
          top->right = __copy(right(x), top);
        p = top;
        x = left(x);
    
        while (x != 0) { 
          link_type y = clone_node(x);
          p->left = y;
          y->parent = p;
          if (x->right)
            y->right = __copy(right(x), y);
          p = y;
          x = left(x);
        }
      }
      __STL_UNWIND(__erase(top));
    
      return top;
    }

## 析构函数 ##

~rb_tree() { 
        clear();
        put_node(header);
      }

调用clear()函数，把以根为树的整个红黑树节点全部删除、释放内存。  
最后再把header释放。

## 迭代器相关的函数 ##

iterator begin() {  return leftmost(); }
      const_iterator begin() const {  return leftmost(); }
      iterator end() {  return header; }
      const_iterator end() const {  return header; }
      reverse_iterator rbegin() {  return reverse_iterator(end()); }
      const_reverse_iterator rbegin() const {  
        return const_reverse_iterator(end()); 
      }
      reverse_iterator rend() {  return reverse_iterator(begin()); }
      const_reverse_iterator rend() const {  
        return const_reverse_iterator(begin());
      }

可以看出，begin()就是指向最小的元素的迭代器。end()指向header。rbegin()则指向header,rend()指向最小元素。

## 容量函数 ##

bool empty() const {  return node_count == 0; }
      size_type size() const {  return node_count; }
      size_type max_size() const {  return size_type(-1); }

主要是是否为空，节点个数。从源码来看，始终有node\_count维护节点个数，因此size()调用时 O ( 1 ) O(1) O(1)的。

## swap ##

void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& t) { 
        __STD::swap(header, t.header);
        __STD::swap(node_count, t.node_count);
        __STD::swap(key_compare, t.key_compare);
      }

这个函数主要用于交换两个红黑树的header和node\_count

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191207145232910.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191207144959860.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191207154452636.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY=,size_16,color_FFFFFF,t_70