The class template bstree is an unbalanced intrusive binary search tree container. More...

#include <bstree.hpp>

Inheritance diagram for boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >:

[legend]

Collaboration diagram for boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >:

[legend]

Public Types
typedef node_algorithms::insert_commit_data	insert_commit_data

Public Member Functions
typedef	BOOST_INTRUSIVE_IMPDEF (ValueTraits) value_traits

typedef	BOOST_INTRUSIVE_IMPDEF (typename value_traits::pointer) pointer

typedef	BOOST_INTRUSIVE_IMPDEF (typename value_traits::const_pointer) const _pointer

typedef	BOOST_INTRUSIVE_IMPDEF (typename pointer_traits< pointer >::element_type) value_type

typedef	BOOST_INTRUSIVE_IMPDEF (value_type) key_type

typedef	BOOST_INTRUSIVE_IMPDEF (typename pointer_traits< pointer >::reference) reference

typedef	BOOST_INTRUSIVE_IMPDEF (typename pointer_traits< const_pointer >::reference) const _reference

typedef	BOOST_INTRUSIVE_IMPDEF (typename pointer_traits< const_pointer >::difference_type) difference_type

typedef	BOOST_INTRUSIVE_IMPDEF (SizeType) size_type

typedef	BOOST_INTRUSIVE_IMPDEF (typename data_type::value_compare) value_compare

typedef	BOOST_INTRUSIVE_IMPDEF (value_compare) key_compare

typedef	BOOST_INTRUSIVE_IMPDEF (iterator_type) iterator

typedef	BOOST_INTRUSIVE_IMPDEF (const_iterator_type) const _iterator

typedef	BOOST_INTRUSIVE_IMPDEF (boost::intrusive::detail::reverse_iterator< iterator >) reverse_iterator

typedef	BOOST_INTRUSIVE_IMPDEF (boost::intrusive::detail::reverse_iterator< const_iterator >) const _reverse_iterator

typedef	BOOST_INTRUSIVE_IMPDEF (typename value_traits::node_traits) node_traits

typedef	BOOST_INTRUSIVE_IMPDEF (typename node_traits::node) node

typedef	BOOST_INTRUSIVE_IMPDEF (typename node_traits::node_ptr) node_ptr

typedef	BOOST_INTRUSIVE_IMPDEF (typename node_traits::const_node_ptr) const _node_ptr

typedef	BOOST_INTRUSIVE_IMPDEF (algo_type) node_algorithms

	bstree_impl (const value_compare &cmp=value_compare(), const value_traits &v_traits=value_traits())
	Effects: Constructs an empty container. More...

template<class Iterator >
	bstree_impl (bool unique, Iterator b, Iterator e, const value_compare &cmp=value_compare(), const value_traits &v_traits=value_traits())
	Requires: Dereferencing iterator must yield an lvalue of type value_type. More...

	bstree_impl (BOOST_RV_REF(bstree_impl) x)
	Effects: to-do More...

bstree_impl &	operator= (BOOST_RV_REF(bstree_impl) x)
	Effects: to-do More...

bool	empty () const
	Effects: Returns true if the container is empty. More...

size_type	size () const
	Effects: Returns the number of elements stored in the container. More...

void	swap (bstree_impl &other)
	Effects: Swaps the contents of two containers. More...

template<class Cloner , class Disposer >
void	clone_from (const bstree_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...

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 >
size_type	erase_and_dispose (const_reference value, Disposer disposer)
	Requires: Disposer::operator()(pointer) shouldn't throw. More...

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

size_type	count (const_reference value) const
	Effects: Returns the number of contained elements with the given value More...

template<class KeyType , class KeyValueCompare >
size_type	count (const KeyType &key, KeyValueCompare comp) const
	Effects: Returns the number of contained elements with the given key More...

size_type	count (const_reference value)

template<class KeyType , class KeyValueCompare >
size_type	count (const KeyType &key, KeyValueCompare comp)

pointer	unlink_leftmost_without_rebalance ()
	Effects: Unlinks the leftmost node from the container. More...

template<class ExtraChecker >
void	check (ExtraChecker extra_checker) const
	Effects: Asserts the integrity of the container with additional checks provided by the user. More...

void	check () const
	Effects: Asserts the integrity of the container. More...

Static Public Member Functions
static bstree_impl &	container_from_end_iterator (iterator end_iterator)
	Precondition: end_iterator must be a valid end iterator of the container. More...

static const bstree_impl &	container_from_end_iterator (const_iterator end_iterator)
	Precondition: end_iterator must be a valid end const_iterator of the container. More...

static bstree_impl &	container_from_iterator (iterator it)
	Precondition: it must be a valid iterator of the container. More...

static const bstree_impl &	container_from_iterator (const_iterator it)
	Precondition: it must be a valid end const_iterator of container. More...

static void	remove_node (reference value)
	Effects: removes "value" from the container. More...

Static Public Attributes
static const bool	constant_time_size = ConstantTimeSize

static const bool	stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value

Detailed Description

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
class boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >

The class template bstree is an unbalanced intrusive binary search tree container.

The no-throw guarantee holds only, if the value_compare object doesn't throw.

The complexity guarantees only hold if the tree is balanced, logarithmic complexity would increase to linear if the tree is totally unbalanced.

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<> and compare<>.

Member Typedef Documentation

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef node_algorithms::insert_commit_data boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_commit_data

Constructor & Destructor Documentation

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::bstree_impl	(	const value_compare &	cmp = `value_compare()`,
		const value_traits &	v_traits = `value_traits()`
	)

inlineexplicit

Effects: Constructs an empty container.

Complexity: Constant.

Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor of the value_compare object throws. Basic guarantee.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Iterator >

boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::bstree_impl	(	bool	unique,
		Iterator	b,
		Iterator	e,
		const value_compare &	cmp = `value_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 container and inserts elements from [b, e).

Complexity: Linear in N if [b, e) is already sorted using comp and otherwise N * log N, where N is the distance between first and last.

Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor/operator() of the value_compare object throws. Basic guarantee.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::bstree_impl ( BOOST_RV_REF(bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >) x )

inline

Effects: to-do

Member Function Documentation

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( ValueTraits )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename value_traits::pointer )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename value_traits::const_pointer ) const

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename pointer_traits< pointer >::element_type )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( value_type )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename pointer_traits< pointer >::reference )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename pointer_traits< const_pointer >::reference ) const

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename pointer_traits< const_pointer >::difference_type )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( SizeType )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename data_type::value_compare )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( value_compare )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( iterator_type )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( const_iterator_type ) const

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( boost::intrusive::detail::reverse_iterator< iterator > )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( boost::intrusive::detail::reverse_iterator< const_iterator > ) const

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename value_traits::node_traits )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename node_traits::node )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename node_traits::node_ptr )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( typename node_traits::const_node_ptr ) const

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

typedef boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::BOOST_INTRUSIVE_IMPDEF ( algo_type )

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class ExtraChecker >

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::check ( ExtraChecker extra_checker ) const

inline

Effects: Asserts the integrity of the container with additional checks provided by the user.

Complexity: Linear time.

Note: The method might not have effect when asserts are turned off (e.g., with NDEBUG). Experimental function, interface might change in future versions.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::check ( ) const

inline

Effects: Asserts the integrity of the container.

Complexity: Linear time.

Note: The method has no effect when asserts are turned off (e.g., with NDEBUG). Experimental function, interface might change in future versions.

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::check().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::clear ( void )

inline

Effects: Erases all of the elements.

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

Throws: Nothing.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Disposer >

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::clear_and_dispose ( Disposer disposer )

inline

Effects: Erases all of the elements calling disposer(p) for each node to be erased.

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

Throws: Nothing.

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

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::clear(), and boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::clone_from().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Cloner , class Disposer >

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::clone_from	(	const bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder > &	src,
		Cloner	cloner,
		Disposer	disposer
	)

inline

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

Cloner should yield to nodes equivalent to the original nodes.

Effects: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(const_reference ) and inserts them on *this. Copies the predicate from the source container.

If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).

Complexity: Linear to erased plus inserted elements.

Throws: If cloner throws or predicate copy assignment throws. Basic guarantee.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

static bstree_impl& boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::container_from_end_iterator ( iterator end_iterator )

inlinestatic

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

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

Throws: Nothing.

Complexity: Constant.

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::container_from_iterator().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

static const bstree_impl& boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::container_from_end_iterator ( const_iterator end_iterator )

inlinestatic

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

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

Throws: Nothing.

Complexity: Constant.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

static bstree_impl& boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::container_from_iterator ( iterator it )

inlinestatic

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

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

Throws: Nothing.

Complexity: Logarithmic.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

static const bstree_impl& boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::container_from_iterator ( const_iterator it )

inlinestatic

Precondition: it must be a valid end const_iterator of container.

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

Throws: Nothing.

Complexity: Logarithmic.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::count ( const_reference value ) const

inline

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

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

Throws: If value_compare throws.

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::count().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class KeyType , class KeyValueCompare >

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::count	(	const KeyType &	key,
		KeyValueCompare	comp
	)		const

inline

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

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

Throws: If comp throws.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::count ( const_reference value )

inline

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class KeyType , class KeyValueCompare >

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::count	(	const KeyType &	key,
		KeyValueCompare	comp
	)

inline

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

bool boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::empty ( void ) const

inline

Effects: Returns true if the container is empty.

Complexity: Constant.

Throws: Nothing.

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::clone_from(), and boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::insert_unique().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase ( const_iterator i )

inline

Effects: Erases the element pointed to by pos.

Complexity: Average complexity for erase element is constant time.

Throws: Nothing.

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

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::erase(), and boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::erase_and_dispose().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase	(	const_iterator	b,
		const_iterator	e
	)

inline

Effects: Erases the range pointed to by b end e.

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

Throws: Nothing.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase ( const_reference value )

inline

Effects: Erases all the elements with the given value.

Returns: The number of erased elements.

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

Throws: Nothing.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class KeyType , class KeyValueCompare >

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase	(	const KeyType &	key,
		KeyValueCompare	comp
	)

inline

Effects: Erases all the elements with the given key.

according to the comparison functor "comp".

Returns: The number of erased elements.

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

Throws: Nothing.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Disposer >

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase_and_dispose	(	const_iterator	i,
		Disposer	disposer
	)

inline

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

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

Complexity: Average complexity for erase element is constant time.

Throws: Nothing.

Note: Invalidates the iterators to the erased elements.

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::erase_and_dispose().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Disposer >

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase_and_dispose	(	iterator	i,
		Disposer	disposer
	)

inline

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Disposer >

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase_and_dispose	(	const_reference	value,
		Disposer	disposer
	)

inline

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

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

Returns: The number of erased elements.

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

Throws: Nothing.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Disposer >

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase_and_dispose	(	const_iterator	b,
		const_iterator	e,
		Disposer	disposer
	)

inline

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

Effects: Erases the range pointed to by b end e. Disposer::operator()(pointer) is called for the removed elements.

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

Throws: Nothing.

Note: Invalidates the iterators to the erased elements.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class KeyType , class KeyValueCompare , class Disposer >

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase_and_dispose	(	const KeyType &	key,
		KeyValueCompare	comp,
		Disposer	disposer
	)

inline

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

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

Returns: The number of erased elements.

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

Throws: Nothing.

Note: Invalidates the iterators to the erased elements.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_before	(	const_iterator	pos,
		reference	value
	)

inline

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

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

Complexity: Constant time.

Throws: Nothing.

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.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_equal ( reference value )

inline

Requires: value must be an lvalue

Effects: Inserts value into the container before the upper bound.

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

Throws: If the internal value_compare ordering function throws. Strong guarantee.

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

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::bstree_impl(), and boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::insert_equal().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_equal	(	const_iterator	hint,
		reference	value
	)

inline

Requires: value must be an lvalue, and "hint" must be a valid iterator.

Effects: Inserts x into the container, using "hint" as a hint to where it will be inserted. If "hint" is the upper_bound the insertion takes constant time (two comparisons in the worst case)

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

Throws: If the internal value_compare ordering function throws. Strong guarantee.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Iterator >

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_equal	(	Iterator	b,
		Iterator	e
	)

inline

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

Effects: Inserts a each element of a range into the container before the upper bound of the key of each element.

Complexity: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().

Throws: Nothing.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

std::pair<iterator, bool> boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_unique ( 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: Nothing.

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

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::bstree_impl(), and boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::insert_unique().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_unique	(	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: Nothing.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

template<class Iterator >

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_unique	(	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: Nothing.

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

iterator boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_unique_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 container 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.

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::insert_unique().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

bstree_impl& boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::operator= ( BOOST_RV_REF(bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >) x )

inline

Effects: to-do

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::push_back ( reference value )

inline

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

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

Complexity: Constant time.

Throws: Nothing.

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.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::push_front ( reference value )

inline

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

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

Complexity: Constant time.

Throws: Nothing.

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.

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

static void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::remove_node ( reference value )

inlinestatic

Effects: removes "value" from the container.

Throws: Nothing.

Complexity: Logarithmic time.

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

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

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

size_type boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::size ( void ) const

inline

Effects: Returns the number of elements stored in the container.

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

Throws: Nothing.

Referenced by boost::intrusive::operator==().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

void boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::swap ( bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder > & other )

inline

Effects: Swaps the contents of two containers.

Complexity: Constant.

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

Referenced by boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::bstree_impl(), boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::operator=(), boost::intrusive::bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder >::swap(), and boost::intrusive::swap().

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

pointer boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::unlink_leftmost_without_rebalance ( )

inline

Effects: Unlinks the leftmost node from the container.

Complexity: Average complexity is constant time.

Throws: Nothing.

Notes: This function breaks the container and the container can only be used for more unlink_leftmost_without_rebalance calls. This function is normally used to achieve a step by step controlled destruction of the container.

Member Data Documentation

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

const bool boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::constant_time_size = ConstantTimeSize

static

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>

const bool boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value

static

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

boost_1_57_0/boost/intrusive/bstree.hpp

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder> class boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class ValueTraits, class VoidKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder>
class boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >