 |
Boost
v1.57.0
doxygen for www.boost.org
|
|
|
Boost
v1.57.0
doxygen for www.boost.org
|
|
The class template treap is an intrusive treap container that is used to construct intrusive set and multiset containers. More...
#include <treap.hpp>
Public Types | |
| typedef ValueTraits | value_traits |
| typedef implementation_defined::pointer | pointer |
| typedef implementation_defined::const_pointer | const_pointer |
| typedef implementation_defined::value_type | value_type |
| typedef implementation_defined::key_type | key_type |
| typedef implementation_defined::reference | reference |
| typedef implementation_defined::const_reference | const_reference |
| typedef implementation_defined::difference_type | difference_type |
| typedef implementation_defined::size_type | size_type |
| typedef implementation_defined::value_compare | value_compare |
| typedef implementation_defined::key_compare | key_compare |
| typedef implementation_defined::iterator | iterator |
| typedef implementation_defined::const_iterator | const_iterator |
| typedef implementation_defined::reverse_iterator | reverse_iterator |
| typedef implementation_defined::const_reverse_iterator | const_reverse_iterator |
| typedef implementation_defined::node_traits | node_traits |
| typedef implementation_defined::node | node |
| typedef implementation_defined::node_ptr | node_ptr |
| typedef implementation_defined::const_node_ptr | const_node_ptr |
| typedef node_algorithms::insert_commit_data | insert_commit_data |
Public Member Functions | |
| typedef | BOOST_INTRUSIVE_IMPDEF (treap_algorithms< node_traits >) node_algorithms |
| typedef | BOOST_INTRUSIVE_IMPDEF (typename get_prio_type::type) priority_compare |
| treap_impl (const value_compare &cmp=value_compare(), const priority_compare &pcmp=priority_compare(), const value_traits &v_traits=value_traits()) | |
| Effects: Constructs an empty container. More... | |
| template<class Iterator > | |
| treap_impl (bool unique, 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. More... | |
| treap_impl (BOOST_RV_REF(treap_impl) x) | |
| treap_impl & | operator= (BOOST_RV_REF(treap_impl) x) |
| iterator | top () |
| Effects: Returns an iterator pointing to the highest priority object of the treap. More... | |
| const_iterator | top () const |
| Effects: Returns a const_iterator pointing to the highest priority object of the treap. More... | |
| const_iterator | ctop () const |
| Effects: Returns a const_iterator pointing to the highest priority object of the treap. More... | |
| reverse_iterator | rtop () |
| Effects: Returns a reverse_iterator pointing to the highest priority object of the reversed treap. More... | |
| const_reverse_iterator | rtop () const |
| Effects: Returns a const_reverse_iterator pointing to the highest priority objec of the reversed treap. More... | |
| const_reverse_iterator | crtop () const |
| Effects: Returns a const_reverse_iterator pointing to the highest priority object of the reversed treap. More... | |
| priority_compare | priority_comp () const |
| Effects: Returns the priority_compare object used by the container. More... | |
| void | swap (treap_impl &other) |
| Effects: Swaps the contents of two treaps. More... | |
| template<class Cloner , class Disposer > | |
| void | clone_from (const treap_impl &src, Cloner cloner, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| iterator | insert_equal (reference value) |
| Requires: value must be an lvalue More... | |
| iterator | insert_equal (const_iterator hint, reference value) |
| Requires: value must be an lvalue, and "hint" must be a valid iterator. More... | |
| template<class Iterator > | |
| void | insert_equal (Iterator b, Iterator e) |
| Requires: Dereferencing iterator must yield an lvalue of type value_type. More... | |
| std::pair< iterator, bool > | insert_unique (reference value) |
| Requires: value must be an lvalue More... | |
| iterator | insert_unique (const_iterator hint, reference value) |
| Requires: value must be an lvalue, and "hint" must be a valid iterator More... | |
| template<class Iterator > | |
| void | insert_unique (Iterator b, Iterator e) |
| Requires: Dereferencing iterator must yield an lvalue of type value_type. More... | |
| template<class KeyType , class KeyValueCompare , class KeyValuePrioCompare > | |
| std::pair< iterator, bool > | insert_unique_check (const KeyType &key, KeyValueCompare key_value_comp, KeyValuePrioCompare key_value_pcomp, insert_commit_data &commit_data) |
| Requires: key_value_comp must be a comparison function that induces the same strict weak ordering as value_compare. More... | |
| template<class KeyType , class KeyValueCompare , class KeyValuePrioCompare > | |
| std::pair< iterator, bool > | insert_unique_check (const_iterator hint, const KeyType &key, KeyValueCompare key_value_comp, KeyValuePrioCompare key_value_pcomp, insert_commit_data &commit_data) |
| Requires: key_value_comp must be a comparison function that induces the same strict weak ordering as value_compare. More... | |
| iterator | insert_unique_commit (reference value, const insert_commit_data &commit_data) |
| Requires: value must be an lvalue of type value_type. More... | |
| 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 More... | |
| void | push_back (reference value) |
| Requires: value must be an lvalue, and it must be no less than the greatest inserted key More... | |
| void | push_front (reference value) |
| Requires: value must be an lvalue, and it must be no greater than the minimum inserted key More... | |
| iterator | erase (const_iterator i) |
| Effects: Erases the element pointed to by pos. More... | |
| iterator | erase (const_iterator b, const_iterator e) |
| Effects: Erases the range pointed to by b end e. More... | |
| size_type | erase (const_reference value) |
| Effects: Erases all the elements with the given value. More... | |
| template<class KeyType , class KeyValueCompare > | |
| size_type | erase (const KeyType &key, KeyValueCompare comp) |
| Effects: Erases all the elements with the given key. More... | |
| template<class Disposer > | |
| iterator | erase_and_dispose (const_iterator i, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| template<class Disposer > | |
| iterator | erase_and_dispose (iterator i, Disposer disposer) |
| template<class Disposer > | |
| iterator | erase_and_dispose (const_iterator b, const_iterator e, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| template<class Disposer > | |
| size_type | erase_and_dispose (const_reference value, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| template<class KeyType , class KeyValueCompare , class Disposer > | |
| size_type | erase_and_dispose (const KeyType &key, KeyValueCompare comp, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| void | clear () |
| Effects: Erases all of the elements. More... | |
| template<class Disposer > | |
| void | clear_and_dispose (Disposer disposer) |
| Effects: Erases all of the elements calling disposer(p) for each node to be erased. More... | |
| template<class ExtraChecker > | |
| void | check (ExtraChecker extra_checker) const |
| void | check () const |
Static Public Attributes | |
| static const bool | constant_time_size = implementation_defined::constant_time_size |
| static const bool | stateful_value_traits = implementation_defined::stateful_value_traits |
| static const bool | safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value |
The class template treap is an intrusive treap container that is used to construct intrusive set and multiset containers.
The no-throw guarantee holds only, if the value_compare object and priority_compare object don't throw.
The template parameter T is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.
The container supports the following options: base_hook<>/member_hook<>/value_traits<>, constant_time_size<>, size_type<>, compare<> and priority_compare<>
| typedef implementation_defined::const_iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_iterator |
| typedef implementation_defined::const_node_ptr boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_node_ptr |
| typedef implementation_defined::const_pointer boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_pointer |
| typedef implementation_defined::const_reference boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_reference |
| typedef implementation_defined::const_reverse_iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_reverse_iterator |
| typedef implementation_defined::difference_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::difference_type |
| typedef node_algorithms::insert_commit_data boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_commit_data |
| typedef implementation_defined::iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::iterator |
| typedef implementation_defined::key_compare boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::key_compare |
| typedef implementation_defined::key_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::key_type |
| typedef implementation_defined::node boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::node |
| typedef implementation_defined::node_ptr boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::node_ptr |
| typedef implementation_defined::node_traits boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::node_traits |
| typedef implementation_defined::pointer boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::pointer |
| typedef implementation_defined::reference boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::reference |
| typedef implementation_defined::reverse_iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::reverse_iterator |
| typedef implementation_defined::size_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::size_type |
| typedef implementation_defined::value_compare boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::value_compare |
| typedef ValueTraits boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::value_traits |
| typedef implementation_defined::value_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::value_type |
|
inlineexplicit |
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.
|
inline |
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 value_compare/priority_compare objects throw. Basic guarantee.
References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_equal(), and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique().
|
inline |
| typedef boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF | ( | treap_algorithms< node_traits > | ) |
| typedef boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF | ( | typename get_prio_type::type | ) |
|
inline |
References boost::xpressive::check.
|
inline |
|
inline |
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.
References boost::fusion::clear().
|
inline |
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.
|
inline |
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.
|
inline |
Effects: Returns a const_reverse_iterator pointing to the highest priority object of the reversed treap.
Complexity: Constant.
Throws: Nothing.
|
inline |
Effects: Returns a const_iterator pointing to the highest priority object of the treap.
Complexity: Constant.
Throws: Nothing.
References boost::units::root().
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::top().
|
inline |
Effects: Erases the element pointed to by pos.
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.
References boost::fusion::erase(), boost::unit_test::framework::init(), boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::safemode_or_autounlink, and boost::geometry::unique().
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase(), and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose().
|
inline |
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.
References boost::n.
|
inline |
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.
|
inline |
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.
References boost::graph_detail::equal_range(), boost::n, and boost::multiprecision::backends::p.
|
inline |
Requires: Disposer::operator()(pointer) shouldn't throw.
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: if the internal priority_compare function throws. Strong guarantee.
Note: Invalidates the iterators to the erased elements.
|
inline |
|
inline |
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.
References boost::n.
|
inline |
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.
References boost::graph_detail::equal_range(), boost::n, and boost::multiprecision::backends::p.
|
inline |
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.
References boost::graph_detail::equal_range(), boost::n, and boost::multiprecision::backends::p.
|
inline |
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.
References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::safemode_or_autounlink, and boost::geometry::unique().
|
inline |
Requires: value must be an lvalue
Effects: Inserts value into the container before the upper bound.
Complexity: Average complexity for insert element is at most logarithmic.
Throws: If the internal value_compare or priority_compare functions throw. Strong guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::safemode_or_autounlink, and boost::geometry::unique().
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_equal(), and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::treap_impl().
|
inline |
Requires: value must be an lvalue, and "hint" must be a valid iterator.
Effects: Inserts x into the container, using "hint" as a hint to where it will be inserted. If "hint" is the upper_bound the insertion takes constant time (two comparisons in the worst case)
Complexity: Logarithmic in general, but it is amortized constant time if t is inserted immediately before hint.
Throws: If the internal value_compare or priority_compare functions throw. Strong guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::safemode_or_autounlink, and boost::geometry::unique().
|
inline |
Requires: Dereferencing iterator must yield an lvalue of type value_type.
Effects: Inserts a each element of a range into the container before the upper bound of the key of each element.
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 or priority_compare functions throw. Strong guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
References boost::asio::b, boost::end, and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_equal().
|
inline |
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 value_compare or priority_compare functions throw. Strong guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique_check(), and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique_commit().
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique(), and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::treap_impl().
|
inline |
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 value_compare or priority_compare functions throw. Strong guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique_check(), and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique_commit().
|
inline |
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 value_comp().
Throws: If the internal value_compare or priority_compare functions throw. Strong guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
References boost::asio::b, boost::empty(), boost::end, and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique().
|
inline |
Requires: key_value_comp must be a comparison function that induces the same strict weak ordering as value_compare.
key_value_pcomp must be a comparison function that induces the same strict weak ordering as priority_compare. The difference is that key_value_pcomp and key_value_comp compare an arbitrary key with the contained values.
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 key_value_comp or key_value_pcomp ordering 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.
References boost::multiprecision::backends::this.
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique().
|
inline |
Requires: key_value_comp must be a comparison function that induces the same strict weak ordering as value_compare.
key_value_pcomp must be a comparison function that induces the same strict weak ordering as priority_compare. The difference is that key_value_pcomp and key_value_comp compare an arbitrary key with the contained values.
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 key_value_comp or key_value_pcomp ordering 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.
References boost::multiprecision::backends::this.
|
inline |
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.
References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::safemode_or_autounlink, and boost::geometry::unique().
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique().
|
inline |
|
inline |
Effects: Returns the priority_compare object used by the container.
Complexity: Constant.
Throws: If priority_compare copy-constructor throws.
|
inline |
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.
References boost::xpressive::push_back, boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::safemode_or_autounlink, and boost::geometry::unique().
|
inline |
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.
References boost::xpressive::push_front, boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::safemode_or_autounlink, and boost::geometry::unique().
|
inline |
Effects: Returns a reverse_iterator pointing to the highest priority object of the reversed treap.
Complexity: Constant.
Throws: Nothing.
|
inline |
Effects: Returns a const_reverse_iterator pointing to the highest priority objec of the reversed treap.
Complexity: Constant.
Throws: Nothing.
|
inline |
Effects: Swaps the contents of two treaps.
Complexity: Constant.
Throws: If the comparison functor's swap call throws.
References boost::swap.
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::operator=().
|
inline |
Effects: Returns an iterator pointing to the highest priority object of the treap.
Complexity: Constant.
Throws: Nothing.
References boost::units::root().
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::crtop(), and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::rtop().
|
inline |
Effects: Returns a const_iterator pointing to the highest priority object of the treap.
Complexity: Constant.
Throws: Nothing.
|
static |
|
static |
Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase(), boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_before(), boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_equal(), boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique_commit(), boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::push_back(), and boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::push_front().
|
static |
1.8.8