-
iterator begin() ;
Effects: Returns an iterator pointing to the beginning of the multiset.
Complexity: Constant.
Throws: Nothing.
-
const_iterator begin() const;
Effects: Returns a const_iterator pointing to the beginning of the multiset.
Complexity: Constant.
Throws: Nothing.
-
const_iterator cbegin() const;
Effects: Returns a const_iterator pointing to the beginning of the multiset.
Complexity: Constant.
Throws: Nothing.
-
iterator end() ;
Effects: Returns an iterator pointing to the end of the multiset.
Complexity: Constant.
Throws: Nothing.
-
const_iterator end() const;
Effects: Returns a const_iterator pointing to the end of the multiset.
Complexity: Constant.
Throws: Nothing.
-
const_iterator cend() const;
Effects: Returns a const_iterator pointing to the end of the multiset.
Complexity: Constant.
Throws: Nothing.
-
reverse_iterator rbegin() ;
Effects: Returns a reverse_iterator pointing to the beginning of the reversed multiset.
Complexity: Constant.
Throws: Nothing.
-
const_reverse_iterator rbegin() const;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed multiset.
Complexity: Constant.
Throws: Nothing.
-
const_reverse_iterator crbegin() const;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed multiset.
Complexity: Constant.
Throws: Nothing.
-
reverse_iterator rend() ;
Effects: Returns a reverse_iterator pointing to the end of the reversed multiset.
Complexity: Constant.
Throws: Nothing.
-
const_reverse_iterator rend() const;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed multiset.
Complexity: Constant.
Throws: Nothing.
-
const_reverse_iterator crend() const;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed multiset.
Complexity: Constant.
Throws: Nothing.
-
key_compare key_comp() const;
Effects: Returns the key_compare object used by the multiset.
Complexity: Constant.
Throws: If key_compare copy-constructor throws.
-
value_compare value_comp() const;
Effects: Returns the value_compare object used by the multiset.
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 multiset.
Complexity: Linear to elements contained in *this if, constant-time size option is enabled. Constant-time otherwise.
Throws: Nothing.
-
void swap(multiset & other) ;
Effects: Swaps the contents of two 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 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.
-
iterator insert(reference value) ;
Requires: value must be an lvalue
Effects: Inserts value into the 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 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 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(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(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.
-
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(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(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.
-
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 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.