Class template avltree

| Home | Libraries | People | FAQ | More

## Class template avltree

boost::intrusive::avltree

## Synopsis

    template<typename T, class... Options>
    class avltree {
    public:
      // types
      typedef Config::value_traits                                  value_traits;
      typedef real_value_traits::pointer                            pointer;
      typedef real_value_traits::const_pointer                      const_pointer;
      typedef std::iterator_traits< pointer >::value_type           value_type;
      typedef value_type                                            key_type;
      typedef std::iterator_traits< pointer >::reference            reference;
      typedef std::iterator_traits< const_pointer >::reference      const_reference;
      typedef std::iterator_traits< pointer >::difference_type      difference_type;
      typedef Config::size_type                                     size_type;
      typedef Config::compare                                       value_compare;
      typedef value_compare                                         key_compare;
      typedef tree_iterator< avltree, false >                       iterator;
      typedef tree_iterator< avltree, true >                        const_iterator;
      typedef std::reverse_iterator< iterator >                     reverse_iterator;
      typedef std::reverse_iterator< const_iterator >               const_reverse_iterator;
      typedef real_value_traits::node_traits                        node_traits;
      typedef node_traits::node                                     node;
      typedef boost::pointer_to_other< pointer, node >::type        node_ptr;
      typedef boost::pointer_to_other< node_ptr, const node >::type const_node_ptr;
      typedef avltree_algorithms< node_traits >                     node_algorithms;
      typedef node_algorithms::insert_commit_data                   insert_commit_data;

      // construct/copy/destruct
      avltree(value_compare = value_compare(),
              const value_traits & = value_traits());
      template<typename Iterator>
        avltree(bool, Iterator, Iterator, value_compare = value_compare(),
                const value_traits & = value_traits());
      ~avltree();

      // public member functions
      const real_value_traits & get_real_value_traits() const;
      real_value_traits & get_real_value_traits() ;
      iterator begin() ;
      const_iterator begin() const;
      const_iterator cbegin() const;
      iterator end() ;
      const_iterator end() const;
      const_iterator cend() const;
      reverse_iterator rbegin() ;
      const_reverse_iterator rbegin() const;
      const_reverse_iterator crbegin() const;
      reverse_iterator rend() ;
      const_reverse_iterator rend() const;
      const_reverse_iterator crend() const;
      value_compare value_comp() const;
      bool empty() const;
      size_type size() const;
      void swap(avltree &) ;
      iterator insert_equal(reference) ;
      iterator insert_equal(const_iterator, reference) ;
      template<typename Iterator> void insert_equal(Iterator, Iterator) ;
      std::pair< iterator, bool > insert_unique(reference) ;
      iterator insert_unique(const_iterator, reference) ;
      template<typename Iterator> void insert_unique(Iterator, Iterator) ;
      std::pair< iterator, bool >
      insert_unique_check(const_reference, insert_commit_data &) ;
      template<typename KeyType, typename KeyValueCompare>
        std::pair< iterator, bool >
        insert_unique_check(const KeyType &, KeyValueCompare,
                            insert_commit_data &) ;
      std::pair< iterator, bool >
      insert_unique_check(const_iterator, const_reference, insert_commit_data &) ;
      template<typename KeyType, typename KeyValueCompare>
        std::pair< iterator, bool >
        insert_unique_check(const_iterator, const KeyType &, KeyValueCompare,
                            insert_commit_data &) ;
      iterator insert_unique_commit(reference, const insert_commit_data &) ;
      iterator erase(iterator) ;
      iterator erase(iterator, iterator) ;
      size_type erase(const_reference) ;
      template<typename KeyType, typename KeyValueCompare>
        size_type erase(const KeyType &, KeyValueCompare) ;
      template<typename Disposer> iterator erase_and_dispose(iterator, Disposer) ;
      template<typename Disposer>
        iterator erase_and_dispose(iterator, iterator, Disposer) ;
      template<typename Disposer>
        size_type erase_and_dispose(const_reference, Disposer) ;
      template<typename KeyType, typename KeyValueCompare, typename Disposer>
        size_type erase_and_dispose(const KeyType &, KeyValueCompare, Disposer) ;
      void clear() ;
      template<typename Disposer> void clear_and_dispose(Disposer) ;
      size_type count(const_reference) const;
      template<typename KeyType, typename KeyValueCompare>
        size_type count(const KeyType &, KeyValueCompare) const;
      iterator lower_bound(const_reference) ;
      const_iterator lower_bound(const_reference) const;
      template<typename KeyType, typename KeyValueCompare>
        iterator lower_bound(const KeyType &, KeyValueCompare) ;
      template<typename KeyType, typename KeyValueCompare>
        const_iterator lower_bound(const KeyType &, KeyValueCompare) const;
      iterator upper_bound(const_reference) ;
      template<typename KeyType, typename KeyValueCompare>
        iterator upper_bound(const KeyType &, KeyValueCompare) ;
      const_iterator upper_bound(const_reference) const;
      template<typename KeyType, typename KeyValueCompare>
        const_iterator upper_bound(const KeyType &, KeyValueCompare) const;
      iterator find(const_reference) ;
      template<typename KeyType, typename KeyValueCompare>
        iterator find(const KeyType &, KeyValueCompare) ;
      const_iterator find(const_reference) const;
      template<typename KeyType, typename KeyValueCompare>
        const_iterator find(const KeyType &, KeyValueCompare) const;
      std::pair< iterator, iterator > equal_range(const_reference) ;
      template<typename KeyType, typename KeyValueCompare>
        std::pair< iterator, iterator >
        equal_range(const KeyType &, KeyValueCompare) ;
      std::pair< const_iterator, const_iterator >
      equal_range(const_reference) const;
      template<typename KeyType, typename KeyValueCompare>
        std::pair< const_iterator, const_iterator >
        equal_range(const KeyType &, KeyValueCompare) const;
      template<typename Cloner, typename Disposer>
        void clone_from(const avltree &, Cloner, Disposer) ;
      pointer unlink_leftmost_without_rebalance() ;
      void replace_node(iterator, reference) ;
      iterator iterator_to(reference) ;
      const_iterator iterator_to(const_reference) const;

      // public static functions
      static avltree & container_from_end_iterator(iterator) ;
      static const avltree & container_from_end_iterator(const_iterator) ;
      static avltree & container_from_iterator(iterator) ;
      static const avltree & container_from_iterator(const_iterator) ;
      static iterator s_iterator_to(reference) ;
      static const_iterator s_iterator_to(const_reference) ;
      static void init_node(reference) ;

      // private static functions
      static avltree & priv_container_from_end_iterator(const const_iterator &) ;
      static avltree & priv_container_from_iterator(const const_iterator &) ;
      static const bool constant_time_size;
      static const bool stateful_value_traits;
    };

