_Tree< _Traits > Class Template Reference

Inheritance diagram for _Tree< _Traits >:

Public Types
enum	{ _Multi = _Traits::_Multi }
typedef _Tree< _Traits >	_Myt
typedef _Tree_comp< !is_empty< typename _Traits::key_compare >::value, _Traits >	_Mybase
typedef _Traits::key_type	key_type
typedef _Traits::value_compare	value_compare
typedef _Mybase::_Node	_Node
typedef _Mybase::_Nodeptr	_Nodeptr
typedef _Mybase::_Alty	_Alty
typedef _Mybase::key_compare	key_compare
typedef _Mybase::allocator_type	allocator_type
typedef _Mybase::value_type	value_type
typedef _Mybase::size_type	size_type
typedef _Mybase::difference_type	difference_type
typedef _Mybase::pointer	pointer
typedef _Mybase::const_pointer	const_pointer
typedef _Mybase::reference	reference
typedef _Mybase::const_reference	const_reference
typedef _Mybase::const_iterator	const_iterator
typedef _If< is_same< key_type, value_type >::value, typename _Mybase::const_iterator, typename _Mybase::iterator >::type	iterator
typedef _STD reverse_iterator< iterator >	reverse_iterator
typedef _STD reverse_iterator< const_iterator >	const_reverse_iterator
typedef pair< iterator, bool >	_Pairib
typedef pair< iterator, iterator >	_Pairii
typedef pair< const_iterator, const_iterator >	_Paircc
Public Types inherited from _Tree_comp< !is_empty< _Traits::key_compare >::value, _Traits >
typedef _Tree_comp< _Pr_has_storage, _Traits >	_Myt
typedef _Tree_buy< typename _Traits::value_type, typename _Traits::allocator_type >	_Mybase
typedef _Traits::allocator_type	allocator_type
typedef _Traits::key_compare	key_compare
Public Types inherited from _Tree_buy< _Traits::value_type, _Traits::allocator_type >
typedef _Tree_alloc<!is_empty< _Traits::allocator_type >::value, _Tree_base_types< _Traits::value_type, _Traits::allocator_type > >	_Mybase
typedef _Mybase::_Alty	_Alty
typedef _Mybase::_Nodeptr	_Nodeptr
typedef _Mybase::value_type	value_type
Public Types inherited from _Tree_alloc<!is_empty< _Traits::allocator_type >::value, _Tree_base_types< _Traits::value_type, _Traits::allocator_type > >
typedef _Tree_alloc< _Al_has_storage, _Tree_base_types< _Traits::value_type, _Traits::allocator_type > >	_Myt
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Alloc	_Alloc
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Alnod_type	_Alty
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Node	_Node
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Nodeptr	_Nodeptr
Public Types inherited from _Tree_val< _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types >
enum	_Redbl
typedef _Tree_val< _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types >	_Myt
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types::_Nodeptr	_Nodeptr
typedef _Nodeptr &	_Nodepref
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types::value_type	value_type
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types::size_type	size_type
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types::difference_type	difference_type
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types::pointer	pointer
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types::const_pointer	const_pointer
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types::reference	reference
typedef _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types::const_reference	const_reference
typedef _Tree_const_iterator< _Myt >	const_iterator
typedef _Tree_iterator< _Myt >	iterator

Public Member Functions
	_Tree (const key_compare &_Parg, const allocator_type &_Al)
	_Tree (const value_type *_First, const value_type *_Last, const key_compare &_Parg, const allocator_type &_Al)
	_Tree (const _Myt &_Right, const allocator_type &_Al)
	_Tree (_Myt &&_Right)
	_Tree (_Myt &&_Right, const allocator_type &_Al)
_Myt &	operator= (_Myt &&_Right)
void	_Assign_rv (_Myt &&_Right, true_type)
void	_Assign_rv (_Myt &&_Right, false_type)
void	_Assign_rv (_Myt &&_Right)
_Pairib	insert (value_type &&_Val)
iterator	insert (const_iterator _Where, value_type &&_Val)
template<class _Valty >
enable_if< is_convertible< _Valty, value_type >::value, _Pairib >::type	insert (_Valty &&_Val)
template<class _Valty >
enable_if< is_convertible< _Valty, value_type >::value, iterator >::type	insert (const_iterator _Where, _Valty &&_Val)
template<class... _Valty>
_Pairib	emplace (_Valty &&..._Val)
template<class... _Valty>
iterator	emplace_hint (const_iterator _Where, _Valty &&..._Val)
	~_Tree () _NOEXCEPT
_Myt &	operator= (const _Myt &_Right)
iterator	begin () _NOEXCEPT
const_iterator	begin () const _NOEXCEPT
iterator	end () _NOEXCEPT
const_iterator	end () const _NOEXCEPT
reverse_iterator	rbegin () _NOEXCEPT
const_reverse_iterator	rbegin () const _NOEXCEPT
reverse_iterator	rend () _NOEXCEPT
const_reverse_iterator	rend () const _NOEXCEPT
const_iterator	cbegin () const _NOEXCEPT
const_iterator	cend () const _NOEXCEPT
const_reverse_iterator	crbegin () const _NOEXCEPT
const_reverse_iterator	crend () const _NOEXCEPT
size_type	size () const _NOEXCEPT
size_type	max_size () const _NOEXCEPT
bool	empty () const _NOEXCEPT
allocator_type	get_allocator () const _NOEXCEPT
key_compare	key_comp () const
value_compare	value_comp () const
_Pairib	insert (const value_type &_Val)
iterator	insert (const_iterator _Where, const value_type &_Val)
template<class _Iter >
void	insert (_Iter _First, _Iter _Last)
void	insert (_XSTD initializer_list< value_type > _Ilist)
iterator	erase (const_iterator _Where)
iterator	erase (const_iterator _First, const_iterator _Last)
size_type	erase (const key_type &_Keyval)
void	clear () _NOEXCEPT
iterator	find (const key_type &_Keyval)
const_iterator	find (const key_type &_Keyval) const
size_type	count (const key_type &_Keyval) const
iterator	lower_bound (const key_type &_Keyval)
const_iterator	lower_bound (const key_type &_Keyval) const
iterator	upper_bound (const key_type &_Keyval)
const_iterator	upper_bound (const key_type &_Keyval) const
_Pairii	equal_range (const key_type &_Keyval)
_Paircc	equal_range (const key_type &_Keyval) const
void	swap (_Myt &_Right)
Public Member Functions inherited from _Tree_comp< !is_empty< _Traits::key_compare >::value, _Traits >
	_Tree_comp (const key_compare &_Parg, const allocator_type &_Al)
key_compare &	_Getcomp ()
const key_compare &	_Getcomp () const
void	_Setcomp (const key_compare &_Right)
void	_Swapcomp (key_compare &_Right)
Public Member Functions inherited from _Tree_buy< _Traits::value_type, _Traits::allocator_type >
	_Tree_buy (const _Traits::allocator_type &_Al=_Traits::allocator_type())
_Nodeptr	_Buynode0 ()
void	_Freenode0 (_Nodeptr _Pnode)
_Nodeptr	_Buynode (_Valty &&..._Val)
Public Member Functions inherited from _Tree_alloc<!is_empty< _Traits::allocator_type >::value, _Tree_base_types< _Traits::value_type, _Traits::allocator_type > >
	_Tree_alloc (const _Alloc &_Al=_Alloc())
	~_Tree_alloc () _NOEXCEPT
void	_Change_alloc (const _Alty &_Al)
void	_Swap_alloc (_Myt &_Right)
_Nodeptr	_Buyheadnode ()
void	_Freeheadnode (_Nodeptr _Pnode)
_Alty &	_Getal ()
const _Alty &	_Getal () const
Public Member Functions inherited from _Tree_val< _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types >
	_Tree_val ()
