ReactOS  0.4.13-dev-241-g63286c6
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, > Class Template Reference

#include <_tree.h>

Inheritance diagram for _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >:
Collaboration diagram for _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >:

Public Types

typedef _Key key_type
 
typedef _Value value_type
 
typedef _Traits::pointer pointer
 
typedef const value_typeconst_pointer
 
typedef _Traits::reference reference
 
typedef const value_typeconst_reference
 
typedef size_t size_type
 
typedef ptrdiff_t difference_type
 
typedef bidirectional_iterator_tag _Iterator_category
 
typedef _Base::allocator_type allocator_type
 
typedef _Traits::_NonConstTraits _NonConstTraits
 
typedef _Traits::_ConstTraits _ConstTraits
 
typedef _Rb_tree_iterator< value_type, _NonConstTraitsiterator
 
typedef _Rb_tree_iterator< value_type, _ConstTraitsconst_iterator
 
typedef _Base::key_type key_type
 
typedef _Traits::_NonConstTraits _NonConstIteTraits
 
typedef _Traits::_ConstTraits _ConstIteTraits
 
typedef _STLP_PRIV _DBG_iter< _Base, _STLP_PRIV _DbgTraits< _NonConstIteTraits > > iterator
 
typedef _STLP_PRIV _DBG_iter< _Base, _STLP_PRIV _DbgTraits< _ConstIteTraits > > const_iterator
 
- Public Types inherited from _Rb_tree_base< _Value, _Alloc >
typedef _Rb_tree_node_base _Node_base
 
typedef _Rb_tree_node< _Value_Node
 
typedef _Alloc allocator_type
 

Public Member Functions

 _Rb_tree ()
 
 _Rb_tree (const _Compare &__comp)
 
 _Rb_tree (const _Compare &__comp, const allocator_type &__a)
 
 _Rb_tree (const _Self &__x)
 
 _Rb_tree (__move_source< _Self > src)
 
 ~_Rb_tree ()
 
_Selfoperator= (const _Self &__x)
 
_Compare key_comp () const
 
iterator begin ()
 
const_iterator begin () const
 
iterator end ()
 
const_iterator end () const
 
reverse_iterator rbegin ()
 
const_reverse_iterator rbegin () const
 
reverse_iterator rend ()
 
const_reverse_iterator rend () const
 
bool empty () const
 
size_type size () const
 
size_type max_size () const
 
void swap (_Self &__t)
 
pair< iterator, boolinsert_unique (const value_type &__x)
 
iterator insert_equal (const value_type &__x)
 
iterator insert_unique (iterator __pos, const value_type &__x)
 
iterator insert_equal (iterator __pos, const value_type &__x)
 
void insert_unique (const_iterator __first, const_iterator __last)
 
void insert_unique (const value_type *__first, const value_type *__last)
 
void insert_equal (const_iterator __first, const_iterator __last)
 
void insert_equal (const value_type *__first, const value_type *__last)
 
void erase (iterator __pos)
 
size_type erase (const key_type &__x)
 
size_type erase_unique (const key_type &__x)
 
void erase (iterator __first, iterator __last)
 
void erase (const key_type *__first, const key_type *__last)
 
void clear ()
 
_STLP_TEMPLATE_FOR_CONT_EXT iterator find (const _KT &__k)
 
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find (const _KT &__k) const
 
_STLP_TEMPLATE_FOR_CONT_EXT size_type count (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator lower_bound (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator upper_bound (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iteratorequal_range (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iteratorequal_range (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iteratorequal_range_unique (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iteratorequal_range_unique (const _KT &__x) const
 
 _Rb_tree ()
 
 _Rb_tree (const _Compare &__comp)
 
 _Rb_tree (const _Compare &__comp, const allocator_type &__a)
 
 _Rb_tree (const _Self &__x)
 
 _Rb_tree (__move_source< _Self > src)
 
 ~_Rb_tree ()
 
_Selfoperator= (const _Self &__x)
 
allocator_type get_allocator () const
 
_Compare key_comp () const
 
iterator begin ()
 
const_iterator begin () const
 
iterator end ()
 
const_iterator end () const
 
reverse_iterator rbegin ()
 
const_reverse_iterator rbegin () const
 
reverse_iterator rend ()
 
const_reverse_iterator rend () const
 
bool empty () const
 
size_type size () const
 
size_type max_size () const
 
_STLP_TEMPLATE_FOR_CONT_EXT size_type count (const _KT &__x) const
 
void swap (_Self &__t)
 
_STLP_TEMPLATE_FOR_CONT_EXT iterator find (const _KT &__k)
 
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find (const _KT &__k) const
 
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator lower_bound (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator upper_bound (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iteratorequal_range (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iteratorequal_range (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iteratorequal_range_unique (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iteratorequal_range_unique (const _KT &__x) const
 
pair< iterator, boolinsert_unique (const value_type &__x)
 
iterator insert_equal (const value_type &__x)
 
iterator insert_unique (iterator __pos, const value_type &__x)
 
iterator insert_equal (iterator __pos, const value_type &__x)
 
void insert_unique (const_iterator __first, const_iterator __last)
 
void insert_unique (const value_type *__first, const value_type *__last)
 
void insert_equal (const_iterator __first, const_iterator __last)
 
void insert_equal (const value_type *__first, const value_type *__last)
 
void erase (iterator __pos)
 
size_type erase (const key_type &__x)
 
size_type erase_unique (const key_type &__x)
 
void erase (iterator __first, iterator __last)
 
void erase (const key_type *__first, const key_type *__last)
 
void clear ()
 
- Public Member Functions inherited from _Rb_tree_base< _Value, _Alloc >
allocator_type get_allocator () const
 

Public Attributes

 _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS
 

Protected Types

typedef _Rb_tree_node_base_Base_ptr
 
typedef _Rb_tree_node< _Value_Node
 
typedef _Node_Link_type
 
typedef _Rb_tree_Color_type _Color_type
 

Protected Member Functions

_Base_ptr _M_create_node (const value_type &__x)
 
_Base_ptr _M_clone_node (_Base_ptr __x)
 
_Base_ptr _M_root () const
 
_Base_ptr _M_leftmost () const
 
_Base_ptr _M_rightmost () const
 
_Base_ptr_M_root ()
 
_Base_ptr_M_leftmost ()
 
_Base_ptr_M_rightmost ()
 
- Protected Member Functions inherited from _Rb_tree_base< _Value, _Alloc >
 _Rb_tree_base (const allocator_type &__a)
 
 _Rb_tree_base (__move_source< _Self > src)
 
void _M_empty_initialize ()
 
void _M_rebind (_Node_base *__static_node)
 

Static Protected Member Functions

static _Base_ptr &_STLP_CALL _S_left (_Base_ptr __x)
 
static _Base_ptr &_STLP_CALL _S_right (_Base_ptr __x)
 
static _Base_ptr &_STLP_CALL _S_parent (_Base_ptr __x)
 
static value_type &_STLP_CALL _S_value (_Base_ptr __x)
 
static const _Key &_STLP_CALL _S_key (_Base_ptr __x)
 
static _Color_type &_STLP_CALL _S_color (_Base_ptr __x)
 
static _Base_ptr _STLP_CALL _S_minimum (_Base_ptr __x)
 
static _Base_ptr _STLP_CALL _S_maximum (_Base_ptr __x)
 

Protected Attributes

size_type _M_node_count
 
_Compare _M_key_compare
 
- Protected Attributes inherited from _Rb_tree_base< _Value, _Alloc >
_AllocProxy _M_header
 

Private Types

typedef _Rb_tree_base< _Value, _Alloc_Base
 
typedef _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc_Self
 
typedef _STLP_NON_DBG_TREE _Base
 
typedef _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc_Self
 
typedef _Base::iterator _Base_iterator
 
typedef _Base::const_iterator _Base_const_iterator
 

Private Member Functions

iterator _M_insert (_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
 
_Base_ptr _M_copy (_Base_ptr __x, _Base_ptr __p)
 
void _M_erase (_Base_ptr __x)
 
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_find (const _KT &__k) const
 
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_lower_bound (const _KT &__k) const
 
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_upper_bound (const _KT &__k) const
 
void _Invalidate_iterator (const iterator &__it)
 
void _Invalidate_iterators (const iterator &__first, const iterator &__last)
 

Private Attributes

_Base _M_non_dbg_impl
 
_STLP_PRIV __owned_list _M_iter_list
 

Detailed Description

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >)>
class _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >

Definition at line 292 of file _tree.h.

Member Typedef Documentation

◆ _Base [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _STLP_NON_DBG_TREE _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Base
private

Definition at line 94 of file _tree.h.

◆ _Base [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Rb_tree_base<_Value, _Alloc> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Base
private

Definition at line 293 of file _tree.h.

◆ _Base_const_iterator

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Base::const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Base_const_iterator
private

Definition at line 118 of file _tree.h.

◆ _Base_iterator

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Base::iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Base_iterator
private

Definition at line 117 of file _tree.h.

◆ _Base_ptr

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Rb_tree_node_base* _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Base_ptr
protected

Definition at line 296 of file _tree.h.

◆ _Color_type

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Rb_tree_Color_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Color_type
protected

Definition at line 299 of file _tree.h.

◆ _ConstIteTraits

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Traits::_ConstTraits _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_ConstIteTraits

Definition at line 104 of file _tree.h.

◆ _ConstTraits

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Traits::_ConstTraits _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_ConstTraits

Definition at line 370 of file _tree.h.

◆ _Iterator_category

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef bidirectional_iterator_tag _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Iterator_category

Definition at line 309 of file _tree.h.

◆ _Link_type

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Node* _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Link_type
protected

Definition at line 298 of file _tree.h.

◆ _Node

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Rb_tree_node<_Value> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Node
protected

Definition at line 297 of file _tree.h.

◆ _NonConstIteTraits

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Traits::_NonConstTraits _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_NonConstIteTraits

Definition at line 103 of file _tree.h.

◆ _NonConstTraits

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Traits::_NonConstTraits _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_NonConstTraits

Definition at line 369 of file _tree.h.

◆ _Self [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Self
private

Definition at line 95 of file _tree.h.

◆ _Self [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Self
private

Definition at line 294 of file _tree.h.

◆ allocator_type

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Base::allocator_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::allocator_type

Definition at line 310 of file _tree.h.

◆ const_iterator [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_ConstIteTraits> > _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::const_iterator

Definition at line 106 of file _tree.h.

◆ const_iterator [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Rb_tree_iterator<value_type, _ConstTraits> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::const_iterator

Definition at line 372 of file _tree.h.

◆ const_pointer

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef const value_type* _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::const_pointer

Definition at line 304 of file _tree.h.

◆ const_reference

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef const value_type& _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::const_reference

Definition at line 306 of file _tree.h.

◆ difference_type

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef ptrdiff_t _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::difference_type

Definition at line 308 of file _tree.h.

◆ iterator [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_NonConstIteTraits> > _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::iterator

Definition at line 105 of file _tree.h.

◆ iterator [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Rb_tree_iterator<value_type, _NonConstTraits> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::iterator

Definition at line 371 of file _tree.h.

◆ key_type [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Base::key_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::key_type

Definition at line 101 of file _tree.h.

◆ key_type [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Key _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::key_type

Definition at line 301 of file _tree.h.

◆ pointer

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Traits::pointer _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::pointer

Definition at line 303 of file _tree.h.

◆ reference

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Traits::reference _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::reference

Definition at line 305 of file _tree.h.

◆ size_type

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef size_t _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::size_type

Definition at line 307 of file _tree.h.

◆ value_type

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
typedef _Value _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::value_type

Definition at line 302 of file _tree.h.

Constructor & Destructor Documentation

◆ _Rb_tree() [1/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( )
inline

Definition at line 382 of file _tree.h.

384  {}
_Base::allocator_type allocator_type
Definition: _tree.h:310
size_type _M_node_count
Definition: _tree.h:332
_Compare _M_key_compare
Definition: _tree.h:333

◆ _Rb_tree() [2/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( const _Compare &  __comp)
inline

Definition at line 386 of file _tree.h.

388  {}
_Base::allocator_type allocator_type
Definition: _tree.h:310
size_type _M_node_count
Definition: _tree.h:332
_Compare _M_key_compare
Definition: _tree.h:333

◆ _Rb_tree() [3/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( const _Compare &  __comp,
const allocator_type __a 
)
inline

Definition at line 390 of file _tree.h.

392  {}
size_type _M_node_count
Definition: _tree.h:332
_Compare _M_key_compare
Definition: _tree.h:333

◆ _Rb_tree() [4/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( const _Self __x)
inline

Definition at line 394 of file _tree.h.

395  : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
396  _M_node_count(0), _M_key_compare(__x._M_key_compare) {
397  if (__x._M_root() != 0) {
399  _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
402  }
403  _M_node_count = __x._M_node_count;
404  }
_Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p)
Definition: _tree.c:624
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
static _Color_type &_STLP_CALL _S_color(_Base_ptr __x)
Definition: _tree.h:359
_Value _M_data
Definition: _alloc.h:478
size_type _M_node_count
Definition: _tree.h:332
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:365
_Base_ptr _M_root() const
Definition: _tree.h:335
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:362
#define _S_rb_tree_red
Definition: _tree.h:81
_Compare _M_key_compare
Definition: _tree.h:333

◆ _Rb_tree() [5/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( __move_source< _Self src)
inline

Definition at line 407 of file _tree.h.

409  _M_node_count(src.get()._M_node_count),
410  _M_key_compare(_AsMoveSource(src.get()._M_key_compare))
411  { src.get()._M_node_count = 0; }
size_type _M_node_count
Definition: _tree.h:332
_STLP_TYPENAME_ON_RETURN_TYPE _MoveSourceTraits< _Tp >::_Type _AsMoveSource(_Tp &src)
GLenum src
Definition: glext.h:6340
_Compare _M_key_compare
Definition: _tree.h:333

◆ ~_Rb_tree() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::~_Rb_tree ( )
inline

Definition at line 414 of file _tree.h.

414 { clear(); }
void clear()
Definition: _tree.h:530

◆ _Rb_tree() [6/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( )
inline

Definition at line 121 of file _tree.h.

_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97

◆ _Rb_tree() [7/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( const _Compare &  __comp)
inline

Definition at line 123 of file _tree.h.

_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97

◆ _Rb_tree() [8/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( const _Compare &  __comp,
const allocator_type __a 
)
inline

Definition at line 125 of file _tree.h.

126  : _M_non_dbg_impl(__comp, __a), _M_iter_list(&_M_non_dbg_impl) {}
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97

◆ _Rb_tree() [9/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( const _Self __x)
inline

Definition at line 127 of file _tree.h.

128  : _M_non_dbg_impl(__x._M_non_dbg_impl), _M_iter_list(&_M_non_dbg_impl) {}
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97

◆ _Rb_tree() [10/10]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree ( __move_source< _Self src)
inline

Definition at line 131 of file _tree.h.

131  :
132  _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)),
134 # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
135  src.get()._M_iter_list._Invalidate_all();
136 # else
137  src.get()._M_iter_list._Set_owner(_M_iter_list);
138 # endif
139  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
GLenum src
Definition: glext.h:6340

◆ ~_Rb_tree() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::~_Rb_tree ( )
inline

Definition at line 142 of file _tree.h.

142 {}

Member Function Documentation

◆ _Invalidate_iterator()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Invalidate_iterator ( const iterator __it)
inlineprivate

Definition at line 112 of file _tree.h.

113  { _STLP_PRIV __invalidate_iterator(&_M_iter_list,__it); }
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
#define _STLP_PRIV
Definition: _dm.h:70

◆ _Invalidate_iterators()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Invalidate_iterators ( const iterator __first,
const iterator __last 
)
inlineprivate

Definition at line 114 of file _tree.h.

115  { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
#define _STLP_PRIV
Definition: _dm.h:70

◆ _M_clone_node()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Base_ptr _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_clone_node ( _Base_ptr  __x)
inlineprotected

Definition at line 326 of file _tree.h.

326  {
327  _Base_ptr __tmp = _M_create_node(_S_value(__x));
328  _S_color(__tmp) = _S_color(__x);
329  return __tmp;
330  }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
static _Color_type &_STLP_CALL _S_color(_Base_ptr __x)
Definition: _tree.h:359
static value_type &_STLP_CALL _S_value(_Base_ptr __x)
Definition: _tree.h:355
_Base_ptr _M_create_node(const value_type &__x)
Definition: _tree.h:315

◆ _M_copy()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree_node_base * _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc >::_M_copy ( _Base_ptr  __x,
_Base_ptr  __p 
)
private

Definition at line 624 of file _tree.c.

625  {
626  // structural copy. __x and __p must be non-null.
627  _Base_ptr __top = _M_clone_node(__x);
628  _S_parent(__top) = __p;
629 
630  _STLP_TRY {
631  if (_S_right(__x))
632  _S_right(__top) = _M_copy(_S_right(__x), __top);
633  __p = __top;
634  __x = _S_left(__x);
635 
636  while (__x != 0) {
637  _Base_ptr __y = _M_clone_node(__x);
638  _S_left(__p) = __y;
639  _S_parent(__y) = __p;
640  if (_S_right(__x))
641  _S_right(__y) = _M_copy(_S_right(__x), __y);
642  __p = __y;
643  __x = _S_left(__x);
644  }
645  }
646  _STLP_UNWIND(_M_erase(__top))
647 
648  return __top;
649 }
_Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p)
Definition: _tree.c:624
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
#define _STLP_UNWIND(action)
Definition: features.h:824
static _Base_ptr &_STLP_CALL _S_parent(_Base_ptr __x)
Definition: _tree.h:353
#define _STLP_TRY
Definition: features.h:817
_Base_ptr _M_clone_node(_Base_ptr __x)
Definition: _tree.h:326
void _M_erase(_Base_ptr __x)
Definition: _tree.c:655

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_Rb_tree().

◆ _M_create_node()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Base_ptr _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_create_node ( const value_type __x)
inlineprotected

Definition at line 315 of file _tree.h.

315  {
316  _Link_type __tmp = this->_M_header.allocate(1);
317  _STLP_TRY {
318  _Copy_Construct(&__tmp->_M_value_field, __x);
319  }
320  _STLP_UNWIND(this->_M_header.deallocate(__tmp,1))
321  _S_left(__tmp) = 0;
322  _S_right(__tmp) = 0;
323  return __tmp;
324  }
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
_Tp * allocate(size_type __n, size_type &__allocated_n)
Definition: _alloc.h:525
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_Node * _Link_type
Definition: _tree.h:298
#define _STLP_UNWIND(action)
Definition: features.h:824
void _Copy_Construct(_Tp *__p, const _Tp &__val)
Definition: _construct.h:130
#define _STLP_TRY
Definition: features.h:817

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_clone_node().

◆ _M_erase()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc >::_M_erase ( _Base_ptr  __x)
private

Definition at line 655 of file _tree.c.

655  {
656  // erase without rebalancing
657  while (__x != 0) {
658  _M_erase(_S_right(__x));
659  _Base_ptr __y = _S_left(__x);
661  this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x),1);
662  __x = __y;
663  }
664 }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_Node * _Link_type
Definition: _tree.h:298
void _Destroy(_Tp *__pointer)
Definition: _construct.h:63
static value_type &_STLP_CALL _S_value(_Base_ptr __x)
Definition: _tree.h:355
void _M_erase(_Base_ptr __x)
Definition: _tree.c:655

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::clear().

◆ _M_find()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_find ( const _KT &  __k) const
inlineprivate

Definition at line 548 of file _tree.h.

548  {
549  _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); // Last node which is not less than __k.
550  _Base_ptr __x = _M_root(); // Current node.
551 
552  while (__x != 0)
553  if (!_M_key_compare(_S_key(__x), __k))
554  __y = __x, __x = _S_left(__x);
555  else
556  __x = _S_right(__x);
557 
558  if (__y != &this->_M_header._M_data) {
559  if (_M_key_compare(__k, _S_key(__y))) {
560  __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
561  }
562  }
563  return __y;
564  }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
_Value _M_data
Definition: _alloc.h:478
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_Base_ptr _M_root() const
Definition: _tree.h:335
#define __CONST_CAST(__x, __y)
Definition: features.h:584
_Compare _M_key_compare
Definition: _tree.h:333

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::find().

◆ _M_insert()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
__iterator__ _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc >::_M_insert ( _Base_ptr  __parent,
const value_type __val,
_Base_ptr  __on_left = 0,
_Base_ptr  __on_right = 0 
)
private

Definition at line 350 of file _tree.c.

353  {
354  // We do not create the node here as, depending on tests, we might call
355  // _M_key_compare that can throw an exception.
356  _Base_ptr __new_node;
357 
358  if ( __parent == &this->_M_header._M_data ) {
359  __new_node = _M_create_node(__val);
360  _S_left(__parent) = __new_node; // also makes _M_leftmost() = __new_node
361  _M_root() = __new_node;
362  _M_rightmost() = __new_node;
363  }
364  else if ( __on_right == 0 && // If __on_right != 0, the remainder fails to false
365  ( __on_left != 0 || // If __on_left != 0, the remainder succeeds to true
366  _M_key_compare( _KeyOfValue()(__val), _S_key(__parent) ) ) ) {
367  __new_node = _M_create_node(__val);
368  _S_left(__parent) = __new_node;
369  if (__parent == _M_leftmost())
370  _M_leftmost() = __new_node; // maintain _M_leftmost() pointing to min node
371  }
372  else {
373  __new_node = _M_create_node(__val);
374  _S_right(__parent) = __new_node;
375  if (__parent == _M_rightmost())
376  _M_rightmost() = __new_node; // maintain _M_rightmost() pointing to max node
377  }
378  _S_parent(__new_node) = __parent;
380  ++_M_node_count;
381  return iterator(__new_node);
382 }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
_Value _M_data
Definition: _alloc.h:478
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_Base_ptr _M_parent
Definition: _tree.h:89
size_type _M_node_count
Definition: _tree.h:332
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
static _Base_ptr &_STLP_CALL _S_parent(_Base_ptr __x)
Definition: _tree.h:353
_Base_ptr _M_root() const
Definition: _tree.h:335
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr &__root)
_Base_ptr _M_create_node(const value_type &__x)
Definition: _tree.h:315
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371
_Compare _M_key_compare
Definition: _tree.h:333

◆ _M_leftmost() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Base_ptr _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_leftmost ( ) const
inlineprotected

◆ _M_leftmost() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Base_ptr& _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_leftmost ( )
inlineprotected

Definition at line 344 of file _tree.h.

345  { return this->_M_header._M_data._M_left; }
_Value _M_data
Definition: _alloc.h:478
_Base_ptr _M_left
Definition: _tree.h:90

◆ _M_lower_bound()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_lower_bound ( const _KT &  __k) const
inlineprivate

Definition at line 567 of file _tree.h.

567  {
568  _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */
569  _Base_ptr __x = _M_root(); /* Current node. */
570 
571  while (__x != 0)
572  if (!_M_key_compare(_S_key(__x), __k))
573  __y = __x, __x = _S_left(__x);
574  else
575  __x = _S_right(__x);
576 
577  return __y;
578  }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
_Value _M_data
Definition: _alloc.h:478
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_Base_ptr _M_root() const
Definition: _tree.h:335
#define __CONST_CAST(__x, __y)
Definition: features.h:584
_Compare _M_key_compare
Definition: _tree.h:333

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::lower_bound().

◆ _M_rightmost() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Base_ptr _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_rightmost ( ) const
inlineprotected

◆ _M_rightmost() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Base_ptr& _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_rightmost ( )
inlineprotected

Definition at line 346 of file _tree.h.

347  { return this->_M_header._M_data._M_right; }
_Base_ptr _M_right
Definition: _tree.h:91
_Value _M_data
Definition: _alloc.h:478

◆ _M_root() [1/2]

◆ _M_root() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Base_ptr& _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_root ( )
inlineprotected

Definition at line 342 of file _tree.h.

343  { return this->_M_header._M_data._M_parent; }
_Value _M_data
Definition: _alloc.h:478
_Base_ptr _M_parent
Definition: _tree.h:89

◆ _M_upper_bound()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_upper_bound ( const _KT &  __k) const
inlineprivate

Definition at line 581 of file _tree.h.

581  {
582  _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */
583  _Base_ptr __x = _M_root(); /* Current node. */
584 
585  while (__x != 0)
586  if (_M_key_compare(__k, _S_key(__x)))
587  __y = __x, __x = _S_left(__x);
588  else
589  __x = _S_right(__x);
590 
591  return __y;
592  }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
_Value _M_data
Definition: _alloc.h:478
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_Base_ptr _M_root() const
Definition: _tree.h:335
#define __CONST_CAST(__x, __y)
Definition: features.h:584
_Compare _M_key_compare
Definition: _tree.h:333

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::upper_bound().

◆ _S_color()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
static _Color_type& _STLP_CALL _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_S_color ( _Base_ptr  __x)
inlinestaticprotected

◆ _S_key()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
static const _Key& _STLP_CALL _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_S_key ( _Base_ptr  __x)
inlinestaticprotected

◆ _S_left()

◆ _S_maximum()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
static _Base_ptr _STLP_CALL _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_S_maximum ( _Base_ptr  __x)
inlinestaticprotected

Definition at line 365 of file _tree.h.

366  { return _Rb_tree_node_base::_S_maximum(__x); }
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:98

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_Rb_tree().

◆ _S_minimum()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
static _Base_ptr _STLP_CALL _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_S_minimum ( _Base_ptr  __x)
inlinestaticprotected

Definition at line 362 of file _tree.h.

363  { return _Rb_tree_node_base::_S_minimum(__x); }
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:93

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_Rb_tree().

◆ _S_parent()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
static _Base_ptr& _STLP_CALL _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_S_parent ( _Base_ptr  __x)
inlinestaticprotected

Definition at line 353 of file _tree.h.

354  { return __x->_M_parent; }

◆ _S_right()

◆ _S_value()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
static value_type& _STLP_CALL _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_S_value ( _Base_ptr  __x)
inlinestaticprotected

◆ begin() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::begin ( )
inline

Definition at line 156 of file _tree.h.

156 { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ begin() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::begin ( ) const
inline

Definition at line 157 of file _tree.h.

157 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ begin() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::begin ( )
inline

Definition at line 421 of file _tree.h.

421 { return iterator(_M_leftmost()); }
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::rend().

◆ begin() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::begin ( ) const
inline

Definition at line 422 of file _tree.h.

422 { return const_iterator(_M_leftmost()); }
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ clear() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::clear ( void  )
inline

Definition at line 301 of file _tree.h.

301  {
302  //should not invalidate end:
304  _M_non_dbg_impl.clear();
305  }
void _Invalidate_iterators(const iterator &__first, const iterator &__last)
Definition: _tree.h:114
iterator end()
Definition: _tree.h:423
iterator begin()
Definition: _tree.h:421
_Base _M_non_dbg_impl
Definition: _tree.h:96

◆ clear() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::clear ( void  )
inline

Definition at line 530 of file _tree.h.

530  {
531  if (_M_node_count != 0) {
532  _M_erase(_M_root());
533  _M_leftmost() = &this->_M_header._M_data;
534  _M_root() = 0;
535  _M_rightmost() = &this->_M_header._M_data;
536  _M_node_count = 0;
537  }
538  }
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
_Value _M_data
Definition: _alloc.h:478
size_type _M_node_count
Definition: _tree.h:332
_Base_ptr _M_root() const
Definition: _tree.h:335
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
void _M_erase(_Base_ptr __x)
Definition: _tree.c:655

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::erase(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::~_Rb_tree().

◆ count() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::count ( const _KT &  __x) const
inline

Definition at line 170 of file _tree.h.

170 { return _M_non_dbg_impl.count(__x); }
_Base _M_non_dbg_impl
Definition: _tree.h:96

◆ count() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::count ( const _KT &  __x) const
inline

Definition at line 596 of file _tree.h.

596  {
598  return _STLP_STD::distance(__p.first, __p.second);
599  }
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
_T1 first
Definition: _pair.h:51
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__x)
Definition: _tree.h:609
Definition: _pair.h:47
_T2 second
Definition: _pair.h:52

◆ empty() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
bool _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::empty ( ) const
inline

Definition at line 166 of file _tree.h.

166 { return _M_non_dbg_impl.empty(); }
_Base _M_non_dbg_impl
Definition: _tree.h:96

◆ empty() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
bool _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::empty ( ) const
inline

◆ end() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::end ( )
inline

Definition at line 158 of file _tree.h.

158 { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ end() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::end ( ) const
inline

Definition at line 159 of file _tree.h.

159 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ end() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::end ( )
inline

Definition at line 423 of file _tree.h.

423 { return iterator(&this->_M_header._M_data); }
_Value _M_data
Definition: _alloc.h:478
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::rbegin().

◆ end() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::end ( ) const
inline

Definition at line 424 of file _tree.h.

_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
_Value _M_data
Definition: _alloc.h:478
#define __CONST_CAST(__x, __y)
Definition: features.h:584
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ equal_range() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT pair<iterator,iterator> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range ( const _KT &  __x)
inline

Definition at line 199 of file _tree.h.

199  {
201  iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)));
202  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
Definition: _pair.h:47
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ equal_range() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT pair<const_iterator, const_iterator> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range ( const _KT &  __x) const
inline

Definition at line 204 of file _tree.h.

204  {
206  const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)));
207  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
Definition: _pair.h:47
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ equal_range() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT pair<iterator,iterator> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range ( const _KT &  __x)
inline

Definition at line 609 of file _tree.h.

610  { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); }
_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound(const _KT &__x)
Definition: _tree.h:605
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)
Definition: _tree.h:601
Definition: _pair.h:47

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::count(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::erase().

◆ equal_range() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT pair<const_iterator, const_iterator> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range ( const _KT &  __x) const
inline

Definition at line 612 of file _tree.h.

_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound(const _KT &__x)
Definition: _tree.h:605
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)
Definition: _tree.h:601
Definition: _pair.h:47

◆ equal_range_unique() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT pair<iterator,iterator> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range_unique ( const _KT &  __x)
inline

Definition at line 210 of file _tree.h.

210  {
211  _STLP_STD::pair<_Base_iterator, _Base_iterator> __p;
212  __p = _M_non_dbg_impl.equal_range_unique(__x);
213  return pair<iterator, iterator>(iterator(&_M_iter_list, __p.first), iterator(&_M_iter_list, __p.second));
214  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
Definition: _pair.h:47
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ equal_range_unique() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT pair<const_iterator, const_iterator> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range_unique ( const _KT &  __x) const
inline

Definition at line 216 of file _tree.h.

216  {
217  _STLP_STD::pair<_Base_const_iterator, _Base_const_iterator> __p;
218  __p = _M_non_dbg_impl.equal_range_unique(__x);
220  const_iterator(&_M_iter_list, __p.second));
221  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
Definition: _pair.h:47
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ equal_range_unique() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT pair<iterator,iterator> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range_unique ( const _KT &  __x)
inline

Definition at line 615 of file _tree.h.

615  {
617  __p.second = lower_bound(__x);
618  if (__p.second._M_node != &this->_M_header._M_data &&
619  !_M_key_compare(__x, _S_key(__p.second._M_node))) {
620  __p.first = __p.second++;
621  }
622  else {
623  __p.first = __p.second;
624  }
625  return __p;
626  }
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)
Definition: _tree.h:601
_Base_ptr _M_node
Definition: _tree.h:140
_T1 first
Definition: _pair.h:51
Definition: _pair.h:47
_T2 second
Definition: _pair.h:52
_Compare _M_key_compare
Definition: _tree.h:333

◆ equal_range_unique() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT pair<const_iterator, const_iterator> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range_unique ( const _KT &  __x) const
inline

Definition at line 628 of file _tree.h.

628  {
630  __p.second = lower_bound(__x);
631  if (__p.second._M_node != &this->_M_header._M_data &&
632  !_M_key_compare(__x, _S_key(__p.second._M_node))) {
633  __p.first = __p.second++;
634  }
635  else {
636  __p.first = __p.second;
637  }
638  return __p;
639  }
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)
Definition: _tree.h:601
_Base_ptr _M_node
Definition: _tree.h:140
_T1 first
Definition: _pair.h:51
Definition: _pair.h:47
_T2 second
Definition: _pair.h:52
_Compare _M_key_compare
Definition: _tree.h:333

◆ erase() [1/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase ( iterator  __pos)
inline

Definition at line 269 of file _tree.h.

269  {
270  _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos))
272  _Invalidate_iterator(__pos);
273  _M_non_dbg_impl.erase(__pos._M_iterator);
274  }
bool _Dereferenceable(const _Iterator &__it)
Definition: _iterator.h:93
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
void _Invalidate_iterator(const iterator &__it)
Definition: _tree.h:112
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440

◆ erase() [2/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase ( const key_type __x)
inline

Definition at line 275 of file _tree.h.

275  {
277  size_type __n = _STLP_STD::distance(__p.first._M_iterator, __p.second._M_iterator);
279  _M_non_dbg_impl.erase(__p.first._M_iterator, __p.second._M_iterator);
280  return __n;
281  }
void _Invalidate_iterators(const iterator &__first, const iterator &__last)
Definition: _tree.h:114
return __n
Definition: _algo.h:75
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
_Base _M_non_dbg_impl
Definition: _tree.h:96
_T1 first
Definition: _pair.h:51
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__x)
Definition: _tree.h:609
Definition: _pair.h:47
_T2 second
Definition: _pair.h:52
size_t size_type
Definition: _tree.h:307

◆ erase() [3/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase ( iterator  __first,
iterator  __last 
)
inline

Definition at line 292 of file _tree.h.

292  {
293  _STLP_DEBUG_CHECK(__check_range(__first, __last, begin(), end()))
294  _Invalidate_iterators(__first, __last);
295  _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator);
296  }
void _Invalidate_iterators(const iterator &__first, const iterator &__last)
Definition: _tree.h:114
iterator end()
Definition: _tree.h:423
iterator begin()
Definition: _tree.h:421
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Base _M_non_dbg_impl
Definition: _tree.h:96
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
void erase(iterator __pos)
Definition: _tree.h:492

◆ erase() [4/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase ( const key_type __first,
const key_type __last 
)
inline

Definition at line 297 of file _tree.h.

297  {
298  while (__first != __last) erase(*__first++);
299  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void erase(iterator __pos)
Definition: _tree.h:492

◆ erase() [5/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase ( iterator  __pos)
inline

Definition at line 492 of file _tree.h.

492  {
494  this->_M_header._M_data._M_parent,
495  this->_M_header._M_data._M_left,
496  this->_M_header._M_data._M_right);
498  this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
499  --_M_node_count;
500  }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
_Node * _Link_type
Definition: _tree.h:298
static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z, _Base_ptr &__root, _Base_ptr &__leftmost, _Base_ptr &__rightmost)
size_type _M_node_count
Definition: _tree.h:332
void _Destroy(_Tp *__pointer)
Definition: _construct.h:63
static value_type &_STLP_CALL _S_value(_Base_ptr __x)
Definition: _tree.h:355

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::erase(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::erase_unique().

◆ erase() [6/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase ( const key_type __x)
inline

Definition at line 502 of file _tree.h.

502  {
505  erase(__p.first, __p.second);
506  return __n;
507  }
return __n
Definition: _algo.h:75
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
_T1 first
Definition: _pair.h:51
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__x)
Definition: _tree.h:609
void erase(iterator __pos)
Definition: _tree.h:492
Definition: _pair.h:47
_T2 second
Definition: _pair.h:52
size_t size_type
Definition: _tree.h:307

◆ erase() [7/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase ( iterator  __first,
iterator  __last 
)
inline

Definition at line 518 of file _tree.h.

518  {
519  if (__first._M_node == this->_M_header._M_data._M_left && // begin()
520  __last._M_node == &this->_M_header._M_data) // end()
521  clear();
522  else
523  while (__first != __last) erase(__first++);
524  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void erase(iterator __pos)
Definition: _tree.h:492
void clear()
Definition: _tree.h:530

◆ erase() [8/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase ( const key_type __first,
const key_type __last 
)
inline

Definition at line 526 of file _tree.h.

526  {
527  while (__first != __last) erase(*__first++);
528  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void erase(iterator __pos)
Definition: _tree.h:492

◆ erase_unique() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase_unique ( const key_type __x)
inline

Definition at line 282 of file _tree.h.

282  {
283  _Base_iterator __i = _M_non_dbg_impl.find(__x);
284  if (__i != _M_non_dbg_impl.end()) {
286  _M_non_dbg_impl.erase(__i);
287  return 1;
288  }
289  return 0;
290  }
_Base::iterator _Base_iterator
Definition: _tree.h:117
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
void _Invalidate_iterator(const iterator &__it)
Definition: _tree.h:112
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ erase_unique() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase_unique ( const key_type __x)
inline

Definition at line 509 of file _tree.h.

509  {
510  iterator __i = find(__x);
511  if (__i._M_node != &this->_M_header._M_data) {
512  erase(__i);
513  return 1;
514  }
515  return 0;
516  }
void erase(iterator __pos)
Definition: _tree.h:492
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__k)
Definition: _tree.h:543

◆ find() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::find ( const _KT &  __k)
inline

Definition at line 178 of file _tree.h.

179  { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ find() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::find ( const _KT &  __k) const
inline

Definition at line 181 of file _tree.h.

182  { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ find() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::find ( const _KT &  __k)
inline

Definition at line 543 of file _tree.h.

543 { return iterator(_M_find(__k)); }
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_find(const _KT &__k) const
Definition: _tree.h:548
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::erase_unique().

◆ find() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::find ( const _KT &  __k) const
inline

Definition at line 545 of file _tree.h.

545 { return const_iterator(_M_find(__k)); }
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_find(const _KT &__k) const
Definition: _tree.h:548
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ get_allocator()

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
allocator_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::get_allocator ( ) const
inline

Definition at line 153 of file _tree.h.

153 { return _M_non_dbg_impl.get_allocator(); }
allocator_type get_allocator() const
Definition: _tree.h:244
_Base _M_non_dbg_impl
Definition: _tree.h:96

◆ insert_equal() [1/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_equal ( const value_type __x)
inline

Definition at line 227 of file _tree.h.

228  { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__x)); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ insert_equal() [2/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_equal ( iterator  __pos,
const value_type __x 
)
inline

Definition at line 234 of file _tree.h.

234  {
235  _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list, __pos))
236  return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__pos._M_iterator, __x));
237  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ insert_equal() [3/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_equal ( const_iterator  __first,
const_iterator  __last 
)
inline

Definition at line 259 of file _tree.h.

259  {
260  _STLP_DEBUG_CHECK(__check_range(__first,__last))
261  _M_non_dbg_impl.insert_equal(__first._M_iterator, __last._M_iterator);
262  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Base _M_non_dbg_impl
Definition: _tree.h:96
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440

◆ insert_equal() [4/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_equal ( const value_type __first,
const value_type __last 
)
inline

Definition at line 263 of file _tree.h.

263  {
264  _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last))
265  _M_non_dbg_impl.insert_equal(__first, __last);
266  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Base _M_non_dbg_impl
Definition: _tree.h:96
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440

◆ insert_equal() [5/8]

template<class _Key , class _Compare , class _Value , class _KeyOfValue , class _Traits , class _Alloc >
__iterator__ _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc >::insert_equal ( const value_type __x)

Definition at line 387 of file _tree.c.

387  {
388  _Base_ptr __y = &this->_M_header._M_data;
389  _Base_ptr __x = _M_root();
390  while (__x != 0) {
391  __y = __x;
392  if (_M_key_compare(_KeyOfValue()(__val), _S_key(__x))) {
393  __x = _S_left(__x);
394  }
395  else
396  __x = _S_right(__x);
397  }
398  return _M_insert(__y, __val, __x);
399 }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
iterator _M_insert(_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
Definition: _tree.c:350
_Value _M_data
Definition: _alloc.h:478
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
_Base_ptr _M_root() const
Definition: _tree.h:335
_Compare _M_key_compare
Definition: _tree.h:333

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::insert_equal().

◆ insert_equal() [6/8]

template<class _Key , class _Compare , class _Value , class _KeyOfValue , class _Traits , class _Alloc >
__iterator__ _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc >::insert_equal ( iterator  __pos,
const value_type __x 
)

Definition at line 539 of file _tree.c.

540  {
541  if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
542 
543  // Check for zero members
544  if (size() <= 0)
545  return insert_equal(__val);
546 
547  if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val)))
548  return _M_insert(__position._M_node, __val, __position._M_node);
549  else {
550  // Check for only one member
551  if (__position._M_node->_M_left == __position._M_node)
552  // Unlike insert_unique, can't avoid doing a comparison here.
553  return _M_insert(__position._M_node, __val);
554 
555  // All other cases:
556  // Standard-conformance - does the insertion point fall immediately AFTER
557  // the hint?
558  iterator __after = __position;
559  ++__after;
560 
561  // Already know that compare(pos, v) must be true!
562  // Therefore, we want to know if compare(after, v) is false.
563  // (i.e., we now pos < v, now we want to know if v <= after)
564  // If not, invalid hint.
565  if ( __after._M_node == &this->_M_header._M_data ||
566  !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) {
567  if (_S_right(__position._M_node) == 0)
568  return _M_insert(__position._M_node, __val, 0, __position._M_node);
569  else
570  return _M_insert(__after._M_node, __val, __after._M_node);
571  }
572  else { // Invalid hint
573  return insert_equal(__val);
574  }
575  }
576  }
577  else if (__position._M_node == &this->_M_header._M_data) { // end()
578  if (!_M_key_compare(_KeyOfValue()(__val), _S_key(_M_rightmost())))
579  return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
580  else {
581  return insert_equal(__val);
582  }
583  }
584  else {
585  iterator __before = __position;
586  --__before;
587  // store the result of the comparison between pos and v so
588  // that we don't have to do it again later. Note that this reverses the shortcut
589  // on the if, possibly harming efficiency in comparisons; I think the harm will
590  // be negligible, and to do what I want to do (save the result of a comparison so
591  // that it can be re-used) there is no alternative. Test here is for before <= v <= pos.
592  bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
593  if (!__comp_pos_v &&
594  !_M_key_compare(_KeyOfValue()(__val), _S_key(__before._M_node))) {
595  if (_S_right(__before._M_node) == 0)
596  return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
597  else
598  return _M_insert(__position._M_node, __val, __position._M_node);
599  }
600  else {
601  // Does the insertion point fall immediately AFTER the hint?
602  // Test for pos < v <= after
603  iterator __after = __position;
604  ++__after;
605 
606  if (__comp_pos_v &&
607  ( __after._M_node == &this->_M_header._M_data ||
608  !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) ) {
609  if (_S_right(__position._M_node) == 0)
610  return _M_insert(__position._M_node, __val, 0, __position._M_node);
611  else
612  return _M_insert(__after._M_node, __val, __after._M_node);
613  }
614  else { // Invalid hint
615  return insert_equal(__val);
616  }
617  }
618  }
619 }
size_type size() const
Definition: _tree.h:433
iterator insert_equal(const value_type &__x)
Definition: _tree.c:387
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
iterator _M_insert(_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
Definition: _tree.c:350
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
_Compare _M_key_compare
Definition: _tree.h:333

◆ insert_equal() [7/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_equal ( const_iterator  __first,
const_iterator  __last 
)
inline

Definition at line 482 of file _tree.h.

482  {
483  for ( ; __first != __last; ++__first)
484  insert_equal(*__first);
485  }
iterator insert_equal(const value_type &__x)
Definition: _tree.c:387
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68

◆ insert_equal() [8/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_equal ( const value_type __first,
const value_type __last 
)
inline

Definition at line 486 of file _tree.h.

486  {
487  for ( ; __first != __last; ++__first)
488  insert_equal(*__first);
489  }
iterator insert_equal(const value_type &__x)
Definition: _tree.c:387
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68

◆ insert_unique() [1/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
pair<iterator,bool> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_unique ( const value_type __x)
inline

Definition at line 223 of file _tree.h.

223  {
224  _STLP_STD::pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__x);
225  return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
226  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
Definition: _pair.h:47
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ insert_unique() [2/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_unique ( iterator  __pos,
const value_type __x 
)
inline

Definition at line 230 of file _tree.h.

230  {
231  _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos))
232  return iterator(&_M_iter_list, _M_non_dbg_impl.insert_unique(__pos._M_iterator, __x));
233  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ insert_unique() [3/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_unique ( const_iterator  __first,
const_iterator  __last 
)
inline

Definition at line 251 of file _tree.h.

251  {
252  _STLP_DEBUG_CHECK(__check_range(__first,__last))
253  _M_non_dbg_impl.insert_unique(__first._M_iterator, __last._M_iterator);
254  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Base _M_non_dbg_impl
Definition: _tree.h:96
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440

◆ insert_unique() [4/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_unique ( const value_type __first,
const value_type __last 
)
inline

Definition at line 255 of file _tree.h.

255  {
256  _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last))
257  _M_non_dbg_impl.insert_unique(__first, __last);
258  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Base _M_non_dbg_impl
Definition: _tree.h:96
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440

◆ insert_unique() [5/8]

template<class _Key , class _Compare , class _Value , class _KeyOfValue , class _Traits , class _Alloc >
pair< __iterator__, bool > _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc >::insert_unique ( const value_type __x)

Definition at line 405 of file _tree.c.

405  {
406  _Base_ptr __y = &this->_M_header._M_data;
407  _Base_ptr __x = _M_root();
408  bool __comp = true;
409  while (__x != 0) {
410  __y = __x;
411  __comp = _M_key_compare(_KeyOfValue()(__val), _S_key(__x));
412  __x = __comp ? _S_left(__x) : _S_right(__x);
413  }
414  iterator __j = iterator(__y);
415  if (__comp) {
416  if (__j == begin())
417  return pair<iterator,bool>(_M_insert(__y, __val, /* __x*/ __y), true);
418  else
419  --__j;
420  }
421  if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__val))) {
422  return pair<iterator,bool>(_M_insert(__y, __val, __x), true);
423  }
424  return pair<iterator,bool>(__j, false);
425 }
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
iterator _M_insert(_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
Definition: _tree.c:350
_Value _M_data
Definition: _alloc.h:478
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
iterator begin()
Definition: _tree.h:421
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
_Base_ptr _M_root() const
Definition: _tree.h:335
Definition: _pair.h:47
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371
_Compare _M_key_compare
Definition: _tree.h:333

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::insert_unique().

◆ insert_unique() [6/8]

template<class _Key , class _Compare , class _Value , class _KeyOfValue , class _Traits , class _Alloc >
__iterator__ _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc >::insert_unique ( iterator  __pos,
const value_type __x 
)

Definition at line 432 of file _tree.c.

433  {
434  if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
435 
436  // if the container is empty, fall back on insert_unique.
437  if (empty())
438  return insert_unique(__val).first;
439 
440  if (_M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node))) {
441  return _M_insert(__position._M_node, __val, __position._M_node);
442  }
443  // first argument just needs to be non-null
444  else {
445  bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__val) );
446 
447  if (__comp_pos_v == false) // compare > and compare < both false so compare equal
448  return __position;
449  //Below __comp_pos_v == true
450 
451  // Standard-conformance - does the insertion point fall immediately AFTER
452  // the hint?
453  iterator __after = __position;
454  ++__after;
455 
456  // Check for only one member -- in that case, __position points to itself,
457  // and attempting to increment will cause an infinite loop.
458  if (__after._M_node == &this->_M_header._M_data)
459  // Check guarantees exactly one member, so comparison was already
460  // performed and we know the result; skip repeating it in _M_insert
461  // by specifying a non-zero fourth argument.
462  return _M_insert(__position._M_node, __val, 0, __position._M_node);
463 
464  // All other cases:
465 
466  // Optimization to catch insert-equivalent -- save comparison results,
467  // and we get this for free.
468  if (_M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) )) {
469  if (_S_right(__position._M_node) == 0)
470  return _M_insert(__position._M_node, __val, 0, __position._M_node);
471  else
472  return _M_insert(__after._M_node, __val, __after._M_node);
473  }
474  else {
475  return insert_unique(__val).first;
476  }
477  }
478  }
479  else if (__position._M_node == &this->_M_header._M_data) { // end()
480  if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__val))) {
481  // pass along to _M_insert that it can skip comparing
482  // v, Key ; since compare Key, v was true, compare v, Key must be false.
483  return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
484  }
485  else
486  return insert_unique(__val).first;
487  }
488  else {
489  iterator __before = __position;
490  --__before;
491 
492  bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node));
493 
494  if (__comp_v_pos
495  && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__val) )) {
496 
497  if (_S_right(__before._M_node) == 0)
498  return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
499  else
500  return _M_insert(__position._M_node, __val, __position._M_node);
501  // first argument just needs to be non-null
502  }
503  else {
504  // Does the insertion point fall immediately AFTER the hint?
505  iterator __after = __position;
506  ++__after;
507  // Optimization to catch equivalent cases and avoid unnecessary comparisons
508  bool __comp_pos_v = !__comp_v_pos; // Stored this result earlier
509  // If the earlier comparison was true, this comparison doesn't need to be
510  // performed because it must be false. However, if the earlier comparison
511  // was false, we need to perform this one because in the equal case, both will
512  // be false.
513  if (!__comp_v_pos) {
514  __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
515  }
516 
517  if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false
518  && __comp_pos_v
519  && (__after._M_node == &this->_M_header._M_data ||
520  _M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) ))) {
521  if (_S_right(__position._M_node) == 0)
522  return _M_insert(__position._M_node, __val, 0, __position._M_node);
523  else
524  return _M_insert(__after._M_node, __val, __after._M_node);
525  } else {
526  // Test for equivalent case
527  if (__comp_v_pos == __comp_pos_v)
528  return __position;
529  else
530  return insert_unique(__val).first;
531  }
532  }
533  }
534 }
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
iterator _M_insert(_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
Definition: _tree.c:350
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.c:405
bool empty() const
Definition: _tree.h:432
_Compare _M_key_compare
Definition: _tree.h:333

◆ insert_unique() [7/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_unique ( const_iterator  __first,
const_iterator  __last 
)
inline

Definition at line 474 of file _tree.h.

474  {
475  for ( ; __first != __last; ++__first)
476  insert_unique(*__first);
477  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.c:405

◆ insert_unique() [8/8]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_unique ( const value_type __first,
const value_type __last 
)
inline

Definition at line 478 of file _tree.h.

478  {
479  for ( ; __first != __last; ++__first)
480  insert_unique(*__first);
481  }
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.c:405

◆ key_comp() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Compare _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::key_comp ( ) const
inline

Definition at line 154 of file _tree.h.

154 { return _M_non_dbg_impl.key_comp().non_dbg_key_comp(); }
_Base _M_non_dbg_impl
Definition: _tree.h:96

◆ key_comp() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Compare _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::key_comp ( ) const
inline

Definition at line 419 of file _tree.h.

419 { return _M_key_compare; }
_Compare _M_key_compare
Definition: _tree.h:333

◆ lower_bound() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::lower_bound ( const _KT &  __x)
inline

Definition at line 185 of file _tree.h.

186  { return iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ lower_bound() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::lower_bound ( const _KT &  __x) const
inline

Definition at line 188 of file _tree.h.

189  { return const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ lower_bound() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::lower_bound ( const _KT &  __x)
inline

Definition at line 601 of file _tree.h.

601 { return iterator(_M_lower_bound(__x)); }
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_lower_bound(const _KT &__k) const
Definition: _tree.h:567
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::equal_range(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::equal_range_unique().

◆ lower_bound() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::lower_bound ( const _KT &  __x) const
inline

Definition at line 603 of file _tree.h.

603 { return const_iterator(_M_lower_bound(__x)); }
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_lower_bound(const _KT &__k) const
Definition: _tree.h:567
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ max_size() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::max_size ( ) const
inline

Definition at line 168 of file _tree.h.

168 { return _M_non_dbg_impl.max_size(); }
_Base _M_non_dbg_impl
Definition: _tree.h:96

◆ max_size() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::max_size ( ) const
inline

Definition at line 434 of file _tree.h.

434 { return size_type(-1); }
size_t size_type
Definition: _tree.h:307

◆ operator=() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Self& _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::operator= ( const _Self __x)
inline

Definition at line 144 of file _tree.h.

144  {
145  if (this != &__x) {
146  //Should not invalidate end iterator:
148  _M_non_dbg_impl = __x._M_non_dbg_impl;
149  }
150  return *this;
151  }
void _Invalidate_iterators(const iterator &__first, const iterator &__last)
Definition: _tree.h:114
iterator end()
Definition: _tree.h:423
iterator begin()
Definition: _tree.h:421
_Base _M_non_dbg_impl
Definition: _tree.h:96

◆ operator=() [2/2]

template<class _Key , class _Compare , class _Value , class _KeyOfValue , class _Traits , class _Alloc >
_STLP_BEGIN_NAMESPACE _STLP_MOVE_TO_PRIV_NAMESPACE _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc > & _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc >::operator= ( const _Self __x)

Definition at line 321 of file _tree.c.

322  {
323  if (this != &__x) {
324  // Note that _Key may be a constant type.
325  clear();
326  _M_node_count = 0;
327  _M_key_compare = __x._M_key_compare;
328  if (__x._M_root() == 0) {
329  _M_root() = 0;
330  _M_leftmost() = &this->_M_header._M_data;
331  _M_rightmost() = &this->_M_header._M_data;
332  }
333  else {
334  _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
337  _M_node_count = __x._M_node_count;
338  }
339  }
340  return *this;
341 }
_Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p)
Definition: _tree.c:624
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
_Value _M_data
Definition: _alloc.h:478
size_type _M_node_count
Definition: _tree.h:332
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:365
_Base_ptr _M_root() const
Definition: _tree.h:335
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:362
void clear()
Definition: _tree.h:530
_Compare _M_key_compare
Definition: _tree.h:333

◆ rbegin() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
reverse_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rbegin ( )
inline

Definition at line 161 of file _tree.h.

161 { return reverse_iterator(end()); }
#define reverse_iterator
Definition: _abbrevs.h:34
iterator end()
Definition: _tree.h:423

◆ rbegin() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
const_reverse_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rbegin ( ) const
inline

Definition at line 162 of file _tree.h.

162 { return const_reverse_iterator(end()); }
iterator end()
Definition: _tree.h:423

◆ rbegin() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
reverse_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rbegin ( )
inline

Definition at line 426 of file _tree.h.

426 { return reverse_iterator(end()); }
#define reverse_iterator
Definition: _abbrevs.h:34
iterator end()
Definition: _tree.h:423

◆ rbegin() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
const_reverse_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rbegin ( ) const
inline

Definition at line 427 of file _tree.h.

428  { return const_reverse_iterator(end()); }
iterator end()
Definition: _tree.h:423

◆ rend() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
reverse_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rend ( )
inline

Definition at line 163 of file _tree.h.

163 { return reverse_iterator(begin()); }
#define reverse_iterator
Definition: _abbrevs.h:34
iterator begin()
Definition: _tree.h:421

◆ rend() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
const_reverse_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rend ( ) const
inline

Definition at line 164 of file _tree.h.

164 { return const_reverse_iterator(begin()); }
iterator begin()
Definition: _tree.h:421

◆ rend() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
reverse_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rend ( )
inline

Definition at line 429 of file _tree.h.

429 { return reverse_iterator(begin()); }
#define reverse_iterator
Definition: _abbrevs.h:34
iterator begin()
Definition: _tree.h:421

◆ rend() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
const_reverse_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rend ( ) const
inline

Definition at line 430 of file _tree.h.

431  { return const_reverse_iterator(begin()); }
iterator begin()
Definition: _tree.h:421

◆ size() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::size ( ) const
inline

Definition at line 167 of file _tree.h.

167 { return _M_non_dbg_impl.size(); }
_Base _M_non_dbg_impl
Definition: _tree.h:96

◆ size() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
size_type _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::size ( ) const
inline

Definition at line 433 of file _tree.h.

433 { return _M_node_count; }
size_type _M_node_count
Definition: _tree.h:332

◆ swap() [1/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::swap ( _Self __t)
inline

Definition at line 172 of file _tree.h.

172  {
173  _M_non_dbg_impl.swap(__t._M_non_dbg_impl);
174  _M_iter_list._Swap_owners(__t._M_iter_list);
175  }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97

◆ swap() [2/2]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
void _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::swap ( _Self __t)
inline

Definition at line 436 of file _tree.h.

436  {
437  if (__t.empty()) {
438  if (this->empty()) return;
439  __t._M_header.swap(this->_M_header);
440  __t._M_rebind(&this->_M_header._M_data);
441  this->_M_empty_initialize();
442  }
443  else if (this->empty()) {
444  __t.swap(*this);
445  return;
446  }
447  else {
448  this->_M_header.swap(__t._M_header);
449  this->_M_rebind(&__t._M_header._M_data);
450  __t._M_rebind(&this->_M_header._M_data);
451  }
452  _STLP_STD::swap(_M_node_count, __t._M_node_count);
453  _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
454  }
void _M_rebind(_Node_base *__static_node)
Definition: _tree.h:270
#define swap(a, b)
Definition: qsort.c:63
_Value _M_data
Definition: _alloc.h:478
size_type _M_node_count
Definition: _tree.h:332
void swap(_Self &__x)
Definition: _alloc.h:520
bool empty() const
Definition: _tree.h:432
_Compare _M_key_compare
Definition: _tree.h:333

◆ upper_bound() [1/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::upper_bound ( const _KT &  __x)
inline

Definition at line 192 of file _tree.h.

193  { return iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

◆ upper_bound() [2/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::upper_bound ( const _KT &  __x) const
inline

Definition at line 195 of file _tree.h.

196  { return const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); }
_Base _M_non_dbg_impl
Definition: _tree.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ upper_bound() [3/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::upper_bound ( const _KT &  __x)
inline

Definition at line 605 of file _tree.h.

605 { return iterator(_M_upper_bound(__x)); }
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_upper_bound(const _KT &__k) const
Definition: _tree.h:581
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::equal_range().

◆ upper_bound() [4/4]

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::upper_bound ( const _KT &  __x) const
inline

Definition at line 607 of file _tree.h.

607 { return const_iterator(_M_upper_bound(__x)); }
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_upper_bound(const _KT &__k) const
Definition: _tree.h:581
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

Member Data Documentation

◆ _M_iter_list

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_STLP_PRIV __owned_list _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_iter_list
private

Definition at line 97 of file _tree.h.

◆ _M_key_compare

◆ _M_node_count

◆ _M_non_dbg_impl

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Base _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_non_dbg_impl
private

Definition at line 96 of file _tree.h.

◆ _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS

template<class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, _STLP_DFL_TMPL_PARAM(_Alloc, allocator< _Value >) >
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS

Definition at line 373 of file _tree.h.


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