list

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

			_STD forward<_Valty>(_Val));
		_CATCH_ALL
		this->_Alnod.deallocate(_Pnode, 1);
		_RERAISE;
		_CATCH_END

		return (_Pnode);
		}

	static _Nodepref _Nextnode(_Nodeptr _Pnode)
		{	// return reference to successor pointer in node
		return ((_Nodepref)(*_Pnode)._Next);
		}

	static _Nodepref _Prevnode(_Nodeptr _Pnode)
		{	// return reference to predecessor pointer in node
		return ((_Nodepref)(*_Pnode)._Prev);
		}

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

		// TEMPLATE CLASS list
template<class _Ty,
	class _Ax = allocator<_Ty> >
	class list
		: public _List_val<_Ty, _Ax>
	{	// bidirectional linked list
public:
	typedef list<_Ty, _Ax> _Myt;
	typedef _List_val<_Ty, _Ax> _Mybase;
	typedef typename _Mybase::_Alty _Alloc;
	typedef typename _Mybase::_Node _Node;
	typedef typename _Mybase::_Nodeptr _Nodeptr;

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

	typedef _List_const_iterator<_Mybase>
		const_iterator;
	typedef _List_iterator<_Mybase>
		iterator;

	typedef _STD reverse_iterator<iterator> reverse_iterator;
	typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;

	list()
		: _Mybase()
		{	// construct empty list
		}

	explicit list(const _Alloc& _Al)
		: _Mybase(_Al)
		{	// construct empty list, allocator
		}

	explicit list(size_type _Count)
		: _Mybase()
		{	// construct list from _Count * _Ty()
		resize(_Count);
		}

	list(size_type _Count, const _Ty& _Val)
		: _Mybase()
		{	// construct list from _Count * _Val
		_Construct_n(_Count, _Val);
		}

	list(size_type _Count, const _Ty& _Val, const _Alloc& _Al)
		: _Mybase(_Al)
		{	// construct list, allocator from _Count * _Val
		_Construct_n(_Count, _Val);
		}

	list(const _Myt& _Right)
		: _Mybase(_Right._Alval)
		{	// construct list by copying _Right
		_TRY_BEGIN
		insert(begin(), _Right.begin(), _Right.end());
		_CATCH_ALL
		_Tidy();
		_RERAISE;
		_CATCH_END
		}

	template<class _Iter>
		list(_Iter _First, _Iter _Last)
		: _Mybase()
		{	// construct list from [_First, _Last)
		_Construct(_First, _Last, _Iter_cat(_First));
		}

	template<class _Iter>
		list(_Iter _First, _Iter _Last, const _Alloc& _Al)
		: _Mybase(_Al)
		{	// construct list, allocator from [_First, _Last)
		_Construct(_First, _Last, _Iter_cat(_First));
		}

	template<class _Iter>
		void _Construct(_Iter _Count, _Iter _Val, _Int_iterator_tag)
		{	// construct list from _Count * _Val
		_Construct_n((size_type)_Count, (_Ty)_Val);
		}

	template<class _Iter>
		void _Construct(_Iter _First,
			_Iter _Last, input_iterator_tag)
		{	// construct list from [_First, _Last), input iterators
		_TRY_BEGIN
		insert(begin(), _First, _Last);
		_CATCH_ALL
		_Tidy();
		_RERAISE;
		_CATCH_END
		}

	void _Construct_n(size_type _Count,
		const _Ty& _Val)
		{	// construct from _Count * _Val
		_TRY_BEGIN
		_Insert_n(begin(), _Count, _Val);
		_CATCH_ALL
		_Tidy();
		_RERAISE;
		_CATCH_END
		}

	list(_Myt&& _Right)
		: _Mybase(_Right._Alval)
		{	// construct list 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)
			{	// clear this and steal from _Right
			clear();
			if (!_Right.empty())
				_Splice(begin(), _Right, _Right.begin(), _Right.end(),
					_Right._Mysize);
			}
		}

	void push_front(_Ty&& _Val)
		{	// insert element at beginning
		_Insert_rv(begin(), _STD forward<_Ty>(_Val));
		}

	void push_back(_Ty&& _Val)
		{	// insert element at end
		_Insert_rv(end(), _STD forward<_Ty>(_Val));
		}

	template<class _Valty>
		void emplace_front(_Valty&& _Val)
		{	// insert element at beginning
		_Insert_rv(begin(), _STD forward<_Valty>(_Val));
		}

	template<class _Valty>
		void emplace_back(_Valty&& _Val)
		{	// insert element at end
		_Insert_rv(end(), _STD forward<_Valty>(_Val));
		}

	template<class _Valty>
		iterator insert(const_iterator _Where, _Valty&& _Val)
		{	// insert _Val at _Where
		return (emplace(_Where, _STD forward<_Valty>(_Val)));
		}

	template<class _Valty>
		iterator emplace(const_iterator _Where, _Valty&& _Val)
		{	// insert _Val at _Where
		_Insert_rv(_Where, _STD forward<_Valty>(_Val));
		return (_Make_iter(--_Where));
		}

	template<class _Valty>
		void _Insert_rv(const_iterator _Where,
		_Valty&& _Val)
		{	// insert _Val at _Where
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Where._Getcont() != this)
			_DEBUG_ERROR("list insert iterator outside range");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		_Nodeptr _Pnode = _Where._Mynode();
		_Nodeptr _Newnode =
			this->_Buynode(_Pnode, this->_Prevnode(_Pnode),
				_STD forward<_Valty>(_Val));
		_Incsize(1);
		this->_Prevnode(_Pnode) = _Newnode;
		this->_Nextnode(this->_Prevnode(_Newnode)) = _Newnode;
		}

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

	~list()
		{	// destroy the object
		_Tidy();
		}

	_Myt& operator=(const _Myt& _Right)
		{	// assign _Right
		if (this != &_Right)
			assign(_Right.begin(), _Right.end());
		return (*this);
		}

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

	const_iterator begin() const
		{	// return iterator for beginning of nonmutable sequence
		return (const_iterator(this->_Nextnode(this->_Myhead), 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));
		}

	iterator _Make_iter(const_iterator _Where) const
		{	// make iterator from const_iterator
		return (iterator(_Where._Ptr, 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 */

	void resize(size_type _Newsize)
		{	// determine new length, padding with _Ty() elements as needed
		if (this->_Mysize < _Newsize)
			{	// pad to make larger
			size_type _Count = 0;
			_TRY_BEGIN
			for (; this->_Mysize < _Newsize; ++_Count)
				_Insert(end());
			_CATCH_ALL
			for (; 0 < _Count; --_Count)
				pop_back();	// undo inserts
			_RERAISE;
			_CATCH_END
			}
		else
			while (_Newsize < this->_Mysize)
				pop_back();
		}

	void resize(size_type _Newsize, const _Ty& _Val)
		{	// determine new length, padding with _Val elements as needed
		if (this->_Mysize < _Newsize)
			_Insert_n(end(), _Newsize - this->_Mysize, _Val);
		else
			while (_Newsize < this->_Mysize)
				pop_back();
		}

	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
		{	// test if sequence is empty
		return (this->_Mysize == 0);
		}

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

	reference front()
		{	// return first element of mutable sequence
		return (*begin());
		}

	const_reference front() const
		{	// return first element of nonmutable sequence
		return (*begin());
		}

	reference back()
		{	// return last element of mutable sequence
		return (*(--end()));
		}

	const_reference back() const
		{	// return last element of nonmutable sequence
		return (*(--end()));
		}

	void push_front(const _Ty& _Val)
		{	// insert element at beginning
		_Insert(begin(), _Val);
		}

	void pop_front()
		{	// erase element at beginning
		erase(begin());
		}

	void push_back(const _Ty& _Val)
		{	// insert element at end
		_Insert(end(), _Val);
		}

	void pop_back()
		{	// erase element at end
		erase(--end());
		}

	template<class _Iter>
		void assign(_Iter _First, _Iter _Last)
		{	// assign [_First, _Last)
		_Assign(_First, _Last, _Iter_cat(_First));
		}

	template<class _Iter>
		void _Assign(_Iter _Count, _Iter _Val, _Int_iterator_tag)
		{	// assign _Count * _Val
		_Assign_n((size_type)_Count, (_Ty)_Val);
		}

	template<class _Iter>
		void _Assign(_Iter _First, _Iter _Last, input_iterator_tag)
		{	// assign [_First, _Last), input iterators
		clear();
		insert(begin(), _First, _Last);
		}

	void assign(size_type _Count, const _Ty& _Val)
		{	// assign _Count * _Val
		_Assign_n(_Count, _Val);
		}

	iterator insert(const_iterator _Where, const _Ty& _Val)
		{	// insert _Val at _Where
		_Insert(_Where, _Val);
		return (_Make_iter(--_Where));
		}

	void _Insert(const_iterator _Where,
		const _Ty& _Val)
		{	// insert _Val at _Where
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Where._Getcont() != this)
			_DEBUG_ERROR("list insert iterator outside range");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		_Nodeptr _Pnode = _Where._Mynode();
		_Nodeptr _Newnode =
			this->_Buynode(_Pnode, this->_Prevnode(_Pnode), _Val);
		_Incsize(1);
		this->_Prevnode(_Pnode) = _Newnode;
		this->_Nextnode(this->_Prevnode(_Newnode)) = _Newnode;
		}

	void _Insert(const_iterator _Where)
		{	// insert _Ty() at _Where
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Where._Getcont() != this)
			_DEBUG_ERROR("list insert iterator outside range");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		_Nodeptr _Pnode = _Where._Mynode();
		_Nodeptr _Newnode =
			this->_Buynode(_Pnode, this->_Prevnode(_Pnode));
		_Incsize(1);
		this->_Prevnode(_Pnode) = _Newnode;
		this->_Nextnode(this->_Prevnode(_Newnode)) = _Newnode;
		}

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

	template<class _Iter>
		void insert(const_iterator _Where, _Iter _First, _Iter _Last)
		{	// insert [_First, _Last) at _Where
		_Insert(_Where, _First, _Last, _Iter_cat(_First));
		}

	template<class _Iter>
		void _Insert(const_iterator _Where, _Iter _Count, _Iter _Val,
			_Int_iterator_tag)
		{	// insert _Count * _Val at _Where
		_Insert_n(_Where, (size_type)_Count, (_Ty)_Val);
		}

	template<class _Iter>
		void _Insert(const_iterator _Where,
			_Iter _First, _Iter _Last, input_iterator_tag)
		{	// insert [_First, _Last) at _Where, input iterators
		size_type _Num = 0;

		_TRY_BEGIN
		for (; _First != _Last; ++_First, ++_Num)
			_Insert(_Where, *_First);
		_CATCH_ALL
		for (; 0 < _Num; --_Num)
			{	// undo inserts
			const_iterator _Before = _Where;
			erase(--_Before);
			}
		_RERAISE;
		_CATCH_END
		}

	template<class _Iter>
		void _Insert(const_iterator _Where,
			_Iter _First, _Iter _Last, forward_iterator_tag)
		{	// insert [_First, _Last) at _Where, forward iterators
		_DEBUG_RANGE(_First, _Last);
		_Iter _Next = _First;

		_TRY_BEGIN
		for (; _First != _Last; ++_First)
			_Insert(_Where, *_First);
		_CATCH_ALL
		for (; _Next != _First; ++_Next)
			{	// undo inserts
			const_iterator _Before = _Where;
			erase(--_Before);
			}
		_RERAISE;
		_CATCH_END
		}

	iterator erase(const_iterator _Where)
		{	// erase element at _Where
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Where._Getcont() != this || _Where._Ptr == this->_Myhead)
			_DEBUG_ERROR("list erase iterator outside range");
		_Nodeptr _Pnode = (_Where++)._Mynode();
		_Orphan_ptr(*this, _Pnode);

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
		_Nodeptr _Pnode = (_Where++)._Mynode();
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		if (_Pnode != this->_Myhead)
			{	// not list head, safe to erase
			this->_Nextnode(this->_Prevnode(_Pnode)) =
				this->_Nextnode(_Pnode);
			this->_Prevnode(this->_Nextnode(_Pnode)) =
				this->_Prevnode(_Pnode);

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

			--this->_Mysize;
			}
		return (_Make_iter(_Where));
		}

	iterator erase(const_iterator _First, const_iterator _Last)
		{	// erase [_First, _Last)
		if (_First == begin() && _Last == end())
			{	// erase all and return fresh iterator
			clear();
			return (end());
			}
		else
			{	// erase subrange
			while (_First != _Last)
				_First = erase(_First);
			return (_Make_iter(_Last));
			}
		}

	void clear()
		{	// erase all
 #if _ITERATOR_DEBUG_LEVEL == 2
		this->_Orphan_ptr(*this, 0);