.TH "__gnu_cxx::rb_tree< _Key, _Value, _KeyOfValue, _Compare, _Alloc >" 3cxx "Wed Jul 28 2021" "libstdc++" \" -*- nroff -*-
.ad l
.nh
.SH NAME
__gnu_cxx::rb_tree< _Key, _Value, _KeyOfValue, _Compare, _Alloc >
.SH SYNOPSIS
.br
.PP
.PP
Inherits std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >\&.
.SS "Public Types"

.in +1c
.ti -1c
.RI "template<typename _Iter > using \fB__same_value_type\fP = is_same< value_type, typename iterator_traits< _Iter >::value_type >"
.br
.ti -1c
.RI "typedef std::_Rb_tree< _Key, _Value, _KeyOfValue, _Compare, _Alloc > \fB_Base\fP"
.br
.ti -1c
.RI "template<typename _Compare2 > using \fB_Compatible_tree\fP = _Rb_tree< _Key, _Val, _KeyOfValue, _Compare2, _Alloc >"
.br
.ti -1c
.RI "typedef _Base::allocator_type \fBallocator_type\fP"
.br
.ti -1c
.RI "typedef _Rb_tree_const_iterator< value_type > \fBconst_iterator\fP"
.br
.ti -1c
.RI "typedef const value_type * \fBconst_pointer\fP"
.br
.ti -1c
.RI "typedef const value_type & \fBconst_reference\fP"
.br
.ti -1c
.RI "typedef \fBstd::reverse_iterator\fP< const_iterator > \fBconst_reverse_iterator\fP"
.br
.ti -1c
.RI "typedef ptrdiff_t \fBdifference_type\fP"
.br
.ti -1c
.RI "using \fBinsert_return_type\fP = _Node_insert_return< conditional_t< is_same_v< _Key, _Val >, const_iterator, iterator >, \fBnode_type\fP >"
.br
.ti -1c
.RI "typedef _Rb_tree_iterator< value_type > \fBiterator\fP"
.br
.ti -1c
.RI "typedef _Key \fBkey_type\fP"
.br
.ti -1c
.RI "using \fBnode_type\fP = _Node_handle< _Key, _Val, _Node_allocator >"
.br
.ti -1c
.RI "typedef value_type * \fBpointer\fP"
.br
.ti -1c
.RI "typedef value_type & \fBreference\fP"
.br
.ti -1c
.RI "typedef \fBstd::reverse_iterator\fP< iterator > \fBreverse_iterator\fP"
.br
.ti -1c
.RI "typedef size_t \fBsize_type\fP"
.br
.ti -1c
.RI "typedef _Val \fBvalue_type\fP"
.br
.in -1c
.SS "Public Member Functions"

.in +1c
.ti -1c
.RI "\fBrb_tree\fP (const _Compare &__comp=_Compare(), const allocator_type &__a=allocator_type())"
.br
.ti -1c
.RI "bool \fB__rb_verify\fP () const"
.br
.ti -1c
.RI "template<typename _Iterator > void \fB_M_assign_equal\fP (_Iterator, _Iterator)"
.br
.ti -1c
.RI "template<typename _Iterator > void \fB_M_assign_unique\fP (_Iterator, _Iterator)"
.br
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> size_type \fB_M_count_tr\fP (const _Kt &__k) const"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> iterator \fB_M_emplace_equal\fP (_Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> iterator \fB_M_emplace_hint_equal\fP (const_iterator __pos, _Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> iterator \fB_M_emplace_hint_unique\fP (const_iterator __pos, _Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> \fBpair\fP< iterator, bool > \fB_M_emplace_unique\fP (_Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> \fBpair\fP< typename _Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::iterator, bool > \fB_M_emplace_unique\fP (_Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> \fBpair\fP< iterator, iterator > \fB_M_equal_range_tr\fP (const _Kt &__k)"
.br
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> \fBpair\fP< const_iterator, const_iterator > \fB_M_equal_range_tr\fP (const _Kt &__k) const"
.br
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> iterator \fB_M_find_tr\fP (const _Kt &__k)"
.br
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> const_iterator \fB_M_find_tr\fP (const _Kt &__k) const"
.br
.ti -1c
.RI "\fBpair\fP< _Base_ptr, _Base_ptr > \fB_M_get_insert_equal_pos\fP (const key_type &__k)"
.br
.ti -1c
.RI "\fBpair\fP< _Base_ptr, _Base_ptr > \fB_M_get_insert_hint_equal_pos\fP (const_iterator __pos, const key_type &__k)"
.br
.ti -1c
.RI "\fBpair\fP< _Base_ptr, _Base_ptr > \fB_M_get_insert_hint_unique_pos\fP (const_iterator __pos, const key_type &__k)"
.br
.ti -1c
.RI "\fBpair\fP< _Base_ptr, _Base_ptr > \fB_M_get_insert_unique_pos\fP (const key_type &__k)"
.br
.ti -1c
.RI "const _Node_allocator & \fB_M_get_Node_allocator\fP () const noexcept"
.br
.ti -1c
.RI "_Node_allocator & \fB_M_get_Node_allocator\fP () noexcept"
.br
.ti -1c
.RI "template<typename _Arg > iterator \fB_M_insert_equal\fP (_Arg &&__x)"
.br
.ti -1c
.RI "template<typename _Arg > iterator \fB_M_insert_equal_\fP (const_iterator __pos, _Arg &&__x)"
.br
.ti -1c
.RI "template<typename _Arg , typename _NodeGen > iterator \fB_M_insert_equal_\fP (const_iterator __pos, _Arg &&__x, _NodeGen &)"
.br
.ti -1c
.RI "template<typename _InputIterator > __enable_if_t< \fB__same_value_type\fP< _InputIterator >::value > \fB_M_insert_range_equal\fP (_InputIterator __first, _InputIterator __last)"
.br
.ti -1c
.RI "template<typename _InputIterator > __enable_if_t<!\fB__same_value_type\fP< _InputIterator >::value > \fB_M_insert_range_equal\fP (_InputIterator __first, _InputIterator __last)"
.br
.ti -1c
.RI "template<typename _InputIterator > __enable_if_t< \fB__same_value_type\fP< _InputIterator >::value > \fB_M_insert_range_unique\fP (_InputIterator __first, _InputIterator __last)"
.br
.ti -1c
.RI "template<typename _InputIterator > __enable_if_t<!\fB__same_value_type\fP< _InputIterator >::value > \fB_M_insert_range_unique\fP (_InputIterator __first, _InputIterator __last)"
.br
.ti -1c
.RI "template<typename _Arg > \fBpair\fP< typename _Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::iterator, bool > \fB_M_insert_unique\fP (_Arg &&__v)"
.br
.ti -1c
.RI "template<typename _Arg > \fBpair\fP< iterator, bool > \fB_M_insert_unique\fP (_Arg &&__x)"
.br
.ti -1c
.RI "template<typename _Arg > iterator \fB_M_insert_unique_\fP (const_iterator __pos, _Arg &&__x)"
.br
.ti -1c
.RI "template<typename _Arg , typename _NodeGen > iterator \fB_M_insert_unique_\fP (const_iterator __pos, _Arg &&__x, _NodeGen &)"
.br
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> iterator \fB_M_lower_bound_tr\fP (const _Kt &__k)"
.br
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> const_iterator \fB_M_lower_bound_tr\fP (const _Kt &__k) const"
.br
.ti -1c
.RI "template<typename _Compare2 > void \fB_M_merge_equal\fP (_Compatible_tree< _Compare2 > &__src) noexcept"
.br
.RI "Merge from a compatible container into one with equivalent keys\&. "
.ti -1c
.RI "template<typename _Compare2 > void \fB_M_merge_unique\fP (_Compatible_tree< _Compare2 > &__src) noexcept"
.br
.RI "Merge from a compatible container into one with unique keys\&. "
.ti -1c
.RI "iterator \fB_M_reinsert_node_equal\fP (\fBnode_type\fP &&__nh)"
.br
.RI "Re-insert an extracted node\&. "
.ti -1c
.RI "iterator \fB_M_reinsert_node_hint_equal\fP (const_iterator __hint, \fBnode_type\fP &&__nh)"
.br
.RI "Re-insert an extracted node\&. "
.ti -1c
.RI "iterator \fB_M_reinsert_node_hint_unique\fP (const_iterator __hint, \fBnode_type\fP &&__nh)"
.br
.RI "Re-insert an extracted node\&. "
.ti -1c
.RI "\fBinsert_return_type\fP \fB_M_reinsert_node_unique\fP (\fBnode_type\fP &&__nh)"
.br
.RI "Re-insert an extracted node\&. "
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> iterator \fB_M_upper_bound_tr\fP (const _Kt &__k)"
.br
.ti -1c
.RI "template<typename _Kt , typename _Req  = __has_is_transparent_t<_Compare, _Kt>> const_iterator \fB_M_upper_bound_tr\fP (const _Kt &__k) const"
.br
.ti -1c
.RI "const_iterator \fBbegin\fP () const noexcept"
.br
.ti -1c
.RI "iterator \fBbegin\fP () noexcept"
.br
.ti -1c
.RI "void \fBclear\fP () noexcept"
.br
.ti -1c
.RI "size_type \fBcount\fP (const key_type &__k) const"
.br
.ti -1c
.RI "bool \fBempty\fP () const noexcept"
.br
.ti -1c
.RI "const_iterator \fBend\fP () const noexcept"
.br
.ti -1c
.RI "iterator \fBend\fP () noexcept"
.br
.ti -1c
.RI "\fBpair\fP< iterator, iterator > \fBequal_range\fP (const key_type &__k)"
.br
.ti -1c
.RI "\fBpair\fP< const_iterator, const_iterator > \fBequal_range\fP (const key_type &__k) const"
.br
.ti -1c
.RI "size_type \fBerase\fP (const key_type &__x)"
.br
.ti -1c
.RI "_GLIBCXX_ABI_TAG_CXX11 iterator \fBerase\fP (const_iterator __first, const_iterator __last)"
.br
.ti -1c
.RI "_GLIBCXX_ABI_TAG_CXX11 iterator \fBerase\fP (const_iterator __position)"
.br
.ti -1c
.RI "_GLIBCXX_ABI_TAG_CXX11 iterator \fBerase\fP (iterator __position)"
.br
.ti -1c
.RI "\fBnode_type\fP \fBextract\fP (const key_type &__k)"
.br
.RI "Extract a node\&. "
.ti -1c
.RI "\fBnode_type\fP \fBextract\fP (const_iterator __pos)"
.br
.RI "Extract a node\&. "
.ti -1c
.RI "iterator \fBfind\fP (const key_type &__k)"
.br
.ti -1c
.RI "const_iterator \fBfind\fP (const key_type &__k) const"
.br
.ti -1c
.RI "allocator_type \fBget_allocator\fP () const noexcept"
.br
.ti -1c
.RI "_Compare \fBkey_comp\fP () const"
.br
.ti -1c
.RI "iterator \fBlower_bound\fP (const key_type &__k)"
.br
.ti -1c
.RI "const_iterator \fBlower_bound\fP (const key_type &__k) const"
.br
.ti -1c
.RI "size_type \fBmax_size\fP () const noexcept"
.br
.ti -1c
.RI "\fBconst_reverse_iterator\fP \fBrbegin\fP () const noexcept"
.br
.ti -1c
.RI "\fBreverse_iterator\fP \fBrbegin\fP () noexcept"
.br
.ti -1c
.RI "\fBconst_reverse_iterator\fP \fBrend\fP () const noexcept"
.br
.ti -1c
.RI "\fBreverse_iterator\fP \fBrend\fP () noexcept"
.br
.ti -1c
.RI "size_type \fBsize\fP () const noexcept"
.br
.ti -1c
.RI "void \fBswap\fP (_Rb_tree &__t) noexcept(/*conditional */)"
.br
.ti -1c
.RI "iterator \fBupper_bound\fP (const key_type &__k)"
.br
.ti -1c
.RI "const_iterator \fBupper_bound\fP (const key_type &__k) const"
.br
.in -1c
.SS "Protected Types"

.in +1c
.ti -1c
.RI "typedef _Rb_tree_node_base * \fB_Base_ptr\fP"
.br
.ti -1c
.RI "typedef const _Rb_tree_node_base * \fB_Const_Base_ptr\fP"
.br
.ti -1c
.RI "typedef const _Rb_tree_node< _Val > * \fB_Const_Link_type\fP"
.br
.ti -1c
.RI "typedef _Rb_tree_node< _Val > * \fB_Link_type\fP"
.br
.in -1c
.SS "Protected Member Functions"

.in +1c
.ti -1c
.RI "_Const_Link_type \fB_M_begin\fP () const noexcept"
.br
.ti -1c
.RI "_Link_type \fB_M_begin\fP () noexcept"
.br
.ti -1c
.RI "template<bool _MoveValue, typename _NodeGen > _Link_type \fB_M_clone_node\fP (_Link_type __x, _NodeGen &__node_gen)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> void \fB_M_construct_node\fP (_Link_type __node, _Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> _Link_type \fB_M_create_node\fP (_Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "void \fB_M_destroy_node\fP (_Link_type __p) noexcept"
.br
.ti -1c
.RI "void \fB_M_drop_node\fP (_Link_type __p) noexcept"
.br
.ti -1c
.RI "_Const_Base_ptr \fB_M_end\fP () const noexcept"
.br
.ti -1c
.RI "_Base_ptr \fB_M_end\fP () noexcept"
.br
.ti -1c
.RI "_Link_type \fB_M_get_node\fP ()"
.br
.ti -1c
.RI "_Const_Base_ptr \fB_M_leftmost\fP () const noexcept"
.br
.ti -1c
.RI "_Base_ptr & \fB_M_leftmost\fP () noexcept"
.br
.ti -1c
.RI "_Link_type \fB_M_mbegin\fP () const noexcept"
.br
.ti -1c
.RI "void \fB_M_put_node\fP (_Link_type __p) noexcept"
.br
.ti -1c
.RI "_Const_Base_ptr \fB_M_rightmost\fP () const noexcept"
.br
.ti -1c
.RI "_Base_ptr & \fB_M_rightmost\fP () noexcept"
.br
.ti -1c
.RI "_Const_Base_ptr \fB_M_root\fP () const noexcept"
.br
.ti -1c
.RI "_Base_ptr & \fB_M_root\fP () noexcept"
.br
.in -1c
.SS "Static Protected Member Functions"

.in +1c
.ti -1c
.RI "static const _Key & \fB_S_key\fP (_Const_Base_ptr __x)"
.br
.ti -1c
.RI "static const _Key & \fB_S_key\fP (_Const_Link_type __x)"
.br
.ti -1c
.RI "static _Link_type \fB_S_left\fP (_Base_ptr __x) noexcept"
.br
.ti -1c
.RI "static _Const_Link_type \fB_S_left\fP (_Const_Base_ptr __x) noexcept"
.br
.ti -1c
.RI "static _Base_ptr \fB_S_maximum\fP (_Base_ptr __x) noexcept"
.br
.ti -1c
.RI "static _Const_Base_ptr \fB_S_maximum\fP (_Const_Base_ptr __x) noexcept"
.br
.ti -1c
.RI "static _Base_ptr \fB_S_minimum\fP (_Base_ptr __x) noexcept"
.br
.ti -1c
.RI "static _Const_Base_ptr \fB_S_minimum\fP (_Const_Base_ptr __x) noexcept"
.br
.ti -1c
.RI "static _Link_type \fB_S_right\fP (_Base_ptr __x) noexcept"
.br
.ti -1c
.RI "static _Const_Link_type \fB_S_right\fP (_Const_Base_ptr __x) noexcept"
.br
.in -1c
.SS "Protected Attributes"

.in +1c
.ti -1c
.RI "_Rb_tree_impl< _Compare > \fB_M_impl\fP"
.br
.in -1c
.SH "Detailed Description"
.PP 

.SS "template<class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc = std::allocator<_Value>>
.br
struct __gnu_cxx::rb_tree< _Key, _Value, _KeyOfValue, _Compare, _Alloc >"
This is an SGI extension\&.
.PP
\fBTodo\fP
.RS 4
Needs documentation! See http://gcc.gnu.org/onlinedocs/libstdc++/manual/documentation_style.html 
.RE
.PP

.PP
Definition at line 77 of file rb_tree\&.
.SH "Member Function Documentation"
.PP 
.SS "template<typename _Key , typename _Val , typename _KeyOfValue , typename _Compare , typename _Alloc  = allocator<_Val>> template<typename _Compare2 > void std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_merge_equal (_Compatible_tree< _Compare2 > & __src)\fC [inline]\fP, \fC [noexcept]\fP, \fC [inherited]\fP"

.PP
Merge from a compatible container into one with equivalent keys\&. 
.PP
Definition at line 1583 of file stl_tree\&.h\&.
.SS "template<typename _Key , typename _Val , typename _KeyOfValue , typename _Compare , typename _Alloc  = allocator<_Val>> template<typename _Compare2 > void std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_merge_unique (_Compatible_tree< _Compare2 > & __src)\fC [inline]\fP, \fC [noexcept]\fP, \fC [inherited]\fP"

.PP
Merge from a compatible container into one with unique keys\&. 
.PP
Definition at line 1561 of file stl_tree\&.h\&.
.SS "template<typename _Key , typename _Val , typename _KeyOfValue , typename _Compare , typename _Alloc  = allocator<_Val>> iterator std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_reinsert_node_equal (\fBnode_type\fP && __nh)\fC [inline]\fP, \fC [inherited]\fP"

.PP
Re-insert an extracted node\&. 
.PP
Definition at line 1470 of file stl_tree\&.h\&.
.SS "template<typename _Key , typename _Val , typename _KeyOfValue , typename _Compare , typename _Alloc  = allocator<_Val>> iterator std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_reinsert_node_hint_equal (const_iterator __hint, \fBnode_type\fP && __nh)\fC [inline]\fP, \fC [inherited]\fP"

.PP
Re-insert an extracted node\&. 
.PP
Definition at line 1512 of file stl_tree\&.h\&.
.SS "template<typename _Key , typename _Val , typename _KeyOfValue , typename _Compare , typename _Alloc  = allocator<_Val>> iterator std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_reinsert_node_hint_unique (const_iterator __hint, \fBnode_type\fP && __nh)\fC [inline]\fP, \fC [inherited]\fP"

.PP
Re-insert an extracted node\&. 
.PP
Definition at line 1490 of file stl_tree\&.h\&.
.SS "template<typename _Key , typename _Val , typename _KeyOfValue , typename _Compare , typename _Alloc  = allocator<_Val>> \fBinsert_return_type\fP std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_reinsert_node_unique (\fBnode_type\fP && __nh)\fC [inline]\fP, \fC [inherited]\fP"

.PP
Re-insert an extracted node\&. 
.PP
Definition at line 1441 of file stl_tree\&.h\&.
.SS "template<typename _Key , typename _Val , typename _KeyOfValue , typename _Compare , typename _Alloc  = allocator<_Val>> \fBnode_type\fP std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::extract (const key_type & __k)\fC [inline]\fP, \fC [inherited]\fP"

.PP
Extract a node\&. 
.PP
Definition at line 1542 of file stl_tree\&.h\&.
.SS "template<typename _Key , typename _Val , typename _KeyOfValue , typename _Compare , typename _Alloc  = allocator<_Val>> \fBnode_type\fP std::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::extract (const_iterator __pos)\fC [inline]\fP, \fC [inherited]\fP"

.PP
Extract a node\&. 
.PP
Definition at line 1532 of file stl_tree\&.h\&.

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