list

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

 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		_Nodeptr _Pnext;
		_Nodeptr _Pnode = this->_Nextnode(this->_Myhead);
		this->_Nextnode(this->_Myhead) = this->_Myhead;
		this->_Prevnode(this->_Myhead) = this->_Myhead;
		this->_Mysize = 0;

		for (; _Pnode != this->_Myhead; _Pnode = _Pnext)
			{	// delete an element
			_Pnext = this->_Nextnode(_Pnode);

			_Dest_val(this->_Alnod, _Pnode);
			this->_Alnod.deallocate(_Pnode, 1);
			}
		}

	void swap(_Myt& _Right)
		{	// exchange contents with _Right
		if (this == &_Right)
			;	// same object, do nothing
		else if (this->_Alval == _Right._Alval)
			{	// same allocator, swap control information
			this->_Swap_all(_Right);
			_STD swap(this->_Myhead, _Right._Myhead);
			_STD swap(this->_Mysize, _Right._Mysize);
			}
		else
			{	// different allocator, do splices
			iterator _Where = begin();
			splice(_Where, _Right);
			_Right.splice(_Right.begin(), *this, _Where, end());
			}
		}

	void splice(const_iterator _Where, _Myt& _Right)
		{	// splice all of _Right at _Where
		if (this != &_Right && !_Right.empty())
			{	// worth splicing, do it
			_Splice(_Where, _Right, _Right.begin(), _Right.end(),
				_Right._Mysize);
			}
		}

	void splice(const_iterator _Where, _Myt& _Right,
		const_iterator _First)
		{	// splice _Right [_First, _First + 1) at _Where
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_First == _Right.end())
			_DEBUG_ERROR("list splice iterator outside range");
		else

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
		if (_First != _Right.end())
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

			{	// element exists, try splice
			const_iterator _Last = _First;
			++_Last;
			if (this != &_Right
				|| (_Where != _First && _Where != _Last))
				_Splice(_Where, _Right, _First, _Last, 1);
			}
		}

	void splice(const_iterator _Where,
		_Myt& _Right, const_iterator _First, const_iterator _Last)
		{	// splice _Right [_First, _Last) at _Where
		if (_First != _Last && (this != &_Right || _Where != _Last))
			{	// worth splicing, do it
			size_type _Count = 0;

			if (this == &_Right)
				;	// just rearrange this list
			else if (_First == _Right.begin() && _Last == _Right.end())
				_Count = _Right._Mysize;	// splice in whole list
			else
				{	// count nodes and check for knot
				const_iterator _Next = _First;

				for (; _Next != _Last; ++_Next, ++_Count)
					if (_Next == _Right.end())
						_Xlength_error("list<T> bad splice");
				}
			_Splice(_Where, _Right, _First, _Last, _Count);
			}
		}

	void remove(const _Ty& _Val_arg)
		{	// erase each element matching _Val
		const _Ty _Val = _Val_arg;	// in case it's removed along the way
		const _Nodeptr _Phead = this->_Myhead;
		_Nodeptr _Pnode = _Phead->_Next;

		while (_Pnode != _Phead)
			if (_Pnode->_Myval == _Val)
				{	// match, remove it
				const _Nodeptr _Pprev = _Pnode->_Prev;
				const _Nodeptr _Perase = _Pnode;
				_Pnode = _Pnode->_Next;

				_Pprev->_Next = _Pnode;
				_Pnode->_Prev = _Pprev;

				_Dest_val(this->_Alnod, _Perase);
				this->_Alnod.deallocate(_Perase, 1);
				--this->_Mysize;
				}
			else
				_Pnode = _Pnode->_Next;
		}

	template<class _Pr1>
		void remove_if(_Pr1 _Pred)
		{	// erase each element satisfying _Pred
		const _Nodeptr _Phead = this->_Myhead;
		_Nodeptr _Pnode = _Phead->_Next;

		while (_Pnode != _Phead)
			if (_Pred(_Pnode->_Myval))
				{	// match, remove it
				const _Nodeptr _Pprev = _Pnode->_Prev;
				const _Nodeptr _Perase = _Pnode;
				_Pnode = _Pnode->_Next;

				_Pprev->_Next = _Pnode;
				_Pnode->_Prev = _Pprev;

				_Dest_val(this->_Alnod, _Perase);
				this->_Alnod.deallocate(_Perase, 1);
				--this->_Mysize;
				}
			else
				_Pnode = _Pnode->_Next;
		}

	void unique()
		{	// erase each element matching previous
		const _Nodeptr _Phead = this->_Myhead;
		_Nodeptr _Pprev = _Phead->_Next;
		_Nodeptr _Pnode = _Pprev->_Next;

		while (_Pnode != _Phead)
			if (_Pprev->_Myval == _Pnode->_Myval)
				{	// match, remove it
				const _Nodeptr _Perase = _Pnode;
				_Pnode = _Pnode->_Next;

				_Pprev->_Next = _Pnode;
				_Pnode->_Prev = _Pprev;

				_Dest_val(this->_Alnod, _Perase);
				this->_Alnod.deallocate(_Perase, 1);
				--this->_Mysize;
				}
			else
				{	// no match, advance
				_Pprev = _Pnode;
				_Pnode = _Pnode->_Next;
				}
		}

	template<class _Pr2>
		void unique(_Pr2 _Pred)
		{	// erase each element satisfying _Pred with previous
		const _Nodeptr _Phead = this->_Myhead;
		_Nodeptr _Pprev = _Phead->_Next;
		_Nodeptr _Pnode = _Pprev->_Next;

		while (_Pnode != _Phead)
			if (_Pred(_Pprev->_Myval, _Pnode->_Myval))
				{	// match, remove it
				const _Nodeptr _Perase = _Pnode;
				_Pnode = _Pnode->_Next;

				_Pprev->_Next = _Pnode;
				_Pnode->_Prev = _Pprev;

				_Dest_val(this->_Alnod, _Perase);
				this->_Alnod.deallocate(_Perase, 1);
				--this->_Mysize;
				}
			else
				{	// no match, advance
				_Pprev = _Pnode;
				_Pnode = _Pnode->_Next;
				}
		}

	void merge(_Myt& _Right)
		{	// merge in elements from _Right, both ordered by operator<
		if (&_Right != this)
			{	// safe to merge, do it
			iterator _First1 = begin(), _Last1 = end();
			iterator _First2 = _Right.begin(), _Last2 = _Right.end();
			_DEBUG_ORDER(_First1, _Last1);
			_DEBUG_ORDER(_First2, _Last2);

			while (_First1 != _Last1 && _First2 != _Last2)
				if (_DEBUG_LT(*_First2, *_First1))
					{	// splice in an element from _Right
					iterator _Mid2 = _First2;
					_Splice(_First1, _Right, _First2, ++_Mid2, 1);
					_First2 = _Mid2;
					}
				else
					++_First1;

			if (_First2 != _Last2)
				_Splice(_Last1, _Right, _First2, _Last2,
					_Right._Mysize);	// splice remainder of _Right
			}
		}

	template<class _Pr3>
		void merge(_Myt& _Right, _Pr3 _Pred)
		{	// merge in elements from _Right, both ordered by _Pred
		if (&_Right != this)
			{	// safe to merge, do it
			iterator _First1 = begin(), _Last1 = end();
			iterator _First2 = _Right.begin(), _Last2 = _Right.end();
			_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
			_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);

			while (_First1 != _Last1 && _First2 != _Last2)
				if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
					{	// splice in an element from _Right
					iterator _Mid2 = _First2;
					_Splice(_First1, _Right, _First2, ++_Mid2, 1);
					_First2 = _Mid2;
					}
				else
					++_First1;

			if (_First2 != _Last2)
				_Splice(_Last1, _Right, _First2, _Last2,
					_Right._Mysize);	// splice remainder of _Right
			}
		}

	void sort()
		{	// order sequence, using operator<
		if (2 <= this->_Mysize)
			{	// worth sorting, do it
			const size_t _MAXBINS = 25;
			_Myt _Templist(this->_Alval), _Binlist[_MAXBINS + 1];
			size_t _Maxbin = 0;

			while (!empty())
				{	// sort another element, using bins
				_Templist._Splice_same(_Templist.begin(), *this, begin(),
					++begin(), 1);

				size_t _Bin;
				for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty();
					++_Bin)
					{	// merge into ever larger bins
					_Binlist[_Bin].merge(_Templist);
					_Binlist[_Bin].swap(_Templist);
					}

				if (_Bin == _MAXBINS)
					_Binlist[_Bin - 1].merge(_Templist);
				else
					{	// spill to new bin, while they last
					_Binlist[_Bin].swap(_Templist);
					if (_Bin == _Maxbin)
						++_Maxbin;
					}
				}

			for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin)
				_Binlist[_Bin].merge(_Binlist[_Bin - 1]);	// merge up
			splice(begin(), _Binlist[_Maxbin - 1]);	// result in last bin
			}
		}

	template<class _Pr3>
		void sort(_Pr3 _Pred)
		{	// order sequence, using _Pred
		if (2 <= this->_Mysize)
			{	// worth sorting, do it
			const size_t _MAXBINS = 25;
			_Myt _Templist(this->_Alval), _Binlist[_MAXBINS + 1];
			size_t _Maxbin = 0;

			while (!empty())
				{	// sort another element, using bins
				_Templist._Splice_same(_Templist.begin(), *this, begin(),
					++begin(), 1);

				size_t _Bin;
				for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty();
					++_Bin)
					{	// merge into ever larger bins
					_Binlist[_Bin].merge(_Templist, _Pred);
					_Binlist[_Bin].swap(_Templist);
					}

				if (_Bin == _MAXBINS)
					_Binlist[_Bin - 1].merge(_Templist, _Pred);
				else
					{	// spill to new bin, while they last
					_Binlist[_Bin].swap(_Templist);
					if (_Bin == _Maxbin)
						++_Maxbin;
					}
				}

			for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin)
				_Binlist[_Bin].merge(_Binlist[_Bin - 1],
					_Pred);	// merge up
			splice(begin(), _Binlist[_Maxbin - 1]);	// result in last bin
			}
		}

	void reverse()
		{	// reverse sequence
		const _Nodeptr _Phead = this->_Myhead;
		_Nodeptr _Pnode = _Phead;

		for (; ; )
			{	// flip pointers in a node
			const _Nodeptr _Pnext = _Pnode->_Next;
			_Pnode->_Next = _Pnode->_Prev;
			_Pnode->_Prev = _Pnext;

			if (_Pnext == _Phead)
				break;
			_Pnode = _Pnext;
			}
		}

	void _Splice(const_iterator _Where,
		_Myt& _Right, const_iterator _First, const_iterator _Last,
		size_type _Count)
		{	// splice _Right [_First, _Last) before _Where
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Where._Getcont() != this)
			_DEBUG_ERROR("list splice iterator outside range");
		if (this->_Alval == _Right._Alval)
			{	// same allocator, just relink
			if (this != &_Right)
				for (const_iterator _Next = _First; _Next != _Last; )
					{	// transfer ownership
					const_iterator _Iter = _Next++;
					_Orphan_ptr(_Right, _Iter._Ptr);
					_Iter._Adopt(this);
					}
			_Splice_same(_Where, _Right, _First, _Last, _Count);
			}

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
		if (this->_Alval == _Right._Alval)
			_Splice_same(_Where, _Right, _First, _Last, _Count);
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		else
			{	// different allocator, copy nodes then erase source
			for (const_iterator _Next = _First; _Next != _Last; ++_Next)
				insert(_Where, (_Ty &&)*_Next);
			_Right.erase(_First, _Last);
			}
		}

	void _Splice_same(const_iterator _Where,
		_Myt& _Right, const_iterator _First, const_iterator _Last,
		size_type _Count)
		{	// splice _Right [_First, _Last) before _Where
		if (this != &_Right)
			{	// splicing from another list, adjust counts
			_Incsize(_Count);
			_Right._Mysize -= _Count;
			}
		this->_Nextnode(this->_Prevnode(_First._Mynode())) =
			_Last._Mynode();
		this->_Nextnode(this->_Prevnode(_Last._Mynode())) =
			_Where._Mynode();
		this->_Nextnode(this->_Prevnode(_Where._Mynode())) =
			_First._Mynode();

		_Nodeptr _Pnode = this->_Prevnode(_Where._Mynode());
		this->_Prevnode(_Where._Mynode()) =
			this->_Prevnode(_Last._Mynode());
		this->_Prevnode(_Last._Mynode()) =
			this->_Prevnode(_First._Mynode());
		this->_Prevnode(_First._Mynode()) = _Pnode;
		}

	void _Assign_n(size_type _Count, const _Ty& _Val)
		{	// assign _Count * _Val
		_Ty _Tmp = _Val;	// in case _Val is in sequence
		clear();
		_Insert_n(begin(), _Count, _Tmp);
		}

	void _Tidy()
		{	// free all storage
		clear();
		}

	void _Insert_n(const_iterator _Where,
		size_type _Count, const _Ty& _Val)
		{	// insert _Count * _Val at _Where
		size_type _Countsave = _Count;

		_TRY_BEGIN
		for (; 0 < _Count; --_Count)
			_Insert(_Where, _Val);
		_CATCH_ALL
		for (; _Count < _Countsave; ++_Count)
			{	// undo inserts
			const_iterator _Before = _Where;
			erase(--_Before);
			}
		_RERAISE;
		_CATCH_END
		}

	void _Incsize(size_type _Count)
		{	// alter element count, with checking
		if (max_size() - this->_Mysize - 1 < _Count)
			_Xlength_error("list<T> too long");
		this->_Mysize += _Count;
		}

 #if _ITERATOR_DEBUG_LEVEL == 2
	void _Orphan_ptr(_Myt& _Cont, _Nodeptr _Ptr) const
		{	// orphan iterators with specified node pointers
		_Lockit _Lock(_LOCK_DEBUG);
		const_iterator **_Pnext = (const_iterator **)_Cont._Getpfirst();
		if (_Pnext != 0)
			while (*_Pnext != 0)
				if ((*_Pnext)->_Ptr == this->_Myhead
					|| _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr)
					_Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
				else
					{	// orphan the iterator
					(*_Pnext)->_Clrcont();
					*_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
					}
		}
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
	};

		// list TEMPLATE OPERATORS

