Boost  v1.57.0
doxygen for www.boost.org
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder > Class Template Reference

The class template treap_set is an intrusive container, that mimics most of the interface of std::set as described in the C++ standard. More...

#include <treap_set.hpp>

Inheritance diagram for boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >:
Collaboration diagram for boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >:

Public Types

typedef
implementation_defined::value_type 
value_type
 
typedef
implementation_defined::value_traits 
value_traits
 
typedef
implementation_defined::pointer 
pointer
 
typedef
implementation_defined::const_pointer 
const_pointer
 
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::priority_compare 
priority_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::insert_commit_data 
insert_commit_data
 
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
implementation_defined::node_algorithms 
node_algorithms
 
typedef
implementation_defined::key_type 
key_type
 

Public Member Functions

 treap_set_impl (const value_compare &cmp=value_compare(), const priority_compare &pcmp=priority_compare(), const value_traits &v_traits=value_traits())
 Effects: Constructs an empty treap_set. More...
 
template<class Iterator >
 treap_set_impl (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_set_impl (BOOST_RV_REF(treap_set_impl) x)
 Effects: to-do More...
 
treap_set_imploperator= (BOOST_RV_REF(treap_set_impl) x)
 Effects: to-do More...
 
std::pair< iterator, bool > insert (reference value)
 Requires: value must be an lvalue More...
 
iterator insert (const_iterator hint, reference value)
 Requires: value must be an lvalue, and "hint" must be a valid iterator More...
 
template<class KeyType , class KeyValueCompare , class KeyValuePrioCompare >
std::pair< iterator, bool > insert_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_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...
 
template<class Iterator >
void insert (Iterator b, Iterator e)
 Requires: Dereferencing iterator must yield an lvalue of type value_type. More...
 
iterator insert_commit (reference value, const insert_commit_data &commit_data)
 Requires: value must be an lvalue of type value_type. More...
 
size_type count (const_reference value) const
 
template<class KeyType , class KeyValueCompare >
size_type count (const KeyType &key, KeyValueCompare comp) const
 
std::pair< iterator, iteratorequal_range (const_reference value)
 
template<class KeyType , class KeyValueCompare >
std::pair< iterator, iteratorequal_range (const KeyType &key, KeyValueCompare comp)
 
std::pair< const_iterator,
const_iterator
equal_range (const_reference value) const
 
template<class KeyType , class KeyValueCompare >
std::pair< const_iterator,
const_iterator
equal_range (const KeyType &key, KeyValueCompare comp) const
 
typedef BOOST_INTRUSIVE_IMPDEF (treap_algorithms< node_traits >) node_algorithms
 
typedef BOOST_INTRUSIVE_IMPDEF (typename get_prio_type::type) priority_compare
 
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
 

Detailed Description

template<class ValueTraits, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
class boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >

The class template treap_set is an intrusive container, that mimics most of the interface of std::set as described in the C++ standard.

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

Member Typedef Documentation

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::const_iterator boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_iterator
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::const_node_ptr boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_node_ptr
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::const_pointer boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_pointer
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::const_reference boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_reference
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::const_reverse_iterator boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::const_reverse_iterator
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::difference_type boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::difference_type
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::insert_commit_data boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_commit_data
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::iterator boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::iterator
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::key_compare boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::key_compare
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::key_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::key_type
inherited
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::node boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::node
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::node_algorithms boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::node_algorithms
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::node_ptr boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::node_ptr
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::node_traits boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::node_traits
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::pointer boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::pointer
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::priority_compare boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::priority_compare
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::reference boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::reference
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::reverse_iterator boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::reverse_iterator
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::size_type boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::size_type
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::value_compare boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::value_compare
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::value_traits boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::value_traits
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef implementation_defined::value_type boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::value_type

Constructor & Destructor Documentation

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::treap_set_impl ( const value_compare cmp = value_compare(),
const priority_compare pcmp = priority_compare(),
const value_traits v_traits = value_traits() 
)
inlineexplicit

Effects: Constructs an empty treap_set.

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Iterator >
boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::treap_set_impl ( Iterator  b,
Iterator  e,
const value_compare cmp = value_compare(),
const priority_compare pcmp = priority_compare(),
const value_traits v_traits = value_traits() 
)
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 treap_set 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 std::distance(last, first).

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<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::treap_set_impl ( BOOST_RV_REF(treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >)  x)
inline

Effects: to-do

Member Function Documentation

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( treap_algorithms< node_traits )
inherited
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
typedef boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename get_prio_type::type  )
inherited
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class ExtraChecker >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::check ( ExtraChecker  extra_checker) const
inlineinherited
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::check ( ) const
inlineinherited

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::clear ( void  )
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Disposer >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::clear_and_dispose ( Disposer  disposer)
inlineinherited

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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Cloner , class Disposer >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::clone_from ( const treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder > &  src,
Cloner  cloner,
Disposer  disposer 
)
inlineinherited

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<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
size_type boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::count ( const_reference  value) const
inline
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare >
size_type boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::count ( const KeyType &  key,
KeyValueCompare  comp 
) const
inline
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
const_reverse_iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::crtop ( ) const
inlineinherited

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

Complexity: Constant.

Throws: Nothing.

References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::top().

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
const_iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::ctop ( ) const
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
std::pair<iterator,iterator> boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::equal_range ( const_reference  value)
inline

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare >
std::pair<iterator,iterator> boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::equal_range ( const KeyType &  key,
KeyValueCompare  comp 
)
inline

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
std::pair<const_iterator, const_iterator> boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::equal_range ( const_reference  value) const
inline

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare >
std::pair<const_iterator, const_iterator> boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::equal_range ( const KeyType &  key,
KeyValueCompare  comp 
) const
inline

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase ( const_iterator  i)
inlineinherited
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase ( const_iterator  b,
const_iterator  e 
)
inlineinherited

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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
size_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase ( const_reference  value)
inlineinherited

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.

References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase().

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare >
size_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase ( const KeyType &  key,
KeyValueCompare  comp 
)
inlineinherited

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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Disposer >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose ( const_iterator  i,
Disposer  disposer 
)
inlineinherited

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.

References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase().

Referenced by boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose().

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Disposer >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose ( iterator  i,
Disposer  disposer 
)
inlineinherited
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Disposer >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose ( const_iterator  b,
const_iterator  e,
Disposer  disposer 
)
inlineinherited

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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Disposer >
size_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose ( const_reference  value,
Disposer  disposer 
)
inlineinherited

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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare , class Disposer >
size_type boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose ( const KeyType &  key,
KeyValueCompare  comp,
Disposer  disposer 
)
inlineinherited

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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
std::pair<iterator, bool> boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert ( reference  value)
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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert ( const_iterator  hint,
reference  value 
)
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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Iterator >
void boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert ( Iterator  b,
Iterator  e 
)
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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_before ( const_iterator  pos,
reference  value 
)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare , class KeyValuePrioCompare >
std::pair<iterator, bool> boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_check ( const KeyType &  key,
KeyValueCompare  key_value_comp,
KeyValuePrioCompare  key_value_pcomp,
insert_commit_data commit_data 
)
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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare , class KeyValuePrioCompare >
std::pair<iterator, bool> boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_check ( const_iterator  hint,
const KeyType &  key,
KeyValueCompare  key_value_comp,
KeyValuePrioCompare  key_value_pcomp,
insert_commit_data commit_data 
)
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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_commit ( reference  value,
const insert_commit_data commit_data 
)
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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_equal ( reference  value)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_equal ( const_iterator  hint,
reference  value 
)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Iterator >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_equal ( Iterator  b,
Iterator  e 
)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
std::pair<iterator, bool> boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique ( reference  value)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique ( const_iterator  hint,
reference  value 
)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class Iterator >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique ( Iterator  b,
Iterator  e 
)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare , class KeyValuePrioCompare >
std::pair<iterator, bool> boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique_check ( const KeyType &  key,
KeyValueCompare  key_value_comp,
KeyValuePrioCompare  key_value_pcomp,
insert_commit_data commit_data 
)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
template<class KeyType , class KeyValueCompare , class KeyValuePrioCompare >
std::pair<iterator, bool> boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique_check ( const_iterator  hint,
const KeyType &  key,
KeyValueCompare  key_value_comp,
KeyValuePrioCompare  key_value_pcomp,
insert_commit_data commit_data 
)
inlineinherited

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.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_unique_commit ( reference  value,
const insert_commit_data commit_data 
)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
treap_set_impl& boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::operator= ( BOOST_RV_REF(treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >)  x)
inline
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
priority_compare boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::priority_comp ( ) const
inlineinherited

Effects: Returns the priority_compare object used by the container.

Complexity: Constant.

Throws: If priority_compare copy-constructor throws.

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::push_back ( reference  value)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::push_front ( reference  value)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
reverse_iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::rtop ( )
inlineinherited

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

Complexity: Constant.

Throws: Nothing.

References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::top().

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
const_reverse_iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::rtop ( ) const
inlineinherited

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

Complexity: Constant.

Throws: Nothing.

References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::top().

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
void boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::swap ( treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder > &  other)
inlineinherited

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

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::top ( void  )
inlineinherited
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
const_iterator boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::top ( void  ) const
inlineinherited

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

Complexity: Constant.

Throws: Nothing.

References boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::ctop().

Member Data Documentation

template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
const bool boost::intrusive::treap_set_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::constant_time_size = implementation_defined::constant_time_size
static
template<class ValueTraits , class VoidOrKeyComp , class VoidOrPrioComp , class SizeType , bool ConstantTimeSize, typename HeaderHolder >
const bool boost::intrusive::treap_impl< ValueTraits, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder >::stateful_value_traits = implementation_defined::stateful_value_traits
staticinherited

The documentation for this class was generated from the following file: