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

Section: C Library Functions (3)
Updated: Wed Apr 17 2019
Page Index
 

NAME

__gnu_pbds::detail::rb_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > - Red-Black tree.

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

 

SYNOPSIS


Inherits __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >.  

Public Types


typedef _Alloc allocator_type

typedef Cmp_Fn cmp_fn

typedef std::pair< size_type, size_type > comp_hash

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 __nothrowcopy::indicator no_throw_indicator

typedef traits_type::node_const_iterator node_const_iterator

typedef traits_type::node_iterator node_iterator

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 integral_constant< int, Store_Hash > store_extra

typedef base_type::value_type value_type
 

Public Member Functions


rb_tree_map (const Cmp_Fn &)

rb_tree_map (const Cmp_Fn &, const node_update &)

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

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)

reverse_iterator erase (reverse_iterator)

template<typename Pred > size_type erase_if (Pred)

point_iterator find (key_const_reference)

point_const_iterator find (key_const_reference) const

Cmp_Fn & get_cmp_fn ()

const Cmp_Fn & get_cmp_fn () const

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

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

point_iterator lower_bound (key_const_reference)

point_const_iterator lower_bound (key_const_reference) 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.
node_iterator node_begin ()
Returns a node_iterator corresponding to the node at the root of the tree.
node_const_iterator node_end () const
Returns a const node_iterator corresponding to a node just after a leaf of the tree.
node_iterator node_end ()
Returns a node_iterator corresponding to a node just after a leaf of the tree.
mapped_reference operator[] (key_const_reference r_key)

reverse_iterator rbegin ()

const_reverse_iterator rbegin () const

reverse_iterator rend ()

const_reverse_iterator rend () const

size_type size () const

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

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

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

point_iterator upper_bound (key_const_reference)

point_const_iterator upper_bound (key_const_reference) const
 

Public Attributes


no_throw_indicator m_no_throw_copies_indicator

store_extra m_store_extra_indicator
 

Protected Types


typedef node_allocator::value_type node

typedef _Alloc::template rebind< typename traits_type::node >::other node_allocator

typedef traits_type::null_node_update_pointer null_node_update_pointer

typedef types_traits< Key, Mapped, _Alloc, false > traits_base
 

Protected Member Functions


void actual_erase_node (node_pointer)

void apply_update (node_pointer, null_node_update_pointer)

template<typename Node_Update_ > void apply_update (node_pointer, Node_Update_ *)

std::pair< node_pointer, bool > erase (node_pointer)

node_pointer get_new_node_for_leaf_insert (const_reference, false_type)

node_pointer get_new_node_for_leaf_insert (const_reference, true_type)

void initialize_min_max ()

iterator insert_imp_empty (const_reference)

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

iterator insert_leaf_new (const_reference, node_pointer, bool)

void join_finish (bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

bool join_prep (bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

size_type recursive_count (node_pointer) const

void rotate_left (node_pointer)

void rotate_parent (node_pointer)

void rotate_right (node_pointer)

void split_finish (bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

bool split_prep (key_const_reference, bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)

void update_min_max_for_erased_node (node_pointer)

void update_to_top (node_pointer, null_node_update_pointer)

template<typename Node_Update_ > void update_to_top (node_pointer, Node_Update_ *)

void value_swap (bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > &)
 

Static Protected Member Functions


static void clear_imp (node_pointer)
 

Protected Attributes


node_pointer m_p_head

size_type m_size
 

Static Protected Attributes


static node_allocator s_node_allocator
 

Detailed Description

 

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


class __gnu_pbds::detail::rb_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >" Red-Black tree.

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

Definition at line 84 of file rb_tree_.hpp.  

Member Function Documentation

 

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_const_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin () const [inline], [inherited]

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

Definition at line 109 of file bin_search_tree_.hpp.  

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin () [inline], [inherited]

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

Definition at line 117 of file bin_search_tree_.hpp.  

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_const_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_end () const [inline], [inherited]

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

Definition at line 125 of file bin_search_tree_.hpp.  

template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_end () [inline], [inherited]

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

Definition at line 133 of file bin_search_tree_.hpp.

 

Author

Generated automatically by Doxygen for libstdc++ from the source code.


 

Index

NAME
SYNOPSIS
Public Types
Public Member Functions
Public Attributes
Protected Types
Protected Member Functions
Static Protected Member Functions
Protected Attributes
Static Protected Attributes
Detailed Description
template<typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename _Alloc>
Member Function Documentation
template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_const_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin () const [inline], [inherited]
template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin () [inline], [inherited]
template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_const_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_end () const [inline], [inherited]
template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_end () [inline], [inherited]
Author