## Description

The class template avltree is an intrusive AVL tree container, that is used to construct intrusive avl_set and avl_multiset containers. The no-throw guarantee holds only, if the value_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<>`.

### `avltree` public construct/copy/destruct

1.     avltree(value_compare cmp = value_compare(),
               const value_traits & v_traits = value_traits());

   Effects: Constructs an empty tree.

   Complexity: Constant.

   Throws: Nothing unless the copy constructor of the value_compare object throws.

2.     template<typename Iterator>
         avltree(bool unique, Iterator b, Iterator e,
                 value_compare cmp = value_compare(),
                 const value_traits & v_traits = value_traits());

   Requires: Dereferencing iterator must yield an lvalue of type value_type. cmp must be a comparison function that induces a strict weak ordering.

   Effects: Constructs an empty tree and inserts elements from [b, e).

   Complexity: Linear in N if [b, e) is already sorted using comp and otherwise N * log N, where N is the distance between first and last.

   Throws: Nothing unless the copy constructor of the value_compare object throws.

3.     ~avltree();

   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.

### `avltree` public member functions

1.     const real_value_traits & get_real_value_traits() const;

2.     real_value_traits & get_real_value_traits() ;

3.     iterator begin() ;

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

   Complexity: Constant.

   Throws: Nothing.

4.     const_iterator begin() const;

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

   Complexity: Constant.

   Throws: Nothing.

5.     const_iterator cbegin() const;

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

   Complexity: Constant.

   Throws: Nothing.

6.     iterator end() ;

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

   Complexity: Constant.

   Throws: Nothing.

7.     const_iterator end() const;

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

   Complexity: Constant.

   Throws: Nothing.

8.     const_iterator cend() const;

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

   Complexity: Constant.

   Throws: Nothing.

9.     reverse_iterator rbegin() ;

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

   Complexity: Constant.

   Throws: Nothing.

10.     const_reverse_iterator rbegin() const;

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

    Complexity: Constant.

    Throws: Nothing.

11.     const_reverse_iterator crbegin() const;

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

    Complexity: Constant.

    Throws: Nothing.

12.     reverse_iterator rend() ;

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

    Complexity: Constant.

    Throws: Nothing.

13.     const_reverse_iterator rend() const;

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

    Complexity: Constant.

    Throws: Nothing.

14.     const_reverse_iterator crend() const;

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

    Complexity: Constant.

    Throws: Nothing.

15.     value_compare value_comp() const;

    Effects: Returns the value_compare object used by the tree.

    Complexity: Constant.

    Throws: If value_compare copy-constructor throws.

16.     bool empty() const;

    Effects: Returns true is the container is empty.

    Complexity: Constant.

    Throws: Nothing.

17.     size_type size() const;

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

    Complexity: Linear to elements contained in *this.

    Throws: Nothing.

18.     void swap(avltree & other) ;

    Effects: Swaps the contents of two multisets.

    Complexity: Constant.

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

19.     iterator insert_equal(reference value) ;

    Requires: value must be an lvalue

    Effects: Inserts value into the tree before the upper bound.

    Complexity: Average complexity for insert element is at most logarithmic.

    Throws: Nothing.

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

20.     iterator insert_equal(const_iterator hint, reference value) ;

    Requires: value must be an lvalue, and "hint" must be a valid iterator.

    Effects: Inserts x into the tree, using "hint" as a hint to where it will be inserted. If "hint" is the upper_bound the insertion takes constant time (two comparisons in the worst case)

    Complexity: Logarithmic in general, but it is amortized constant time if t is inserted immediately before hint.

    Throws: Nothing.

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

21.     template<typename Iterator> void insert_equal(Iterator b, Iterator e) ;

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

    Effects: Inserts a each element of a range into the tree 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: Nothing.

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

22.     std::pair< iterator, bool > insert_unique(reference value) ;

    Requires: value must be an lvalue

    Effects: Inserts value into the tree if the value is not already present.

    Complexity: Average complexity for insert element is at most logarithmic.

    Throws: Nothing.

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

23.     iterator insert_unique(const_iterator hint, reference value) ;

    Requires: value must be an lvalue, and "hint" must be a valid iterator

    Effects: Tries to insert x into the tree, using "hint" as a hint to where it will be inserted.

    Complexity: Logarithmic in general, but it is amortized constant time (two comparisons in the worst case) if t is inserted immediately before hint.

    Throws: Nothing.

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

24.     template<typename Iterator> void insert_unique(Iterator b, Iterator e) ;

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

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

    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: Nothing.

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

25.     std::pair< iterator, bool >
        insert_unique_check(const_reference value, insert_commit_data & commit_data) ;

26.     template<typename KeyType, typename KeyValueCompare>
          std::pair< iterator, bool >
          insert_unique_check(const KeyType & key, KeyValueCompare key_value_comp,
                              insert_commit_data & commit_data) ;

27.     std::pair< iterator, bool >
        insert_unique_check(const_iterator hint, const_reference value,
                            insert_commit_data & commit_data) ;

28.     template<typename KeyType, typename KeyValueCompare>
          std::pair< iterator, bool >
          insert_unique_check(const_iterator hint, const KeyType & key,
                              KeyValueCompare key_value_comp,
                              insert_commit_data & commit_data) ;

29.     iterator insert_unique_commit(reference value,
                                      const insert_commit_data & commit_data) ;

30.     iterator erase(iterator i) ;

    Effects: Erases the element pointed to by pos.

    Complexity: Average complexity for erase element is constant time.

    Throws: Nothing.

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

31.     iterator erase(iterator b, iterator e) ;

    Effects: Erases the range pointed to by b end e.

    Complexity: Average complexity for erase range is at most O(log(size() + N)), where N is the number of elements in the range.

    Throws: Nothing.

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

32.     size_type erase(const_reference value) ;

    Effects: Erases all the elements with the given value.

    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.

33.     template<typename KeyType, typename KeyValueCompare>
          size_type erase(const KeyType & key, KeyValueCompare comp) ;

    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.

34.     template<typename Disposer>
          iterator erase_and_dispose(iterator i, Disposer disposer) ;

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

    Effects: Erases the element pointed to by pos. Disposer::operator()(pointer) is called for the removed element.

    Complexity: Average complexity for erase element is constant time.

    Throws: Nothing.

    Note: Invalidates the iterators to the erased elements.

35.     template<typename Disposer>
          iterator erase_and_dispose(iterator b, iterator e, Disposer disposer) ;

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

    Effects: Erases the range pointed to by b end e. Disposer::operator()(pointer) is called for the removed elements.

    Complexity: Average complexity for erase range is at most O(log(size() + N)), where N is the number of elements in the range.

    Throws: Nothing.

    Note: Invalidates the iterators to the erased elements.

36.     template<typename Disposer>
          size_type erase_and_dispose(const_reference value, Disposer disposer) ;

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

    Effects: Erases all the elements with the given value. 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 (but not the references) to the erased elements. No destructors are called.

37.     template<typename KeyType, typename KeyValueCompare, typename Disposer>
          size_type erase_and_dispose(const KeyType & key, KeyValueCompare comp,
                                      Disposer disposer) ;

    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.

38.     void clear() ;

    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.

39.     template<typename Disposer> void clear_and_dispose(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.

40.     size_type count(const_reference value) const;

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

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

    Throws: Nothing.

41.     template<typename KeyType, typename KeyValueCompare>
          size_type count(const KeyType & key, KeyValueCompare comp) const;

    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: Nothing.

42.     iterator lower_bound(const_reference value) ;

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

    Complexity: Logarithmic.

    Throws: Nothing.

43.     const_iterator lower_bound(const_reference value) const;

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

    Complexity: Logarithmic.

    Throws: Nothing.

44.     template<typename KeyType, typename KeyValueCompare>
          iterator lower_bound(const KeyType & key, KeyValueCompare comp) ;

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

    Complexity: Logarithmic.

    Throws: Nothing.

45.     template<typename KeyType, typename KeyValueCompare>
          const_iterator lower_bound(const KeyType & key, KeyValueCompare comp) const;

    Effects: Returns a const iterator to the first element whose key is not less than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing.

46.     iterator upper_bound(const_reference value) ;

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

    Complexity: Logarithmic.

    Throws: Nothing.

47.     template<typename KeyType, typename KeyValueCompare>
          iterator upper_bound(const KeyType & key, KeyValueCompare comp) ;

    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: Nothing.

48.     const_iterator upper_bound(const_reference value) const;

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

    Complexity: Logarithmic.

    Throws: Nothing.

49.     template<typename KeyType, typename KeyValueCompare>
          const_iterator upper_bound(const KeyType & key, KeyValueCompare comp) const;

    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: Nothing.

50.     iterator find(const_reference value) ;

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

    Complexity: Logarithmic.

    Throws: Nothing.

51.     template<typename KeyType, typename KeyValueCompare>
          iterator find(const KeyType & key, KeyValueCompare comp) ;

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

    Complexity: Logarithmic.

    Throws: Nothing.

52.     const_iterator find(const_reference value) const;

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

    Complexity: Logarithmic.

    Throws: Nothing.

53.     template<typename KeyType, typename KeyValueCompare>
          const_iterator find(const KeyType & key, KeyValueCompare comp) const;

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

    Complexity: Logarithmic.

    Throws: Nothing.

54.     std::pair< iterator, iterator > equal_range(const_reference value) ;

    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: Nothing.

55.     template<typename KeyType, typename KeyValueCompare>
          std::pair< iterator, iterator >
          equal_range(const KeyType & key, KeyValueCompare comp) ;

    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: Nothing.

56.     std::pair< const_iterator, const_iterator >
        equal_range(const_reference value) const;

    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: Nothing.

57.     template<typename KeyType, typename KeyValueCompare>
          std::pair< const_iterator, const_iterator >
          equal_range(const KeyType & key, KeyValueCompare comp) const;

    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: Nothing.

58.     template<typename Cloner, typename Disposer>
          void clone_from(const avltree & src, Cloner cloner, Disposer disposer) ;

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

    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.

    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.

59.     pointer unlink_leftmost_without_rebalance() ;

    Effects: Unlinks the leftmost node from the tree.

    Complexity: Average complexity is constant time.

    Throws: Nothing.

    Notes: This function breaks the tree and the tree 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 tree.

60.     void replace_node(iterator replace_this, reference with_this) ;

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

    Effects: Replaces replace_this in its position in the tree with with_this. The tree 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.

61.     iterator iterator_to(reference value) ;

    Requires: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.

    Effects: Returns: a valid iterator i belonging to the set that points to the value

    Complexity: Constant.

    Throws: Nothing.

62.     const_iterator iterator_to(const_reference value) const;

    Requires: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.

    Effects: Returns: a valid const_iterator i belonging to the set that points to the value

    Complexity: Constant.

    Throws: Nothing.

### `avltree` public static functions

1.     static avltree & container_from_end_iterator(iterator end_iterator) ;

   Precondition: end_iterator must be a valid end iterator of avltree.

   Effects: Returns a const reference to the avltree associated to the end iterator

   Throws: Nothing.

   Complexity: Constant.

2.     static const avltree &
       container_from_end_iterator(const_iterator end_iterator) ;

   Precondition: end_iterator must be a valid end const_iterator of avltree.

   Effects: Returns a const reference to the avltree associated to the end iterator

   Throws: Nothing.

   Complexity: Constant.

3.     static avltree & container_from_iterator(iterator it) ;

   Precondition: it must be a valid iterator of rbtree.

   Effects: Returns a const reference to the tree associated to the iterator

   Throws: Nothing.

   Complexity: Logarithmic.

4.     static const avltree & container_from_iterator(const_iterator it) ;

   Precondition: it must be a valid end const_iterator of rbtree.

   Effects: Returns a const reference to the tree associated to the iterator

   Throws: Nothing.

   Complexity: Logarithmic.

5.     static iterator s_iterator_to(reference value) ;

   Requires: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.

   Effects: Returns: a valid iterator i belonging to the set that points to the value

   Complexity: Constant.

   Throws: Nothing.

   Note: This static function is available only if the value traits is stateless.

6.     static const_iterator s_iterator_to(const_reference value) ;

   Requires: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.

   Effects: Returns: a valid const_iterator i belonging to the set that points to the value

   Complexity: Constant.

   Throws: Nothing.

   Note: This static function is available only if the value traits is stateless.

7.     static void init_node(reference value) ;

   Requires: value shall not be in a tree.

   Effects: init_node puts the hook of a value in a well-known default state.

   Throws: Nothing.

   Complexity: Constant time.

   Note: This function puts the hook in the well-known default state used by auto_unlink and safe hooks.

### `avltree` private static functions

1.     static avltree &
       priv_container_from_end_iterator(const const_iterator & end_iterator) ;

2.     static avltree & priv_container_from_iterator(const const_iterator & it) ;