Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

rb_tree Class Template Reference

#include <stl_tree.h>

Inheritance diagram for rb_tree:

Inheritance graph
[legend]
Collaboration diagram for rb_tree:

Collaboration graph
[legend]
List of all members.

Public Types

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
typedef __rb_tree_iterator<
value_type, reference, pointer > 		iterator
typedef __rb_tree_iterator<
value_type, const_reference,
const_pointer > 		const_iterator
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

Public Methods

 rb_tree (const Compare &comp=Compare())
 rb_tree (const rb_tree< Key, Value, KeyOfValue, Compare, Alloc > &x)
 ~rb_tree ()
rb_tree< Key, Value, KeyOfValue,
Compare, Alloc > & 		operator= (const rb_tree< Key, Value, KeyOfValue, Compare, Alloc > &x)
Compare key_comp () const
iterator begin ()
const_iterator begin () const
iterator end ()
const_iterator end () const
reverse_iterator rbegin ()
const_reverse_iterator rbegin () const
reverse_iterator rend ()
const_reverse_iterator rend () const
bool empty () const
size_type size () const
size_type max_size () const
void swap (rb_tree< Key, Value, KeyOfValue, Compare, Alloc > &t)
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)
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)
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 ()
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
bool __rb_verify () const

Protected Types

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

Protected Methods

link_type get_node ()
void put_node (link_type p)
link_type create_node (const value_type &x)
link_type clone_node (link_type x)
void destroy_node (link_type p)
link_type & root () const
link_type & leftmost () const
link_type & rightmost () const

Static Protected Methods

link_type & left (link_type x)
link_type & right (link_type x)
link_type & parent (link_type x)
reference value (link_type x)
const Key & key (link_type x)
color_type & color (link_type x)
link_type & left (base_ptr x)
link_type & right (base_ptr x)
link_type & parent (base_ptr x)
reference value (base_ptr x)
const Key & key (base_ptr x)
color_type & color (base_ptr x)
link_type minimum (link_type x)
link_type maximum (link_type x)

Protected Attributes

size_type node_count
link_type header
Compare key_compare

Private Methods

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 ()

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree< Key, Value, KeyOfValue, Compare, Alloc >

Member Typedef Documentation

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef __rb_tree_node_base* rb_tree::base_ptr [protected]
 

Definition at line 423 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef __rb_tree_color_type rb_tree::color_type [protected]
 

Definition at line 426 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::color.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef __rb_tree_iterator<value_type, const_reference, const_pointer> rb_tree::const_iterator
 

Definition at line 496 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef const value_type* rb_tree::const_pointer
 

Definition at line 431 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef const value_type& rb_tree::const_reference
 

Definition at line 433 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef reverse_bidirectional_iterator<const_iterator, value_type, const_reference, difference_type> rb_tree::const_reverse_iterator
 

Definition at line 507 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rbegin, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rend.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef ptrdiff_t rb_tree::difference_type
 

Definition at line 436 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef __rb_tree_iterator<value_type, reference, pointer> rb_tree::iterator
 

Definition at line 494 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef Key rb_tree::key_type
 

Definition at line 428 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef rb_tree_node* rb_tree::link_type
 

Definition at line 434 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::color, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::key.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef value_type* rb_tree::pointer
 

Definition at line 430 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef __rb_tree_node<Value> rb_tree::rb_tree_node [protected]
 

Definition at line 424 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef simple_alloc<rb_tree_node, Alloc> rb_tree::rb_tree_node_allocator [protected]
 

Definition at line 425 of file stl_tree.h.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef value_type& rb_tree::reference
 

Definition at line 432 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::value.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef reverse_bidirectional_iterator<iterator, value_type, reference, difference_type> rb_tree::reverse_iterator
 

Definition at line 504 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rbegin, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rend.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef size_t rb_tree::size_type
 

Definition at line 435 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::max_size, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::size.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef Value rb_tree::value_type
 

Definition at line 429 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::create_node.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typedef void* rb_tree::void_pointer [protected]
 

Definition at line 422 of file stl_tree.h.

Constructor & Destructor Documentation

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::rb_tree (  const Compare &    comp = Compare() )  [inline]
 

Definition at line 523 of file stl_tree.h. 

00524     : node_count(0), key_compare(comp) { init(); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::rb_tree (  const rb_tree< Key, Value, KeyOfValue, Compare, Alloc > &    x )  [inline]
 

Definition at line 526 of file stl_tree.h. 

00527     : node_count(0), key_compare(x.key_compare)
00528   { 
00529     header = get_node();
00530     color(header) = __rb_tree_red;
00531     if (x.root() == 0) {
00532       root() = 0;
00533       leftmost() = header;
00534       rightmost() = header;
00535     }
00536     else {
00537       __STL_TRY {
00538         root() = __copy(x.root(), header);
00539       }
00540       __STL_UNWIND(put_node(header));
00541       leftmost() = minimum(root());
00542       rightmost() = maximum(root());
00543     }
00544     node_count = x.node_count;
00545   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::~rb_tree (    )  [inline]
 

Definition at line 546 of file stl_tree.h. 

00546              {
00547     clear();
00548     put_node(header);
00549   }

Member Function Documentation

template<class K, class V, class KeyOfValue, class Compare, class Alloc>
rb_tree< K, V, KeyOfValue, Compare, Alloc >::link_type rb_tree< K, V, KeyOfValue, Compare, Alloc >::__copy (  link_type    x,
link_type    p
)  [private]
 

Definition at line 877 of file stl_tree.h.

References __erase, __STL_TRY, __STL_UNWIND, clone_node, __rb_tree_node_base::left, left, __rb_tree_node_base::parent, right, and __rb_tree_node_base::right.

Referenced by operator=, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00877                                                                           {
00878                                 // structural copy.  x and p must be non-null.
00879   link_type top = clone_node(x);
00880   top->parent = p;
00881  
00882   __STL_TRY {
00883     if (x->right)
00884       top->right = __copy(right(x), top);
00885     p = top;
00886     x = left(x);
00887 
00888     while (x != 0) {
00889       link_type y = clone_node(x);
00890       p->left = y;
00891       y->parent = p;
00892       if (x->right)
00893         y->right = __copy(right(x), y);
00894       p = y;
00895       x = left(x);
00896     }
00897   }
00898   __STL_UNWIND(__erase(top));
00899 
00900   return top;
00901 }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::__erase (  link_type    x )  [private]
 

Definition at line 904 of file stl_tree.h.

References destroy_node, left, and right.

Referenced by __copy, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::clear. 

00904                                                                          {
00905                                 // erase without rebalancing
00906   while (x != 0) {
00907     __erase(right(x));
00908     link_type y = left(x);
00909     destroy_node(x);
00910     x = y;
00911   }
00912 }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::__insert (  base_ptr    x,
base_ptr    y,
const value_type &    v
)  [private]
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>
bool rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::__rb_verify (    )  const
 

Definition at line 1059 of file stl_tree.h.

References __black_count, __rb_tree_red, begin, __rb_tree_node_base::color, end, key, key_compare, left, __rb_tree_node_base::left, leftmost, __rb_tree_node_base::maximum, __rb_tree_node_base::minimum, __rb_tree_base_iterator::node, node_count, right, __rb_tree_node_base::right, rightmost, and root. 

01060 {
01061   if (node_count == 0 || begin() == end())
01062     return node_count == 0 && begin() == end() &&
01063       header->left == header && header->right == header;
01064   
01065   int len = __black_count(leftmost(), root());
01066   for (const_iterator it = begin(); it != end(); ++it) {
01067     link_type x = (link_type) it.node;
01068     link_type L = left(x);
01069     link_type R = right(x);
01070 
01071     if (x->color == __rb_tree_red)
01072       if ((L && L->color == __rb_tree_red) ||
01073           (R && R->color == __rb_tree_red))
01074         return false;
01075 
01076     if (L && key_compare(key(x), key(L)))
01077       return false;
01078     if (R && key_compare(key(R), key(x)))
01079       return false;
01080 
01081     if (!L && !R && __black_count(x, root()) != len)
01082       return false;
01083   }
01084 
01085   if (leftmost() != __rb_tree_node_base::minimum(root()))
01086     return false;
01087   if (rightmost() != __rb_tree_node_base::maximum(root()))
01088     return false;
01089 
01090   return true;
01091 }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::begin (    )  const [inline]
 

Definition at line 557 of file stl_tree.h. 

00557 { return leftmost(); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::begin (    )  [inline]
 

Definition at line 556 of file stl_tree.h.

Referenced by __rb_verify, erase, operator==, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rend. 

00556 { return leftmost(); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::clear (    )  [inline]
 

Definition at line 602 of file stl_tree.h.

Referenced by erase, operator=, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::~rb_tree. 

00602                {
00603     if (node_count != 0) {
00604       __erase(root());
00605       leftmost() = header;
00606       root() = 0;
00607       rightmost() = header;
00608       node_count = 0;
00609     }
00610   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::clone_node (  link_type    x )  [inline, protected]
 

Definition at line 450 of file stl_tree.h.

Referenced by __copy. 

00450                                     {
00451     link_type tmp = create_node(x->value_field);
00452     tmp->color = x->color;
00453     tmp->left = 0;
00454     tmp->right = 0;
00455     return tmp;
00456   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
color_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::color (  base_ptr    x )  [inline, static, protected]
 

Definition at line 484 of file stl_tree.h. 

00484 { return (color_type&)(link_type(x)->color); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
color_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::color (  link_type    x )  [inline, static, protected]
 

Definition at line 477 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::init, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00477 { return (color_type&)(x->color); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
size_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::count (  const key_type &    x )  const
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::create_node (  const value_type &    x )  [inline, protected]
 

Definition at line 441 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::clone_node. 

00441                                              {
00442     link_type tmp = get_node();
00443     __STL_TRY {
00444       construct(&tmp->value_field, x);
00445     }
00446     __STL_UNWIND(put_node(tmp));
00447     return tmp;
00448   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::destroy_node (  link_type    p )  [inline, protected]
 

Definition at line 458 of file stl_tree.h.

Referenced by __erase, and erase. 

00458                                  {
00459     destroy(&p->value_field);
00460     put_node(p);
00461   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
bool rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::empty (    )  const [inline]
 

Definition at line 568 of file stl_tree.h. 

00568 { return node_count == 0; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::end (    )  const [inline]
 

Definition at line 559 of file stl_tree.h. 

00559 { return header; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::end (    )  [inline]
 

Definition at line 558 of file stl_tree.h.

Referenced by __rb_verify, erase, operator==, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rbegin. 

00558 { return header; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
pair<const_iterator, const_iterator> rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::equal_range (  const key_type &    x )  const
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
pair<iterator,iterator> rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::equal_range (  const key_type &    x ) 
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::erase (  const key_type *    first,
const key_type *    last
) 
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::erase (  iterator    first,
iterator    last
) 
 

Definition at line 915 of file stl_tree.h.

References begin, clear, end, and erase. 

00916                                                                            {
00917   if (first == begin() && last == end())
00918     clear();
00919   else
00920     while (first != last) erase(first++);
00921 }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
size_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::erase (  const key_type &    x ) 
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::erase (  iterator    position )  [inline]
 

Definition at line 856 of file stl_tree.h.

References __rb_tree_rebalance_for_erase, destroy_node, __rb_tree_node_base::left, __rb_tree_base_iterator::node, node_count, __rb_tree_node_base::parent, and __rb_tree_node_base::right.

Referenced by erase. 

00856                                                                         {
00857   link_type y = (link_type) __rb_tree_rebalance_for_erase(position.node,
00858                                                           header->parent,
00859                                                           header->left,
00860                                                           header->right);
00861   destroy_node(y);
00862   --node_count;
00863 }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::find (  const key_type &    x )  const
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::find (  const key_type &    x ) 
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::get_node (    )  [inline, protected]
 

Definition at line 438 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::create_node, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::init, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00438 { return rb_tree_node_allocator::allocate(); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::init (    )  [inline, private]
 

Definition at line 513 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00513               {
00514     header = get_node();
00515     color(header) = __rb_tree_red; // used to distinguish header from 
00516                                    // root, in iterator.operator++
00517     root() = 0;
00518     leftmost() = header;
00519     rightmost() = header;
00520   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::insert_equal (  const value_type *    first,
const value_type *    last
) 
 

template<class K, class V, class KoV, class Cmp, class Al>
void rb_tree< K, V, KoV, Cmp, Al >::insert_equal (  const_iterator    first,
const_iterator    last
) 
 

Definition at line 831 of file stl_tree.h.

References insert_equal. 

00832                                                                {
00833   for ( ; first != last; ++first)
00834     insert_equal(*first);
00835 }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::insert_equal (  iterator    position,
const value_type &    x
) 
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::insert_equal (  const value_type &    x ) 
 

Referenced by insert_equal.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::insert_unique (  const value_type *    first,
const value_type *    last
) 
 

template<class K, class V, class KoV, class Cmp, class A>
void rb_tree< K, V, KoV, Cmp, A >::insert_unique (  const_iterator    first,
const_iterator    last
) 
 

Definition at line 846 of file stl_tree.h.

References insert_unique. 

00847                                                                {
00848   for ( ; first != last; ++first)
00849     insert_unique(*first);
00850 }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::insert_unique (  iterator    position,
const value_type &    x
) 
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
pair<iterator,bool> rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::insert_unique (  const value_type &    x ) 
 

Referenced by insert_unique.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const Key& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::key (  base_ptr    x )  [inline, static, protected]
 

Definition at line 483 of file stl_tree.h. 

00483 { return KeyOfValue()(value(link_type(x)));}

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const Key& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::key (  link_type    x )  [inline, static, protected]
 

Definition at line 476 of file stl_tree.h.

Referenced by __rb_verify. 

00476 { return KeyOfValue()(value(x)); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
Compare rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::key_comp (    )  const [inline]
 

Definition at line 555 of file stl_tree.h. 

00555 { return key_compare; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::left (  base_ptr    x )  [inline, static, protected]
 

Definition at line 479 of file stl_tree.h. 

00479 { return (link_type&)(x->left); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::left (  link_type    x )  [inline, static, protected]
 

Definition at line 472 of file stl_tree.h.

Referenced by __copy, __erase, and __rb_verify. 

00472 { return (link_type&)(x->left); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::leftmost (    )  const [inline, protected]
 

Definition at line 469 of file stl_tree.h.

Referenced by __rb_verify, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::begin, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::clear, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::init, operator=, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00469 { return (link_type&) header->left; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::lower_bound (  const key_type &    x )  const
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::lower_bound (  const key_type &    x ) 
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
size_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::max_size (    )  const [inline]
 

Definition at line 570 of file stl_tree.h. 

00570 { return size_type(-1); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::maximum (  link_type    x )  [inline, static, protected]
 

Definition at line 489 of file stl_tree.h.

Referenced by operator=, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00489                                         {
00490     return (link_type) __rb_tree_node_base::maximum(x);
00491   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::minimum (  link_type    x )  [inline, static, protected]
 

Definition at line 486 of file stl_tree.h.

Referenced by operator=, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00486                                         { 
00487     return (link_type)  __rb_tree_node_base::minimum(x);
00488   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>
rb_tree< Key, Value, KeyOfValue, Compare, Alloc > & rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::operator= (  const rb_tree< Key, Value, KeyOfValue, Compare, Alloc > &    x ) 
 

Definition at line 655 of file stl_tree.h.

References __copy, clear, key_compare, leftmost, maximum, minimum, node_count, rightmost, and root. 

00655                                                                     {
00656   if (this != &x) {
00657                                 // Note that Key may be a constant type.
00658     clear();
00659     node_count = 0;
00660     key_compare = x.key_compare;        
00661     if (x.root() == 0) {
00662       root() = 0;
00663       leftmost() = header;
00664       rightmost() = header;
00665     }
00666     else {
00667       root() = __copy(x.root(), header);
00668       leftmost() = minimum(root());
00669       rightmost() = maximum(root());
00670       node_count = x.node_count;
00671     }
00672   }
00673   return *this;
00674 }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::parent (  base_ptr    x )  [inline, static, protected]
 

Definition at line 481 of file stl_tree.h. 

00481 { return (link_type&)(x->parent); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::parent (  link_type    x )  [inline, static, protected]
 

Definition at line 474 of file stl_tree.h. 

00474 { return (link_type&)(x->parent); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::put_node (  link_type    p )  [inline, protected]
 

Definition at line 439 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::create_node, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::destroy_node, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::~rb_tree. 

00439 { rb_tree_node_allocator::deallocate(p); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const_reverse_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::rbegin (    )  const [inline]
 

Definition at line 561 of file stl_tree.h. 

00561                                         { 
00562     return const_reverse_iterator(end()); 
00563   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
reverse_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::rbegin (    )  [inline]
 

Definition at line 560 of file stl_tree.h. 

00560 { return reverse_iterator(end()); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const_reverse_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::rend (    )  const [inline]
 

Definition at line 565 of file stl_tree.h. 

00565                                       { 
00566     return const_reverse_iterator(begin());
00567   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
reverse_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::rend (    )  [inline]
 

Definition at line 564 of file stl_tree.h. 

00564 { return reverse_iterator(begin()); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::right (  base_ptr    x )  [inline, static, protected]
 

Definition at line 480 of file stl_tree.h. 

00480 { return (link_type&)(x->right); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::right (  link_type    x )  [inline, static, protected]
 

Definition at line 473 of file stl_tree.h.

Referenced by __copy, __erase, and __rb_verify. 

00473 { return (link_type&)(x->right); }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::rightmost (    )  const [inline, protected]
 

Definition at line 470 of file stl_tree.h.

Referenced by __rb_verify, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::clear, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::init, operator=, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00470 { return (link_type&) header->right; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type& rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::root (    )  const [inline, protected]
 

Definition at line 468 of file stl_tree.h.

Referenced by __rb_verify, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::clear, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::init, operator=, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree. 

00468 { return (link_type&) header->parent; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
size_type rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::size (    )  const [inline]
 

Definition at line 569 of file stl_tree.h.

Referenced by operator==. 

00569 { return node_count; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
void rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::swap (  rb_tree< Key, Value, KeyOfValue, Compare, Alloc > &    t )  [inline]
 

Definition at line 572 of file stl_tree.h. 

00572                                                                 {
00573     __STD::swap(header, t.header);
00574     __STD::swap(node_count, t.node_count);
00575     __STD::swap(key_compare, t.key_compare);
00576   }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
const_iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::upper_bound (  const key_type &    x )  const
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
iterator rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::upper_bound (  const key_type &    x ) 
 

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
reference rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::value (  base_ptr    x )  [inline, static, protected]
 

Definition at line 482 of file stl_tree.h. 

00482 { return ((link_type)x)->value_field; }

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
reference rb_tree< Key, Value, KeyOfValue, Compare, Alloc >::value (  link_type    x )  [inline, static, protected]
 

Definition at line 475 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::key. 

00475 { return x->value_field; }

Member Data Documentation

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
link_type rb_tree::header [protected]
 

Definition at line 465 of file stl_tree.h.

Referenced by rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::swap.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
Compare rb_tree::key_compare [protected]
 

Definition at line 466 of file stl_tree.h.

Referenced by __rb_verify, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::key_comp, operator=, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::swap.

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
size_type rb_tree::node_count [protected]
 

Definition at line 464 of file stl_tree.h.

Referenced by __rb_verify, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::clear, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::empty, erase, operator=, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::rb_tree, rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::size, and rb_tree< key_type, value_type, select1st< value_type >, key_compare, Alloc >::swap.

The documentation for this class was generated from the following file:
logo OpenMask

Documentation generated on Thu May 2 15:03:41 2002

Generated with doxygen 1.2.12 by Dimitri van Heesch ,   1997-2001