Red-Black tree. More...

#include <rb_tree_.hpp>

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

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

Public Types
typedef _Alloc	allocator_type

typedef Cmp_Fn	cmp_fn

typedef base_type::const_iterator	const_iterator

typedef base_type::const_pointer	const_pointer

typedef base_type::const_reference	const_reference

typedef base_type::const_reverse_iterator	const_reverse_iterator

typedef rb_tree_tag	container_category

typedef _Alloc::difference_type	difference_type

typedef base_type::iterator	iterator

typedef base_type::key_const_pointer	key_const_pointer

typedef base_type::key_const_reference	key_const_reference

typedef base_type::key_pointer	key_pointer

typedef base_type::key_reference	key_reference

typedef base_type::key_type	key_type

typedef base_type::mapped_const_pointer	mapped_const_pointer

typedef base_type::mapped_const_reference	mapped_const_reference

typedef base_type::mapped_pointer	mapped_pointer

typedef base_type::mapped_reference	mapped_reference

typedef base_type::mapped_type	mapped_type

typedef base_type::node_update	node_update

typedef base_type::const_iterator	point_const_iterator

typedef base_type::point_iterator	point_iterator

typedef base_type::pointer	pointer

typedef base_type::reference	reference

typedef base_type::reverse_iterator	reverse_iterator

typedef _Alloc::size_type	size_type

typedef base_type::value_type	value_type

Public Member Functions
	PB_DS_RB_TREE_NAME ()

	PB_DS_RB_TREE_NAME (const Cmp_Fn &)

	PB_DS_RB_TREE_NAME (const Cmp_Fn &, const node_update &)

	PB_DS_RB_TREE_NAME (const PB_DS_RB_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

template<typename It >
void	copy_from_range (It, It)

bool	erase (key_const_reference)

iterator	erase (iterator)

reverse_iterator	erase (reverse_iterator)

template<typename Pred >
size_type	erase_if (Pred)

std::pair< point_iterator, bool >	insert (const_reference)

void	join (PB_DS_RB_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

mapped_reference	operator[] (key_const_reference r_key)

void	split (key_const_reference, PB_DS_RB_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

void	swap (PB_DS_RB_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

Private Types
typedef PB_DS_RB_TREE_BASE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >	base_type

typedef base_type::node_pointer	node_pointer

Private Member Functions
size_type	black_height (node_pointer)

void	erase_node (node_pointer)

std::pair< node_pointer, node_pointer >	find_join_pos_left (node_pointer, size_type, size_type)

std::pair< node_pointer, node_pointer >	find_join_pos_right (node_pointer, size_type, size_type)

void	initialize ()

void	insert_fixup (node_pointer)

void	join_imp (node_pointer, node_pointer)

void	remove_fixup (node_pointer, node_pointer)

void	remove_node (node_pointer)

void	split_at_node (node_pointer, PB_DS_RB_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

void	split_imp (node_pointer, PB_DS_RB_TREE_NAME< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

node_pointer	split_min ()

std::pair< node_pointer, node_pointer >	split_min_imp ()

Static Private Member Functions
static bool	is_effectively_black (const node_pointer)

Detailed Description

Red-Black tree.

This implementation uses an idea from the SGI STL (using a header node which is needed for efficient iteration).