Public Member Functions inherited from _Container_base0
void	_Orphan_all ()
void	_Swap_all (_Container_base0 &)

Protected Member Functions
template<class _Valty >
_Nodeptr	_Buynode_if_nil (_Nodeptr _Node, _Valty &&)
template<class _Valty >
_Nodeptr	_Buynode_if_nil (_Nil, _Valty &&_Val)
void	_Destroy_if_not_nil (_Nodeptr _Newnode)
void	_Destroy_if_not_nil (_Nil)
template<class _Valty , class _Nodety >
iterator	_Insert_hint (const_iterator _Where, _Valty &&_Val, _Nodety _Newnode)
template<class _Valty , class _Nodety >
_Pairib	_Insert_nohint (bool _Leftish, _Valty &&_Val, _Nodety _Newnode)
template<class _Valty , class _Nodety >
iterator	_Insert_at (bool _Addleft, _Nodeptr _Wherenode, _Valty &&_Val, _Nodety _Node)
template<class _Moveit >
void	_Copy (const _Myt &_Right, _Moveit _Movefl)
template<class _Want_to_move , class _Can_move , class _Is_set , class _Dummy >
_Nodeptr	_Copy_or_move (_Nodeptr _Rootnode, _Want_to_move, _Can_move, _Is_set, _Dummy)
template<class _Dummy >
_Nodeptr	_Copy_or_move (_Nodeptr _Rootnode, true_type, true_type, true_type, _Dummy)
template<class _Dummy >
_Nodeptr	_Copy_or_move (_Nodeptr _Rootnode, true_type, true_type, false_type, _Dummy)
template<class _Moveit >
_Nodeptr	_Copy_nodes (_Nodeptr _Rootnode, _Nodeptr _Wherenode, _Moveit _Movefl)
_Paircc	_Eqrange (const key_type &_Keyval) const
_Pairii	_Eqrange (const key_type &_Keyval)
void	_Erase (_Nodeptr _Rootnode)
_Nodeptr	_Lbound (const key_type &_Keyval) const
_Nodeptr	_Lbound (const key_type &_Keyval)
_Nodeptr &	_Lmost () const
void	_Lrotate (_Nodeptr _Wherenode)
_Nodeptr &	_Rmost () const
_Nodeptr &	_Root () const
void	_Rrotate (_Nodeptr _Wherenode)
_Nodeptr	_Ubound (const key_type &_Keyval) const
_Nodeptr	_Ubound (const key_type &_Keyval)
void	_Tidy ()
const key_type &	_Kfn (const value_type &_Val) const
const key_type &	_Key (_Nodeptr _Pnode) const

Additional Inherited Members
Static Public Member Functions inherited from _Tree_val< _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types >
static char &	_Color (_Nodeptr _Pnode)
static char &	_Isnil (_Nodeptr _Pnode)
static _Nodepref	_Left (_Nodeptr _Pnode)
static _Nodepref	_Parent (_Nodeptr _Pnode)
static _Nodepref	_Right (_Nodeptr _Pnode)
static reference	_Myval (_Nodeptr _Pnode)
static _Nodeptr	_Max (_Nodeptr _Pnode)
static _Nodeptr	_Min (_Nodeptr _Pnode)
Public Attributes inherited from _Tree_comp< !is_empty< _Traits::key_compare >::value, _Traits >
key_compare	comp
Public Attributes inherited from _Tree_alloc<!is_empty< _Traits::allocator_type >::value, _Tree_base_types< _Traits::value_type, _Traits::allocator_type > >
_Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Alnod_type	_Alnod
Public Attributes inherited from _Tree_val< _Tree_base_types< _Traits::value_type, _Traits::allocator_type >::_Val_types >
_Nodeptr	_Myhead
size_type	_Mysize

Member Typedef Documentation

template<class _Traits>

typedef _Mybase::_Alty _Tree< _Traits >::_Alty

template<class _Traits>

typedef _Tree_comp< !is_empty<typename _Traits::key_compare>::value, _Traits> _Tree< _Traits >::_Mybase

template<class _Traits>

typedef _Tree<_Traits> _Tree< _Traits >::_Myt

template<class _Traits>

typedef _Mybase::_Node _Tree< _Traits >::_Node

template<class _Traits>

typedef _Mybase::_Nodeptr _Tree< _Traits >::_Nodeptr

template<class _Traits>

typedef pair<const_iterator, const_iterator> _Tree< _Traits >::_Paircc

template<class _Traits>

typedef pair<iterator, bool> _Tree< _Traits >::_Pairib

template<class _Traits>

typedef pair<iterator, iterator> _Tree< _Traits >::_Pairii

template<class _Traits>

typedef _Mybase::allocator_type _Tree< _Traits >::allocator_type

template<class _Traits>

typedef _Mybase::const_iterator _Tree< _Traits >::const_iterator

template<class _Traits>

typedef _Mybase::const_pointer _Tree< _Traits >::const_pointer

template<class _Traits>

typedef _Mybase::const_reference _Tree< _Traits >::const_reference

template<class _Traits>

typedef _STD reverse_iterator<const_iterator> _Tree< _Traits >::const_reverse_iterator

template<class _Traits>

typedef _Mybase::difference_type _Tree< _Traits >::difference_type

template<class _Traits>

typedef _If<is_same<key_type, value_type>::value, typename _Mybase::const_iterator, typename _Mybase::iterator>::type _Tree< _Traits >::iterator

template<class _Traits>

typedef _Mybase::key_compare _Tree< _Traits >::key_compare

template<class _Traits>

typedef _Traits::key_type _Tree< _Traits >::key_type

template<class _Traits>

typedef _Mybase::pointer _Tree< _Traits >::pointer

template<class _Traits>

typedef _Mybase::reference _Tree< _Traits >::reference

template<class _Traits>

typedef _STD reverse_iterator<iterator> _Tree< _Traits >::reverse_iterator

template<class _Traits>

typedef _Mybase::size_type _Tree< _Traits >::size_type

template<class _Traits>

typedef _Traits::value_compare _Tree< _Traits >::value_compare

template<class _Traits>

typedef _Mybase::value_type _Tree< _Traits >::value_type

Member Enumeration Documentation

template<class _Traits>

anonymous enum

Enumerator
_Multi

        {   // get multi parameter
        _Multi = _Traits::_Multi};

Constructor & Destructor Documentation

template<class _Traits>

_Tree< _Traits >::_Tree ( const key_compare &  _Parg, const allocator_type &  _Al  )

inline

        : _Mybase(_Parg, _Al)
        {   // construct empty tree
        }

template<class _Traits>

_Tree< _Traits >::_Tree ( const value_type *  _First, const value_type *  _Last, const key_compare &  _Parg, const allocator_type &  _Al  )

inline

        : _Mybase(_Parg, _Al)
        {   // construct tree from [_First, _Last) array
        _TRY_BEGIN
        insert(_First, _Last);
        _CATCH_ALL
        _Tidy();
        _RERAISE;
        _CATCH_END
        }

template<class _Traits>

_Tree< _Traits >::_Tree ( const _Myt &  _Right, const allocator_type &  _Al  )

inline

        : _Mybase(_Right.key_comp(), _Al)
        {   // construct tree by copying _Right, allocator
        _TRY_BEGIN
        _Copy(_Right, false_type());
        _CATCH_ALL
        _Tidy();
        _RERAISE;
        _CATCH_END
        }

template<class _Traits>

_Tree< _Traits >::_Tree ( _Myt &&  _Right )

inline

        : _Mybase(_Right.key_comp(), _Right._Getal())
        {   // construct tree by moving _Right
        _Assign_rv(_STD forward<_Myt>(_Right), true_type());
        }

template<class _Traits>

_Tree< _Traits >::_Tree ( _Myt &&  _Right, const allocator_type &  _Al  )

inline

        : _Mybase(_Right.key_comp(), _Al)
        {   // construct tree by moving _Right, allocator
        _Assign_rv(_STD forward<_Myt>(_Right));
        }

template<class _Traits>

_Tree< _Traits >::~_Tree ( )

inline

        {   // destroy tree
        _Tidy();
        }

Member Function Documentation

template<class _Traits>

void _Tree< _Traits >::_Assign_rv ( _Myt &&  _Right, true_type    )

inline

        {   // move from _Right, stealing its contents
        this->_Swap_all(_Right);
        this->_Swapcomp(_Right._Getcomp());
        _Swap_adl(this->_Myhead, _Right._Myhead);
        _STD swap(this->_Mysize, _Right._Mysize);
        }

template<class _Traits>

void _Tree< _Traits >::_Assign_rv ( _Myt &&  _Right, false_type    )

inline

        {   // move from _Right, possibly moving its contents
        if (get_allocator() == _Right.get_allocator())
            _Assign_rv(_STD forward<_Myt>(_Right), true_type());
        else
            _Copy(_Right, true_type());
        }

template<class _Traits>

void _Tree< _Traits >::_Assign_rv ( _Myt &&  _Right )

inline

        {   // assign by moving _Right
        _Assign_rv(_STD forward<_Myt>(_Right),
            typename _Alty::propagate_on_container_move_assignment());
        }

template<class _Traits>

template<class _Valty >

_Nodeptr _Tree< _Traits >::_Buynode_if_nil ( _Nodeptr  _Node, _Valty &&    )

inlineprotected

        {   // node exists, just return it
        return (_Node);
        }

template<class _Traits>

template<class _Valty >

_Nodeptr _Tree< _Traits >::_Buynode_if_nil ( _Nil  , _Valty &&  _Val  )

inlineprotected

        {   // node doesn't exist, make it
        return (this->_Buynode(_STD forward<_Valty>(_Val)));
        }

template<class _Traits>

template<class _Moveit >

void _Tree< _Traits >::_Copy ( const _Myt &  _Right, _Moveit  _Movefl  )

inlineprotected

        {   // copy or move entire tree from _Right
        _Root() = _Copy_nodes(_Right._Root(), this->_Myhead, _Movefl);
        this->_Mysize = _Right.size();
        if (!this->_Isnil(_Root()))
            {   // nonempty tree, look for new smallest and largest
            _Lmost() = this->_Min(_Root());
            _Rmost() = this->_Max(_Root());
            }
        else
            {   // empty tree, just tidy head pointers
            _Lmost() = this->_Myhead;
            _Rmost() = this->_Myhead;
            }
        }

template<class _Traits>

template<class _Moveit >

_Nodeptr _Tree< _Traits >::_Copy_nodes ( _Nodeptr  _Rootnode, _Nodeptr  _Wherenode, _Moveit  _Movefl  )

inlineprotected

        {   // copy entire subtree, recursively
        _Nodeptr _Newroot = this->_Myhead;  // point at nil node

        if (!this->_Isnil(_Rootnode))
            {   // copy or move a node, then any subtrees
            _Nodeptr _Pnode = _Copy_or_move(_Rootnode, _Movefl,
                typename is_move_constructible<value_type>::type(),
                typename is_same<key_type, value_type>::type(), 0);
            _Pnode->_Parent = _Wherenode;
            _Pnode->_Color = this->_Color(_Rootnode);
            if (this->_Isnil(_Newroot))
                _Newroot = _Pnode;  // memorize new root

            _TRY_BEGIN
            this->_Left(_Pnode) =
                _Copy_nodes(this->_Left(_Rootnode), _Pnode, _Movefl);
            this->_Right(_Pnode) =
                _Copy_nodes(this->_Right(_Rootnode), _Pnode, _Movefl);
            _CATCH_ALL
            _Erase(_Newroot);   // subtree copy failed, bail out
            _RERAISE;
            _CATCH_END
            }

        return (_Newroot);  // return newly constructed tree
        }

template<class _Traits>

template<class _Want_to_move , class _Can_move , class _Is_set , class _Dummy >

_Nodeptr _Tree< _Traits >::_Copy_or_move ( _Nodeptr  _Rootnode, _Want_to_move  , _Can_move  , _Is_set  , _Dummy    )

inlineprotected

        {   // copy to new node -- nonmovable
        return (this->_Buynode(this->_Myval(_Rootnode)));
        }

template<class _Traits>

template<class _Dummy >

_Nodeptr _Tree< _Traits >::_Copy_or_move ( _Nodeptr  _Rootnode, true_type  , true_type  , true_type  , _Dummy    )

inlineprotected

        {   // move to new node -- movable, set
        return (this->_Buynode(
            _STD forward<value_type>(this->_Myval(_Rootnode))));
        }

template<class _Traits>

template<class _Dummy >

_Nodeptr _Tree< _Traits >::_Copy_or_move ( _Nodeptr  _Rootnode, true_type  , true_type  , false_type  , _Dummy    )

inlineprotected

        {   // move to new node -- movable, map
        return (this->_Buynode(
            _STD forward<key_type>(const_cast<key_type&>(
                this->_Myval(_Rootnode).first)),
            _STD forward<typename value_type::second_type>(this->_Myval(
                _Rootnode).second)));
        }

template<class _Traits>

void _Tree< _Traits >::_Destroy_if_not_nil ( _Nodeptr  _Newnode )

inlineprotected

        {   // node exists, destroy it
        this->_Getal().destroy(
            _STD addressof(this->_Myval(_Newnode)));

        this->_Getal().deallocate(_Newnode, 1);
        }

template<class _Traits>

void _Tree< _Traits >::_Destroy_if_not_nil ( _Nil  )

inlineprotected

        {   // node doesn't exist, do nothing
        }

template<class _Traits>

_Paircc _Tree< _Traits >::_Eqrange ( const key_type &  _Keyval ) const

inlineprotected

        {   // find leftmost node not less than _Keyval
        _Nodeptr _Pnode = _Root();
        _Nodeptr _Lonode = this->_Myhead;   // end() if search fails
        _Nodeptr _Hinode = this->_Myhead;   // end() if search fails

        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Pnode), _Keyval))
                _Pnode = this->_Right(_Pnode);  // descend right subtree
            else
                {   // _Pnode not less than _Keyval, remember it
                if (this->_Isnil(_Hinode)
                        && _DEBUG_LT_PRED(this->_Getcomp(), _Keyval,
                        this->_Key(_Pnode)))
                    _Hinode = _Pnode;   // _Pnode greater, remember it
                _Lonode = _Pnode;
                _Pnode = this->_Left(_Pnode);   // descend left subtree
                }

        _Pnode = this->_Isnil(_Hinode) ? _Root()
            : this->_Left(_Hinode); // continue scan for upper bound
        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Pnode)))
                {   // _Pnode greater than _Keyval, remember it
                _Hinode = _Pnode;
                _Pnode = this->_Left(_Pnode);   // descend left subtree
                }
            else
                _Pnode = this->_Right(_Pnode);  // descend right subtree

        const_iterator _First = const_iterator(_Lonode, this);
        const_iterator _Last = const_iterator(_Hinode, this);
        return (_Paircc(_First, _Last));
        }

template<class _Traits>

_Pairii _Tree< _Traits >::_Eqrange ( const key_type &  _Keyval )

inlineprotected

        {   // find leftmost node not less than _Keyval
        _Nodeptr _Pnode = _Root();
        _Nodeptr _Lonode = this->_Myhead;   // end() if search fails
        _Nodeptr _Hinode = this->_Myhead;   // end() if search fails

        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Pnode), _Keyval))
                _Pnode = this->_Right(_Pnode);  // descend right subtree
            else
                {   // _Pnode not less than _Keyval, remember it
                if (this->_Isnil(_Hinode)
                        && _DEBUG_LT_PRED(this->_Getcomp(), _Keyval,
                         this->_Key(_Pnode)))
                    _Hinode = _Pnode;   // _Pnode greater, remember it
                _Lonode = _Pnode;
                _Pnode = this->_Left(_Pnode);   // descend left subtree
                }

        _Pnode = this->_Isnil(_Hinode) ? _Root()
            : this->_Left(_Hinode); // continue scan for upper bound
        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Pnode)))
                {   // _Pnode greater than _Keyval, remember it
                _Hinode = _Pnode;
                _Pnode = this->_Left(_Pnode);   // descend left subtree
                }
            else
                _Pnode = this->_Right(_Pnode);  // descend right subtree

        iterator _First = iterator(_Lonode, this);
        iterator _Last = iterator(_Hinode, this);
        return (_Pairii(_First, _Last));
        }

template<class _Traits>

void _Tree< _Traits >::_Erase ( _Nodeptr  _Rootnode )

inlineprotected

        {   // free entire subtree, recursively
        for (_Nodeptr _Pnode = _Rootnode;
            !this->_Isnil(_Pnode); _Rootnode = _Pnode)
            {   // free subtrees, then node
            _Erase(this->_Right(_Pnode));
            _Pnode = this->_Left(_Pnode);
            this->_Getal().destroy(
                _STD addressof(this->_Myval(_Rootnode)));

            this->_Getal().deallocate(_Rootnode, 1);
            }
        }

template<class _Traits>

template<class _Valty , class _Nodety >

iterator _Tree< _Traits >::_Insert_at ( bool  _Addleft, _Nodeptr  _Wherenode, _Valty &&  _Val, _Nodety  _Node  )

inlineprotected

        {   // add node with value next to _Wherenode, to left if _Addleft
        if (max_size() - 1 <= this->_Mysize)
            {   // tree would get too big, fail
            _Destroy_if_not_nil(_Node);
            _Xlength_error("map/set<T> too long");
            }
        _Nodeptr _Newnode = _Buynode_if_nil(_Node,
            _STD forward<_Valty>(_Val));

        ++this->_Mysize;
        _Newnode->_Parent = _Wherenode;

        if (_Wherenode == this->_Myhead)
            {   // first node in tree, just set head values
            _Root() = _Newnode;
            _Lmost() = _Newnode;
            _Rmost() = _Newnode;
            }
        else if (_Addleft)
            {   // add to left of _Wherenode
            this->_Left(_Wherenode) = _Newnode;
            if (_Wherenode == _Lmost())
                _Lmost() = _Newnode;
            }
        else
            {   // add to right of _Wherenode
            this->_Right(_Wherenode) = _Newnode;
            if (_Wherenode == _Rmost())
                _Rmost() = _Newnode;
            }

        for (_Nodeptr _Pnode = _Newnode;
            this->_Color(this->_Parent(_Pnode)) == this->_Red; )
            if (this->_Parent(_Pnode)
                == this->_Left(this->_Parent(this->_Parent(_Pnode))))
                {   // fixup red-red in left subtree
                _Wherenode =
                    this->_Right(this->_Parent(this->_Parent(_Pnode)));
                if (this->_Color(_Wherenode) == this->_Red)
                    {   // parent has two red children, blacken both
                    this->_Color(this->_Parent(_Pnode)) = this->_Black;
                    this->_Color(_Wherenode) = this->_Black;
                    this->_Color(this->_Parent(this->_Parent(_Pnode)))
                        = this->_Red;
                    _Pnode = this->_Parent(this->_Parent(_Pnode));
                    }
                else
                    {   // parent has red and black children
                    if (_Pnode == this->_Right(this->_Parent(_Pnode)))
                        {   // rotate right child to left
                        _Pnode = this->_Parent(_Pnode);
                        _Lrotate(_Pnode);
                        }
                    this->_Color(this->_Parent(_Pnode)) =
                        this->_Black;   // propagate red up
                    this->_Color(this->_Parent(this->_Parent(_Pnode))) =
                        this->_Red;
                    _Rrotate(this->_Parent(this->_Parent(_Pnode)));
                    }
                }
            else
                {   // fixup red-red in right subtree
                _Wherenode =
                    this->_Left(this->_Parent(this->_Parent(_Pnode)));
                if (this->_Color(_Wherenode) == this->_Red)
                    {   // parent has two red children, blacken both
                    this->_Color(this->_Parent(_Pnode)) = this->_Black;
                    this->_Color(_Wherenode) = this->_Black;
                    this->_Color(this->_Parent(this->_Parent(_Pnode))) =
                        this->_Red;
                    _Pnode = this->_Parent(this->_Parent(_Pnode));
                    }
                else
                    {   // parent has red and black children
                    if (_Pnode == this->_Left(this->_Parent(_Pnode)))
                        {   // rotate left child to right
                        _Pnode = this->_Parent(_Pnode);
                        _Rrotate(_Pnode);
                        }
                    this->_Color(this->_Parent(_Pnode)) =
                        this->_Black;   // propagate red up
                    this->_Color(this->_Parent(this->_Parent(_Pnode))) =
                        this->_Red;
                    _Lrotate(this->_Parent(this->_Parent(_Pnode)));
                    }
                }

        this->_Color(_Root()) = this->_Black;   // root is always black
        return (iterator(_Newnode, this));
        }

template<class _Traits>

template<class _Valty , class _Nodety >

iterator _Tree< _Traits >::_Insert_hint ( const_iterator  _Where, _Valty &&  _Val, _Nodety  _Newnode  )

inlineprotected

        {   // try to insert node using _Where as a hint
        const_iterator _Next;
        bool _Leftish = false;  // assume nearest point is end of sequence

        _TRY_BEGIN

 #if _ITERATOR_DEBUG_LEVEL == 2
        if (_Where._Getcont() != this)
            _DEBUG_ERROR("map/set insert iterator outside range");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

        if (size() == 0)
            return (_Insert_at(true, this->_Myhead,
                _STD forward<_Valty>(_Val), _Newnode)); // empty tree
        else if (this->_Multi)
            {   // insert even if duplicate
            if (_Where == begin())
                {   // insert at beginning if before first element
                if (!_DEBUG_LT_PRED(this->_Getcomp(),
                    this->_Key(_Where._Mynode()), this->_Kfn(_Val)))
                    return (_Insert_at(true, _Where._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                _Leftish = true;    // nearest point is beginning of sequence
                }
            else if (_Where == end())
                {   // insert at end if after last element
                if (!_DEBUG_LT_PRED(this->_Getcomp(),
                    this->_Kfn(_Val), this->_Key(_Rmost())))
                    return (_Insert_at(false, _Rmost(),
                        _STD forward<_Valty>(_Val), _Newnode));
                }
            else if (!_DEBUG_LT_PRED(this->_Getcomp(),
                this->_Key(_Where._Mynode()), this->_Kfn(_Val))
                && !_DEBUG_LT_PRED(this->_Getcomp(),
                    this->_Kfn(_Val),
                    this->_Key((--(_Next = _Where))._Mynode())))
                {   // insert before _Where
                if (this->_Isnil(this->_Right(_Next._Mynode())))
                    return (_Insert_at(false, _Next._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                else
                    return (_Insert_at(true, _Where._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                }
            else if (!_DEBUG_LT_PRED(this->_Getcomp(),
                this->_Kfn(_Val), this->_Key(_Where._Mynode()))
                && (++(_Next = _Where) == end()
                    || !_DEBUG_LT_PRED(this->_Getcomp(),
                        this->_Key(_Next._Mynode()), this->_Kfn(_Val))))
                {   // insert after _Where
                if (this->_Isnil(this->_Right(_Where._Mynode())))
                    return (_Insert_at(false, _Where._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                else
                    return (_Insert_at(true, _Next._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                }
            else
                _Leftish = true;    // nearest point is beginning of sequence
            }
        else
            {   // insert only if unique
            if (_Where == begin())
                {   // insert at beginning if before first element
                if (_DEBUG_LT_PRED(this->_Getcomp(),
                    this->_Kfn(_Val), this->_Key(_Where._Mynode())))
                    return (_Insert_at(true, _Where._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                }
            else if (_Where == end())
                {   // insert at end if after last element
                if (_DEBUG_LT_PRED(this->_Getcomp(),
                    this->_Key(_Rmost()), this->_Kfn(_Val)))
                    return (_Insert_at(false, _Rmost(),
                        _STD forward<_Valty>(_Val), _Newnode));
                }
            else if (_DEBUG_LT_PRED(this->_Getcomp(),
                this->_Kfn(_Val), this->_Key(_Where._Mynode()))
                && _DEBUG_LT_PRED(this->_Getcomp(),
                    this->_Key((--(_Next = _Where))._Mynode()),
                    this->_Kfn(_Val)))
                {   // insert before _Where
                if (this->_Isnil(this->_Right(_Next._Mynode())))
                    return (_Insert_at(false, _Next._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                else
                    return (_Insert_at(true, _Where._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                }
            else if (_DEBUG_LT_PRED(this->_Getcomp(),
                this->_Key(_Where._Mynode()), this->_Kfn(_Val))
                && (++(_Next = _Where) == end()
                    || _DEBUG_LT_PRED(this->_Getcomp(),
                        this->_Kfn(_Val), this->_Key(_Next._Mynode()))))
                {   // insert after _Where
                if (this->_Isnil(this->_Right(_Where._Mynode())))
                    return (_Insert_at(false, _Where._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                else
                    return (_Insert_at(true, _Next._Mynode(),
                        _STD forward<_Valty>(_Val), _Newnode));
                }
            }
        _CATCH_ALL
        _Destroy_if_not_nil(_Newnode);
        _RERAISE;
        _CATCH_END

        return (_Insert_nohint(_Leftish,
            _STD forward<_Valty>(_Val), _Newnode).first);
        }

template<class _Traits>

template<class _Valty , class _Nodety >

_Pairib _Tree< _Traits >::_Insert_nohint ( bool  _Leftish, _Valty &&  _Val, _Nodety  _Newnode  )

inlineprotected

        {   // try to insert node, on left if _Leftish
        _TRY_BEGIN
        _Nodeptr _Trynode = _Root();
        _Nodeptr _Wherenode = this->_Myhead;
        bool _Addleft = true;   // add to left of head if tree empty

        while (!this->_Isnil(_Trynode))
            {   // look for leaf to insert before (_Addleft) or after
            _Wherenode = _Trynode;
            if (_Leftish)
                _Addleft = !_DEBUG_LT_PRED(this->_Getcomp(),
                    this->_Key(_Trynode),
                    this->_Kfn(_Val));  // favor left end
            else
                _Addleft = _DEBUG_LT_PRED(this->_Getcomp(),
                    this->_Kfn(_Val),
                    this->_Key(_Trynode));  // favor right end
            _Trynode = _Addleft ? this->_Left(_Trynode)
                : this->_Right(_Trynode);
            }

        if (this->_Multi)
            return (_Pairib(_Insert_at(_Addleft, _Wherenode,
                _STD forward<_Valty>(_Val), _Newnode), true));
        else
            {   // insert only if unique
            iterator _Where = iterator(_Wherenode, this);
            if (!_Addleft)
                ;   // need to test if insert after is okay
            else if (_Where == begin())
                return (_Pairib(_Insert_at(true, _Wherenode,
                    _STD forward<_Valty>(_Val), _Newnode), true));
            else
                --_Where;   // need to test if insert before is okay

            if (_DEBUG_LT_PRED(this->_Getcomp(),
                this->_Key(_Where._Mynode()),
                this->_Kfn(_Val)))
                return (_Pairib(_Insert_at(_Addleft, _Wherenode,
                    _STD forward<_Valty>(_Val), _Newnode), true));
            else
                {   // duplicate, don't insert
                _Destroy_if_not_nil(_Newnode);
                return (_Pairib(_Where, false));
                }
            }
        _CATCH_ALL
        _Destroy_if_not_nil(_Newnode);
        _RERAISE;
        _CATCH_END
        }

template<class _Traits>

const key_type& _Tree< _Traits >::_Key ( _Nodeptr  _Pnode ) const

inlineprotected

        {   // return reference to key in node
        return ((const key_type&)this->_Kfn(this->_Myval(_Pnode)));
        }

template<class _Traits>

const key_type& _Tree< _Traits >::_Kfn ( const value_type &  _Val ) const

inlineprotected

        {   // get key from value
        return (_Traits::_Kfn(_Val));
        }

template<class _Traits>

_Nodeptr _Tree< _Traits >::_Lbound ( const key_type &  _Keyval ) const

inlineprotected

        {   // find leftmost node not less than _Keyval
        _Nodeptr _Pnode = _Root();
        _Nodeptr _Wherenode = this->_Myhead;    // end() if search fails

        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Pnode), _Keyval))
                _Pnode = this->_Right(_Pnode);  // descend right subtree
            else
                {   // _Pnode not less than _Keyval, remember it
                _Wherenode = _Pnode;
                _Pnode = this->_Left(_Pnode);   // descend left subtree
                }

        return (_Wherenode);    // return best remembered candidate
        }

template<class _Traits>

_Nodeptr _Tree< _Traits >::_Lbound ( const key_type &  _Keyval )

inlineprotected

        {   // find leftmost node not less than _Keyval
        _Nodeptr _Pnode = _Root();
        _Nodeptr _Wherenode = this->_Myhead;    // end() if search fails

        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Pnode), _Keyval))
                _Pnode = this->_Right(_Pnode);  // descend right subtree
            else
                {   // _Pnode not less than _Keyval, remember it
                _Wherenode = _Pnode;
                _Pnode = this->_Left(_Pnode);   // descend left subtree
                }

        return (_Wherenode);    // return best remembered candidate
        }

template<class _Traits>

_Nodeptr& _Tree< _Traits >::_Lmost ( ) const

inlineprotected

        {   // return leftmost node in nonmutable tree
        return (this->_Left(this->_Myhead));
        }

template<class _Traits>

void _Tree< _Traits >::_Lrotate ( _Nodeptr  _Wherenode )

inlineprotected

        {   // promote right node to root of subtree
        _Nodeptr _Pnode = this->_Right(_Wherenode);
        this->_Right(_Wherenode) = this->_Left(_Pnode);

        if (!this->_Isnil(this->_Left(_Pnode)))
            this->_Parent(this->_Left(_Pnode)) = _Wherenode;
        this->_Parent(_Pnode) = this->_Parent(_Wherenode);

        if (_Wherenode == _Root())
            _Root() = _Pnode;
        else if (_Wherenode == this->_Left(this->_Parent(_Wherenode)))
            this->_Left(this->_Parent(_Wherenode)) = _Pnode;
        else
            this->_Right(this->_Parent(_Wherenode)) = _Pnode;

        this->_Left(_Pnode) = _Wherenode;
        this->_Parent(_Wherenode) = _Pnode;
        }

template<class _Traits>

_Nodeptr& _Tree< _Traits >::_Rmost ( ) const

inlineprotected

        {   // return rightmost node in nonmutable tree
        return (this->_Right(this->_Myhead));
        }

template<class _Traits>

_Nodeptr& _Tree< _Traits >::_Root ( ) const

inlineprotected

        {   // return root of nonmutable tree
        return (this->_Parent(this->_Myhead));
        }

template<class _Traits>

void _Tree< _Traits >::_Rrotate ( _Nodeptr  _Wherenode )

inlineprotected

        {   // promote left node to root of subtree
        _Nodeptr _Pnode = this->_Left(_Wherenode);
        this->_Left(_Wherenode) = this->_Right(_Pnode);

        if (!this->_Isnil(this->_Right(_Pnode)))
            this->_Parent(this->_Right(_Pnode)) = _Wherenode;
        this->_Parent(_Pnode) = this->_Parent(_Wherenode);

        if (_Wherenode == _Root())
            _Root() = _Pnode;
        else if (_Wherenode == this->_Right(this->_Parent(_Wherenode)))
            this->_Right(this->_Parent(_Wherenode)) = _Pnode;
        else
            this->_Left(this->_Parent(_Wherenode)) = _Pnode;

        this->_Right(_Pnode) = _Wherenode;
        this->_Parent(_Wherenode) = _Pnode;
        }

template<class _Traits>

void _Tree< _Traits >::_Tidy ( )

inlineprotected

        {   // free all storage
        erase(begin(), end());
        }

template<class _Traits>

_Nodeptr _Tree< _Traits >::_Ubound ( const key_type &  _Keyval ) const

inlineprotected

        {   // find leftmost node greater than _Keyval
        _Nodeptr _Pnode = _Root();
        _Nodeptr _Wherenode = this->_Myhead;    // end() if search fails

        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Pnode)))
                {   // _Pnode greater than _Keyval, remember it
                _Wherenode = _Pnode;
                _Pnode = this->_Left(_Pnode);   // descend left subtree
                }
            else
                _Pnode = this->_Right(_Pnode);  // descend right subtree

        return (_Wherenode);    // return best remembered candidate
        }

template<class _Traits>

_Nodeptr _Tree< _Traits >::_Ubound ( const key_type &  _Keyval )

inlineprotected

        {   // find leftmost node greater than _Keyval
        _Nodeptr _Pnode = _Root();
        _Nodeptr _Wherenode = this->_Myhead;    // end() if search fails

        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Pnode)))
                {   // _Pnode greater than _Keyval, remember it
                _Wherenode = _Pnode;
                _Pnode = this->_Left(_Pnode);   // descend left subtree
                }
            else
                _Pnode = this->_Right(_Pnode);  // descend right subtree

        return (_Wherenode);    // return best remembered candidate
        }

template<class _Traits>

iterator _Tree< _Traits >::begin ( )

inline

        {   // return iterator for beginning of mutable sequence
        return (iterator(_Lmost(), this));
        }

template<class _Traits>

const_iterator _Tree< _Traits >::begin ( ) const

inline

        {   // return iterator for beginning of nonmutable sequence
        return (const_iterator(_Lmost(), this));
        }

template<class _Traits>

const_iterator _Tree< _Traits >::cbegin ( ) const

inline

        {   // return iterator for beginning of nonmutable sequence
        return (((const _Myt *)this)->begin());
        }

template<class _Traits>

const_iterator _Tree< _Traits >::cend ( ) const

inline

        {   // return iterator for end of nonmutable sequence
        return (((const _Myt *)this)->end());
        }

template<class _Traits>

void _Tree< _Traits >::clear ( )

inline

        {   // erase all
 #if _ITERATOR_DEBUG_LEVEL == 2
        this->_Orphan_ptr(*this, 0);
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

        _Erase(_Root());
        _Root() = this->_Myhead;
        _Lmost() = this->_Myhead;
        _Rmost() = this->_Myhead;
        this->_Mysize = 0;
        }

template<class _Traits>

size_type _Tree< _Traits >::count ( const key_type &  _Keyval ) const

inline

        {   // count all elements that match _Keyval
        _Paircc _Ans = equal_range(_Keyval);
        size_type _Num = 0;
        _Distance(_Ans.first, _Ans.second, _Num);
        return (_Num);
        }

template<class _Traits>

const_reverse_iterator _Tree< _Traits >::crbegin ( ) const

inline

        {   // return iterator for beginning of reversed nonmutable sequence
        return (((const _Myt *)this)->rbegin());
        }

template<class _Traits>

const_reverse_iterator _Tree< _Traits >::crend ( ) const

inline

        {   // return iterator for end of reversed nonmutable sequence
        return (((const _Myt *)this)->rend());
        }

template<class _Traits>

template<class... _Valty>

_Pairib _Tree< _Traits >::emplace ( _Valty &&...  _Val )

inline

        {   // try to insert value_type(_Val...), favoring right side
        _Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val)...);
        return (_Insert_nohint(false,
            this->_Myval(_Newnode), _Newnode));
        }

template<class _Traits>

template<class... _Valty>

iterator _Tree< _Traits >::emplace_hint ( const_iterator  _Where, _Valty &&...  _Val  )

inline

        {   // insert value_type(_Val...) at _Where
        _Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val)...);
        return (_Insert_hint(_Where,
            this->_Myval(_Newnode), _Newnode));
        }

template<class _Traits>

bool _Tree< _Traits >::empty ( ) const

inline

        {   // return true only if sequence is empty
        return (size() == 0);
        }

template<class _Traits>

iterator _Tree< _Traits >::end ( )

inline

        {   // return iterator for end of mutable sequence
        return (iterator(this->_Myhead, this));
        }

template<class _Traits>

const_iterator _Tree< _Traits >::end ( ) const

inline

        {   // return iterator for end of nonmutable sequence
        return (const_iterator(this->_Myhead, this));
        }

template<class _Traits>

_Pairii _Tree< _Traits >::equal_range ( const key_type &  _Keyval )

inline

        {   // find range equivalent to _Keyval in mutable tree
        return (_Eqrange(_Keyval));
        }

template<class _Traits>

_Paircc _Tree< _Traits >::equal_range ( const key_type &  _Keyval ) const

inline

        {   // find range equivalent to _Keyval in nonmutable tree
        return (_Eqrange(_Keyval));
        }

template<class _Traits>

iterator _Tree< _Traits >::erase ( const_iterator  _Where )

inline

        {   // erase element at _Where
 #if _ITERATOR_DEBUG_LEVEL == 2
        if (_Where._Getcont() != this || this->_Isnil(_Where._Mynode()))
            _DEBUG_ERROR("map/set erase iterator outside range");
        _Nodeptr _Erasednode = _Where._Mynode();    // node to erase
        ++_Where;   // save successor iterator for return
        _Orphan_ptr(*this, _Erasednode);

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
        _Nodeptr _Erasednode = _Where._Mynode();    // node to erase
        ++_Where;   // save successor iterator for return
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

        _Nodeptr _Fixnode;  // the node to recolor as needed
        _Nodeptr _Fixnodeparent;    // parent of _Fixnode (which may be nil)
        _Nodeptr _Pnode = _Erasednode;

        if (this->_Isnil(this->_Left(_Pnode)))
            _Fixnode = this->_Right(_Pnode);    // stitch up right subtree
        else if (this->_Isnil(this->_Right(_Pnode)))
            _Fixnode = this->_Left(_Pnode); // stitch up left subtree
        else
            {   // two subtrees, must lift successor node to replace erased
            _Pnode = _Where._Mynode();  // _Pnode is successor node
            _Fixnode = this->_Right(_Pnode);    // _Fixnode is only subtree
            }

        if (_Pnode == _Erasednode)
            {   // at most one subtree, relink it
            _Fixnodeparent = this->_Parent(_Erasednode);
            if (!this->_Isnil(_Fixnode))
                this->_Parent(_Fixnode) = _Fixnodeparent;   // link up

            if (_Root() == _Erasednode)
                _Root() = _Fixnode; // link down from root
            else if (this->_Left(_Fixnodeparent) == _Erasednode)
                this->_Left(_Fixnodeparent) = _Fixnode; // link down to left
            else
                this->_Right(_Fixnodeparent) =
                    _Fixnode;   // link down to right

            if (_Lmost() == _Erasednode)
                _Lmost() = this->_Isnil(_Fixnode)
                    ? _Fixnodeparent    // smallest is parent of erased node
                    : this->_Min(_Fixnode); // smallest in relinked subtree

            if (_Rmost() == _Erasednode)
                _Rmost() = this->_Isnil(_Fixnode)
                    ? _Fixnodeparent    // largest is parent of erased node
                    : this->_Max(_Fixnode); // largest in relinked subtree
            }
        else
            {   // erased has two subtrees, _Pnode is successor to erased
            this->_Parent(this->_Left(_Erasednode)) =
                _Pnode; // link left up
            this->_Left(_Pnode) =
                this->_Left(_Erasednode);   // link successor down

            if (_Pnode == this->_Right(_Erasednode))
                _Fixnodeparent = _Pnode;    // successor is next to erased
            else
                {   // successor further down, link in place of erased
                _Fixnodeparent =
                    this->_Parent(_Pnode);  // parent is successor's
                if (!this->_Isnil(_Fixnode))
                    this->_Parent(_Fixnode) = _Fixnodeparent;   // link fix up
                this->_Left(_Fixnodeparent) = _Fixnode; // link fix down
                this->_Right(_Pnode) =
                    this->_Right(_Erasednode);  // link next down
                this->_Parent(this->_Right(_Erasednode)) =
                    _Pnode; // right up
                }

            if (_Root() == _Erasednode)
                _Root() = _Pnode;   // link down from root
            else if (this->_Left(this->_Parent(_Erasednode)) == _Erasednode)
                this->_Left(this->_Parent(_Erasednode)) =
                    _Pnode; // link down to left
            else
                this->_Right(this->_Parent(_Erasednode)) =
                    _Pnode; // link down to right

            this->_Parent(_Pnode) =
                this->_Parent(_Erasednode); // link successor up
            _STD swap(this->_Color(_Pnode),
                this->_Color(_Erasednode)); // recolor it
            }

        if (this->_Color(_Erasednode) == this->_Black)
            {   // erasing black link, must recolor/rebalance tree
            for (; _Fixnode != _Root()
                && this->_Color(_Fixnode) == this->_Black;
                _Fixnodeparent = this->_Parent(_Fixnode))
                if (_Fixnode == this->_Left(_Fixnodeparent))
                    {   // fixup left subtree
                    _Pnode = this->_Right(_Fixnodeparent);
                    if (this->_Color(_Pnode) == this->_Red)
                        {   // rotate red up from right subtree
                        this->_Color(_Pnode) = this->_Black;
                        this->_Color(_Fixnodeparent) = this->_Red;
                        _Lrotate(_Fixnodeparent);
                        _Pnode = this->_Right(_Fixnodeparent);
                        }

                    if (this->_Isnil(_Pnode))
                        _Fixnode = _Fixnodeparent;  // shouldn't happen
                    else if (this->_Color(this->_Left(_Pnode)) == this->_Black
                        && this->_Color(this->_Right(_Pnode)) == this->_Black)
                        {   // redden right subtree with black children
                        this->_Color(_Pnode) = this->_Red;
                        _Fixnode = _Fixnodeparent;
                        }
                    else
                        {   // must rearrange right subtree
                        if (this->_Color(this->_Right(_Pnode))
                            == this->_Black)
                            {   // rotate red up from left sub-subtree
                            this->_Color(this->_Left(_Pnode)) = this->_Black;
                            this->_Color(_Pnode) = this->_Red;
                            _Rrotate(_Pnode);
                            _Pnode = this->_Right(_Fixnodeparent);
                            }

                        this->_Color(_Pnode) = this->_Color(_Fixnodeparent);
                        this->_Color(_Fixnodeparent) = this->_Black;
                        this->_Color(this->_Right(_Pnode)) = this->_Black;
                        _Lrotate(_Fixnodeparent);
                        break;  // tree now recolored/rebalanced
                        }
                    }
                else
                    {   // fixup right subtree
                    _Pnode = this->_Left(_Fixnodeparent);
                    if (this->_Color(_Pnode) == this->_Red)
                        {   // rotate red up from left subtree
                        this->_Color(_Pnode) = this->_Black;
                        this->_Color(_Fixnodeparent) = this->_Red;
                        _Rrotate(_Fixnodeparent);
                        _Pnode = this->_Left(_Fixnodeparent);
                        }

                    if (this->_Isnil(_Pnode))
                        _Fixnode = _Fixnodeparent;  // shouldn't happen
                    else if (this->_Color(this->_Right(_Pnode)) ==
                        this->_Black
                        && this->_Color(this->_Left(_Pnode)) == this->_Black)
                        {   // redden left subtree with black children
                        this->_Color(_Pnode) = this->_Red;
                        _Fixnode = _Fixnodeparent;
                        }
                    else
                        {   // must rearrange left subtree
                        if (this->_Color(this->_Left(_Pnode)) == this->_Black)
                            {   // rotate red up from right sub-subtree
                            this->_Color(this->_Right(_Pnode)) = this->_Black;
                            this->_Color(_Pnode) = this->_Red;
                            _Lrotate(_Pnode);
                            _Pnode = this->_Left(_Fixnodeparent);
                            }

                        this->_Color(_Pnode) = this->_Color(_Fixnodeparent);
                        this->_Color(_Fixnodeparent) = this->_Black;
                        this->_Color(this->_Left(_Pnode)) = this->_Black;
                        _Rrotate(_Fixnodeparent);
                        break;  // tree now recolored/rebalanced
                        }
                    }

            this->_Color(_Fixnode) = this->_Black;  // stopping node is black
            }

        this->_Getal().destroy(
            _STD addressof(this->_Myval(_Erasednode))); // delete erased node

        this->_Getal().deallocate(_Erasednode, 1);

        if (0 < this->_Mysize)
            --this->_Mysize;

        return (iterator(_Where._Ptr, this));   // return successor iterator
        }

template<class _Traits>

iterator _Tree< _Traits >::erase ( const_iterator  _First, const_iterator  _Last  )

inline

        {   // erase [_First, _Last)
        if (_First == begin() && _Last == end())
            {   // erase all
            clear();
            return (begin());
            }
        else
            {   // partial erase, one at a time
            while (_First != _Last)
                erase(_First++);
            return (iterator(_First._Ptr, this));
            }
        }

template<class _Traits>

size_type _Tree< _Traits >::erase ( const key_type &  _Keyval )

inline

        {   // erase and count all that match _Keyval
        _Pairii _Where = equal_range(_Keyval);
        size_type _Num = 0;
        _Distance(_Where.first, _Where.second, _Num);
        erase(_Where.first, _Where.second);
        return (_Num);
        }

template<class _Traits>

iterator _Tree< _Traits >::find ( const key_type &  _Keyval )

inline

        {   // find an element in mutable sequence that matches _Keyval
        iterator _Where = lower_bound(_Keyval);
        return (_Where == end()
            || _DEBUG_LT_PRED(this->_Getcomp(),
                _Keyval, this->_Key(_Where._Mynode()))
                    ? end() : _Where);
        }

template<class _Traits>

const_iterator _Tree< _Traits >::find ( const key_type &  _Keyval ) const

inline

        {   // find an element in nonmutable sequence that matches _Keyval
        const_iterator _Where = lower_bound(_Keyval);
        return (_Where == end()
            || _DEBUG_LT_PRED(this->_Getcomp(),
                _Keyval, this->_Key(_Where._Mynode()))
                    ? end() : _Where);
        }

template<class _Traits>

allocator_type _Tree< _Traits >::get_allocator ( ) const

inline

        {   // return allocator object for values
        return (this->_Getal());
        }

template<class _Traits>

_Pairib _Tree< _Traits >::insert ( value_type &&  _Val )

inline

        {   // try to insert node with value _Val, favoring right side
        return (_Insert_nohint(false,
            _STD forward<value_type>(_Val), _Nil_obj));
        }

template<class _Traits>

iterator _Tree< _Traits >::insert ( const_iterator  _Where, value_type &&  _Val  )

inline

        {   // try to insert node with value _Val using _Where as a hint
        return (_Insert_hint(_Where,
            _STD forward<value_type>(_Val), _Nil_obj));
        }

template<class _Traits>

template<class _Valty >

enable_if<is_convertible<_Valty, value_type>::value, _Pairib>::type _Tree< _Traits >::insert ( _Valty &&  _Val )

inline

        {   // try to insert node with value _Val, favoring right side
        _Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val));
        return (_Insert_nohint(false,
            this->_Myval(_Newnode), _Newnode));
        }

template<class _Traits>

template<class _Valty >

enable_if<is_convertible<_Valty, value_type>::value, iterator>::type _Tree< _Traits >::insert ( const_iterator  _Where, _Valty &&  _Val  )

inline

        {   // try to insert node with value _Val using _Where as a hint
        _Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val));
        return (_Insert_hint(_Where,
            this->_Myval(_Newnode), _Newnode));
        }

template<class _Traits>

_Pairib _Tree< _Traits >::insert ( const value_type &  _Val )

inline

        {   // try to insert node with value _Val, favoring right side
        return (_Insert_nohint(false,
            _Val, _Nil_obj));
        }

template<class _Traits>

iterator _Tree< _Traits >::insert ( const_iterator  _Where, const value_type &  _Val  )

inline

        {   // try to insert node with value _Val using _Where as a hint
        return (_Insert_hint(_Where,
            _Val, _Nil_obj));
        }

template<class _Traits>

template<class _Iter >

void _Tree< _Traits >::insert ( _Iter  _First, _Iter  _Last  )

inline

        {   // insert [_First, _Last) one at a time
        _DEBUG_RANGE(_First, _Last);
        for (; _First != _Last; ++_First)

            emplace_hint(end(), *_First);
        }

template<class _Traits>

void _Tree< _Traits >::insert ( _XSTD initializer_list< value_type >  _Ilist )

inline

        {   // insert initializer_list
        insert(_Ilist.begin(), _Ilist.end());
        }

template<class _Traits>

key_compare _Tree< _Traits >::key_comp ( ) const

inline

        {   // return object for comparing keys
        return (this->_Getcomp());
        }

template<class _Traits>

iterator _Tree< _Traits >::lower_bound ( const key_type &  _Keyval )

inline

        {   // find leftmost node not less than _Keyval in mutable tree
        return (iterator(_Lbound(_Keyval), this));
        }

template<class _Traits>

const_iterator _Tree< _Traits >::lower_bound ( const key_type &  _Keyval ) const

inline

        {   // find leftmost node not less than _Keyval in nonmutable tree
        return (const_iterator(_Lbound(_Keyval), this));
        }

template<class _Traits>

size_type _Tree< _Traits >::max_size ( ) const

inline

        {   // return maximum possible length of sequence
        return (this->_Getal().max_size());
        }

template<class _Traits>

_Myt& _Tree< _Traits >::operator= ( _Myt &&  _Right )

inline

        {   // assign by moving _Right
        if (this != &_Right)
            {   // different, move it
            clear();
            if (_Alty::propagate_on_container_move_assignment::value
                && this->_Getal() != _Right._Getal())
                this->_Change_alloc(_Right._Getal());

            _Assign_rv(_STD forward<_Myt>(_Right));
            }
        return (*this);
        }

template<class _Traits>

_Myt& _Tree< _Traits >::operator= ( const _Myt &  _Right )

inline

        {   // replace contents from _Right
        if (this != &_Right)
            {   // different, assign it
            clear();
            if (this->_Getal() != _Right._Getal()
                && _Alty::propagate_on_container_copy_assignment::value)
                this->_Change_alloc(_Right._Getal());

            this->_Setcomp(_Right._Getcomp());
            _Copy(_Right, false_type());
            }
        return (*this);
        }

template<class _Traits>

reverse_iterator _Tree< _Traits >::rbegin ( )

inline

        {   // return iterator for beginning of reversed mutable sequence
        return (reverse_iterator(end()));
        }

template<class _Traits>

const_reverse_iterator _Tree< _Traits >::rbegin ( ) const

inline

        {   // return iterator for beginning of reversed nonmutable sequence
        return (const_reverse_iterator(end()));
        }

template<class _Traits>

reverse_iterator _Tree< _Traits >::rend ( )

inline

        {   // return iterator for end of reversed mutable sequence
        return (reverse_iterator(begin()));
        }

template<class _Traits>

const_reverse_iterator _Tree< _Traits >::rend ( ) const

inline

        {   // return iterator for end of reversed nonmutable sequence
        return (const_reverse_iterator(begin()));
        }

template<class _Traits>

size_type _Tree< _Traits >::size ( ) const

inline

        {   // return length of sequence
        return (this->_Mysize);
        }

template<class _Traits>

void _Tree< _Traits >::swap ( _Myt &  _Right )

inline

        {   // exchange contents with _Right
        if (this == &_Right)
            ;   // same object, do nothing
        else if (this->_Getal() == _Right._Getal())
            {   // same allocator, swap control information
            this->_Swap_all(_Right);
            this->_Swapcomp(_Right._Getcomp());
            _Swap_adl(this->_Myhead, _Right._Myhead);
            _STD swap(this->_Mysize, _Right._Mysize);
            }

        else if (_Alty::propagate_on_container_swap::value)
            {   // swap allocators and control information
            this->_Swap_alloc(_Right);
            this->_Swapcomp(_Right._Getcomp());
            _Swap_adl(this->_Myhead, _Right._Myhead);
            _STD swap(this->_Mysize, _Right._Mysize);
            }

        else
            {   // containers are incompatible
 #if _ITERATOR_DEBUG_LEVEL == 2
            _DEBUG_ERROR("map/set containers incompatible for swap");

 #else /* ITERATOR_DEBUG_LEVEL == 2 */
            _XSTD terminate();
 #endif /* ITERATOR_DEBUG_LEVEL == 2 */
            }
        }

template<class _Traits>

iterator _Tree< _Traits >::upper_bound ( const key_type &  _Keyval )

inline

        {   // find leftmost node greater than _Keyval in mutable tree
        return (iterator(_Ubound(_Keyval), this));
        }

template<class _Traits>

const_iterator _Tree< _Traits >::upper_bound ( const key_type &  _Keyval ) const

inline

        {   // find leftmost node greater than _Keyval in nonmutable tree
        return (const_iterator(_Ubound(_Keyval), this));
        }

template<class _Traits>

value_compare _Tree< _Traits >::value_comp ( ) const

inline

        {   // return object for comparing values
        return (value_compare(key_comp()));
        }

---

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

• VS2013/inc/xtree