Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Class template rbtree

boost::intrusive::rbtree

Synopsis

// In header: <boost/intrusive/rbtree.hpp>

template<typename T,  Options> 
class rbtree {
public:
  // types
  typedef                                     ;          
  typedef                 ;               
  typedef           ;         
  typedef              ;            
  typedef                ;              
  typedef            ;          
  typedef               ;             
  typedef         ;       
  typedef         ;       
  typedef               ;             
  typedef           ;         
  typedef             ;           
  typedef                ;              
  typedef          ;        
  typedef        ;      
  typedef  ;
  typedef             ;           
  typedef                    ;                  
  typedef                ;              
  typedef          ;        
  typedef         ;       
  typedef      ;    

  // construct/copy/destruct
  ();
  (,  = );
  template<typename Iterator> 
    (, , ,  = , 
            = );
  (rbtree &&);
  rbtree & (rbtree &&);
  ~();

  // public member functions
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   (rbtree &);
  template<typename Cloner, typename Disposer> 
     (rbtree &, , );
  template<typename Cloner, typename Disposer> 
     (rbtree &&, , );
  template<typename Cloner, typename Disposer> 
     (rbtree &&, , );
   ();
   (, );
  template<typename Iterator>  (, );
   ();
   (, );
  template<typename KeyType, typename KeyTypeKeyCompare> 
     
    (, , 
                        );
  template<typename KeyType, typename KeyTypeKeyCompare> 
     
    (, , , 
                        );
   
  (, );
   
  (, , );
   (, ) ;
  template<typename Iterator>  (, );
   (, ) ;
   () ;
   () ;
   () ;
   (, ) ;
   ();
  template<typename KeyType, typename KeyTypeKeyCompare> 
     (, );
  template<typename Disposer> 
     (, ) ;
  template<typename Disposer> 
     (, , ) ;
  template<typename Disposer> 
     (, );
  template<typename KeyType, typename KeyTypeKeyCompare, typename Disposer> 
     (, , );
   () ;
  template<typename Disposer>  () ;
   () ;
  template<typename KeyType, typename KeyTypeKeyCompare> 
     (, ) ;
   ();
  template<typename KeyType, typename KeyTypeKeyCompare> 
     (, );
   () ;
  template<typename KeyType, typename KeyTypeKeyCompare> 
     (, ) ;
   ();
  template<typename KeyType, typename KeyTypeKeyCompare> 
     (, );
   () ;
  template<typename KeyType, typename KeyTypeKeyCompare> 
     (, ) ;
   ();
  template<typename KeyType, typename KeyTypeKeyCompare> 
     (, );
   () ;
  template<typename KeyType, typename KeyTypeKeyCompare> 
     (, ) ;
   ();
  template<typename KeyType, typename KeyTypeKeyCompare> 
     
    (, );
   
  () ;
  template<typename KeyType, typename KeyTypeKeyCompare> 
     
    (, ) ;
   
  (, , , );
  template<typename KeyType, typename KeyTypeKeyCompare> 
     
    (, , , , 
                  );
   
  (, , , ) ;
  template<typename KeyType, typename KeyTypeKeyCompare> 
     
    (, , , , 
                  ) ;
   () ;
   () ;
   () ;
   (, ) ;
   () ;
  template<typename T,  Options2> 
     (rbtree< );
  template<typename T,  Options2> 
     (rbtree< );

  // public static functions
  rbtree & () ;
  rbtree & () ;
  rbtree & () ;
  rbtree & () ;
   () ;
   () ;
   () ;

  // public data members
  static  constant_time_size;
};

Description

The class template rbtree is an intrusive red-black tree container, that is used to construct intrusive set and multiset containers. The no-throw guarantee holds only, if the key_compare object doesn't throw.

The template parameter T is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.

The container supports the following options: base_hook<>/member_hook<>/value_traits<>, constant_time_size<>, size_type<> and compare<>.

rbtree public construct/copy/destruct

  1. ();

    Effects: Constructs an empty container.

    Complexity: Constant.

    Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor of the key_compare object throws. Basic guarantee.

  2. ( cmp,  v_traits = );
  3. template<typename Iterator> 
      ( unique,  b,  e,  cmp = , 
              v_traits = );
  4. (rbtree && x);

    Effects: Constructs a container moving resources from another container. Internal comparison object and value traits are move constructed and nodes belonging to x (except the node representing the "end") are linked to *this.

    Complexity: Constant.

    Throws: If value_traits::node_traits::node's move constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the move constructor of the comparison objet throws.

  5. rbtree & (rbtree && x);

    Effects: Equivalent to swap

  6. ~();

    Effects: Detaches all elements from this. The objects in the set are not deleted (i.e. no destructors are called), but the nodes according to the value_traits template parameter are reinitialized and thus can be reused.

    Complexity: Linear to elements contained in *this.

    Throws: Nothing.

rbtree public member functions

  1.  () ;

    Effects: Returns an iterator pointing to the beginning of the container.

    Complexity: Constant.

    Throws: Nothing.

  2.  () ;

    Effects: Returns a const_iterator pointing to the beginning of the container.

    Complexity: Constant.

    Throws: Nothing.

  3.  () ;

    Effects: Returns a const_iterator pointing to the beginning of the container.

    Complexity: Constant.

    Throws: Nothing.

  4.  () ;

    Effects: Returns an iterator pointing to the end of the container.

    Complexity: Constant.

    Throws: Nothing.

  5.  () ;

    Effects: Returns a const_iterator pointing to the end of the container.

    Complexity: Constant.

    Throws: Nothing.

  6.  () ;

    Effects: Returns a const_iterator pointing to the end of the container.

    Complexity: Constant.

    Throws: Nothing.

  7.  () ;

    Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  8.  () ;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  9.  () ;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  10.  () ;

    Effects: Returns a reverse_iterator pointing to the end of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  11.  () ;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  12.  () ;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  13.  () ;

    Effects: Returns a iterator pointing to the root node of the container or end() if not present.

    Complexity: Constant.

    Throws: Nothing.

  14.  () ;

    Effects: Returns a const_iterator pointing to the root node of the container or cend() if not present.

    Complexity: Constant.

    Throws: Nothing.

  15.  () ;

    Effects: Returns a const_iterator pointing to the root node of the container or cend() if not present.

    Complexity: Constant.

    Throws: Nothing.

  16.  () ;

    Effects: Returns the key_compare object used by the container.

    Complexity: Constant.

    Throws: If key_compare copy-constructor throws.

  17.  () ;

    Effects: Returns the value_compare object used by the container.

    Complexity: Constant.

    Throws: If value_compare copy-constructor throws.

  18.  () ;

    Effects: Returns true if the container is empty.

    Complexity: Constant.

    Throws: Nothing.

  19.  () ;

    Effects: Returns the number of elements stored in the container.

    Complexity: Linear to elements contained in *this if constant-time size option is disabled. Constant time otherwise.

    Throws: Nothing.

  20.  (rbtree & other);

    Effects: Swaps the contents of two containers.

    Complexity: Constant.

    Throws: If the comparison functor's swap call throws.

  21. template<typename Cloner, typename Disposer> 
       (rbtree & src,  cloner,  disposer);

    Requires: Disposer::operator()(pointer) shouldn't throw. Cloner should yield to nodes equivalent to the original nodes.

    Effects: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(const_reference ) and inserts them on *this. Copies the predicate from the source container.

    If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).

    Complexity: Linear to erased plus inserted elements.

    Throws: If cloner throws or predicate copy assignment throws. Basic guarantee.

  22. template<typename Cloner, typename Disposer> 
       (rbtree && src,  cloner,  disposer);

    Requires: Disposer::operator()(pointer) shouldn't throw. Cloner should yield to nodes equivalent to the original nodes.

    Effects: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(reference) and inserts them on *this. Copies the predicate from the source container.

    If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).

    Complexity: Linear to erased plus inserted elements.

    Throws: If cloner throws or predicate copy assignment throws. Basic guarantee.

    Note: This version can modify the source container, useful to implement move semantics.

  23. template<typename Cloner, typename Disposer> 
       (rbtree && src,  cloner,  disposer);

    Requires: Disposer::operator()(pointer) shouldn't throw. Cloner should yield to nodes equivalent to the original nodes.

    Effects: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(reference) and inserts them on *this. Copies the predicate from the source container.

    If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).

    Complexity: Linear to erased plus inserted elements.

    Throws: If cloner throws or predicate copy assignment throws. Basic guarantee.

    Note: This version can modify the source container, useful to implement move semantics.

  24.  ( value);
  25.  ( hint,  value);
  26. template<typename Iterator>  ( b,  e);

    Requires: Dereferencing iterator must yield an lvalue of type value_type.

    Effects: Inserts a each element of a range into the container before the upper bound of the key of each element.

    Complexity: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().

    Throws: If the comparison functor call throws.

    Note: Does not affect the validity of iterators and references. No copy-constructors are called.

  27.  ( value);
  28.  ( hint,  value);
  29. template<typename KeyType, typename KeyTypeKeyCompare> 
       
      ( key,  comp, 
                           commit_data);
  30. template<typename KeyType, typename KeyTypeKeyCompare> 
       
      ( hint,  key, 
                           comp, 
                           commit_data);
  31.  
    ( key,  commit_data);
  32.  
    ( hint,  key, 
                         commit_data);
  33.  ( value, 
                                   commit_data) ;

    Requires: value must be an lvalue of type value_type. commit_data must have been obtained from a previous call to "insert_check". No objects should have been inserted or erased from the container between the "insert_check" that filled "commit_data" and the call to "insert_commit".

    Effects: Inserts the value in the container using the information obtained from the "commit_data" that a previous "insert_check" filled.

    Returns: An iterator to the newly inserted object.

    Complexity: Constant time.

    Throws: Nothing.

    Notes: This function has only sense if a "insert_check" has been previously executed to fill "commit_data". No value should be inserted or erased between the "insert_check" and "insert_commit" calls.

  34. template<typename Iterator>  ( b,  e);

    Requires: Dereferencing iterator must yield an lvalue of type value_type.

    Effects: Tries to insert each element of a range into the container.

    Complexity: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().

    Throws: If the comparison functor call throws.

    Note: Does not affect the validity of iterators and references. No copy-constructors are called.

  35.  ( pos,  value) ;

    Requires: value must be an lvalue, "pos" must be a valid iterator (or end) and must be the succesor of value once inserted according to the predicate

    Effects: Inserts x into the container before "pos".

    Complexity: Constant time.

    Throws: Nothing.

    Note: This function does not check preconditions so if "pos" is not the successor of "value" container ordering invariant will be broken. This is a low-level function to be used only for performance reasons by advanced users.

  36.  ( value) ;

    Requires: value must be an lvalue, and it must be no less than the greatest inserted key

    Effects: Inserts x into the container in the last position.

    Complexity: Constant time.

    Throws: Nothing.

    Note: This function does not check preconditions so if value is less than the greatest inserted key container ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users.

  37.  ( value) ;

    Requires: value must be an lvalue, and it must be no greater than the minimum inserted key

    Effects: Inserts x into the container in the first position.

    Complexity: Constant time.

    Throws: Nothing.

    Note: This function does not check preconditions so if value is greater than the minimum inserted key container ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users.

  38.  ( i) ;
  39.  ( b,  e) ;
  40.  ( key);
  41. template<typename KeyType, typename KeyTypeKeyCompare> 
       ( key,  comp);

    Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), with nk the key_type of a value_type inserted into *this.

    Effects: Erases all the elements with the given key. according to the comparison functor "comp".

    Returns: The number of erased elements.

    Complexity: O(log(size() + N).

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

  42. template<typename Disposer> 
       ( i,  disposer) ;
  43. template<typename Disposer> 
       ( b,  e, 
                                  disposer) ;
  44. template<typename Disposer> 
       ( key,  disposer);
  45. template<typename KeyType, typename KeyTypeKeyCompare, typename Disposer> 
       ( key,  comp, 
                                   disposer);

    Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk) and nk the key_type of a value_type inserted into *this.

    Requires: Disposer::operator()(pointer) shouldn't throw.

    Effects: Erases all the elements with the given key. according to the comparison functor "comp". Disposer::operator()(pointer) is called for the removed elements.

    Returns: The number of erased elements.

    Complexity: O(log(size() + N).

    Throws: Nothing.

    Note: Invalidates the iterators to the erased elements.

  46.  () ;

    Effects: Erases all of the elements.

    Complexity: Linear to the number of elements on the container. if it's a safe-mode or auto-unlink value_type. Constant time otherwise.

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

  47. template<typename Disposer>  ( disposer) ;

    Effects: Erases all of the elements calling disposer(p) for each node to be erased. Complexity: Average complexity for is at most O(log(size() + N)), where N is the number of elements in the container.

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. Calls N times to disposer functor.

  48.  ( key) ;
  49. template<typename KeyType, typename KeyTypeKeyCompare> 
       ( key,  comp) ;

    Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this.

    Effects: Returns the number of contained elements with the given key

    Complexity: Logarithmic to the number of elements contained plus lineal to number of objects with the given key.

    Throws: If comp throws.

  50.  ( key);
  51. template<typename KeyType, typename KeyTypeKeyCompare> 
       ( key,  comp);
  52.  ( key) ;
  53. template<typename KeyType, typename KeyTypeKeyCompare> 
       
      ( key,  comp) ;
  54.  ( key);
  55. template<typename KeyType, typename KeyTypeKeyCompare> 
       ( key,  comp);

    Requires: key is a value such that *this is partitioned with respect to !comp(key, nk), with nk the key_type of a value_type inserted into *this.

    Effects: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: If comp throws.

  56.  ( key) ;
  57. template<typename KeyType, typename KeyTypeKeyCompare> 
       
      ( key,  comp) ;

    Requires: key is a value such that *this is partitioned with respect to !comp(key, nk), with nk the key_type of a value_type inserted into *this.

    Effects: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: If comp throws.

  58.  ( key);
  59. template<typename KeyType, typename KeyTypeKeyCompare> 
       ( key,  comp);

    Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this.

    Effects: Finds an iterator to the first element whose key is k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: If comp throws.

  60.  ( key) ;
  61. template<typename KeyType, typename KeyTypeKeyCompare> 
       ( key,  comp) ;

    Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this.

    Effects: Finds an iterator to the first element whose key is k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: If comp throws.

  62.  ( key);
  63. template<typename KeyType, typename KeyTypeKeyCompare> 
       
      ( key,  comp);

    Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), with nk the key_type of a value_type inserted into *this.

    Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.

    Complexity: Logarithmic.

    Throws: If comp throws.

  64.  
    ( key) ;
  65. template<typename KeyType, typename KeyTypeKeyCompare> 
       
      ( key,  comp) ;

    Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), with nk the key_type of a value_type inserted into *this.

    Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.

    Complexity: Logarithmic.

    Throws: If comp throws.

  66.  
    ( lower,  upper_key, 
                   left_closed,  right_closed);
  67. template<typename KeyType, typename KeyTypeKeyCompare> 
       
      ( lower_key,  upper_key, 
                     comp,  left_closed,  right_closed);

    Requires: lower_key is a value such that *this is partitioned with respect to comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise.

    upper_key is a value such that *this is partitioned with respect to !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise.

    upper_key shall not precede lower_key according to comp [comp(upper_key, lower_key) shall be false]

    If lower_key is equivalent to upper_key [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then ('left_closed' || 'right_closed') must be false.

    Effects: Returns an a pair with the following criteria:

    first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise

    second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise

    Complexity: Logarithmic.

    Throws: If comp throws.

    Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.

    Note: Experimental function, the interface might change in future releases.

  68.  
    ( lower_key,  upper_key, 
                   left_closed,  right_closed) ;
  69. template<typename KeyType, typename KeyTypeKeyCompare> 
       
      ( lower_key,  upper_key, 
                     comp,  left_closed,  right_closed) ;

    Requires: lower_key is a value such that *this is partitioned with respect to comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise.

    upper_key is a value such that *this is partitioned with respect to !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise.

    upper_key shall not precede lower_key according to comp [comp(upper_key, lower_key) shall be false]

    If lower_key is equivalent to upper_key [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then ('left_closed' || 'right_closed') must be false.

    Effects: Returns an a pair with the following criteria:

    first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise

    second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise

    Complexity: Logarithmic.

    Throws: If comp throws.

    Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.

    Note: Experimental function, the interface might change in future releases.

  70.  ( value) ;
  71.  ( value) ;
  72.  () ;

    Effects: Unlinks the leftmost node from the container.

    Complexity: Average complexity is constant time.

    Throws: Nothing.

    Notes: This function breaks the container and the container can only be used for more unlink_leftmost_without_rebalance calls. This function is normally used to achieve a step by step controlled destruction of the container.

  73.  ( replace_this,  with_this) ;

    Requires: replace_this must be a valid iterator of *this and with_this must not be inserted in any container.

    Effects: Replaces replace_this in its position in the container with with_this. The container does not need to be rebalanced.

    Complexity: Constant.

    Throws: Nothing.

    Note: This function will break container ordering invariants if with_this is not equivalent to *replace_this according to the ordering rules. This function is faster than erasing and inserting the node, since no rebalancing or comparison is needed.

  74.  ( value) ;

    Effects: removes "value" from the container.

    Throws: Nothing.

    Complexity: Logarithmic time.

    Note: This static function is only usable with non-constant time size containers that have stateless comparison functors.

    If the user calls this function with a constant time size container or stateful comparison functor a compilation error will be issued.

  75. template<typename T,  Options2> 
       (rbtree< );
  76. template<typename T,  Options2> 
       (rbtree< );

rbtree public static functions

  1. rbtree & ( end_iterator) ;
  2. rbtree & 
    ( end_iterator) ;
  3. rbtree & ( it) ;
  4. rbtree & ( it) ;
  5.  ( value) ;
  6.  ( value) ;
  7.  ( value) ;

PrevUpHomeNext