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

[legend]

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

[legend]

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_impl &	operator= (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, iterator >	equal_range (const_reference value)

template<class KeyType , class KeyValueCompare >
std::pair< iterator, iterator >	equal_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

References boost::xpressive::check.

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

References boost::algorithm::find().

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

References boost::algorithm::find().

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

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

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

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