關聯容器 — 紅黑樹 · 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); } ~~~ 注意上面代碼的紅色部分使用了一個技巧來處理節點為root時的邊界情況，它使用了一個header指針。先看看初始化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始終指向root（這里初始化為null）；left始終指向最小節點；right始終指向最大節點。header記錄了這些信息之后，容器的begin()、end()就很好求了： ~~~ iterator begin() { return leftmost(); } // header->left iterator end() { return header; } // 返回header，調用__rb_tree_iterator構造函數由指針轉迭代器 ~~~ 和其它容器一樣，end()同樣是返回最后一個元素（最大節點）的下一個節點。參考：《STL源碼剖析》 P213.