ReactOS: _Rb_tree< _Key, _Compare, _Value, _KeyOfValue,

_Rb_tree_base< _Value, _Alloc >

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.

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

388 {}

_Rb_tree::allocator_type

_Base::allocator_type allocator_type

Definition: _tree.h:310

_Rb_tree_base< _Value, _Alloc >

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.

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

392 {}

_Rb_tree_base< _Value, _Alloc >

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.

     : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
       _M_node_count(0), _M_key_compare(__x._M_key_compare) {
     if (__x._M_root() != 0) {
       _S_color(&this->_M_header._M_data) = _S_rb_tree_red;
       _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
       _M_leftmost() = _S_minimum(_M_root());
       _M_rightmost() = _S_maximum(_M_root());
     }
     _M_node_count = __x._M_node_count;
   }

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

     : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())),
       _M_node_count(src.get()._M_node_count),
       _M_key_compare(_AsMoveSource(src.get()._M_key_compare))
   { src.get()._M_node_count = 0; }

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

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

124 : _M_non_dbg_impl(__comp), _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() [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.

                                     :
     _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)),
     _M_iter_list(&_M_non_dbg_impl) {
 #  if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
     src.get()._M_iter_list._Invalidate_all();
 #  else
     src.get()._M_iter_list._Set_owner(_M_iter_list);
 #  endif
   }

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

__it

_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)

_STLP_PRIV

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

__last

_STLP_INLINE_LOOP _InputIter __last

Definition: _algo.h:68

_STLP_PRIV __owned_list _M_iter_list

Definition: _tree.h:97

_STLP_PRIV

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

                                          {
     _Base_ptr __tmp = _M_create_node(_S_value(__x));
     _S_color(__tmp) = _S_color(__x);
     return __tmp;
   }

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

                                                                                              {
   // structural copy.  __x and __p must be non-null.
   _Base_ptr __top = _M_clone_node(__x);
   _S_parent(__top) = __p;
 
   _STLP_TRY {
     if (_S_right(__x))
       _S_right(__top) = _M_copy(_S_right(__x), __top);
     __p = __top;
     __x = _S_left(__x);
 
     while (__x != 0) {
       _Base_ptr __y = _M_clone_node(__x);
       _S_left(__p) = __y;
       _S_parent(__y) = __p;
       if (_S_right(__x))
         _S_right(__y) = _M_copy(_S_right(__x), __y);
       __p = __y;
       __x = _S_left(__x);
     }
   }
   _STLP_UNWIND(_M_erase(__top))
 
   return __top;
 }

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.

                                                   {
     _Link_type __tmp = this->_M_header.allocate(1);
     _STLP_TRY {
       _Copy_Construct(&__tmp->_M_value_field, __x);
     }
     _STLP_UNWIND(this->_M_header.deallocate(__tmp,1))
     _S_left(__tmp) = 0;
     _S_right(__tmp) = 0;
     return __tmp;
   }

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.

                                                                                            {
   // erase without rebalancing
   while (__x != 0) {
     _M_erase(_S_right(__x));
     _Base_ptr __y = _S_left(__x);
     _STLP_STD::_Destroy(&_S_value(__x));
     this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x),1);
     __x = __y;
   }
 }

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.

                                           {
     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);      // Last node which is not less than __k.
     _Base_ptr __x = _M_root();      // Current node.
 
     while (__x != 0)
       if (!_M_key_compare(_S_key(__x), __k))
         __y = __x, __x = _S_left(__x);
       else
         __x = _S_right(__x);
 
     if (__y != &this->_M_header._M_data) {
       if (_M_key_compare(__k, _S_key(__y))) {
         __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
       }
     }
     return __y;
   }

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.

                                                                                                        {
   // We do not create the node here as, depending on tests, we might call
   // _M_key_compare that can throw an exception.
   _Base_ptr __new_node;
 
   if ( __parent == &this->_M_header._M_data ) {
     __new_node = _M_create_node(__val);
     _S_left(__parent) = __new_node;   // also makes _M_leftmost() = __new_node
     _M_root() = __new_node;
     _M_rightmost() = __new_node;
   }
   else if ( __on_right == 0 &&     // If __on_right != 0, the remainder fails to false
            ( __on_left != 0 ||     // If __on_left != 0, the remainder succeeds to true
              _M_key_compare( _KeyOfValue()(__val), _S_key(__parent) ) ) ) {
     __new_node = _M_create_node(__val);
     _S_left(__parent) = __new_node;
     if (__parent == _M_leftmost())
       _M_leftmost() = __new_node;   // maintain _M_leftmost() pointing to min node
   }
   else {
     __new_node = _M_create_node(__val);
     _S_right(__parent) = __new_node;
     if (__parent == _M_rightmost())
       _M_rightmost() = __new_node;  // maintain _M_rightmost() pointing to max node
   }
   _S_parent(__new_node) = __parent;
   _Rb_global_inst::_Rebalance(__new_node, this->_M_header._M_data._M_parent);
   ++_M_node_count;
   return iterator(__new_node);
 }

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

Definition at line 337 of file _tree.h.

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

_AllocProxy _M_header

Definition: _tree.h:282

_Rb_tree_node_base::_M_left

_Value _M_data

Definition: _alloc.h:478

_Base_ptr _M_left

Definition: _tree.h:90

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

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

_AllocProxy _M_header

Definition: _tree.h:282

_Rb_tree_node_base::_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.

                                                  {
     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */
     _Base_ptr __x = _M_root(); /* Current node. */
 
     while (__x != 0)
       if (!_M_key_compare(_S_key(__x), __k))
         __y = __x, __x = _S_left(__x);
       else
         __x = _S_right(__x);
 
     return __y;
   }

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

Definition at line 339 of file _tree.h.

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

_Rb_tree_node_base::_M_right

_AllocProxy _M_header

Definition: _tree.h:282

_Base_ptr _M_right

Definition: _tree.h:91

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

_Value _M_data

Definition: _alloc.h:478

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

_Rb_tree_node_base::_M_right

_AllocProxy _M_header

Definition: _tree.h:282

_Base_ptr _M_right

Definition: _tree.h:91

_Value _M_data

Definition: _alloc.h:478

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

inlineprotected

Definition at line 335 of file _tree.h.

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

_AllocProxy _M_header

Definition: _tree.h:282

_Rb_tree_node_base::_M_parent

_Value _M_data

Definition: _alloc.h:478

_Base_ptr _M_parent

Definition: _tree.h:89

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_find(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_lower_bound(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_upper_bound(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_Rb_tree(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::clear(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::operator=().

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

_AllocProxy _M_header

Definition: _tree.h:282

_Rb_tree_node_base::_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.

                                                  {
     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */
     _Base_ptr __x = _M_root(); /* Current node. */
 
     while (__x != 0)
       if (_M_key_compare(__k, _S_key(__x)))
         __y = __x, __x = _S_left(__x);
       else
         __x = _S_right(__x);
 
     return __y;
   }

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

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_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_clone_node(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_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));}

_Rb_tree::_S_value

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 >::_M_find(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_lower_bound(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_upper_bound(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::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_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_create_node(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_find(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_lower_bound(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_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_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); }

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

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_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_create_node(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_find(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_lower_bound(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_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; }

__STATIC_CAST

#define __STATIC_CAST(__x, __y)

Definition: features.h:585

_Rb_tree::_Link_type

_Node * _Link_type

Definition: _tree.h:298

Referenced by _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_M_clone_node(), _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::_S_key(), and _Rb_tree< key_type, key_compare, value_type, _STLP_SELECT1ST(value_type, void), _MapTraits, _Alloc >::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 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()); }

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

_Rb_tree::_M_leftmost

_Base_ptr _M_leftmost() const

Definition: _tree.h:337

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().

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

                {
     //should not invalidate end:
     _Invalidate_iterators(begin(), end());
     _M_non_dbg_impl.clear();
   }

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

                {
     if (_M_node_count != 0) {
       _M_erase(_M_root());
       _M_leftmost() = &this->_M_header._M_data;
       _M_root() = 0;
       _M_rightmost() = &this->_M_header._M_data;
       _M_node_count = 0;
     }
   }

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

                                         {
     pair<const_iterator, const_iterator> __p = equal_range(__x);
     return _STLP_STD::distance(__p.first, __p.second);
   }

◆ 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

Definition at line 432 of file _tree.h.

432 { return _M_node_count == 0; }

size_type _M_node_count

Definition: _tree.h:332

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

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

_AllocProxy _M_header

Definition: _tree.h:282

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

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

_AllocProxy _M_header

Definition: _tree.h:282

_Rb_tree::_Base_ptr

_Rb_tree_node_base * _Base_ptr

Definition: _tree.h:296

_Value _M_data

Definition: _alloc.h:478

__CONST_CAST

#define __CONST_CAST(__x, __y)

Definition: features.h:584

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().

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

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

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

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

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

_Rb_tree::upper_bound

_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound(const _KT &__x)

Definition: _tree.h:605

_Rb_tree::lower_bound

_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)

Definition: _tree.h:601

pair

Definition: _pair.h:47

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

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

_Rb_tree::upper_bound

_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound(const _KT &__x)

Definition: _tree.h:605

_Rb_tree::lower_bound

_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)

Definition: _tree.h:601

pair

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.

                                                              {
     _STLP_STD::pair<_Base_iterator, _Base_iterator> __p;
     __p = _M_non_dbg_impl.equal_range_unique(__x);
     return pair<iterator, iterator>(iterator(&_M_iter_list, __p.first), iterator(&_M_iter_list, __p.second));
   }

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

                                                                                 {
     _STLP_STD::pair<_Base_const_iterator, _Base_const_iterator> __p;
     __p = _M_non_dbg_impl.equal_range_unique(__x);
     return pair<const_iterator, const_iterator>(const_iterator(&_M_iter_list, __p.first),
                                                 const_iterator(&_M_iter_list, __p.second));
   }

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

                                                              {
     pair<iterator, iterator> __p;
     __p.second = lower_bound(__x);
     if (__p.second._M_node != &this->_M_header._M_data &&
         !_M_key_compare(__x, _S_key(__p.second._M_node))) {
       __p.first = __p.second++;
     }
     else {
       __p.first = __p.second;
     }
     return __p;
   }

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

                                                                                 {
     pair<const_iterator, const_iterator> __p;
     __p.second = lower_bound(__x);
     if (__p.second._M_node != &this->_M_header._M_data &&
         !_M_key_compare(__x, _S_key(__p.second._M_node))) {
       __p.first = __p.second++;
     }
     else {
       __p.first = __p.second;
     }
     return __p;
   }

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

                              {
     _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos))
     _STLP_DEBUG_CHECK(_Dereferenceable(__pos))
     _Invalidate_iterator(__pos);
     _M_non_dbg_impl.erase(__pos._M_iterator);
   }

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

                                        {
     pair<iterator, iterator> __p = equal_range(__x);
     size_type __n = _STLP_STD::distance(__p.first._M_iterator, __p.second._M_iterator);
     _Invalidate_iterators(__p.first, __p.second);
     _M_non_dbg_impl.erase(__p.first._M_iterator, __p.second._M_iterator);
     return __n;
   }

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

                                                 {
     _STLP_DEBUG_CHECK(__check_range(__first, __last, begin(), end()))
     _Invalidate_iterators(__first, __last);
     _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator);
   }

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

                                                               {
     while (__first != __last) erase(*__first++);
   }

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

                              {
     _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node,
                                                           this->_M_header._M_data._M_parent,
                                                           this->_M_header._M_data._M_left,
                                                           this->_M_header._M_data._M_right);
     _STLP_STD::_Destroy(&_S_value(__x));
     this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
     --_M_node_count;
   }

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.

                                        {
     pair<iterator,iterator> __p = equal_range(__x);
     size_type __n = _STLP_STD::distance(__p.first, __p.second);
     erase(__p.first, __p.second);
     return __n;
   }

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

                                                 {
     if (__first._M_node == this->_M_header._M_data._M_left && // begin()
         __last._M_node == &this->_M_header._M_data)           // end()
       clear();
     else
       while (__first != __last) erase(__first++);
   }

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

                                                               {
     while (__first != __last) erase(*__first++);
   }

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

                                               {
     _Base_iterator __i = _M_non_dbg_impl.find(__x);
     if (__i != _M_non_dbg_impl.end()) {
       _Invalidate_iterator(iterator(&_M_iter_list, __i));
       _M_non_dbg_impl.erase(__i);
       return 1;
     }
     return 0;
   }

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

                                               {
     iterator __i = find(__x);
     if (__i._M_node != &this->_M_header._M_data) {
       erase(__i);
       return 1;
     }
     return 0;
   }

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

_Rb_tree::_M_find

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

_Rb_tree::_M_find

_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_find(const _KT &__k) const

Definition: _tree.h:548

_Rb_tree_base::get_allocator

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

                                                                {
     _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list, __pos))
     return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__pos._M_iterator, __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_iterator	__first,
		const_iterator	__last
	)

inline

Definition at line 259 of file _tree.h.

                                                                    {
     _STLP_DEBUG_CHECK(__check_range(__first,__last))
     _M_non_dbg_impl.insert_equal(__first._M_iterator, __last._M_iterator);
   }

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

                                                                          {
     _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last))
     _M_non_dbg_impl.insert_equal(__first, __last);
   }

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

                                                                                             {
   _Base_ptr __y = &this->_M_header._M_data;
   _Base_ptr __x = _M_root();
   while (__x != 0) {
     __y = __x;
     if (_M_key_compare(_KeyOfValue()(__val), _S_key(__x))) {
       __x = _S_left(__x);
     }
     else
       __x = _S_right(__x);
   }
   return _M_insert(__y, __val, __x);
 }

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.

                                                                                               {
   if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
 
     // Check for zero members
     if (size() <= 0)
         return insert_equal(__val);
 
     if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val)))
       return _M_insert(__position._M_node, __val, __position._M_node);
     else {
       // Check for only one member
       if (__position._M_node->_M_left == __position._M_node)
         // Unlike insert_unique, can't avoid doing a comparison here.
         return _M_insert(__position._M_node, __val);
 
       // All other cases:
       // Standard-conformance - does the insertion point fall immediately AFTER
       // the hint?
       iterator __after = __position;
       ++__after;
 
       // Already know that compare(pos, v) must be true!
       // Therefore, we want to know if compare(after, v) is false.
       // (i.e., we now pos < v, now we want to know if v <= after)
       // If not, invalid hint.
       if ( __after._M_node == &this->_M_header._M_data ||
            !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) {
         if (_S_right(__position._M_node) == 0)
           return _M_insert(__position._M_node, __val, 0, __position._M_node);
         else
           return _M_insert(__after._M_node, __val, __after._M_node);
       }
       else { // Invalid hint
         return insert_equal(__val);
       }
     }
   }
   else if (__position._M_node == &this->_M_header._M_data) { // end()
     if (!_M_key_compare(_KeyOfValue()(__val), _S_key(_M_rightmost())))
       return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
     else {
       return insert_equal(__val);
     }
   }
   else {
     iterator __before = __position;
     --__before;
     // store the result of the comparison between pos and v so
     // that we don't have to do it again later.  Note that this reverses the shortcut
     // on the if, possibly harming efficiency in comparisons; I think the harm will
     // be negligible, and to do what I want to do (save the result of a comparison so
     // that it can be re-used) there is no alternative.  Test here is for before <= v <= pos.
     bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
     if (!__comp_pos_v &&
         !_M_key_compare(_KeyOfValue()(__val), _S_key(__before._M_node))) {
       if (_S_right(__before._M_node) == 0)
         return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
       else
         return _M_insert(__position._M_node, __val, __position._M_node);
     }
     else {
       // Does the insertion point fall immediately AFTER the hint?
       // Test for pos < v <= after
       iterator __after = __position;
       ++__after;
 
       if (__comp_pos_v &&
           ( __after._M_node == &this->_M_header._M_data ||
             !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) ) {
         if (_S_right(__position._M_node) == 0)
           return _M_insert(__position._M_node, __val, 0, __position._M_node);
         else
           return _M_insert(__after._M_node, __val, __after._M_node);
       }
       else { // Invalid hint
         return insert_equal(__val);
       }
     }
   }
 }

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

                                                                    {
     for ( ; __first != __last; ++__first)
       insert_equal(*__first);
   }

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

                                                                          {
     for ( ; __first != __last; ++__first)
       insert_equal(*__first);
   }

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

                                                            {
     _STLP_STD::pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__x);
     return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
   }

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

                                                                 {
     _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos))
     return iterator(&_M_iter_list, _M_non_dbg_impl.insert_unique(__pos._M_iterator, __x));
   }

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

                                                                     {
     _STLP_DEBUG_CHECK(__check_range(__first,__last))
     _M_non_dbg_impl.insert_unique(__first._M_iterator, __last._M_iterator);
   }

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

                                                                           {
     _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last))
     _M_non_dbg_impl.insert_unique(__first, __last);
   }

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

                                                                                              {
   _Base_ptr __y = &this->_M_header._M_data;
   _Base_ptr __x = _M_root();
   bool __comp = true;
   while (__x != 0) {
     __y = __x;
     __comp = _M_key_compare(_KeyOfValue()(__val), _S_key(__x));
     __x = __comp ? _S_left(__x) : _S_right(__x);
   }
   iterator __j = iterator(__y);
   if (__comp) {
     if (__j == begin())
       return pair<iterator,bool>(_M_insert(__y, __val, /* __x*/ __y), true);
     else
       --__j;
   }
   if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__val))) {
     return pair<iterator,bool>(_M_insert(__y, __val, __x), true);
   }
   return pair<iterator,bool>(__j, false);
 }

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.

                                                                                                {
   if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
 
     // if the container is empty, fall back on insert_unique.
     if (empty())
       return insert_unique(__val).first;
 
     if (_M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node))) {
       return _M_insert(__position._M_node, __val, __position._M_node);
     }
     // first argument just needs to be non-null
     else {
       bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__val) );
 
       if (__comp_pos_v == false)  // compare > and compare < both false so compare equal
         return __position;
       //Below __comp_pos_v == true
 
       // Standard-conformance - does the insertion point fall immediately AFTER
       // the hint?
       iterator __after = __position;
       ++__after;
 
       // Check for only one member -- in that case, __position points to itself,
       // and attempting to increment will cause an infinite loop.
       if (__after._M_node == &this->_M_header._M_data)
         // Check guarantees exactly one member, so comparison was already
         // performed and we know the result; skip repeating it in _M_insert
         // by specifying a non-zero fourth argument.
         return _M_insert(__position._M_node, __val, 0, __position._M_node);
 
       // All other cases:
 
       // Optimization to catch insert-equivalent -- save comparison results,
       // and we get this for free.
       if (_M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) )) {
         if (_S_right(__position._M_node) == 0)
           return _M_insert(__position._M_node, __val, 0, __position._M_node);
         else
           return _M_insert(__after._M_node, __val, __after._M_node);
       }
       else {
         return insert_unique(__val).first;
       }
     }
   }
   else if (__position._M_node == &this->_M_header._M_data) { // end()
     if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__val))) {
         // pass along to _M_insert that it can skip comparing
         // v, Key ; since compare Key, v was true, compare v, Key must be false.
         return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
     }
     else
       return insert_unique(__val).first;
   }
   else {
     iterator __before = __position;
     --__before;
 
     bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node));
 
     if (__comp_v_pos
         && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__val) )) {
 
       if (_S_right(__before._M_node) == 0)
         return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
       else
         return _M_insert(__position._M_node, __val, __position._M_node);
       // first argument just needs to be non-null
     }
     else {
       // Does the insertion point fall immediately AFTER the hint?
       iterator __after = __position;
       ++__after;
       // Optimization to catch equivalent cases and avoid unnecessary comparisons
       bool __comp_pos_v = !__comp_v_pos;  // Stored this result earlier
       // If the earlier comparison was true, this comparison doesn't need to be
       // performed because it must be false.  However, if the earlier comparison
       // was false, we need to perform this one because in the equal case, both will
       // be false.
       if (!__comp_v_pos) {
         __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
       }
 
       if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false
           && __comp_pos_v
           && (__after._M_node == &this->_M_header._M_data ||
               _M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) ))) {
         if (_S_right(__position._M_node) == 0)
           return _M_insert(__position._M_node, __val, 0, __position._M_node);
         else
           return _M_insert(__after._M_node, __val, __after._M_node);
       } else {
         // Test for equivalent case
         if (__comp_v_pos == __comp_pos_v)
           return __position;
         else
           return insert_unique(__val).first;
       }
     }
   }
 }

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

                                                                     {
     for ( ; __first != __last; ++__first)
       insert_unique(*__first);
   }

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

                                                                           {
     for ( ; __first != __last; ++__first)
       insert_unique(*__first);
   }

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

_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_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().

_Rb_tree_iterator< value_type, _NonConstTraits > iterator

Definition: _tree.h:371

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

_Rb_tree::_M_lower_bound

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

_Rb_tree::size_type

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.

                                      {
     if (this != &__x) {
       //Should not invalidate end iterator:
       _Invalidate_iterators(begin(), end());
       _M_non_dbg_impl = __x._M_non_dbg_impl;
     }
     return *this;
   }

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

                                                                         {
   if (this != &__x) {
     // Note that _Key may be a constant type.
     clear();
     _M_node_count = 0;
     _M_key_compare = __x._M_key_compare;
     if (__x._M_root() == 0) {
       _M_root() = 0;
       _M_leftmost() = &this->_M_header._M_data;
       _M_rightmost() = &this->_M_header._M_data;
     }
     else {
       _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
       _M_leftmost() = _S_minimum(_M_root());
       _M_rightmost() = _S_maximum(_M_root());
       _M_node_count = __x._M_node_count;
     }
   }
   return *this;
 }

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

                         {
     _M_non_dbg_impl.swap(__t._M_non_dbg_impl);
     _M_iter_list._Swap_owners(__t._M_iter_list);
   }

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

                         {
     if (__t.empty()) {
       if (this->empty()) return;
       __t._M_header.swap(this->_M_header);
       __t._M_rebind(&this->_M_header._M_data);
       this->_M_empty_initialize();
     }
     else if (this->empty()) {
       __t.swap(*this);
       return;
     }
     else {
       this->_M_header.swap(__t._M_header);
       this->_M_rebind(&__t._M_header._M_data);
       __t._M_rebind(&this->_M_header._M_data);
     }
     _STLP_STD::swap(_M_node_count, __t._M_node_count);
     _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
   }

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

_Rb_tree::_M_upper_bound

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

_Rb_tree::_M_upper_bound

_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_upper_bound(const _KT &__k) const

Definition: _tree.h:581