📄 xtree
字号:
; // need to test if insert after is okay
else if (_Where == begin())
return (_Pairib(_Insert(true, _Wherenode, _Node), true));
else
--_Where; // need to test if insert before is okay
if (_DEBUG_LT_PRED(this->comp,
this->_Key(_Where._Mynode()),
this->_Kfn(_Val)))
return (_Pairib(_Insert(_Addleft, _Wherenode, _Node), true));
else
{ // duplicate, don't insert
_Dest_val(this->_Alval,
_STD addressof(this->_Myval(_Node)));
this->_Alnod.deallocate(_Node, 1);
return (_Pairib(_Where, false));
}
}
}
iterator insert(const_iterator _Where,
const value_type& _Val)
{ // try to insert node with value _Val using _Where as a hint
#if _ITERATOR_DEBUG_LEVEL == 2
if (_Where._Getcont() != this)
_DEBUG_ERROR("map/set insert iterator outside range");
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
const_iterator _Next;
bool _Leftish = false; // assume nearest point is end of sequence
if (size() == 0)
return (_Insert(true, this->_Myhead, _Val)); // 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->comp,
this->_Key(_Where._Mynode()), this->_Kfn(_Val)))
return (_Insert(true, _Where._Mynode(), _Val));
_Leftish = true; // nearest point is beginning of sequence
}
else if (_Where == end())
{ // insert at end if after last element
if (!_DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val), this->_Key(_Rmost())))
return (_Insert(false, _Rmost(), _Val));
}
else if (!_DEBUG_LT_PRED(this->comp,
this->_Key(_Where._Mynode()), this->_Kfn(_Val))
&& !_DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val),
this->_Key((--(_Next = _Where))._Mynode())))
{ // insert before _Where
if (this->_Isnil(this->_Right(_Next._Mynode())))
return (_Insert(false, _Next._Mynode(), _Val));
else
return (_Insert(true, _Where._Mynode(), _Val));
}
else if (!_DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val), this->_Key(_Where._Mynode()))
&& (++(_Next = _Where) == end()
|| !_DEBUG_LT_PRED(this->comp,
this->_Key(_Next._Mynode()), this->_Kfn(_Val))))
{ // insert after _Where
if (this->_Isnil(this->_Right(_Where._Mynode())))
return (_Insert(false, _Where._Mynode(), _Val));
else
return (_Insert(true, _Next._Mynode(), _Val));
}
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->comp,
this->_Kfn(_Val), this->_Key(_Where._Mynode())))
return (_Insert(true, _Where._Mynode(), _Val));
}
else if (_Where == end())
{ // insert at end if after last element
if (_DEBUG_LT_PRED(this->comp,
this->_Key(_Rmost()), this->_Kfn(_Val)))
return (_Insert(false, _Rmost(), _Val));
}
else if (_DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val), this->_Key(_Where._Mynode()))
&& _DEBUG_LT_PRED(this->comp,
this->_Key((--(_Next = _Where))._Mynode()),
this->_Kfn(_Val)))
{ // insert before _Where
if (this->_Isnil(this->_Right(_Next._Mynode())))
return (_Insert(false, _Next._Mynode(), _Val));
else
return (_Insert(true, _Where._Mynode(), _Val));
}
else if (_DEBUG_LT_PRED(this->comp,
this->_Key(_Where._Mynode()), this->_Kfn(_Val))
&& (++(_Next = _Where) == end()
|| _DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val), this->_Key(_Next._Mynode()))))
{ // insert after _Where
if (this->_Isnil(this->_Right(_Where._Mynode())))
return (_Insert(false, _Where._Mynode(), _Val));
else
return (_Insert(true, _Next._Mynode(), _Val));
}
}
return (insert(_Val, _Leftish).first); // try usual insert
}
iterator _Insert(const_iterator _Where,
_Nodeptr _Node)
{ // try to insert node at _Node using _Where as a hint
#if _ITERATOR_DEBUG_LEVEL == 2
if (_Where._Getcont() != this)
_DEBUG_ERROR("map/set insert iterator outside range");
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
const value_type& _Val = this->_Myval(_Node);
const_iterator _Next;
bool _Leftish = false; // assume nearest point is end of sequence
if (size() == 0)
return (_Insert(true, this->_Myhead, _Node)); // 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->comp,
this->_Key(_Where._Mynode()), this->_Kfn(_Val)))
return (_Insert(true, _Where._Mynode(), _Node));
_Leftish = true; // nearest point is beginning of sequence
}
else if (_Where == end())
{ // insert at end if after last element
if (!_DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val), this->_Key(_Rmost())))
return (_Insert(false, _Rmost(), _Node));
}
else if (!_DEBUG_LT_PRED(this->comp,
this->_Key(_Where._Mynode()), this->_Kfn(_Val))
&& !_DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val),
this->_Key((--(_Next = _Where))._Mynode())))
{ // insert before _Where
if (this->_Isnil(this->_Right(_Next._Mynode())))
return (_Insert(false, _Next._Mynode(), _Node));
else
return (_Insert(true, _Where._Mynode(), _Node));
}
else if (!_DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val), this->_Key(_Where._Mynode()))
&& (++(_Next = _Where) == end()
|| !_DEBUG_LT_PRED(this->comp,
this->_Key(_Next._Mynode()), this->_Kfn(_Val))))
{ // insert after _Where
if (this->_Isnil(this->_Right(_Where._Mynode())))
return (_Insert(false, _Where._Mynode(), _Node));
else
return (_Insert(true, _Next._Mynode(), _Node));
}
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->comp,
this->_Kfn(_Val), this->_Key(_Where._Mynode())))
return (_Insert(true, _Where._Mynode(), _Node));
}
else if (_Where == end())
{ // insert at end if after last element
if (_DEBUG_LT_PRED(this->comp,
this->_Key(_Rmost()), this->_Kfn(_Val)))
return (_Insert(false, _Rmost(), _Node));
}
else if (_DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val), this->_Key(_Where._Mynode()))
&& _DEBUG_LT_PRED(this->comp,
this->_Key((--(_Next = _Where))._Mynode()),
this->_Kfn(_Val)))
{ // insert before _Where
if (this->_Isnil(this->_Right(_Next._Mynode())))
return (_Insert(false, _Next._Mynode(), _Node));
else
return (_Insert(true, _Where._Mynode(), _Node));
}
else if (_DEBUG_LT_PRED(this->comp,
this->_Key(_Where._Mynode()), this->_Kfn(_Val))
&& (++(_Next = _Where) == end()
|| _DEBUG_LT_PRED(this->comp,
this->_Kfn(_Val), this->_Key(_Next._Mynode()))))
{ // insert after _Where
if (this->_Isnil(this->_Right(_Where._Mynode())))
return (_Insert(false, _Where._Mynode(), _Node));
else
return (_Insert(true, _Next._Mynode(), _Node));
}
}
return (_Linsert(_Node, _Leftish).first); // try usual insert
}
template<class _Iter>
void insert(_Iter _First, _Iter _Last)
{ // insert [_First, _Last) one at a time
_DEBUG_RANGE(_First, _Last);
for (; _First != _Last; ++_First)
{ // insert element as lvalue
const value_type& _Val = *_First;
insert(end(), _Val);
}
}
iterator erase(const_iterator _Where)
{ // 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 */
if (this->_Isnil(_Where._Mynode()))
_Xout_of_range("invalid map/set<T> iterator");
_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
}
_Dest_val(this->_Alval,
_STD addressof(this->_Myval(_Erasednode))); // delete erased node
this->_Alnod.deallocate(_Erasednode, 1);
if (0 < this->_Mysize)
--this->_Mysize;
return (iterator(_Where._Ptr, this)); // return successor iterator
}
iterator erase(const_iterator _First, const_iterator _Last)
{ // 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));
}
}
size_type erase(const key_type& _Keyval)
{ // 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);
}
void erase(const key_type *_First, const key_type *_Last)
{ // erase all that match array of keys [_First, _Last)
_DEBUG_RANGE(_First, _Last);
while (_First != _Last)
erase(*_First++);
}
void clear()
{ // 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;
}
iterator find(const key_type& _Keyval)
{ // find an element in mutable sequence that matches _Keyval
iterator _Where = lower_bound(_Keyval);
return (_Where == end()
|| _DEBUG_LT_PRED(this->comp,
_Keyval, this->_Key(_Where._Mynode()))
? end() : _Where);
}
const_iterator find(const key_type& _Keyval) const
{ // find an element in nonmutable sequence that matches _Keyval
const_iterator _Where = lower_bound(_Keyval);
return (_Where == end()
|| _DEBUG_LT_PRED(this->comp,
_Keyval, this->_Key(_Where._Mynode()))
? end() : _Where);
}
size_type count(const key_type& _Keyval) const
{ // count all elements that match _Keyval
_Paircc _Ans = equal_range(_Keyval);
size_type _Num = 0;
_Distance(_Ans.first, _Ans.second, _Num);
return (_Num);
}
iterator lower_bound(const key_type& _Keyval)
{ // find leftmost node not less than _Keyval in mutable tree
return (iterator(_Lbound(_Keyval), this));
}
const_iterator lower_bound(const key_type& _Keyval) const
{ // find leftmost node not less than _Keyval in nonmutable tree
return (const_iterator(_Lbound(_Keyval), this));
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -