splay_multiset(const value_compare & cmp = value_compare(), 
               const value_traits & v_traits = value_traits());

Effects: Constructs an empty splay_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.

template<typename Iterator> 
  splay_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 splay_multiset and inserts elements from [b, e).

Complexity: Linear in N if [b, e) is already sorted using comp and otherwise amortized 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.

splay_multiset(BOOST_RV_REF(splay_multiset) x);

Effects: to-do

splay_multiset& operator=(BOOST_RV_REF(splay_multiset) x);

Effects: to-do

~splay_multiset();

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

Complexity: Constant.

Throws: Nothing.

const_iterator begin() const;

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

Complexity: Constant.

Throws: Nothing.

const_iterator cbegin() const;

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

Complexity: Constant.

Throws: Nothing.

iterator end();

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

Complexity: Constant.

Throws: Nothing.

const_iterator end() const;

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

Complexity: Constant.

Throws: Nothing.

const_iterator cend() const;

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

Complexity: Constant.

Throws: Nothing.

reverse_iterator rbegin();

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator rbegin() const;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator crbegin() const;

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

Complexity: Constant.

Throws: Nothing.

reverse_iterator rend();

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator rend() const;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator crend() const;

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

Complexity: Constant.

Throws: Nothing.

key_compare key_comp() const;

Effects: Returns the key_compare object used by the splay_multiset.

Complexity: Constant.

Throws: If key_compare copy-constructor throws.

value_compare value_comp() const;

Effects: Returns the value_compare object used by the splay_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 splay_multiset.

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

Throws: Nothing.

void swap(splay_multiset & other);

Effects: Swaps the contents of two splay_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 splay_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 splay_multiset.

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

Complexity: Amortized 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 splay_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: Amortized 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 splay_multiset.

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

Complexity: Insert range is amortized 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 amortized 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: Amortized 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: Amortized 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 amortized 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: Amortized 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: Amortized 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);

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

Complexity: Amortized 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);

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

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

Throws: If comp ordering function throws.

size_type count_dont_splay(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_dont_splay(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: Amortized 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: Amortized 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_dont_splay(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_dont_splay(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: Amortized 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: Amortized 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_dont_splay(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_dont_splay(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: Amortized 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: Amortized 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_dont_splay(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_dont_splay(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: Amortized 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: Amortized 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_dont_splay(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_dont_splay(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 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.

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 splay_up(iterator i);

Requires: i must be a valid iterator of *this.

Effects: Rearranges the splay set so that the element pointed by i is placed as the root of the tree, improving future searches of this value.

Complexity: Amortized logarithmic.

Throws: Nothing.

template<typename KeyType, typename KeyNodePtrCompare> 
  iterator splay_down(const KeyType & key, KeyNodePtrCompare comp);

Effects: Rearranges the splay set so that if *this stores an element with a key equivalent to value the element is placed as the root of the tree. If the element is not present returns the last node compared with the key. If the tree is empty, end() is returned.

Complexity: Amortized logarithmic.

Returns: An iterator to the new root of the tree, end() if the tree is empty.

Throws: If the comparison functor throws.

iterator splay_down(const value_type & value);

Effects: Rearranges the splay set so that if *this stores an element with a key equivalent to value the element is placed as the root of the tree.

Complexity: Amortized logarithmic.

Returns: An iterator to the new root of the tree, end() if the tree is empty.

Throws: If the predicate throws.

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.

static splay_multiset & container_from_end_iterator(iterator end_iterator);

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

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

Throws: Nothing.

Complexity: Constant.

static const splay_multiset & 
container_from_end_iterator(const_iterator end_iterator);

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

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

Throws: Nothing.

Complexity: Constant.

static splay_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: Logarithmic.

static const splay_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 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 set/splay_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.