ReactOS 0.4.15-dev-5895-g2687c1b
Public Types | Public Member Functions | Public Attributes | Protected Types | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Private Types | Private Member Functions | Private Attributes | List of all members
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, > Class Template Reference

#include <_tree.h>

Inheritance diagram for _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >:
Inheritance graph
[legend]
Collaboration diagram for _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >:
Collaboration graph
[legend]

Public Types

typedef _Key key_type
 
typedef _Value value_type
 
typedef _Traits::pointer pointer
 
typedef const value_type * const_pointer
 
typedef _Traits::reference reference
 
typedef const value_type & const_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, _NonConstTraits > iterator
 
typedef _Rb_tree_iterator< value_type, _ConstTraits > const_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 ()
 
_Self & operator= (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, bool > insert_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, iterator > equal_range (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range_unique (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_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 ()
 
_Self & operator= (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, iterator > equal_range (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range (const _KT &__x) const
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range_unique (const _KT &__x)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range_unique (const _KT &__x) const
 
pair< iterator, bool > insert_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 _Rb_tree_base<_Value, _Alloc> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Base
private

Definition at line 293 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 _STLP_NON_DBG_TREE _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Base
private

Definition at line 94 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 294 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 95 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 _Rb_tree_iterator<value_type, _ConstTraits> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::const_iterator

Definition at line 372 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 _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_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 _Rb_tree_iterator<value_type, _NonConstTraits> _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::iterator

Definition at line 371 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 _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.

◆ key_type [1/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.

◆ key_type [2/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.

◆ 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.

383 : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
384 {}
_Rb_tree_base
Definition: _tree.h:232
_Rb_tree::_M_node_count
size_type _M_node_count
Definition: _tree.h:332
_Rb_tree::_M_key_compare
_Compare _M_key_compare
Definition: _tree.h:333
_Rb_tree::allocator_type
_Base::allocator_type allocator_type
Definition: _tree.h:310

◆ _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.

387 : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
388 {}

◆ _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.

391 : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp)
392 {}

◆ _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) {
398 _S_color(&this->_M_header._M_data) = _S_rb_tree_red;
399 _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
400 _M_leftmost() = _S_minimum(_M_root());
401 _M_rightmost() = _S_maximum(_M_root());
402 }
403 _M_node_count = __x._M_node_count;
404 }
_S_rb_tree_red
#define _S_rb_tree_red
Definition: _tree.h:81
_Rb_tree_base< _Value, _Alloc >::_M_header
_AllocProxy _M_header
Definition: _tree.h:282
_Rb_tree::_M_leftmost
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
_Rb_tree::_M_rightmost
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
_Rb_tree::_S_minimum
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:362
_Rb_tree::_S_color
static _Color_type &_STLP_CALL _S_color(_Base_ptr __x)
Definition: _tree.h:359
_Rb_tree::_M_root
_Base_ptr _M_root() const
Definition: _tree.h:335
_Rb_tree::_S_maximum
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:365
_Rb_tree::_M_copy
_Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p)
Definition: _tree.c:624
_STLP_alloc_proxy::_M_data
_Value _M_data
Definition: _alloc.h:478

◆ _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.

408 : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())),
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; }
_AsMoveSource
_STLP_TYPENAME_ON_RETURN_TYPE _MoveSourceTraits< _Tp >::_Type _AsMoveSource(_Tp &src)
Definition: _move_construct_fwk.h:101
__move_source
Definition: _move_construct_fwk.h:35
src
GLenum src
Definition: glext.h:6340

◆ ~_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(); }
_Rb_tree::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.

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

◆ _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.

124 : _M_non_dbg_impl(__comp), _M_iter_list(&_M_non_dbg_impl) {}

◆ _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) {}

◆ _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) {}

◆ _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)),
133 _M_iter_list(&_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 }

◆ ~_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
#define _STLP_PRIV
Definition: _dm.h:70
__it
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)

◆ _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); }
__last
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68

◆ _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::_M_create_node
_Base_ptr _M_create_node(const value_type &__x)
Definition: _tree.h:315
_Rb_tree::_S_value
static value_type &_STLP_CALL _S_value(_Base_ptr __x)
Definition: _tree.h:355
_Rb_tree::_Base_ptr
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296

◆ _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}
_Rb_tree::_M_clone_node
_Base_ptr _M_clone_node(_Base_ptr __x)
Definition: _tree.h:326
_Rb_tree::_S_right
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
_Rb_tree::_S_parent
static _Base_ptr &_STLP_CALL _S_parent(_Base_ptr __x)
Definition: _tree.h:353
_Rb_tree::_M_erase
void _M_erase(_Base_ptr __x)
Definition: _tree.c:655
_Rb_tree::_S_left
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_STLP_UNWIND
#define _STLP_UNWIND(action)
Definition: features.h:824
_STLP_TRY
#define _STLP_TRY
Definition: features.h:817

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_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 }
_Copy_Construct
void _Copy_Construct(_Tp *__p, const _Tp &__val)
Definition: _construct.h:130
return
return
Definition: dirsup.c:529
_Rb_tree::_Link_type
_Node * _Link_type
Definition: _tree.h:298
_STLP_alloc_proxy::allocate
_Tp * allocate(size_type __n, size_type &__allocated_n)
Definition: _alloc.h:525

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_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);
660 _STLP_STD::_Destroy(&_S_value(__x));
661 this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x),1);
662 __x = __y;
663 }
664}
__STATIC_CAST
#define __STATIC_CAST(__x, __y)
Definition: features.h:585

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::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::_S_key
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
__CONST_CAST
#define __CONST_CAST(__x, __y)
Definition: features.h:584

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::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;
379 _Rb_global_inst::_Rebalance(__new_node, this->_M_header._M_data._M_parent);
380 ++_M_node_count;
381 return iterator(__new_node);
382}
__val
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
_Rb_global::_Rebalance
static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr &__root)
_Rb_tree::iterator
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371
_Rb_tree_node_base::_M_parent
_Base_ptr _M_parent
Definition: _tree.h:89
__on_left
Definition: _string_sum.h:80
__on_right
Definition: _string_sum.h:81

◆ _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 ( )
inlineprotected

Definition at line 344 of file _tree.h.

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

◆ _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 ( ) const
inlineprotected

Definition at line 337 of file _tree.h.

338 { return this->_M_header._M_data._M_left; }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::begin(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::clear().

◆ _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 }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::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 ( )
inlineprotected

Definition at line 346 of file _tree.h.

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

◆ _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 ( ) const
inlineprotected

Definition at line 339 of file _tree.h.

340 { return this->_M_header._M_data._M_right; }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::clear().

◆ _M_root() [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_root ( )
inlineprotected

Definition at line 342 of file _tree.h.

343 { return this->_M_header._M_data._M_parent; }

◆ _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 ( ) const
inlineprotected

Definition at line 335 of file _tree.h.

336 { return this->_M_header._M_data._M_parent; }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_find(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_lower_bound(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_upper_bound(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::clear(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::operator=().

◆ _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 }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::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

Definition at line 359 of file _tree.h.

360 { return (_Color_type&)(__x->_M_color); }
_Rb_tree::_Color_type
_Rb_tree_Color_type _Color_type
Definition: _tree.h:299

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_clone_node(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree().

◆ _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

Definition at line 357 of file _tree.h.

358 { return _KeyOfValue()(_S_value(__x));}

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_find(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_lower_bound(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_upper_bound(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range_unique().

◆ _S_left()

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_left ( _Base_ptr  __x)
inlinestaticprotected

Definition at line 349 of file _tree.h.

350 { return __x->_M_left; }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_create_node(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_find(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_lower_bound(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_upper_bound().

◆ _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); }
_Rb_tree_node_base::_S_maximum
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:98

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_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); }
_Rb_tree_node_base::_S_minimum
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:93

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_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()

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_right ( _Base_ptr  __x)
inlinestaticprotected

Definition at line 351 of file _tree.h.

352 { return __x->_M_right; }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_create_node(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_find(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_lower_bound(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_upper_bound().

◆ _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

Definition at line 355 of file _tree.h.

356 { return __STATIC_CAST(_Link_type, __x)->_M_value_field; }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_clone_node(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_S_key(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase().

◆ 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 421 of file _tree.h.

421{ return iterator(_M_leftmost()); }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rend().

◆ begin() [2/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()); }

◆ begin() [3/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()); }
_Rb_tree::const_iterator
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372

◆ 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 157 of file _tree.h.

157{ return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }

◆ 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 ( )
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 }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::~_Rb_tree().

◆ 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 ( )
inline

Definition at line 301 of file _tree.h.

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

◆ 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 596 of file _tree.h.

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

◆ 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 170 of file _tree.h.

170{ return _M_non_dbg_impl.count(__x); }

◆ 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 432 of file _tree.h.

432{ return _M_node_count == 0; }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::swap().

◆ 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

Definition at line 166 of file _tree.h.

166{ return _M_non_dbg_impl.empty(); }

◆ 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 423 of file _tree.h.

423{ return iterator(&this->_M_header._M_data); }

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::rbegin().

◆ end() [2/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()); }

◆ end() [3/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.

424{ return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); }

◆ 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 159 of file _tree.h.

159{ return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); }

◆ 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 609 of file _tree.h.

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

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::count(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase().

◆ 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< iterator, iterator > _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range ( const _KT &  __x)
inline

Definition at line 199 of file _tree.h.

199 {
200 return pair<iterator, iterator>(iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)),
201 iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)));
202 }

◆ 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< 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.

613 { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); }

◆ 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 204 of file _tree.h.

204 {
205 return pair<const_iterator,const_iterator>(const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)),
206 const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)));
207 }

◆ 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 615 of file _tree.h.

615 {
616 pair<iterator, iterator> __p;
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 }

◆ 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< 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 }

◆ 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< 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 {
629 pair<const_iterator, const_iterator> __p;
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 }

◆ 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 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);
219 return pair<const_iterator, const_iterator>(const_iterator(&_M_iter_list, __p.first),
220 const_iterator(&_M_iter_list, __p.second));
221 }

◆ erase() [1/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 {
503 pair<iterator,iterator> __p = equal_range(__x);
504 size_type __n = _STLP_STD::distance(__p.first, __p.second);
505 erase(__p.first, __p.second);
506 return __n;
507 }
__n
return __n
Definition: _algo.h:75
_Rb_tree::size_type
size_t size_type
Definition: _tree.h:307
_Rb_tree::erase
void erase(iterator __pos)
Definition: _tree.h:492

◆ 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 {
276 pair<iterator, iterator> __p = equal_range(__x);
277 size_type __n = _STLP_STD::distance(__p.first._M_iterator, __p.second._M_iterator);
278 _Invalidate_iterators(__p.first, __p.second);
279 _M_non_dbg_impl.erase(__p.first._M_iterator, __p.second._M_iterator);
280 return __n;
281 }

◆ 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 ( 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 }

◆ 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 }

◆ 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  __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 }

◆ erase() [6/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 }
_STLP_DEBUG_CHECK
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440

◆ 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  __pos)
inline

Definition at line 492 of file _tree.h.

492 {
493 _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node,
494 this->_M_header._M_data._M_parent,
495 this->_M_header._M_data._M_left,
496 this->_M_header._M_data._M_right);
497 _STLP_STD::_Destroy(&_S_value(__x));
498 this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
499 --_M_node_count;
500 }
_Rb_global::_Rebalance_for_erase
static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z, _Base_ptr &__root, _Base_ptr &__leftmost, _Base_ptr &__rightmost)

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase_unique().

◆ 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 ( iterator  __pos)
inline

Definition at line 269 of file _tree.h.

269 {
270 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos))
271 _STLP_DEBUG_CHECK(_Dereferenceable(__pos))
272 _Invalidate_iterator(__pos);
273 _M_non_dbg_impl.erase(__pos._M_iterator);
274 }
_Rb_tree::_Invalidate_iterator
void _Invalidate_iterator(const iterator &__it)
Definition: _tree.h:112
_Dereferenceable
bool _Dereferenceable(const _Iterator &__it)
Definition: _iterator.h:93

◆ 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 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 }
find
static TAGID TAGID find
Definition: db.cpp:155

◆ 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 282 of file _tree.h.

282 {
283 _Base_iterator __i = _M_non_dbg_impl.find(__x);
284 if (__i != _M_non_dbg_impl.end()) {
285 _Invalidate_iterator(iterator(&_M_iter_list, __i));
286 _M_non_dbg_impl.erase(__i);
287 return 1;
288 }
289 return 0;
290 }
_Rb_tree::_Base_iterator
_Base::iterator _Base_iterator
Definition: _tree.h:117

◆ 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 543 of file _tree.h.

543{ return iterator(_M_find(__k)); }
_Rb_tree::_M_find
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_find(const _KT &__k) const
Definition: _tree.h:548

◆ 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 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)); }

◆ 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 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)); }

◆ 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 181 of file _tree.h.

182 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); }

◆ 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(); }
_Rb_tree_base::get_allocator
allocator_type get_allocator() const
Definition: _tree.h:244

◆ insert_equal() [1/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::_M_insert
iterator _M_insert(_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
Definition: _tree.c:350

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_equal().

◆ 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 ( 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)); }

◆ 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 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 }
_Rb_tree::insert_equal
iterator insert_equal(const value_type &__x)
Definition: _tree.c:387

◆ 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 }

◆ insert_equal() [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, >::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 }

◆ insert_equal() [6/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 }

◆ insert_equal() [7/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}
_Rb_tree::size
size_type size() const
Definition: _tree.h:433

◆ insert_equal() [8/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 }

◆ insert_unique() [1/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}

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::insert_unique().

◆ insert_unique() [2/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 }

◆ 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 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 }
_Rb_tree::insert_unique
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.c:405

◆ 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 }

◆ insert_unique() [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, >::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 }

◆ insert_unique() [6/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 }

◆ insert_unique() [7/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}
_Rb_tree::empty
bool empty() const
Definition: _tree.h:432

◆ insert_unique() [8/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 }

◆ 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 419 of file _tree.h.

419{ return _M_key_compare; }

◆ 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 154 of file _tree.h.

154{ return _M_non_dbg_impl.key_comp().non_dbg_key_comp(); }

◆ 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 601 of file _tree.h.

601{ return iterator(_M_lower_bound(__x)); }
_Rb_tree::_M_lower_bound
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_lower_bound(const _KT &__k) const
Definition: _tree.h:567

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range_unique().

◆ 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 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)); }

◆ 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 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)); }

◆ 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 188 of file _tree.h.

189 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); }

◆ 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 434 of file _tree.h.

434{ return size_type(-1); }

◆ 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 168 of file _tree.h.

168{ return _M_non_dbg_impl.max_size(); }

◆ operator=() [1/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);
335 _M_leftmost() = _S_minimum(_M_root());
336 _M_rightmost() = _S_maximum(_M_root());
337 _M_node_count = __x._M_node_count;
338 }
339 }
340 return *this;
341}

◆ operator=() [2/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:
147 _Invalidate_iterators(begin(), end());
148 _M_non_dbg_impl = __x._M_non_dbg_impl;
149 }
150 return *this;
151 }

◆ 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 426 of file _tree.h.

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

◆ rbegin() [2/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()); }

◆ rbegin() [3/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()); }

◆ 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 162 of file _tree.h.

162{ return const_reverse_iterator(end()); }

◆ 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 429 of file _tree.h.

429{ return reverse_iterator(begin()); }

◆ rend() [2/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()); }

◆ rend() [3/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()); }

◆ 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 164 of file _tree.h.

164{ return const_reverse_iterator(begin()); }

◆ 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 433 of file _tree.h.

433{ return _M_node_count; }

◆ 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 167 of file _tree.h.

167{ return _M_non_dbg_impl.size(); }

◆ 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 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 }
_Rb_tree_base< _Value, _Alloc >::_M_rebind
void _M_rebind(_Node_base *__static_node)
Definition: _tree.h:270
_Rb_tree_base< _Value, _Alloc >::_M_empty_initialize
void _M_empty_initialize()
Definition: _tree.h:262
_STLP_alloc_proxy::swap
void swap(_Self &__x)
Definition: _alloc.h:520

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::swap().

◆ 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 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 }

◆ 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 605 of file _tree.h.

605{ return iterator(_M_upper_bound(__x)); }
_Rb_tree::_M_upper_bound
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_upper_bound(const _KT &__k) const
Definition: _tree.h:581

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range().

◆ 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 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)); }

◆ 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 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)); }

◆ 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 195 of file _tree.h.

196 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); }

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.

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::swap().

◆ _M_key_compare

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, >::_M_key_compare
protected

Definition at line 333 of file _tree.h.

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_find(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_lower_bound(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_M_upper_bound(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::equal_range_unique(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::key_comp(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::operator=(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::swap().

◆ _M_node_count

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, >::_M_node_count
protected

Definition at line 332 of file _tree.h.

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::_Rb_tree(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::clear(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::empty(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::erase(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::operator=(), _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::size(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::swap().

◆ _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.

Referenced by _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::operator=(), and _Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, >::swap().

◆ _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: