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

#include <bs_set.hpp>

Inheritance diagram for boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >:

[legend]

Collaboration diagram for boost::intrusive::bs_multiset_impl< ValueTraits, Compare, 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::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

Public Member Functions
	bs_multiset_impl (const value_compare &cmp=value_compare(), const value_traits &v_traits=value_traits())

template<class Iterator >
	bs_multiset_impl (Iterator b, Iterator e, const value_compare &cmp=value_compare(), const value_traits &v_traits=value_traits())

	bs_multiset_impl (BOOST_RV_REF(bs_multiset_impl) x)

bs_multiset_impl &	operator= (BOOST_RV_REF(bs_multiset_impl) x)

iterator	insert (reference value)

iterator	insert (const_iterator hint, reference value)

template<class Iterator >
void	insert (Iterator b, Iterator e)

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

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

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

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

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

size_type	erase (const KeyType &key, KeyValueCompare comp)
	Effects: Erases all the elements with the given key. More...

iterator	erase_and_dispose (const_iterator i, Disposer disposer)
	Requires: Disposer::operator()(pointer) shouldn't throw. More...

iterator	erase_and_dispose (iterator i, Disposer disposer)

size_type	erase_and_dispose (const_reference value, Disposer disposer)
	Requires: Disposer::operator()(pointer) shouldn't throw. More...

iterator	erase_and_dispose (const_iterator b, const_iterator e, Disposer disposer)
	Requires: Disposer::operator()(pointer) shouldn't throw. More...

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

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

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)

size_type	count (const KeyType &key, KeyValueCompare comp)

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

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 = tree_type::constant_time_size

static const bool	stateful_value_traits

Detailed Description

template<class ValueTraits, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
class boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >

The class template bs_multiset is an intrusive container, that mimics most of the interface of std::multiset 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<> and compare<>.

Member Typedef Documentation

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::const_iterator boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::const_iterator

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::const_node_ptr boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::const_node_ptr

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::const_pointer boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::const_pointer

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::const_reference boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::const_reference

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::const_reverse_iterator boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::const_reverse_iterator

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::difference_type boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::difference_type

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::insert_commit_data boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::insert_commit_data

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::iterator boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::iterator

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::key_compare boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::key_compare

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::node boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::node

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::node_algorithms boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::node_algorithms

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::node_ptr boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::node_ptr

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::node_traits boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::node_traits

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::pointer boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::pointer

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::reference boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::reference

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::reverse_iterator boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::reverse_iterator

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::size_type boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::size_type

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::value_compare boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::value_compare

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::value_traits boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::value_traits

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

typedef implementation_defined::value_type boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::value_type

Constructor & Destructor Documentation

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

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

inlineexplicit

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

template<class Iterator >

boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::bs_multiset_impl	(	Iterator	b,
		Iterator	e,
		const value_compare &	cmp = `value_compare()`,
		const value_traits &	v_traits = `value_traits()`
	)

inline

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::bs_multiset_impl ( BOOST_RV_REF(bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >) x )

inline

Member Function Documentation

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inherited

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

inlineinherited

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.

References boost::xpressive::check, and boost::detail::type.

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

inlineinherited

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.

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

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

void boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, 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.

void boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::clone_from	(	const bstree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, 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.

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::clear_and_dispose(), and boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::empty().

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

inlinestaticinherited

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

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

Throws: Nothing.

Complexity: Constant.

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

inlinestaticinherited

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.

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

inlinestaticinherited

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.

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::container_from_end_iterator().

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

inlinestaticinherited

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.

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::container_from_end_iterator().

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

inlineinherited

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.

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::count().

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

inlineinherited

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.

References boost::graph_detail::equal_range(), and boost::n.

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

inlineinherited

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::count().

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

inlineinherited

References boost::graph_detail::equal_range(), and boost::n.

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

inlineinherited

Effects: Returns true if the container is empty.

Complexity: Constant.

Throws: Nothing.

References boost::geometry::unique().

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

inlineinherited

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.

References boost::fusion::erase(), boost::unit_test::framework::init(), and boost::geometry::unique().

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

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

References boost::n.

size_type boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, 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: Nothing.

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

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase().

size_type boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, 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: Nothing.

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

References boost::graph_detail::equal_range(), and boost::n.

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

Note: Invalidates the iterators to the erased elements.

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase().

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

inlineinherited

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::erase_and_dispose().

size_type boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, 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: Nothing.

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

References boost::graph_detail::equal_range(), and boost::n.

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

Note: Invalidates the iterators to the erased elements.

References boost::n.

size_type boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, 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: Nothing.

Note: Invalidates the iterators to the erased elements.

References boost::graph_detail::equal_range(), and boost::n.

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

iterator boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::insert ( reference value )

inline

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

iterator boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::insert	(	const_iterator	hint,
		reference	value
	)

inline

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

template<class Iterator >

void boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::insert	(	Iterator	b,
		Iterator	e
	)

inline

iterator boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, 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: 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.

References boost::geometry::unique().

iterator boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, 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 ordering function throws. Strong guarantee.

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

References boost::geometry::unique().

iterator boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, 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 ordering function throws. Strong guarantee.

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

References boost::geometry::unique().

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

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

References boost::asio::b, boost::end, and boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_equal().

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

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

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_unique_commit().

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

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

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_unique_commit().

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

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

References boost::asio::b, boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::empty(), boost::end, and boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_unique().

iterator boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::insert_unique_commit	(	reference	value,
		const insert_commit_data &	commit_data
	)

inlineinherited

Requires: value must be an lvalue of type value_type.

commit_data must have been obtained from a previous call to "insert_check". No objects should have been inserted or erased from the container between the "insert_check" that filled "commit_data" and the call to "insert_commit".

Effects: Inserts the value in the 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.

References boost::geometry::unique().

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

bs_multiset_impl& boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::operator= ( BOOST_RV_REF(bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >) x )

inline

References boost::move(), and boost::multiprecision::backends::operator=().

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

inlineinherited

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

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

Complexity: Constant time.

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

References boost::xpressive::push_back, and boost::geometry::unique().

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

inlineinherited

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

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

Complexity: Constant time.

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

References boost::xpressive::push_front, and boost::geometry::unique().

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

inlinestaticinherited

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.

References boost::BOOST_STATIC_ASSERT(), and boost::unit_test::framework::init().

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

inlineinherited

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.

References boost::fusion::size().

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

inlineinherited

Effects: Swaps the contents of two containers.

Complexity: Constant.

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

References boost::intrusive::bstree_impl< ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::swap(), and boost::intrusive::swap().

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

inlineinherited

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.

References boost::unit_test::framework::init().

Member Data Documentation

template<class ValueTraits , class Compare , class SizeType , bool ConstantTimeSize, typename HeaderHolder >

const bool boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::constant_time_size = tree_type::constant_time_size

static

const bool boost::intrusive::bstree_impl< ValueTraits, Compare , SizeType, ConstantTimeSize, AlgoType, HeaderHolder >::stateful_value_traits

staticinherited

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

boost_1_57_0/boost/intrusive/bs_set.hpp

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

template<class ValueTraits, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder> class boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class ValueTraits, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
class boost::intrusive::bs_multiset_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >