Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Class template sg_multiset

boost::intrusive::sg_multiset

Synopsis

template<typename T, class... Options> 
class sg_multiset {
public:
  // types
  typedef implementation_defined::value_type             value_type;            
  typedef implementation_defined::value_traits           value_traits;          
  typedef implementation_defined::pointer                pointer;               
  typedef implementation_defined::const_pointer          const_pointer;         
  typedef implementation_defined::reference              reference;             
  typedef implementation_defined::const_reference        const_reference;       
  typedef implementation_defined::difference_type        difference_type;       
  typedef implementation_defined::size_type              size_type;             
  typedef implementation_defined::value_compare          value_compare;         
  typedef implementation_defined::key_compare            key_compare;           
  typedef implementation_defined::iterator               iterator;              
  typedef implementation_defined::const_iterator         const_iterator;        
  typedef implementation_defined::reverse_iterator       reverse_iterator;      
  typedef implementation_defined::const_reverse_iterator const_reverse_iterator;
  typedef implementation_defined::insert_commit_data     insert_commit_data;    
  typedef implementation_defined::node_traits            node_traits;           
  typedef implementation_defined::node                   node;                  
  typedef implementation_defined::node_ptr               node_ptr;              
  typedef implementation_defined::const_node_ptr         const_node_ptr;        
  typedef implementation_defined::node_algorithms        node_algorithms;       

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

  // public member functions
  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;
  key_compare key_comp() const;
  value_compare value_comp() const;
  bool empty() const;
  size_type size() const;
  void swap(sg_multiset &) ;
  template<typename Cloner, typename Disposer> 
    void clone_from(const sg_multiset &, Cloner, Disposer) ;
  iterator insert(reference) ;
  iterator insert(const_iterator, reference) ;
  template<typename Iterator> void insert(Iterator, Iterator) ;
  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) ;
  template<typename KeyType, typename KeyValueCompare> 
    iterator lower_bound(const KeyType &, KeyValueCompare) ;
  const_iterator lower_bound(const_reference) const;
  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;
  iterator iterator_to(reference) ;
  const_iterator iterator_to(const_reference) const;
  pointer unlink_leftmost_without_rebalance() ;
  void replace_node(iterator, reference) ;
  void rebalance() ;
  iterator rebalance_subtree(iterator) ;
  float balance_factor() const;
  void balance_factor(float) ;

  // public static functions
  static sg_multiset & container_from_end_iterator(iterator) ;
  static const sg_multiset & 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) ;
};

Description

The class template sg_multiset is an intrusive container, that mimics most of the interface of std::sg_multiset as described in the C++ standard.

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

sg_multiset public construct/copy/destruct

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

    Effects: Constructs an empty sg_multiset.

    Complexity: Constant.

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

  2. template<typename Iterator> 
      sg_multiset(Iterator b, Iterator e, 
                  const 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 sg_multiset 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: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor/operator() of the value_compare object throws.

  3. ~sg_multiset();

    Effects: Detaches all elements from this. The objects in the sg_multiset are not deleted (i.e. no destructors are called).

    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.

sg_multiset public member functions

  1. iterator begin() ;

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

    Complexity: Constant.

    Throws: Nothing.

  2. const_iterator begin() const;

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

    Complexity: Constant.

    Throws: Nothing.

  3. const_iterator cbegin() const;

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

    Complexity: Constant.

    Throws: Nothing.

  4. iterator end() ;

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

    Complexity: Constant.

    Throws: Nothing.

  5. const_iterator end() const;

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

    Complexity: Constant.

    Throws: Nothing.

  6. const_iterator cend() const;

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

    Complexity: Constant.

    Throws: Nothing.

  7. reverse_iterator rbegin() ;

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

    Complexity: Constant.

    Throws: Nothing.

  8. const_reverse_iterator rbegin() const;

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

    Complexity: Constant.

    Throws: Nothing.

  9. const_reverse_iterator crbegin() const;

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

    Complexity: Constant.

    Throws: Nothing.

  10. reverse_iterator rend() ;

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

    Complexity: Constant.

    Throws: Nothing.

  11. const_reverse_iterator rend() const;

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

    Complexity: Constant.

    Throws: Nothing.

  12. const_reverse_iterator crend() const;

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

    Complexity: Constant.

    Throws: Nothing.

  13. key_compare key_comp() const;

    Effects: Returns the key_compare object used by the sg_multiset.

    Complexity: Constant.

    Throws: If key_compare copy-constructor throws.

  14. value_compare value_comp() const;

    Effects: Returns the value_compare object used by the sg_multiset.

    Complexity: Constant.

    Throws: If value_compare copy-constructor throws.

  15. bool empty() const;

    Effects: Returns true is the container is empty.

    Complexity: Constant.

    Throws: Nothing.

  16. size_type size() const;

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

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

    Throws: Nothing.

  17. void swap(sg_multiset & other) ;

    Effects: Swaps the contents of two sg_multisets.

    Complexity: Constant.

    Throws: If the swap() call for the comparison functor found using ADL throws. Strong guarantee.

  18. template<typename Cloner, typename Disposer> 
      void clone_from(const sg_multiset & 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. Basic guarantee.

  19. iterator insert(reference value) ;

    Requires: value must be an lvalue

    Effects: Inserts value into the sg_multiset.

    Returns: An iterator that points to the position where the new element was inserted.

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

    Throws: If the internal value_compare ordering function throws. Strong guarantee.

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

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

    Requires: value must be an lvalue

    Effects: Inserts x into the sg_multiset, using pos as a hint to where it will be inserted.

    Returns: An iterator that points to the position where the new element was inserted.

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

    Throws: If the internal value_compare ordering function throws. Strong guarantee.

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

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

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

    Effects: Inserts a range into the sg_multiset.

    Returns: An iterator that points to the position where the new element was inserted.

    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 internal value_compare ordering function throws. Basic guarantee.

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

  22. iterator erase(iterator i) ;

    Effects: Erases the element pointed to by pos.

    Complexity: Average complexity is constant time.

    Returns: An iterator to the element after the erased element.

    Throws: Nothing.

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

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

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

    Returns: An iterator to the element after the erased 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 (but not the references) to the erased elements. No destructors are called.

  24. 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() + this->count(value)).

    Throws: If the internal value_compare ordering function throws. Basic guarantee.

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

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

    Effects: Erases all the elements that compare equal with the given key and the given comparison functor.

    Returns: The number of erased elements.

    Complexity: O(log(size() + this->count(key, comp)).

    Throws: If comp ordering function throws. Basic guarantee.

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

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

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

    Returns: An iterator to the element after the erased element.

    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.

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

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

    Returns: An iterator to the element after the erased elements.

    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.

  28. 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() + this->count(value)).

    Throws: If the internal value_compare ordering function throws. Basic guarantee.

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

  29. 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() + this->count(key, comp)).

    Throws: If comp ordering function throws. Basic guarantee.

    Note: Invalidates the iterators to the erased elements.

  30. void clear() ;

    Effects: Erases all the elements of the container.

    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.

  31. template<typename Disposer> void clear_and_dispose(Disposer disposer) ;

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

    Effects: Erases all the elements of the container.

    Complexity: Linear to the number of elements on the container. Disposer::operator()(pointer) is called for the removed elements.

    Throws: Nothing.

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

  32. size_type count(const_reference value) 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: If the internal value_compare ordering function throws.

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

    Effects: Returns the number of contained elements with the same key compared with the given comparison functor.

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

    Throws: If comp ordering function throws.

  34. 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: If the internal value_compare ordering function throws.

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

    Requires: comp must imply the same element order as value_compare. Usually key is the part of the value_type that is used in the ordering functor.

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

    Complexity: Logarithmic.

    Throws: If comp ordering function throws.

    Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.

  36. const_iterator lower_bound(const_reference value) 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: If the internal value_compare ordering function throws.

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

    Requires: comp must imply the same element order as value_compare. Usually key is the part of the value_type that is used in the ordering functor.

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

    Complexity: Logarithmic.

    Throws: If comp ordering function throws.

    Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.

  38. 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: If the internal value_compare ordering function throws.

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

    Requires: comp must imply the same element order as value_compare. Usually key is the part of the value_type that is used in the ordering functor.

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

    Complexity: Logarithmic.

    Throws: If comp ordering function throws.

    Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.

  40. 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: If the internal value_compare ordering function throws.

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

    Requires: comp must imply the same element order as value_compare. Usually key is the part of the value_type that is used in the ordering functor.

    Effects: Returns a const_iterator to the first element whose key according to the comparison functor is greater than key or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: If comp ordering function throws.

    Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.

  42. iterator find(const_reference value) ;

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

    Complexity: Logarithmic.

    Throws: If the internal value_compare ordering function throws.

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

    Requires: comp must imply the same element order as value_compare. Usually key is the part of the value_type that is used in the ordering functor.

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

    Complexity: Logarithmic.

    Throws: If comp ordering function throws.

    Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.

  44. const_iterator find(const_reference value) const;

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

    Complexity: Logarithmic.

    Throws: If the internal value_compare ordering function throws.

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

    Requires: comp must imply the same element order as value_compare. Usually key is the part of the value_type that is used in the ordering functor.

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

    Complexity: Logarithmic.

    Throws: If comp ordering function throws.

    Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.

  46. 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: If the internal value_compare ordering function throws.

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

    Requires: comp must imply the same element order as value_compare. Usually key is the part of the value_type that is used in the ordering functor.

    Effects: Finds a range containing all elements whose key is k according to the comparison functor 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 ordering function throws.

    Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.

  48. 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: If the internal value_compare ordering function throws.

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

    Requires: comp must imply the same element order as value_compare. Usually key is the part of the value_type that is used in the ordering functor.

    Effects: Finds a range containing all elements whose key is k according to the comparison functor 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 ordering function throws.

    Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.

  50. iterator iterator_to(reference value) ;

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

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

    Complexity: Constant.

    Throws: Nothing.

  51. const_iterator iterator_to(const_reference value) const;

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

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

    Complexity: Constant.

    Throws: Nothing.

  52. 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.

  53. 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.

  54. void rebalance() ;

    Effects: Rebalances the tree.

    Throws: Nothing.

    Complexity: Linear.

  55. 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.

  56. float balance_factor() const;

    Returns: The balance factor (alpha) used in this tree

    Throws: Nothing.

    Complexity: Constant.

  57. 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.

sg_multiset public static functions

  1. static sg_multiset & container_from_end_iterator(iterator end_iterator) ;

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

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

    Throws: Nothing.

    Complexity: Constant.

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

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

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

    Throws: Nothing.

    Complexity: Constant.

  3. static iterator s_iterator_to(reference value) ;

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

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

    Complexity: Constant.

    Throws: Nothing.

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

  4. static const_iterator s_iterator_to(const_reference value) ;

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

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

    Complexity: Constant.

    Throws: Nothing.

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

  5. static void init_node(reference value) ;

    Requires: value shall not be in a sg_multiset/sg_multiset.

    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.


PrevUpHomeNext