boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder > Class Template Reference

The class template splaytree is an intrusive splay tree container that is used to construct intrusive splay_set and splay_multiset containers. More...

#include <splaytree.hpp>

Inheritance diagram for boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >:

Public Types
typedef ValueTraits	value_traits
typedef implementation_defined::pointer	pointer
typedef implementation_defined::const_pointer	const_pointer
typedef implementation_defined::value_type	value_type
typedef implementation_defined::key_type	key_type
typedef implementation_defined::reference	reference
typedef implementation_defined::const_reference	const_reference
typedef implementation_defined::difference_type	difference_type
typedef implementation_defined::size_type	size_type
typedef implementation_defined::value_compare	value_compare
typedef implementation_defined::key_compare	key_compare
typedef implementation_defined::iterator	iterator
typedef implementation_defined::const_iterator	const_iterator
typedef implementation_defined::reverse_iterator	reverse_iterator
typedef implementation_defined::const_reverse_iterator	const_reverse_iterator
typedef implementation_defined::node_traits	node_traits
typedef implementation_defined::node	node
typedef implementation_defined::node_ptr	node_ptr
typedef implementation_defined::const_node_ptr	const_node_ptr
typedef implementation_defined::node_algorithms	node_algorithms
typedef implementation_defined::insert_commit_data	insert_commit_data

Public Member Functions
	splaytree_impl (const value_compare &cmp=value_compare(), const value_traits &v_traits=value_traits())
template<class Iterator >
	splaytree_impl (bool unique, Iterator b, Iterator e, const value_compare &cmp=value_compare(), const value_traits &v_traits=value_traits())
	splaytree_impl (BOOST_RV_REF(splaytree_impl) x)
splaytree_impl &	operator= (BOOST_RV_REF(splaytree_impl) x)
void	splay_up (iterator i)
	Requires: i must be a valid iterator of *this. More...
template<class KeyType , class KeyValueCompare >
iterator	splay_down (const KeyType &key, KeyValueCompare comp)
	Effects: Rearranges the container so that if *this stores an element with a key equivalent to value the element is placed as the root of the tree. More...
iterator	splay_down (const_reference value)
	Effects: Rearranges the container so that if *this stores an element with a key equivalent to value the element is placed as the root of the tree. More...

Static Public Attributes
static const bool	constant_time_size = implementation_defined::constant_time_size

Detailed Description

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

The class template splaytree is an intrusive splay tree container that is used to construct intrusive splay_set and splay_multiset containers.

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

The template parameter T is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.

The container supports the following options: base_hook<>/member_hook<>/value_traits<>, constant_time_size<>, size_type<> and compare<>.

Member Typedef Documentation

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

typedef implementation_defined::const_iterator boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::const_iterator

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

typedef implementation_defined::const_node_ptr boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::const_node_ptr

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

typedef implementation_defined::const_pointer boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::const_pointer

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

typedef implementation_defined::const_reference boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::const_reference

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

typedef implementation_defined::const_reverse_iterator boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::const_reverse_iterator

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

typedef implementation_defined::difference_type boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::difference_type

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

typedef implementation_defined::insert_commit_data boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::insert_commit_data

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

typedef implementation_defined::iterator boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::iterator

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

typedef implementation_defined::key_compare boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::key_compare

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

typedef implementation_defined::key_type boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::key_type

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

typedef implementation_defined::node boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::node

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

typedef implementation_defined::node_algorithms boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::node_algorithms

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

typedef implementation_defined::node_ptr boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::node_ptr

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

typedef implementation_defined::node_traits boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::node_traits

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

typedef implementation_defined::pointer boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::pointer

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

typedef implementation_defined::reference boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::reference

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

typedef implementation_defined::reverse_iterator boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::reverse_iterator

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

typedef implementation_defined::size_type boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::size_type

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

typedef implementation_defined::value_compare boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::value_compare

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

typedef ValueTraits boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::value_traits

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

typedef implementation_defined::value_type boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::value_type

Constructor & Destructor Documentation

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

boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::splaytree_impl ( const value_compare &  cmp = value_compare(), const value_traits &  v_traits = value_traits()  )

inlineexplicit

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

template<class Iterator >

boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::splaytree_impl ( bool  unique, Iterator  b, Iterator  e, const value_compare &  cmp = value_compare(), const value_traits &  v_traits = value_traits()  )

inline

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

boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::splaytree_impl ( BOOST_RV_REF(splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >)  x )

inline

Member Function Documentation

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

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

inline

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

template<class KeyType , class KeyValueCompare >

iterator boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::splay_down ( const KeyType &  key, KeyValueCompare  comp  )

inline

Effects: Rearranges the container so that if *this stores an element with a key equivalent to value the element is placed as the root of the tree.

If the element is not present returns the last node compared with the key. If the tree is empty, end() is returned.

Complexity: Amortized logarithmic.

Returns: An iterator to the new root of the tree, end() if the tree is empty.

Throws: If the comparison functor throws.

Referenced by boost::intrusive::splaytree_impl< ValueTraits, Compare, SizeType, ConstantTimeSize, HeaderHolder >::splay_down().

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

iterator boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::splay_down ( const_reference  value )

inline

Effects: Rearranges the container so that if *this stores an element with a key equivalent to value the element is placed as the root of the tree.

Complexity: Amortized logarithmic.

Returns: An iterator to the new root of the tree, end() if the tree is empty.

Throws: If the predicate throws.

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

void boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::splay_up ( iterator  i )

inline

Requires: i must be a valid iterator of *this.

Effects: Rearranges the container so that the element pointed by i is placed as the root of the tree, improving future searches of this value.

Complexity: Amortized logarithmic.

Throws: Nothing.

Member Data Documentation

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

const bool boost::intrusive::splaytree_impl< ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, HeaderHolder >::constant_time_size = implementation_defined::constant_time_size

static

---

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

• boost_1_57_0/boost/intrusive/splaytree.hpp