template<class _Ty,
	class _Alloc> inline
	void swap(list<_Ty, _Alloc>& _Left, list<_Ty, _Alloc>& _Right)
	{	// swap _Left and _Right lists
	_Left.swap(_Right);
	}

template<class _Ty,
	class _Alloc> inline
	void swap(list<_Ty, _Alloc>& _Left, list<_Ty, _Alloc>&& _Right)
	{	// swap _Left and _Right lists
	typedef list<_Ty, _Alloc> _Myt;
	_Left.swap(_STD forward<_Myt>(_Right));
	}

template<class _Ty,
	class _Alloc> inline
	void swap(list<_Ty, _Alloc>&& _Left, list<_Ty, _Alloc>& _Right)
	{	// swap _Left and _Right lists
	typedef list<_Ty, _Alloc> _Myt;
	_Right.swap(_STD forward<_Myt>(_Left));
	}

template<class _Ty,
	class _Alloc> inline
	bool operator==(const list<_Ty, _Alloc>& _Left,
		const list<_Ty, _Alloc>& _Right)
	{	// test for list equality
	return (_Left.size() == _Right.size()
		&& equal(_Left.begin(), _Left.end(), _Right.begin()));
	}

template<class _Ty,
	class _Alloc> inline
	bool operator!=(const list<_Ty, _Alloc>& _Left,
		const list<_Ty, _Alloc>& _Right)
	{	// test for list inequality
	return (!(_Left == _Right));
	}

template<class _Ty,
	class _Alloc> inline
	bool operator<(const list<_Ty, _Alloc>& _Left,
		const list<_Ty, _Alloc>& _Right)
	{	// test if _Left < _Right for lists
	return (lexicographical_compare(_Left.begin(), _Left.end(),
		_Right.begin(), _Right.end()));
	}

template<class _Ty,
	class _Alloc> inline
	bool operator>(const list<_Ty, _Alloc>& _Left,
		const list<_Ty, _Alloc>& _Right)
	{	// test if _Left > _Right for lists
	return (_Right < _Left);
	}

template<class _Ty,
	class _Alloc> inline
	bool operator<=(const list<_Ty, _Alloc>& _Left,
		const list<_Ty, _Alloc>& _Right)
	{	// test if _Left <= _Right for lists
	return (!(_Right < _Left));
	}

template<class _Ty,
	class _Alloc> inline
	bool operator>=(const list<_Ty, _Alloc>& _Left,
		const list<_Ty, _Alloc>& _Right)
	{	// test if _Left >= _Right for lists
	return (!(_Left < _Right));
	}
_STD_END
 #pragma warning(pop)
 #pragma pack(pop)

#endif /* RC_INVOKED */
#endif /* _LIST_ */

/*
 * 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.
 */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V5.20:0009 */