.TH "__gnu_pbds::detail::rb_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >" 3cxx "libstdc++" \" -*- nroff -*-
.ad l
.nh
.SH NAME
__gnu_pbds::detail::rb_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc > \- Red-Black tree\&.  

.SH SYNOPSIS
.br
.PP
.PP
\fC#include <rb_tree_\&.hpp>\fP
.PP
Inherits __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >\&.
.SS "Public Types"

.in +1c
.ti -1c
.RI "typedef _Alloc \fBallocator_type\fP"
.br
.ti -1c
.RI "typedef Cmp_Fn \fBcmp_fn\fP"
.br
.ti -1c
.RI "typedef \fBstd::pair\fP< size_type, size_type > \fBcomp_hash\fP"
.br
.ti -1c
.RI "typedef base_type::const_iterator \fBconst_iterator\fP"
.br
.ti -1c
.RI "typedef base_type::const_pointer \fBconst_pointer\fP"
.br
.ti -1c
.RI "typedef base_type::const_reference \fBconst_reference\fP"
.br
.ti -1c
.RI "typedef base_type::const_reverse_iterator \fBconst_reverse_iterator\fP"
.br
.ti -1c
.RI "typedef \fBrb_tree_tag\fP \fBcontainer_category\fP"
.br
.ti -1c
.RI "typedef _Alloc::difference_type \fBdifference_type\fP"
.br
.ti -1c
.RI "typedef base_type::iterator \fBiterator\fP"
.br
.ti -1c
.RI "typedef base_type::key_const_pointer \fBkey_const_pointer\fP"
.br
.ti -1c
.RI "typedef base_type::key_const_reference \fBkey_const_reference\fP"
.br
.ti -1c
.RI "typedef base_type::key_pointer \fBkey_pointer\fP"
.br
.ti -1c
.RI "typedef base_type::key_reference \fBkey_reference\fP"
.br
.ti -1c
.RI "typedef base_type::key_type \fBkey_type\fP"
.br
.ti -1c
.RI "typedef base_type::mapped_const_pointer \fBmapped_const_pointer\fP"
.br
.ti -1c
.RI "typedef base_type::mapped_const_reference \fBmapped_const_reference\fP"
.br
.ti -1c
.RI "typedef base_type::mapped_pointer \fBmapped_pointer\fP"
.br
.ti -1c
.RI "typedef base_type::mapped_reference \fBmapped_reference\fP"
.br
.ti -1c
.RI "typedef base_type::mapped_type \fBmapped_type\fP"
.br
.ti -1c
.RI "typedef __nothrowcopy::indicator \fBno_throw_indicator\fP"
.br
.ti -1c
.RI "typedef traits_type::node_const_iterator \fBnode_const_iterator\fP"
.br
.ti -1c
.RI "typedef traits_type::node_iterator \fBnode_iterator\fP"
.br
.ti -1c
.RI "typedef base_type::node_update \fBnode_update\fP"
.br
.ti -1c
.RI "typedef base_type::const_iterator \fBpoint_const_iterator\fP"
.br
.ti -1c
.RI "typedef base_type::point_iterator \fBpoint_iterator\fP"
.br
.ti -1c
.RI "typedef base_type::pointer \fBpointer\fP"
.br
.ti -1c
.RI "typedef base_type::reference \fBreference\fP"
.br
.ti -1c
.RI "typedef base_type::reverse_iterator \fBreverse_iterator\fP"
.br
.ti -1c
.RI "typedef _Alloc::size_type \fBsize_type\fP"
.br
.ti -1c
.RI "typedef integral_constant< int, Store_Hash > \fBstore_extra\fP"
.br
.ti -1c
.RI "typedef \fBstored_data\fP< \fBvalue_type\fP, size_type, Store_Hash > \fBstored_data_type\fP"
.br
.ti -1c
.RI "typedef \fBbase_type::value_type\fP \fBvalue_type\fP"
.br
.in -1c
.SS "Public Member Functions"

