SGI STL中set/map底层都是通过RB-tree实现的。

首先看看RB-tree结点的定义

1 typedef bool __rb_tree_color_type; 2 const __rb_tree_color_type __rb_tree_red = false; 3 const __rb_tree_color_type __rb_tree_black = true; 4  5 // 结点的基类 6 struct __rb_tree_node_base 7 { 8     typedef __rb_tree_color_type color_type; 9     typedef __rb_tree_node_base* base_ptr;10 11     // 关键的4个域12     color_type color; 13     base_ptr parent;14     base_ptr left;15     base_ptr right;16     17     // 返回极值18     static base_ptr minimum(base_ptr x)19    {20         while (x->left != 0) x = x->left;21         return x;22     }23 24     static base_ptr maximum(base_ptr x)25     {26         while (x->right != 0) x = x->right;27         return x;28      }29 }30 31 // 多了一个value域32 template 
      
       33 struct __rb_tree_node : public __rb_tree_node_base34 {35     typedef __rb_tree_node
       
        * link_type;36     Value value_field;37 };
       
      

下图是RB-tree结点跟其迭代器的关系

重点看看__rb_tree_iterator的operator++跟operator--，

实际是调用__rb_tree_base_iterator的increment跟decrement。

可以看出迭代器前移/后移的时候会按key的顺序找到下一个/上一个结点。

(set/map<...>::begin()会返回RB-tree中key最小的结点，因此使用operator++遍历会按key的顺序从小到大遍历结点)

1 void increment() 2 { 3     if (node->right != 0) { 4         node = node->right; 5         while (node->left != 0) 6             node = node->left; 7     } 8     else { 9         base_ptr y = node->parent;10         while (node == y->right) {11             node = y;12             y = y->parent;13         }14         if (node->right != y)15             node = y;16     }17 }18 19 void decrement()20 {21     if (node->color == __rb_tree_red &&22         node->parent->parent == node)23         node = node->right;24     else if (node->left != 0) {25         base_ptr y = node->left;26         while (y->right != 0)27             y = y->right;28         node = y;29     }30     else {31         base_ptr y = node->parent;32         while (node == y->left) {33             node = y;34             y = y->parent;35         }36         node = y;37     }38 }

 

SGI STL中的rb_tree用了一个小trick，就是使用了一个header结点，用来代表整个rb_tree。

该结点与root结点互为父结点，该结点的left指向最左(key最小)的结点，right指向最右(key最大)的结点。

 

除此之外，该rb_tree的实现跟普通的红黑树类似，详情可以查看:http://www.cnblogs.com/runnyu/p/4679279.html。

1 template 
      
        3 class rb_tree { 4     // rb_tree的基本定义 5 protected: 6     typedef __rb_tree_node_base* base_ptr; 7     typedef __rb_tree_node
       
         rb_tree_node; 8     typedef simple_alloc
        
          rb_tree_node_allocator; 9 public:10     typedef Key key_type;11     typedef Value value_type;12     typedef value_type* pointer;13     typedef value_type& reference;14     typedef rb_tree_node* link_type;15     typedef size_t size_type;16     typedef ptrdiff_t difference_type;17 18     typedef __rb_tree_iterator
         
           iterator;19 20     link_type header;21     // ...22     23     // 主要接口24     iterator begin() { return leftmost(); } // 返回最左边的结点(最小key)25     iterator end() { return header; }26     27     iterator insert_equal(const value_type& x); // 插入元素 并允许键值相同28     pair
          
            insert_unique(const value_type& x); // 插入元素 键值是独一无二的29     30 };
          
         
        
       
      

 

set/multiset

有了rb_tree，set/multiset的实现也只是调用rb_tree的接口而已。

其中set跟multiset不一样的是，set插入的时候调用的是insert_unique()，而multiset调用的是insert_equal()。

下面是给出set的基本定义：

1 template 
      
       , class Alloc = alloc> 2 class set { 3 public: 4     typedef Key key_type; 5     typedef Key value_type;  // 使用的value类型跟key一样 6     typedef Compare key_compare; 7     typedef Compare value_compare; 8 private: 9     typedef rb_tree
       
        , key_compare, Alloc> rep_type;11     rep_type t;12 public:13     // 接口的实现只是对rb_tree的封装  不一一列举了14     iterator begin() const { return t.begin(); }15     iterator end() const { return t.end(); }16     pair
        
          insert(const value_type& x) { 17         pair
         
           p = t.insert_unique(x); 18         return pair
          
           (p.first, p.second);19     }20     // ...21 };
          
         
        
       
      

 

map/multimap

map/mulitmap的实现也是通过调用rb_tree的接口。

map/mulitmap不一样的是，map插入的时候调用的是insert_unique()，而multimap调用的是insert_equal()。

下面是给出map的基本定义：

1 template 
      
       , class Alloc  2 class map { 3 public: 4     typedef Key key_type; 5     typedef T data_type; 6     typedef T mapped_type; 7     typedef pair
       
         value_type; // 在rb_tree中value的类型是pair 8     typedef Compare key_compare; 9 private:10     // select1st直接return T.first 用于rb_tree取到key进行比较大小11     typedef rb_tree
        
         , key_compare, Alloc> rep_type;13     rep_type t;14     // ...15     16     // 接口只是对rb_tree的封装  就不一一列举了17     iterator begin() { return t.begin(); }18     iterator end() { return t.end(); }19     pair
         
           insert(const value_type& x) { return t.insert_unique(x); }20      // ...21 }
         
        
       
      

 

另外STL中有未列入标准的hash_set/hash_map以及C++11中的unordered_set/map，底层是使用hashtable实现的。

相比于用rb_tree实现的set/map，它们的插入删除查找操作具有O(1)的时间复杂度(没有冲突情况下)，但是它们的元素的顺序是无序的。