Class template sgtree

boost::intrusive::sgtree

Synopsis

template<typename T, class... Options> 
class sgtree {
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< sgtree, false >                        iterator;              
  typedef tree_iterator< sgtree, 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 sgtree_algorithms< node_traits >                      node_algorithms;       
  typedef node_algorithms::insert_commit_data                   insert_commit_data;    

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

  // 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(sgtree &) ;
  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 sgtree &, Cloner, Disposer) ;
  pointer unlink_leftmost_without_rebalance() ;
  void replace_node(iterator, reference) ;
  iterator iterator_to(reference) ;
  const_iterator iterator_to(const_reference) const;
  void rebalance() ;
  iterator rebalance_subtree(iterator) ;
  float balance_factor() const;
  void balance_factor(float) ;

  // public static functions
  static sgtree & container_from_end_iterator(iterator) ;
  static const sgtree & container_from_end_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 sgtree & priv_container_from_end_iterator(const const_iterator &) ;
  static const bool floating_point;
  static const bool constant_time_size;
  static const bool stateful_value_traits;
};

Description

The class template sgtree is an intrusive scapegoat tree container, that is used to construct intrusive sg_set and sg_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<>, floating_point<>, size_type<> and compare<>.

`sgtree` public construct/copy/destruct

```
sgtree(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.
```
template<typename Iterator> 
  sgtree(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.
```
~sgtree();
```
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.

`sgtree` public member functions

const real_value_traits & get_real_value_traits() const;

real_value_traits & get_real_value_traits() ;

```
iterator begin() ;
```
Effects: Returns an iterator pointing to the beginning of the tree.

Complexity: Constant.

Throws: Nothing.
```
const_iterator begin() const;
```
Effects: Returns a const_iterator pointing to the beginning of the tree.

Complexity: Constant.

Throws: Nothing.
```
const_iterator cbegin() const;
```
Effects: Returns a const_iterator pointing to the beginning of the tree.

Complexity: Constant.

Throws: Nothing.
```
iterator end() ;
```
Effects: Returns an iterator pointing to the end of the tree.

Complexity: Constant.

Throws: Nothing.
```
const_iterator end() const;
```
Effects: Returns a const_iterator pointing to the end of the tree.

Complexity: Constant.

Throws: Nothing.
```
const_iterator cend() const;
```
Effects: Returns a const_iterator pointing to the end of the tree.

Complexity: Constant.

Throws: Nothing.
```
reverse_iterator rbegin() ;
```
Effects: Returns a reverse_iterator pointing to the beginning of the reversed tree.

Complexity: Constant.

Throws: Nothing.
```
const_reverse_iterator rbegin() const;
```
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed tree.

Complexity: Constant.

Throws: Nothing.
```
const_reverse_iterator crbegin() const;
```
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed tree.

Complexity: Constant.

Throws: Nothing.
```
reverse_iterator rend() ;
```
Effects: Returns a reverse_iterator pointing to the end of the reversed tree.

Complexity: Constant.

Throws: Nothing.
```
const_reverse_iterator rend() const;
```
Effects: Returns a const_reverse_iterator pointing to the end of the reversed tree.

Complexity: Constant.

Throws: Nothing.
```
const_reverse_iterator crend() const;
```
Effects: Returns a const_reverse_iterator pointing to the end of the reversed tree.

Complexity: Constant.

Throws: Nothing.
```
value_compare value_comp() const;
```
Effects: Returns the value_compare object used by the tree.

Complexity: Constant.

Throws: If value_compare copy-constructor throws.
```
bool empty() const;
```
Effects: Returns true is the container is empty.

Complexity: Constant.

Throws: Nothing.
```
size_type size() const;
```
Effects: Returns the number of elements stored in the tree.

Complexity: Linear to elements contained in *this.

Throws: Nothing.
```
void swap(sgtree & other) ;
```
Effects: Swaps the contents of two multisets.

Complexity: Constant.

Throws: If the comparison functor's swap call throws.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.

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

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

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

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

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

```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
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.
```
template<typename Cloner, typename Disposer> 
  void clone_from(const sgtree & 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.
```
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.
```
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.
```
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.
```
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.
```
void rebalance() ;
```
Effects: Rebalances the tree.

Throws: Nothing.

Complexity: Linear.
```
iterator rebalance_subtree(iterator root) ;
```
Requires: old_root is a node of a tree.

Effects: Rebalances the subtree rooted at old_root.

Returns: The new root of the subtree.

Throws: Nothing.

Complexity: Linear to the elements in the subtree.
```
float balance_factor() const;
```
Returns: The balance factor (alpha) used in this tree

Throws: Nothing.

Complexity: Constant.
```
void balance_factor(float new_alpha) ;
```
Requires: new_alpha must be a value between 0.5 and 1.0

Effects: Establishes a new balance factor (alpha) and rebalances the tree if the new balance factor is stricter (less) than the old factor.

Throws: Nothing.

Complexity: Linear to the elements in the subtree.

`sgtree` public static functions

```
static sgtree & container_from_end_iterator(iterator end_iterator) ;
```
Precondition: end_iterator must be a valid end iterator of sgtree.

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

Throws: Nothing.

Complexity: Constant.
```
static const sgtree & 
container_from_end_iterator(const_iterator end_iterator) ;
```
Precondition: end_iterator must be a valid end const_iterator of sgtree.

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

Throws: Nothing.

Complexity: Constant.
```
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.
```
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.
```
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.

`sgtree` private static functions

static sgtree & 
priv_container_from_end_iterator(const const_iterator & end_iterator) ;

Boost C++ Libraries