.in +1c
.ti -1c
.RI "\fBrb_tree_map\fP (const Cmp_Fn &)"
.br
.ti -1c
.RI "\fBrb_tree_map\fP (const Cmp_Fn &, const node_update &)"
.br
.ti -1c
.RI "\fBrb_tree_map\fP (const \fBdirect_mask_range_hashing\fP< Size_Type > &)"
.br
.ti -1c
.RI "iterator \fBbegin\fP ()"
.br
.ti -1c
.RI "const_iterator \fBbegin\fP () const"
.br
.ti -1c
.RI "void \fBclear\fP ()"
.br
.ti -1c
.RI "template<typename It > void \fBcopy_from_range\fP (It, It)"
.br
.ti -1c
.RI "bool \fBempty\fP () const"
.br
.ti -1c
.RI "iterator \fBend\fP ()"
.br
.ti -1c
.RI "const_iterator \fBend\fP () const"
.br
.ti -1c
.RI "iterator \fBerase\fP (iterator)"
.br
.ti -1c
.RI "bool \fBerase\fP (key_const_reference)"
.br
.ti -1c
.RI "reverse_iterator \fBerase\fP (reverse_iterator)"
.br
.ti -1c
.RI "template<typename Pred > size_type \fBerase_if\fP (Pred)"
.br
.ti -1c
.RI "point_iterator \fBfind\fP (key_const_reference)"
.br
.ti -1c
.RI "point_const_iterator \fBfind\fP (key_const_reference) const"
.br
.ti -1c
.RI "Cmp_Fn & \fBget_cmp_fn\fP ()"
.br
.ti -1c
.RI "const Cmp_Fn & \fBget_cmp_fn\fP () const"
.br
.ti -1c
.RI "\fBstd::pair\fP< point_iterator, bool > \fBinsert\fP (const_reference)"
.br
.ti -1c
.RI "void \fBjoin\fP (\fBdirect_mask_range_hashing\fP< Size_Type > &)"
.br
.ti -1c
.RI "point_iterator \fBlower_bound\fP (key_const_reference)"
.br
.ti -1c
.RI "point_const_iterator \fBlower_bound\fP (key_const_reference) const"
.br
.ti -1c
.RI "size_type \fBmax_size\fP () const"
.br
.ti -1c
.RI "node_iterator \fBnode_begin\fP ()"
.br
.RI "Returns a node_iterator corresponding to the node at the root of the tree\&. "
.ti -1c
.RI "node_const_iterator \fBnode_begin\fP () const"
.br
.RI "Returns a const node_iterator corresponding to the node at the root of the tree\&. "
.ti -1c
.RI "node_iterator \fBnode_end\fP ()"
.br
.RI "Returns a node_iterator corresponding to a node just after a leaf of the tree\&. "
.ti -1c
.RI "node_const_iterator \fBnode_end\fP () const"
.br
.RI "Returns a const node_iterator corresponding to a node just after a leaf of the tree\&. "
.ti -1c
.RI "mapped_reference \fBoperator[]\fP (key_const_reference r_key)"
.br
.ti -1c
.RI "reverse_iterator \fBrbegin\fP ()"
.br
.ti -1c
.RI "const_reverse_iterator \fBrbegin\fP () const"
.br
.ti -1c
.RI "reverse_iterator \fBrend\fP ()"
.br
.ti -1c
.RI "const_reverse_iterator \fBrend\fP () const"
.br
.ti -1c
.RI "size_type \fBsize\fP () const"
.br
.ti -1c
.RI "void \fBsplit\fP (key_const_reference, \fBdirect_mask_range_hashing\fP< Size_Type > &)"
.br
.ti -1c
.RI "void \fBswap\fP (\fBdirect_mask_range_hashing\fP< Size_Type > &)"
.br
.ti -1c
.RI "void \fBswap\fP (\fBtree_order_statistics_node_update\fP< Node_CItr, Node_Itr, Cmp_Fn, _Alloc > &)"
.br
.ti -1c
.RI "point_iterator \fBupper_bound\fP (key_const_reference)"
.br
.ti -1c
.RI "point_const_iterator \fBupper_bound\fP (key_const_reference) const"
.br
.in -1c
.SS "Public Attributes"

.in +1c
.ti -1c
.RI "no_throw_indicator \fBm_no_throw_copies_indicator\fP"
.br
.ti -1c
.RI "store_extra \fBm_store_extra_indicator\fP"
.br
.in -1c
.SS "Protected Types"

.in +1c
.ti -1c
.RI "typedef node_alloc_traits::value_type \fBnode\fP"
.br
.ti -1c
.RI "typedef node_alloc_traits::allocator_type \fBnode_allocator\fP"
.br
.ti -1c
.RI "typedef traits_type::null_node_update_pointer \fBnull_node_update_pointer\fP"
.br
.ti -1c
.RI "typedef \fBtypes_traits\fP< Key, Mapped, _Alloc, false > \fBtraits_base\fP"
.br
.in -1c
.SS "Protected Member Functions"

.in +1c
.ti -1c
.RI "void \fBactual_erase_node\fP (node_pointer)"
.br
.ti -1c
.RI "template<typename Node_Update_ > void \fBapply_update\fP (node_pointer, Node_Update_ *)"
.br
.ti -1c
.RI "void \fBapply_update\fP (node_pointer, null_node_update_pointer)"
.br
.ti -1c
.RI "\fBstd::pair\fP< node_pointer, bool > \fBerase\fP (node_pointer)"
.br
.ti -1c
.RI "node_pointer \fBget_new_node_for_leaf_insert\fP (const_reference, false_type)"
.br
.ti -1c
.RI "node_pointer \fBget_new_node_for_leaf_insert\fP (const_reference, true_type)"
.br
.ti -1c
.RI "void \fBinitialize_min_max\fP ()"
.br
.ti -1c
.RI "iterator \fBinsert_imp_empty\fP (const_reference)"
.br
.ti -1c
.RI "\fBstd::pair\fP< point_iterator, bool > \fBinsert_leaf\fP (const_reference)"
.br
.ti -1c
.RI "iterator \fBinsert_leaf_new\fP (const_reference, node_pointer, bool)"
.br
.ti -1c
.RI "void \fBjoin_finish\fP (\fBtree_order_statistics_node_update\fP< Node_CItr, Node_Itr, Cmp_Fn, _Alloc > &)"
.br
.ti -1c
.RI "bool \fBjoin_prep\fP (\fBtree_order_statistics_node_update\fP< Node_CItr, Node_Itr, Cmp_Fn, _Alloc > &)"
.br
.ti -1c
.RI "size_type \fBrecursive_count\fP (node_pointer) const"
.br
.ti -1c
.RI "void \fBrotate_left\fP (node_pointer)"
.br
.ti -1c
.RI "void \fBrotate_parent\fP (node_pointer)"
.br
.ti -1c
.RI "void \fBrotate_right\fP (node_pointer)"
.br
.ti -1c
.RI "void \fBsplit_finish\fP (\fBtree_order_statistics_node_update\fP< Node_CItr, Node_Itr, Cmp_Fn, _Alloc > &)"
.br
.ti -1c
.RI "bool \fBsplit_prep\fP (key_const_reference, \fBtree_order_statistics_node_update\fP< Node_CItr, Node_Itr, Cmp_Fn, _Alloc > &)"
.br
.ti -1c
.RI "void \fBupdate_min_max_for_erased_node\fP (node_pointer)"
.br
.ti -1c
.RI "template<typename Node_Update_ > void \fBupdate_to_top\fP (node_pointer, Node_Update_ *)"
.br
.ti -1c
.RI "void \fBupdate_to_top\fP (node_pointer, null_node_update_pointer)"
.br
.ti -1c
.RI "void \fBvalue_swap\fP (\fBtree_order_statistics_node_update\fP< Node_CItr, Node_Itr, Cmp_Fn, _Alloc > &)"
.br
.in -1c
.SS "Static Protected Member Functions"

.in +1c
.ti -1c
.RI "static void \fBclear_imp\fP (node_pointer)"
.br
.in -1c
.SS "Protected Attributes"

.in +1c
.ti -1c
.RI "node_pointer \fBm_p_head\fP"
.br
.ti -1c
.RI "size_type \fBm_size\fP"
.br
.in -1c
.SS "Static Protected Attributes"

.in +1c
.ti -1c
.RI "static node_allocator \fBs_node_allocator\fP"
.br
.in -1c
.SH "Detailed Description"
.PP 

.SS "template<typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename _Alloc>
.br
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 \fIheader\fP node which is needed for efficient iteration)\&. 
.SH "Member Function Documentation"
.PP 
.SS "template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > node_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin ()\fC [inline]\fP, \fC [inherited]\fP"

.PP
Returns a node_iterator corresponding to the node at the root of the tree\&. 
.SS "template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > node_const_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_begin () const\fC [inline]\fP, \fC [inherited]\fP"

.PP
Returns a const node_iterator corresponding to the node at the root of the tree\&. 
.SS "template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > node_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_end ()\fC [inline]\fP, \fC [inherited]\fP"

.PP
Returns a node_iterator corresponding to a node just after a leaf of the tree\&. 
.SS "template<typename Key , typename Mapped , typename Cmp_Fn , typename Node_And_It_Traits , typename _Alloc > node_const_iterator __gnu_pbds::detail::bin_search_tree_map< Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc >::node_end () const\fC [inline]\fP, \fC [inherited]\fP"

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

.SH "Author"
.PP 
Generated automatically by Doxygen for libstdc++ from the source code\&.