treap_set();

Effects: Constructs an empty container.

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

explicit treap_set(const key_compare & cmp, 
                   const priority_compare & pcmp = priority_compare(), 
                   const value_traits & v_traits = value_traits());

Effects: Constructs an empty container.

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

template<typename Iterator> 
  treap_set(Iterator b, Iterator e, const key_compare & cmp = key_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 container 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 key_compare/priority_compare objects throw. Basic guarantee.

treap_set(treap_set && x);

Effects: to-do

treap_set & operator=(treap_set && x);

Effects: to-do

~treap_set();

Effects: Detaches all elements from this. The objects in the set are not deleted (i.e. no destructors are called), but the nodes according to the value_traits template parameter are reinitialized and thus can be reused.

Complexity: Linear to elements contained in *this.

Throws: Nothing.

iterator begin();

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

Complexity: Constant.

Throws: Nothing.

const_iterator begin() const;

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

Complexity: Constant.

Throws: Nothing.

const_iterator cbegin() const;

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

Complexity: Constant.

Throws: Nothing.

iterator end();

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

Complexity: Constant.

Throws: Nothing.

const_iterator end() const;

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

Complexity: Constant.

Throws: Nothing.

const_iterator cend() const;

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

Complexity: Constant.

Throws: Nothing.

reverse_iterator rbegin();

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator rbegin() const;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator crbegin() const;

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

Complexity: Constant.

Throws: Nothing.

reverse_iterator rend();

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator rend() const;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator crend() const;

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

Complexity: Constant.

Throws: Nothing.

iterator root();

Effects: Returns a iterator pointing to the root node of the container or end() if not present.

Complexity: Constant.

Throws: Nothing.

const_iterator root() const;

Effects: Returns a const_iterator pointing to the root node of the container or cend() if not present.

Complexity: Constant.

Throws: Nothing.

const_iterator croot() const;

Effects: Returns a const_iterator pointing to the root node of the container or cend() if not present.

Complexity: Constant.

Throws: Nothing.

key_compare key_comp() const;

Effects: Returns the key_compare object used by the container.

Complexity: Constant.

Throws: If key_compare copy-constructor throws.

value_compare value_comp() const;

Effects: Returns the value_compare object used by the container.

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

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

Throws: Nothing.

void swap(treap_set & other);

Effects: Swaps the contents of two treaps.

Complexity: Constant.

Throws: If the comparison functor's swap call throws.

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

template<typename Cloner, typename Disposer> 
  void clone_from(treap_set && 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()(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 top();

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

Complexity: Constant.

Throws: Nothing.

const_iterator top() const;

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

Complexity: Constant.

Throws: Nothing.

const_iterator ctop() const;

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

Complexity: Constant.

Throws: Nothing.

reverse_iterator rtop();

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator rtop() const;

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

Complexity: Constant.

Throws: Nothing.

const_reverse_iterator crtop() const;

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

Complexity: Constant.

Throws: Nothing.

priority_compare priority_comp() const;

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

Complexity: Constant.

Throws: Nothing.

std::pair< iterator, bool > insert(reference value);

Requires: value must be an lvalue

Effects: Inserts value into the container if the value is not already present.

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

Throws: If the internal key_compare or priority_compare functions throw. 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, and "hint" must be a valid iterator

Effects: Tries to insert x into the container, using "hint" as a hint to where it will be inserted.

Complexity: Logarithmic in general, but it is amortized constant time (two comparisons in the worst case) if t is inserted immediately before hint.

Throws: If the internal key_compare or priority_compare functions throw. Strong guarantee.

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

std::pair< iterator, bool > 
insert_check(const key_type & key, const priority_type & prio, 
             insert_commit_data & commit_data);

Effects: Checks if a value can be inserted in the container, using a user provided key instead of the value itself.

Returns: If there is an equivalent value returns a pair containing an iterator to the already present value and false. If the value can be inserted returns true in the returned pair boolean and fills "commit_data" that is meant to be used with the "insert_commit" function.

Complexity: Average complexity is at most logarithmic.

Throws: If the comparison or predicate functions throw. Strong guarantee.

Notes: This function is used to improve performance when constructing a value_type is expensive: if there is an equivalent value the constructed object must be discarded. Many times, the part of the node that is used to impose the order is much cheaper to construct than the value_type and this function offers the possibility to use that part to check if the insertion will be successful.

If the check is successful, the user can construct the value_type and use "insert_commit" to insert the object in constant-time. This gives a total logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).

"commit_data" remains valid for a subsequent "insert_commit" only if no more objects are inserted or erased from the container.

std::pair< iterator, bool > 
insert_check(const_iterator hint, const key_type & key, 
             const priority_type & prio, insert_commit_data & commit_data);

Effects: Checks if a value can be inserted in the container, using a user provided key instead of the value itself, using "hint" as a hint to where it will be inserted.

Returns: If there is an equivalent value returns a pair containing an iterator to the already present value and false. If the value can be inserted returns true in the returned pair boolean and fills "commit_data" that is meant to be used with the "insert_commit" function.

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

Throws: If the comparison or predicate functions throw. Strong guarantee.

Notes: This function is used to improve performance when constructing a value_type is expensive: if there is an equivalent value the constructed object must be discarded. Many times, the part of the constructing that is used to impose the order is much cheaper to construct than the value_type and this function offers the possibility to use that key to check if the insertion will be successful.

If the check is successful, the user can construct the value_type and use "insert_commit" to insert the object in constant-time. This can give a total constant-time complexity to the insertion: check(O(1)) + commit(O(1)).

"commit_data" remains valid for a subsequent "insert_commit" only if no more objects are inserted or erased from the container.

template<typename KeyType, typename KeyTypeKeyCompare, typename PrioType, 
         typename PrioValuePrioCompare> 
  std::pair< iterator, bool > 
  insert_check(const KeyType & key, KeyTypeKeyCompare comp, 
               const PrioType & prio, PrioValuePrioCompare pcomp, 
               insert_commit_data & commit_data);

template<typename KeyType, typename KeyTypeKeyCompare, typename PrioType, 
         typename PrioValuePrioCompare> 
  std::pair< iterator, bool > 
  insert_check(const_iterator hint, const KeyType & key, 
               KeyTypeKeyCompare comp, const PrioType & prio, 
               PrioValuePrioCompare pcomp, insert_commit_data & commit_data);

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

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

Effects: Tries to insert each element of a range into the container.

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 key_comp().

Throws: If the internal key_compare or priority_compare functions throw. Strong guarantee.

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

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

Requires: value must be an lvalue of type value_type. commit_data must have been obtained from a previous call to "insert_check". No objects should have been inserted or erased from the container between the "insert_check" that filled "commit_data" and the call to "insert_commit".

Effects: Inserts the value in the avl_set using the information obtained from the "commit_data" that a previous "insert_check" filled.

Returns: An iterator to the newly inserted object.

Complexity: Constant time.

Throws: Nothing

Notes: This function has only sense if a "insert_check" has been previously executed to fill "commit_data". No value should be inserted or erased between the "insert_check" and "insert_commit" calls.

iterator insert_before(const_iterator pos, reference value);

Requires: value must be an lvalue, "pos" must be a valid iterator (or end) and must be the succesor of value once inserted according to the predicate

Effects: Inserts x into the container before "pos".

Complexity: Constant time.

Throws: If the internal priority_compare function throws. Strong guarantee.

Note: This function does not check preconditions so if "pos" is not the successor of "value" container ordering invariant will be broken. This is a low-level function to be used only for performance reasons by advanced users.

void push_back(reference value);

Requires: value must be an lvalue, and it must be no less than the greatest inserted key

Effects: Inserts x into the container in the last position.

Complexity: Constant time.

Throws: If the internal priority_compare function throws. Strong guarantee.

Note: This function does not check preconditions so if value is less than the greatest inserted key container ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users.

void push_front(reference value);

Requires: value must be an lvalue, and it must be no greater than the minimum inserted key

Effects: Inserts x into the container in the first position.

Complexity: Constant time.

Throws: If the internal priority_compare function throws. Strong guarantee.

Note: This function does not check preconditions so if value is greater than the minimum inserted key container ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users.

iterator erase(const_iterator i);

Effects: Erases the element pointed to by i.

Complexity: Average complexity for erase element is constant time.

Throws: if the internal priority_compare function throws. Strong guarantee.

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.

Complexity: Average complexity for erase range is at most O(log(size() + N)), where N is the number of elements in the range.

Throws: if the internal priority_compare function throws. Strong guarantee.

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

size_type erase(const key_type & key);

Effects: Erases all the elements with the given value.

Returns: The number of erased elements.

Complexity: O(log(size() + N).

Throws: if the internal priority_compare function throws. Strong guarantee.

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

template<typename KeyType, typename KeyTypeKeyCompare> 
  size_type erase(const KeyType & key, KeyTypeKeyCompare comp);

Effects: Erases all the elements with the given key. according to the comparison functor "comp".

Returns: The number of erased elements.

Complexity: O(log(size() + N).

Throws: if the internal priority_compare function throws. Equivalent guarantee to while(beg != end) erase(beg++);

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.

Effects: Erases the element pointed to by i. Disposer::operator()(pointer) is called for the removed element.

Complexity: Average complexity for erase element is constant time.

Throws: if the internal priority_compare function throws. Strong guarantee.

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.

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: if the internal priority_compare function throws. Strong guarantee.

Note: Invalidates the iterators to the erased elements.

template<typename Disposer> 
  size_type erase_and_dispose(const key_type & key, Disposer disposer);

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

Effects: Erases all the elements with the given value. Disposer::operator()(pointer) is called for the removed elements.

Returns: The number of erased elements.

Complexity: O(log(size() + N).

Throws: if the priority_compare function throws then weak guarantee and heap invariants are broken. The safest thing would be to clear or destroy the container.

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

template<typename KeyType, typename KeyTypeKeyCompare, typename Disposer> 
  size_type erase_and_dispose(const KeyType & key, KeyTypeKeyCompare comp, 
                              Disposer disposer);

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

Effects: Erases all the elements with the given key. according to the comparison functor "comp". Disposer::operator()(pointer) is called for the removed elements.

Returns: The number of erased elements.

Complexity: O(log(size() + N).

Throws: if the priority_compare function throws then weak guarantee and heap invariants are broken. The safest thing would be to clear or destroy the container.

Note: Invalidates the iterators to the erased elements.

void clear();

Effects: Erases all of the elements.

Complexity: Linear to the number of elements on the container. if it's a safe-mode or auto-unlink value_type. Constant time otherwise.

Throws: Nothing.

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

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

Effects: Erases all of the elements calling disposer(p) for each node to be erased. Complexity: Average complexity for is at most O(log(size() + N)), where N is the number of elements in the container.

Throws: Nothing.

Note: Invalidates the iterators (but not the references) to the erased elements. Calls N times to disposer functor.

size_type count(const key_type & key) const;

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

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

Throws: If key_compare throws.

template<typename KeyType, typename KeyTypeKeyCompare> 
  size_type count(const KeyType & key, KeyTypeKeyCompare comp) const;

Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this.

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

iterator lower_bound(const key_type & key);

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

template<typename KeyType, typename KeyTypeKeyCompare> 
  iterator lower_bound(const KeyType & key, KeyTypeKeyCompare comp);

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

Complexity: Logarithmic.

Throws: If key_compare throws.

const_iterator lower_bound(const key_type & key) const;

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

Complexity: Logarithmic.

Throws: If key_compare throws.

template<typename KeyType, typename KeyTypeKeyCompare> 
  const_iterator 
  lower_bound(const KeyType & key, KeyTypeKeyCompare comp) const;

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

Complexity: Logarithmic.

Throws: If key_compare throws.

iterator upper_bound(const key_type & key);

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

template<typename KeyType, typename KeyTypeKeyCompare> 
  iterator upper_bound(const KeyType & key, KeyTypeKeyCompare comp);

Requires: key is a value such that *this is partitioned with respect to !comp(key, nk), with nk the key_type of a value_type inserted into *this.

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

Complexity: Logarithmic.

Throws: If comp throws.

const_iterator upper_bound(const key_type & key) 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 key_compare throws.

template<typename KeyType, typename KeyTypeKeyCompare> 
  const_iterator 
  upper_bound(const KeyType & key, KeyTypeKeyCompare comp) const;

Requires: key is a value such that *this is partitioned with respect to !comp(key, nk), with nk the key_type of a value_type inserted into *this.

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

Complexity: Logarithmic.

Throws: If comp throws.

iterator find(const key_type & key);

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

Complexity: Logarithmic.

Throws: If key_compare throws.

template<typename KeyType, typename KeyTypeKeyCompare> 
  iterator find(const KeyType & key, KeyTypeKeyCompare comp);

Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this.

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

Complexity: Logarithmic.

Throws: If comp throws.

const_iterator find(const key_type & key) const;

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

Complexity: Logarithmic.

Throws: If key_compare throws.

template<typename KeyType, typename KeyTypeKeyCompare> 
  const_iterator find(const KeyType & key, KeyTypeKeyCompare comp) const;

Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this.

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

Complexity: Logarithmic.

Throws: If comp throws.

std::pair< iterator, iterator > equal_range(const key_type & key);

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

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

Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), with nk the key_type of a value_type inserted into *this.

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

std::pair< const_iterator, const_iterator > 
equal_range(const key_type & key) 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 key_compare throws.

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

Requires: key is a value such that *this is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), with nk the key_type of a value_type inserted into *this.

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

std::pair< iterator, iterator > 
bounded_range(const key_type & lower_key, const key_type & upper_key, 
              bool left_closed, bool right_closed);

Requires: upper_key shall not precede lower_key according to key_compare. [key_comp()(upper_key, lower_key) shall be false]

If lower_key is equivalent to upper_key [!key_comp()(upper_key, lower_key) && !key_comp()(lower_key, upper_key)] then ('left_closed' || 'right_closed') must be false.

Effects: Returns an a pair with the following criteria:

first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise

second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise

Complexity: Logarithmic.

Throws: If key_compare throws.

Note: This function can be more efficient than calling upper_bound and lower_bound for lower_value and upper_value.

Note: Experimental function, the interface might change in future releases.

template<typename KeyType, typename KeyTypeKeyCompare> 
  std::pair< iterator, iterator > 
  bounded_range(const KeyType & lower_key, const KeyType & upper_key, 
                KeyTypeKeyCompare comp, bool left_closed, bool right_closed);

Requires: lower_key is a value such that *this is partitioned with respect to comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise.

upper_key is a value such that *this is partitioned with respect to !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise.

upper_key shall not precede lower_key according to comp [comp(upper_key, lower_key) shall be false]

If lower_key is equivalent to upper_key [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then ('left_closed' || 'right_closed') must be false.

Effects: Returns an a pair with the following criteria:

first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise

second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise

Complexity: Logarithmic.

Throws: If comp throws.

Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.

Note: Experimental function, the interface might change in future releases.

std::pair< const_iterator, const_iterator > 
bounded_range(const key_type & lower_key, const key_type & upper_key, 
              bool left_closed, bool right_closed) const;

Requires: upper_key shall not precede lower_key according to key_compare. [key_comp()(upper_key, lower_key) shall be false]

If lower_key is equivalent to upper_key [!key_comp()(upper_key, lower_key) && !key_comp()(lower_key, upper_key)] then ('left_closed' || 'right_closed') must be false.

Effects: Returns an a pair with the following criteria:

first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise

second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise

Complexity: Logarithmic.

Throws: If key_compare throws.

Note: This function can be more efficient than calling upper_bound and lower_bound for lower_value and upper_value.

Note: Experimental function, the interface might change in future releases.

template<typename KeyType, typename KeyTypeKeyCompare> 
  std::pair< const_iterator, const_iterator > 
  bounded_range(const KeyType & lower_key, const KeyType & upper_key, 
                KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;

Requires: lower_key is a value such that *this is partitioned with respect to comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise.

upper_key is a value such that *this is partitioned with respect to !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise.

upper_key shall not precede lower_key according to comp [comp(upper_key, lower_key) shall be false]

If lower_key is equivalent to upper_key [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then ('left_closed' || 'right_closed') must be false.

Effects: Returns an a pair with the following criteria:

first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise

second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise

Complexity: Logarithmic.

Throws: If comp throws.

Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.

Note: Experimental function, the interface might change in future releases.

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

Complexity: Average complexity is constant time.

Throws: Nothing.

Notes: This function breaks the container and the container 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 container.

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

Effects: Replaces replace_this in its position in the container with with_this. The container 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 remove_node(reference value);

Effects: removes "value" from the container.

Throws: Nothing.

Complexity: Logarithmic time.

Note: This static function is only usable with non-constant time size containers that have stateless comparison functors.

If the user calls this function with a constant time size container or stateful comparison functor a compilation error will be issued.

template<class ... Options2> void merge(treap_set< T, Options2... > & source);

Requires: "source" container's Options can only can differ in the comparison function from *this.

Effects: Attempts to extract each element in source and insert it into a using the comparison object of *this. If there is an element in a with key equivalent to the key of an element from source, then that element is not extracted from source.

Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.

Throws: Nothing unless the comparison object throws.

Complexity: N log(a.size() + N) (N has the value source.size())

template<class ... Options2> 
  void merge(treap_multiset< T, Options2... > & source);

Requires: "source" container's Options can only can differ in the comparison function from *this.

Effects: Attempts to extract each element in source and insert it into a using the comparison object of *this. If there is an element in a with key equivalent to the key of an element from source, then that element is not extracted from source.

Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.

Throws: Nothing unless the comparison object throws.

Complexity: N log(a.size() + N) (N has the value source.size())

static treap_set & container_from_end_iterator(iterator end_iterator);

Precondition: end_iterator must be a valid end iterator of the container.

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

Throws: Nothing.

Complexity: Constant.

static const treap_set & 
container_from_end_iterator(const_iterator end_iterator);

Precondition: end_iterator must be a valid end iterator of the container.

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

Throws: Nothing.

Complexity: Constant.

static treap_set & container_from_iterator(iterator it);

Precondition: it must be a valid iterator of the container.

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

Throws: Nothing.

Complexity: Logarithmic.

static const treap_set & container_from_iterator(const_iterator it);

Precondition: it must be a valid iterator of the container.

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

Throws: Nothing.

Complexity: Logarithmic.

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

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.