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() // 迭代器--时使用 { .... }};
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) { .... }};
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);}
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; }
iterator begin() { return leftmost(); } // header->leftiterator end() { return header; }
// 返回header，调用__rb_tree_iterator构造函数由指针转迭代器
关联容器（底层机制） — 红黑树,布布扣,bubuko.com
原文：http://blog.csdn.net/nestler/article/details/25196283