[STL] 관련 용기 - 붉 은 검 은 나무

set, map, multiset, multimap 네 가지 관련 용기 의 내 부 는 모두 빨 간 검 은 나무 로 이 루어 진다.STL 에서 붉 은 검 은 나 무 는 외부 에 사용 되 지 않 는 다.
독립 용기
。용기 인 만큼 메모리 공간 (노드) 을 분배 하고 내부 에 도 교체 기 가 존재 한다.붉 은 검 은 나무의 일부 성질 에 대해 서 는 '데이터 구조' 중의 필 기 를 참고 할 수 있 으 며, 여기 에는 STL 의 붉 은 검 은 나무 가 어떻게 실현 되 었 는 지 만 기록 되 어 있다.
slist 와 마찬가지 로 빨 간 검 은 나무의 노드 와 교체 기 는 모두 이중 구 조 를 사용 했다.
노드:rb_tree_node 상속 자rb_tree_node_base
교체 기:rb_tree_iterator 상속 자rb_tree_base_iterator
먼저 색상 표 지 를 보 세 요.

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;  // RB             
  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;
  }
};

기본 노드 는 일부 유형 과 지침 을 정 의 했 고 두 조작 은 최소, 최대 치 를 구 하 는 것 이다.
상단 노드:

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

상부 노드 는 간단 합 니 다. 포인터 형식 과 노드 값 을 저장 하 는 변수 만 포함 합 니 다.
기본 교체 기:

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()  //    ++   
  {
       ....
  }
 
  void decrement()  //    --   
  {
       ....
  }
};

기본 교체 기 에서 node 구성원 을 주의 하고 그 다음 에 operator + 와 operator - 를 제공 하 는 내부 방법 입 니 다. 그들 은 빨 간 검 은 나무 특성 에 따라 node 가 뒤의 하나 또는 앞의 노드 를 가리 키 게 합 니 다. 빨 간 검 은 나 무 는 이 진 트 리 이기 때문에 키 값 이 인접 한 노드 를 찾 는 것 은 규칙 적 으로 따라 갈 수 있 습 니 다.그래서 붉 은 검 은 나무의 교체 기 는 양 방향 교체 기 에 속한다.
상층 교체 기:

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; } //    node
  __rb_tree_iterator(const iterator& it) { node = it.node; }
 
  reference operator*() const { return link_type(node)->value_field; }  //    ，  link_type    
  pointer operator->() const { return &(operator*()); }    //      
 
  self& operator++() { increment(); return *this; }
  self operator++(int) {
      ....
  }
     
  self& operator--() { decrement(); return *this; }
  self operator--(int) {
      ....
  }
};

상층 교체 기 는 빨 간 검 은 나무 류 의 교체 기 입 니 다. 그 + 또는 - 작업 은 결국 기본 교체 기 중의 increment () 또는 decrement () 를 호출 했 습 니 다.
다음은 빨 간 검 은 나무의 데이터 구조 구 조 를 기록 합 니 다.

template <class Key, class Value, class KeyOfValue, class Compare,
          class Alloc = alloc>
class rb_tree {
  ....
  typedef __rb_tree_node<Value> rb_tree_node;
  typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator; //      ，        
  typedef rb_tree_node* link_type;
 
  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();
    construct(&tmp->value_field, x);
    return tmp;
  }
  ....
  void destroy_node(link_type p) {  //          
    destroy(&p->value_field);
    put_node(p);
  }
protected:
  size_type node_count; //       
  link_type header;     //         
  Compare key_compare;  //         
 
  ....
  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 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:
  pair<iterator,bool> insert_unique(const value_type& x);  //         
  iterator insert_equal(const value_type& x);            //         
  void erase(iterator position);                           //     
  ....
 
public:
  //      multimap multiset   
  iterator find(const key_type& x);
  size_type count(const key_type& x) const;
  iterator lower_bound(const key_type& x);
  iterator upper_bound(const key_type& x);
  pair<iterator,iterator> equal_range(const key_type& x);
}

위 코드 의 빨간색 부분 은 노드 가 루트 일 때의 경계 상황 을 처리 하 는 기술 을 사 용 했 습 니 다. 이것 은 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; }

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

header 가 가리 키 는 노드 의 색 을 빨간색 (뿌리 노드 의 검은색 을 구별 하기 위해) 으로 설정 합 니 다. 이것 은 뿌리 노드 가 아니 라 보초병 노드 와 유사 합 니 다.header 의 parent 는 루트 를 가리 키 고 있 습 니 다. (여기 서 null 로 초기 화 됨)left 는 항상 최소 노드 를 가리킨다.right 는 항상 최대 노드 를 가리킨다.header 가 이 정 보 를 기록 한 후에 용기 의 begin (), end () 는 잘 구 할 수 있 습 니 다.

iterator begin() { return leftmost(); }   // header->left
iterator end() { return header; }       //   header，  __rb_tree_iterator           

다른 용기 와 마찬가지 로 end () 역시 마지막 요소 (최대 노드) 의 다음 노드 를 되 돌려 줍 니 다.
참고:
《 STL 소스 분석 》 P213.