?? xtree
字號(hào):
break; }}
else
{_Nodeptr _W = _Left(_Parent(_X));
if (_Color(_W) == _Red)
{_Color(_W) = _Black;
_Color(_Parent(_X)) = _Red;
_Rrotate(_Parent(_X));
_W = _Left(_Parent(_X)); }
if (_Color(_Right(_W)) == _Black
&& _Color(_Left(_W)) == _Black)
{_Color(_W) = _Red;
_X = _Parent(_X); }
else
{if (_Color(_Left(_W)) == _Black)
{_Color(_Right(_W)) = _Black;
_Color(_W) = _Red;
_Lrotate(_W);
_W = _Left(_Parent(_X)); }
_Color(_W) = _Color(_Parent(_X));
_Color(_Parent(_X)) = _Black;
_Color(_Left(_W)) = _Black;
_Rrotate(_Parent(_X));
break; }}
_Color(_X) = _Black; }
_Destval(&_Value(_Y));
_Freenode(_Y);
--_Size;
return (_P); }
iterator erase(iterator _F, iterator _L)
{if (size() == 0 || _F != begin() || _L != end())
{while (_F != _L)
erase(_F++);
return (_F); }
else
{_Lockit Lk;
_Erase(_Root());
_Root() = _Nil, _Size = 0;
_Lmost() = _Head, _Rmost() = _Head;
return (begin()); }}
size_type erase(const _K& _X)
{_Pairii _P = equal_range(_X);
size_type _N = 0;
_Distance(_P.first, _P.second, _N);
erase(_P.first, _P.second);
return (_N); }
void erase(const _K *_F, const _K *_L)
{for (; _F != _L; ++_F)
erase(*_F); }
void clear()
{erase(begin(), end()); }
iterator find(const _K& _Kv)
{iterator _P = lower_bound(_Kv);
return (_P == end()
|| key_compare(_Kv, _Key(_P._Mynode()))
? end() : _P); }
const_iterator find(const _K& _Kv) const
{const_iterator _P = lower_bound(_Kv);
return (_P == end()
|| key_compare(_Kv, _Key(_P._Mynode()))
? end() : _P); }
size_type count(const _K& _Kv) const
{_Paircc _Ans = equal_range(_Kv);
size_type _N = 0;
_Distance(_Ans.first, _Ans.second, _N);
return (_N); }
iterator lower_bound(const _K& _Kv)
{return (iterator(_Lbound(_Kv))); }
const_iterator lower_bound(const _K& _Kv) const
{return (const_iterator(_Lbound(_Kv))); }
iterator upper_bound(const _K& _Kv)
{return (iterator(_Ubound(_Kv))); }
const_iterator upper_bound(const _K& _Kv) const
{return (iterator(_Ubound(_Kv))); }
_Pairii equal_range(const _K& _Kv)
{return (_Pairii(lower_bound(_Kv), upper_bound(_Kv))); }
_Paircc equal_range(const _K& _Kv) const
{return (_Paircc(lower_bound(_Kv), upper_bound(_Kv))); }
void swap(_Myt& _X)
{std::swap(key_compare, _X.key_compare);
if (allocator == _X.allocator)
{std::swap(_Head, _X._Head);
std::swap(_Multi, _X._Multi);
std::swap(_Size, _X._Size); }
else
{_Myt _Ts = *this; *this = _X, _X = _Ts; }}
friend void swap(_Myt& _X, _Myt& _Y)
{_X.swap(_Y); }
protected:
static _Nodeptr _Nil;
static size_t _Nilrefs;
void _Copy(const _Myt& _X)
{_Lockit _Lk;
_Root() = _Copy(_X._Root(), _Head);
_Size = _X.size();
if (_Root() != _Nil)
{_Lmost() = _Min(_Root());
_Rmost() = _Max(_Root()); }
else
_Lmost() = _Head, _Rmost() = _Head; }
_Nodeptr _Copy(_Nodeptr _X, _Nodeptr _P)
{_Lockit _Lk;
_Nodeptr _R = _X;
for (; _X != _Nil; _X = _Left(_X))
{_Nodeptr _Y = _Buynode(_P, _Color(_X));
if (_R == _X)
_R = _Y;
_Right(_Y) = _Copy(_Right(_X), _Y);
_Consval(&_Value(_Y), _Value(_X));
_Left(_P) = _Y;
_P = _Y; }
_Left(_P) = _Nil;
return (_R); }
void _Erase(_Nodeptr _X)
{_Lockit _Lk;
for (_Nodeptr _Y = _X; _Y != _Nil; _X = _Y)
{_Erase(_Right(_Y));
_Y = _Left(_Y);
_Destval(&_Value(_X));
_Freenode(_X); }}
void _Init()
{_Lockit _Lk;
if (_Nil == 0)
{_Nil = _Buynode(0, _Black);
_Left(_Nil) = 0, _Right(_Nil) = 0; }
++_Nilrefs;
_Head = _Buynode(_Nil, _Red), _Size = 0;
_Lmost() = _Head, _Rmost() = _Head; }
iterator _Insert(_Nodeptr _X, _Nodeptr _Y, const _Ty& _V)
{_Lockit _Lk;
_Nodeptr _Z = _Buynode(_Y, _Red);
_Left(_Z) = _Nil, _Right(_Z) = _Nil;
_Consval(&_Value(_Z), _V);
++_Size;
if (_Y == _Head || _X != _Nil
|| key_compare(_Kfn()(_V), _Key(_Y)))
{_Left(_Y) = _Z;
if (_Y == _Head)
{_Root() = _Z;
_Rmost() = _Z; }
else if (_Y == _Lmost())
_Lmost() = _Z; }
else
{_Right(_Y) = _Z;
if (_Y == _Rmost())
_Rmost() = _Z; }
for (_X = _Z; _X != _Root()
&& _Color(_Parent(_X)) == _Red; )
if (_Parent(_X) == _Left(_Parent(_Parent(_X))))
{_Y = _Right(_Parent(_Parent(_X)));
if (_Color(_Y) == _Red)
{_Color(_Parent(_X)) = _Black;
_Color(_Y) = _Black;
_Color(_Parent(_Parent(_X))) = _Red;
_X = _Parent(_Parent(_X)); }
else
{if (_X == _Right(_Parent(_X)))
{_X = _Parent(_X);
_Lrotate(_X); }
_Color(_Parent(_X)) = _Black;
_Color(_Parent(_Parent(_X))) = _Red;
_Rrotate(_Parent(_Parent(_X))); }}
else
{_Y = _Left(_Parent(_Parent(_X)));
if (_Color(_Y) == _Red)
{_Color(_Parent(_X)) = _Black;
_Color(_Y) = _Black;
_Color(_Parent(_Parent(_X))) = _Red;
_X = _Parent(_Parent(_X)); }
else
{if (_X == _Left(_Parent(_X)))
{_X = _Parent(_X);
_Rrotate(_X); }
_Color(_Parent(_X)) = _Black;
_Color(_Parent(_Parent(_X))) = _Red;
_Lrotate(_Parent(_Parent(_X))); }}
_Color(_Root()) = _Black;
return (iterator(_Z)); }
_Nodeptr _Lbound(const _K& _Kv) const
{_Lockit _Lk;
_Nodeptr _X = _Root();
_Nodeptr _Y = _Head;
while (_X != _Nil)
if (key_compare(_Key(_X), _Kv))
_X = _Right(_X);
else
_Y = _X, _X = _Left(_X);
return (_Y); }
_Nodeptr& _Lmost()
{return (_Left(_Head)); }
_Nodeptr& _Lmost() const
{return (_Left(_Head)); }
void _Lrotate(_Nodeptr _X)
{_Lockit _Lk;
_Nodeptr _Y = _Right(_X);
_Right(_X) = _Left(_Y);
if (_Left(_Y) != _Nil)
_Parent(_Left(_Y)) = _X;
_Parent(_Y) = _Parent(_X);
if (_X == _Root())
_Root() = _Y;
else if (_X == _Left(_Parent(_X)))
_Left(_Parent(_X)) = _Y;
else
_Right(_Parent(_X)) = _Y;
_Left(_Y) = _X;
_Parent(_X) = _Y; }
static _Nodeptr _Max(_Nodeptr _P)
{_Lockit _Lk;
while (_Right(_P) != _Nil)
_P = _Right(_P);
return (_P); }
static _Nodeptr _Min(_Nodeptr _P)
{_Lockit _Lk;
while (_Left(_P) != _Nil)
_P = _Left(_P);
return (_P); }
_Nodeptr& _Rmost()
{return (_Right(_Head)); }
_Nodeptr& _Rmost() const
{return (_Right(_Head)); }
_Nodeptr& _Root()
{return (_Parent(_Head)); }
_Nodeptr& _Root() const
{return (_Parent(_Head)); }
void _Rrotate(_Nodeptr _X)
{_Lockit _Lk;
_Nodeptr _Y = _Left(_X);
_Left(_X) = _Right(_Y);
if (_Right(_Y) != _Nil)
_Parent(_Right(_Y)) = _X;
_Parent(_Y) = _Parent(_X);
if (_X == _Root())
_Root() = _Y;
else if (_X == _Right(_Parent(_X)))
_Right(_Parent(_X)) = _Y;
else
_Left(_Parent(_X)) = _Y;
_Right(_Y) = _X;
_Parent(_X) = _Y; }
_Nodeptr _Ubound(const _K& _Kv) const
{_Lockit _Lk;
_Nodeptr _X = _Root();
_Nodeptr _Y = _Head;
while (_X != _Nil)
if (key_compare(_Kv, _Key(_X)))
_Y = _X, _X = _Left(_X);
else
_X = _Right(_X);
return (_Y); }
_Nodeptr _Buynode(_Nodeptr _Parg, _Redbl _Carg)
{_Nodeptr _S = (_Nodeptr)allocator._Charalloc(
1 * sizeof (_Node));
_Parent(_S) = _Parg;
_Color(_S) = _Carg;
return (_S); }
void _Consval(_Tptr _P, const _Ty& _V)
{_Construct(&*_P, _V); }
void _Destval(_Tptr _P)
{_Destroy(&*_P); }
void _Freenode(_Nodeptr _S)
{allocator.deallocate(_S, 1); }
_A allocator;
_Pr key_compare;
_Nodeptr _Head;
bool _Multi;
size_type _Size;
};
template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
_Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nodeptr
_Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nil = 0;
template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
size_t _Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nilrefs = 0;
// tree TEMPLATE OPERATORS
template<class _K, class _Ty, class _Kfn,
class _Pr, class _A> inline
bool operator==(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
{return (_X.size() == _Y.size()
&& equal(_X.begin(), _X.end(), _Y.begin())); }
template<class _K, class _Ty, class _Kfn,
class _Pr, class _A> inline
bool operator!=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
{return (!(_X == _Y)); }
template<class _K, class _Ty, class _Kfn,
class _Pr, class _A> inline
bool operator<(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
{return (lexicographical_compare(_X.begin(), _X.end(),
_Y.begin(), _Y.end())); }
template<class _K, class _Ty, class _Kfn,
class _Pr, class _A> inline
bool operator>(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
{return (_Y < _X); }
template<class _K, class _Ty, class _Kfn,
class _Pr, class _A> inline
bool operator<=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
{return (!(_Y < _X)); }
template<class _K, class _Ty, class _Kfn,
class _Pr, class _A> inline
bool operator>=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
{return (!(_X < _Y)); }
_STD_END
#ifdef _MSC_VER
#pragma pack(pop)
#endif /* _MSC_VER */
#endif /* _XTREE_ */
/*
* Copyright (c) 1995 by P.J. Plauger. ALL RIGHTS RESERVED.
* Consult your license regarding permissions and restrictions.
*/
/*
* This file is derived from software bearing the following
* restrictions:
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this
* software and its documentation for any purpose is hereby
* granted without fee, provided that the above copyright notice
* appear in all copies and that both that copyright notice and
* this permission notice appear in supporting documentation.
* Hewlett-Packard Company makes no representations about the
* suitability of this software for any purpose. It is provided
* "as is" without express or implied warranty.
*/
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -