xtree

C语言库函数的原型,有用的拿去

	_Tree_nod(const key_compare& _Parg,
		allocator_type _Al)
		: _Traits(_Parg), _Alnod(_Al), _Alval(_Al)
		{	// construct traits from _Parg, allocators and proxy from _Al
		typename allocator_type::template rebind<_Container_proxy>::other
			_Alproxy(_Alnod);
		this->_Myproxy = _Alproxy.allocate(1);
		_Cons_val(_Alproxy, this->_Myproxy, _Container_proxy());
		this->_Myproxy->_Mycont = this;
		}

	~_Tree_nod()
		{	// destroy proxy
		typename allocator_type::template rebind<_Container_proxy>::other
			_Alproxy(_Alnod);
		this->_Orphan_all();
		_Dest_val(_Alproxy, this->_Myproxy);
		_Alproxy.deallocate(this->_Myproxy, 1);
		this->_Myproxy = 0;
		}
 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */

	_Nodeptr _Myhead;	// pointer to head node
	size_type _Mysize;	// number of elements

	typename allocator_type::template rebind<_Node>::other
		_Alnod;	// allocator object for nodes
	_Alty _Alval;	// allocator object for element values
	};

		// TEMPLATE CLASS _Tree_val
template<class _Traits>
	class _Tree_val
		: public _Tree_nod<_Traits>
	{	// base class for _Tree to hold allocator _Alval
public:
	typedef _Tree_nod<_Traits> _Mybase;
	typedef typename _Traits::allocator_type allocator_type;
	typedef typename _Traits::key_compare key_compare;
	typedef typename _Traits::key_type key_type;

	typedef typename _Mybase::_Nodeptr _Nodeptr;
	typedef typename _Mybase::_Nodepref _Nodepref;
	typedef typename _Mybase::_Alty _Alty;

	typedef typename _Alty::size_type size_type;
	typedef typename _Alty::difference_type difference_type;
	typedef typename _Alty::pointer pointer;
	typedef typename _Alty::const_pointer const_pointer;
	typedef typename _Alty::reference reference;
	typedef typename _Alty::const_reference const_reference;
	typedef typename _Alty::value_type value_type;

	_Tree_val(const key_compare& _Parg,
		allocator_type _Al)
		: _Mybase(_Parg, _Al)
		{	// construct base, and allocator from _Al
		this->_Mysize = 0;
		this->_Myhead = this->_Alnod.allocate(1);

		this->_Left(this->_Myhead) = this->_Myhead;
		this->_Parent(this->_Myhead) = this->_Myhead;
		this->_Right(this->_Myhead) = this->_Myhead;
		this->_Color(this->_Myhead) = this->_Black;
		this->_Isnil(this->_Myhead) = true;
		}

	~_Tree_val()
		{	// destroy the object
		this->_Alnod.deallocate(this->_Myhead, 1);
		}

	_Nodeptr _Buynode()
		{	// allocate a node
		_Nodeptr _Wherenode = this->_Alnod.allocate(1);

		this->_Left(_Wherenode) = this->_Myhead;
		this->_Parent(_Wherenode) = this->_Myhead;
		this->_Right(_Wherenode) = this->_Myhead;
		this->_Color(_Wherenode) = this->_Red;
		this->_Isnil(_Wherenode) = false;
		return (_Wherenode);
		}

	_Nodeptr _Buynode(const value_type& _Val)
		{	// allocate a node with defaults
		_Nodeptr _Wherenode = _Buynode();

		_TRY_BEGIN
		_Cons_val(this->_Alval, _STD addressof(this->_Myval(_Wherenode)),
			_Val);
		_CATCH_ALL
		this->_Alnod.deallocate(_Wherenode, 1);
		_RERAISE;
		_CATCH_END

		return (_Wherenode);
		}

	template<class _Valty>
		_Nodeptr _Buynode(_Valty&& _Val)
		{	// allocate a node with defaults
		_Nodeptr _Wherenode = _Buynode();

		_TRY_BEGIN
		_Cons_val(this->_Alval, _STD addressof(this->_Myval(_Wherenode)),
			_STD forward<_Valty>(_Val));
		_CATCH_ALL
		this->_Alnod.deallocate(_Wherenode, 1);
		_RERAISE;
		_CATCH_END

		return (_Wherenode);
		}

	enum _Redbl
		{	// colors for link to parent
		_Red, _Black};

	static char& _Color(_Nodeptr _Pnode)
		{	// return reference to color in node
		return ((char&)(*_Pnode)._Color);
		}

	static char& _Isnil(_Nodeptr _Pnode)
		{	// return reference to nil flag in node
		return ((char&)(*_Pnode)._Isnil);
		}

	static key_type& _Key(_Nodeptr _Pnode)
		{	// return reference to key in node
		return ((key_type&)_Traits::_Kfn(_Myval(_Pnode)));
		}

	static _Nodepref _Left(_Nodeptr _Pnode)
		{	// return reference to left pointer in node
		return ((_Nodepref)(*_Pnode)._Left);
		}

	static _Nodepref _Parent(_Nodeptr _Pnode)
		{	// return reference to parent pointer in node
		return ((_Nodepref)(*_Pnode)._Parent);
		}

	static _Nodepref _Right(_Nodeptr _Pnode)
		{	// return reference to right pointer in node
		return ((_Nodepref)(*_Pnode)._Right);
		}

	static reference _Myval(_Nodeptr _Pnode)
		{	// return reference to value in node
		return ((reference)(*_Pnode)._Myval);
		}

	static _Nodeptr _Max(_Nodeptr _Pnode)
		{	// return rightmost node in subtree at _Pnode
		while (!_Isnil(_Right(_Pnode)))
			_Pnode = _Right(_Pnode);
		return (_Pnode);
		}

	static _Nodeptr _Min(_Nodeptr _Pnode)
		{	// return leftmost node in subtree at _Pnode
		while (!_Isnil(_Left(_Pnode)))
			_Pnode = _Left(_Pnode);
		return (_Pnode);
		}
	};

		// TEMPLATE CLASS _Tree
template<class _Traits>
	class _Tree
		: public _Tree_val<_Traits>
	{	// ordered red-black tree for [multi_]{map set}
public:
	typedef _Tree<_Traits> _Myt;
	typedef _Tree_val<_Traits> _Mybase;
	typedef typename _Mybase::_Val_type _Val_type;
	typedef typename _Mybase::_Node _Node;
	typedef typename _Mybase::_Nodeptr _Nodeptr;

	typedef typename _Traits::key_type key_type;
	typedef typename _Traits::key_compare key_compare;
	typedef typename _Traits::value_compare value_compare;
	typedef typename _Traits::value_type value_type;
	typedef typename _Traits::allocator_type allocator_type;

	typedef typename allocator_type::size_type size_type;
	typedef typename allocator_type::difference_type difference_type;
	typedef typename allocator_type::pointer pointer;
	typedef typename allocator_type::const_pointer const_pointer;
	typedef typename allocator_type::reference reference;
	typedef typename allocator_type::const_reference const_reference;

	typedef _Tree_const_iterator<_Mybase>
		const_iterator;

	typedef typename _STD tr1::conditional<
		_STD tr1::is_same<key_type, value_type>::value,
		const_iterator,
		_Tree_iterator<_Mybase> >::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;

	explicit _Tree(const key_compare& _Parg,
		const allocator_type& _Al)
		: _Mybase(_Parg, _Al)
		{	// construct empty tree
		}

	_Tree(const value_type *_First, const value_type *_Last,
		const key_compare& _Parg, const allocator_type& _Al)
		: _Mybase(_Parg, _Al)
		{	// construct tree from [_First, _Last) array
		_TRY_BEGIN
		insert(_First, _Last);
		_CATCH_ALL
		_Tidy();
		_RERAISE;
		_CATCH_END
		}

	_Tree(const _Myt& _Right)
		: _Mybase(_Right.key_comp(), _Right._Alval)
		{	// construct tree by copying _Right
		_TRY_BEGIN
		_Copy(_Right);
		_CATCH_ALL
		_Tidy();
		_RERAISE;
		_CATCH_END
		}

	_Tree(_Myt&& _Right)
		: _Mybase(_Right.key_comp(), _Right._Alval)
		{	// construct tree by copying _Right
		_Assign_rv(_STD forward<_Myt>(_Right));
		}

	_Myt& operator=(_Myt&& _Right)
		{	// assign by moving _Right
		_Assign_rv(_STD forward<_Myt>(_Right));
		return (*this);
		}

	void _Assign_rv(_Myt&& _Right)
		{	// assign by moving _Right
		if (this == &_Right)
			;
		else if (get_allocator() != _Right.get_allocator())
			_Xinvalid_argument("invalid map/set<T> move assign");
		else
			{	// clear this and steal from _Right
			clear();
			this->_Swap_all(_Right);
			_Swap_adl(this->comp, _Right.comp);
			_STD swap(this->_Myhead, _Right._Myhead);
			_STD swap(this->_Mysize, _Right._Mysize);
			}
		}

	template<class _Valty>
		_Pairib insert(_Valty&& _Val)
		{	// try to insert node with value _Val, favoring right side
		return (_Linsert(this->_Buynode(_STD forward<_Valty>(_Val)),
			false));
		}

	template<class _Valty>
		typename _STD tr1::enable_if<!_STD tr1::is_same<const_iterator,
			typename _STD tr1::remove_reference<_Valty>::type>::value,
				iterator>::type
		insert(const_iterator _Where,
			_Valty&& _Val)
		{	// try to insert node with value _Val using _Where as a hint
		return (_Insert(_Where,
			this->_Buynode(_STD forward<_Valty>(_Val))));
		}

	template<class _Valty>
		_Pairib emplace(_Valty&& _Val)
		{	// try to insert node with value _Val, favoring right side
		return (_Linsert(this->_Buynode(_STD forward<_Valty>(_Val)),
			false));
		}

	template<class _Valty>
		iterator emplace_hint(const_iterator _Where, _Valty&& _Val)
		{	// insert _Val at _Where
		return (_Insert(_Where,
			this->_Buynode(_STD forward<_Valty>(_Val))));
		}

	void swap(_Myt&& _Right)
		{	// exchange contents with movable _Right
		_Assign_rv(_STD forward<_Myt>(_Right));
		}

	~_Tree()
		{	// destroy tree
		_Tidy();
		}

	_Myt& operator=(const _Myt& _Right)
		{	// replace contents from _Right
		if (this != &_Right)
			{	// worth doing
			erase(begin(), end());
			this->comp = _Right.comp;
			_Copy(_Right);
			}
		return (*this);
		}

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

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

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

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

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

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

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

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

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

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

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

	const_reverse_iterator crend() const
		{	// return iterator for ebd of reversed nonmutable sequence
		return (((const _Myt *)this)->rend());
		}
 #endif /* _HAS_CPP0X */

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

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

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

	allocator_type get_allocator() const
		{	// return allocator object for values
		return (this->_Alval);
		}

	key_compare key_comp() const
		{	// return object for comparing keys
		return (this->comp);
		}

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

	_Pairib insert(const value_type& _Val)
		{	// try to insert node with value _Val, favoring right side
		return (insert(_Val, false));
		}

	_Pairib insert(const value_type& _Val, bool _Leftish)
		{	// try to insert node with value _Val, on left if _Leftish
		_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->comp,
					this->_Key(_Trynode),
					this->_Kfn(_Val));	// favor left end
			else
				_Addleft = _DEBUG_LT_PRED(this->comp,
					this->_Kfn(_Val),
					this->_Key(_Trynode));	// favor right end
			_Trynode = _Addleft ? this->_Left(_Trynode)
				: this->_Right(_Trynode);
			}

		if (this->_Multi)
			return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), 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(true, _Wherenode, _Val), 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, _Val), true));
			else
				return (_Pairib(_Where, false));
			}
		}

	_Pairib _Linsert(_Nodeptr _Node, bool _Leftish)
		{	// try to insert node at _Node, on left if _Leftish
		const value_type& _Val = this->_Myval(_Node);

		_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->comp,
					this->_Key(_Trynode),
					this->_Kfn(_Val));	// favor left end
			else
				_Addleft = _DEBUG_LT_PRED(this->comp,
					this->_Kfn(_Val),
					this->_Key(_Trynode));	// favor right end
			_Trynode = _Addleft ? this->_Left(_Trynode)
				: this->_Right(_Trynode);
			}

		if (this->_Multi)
			return (_Pairib(_Insert(_Addleft, _Wherenode, _Node), true));
		else
			{	// insert only if unique
			iterator _Where = iterator(_Wherenode, this);
			if (!_Addleft)