Boost C++ Libraries

treap_multiset(const value_compare & cmp = value_compare(), 
               const priority_compare & pcmp = priority_compare(), 
               const value_traits & v_traits = value_traits());

Effects: Constructs an empty treap_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 of the value_compare/priority_compare objects throw.

template<typename Iterator> 
  treap_multiset(Iterator b, Iterator e, 
                 const value_compare & cmp = value_compare(), 
                 const priority_compare & pcmp = priority_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 treap_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/priority_compare objects throw.

~treap_multiset();

Effects: Detaches all elements from this. The objects in the treap_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.

iterator begin() ;

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

Complexity: Constant.

Throws: Nothing.

const_iterator begin() const;

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

Complexity: Constant.

Throws: Nothing.

const_iterator cbegin() const;

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

Complexity: Constant.

Throws: Nothing.

iterator end() ;

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

Complexity: Constant.

Throws: Nothing.

const_iterator end() const;

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

Complexity: Constant.

Throws: Nothing.

const_iterator cend() const;

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

Complexity: Constant.

Throws: Nothing.

iterator top() ;

Effects: Returns an iterator pointing to the highest priority object of the tree.

Complexity: Constant.

Throws: Nothing.

const_iterator top() const;

Effects: Returns a const_iterator pointing to the highest priority object of the tree..

Complexity: Constant.

Throws: Nothing.

const_iterator ctop() const;

Effects: Returns a const_iterator pointing to the highest priority object of the tree..

Complexity: Constant.

Throws: Nothing.

reverse_iterator rbegin() ;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator rbegin() const;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator crbegin() const;

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

Complexity: Constant.

Throws: Nothing.

reverse_iterator rend() ;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator rend() const;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator crend() const;

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

Complexity: Constant.

Throws: Nothing.

reverse_iterator rtop() ;

Effects: Returns a reverse_iterator pointing to the highest priority object of the reversed tree.

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator rtop() const;

Effects: Returns a const_reverse_iterator pointing to the highest priority objec of the reversed tree.

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator crtop() const;

Effects: Returns a const_reverse_iterator pointing to the highest priority object of the reversed tree.

Complexity: Constant.

Throws: Nothing.

key_compare key_comp() const;

Effects: Returns the key_compare object used by the treap_multiset.

Complexity: Constant.

Throws: If key_compare copy-constructor throws.

value_compare value_comp() const;

Effects: Returns the value_compare object used by the treap_multiset.

Complexity: Constant.

Throws: If value_compare copy-constructor throws.

bool empty() const;

Effects: Returns true if the container is empty.

Complexity: Constant.

Throws: Nothing.

size_type size() const;

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

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

Throws: Nothing.

void swap(treap_multiset & other) ;

Effects: Swaps the contents of two treap_multisets.

Complexity: Constant.

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

template<typename Cloner, typename Disposer> 
  void clone_from(const treap_multiset & src, Cloner cloner, 
                  Disposer 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.

iterator insert(reference value) ;

Requires: value must be an lvalue

Effects: Inserts value into the treap_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.

iterator insert(const_iterator hint, reference value) ;

Requires: value must be an lvalue

Effects: Inserts x into the treap_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.

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

iterator erase(const_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.

iterator erase(const_iterator b, const_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.

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.

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.

template<typename Disposer> 
  iterator erase_and_dispose(const_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.

template<typename Disposer> 
  iterator erase_and_dispose(const_iterator b, const_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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

iterator iterator_to(reference value) ;

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

Effects: Returns: a valid iterator i belonging to the treap_multiset 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 treap_multiset of appropriate type. Otherwise the behavior is undefined.

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

Complexity: Constant.

Throws: Nothing.

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.

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.

static treap_multiset & container_from_end_iterator(iterator end_iterator) ;

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

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

Throws: Nothing.

Complexity: Constant.

static const treap_multiset & 
container_from_end_iterator(const_iterator end_iterator) ;

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

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

Throws: Nothing.

Complexity: Constant.

static treap_multiset & container_from_iterator(iterator it) ;

Precondition: it must be a valid iterator of multiset.

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

Throws: Nothing.

Complexity: Constant.

static const treap_multiset & container_from_iterator(const_iterator it) ;

Precondition: it must be a valid const_iterator of multiset.

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

Throws: Nothing.

Complexity: Constant.

static iterator s_iterator_to(reference value) ;

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

Effects: Returns: a valid iterator i belonging to the treap_multiset 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 treap_multiset of appropriate type. Otherwise the behavior is undefined.

Effects: Returns: a valid const_iterator i belonging to the treap_multiset 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 treap_multiset/treap_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.