__gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > Class Template Reference

Ordered-vector tree associative-container. More...

#include <ov_tree_map_.hpp>

Inheritance diagram for __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >:

Collaboration diagram for __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >:

Classes
class	cond_dtor
	Conditional destructor. More...

Public Types
typedef _Alloc	allocator_type
typedef Cmp_Fn	cmp_fn
typedef std::pair< size_type, size_type >	comp_hash
typedef point_const_iterator	const_iterator
typedef traits_base::const_pointer	const_pointer
typedef traits_base::const_reference	const_reference
typedef ov_tree_tag	container_category
typedef _Alloc::difference_type	difference_type
typedef point_iterator	iterator
typedef traits_base::key_const_pointer	key_const_pointer
typedef traits_base::key_const_reference	key_const_reference
typedef traits_base::key_pointer	key_pointer
typedef traits_base::key_reference	key_reference
typedef traits_base::key_type	key_type
typedef traits_base::mapped_const_pointer	mapped_const_pointer
typedef traits_base::mapped_const_reference	mapped_const_reference
typedef traits_base::mapped_pointer	mapped_pointer
typedef traits_base::mapped_reference	mapped_reference
typedef traits_base::mapped_type	mapped_type
typedef __nothrowcopy::indicator	no_throw_indicator
typedef traits_type::node_const_iterator	node_const_iterator
typedef traits_type::node_iterator	node_iterator
typedef traits_type::node_update	node_update
typedef const_pointer	point_const_iterator
typedef point_const_iterator	point_iterator
typedef traits_base::pointer	pointer
typedef traits_base::reference	reference
typedef _Alloc::size_type	size_type
typedef integral_constant< int, Store_Hash >	store_extra
typedef traits_base::value_type	value_type

Public Member Functions
	PB_DS_OV_TREE_NAME ()
	PB_DS_OV_TREE_NAME (const Cmp_Fn &)
	PB_DS_OV_TREE_NAME (const Cmp_Fn &, const node_update &)
	PB_DS_OV_TREE_NAME (const PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)
	~PB_DS_OV_TREE_NAME ()
iterator	begin ()
const_iterator	begin () const
void	clear ()
template<typename It >
void	copy_from_range (It, It)
bool	empty () const
iterator	end ()
const_iterator	end () const
bool	erase (key_const_reference)
iterator	erase (iterator it)
template<typename Pred >
size_type	erase_if (Pred)
point_iterator	find (key_const_reference r_key)
point_const_iterator	find (key_const_reference r_key) const
Cmp_Fn &	get_cmp_fn ()
const Cmp_Fn &	get_cmp_fn () const
std::pair< point_iterator, bool >	insert (const_reference r_value)
void	join (PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)
point_iterator	lower_bound (key_const_reference r_key)
point_const_iterator	lower_bound (key_const_reference r_key) const
size_type	max_size () const
node_const_iterator	node_begin () const
	Returns a const node_iterator corresponding to the node at the root of the tree. More...
node_iterator	node_begin ()
	Returns a node_iterator corresponding to the node at the root of the tree. More...
node_const_iterator	node_end () const
	Returns a const node_iterator corresponding to a node just after a leaf of the tree. More...
node_iterator	node_end ()
	Returns a node_iterator corresponding to a node just after a leaf of the tree. More...
mapped_reference	operator[] (key_const_reference r_key)
size_type	size () const
void	split (key_const_reference, PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)
void	swap (PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)
point_iterator	upper_bound (key_const_reference r_key)
point_const_iterator	upper_bound (key_const_reference r_key) const

Public Attributes
no_throw_indicator	m_no_throw_copies_indicator
store_extra	m_store_extra_indicator

Private Types
typedef traits_base::const_pointer	mapped_const_pointer_
typedef traits_base::pointer	mapped_pointer_
typedef _Alloc::template rebind< metadata_type >::other	metadata_allocator
typedef metadata_allocator::const_reference	metadata_const_reference
typedef metadata_allocator::pointer	metadata_pointer
typedef metadata_allocator::reference	metadata_reference
typedef traits_type::metadata_type	metadata_type
typedef remove_const< typename traits_base::value_type >::type	non_const_value_type
typedef traits_type::null_node_update_pointer	null_node_update_pointer
typedef types_traits< Key, Mapped, _Alloc, false >	traits_base
typedef Node_And_It_Traits	traits_type
typedef _Alloc::template rebind< non_const_value_type >::other	value_allocator
typedef value_allocator::pointer	value_vector

Private Member Functions
template<typename It >
void	copy_from_ordered_range (It, It)
template<typename It >
void	copy_from_ordered_range (It, It, It, It)
template<typename It >
It	erase_imp (It)
iterator	insert_new_val (iterator it, const_reference r_value)
node_const_iterator	PB_DS_node_begin_imp () const
node_iterator	PB_DS_node_begin_imp ()
node_const_iterator	PB_DS_node_end_imp () const
node_iterator	PB_DS_node_end_imp ()
void	reallocate_metadata (null_node_update_pointer, size_type)
template<typename Node_Update_ >
void	reallocate_metadata (Node_Update_ *, size_type)
void	update (node_iterator, null_node_update_pointer)
template<typename Node_Update >
void	update (node_iterator, Node_Update *)
void	value_swap (PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

Static Private Member Functions
template<typename Ptr >
static Ptr	mid_pointer (Ptr p_begin, Ptr p_end)

Private Attributes
metadata_pointer	m_a_metadata
value_vector	m_a_values
iterator	m_end_it
size_type	m_size

Static Private Attributes
static metadata_allocator	s_metadata_alloc
static value_allocator	s_value_alloc

Detailed Description

template<typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename _Alloc>
class __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >

Ordered-vector tree associative-container.

Member Typedef Documentation

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef _Alloc __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::allocator_type

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef Cmp_Fn __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::cmp_fn

typedef std::pair<size_type, size_type> __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::comp_hash

inherited

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef point_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::const_iterator

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::const_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::const_pointer

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::const_reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::const_reference

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef ov_tree_tag __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::container_category

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef _Alloc::difference_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::difference_type

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef point_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::iterator

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::key_const_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::key_const_pointer

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::key_const_reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::key_const_reference

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::key_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::key_pointer

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::key_reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::key_reference

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::key_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::key_type

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::mapped_const_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::mapped_const_pointer

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::const_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::mapped_const_pointer_

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::mapped_const_reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::mapped_const_reference

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::mapped_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::mapped_pointer

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::mapped_pointer_

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::mapped_reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::mapped_reference

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::mapped_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::mapped_type

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef _Alloc::template rebind<metadata_type>::other __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::metadata_allocator

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef metadata_allocator::const_reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::metadata_const_reference

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef metadata_allocator::pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::metadata_pointer

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef metadata_allocator::reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::metadata_reference

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_type::metadata_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::metadata_type

private

typedef __nothrowcopy::indicator __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::no_throw_indicator

inherited

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_type::node_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_const_iterator

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_type::node_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_iterator

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_type::node_update __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_update

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef remove_const<typename traits_base::value_type>::type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::non_const_value_type

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_type::null_node_update_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::null_node_update_pointer

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef const_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::point_const_iterator

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef point_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::point_iterator

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::pointer

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::reference

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef _Alloc::size_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::size_type

typedef integral_constant<int, Store_Hash> __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::store_extra

inherited

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef types_traits<Key, Mapped, _Alloc, false> __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::traits_base

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef Node_And_It_Traits __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::traits_type

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef _Alloc::template rebind<non_const_value_type>::other __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::value_allocator

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef traits_base::value_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::value_type

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

typedef value_allocator::pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::value_vector

private

Constructor & Destructor Documentation

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

__gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::PB_DS_OV_TREE_NAME

(

)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

__gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::PB_DS_OV_TREE_NAME

(

const Cmp_Fn &

)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

__gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::PB_DS_OV_TREE_NAME	(	const Cmp_Fn &	,
		const node_update &
	)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

__gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::PB_DS_OV_TREE_NAME

(

const PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &

)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

__gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::~PB_DS_OV_TREE_NAME

(

)

Member Function Documentation

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::begin ( )

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_a_values.

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val().

Here is the caller graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::begin ( ) const

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_a_values.

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::clear

(

)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

template<typename It >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::copy_from_ordered_range ( It  , It    )

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

template<typename It >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::copy_from_ordered_range ( It  , It  , It  , It    )

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

template<typename It >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::copy_from_range	(	It	,
		It
	)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

bool __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::empty ( ) const

inline

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::end ( )

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_end_it.

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::find(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::operator[](), and __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::upper_bound().

Here is the caller graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::end ( ) const

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_end_it.

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

bool __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::erase

(

key_const_reference

)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::erase ( iterator  it )

inline

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

template<typename Pred >

size_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::erase_if ( Pred  )

inline

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

template<typename It >

It __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::erase_imp ( It  )

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

point_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::find ( key_const_reference  r_key )

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::end(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::lower_bound(), PB_DS_ASSERT_VALID, PB_DS_CHECK_KEY_DOES_NOT_EXIST, PB_DS_CHECK_KEY_EXISTS, and PB_DS_V2F.

Here is the call graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

point_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::find ( key_const_reference  r_key ) const

inline

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

Cmp_Fn& __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::get_cmp_fn

(

)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

const Cmp_Fn& __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::get_cmp_fn

(

)

const

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

std::pair<point_iterator, bool> __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert ( const_reference  r_value )

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::end(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::lower_bound(), PB_DS_ASSERT_VALID, PB_DS_CHECK_KEY_EXISTS, and PB_DS_V2F.

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::operator[]().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val ( iterator  it, const_reference  r_value  )

inlineprivate

References _GLIBCXX_DEBUG_ONLY, __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::begin(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::end(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_a_values, __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_end_it, __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_size, __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin(), PB_DS_ASSERT_VALID, PB_DS_CHECK_KEY_DOES_NOT_EXIST, PB_DS_V2F, __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::reallocate_metadata(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::s_value_alloc, __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::cond_dtor< Size_Type >::set_no_action(), and __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::update().

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert(), and __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::operator[]().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::join

(

PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &

)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

point_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::lower_bound ( key_const_reference  r_key )

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_a_values, __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_size, and PB_DS_V2F.

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::find(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::operator[](), and __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::upper_bound().

Here is the caller graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

point_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::lower_bound ( key_const_reference  r_key ) const

inline

References PB_DS_CLASS_C_DEC.

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

size_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::max_size ( ) const

inline

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

template<typename Ptr >

static Ptr __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::mid_pointer ( Ptr  p_begin, Ptr  p_end  )

inlinestaticprivate

References _GLIBCXX_DEBUG_ASSERT.

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

node_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin ( ) const

inline

Returns a const node_iterator corresponding to the node at the root of the tree.

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val().

Here is the caller graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

node_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin ( )

inline

Returns a node_iterator corresponding to the node at the root of the tree.

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

node_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_end ( ) const

inline

Returns a const node_iterator corresponding to a node just after a leaf of the tree.

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

node_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_end ( )

inline

Returns a node_iterator corresponding to a node just after a leaf of the tree.

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

mapped_reference __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::operator[] ( key_const_reference  r_key )

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::end(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::lower_bound(), PB_DS_ASSERT_VALID, PB_DS_CHECK_KEY_EXISTS, and PB_DS_V2F.

Here is the call graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

node_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::PB_DS_node_begin_imp ( ) const

inlineprivate

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

node_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::PB_DS_node_begin_imp ( )

inlineprivate

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

node_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::PB_DS_node_end_imp ( ) const

inlineprivate

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

node_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::PB_DS_node_end_imp ( )

inlineprivate

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::reallocate_metadata ( null_node_update_pointer  , size_type    )

private

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val().

Here is the caller graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

template<typename Node_Update_ >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::reallocate_metadata ( Node_Update_ *  , size_type    )

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

size_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::size ( ) const

inline

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::split	(	key_const_reference	,
		PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &
	)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::swap

(

PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &

)

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::update ( node_iterator  , null_node_update_pointer    )

inlineprivate

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val().

Here is the caller graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

template<typename Node_Update >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::update ( node_iterator  , Node_Update *    )

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

point_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::upper_bound ( key_const_reference  r_key )

inline

References __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::end(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::lower_bound(), PB_DS_CHECK_KEY_DOES_NOT_EXIST, PB_DS_CHECK_KEY_EXISTS, and PB_DS_V2F.

Here is the call graph for this function:

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

point_const_iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::upper_bound ( key_const_reference  r_key ) const

inline

References PB_DS_CLASS_C_DEC.

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

void __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::value_swap ( PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &  )

private

Member Data Documentation

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

metadata_pointer __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_a_metadata

private

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

value_vector __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_a_values

private

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::begin(), __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val(), and __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::lower_bound().

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

iterator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_end_it

private

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::end(), and __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val().

no_throw_indicator __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::m_no_throw_copies_indicator

inherited

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

size_type __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::m_size

private

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val(), and __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::lower_bound().

store_extra __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::m_store_extra_indicator

inherited

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

metadata_allocator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::s_metadata_alloc

staticprivate

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc >

value_allocator __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::s_value_alloc

staticprivate

Referenced by __gnu_pbds::detail::PB_DS_OV_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::insert_new_val().

---

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

• /usr/include/c++/5/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp