Inheritance diagram for _Tree< _Traits >:

Classes
struct	_Copy_tag

struct	_Move_tag

Public Types
enum	{ _Multi = _Traits::_Multi }

typedef _Tree< _Traits >	_Myt

typedef _Tree_comp_alloc< _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_alloc< _Traits >
enum	_Redbl { _Red, _Black }

typedef _Tree_comp_alloc< _Traits >	_Myt

typedef _Traits::allocator_type	allocator_type

typedef _Traits::key_compare	key_compare

typedef _Tree_base_types< typename _Traits::value_type, allocator_type >	_Alloc_types

typedef _Alloc_types::_Alloc	_Alloc

typedef _Alloc_types::_Alnod_type	_Alty

typedef _Alloc_types::_Node	_Node

typedef _Alloc_types::_Nodeptr	_Nodeptr

typedef _Alloc_types::_Val_types	_Val_types

typedef _Nodeptr &	_Nodepref

typedef _Val_types::value_type	value_type

typedef _Val_types::size_type	size_type

typedef _Val_types::difference_type	difference_type

typedef _Val_types::pointer	pointer

typedef _Val_types::const_pointer	const_pointer

typedef _Val_types::reference	reference

typedef _Val_types::const_reference	const_reference

typedef _Tree_const_iterator< _Tree_val< _Val_types > >	const_iterator

typedef _Tree_iterator< _Tree_val< _Val_types > >	iterator

Public Member Functions
	_Tree (const key_compare &_Parg)

	_Tree (const key_compare &_Parg, const allocator_type &_Al)

template<class _Any_alloc >
	_Tree (const _Myt &_Right, _Any_alloc &&_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)

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

template<bool _Multi2 = _Multi, enable_if_t<!_Multi2, int > = 0>
_Pairib	insert (const value_type &_Val)

template<bool _Multi2 = _Multi, enable_if_t< _Multi2, int > = 0>
iterator	insert (const value_type &_Val)

template<bool _Multi2 = _Multi, enable_if_t<!_Multi2, int > = 0>
_Pairib	insert (value_type &&_Val)

template<bool _Multi2 = _Multi, enable_if_t< _Multi2, int > = 0>
iterator	insert (value_type &&_Val)

iterator	insert (const_iterator _Where, const value_type &_Val)

iterator	insert (const_iterator _Where, value_type &&_Val)

template<class _Iter >
void	insert (_Iter _First, _Iter _Last)

void	insert (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

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
iterator	find (const _Other &_Keyval)

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
const_iterator	find (const _Other &_Keyval) const

size_type	count (const key_type &_Keyval) const

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
size_type	count (const _Other &_Keyval) const

iterator	lower_bound (const key_type &_Keyval)

const_iterator	lower_bound (const key_type &_Keyval) const

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
iterator	lower_bound (const _Other &_Keyval)

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
const_iterator	lower_bound (const _Other &_Keyval) const

iterator	upper_bound (const key_type &_Keyval)

const_iterator	upper_bound (const key_type &_Keyval) const

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
iterator	upper_bound (const _Other &_Keyval)

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
const_iterator	upper_bound (const _Other &_Keyval) const

_Pairii	equal_range (const key_type &_Keyval)

_Paircc	equal_range (const key_type &_Keyval) const

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
_Pairii	equal_range (const _Other &_Keyval)

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
_Paircc	equal_range (const _Other &_Keyval) const

void	swap (_Myt &_Right)

Public Member Functions inherited from _Tree_comp_alloc< _Traits >
	_Tree_comp_alloc (const key_compare &_Parg)

template<class _Any_alloc , class = enable_if_t<!is_same<decay_t<_Any_alloc>, _Myt>::value>>
	_Tree_comp_alloc (const key_compare &_Parg, _Any_alloc &&_Al)

void	_Construct ()

	~_Tree_comp_alloc () _NOEXCEPT

void	_Alloc_proxy ()

void	_Free_proxy ()

void	_Copy_alloc (const _Alty &_Al)

void	_Move_alloc (_Alty &_Al)

void	_Orphan_all ()

void	_Swap_all (_Myt &_Right)

_Nodeptr	_Buyheadnode ()

void	_Freeheadnode (_Nodeptr _Pnode)

_Nodeptr	_Buynode0 ()

void	_Freenode0 (_Nodeptr _Pnode)

template<class... _Valty>
_Nodeptr	_Buynode (_Valty &&..._Val)

key_compare &	_Getcomp () _NOEXCEPT

const key_compare &	_Getcomp () const _NOEXCEPT

_Alty &	_Getal () _NOEXCEPT

const _Alty &	_Getal () const _NOEXCEPT

_Tree_val< _Val_types > &	_Get_data () _NOEXCEPT

const _Tree_val< _Val_types > &	_Get_data () const _NOEXCEPT

_Nodeptr &	_Myhead () _NOEXCEPT

const _Nodeptr &	_Myhead () const _NOEXCEPT

size_type &	_Mysize () _NOEXCEPT

const size_type &	_Mysize () const _NOEXCEPT

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 _Ty , class _Is_set >
_Nodeptr	_Copy_or_move (_Ty &_Val, _Copy_tag, _Is_set)

template<class _Ty >
_Nodeptr	_Copy_or_move (_Ty &_Val, _Move_tag, true_type)

template<class _Ty >
_Nodeptr	_Copy_or_move (_Ty &_Val, _Move_tag, false_type)

template<class _Moveit >
_Nodeptr	_Copy_nodes (_Nodeptr _Rootnode, _Nodeptr _Wherenode, _Moveit _Movefl)

template<class _Other >
_Paircc	_Eqrange (const _Other &_Keyval) const

template<class _Other >
_Pairii	_Eqrange (const _Other &_Keyval)

void	_Erase (_Nodeptr _Rootnode)

bool	_Compare (const key_type &_Left, const key_type &_Right) const

template<class _Ty1 , class _Ty2 >
bool	_Compare (const _Ty1 &_Left, const _Ty2 &_Right) const

template<class _Other >
_Nodeptr	_Lbound (const _Other &_Keyval) const

_Nodeptr &	_Lmost () const

void	_Lrotate (_Nodeptr _Wherenode)

_Nodeptr &	_Rmost () const

_Nodeptr &	_Root () const

void	_Rrotate (_Nodeptr _Wherenode)

template<class _Other >
_Nodeptr	_Ubound (const _Other &_Keyval) const

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_comp_alloc< _Traits >
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)

Member Typedef Documentation

template<class _Traits>

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

template<class _Traits>

typedef _Tree_comp_alloc<_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

980 { // get multi parameter

981 _Multi = _Traits::_Multi};

_Tree::_Multi

Definition: xtree:981

Constructor & Destructor Documentation

template<class _Traits>

_Tree< _Traits >::_Tree ( const key_compare & _Parg )

inline

         : _Mybase(_Parg)
         {   // construct empty tree from comparator
         }

template<class _Traits>

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

inline

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

template<class _Traits>

template<class _Any_alloc >

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

inline

         : _Mybase(_Right.key_comp(), _STD forward<_Any_alloc>(_Al))
         {   // construct tree by copying _Right, allocator
         _TRY_BEGIN
         _Copy(_Right, _Copy_tag());
         _CATCH_ALL
         _Tidy();
         _RERAISE;
         _CATCH_END
         }

template<class _Traits>

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

inline

         : _Mybase(_Right.key_comp(), _STD move(_Right._Getal()))
         {   // construct tree by moving _Right
         _Assign_rv(_STD move(_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 move(_Right), false_type());
         }

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);
         _Swap_adl(this->_Getcomp(), _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 (this->_Getal() == _Right._Getal())
             _Assign_rv(_STD move(_Right), true_type());
         else
             _Copy(_Right, _Move_tag());
         }

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>

bool _Tree< _Traits >::_Compare	(	const key_type &	_Left,
		const key_type &	_Right
	)		const

inlineprotected

         {   // compare key_type to key_type, with debug checks
         return (_DEBUG_LT_PRED(this->_Getcomp(), _Left, _Right));
         }

template<class _Traits>

template<class _Ty1 , class _Ty2 >

bool _Tree< _Traits >::_Compare	(	const _Ty1 &	_Left,
		const _Ty2 &	_Right
	)		const

inlineprotected

         {   // compare _Ty1 to _Ty2, without debug checks
         return (this->_Getcomp()(_Left, _Right));
         }

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
             typename is_same<key_type, value_type>::type _Is_set;
             _Nodeptr _Pnode = _Copy_or_move(
                 this->_Myval(_Rootnode), _Movefl, _Is_set);
             _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 _Ty , class _Is_set >

_Nodeptr _Tree< _Traits >::_Copy_or_move	(	_Ty &	_Val,
		_Copy_tag	,
		_Is_set
	)

inlineprotected

         {   // copy to new node
         return (this->_Buynode(_Val));
         }

template<class _Traits>

template<class _Ty >

_Nodeptr _Tree< _Traits >::_Copy_or_move	(	_Ty &	_Val,
		_Move_tag	,
		true_type
	)

inlineprotected

         {   // move to new node -- set
         return (this->_Buynode(_STD move(_Val)));
         }

template<class _Traits>

template<class _Ty >

_Nodeptr _Tree< _Traits >::_Copy_or_move	(	_Ty &	_Val,
		_Move_tag	,
		false_type
	)

inlineprotected

         {   // move to new node -- map
         return (this->_Buynode(
             _STD move(const_cast<key_type&>(_Val.first)),
             _STD move(_Val.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

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

1657 }

template<class _Traits>

template<class _Other >

_Paircc _Tree< _Traits >::_Eqrange ( const _Other & _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, _STD addressof(this->_Get_data()));
         const_iterator _Last = const_iterator(_Hinode, _STD addressof(this->_Get_data()));
         return (_Paircc(_First, _Last));
         }

template<class _Traits>

template<class _Other >

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

inlineprotected

         {   // find leftmost node not less than _Keyval
         _Paircc _Ans(static_cast<const _Myt *>(this)->_Eqrange(_Keyval));
         iterator _First = iterator(_Ans.first._Ptr, _STD addressof(this->_Get_data()));
         iterator _Last = iterator(_Ans.second._Ptr, _STD addressof(this->_Get_data()));
         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, _STD addressof(this->_Get_data())));
         }

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() != _STD addressof(this->_Get_data()))
             {
             _DEBUG_ERROR("map/set insert iterator outside range");
             }
  #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
 
 #pragma warning(push)
 #pragma warning(disable: 4127)  // conditional expression is constant
         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));
                 }
             }
 #pragma warning(pop)
         _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);
             }
 
 #pragma warning(push)
 #pragma warning(disable: 4127)  // conditional expression is constant
         if (this->_Multi)
             return (_Pairib(_Insert_at(_Addleft, _Wherenode,
                 _STD forward<_Valty>(_Val), _Newnode), true));
         else
             {   // insert only if unique
             iterator _Where = iterator(_Wherenode, _STD addressof(this->_Get_data()));
             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));
                 }
             }
 #pragma warning(pop)
         _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>

template<class _Other >

_Nodeptr _Tree< _Traits >::_Lbound ( const _Other & _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 (_Compare(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>

template<class _Other >

_Nodeptr _Tree< _Traits >::_Ubound ( const _Other & _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 (_Compare(_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(), _STD addressof(this->_Get_data())));
         }

template<class _Traits>

const_iterator _Tree< _Traits >::begin ( ) const

inline

         {   // return iterator for beginning of nonmutable sequence
         return (const_iterator(_Lmost(), _STD addressof(this->_Get_data())));
         }

template<class _Traits>

const_iterator _Tree< _Traits >::cbegin ( ) const

inline

         {   // return iterator for beginning of nonmutable sequence
         return (begin());
         }

template<class _Traits>

const_iterator _Tree< _Traits >::cend ( ) const

inline

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

template<class _Traits>

void _Tree< _Traits >::clear ( )

inline

         {   // erase all
  #if _ITERATOR_DEBUG_LEVEL == 2
         this->_Orphan_ptr(nullptr_t{});
  #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);
         return (_STD distance(_Ans.first, _Ans.second));
         }

template<class _Traits>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

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

inline

         {   // count all elements that match _Keyval
         _Paircc _Ans = equal_range(_Keyval);
         return (_STD distance(_Ans.first, _Ans.second));
         }

template<class _Traits>

const_reverse_iterator _Tree< _Traits >::crbegin ( ) const

inline

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

template<class _Traits>

const_reverse_iterator _Tree< _Traits >::crend ( ) const

inline

         {   // return iterator for end of reversed nonmutable sequence
         return (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(), _STD addressof(this->_Get_data())));
         }

template<class _Traits>

const_iterator _Tree< _Traits >::end ( ) const

inline

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

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>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

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

inline

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

template<class _Traits>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

_Paircc _Tree< _Traits >::equal_range ( const _Other & _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() != _STD addressof(this->_Get_data())
             || 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(_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,
             _STD addressof(this->_Get_data())));    // 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, _STD addressof(this->_Get_data())));
             }
         }

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 = _STD distance(_Where.first, _Where.second);
         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>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

iterator _Tree< _Traits >::find ( const _Other & _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>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

const_iterator _Tree< _Traits >::find ( const _Other & _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
         allocator_type _Ret(this->_Getal());
         return (_Ret);
         }

template<class _Traits>

template<bool _Multi2 = _Multi, enable_if_t<!_Multi2, int > = 0>

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

template<class _Traits>

template<bool _Multi2 = _Multi, enable_if_t< _Multi2, int > = 0>

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

inline

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

template<class _Traits>

template<bool _Multi2 = _Multi, enable_if_t<!_Multi2, int > = 0>

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

inline

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

template<class _Traits>

template<bool _Multi2 = _Multi, enable_if_t< _Multi2, int > = 0>

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

inline

         {   // try to insert node with value _Val, favoring right side
         return (_Insert_nohint(false,
             _STD move(_Val), _Nil()).first);
         }

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

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 move(_Val), _Nil()));
         }

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 ( 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), _STD addressof(this->_Get_data())));
         }

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), _STD addressof(this->_Get_data())));
         }

template<class _Traits>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

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

inline

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

template<class _Traits>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

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

inline

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

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 != _STD addressof(_Right))
             {   // different, move it
             clear();
             this->_Move_alloc(_Right._Getal());
             this->_Getcomp() = _Right._Getcomp();
             _Assign_rv(_STD move(_Right),
                 typename _Alty::propagate_on_container_move_assignment());
             }
         return (*this);
         }

template<class _Traits>

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

inline

         {   // replace contents from _Right
         if (this != _STD addressof(_Right))
             {   // different, assign it
             clear();
             this->_Copy_alloc(_Right._Getal());
             this->_Getcomp() = _Right._Getcomp();
             _Copy(_Right, _Copy_tag());
             }
         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 != _STD addressof(_Right))
             {   // (maybe) swap allocators, swap control information
             _Pocs(this->_Getal(), _Right._Getal());
             this->_Swap_all(_Right);
             _Swap_adl(this->_Getcomp(), _Right._Getcomp());
             _Swap_adl(this->_Myhead(), _Right._Myhead());
             _STD swap(this->_Mysize(), _Right._Mysize());
             }
         }

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), _STD addressof(this->_Get_data())));
         }

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), _STD addressof(this->_Get_data())));
         }

template<class _Traits>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

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

inline

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

template<class _Traits>

template<class _Other , class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>

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

inline

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

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:

VS2017/inc/xtree

Classes

Public Types

Public Member Functions

Protected Member Functions

Additional Inherited Members

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation