deque

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

			push_front(_Val);
			_STD rotate(begin(), begin() + 1, begin() + 1 + _Off);
			}
		else
			{	// closer to back, push to back then copy
			push_back(_Val);
			_STD rotate(begin() + _Off, end() - 1, end());
			}
		return (begin() + _Off);
		}

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

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

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

	template<class _It>
		void _Insert(const_iterator _Where,
			_It _First, _It _Last, input_iterator_tag)
		{	// insert [_First, _Last) at _Where, input iterators
		size_type _Off = _Where - begin();

 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Mysize < _Off)
			_DEBUG_ERROR("deque insert iterator outside range");
		_DEBUG_RANGE(_First, _Last);
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		size_type _Oldsize = this->_Mysize;

		if (_First == _Last)
			;
		else if (_Off <= this->_Mysize / 2)
			{	// closer to front, push to front then rotate
			_TRY_BEGIN
			for (; _First != _Last; ++_First)
				push_front(*_First);	// prepend flipped

			_CATCH_ALL
			for (; _Oldsize < this->_Mysize; )
				pop_front();	// restore old size, at least
			_RERAISE;
			_CATCH_END

			size_type _Num = this->_Mysize - _Oldsize;
			_STD reverse(begin(), begin() + _Num);	// flip new stuff in place
			_STD rotate(begin(), begin() + _Num, begin() + _Num + _Off);
			}
		else
			{	// closer to back
			_TRY_BEGIN
			for (; _First != _Last; ++_First)
				push_back(*_First);	// append

			_CATCH_ALL
			for (; _Oldsize < this->_Mysize; )
				pop_back();	// restore old size, at least
			_RERAISE;
			_CATCH_END

			_STD rotate(begin() + _Off, begin() + _Oldsize, end());
			}
		}

	iterator erase(const_iterator _Where)
		{	// erase element at _Where
		return (erase(_Where, _Where + 1));
		}

	iterator erase(const_iterator _First_arg,
		const_iterator _Last_arg)
		{	// erase [_First, _Last)
		iterator _First = _Make_iter(_First_arg);
		iterator _Last = _Make_iter(_Last_arg);

 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Last < _First
			|| _First < begin() || end() < _Last)
			_DEBUG_ERROR("deque erase iterator outside range");
		_DEBUG_RANGE(_First, _Last);

		size_type _Off = _First - begin();
		size_type _Count = _Last - _First;
		bool _Moved = 0 < _Off && _Off + _Count < this->_Mysize;

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
		size_type _Off = _First - begin();
		size_type _Count = _Last - _First;
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		if (_Off < (size_type)(end() - _Last))
			{	// closer to front
			_Move_backward(begin(), _First, _Last);	// copy over hole
			for (; 0 < _Count; --_Count)
				pop_front();	// pop copied elements
			}
		else
			{	// closer to back
			_Move(_Last, end(), _First);	// copy over hole
			for (; 0 < _Count; --_Count)
				pop_back();	// pop copied elements
			}

 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Moved)
			this->_Orphan_all();
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		return (begin() + _Off);
		}

	void clear()
		{	// erase all
		_Tidy();
		}

	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);
			_Swap_adl(this->_Map, _Right._Map);
			_STD swap(this->_Mapsize, _Right._Mapsize);
			_STD swap(this->_Myoff, _Right._Myoff);
			_STD swap(this->_Mysize, _Right._Mysize);
			}
		else
			{	// different allocator, do multiple assigns
			_Myt _Ts = _Move(*this);

			*this = _Move(_Right);
			_Right = _Move(_Ts);
			}
		}

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

	void _Insert_n(const_iterator _Where,
		size_type _Count, const _Ty& _Val)
		{	// insert _Count * _Val at _Where
		iterator _Mid;
		size_type _Num;
		size_type _Off = _Where - begin();
		size_type _Rem = this->_Mysize - _Off;
		size_type _Oldsize = this->_Mysize;

 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Mysize < _Off)
			_DEBUG_ERROR("deque insert iterator outside range");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		if (_Off < _Rem)
			{	// closer to front
			_TRY_BEGIN
			if (_Off < _Count)
				{	// insert longer than prefix
				for (_Num = _Count - _Off; 0 < _Num; --_Num)
					push_front(_Val);	// push excess values
				for (_Num = _Off; 0 < _Num; --_Num)
					push_front(begin()[_Count - 1]);	// push prefix

				_Mid = begin() + _Count;
				_STD fill(_Mid, _Mid + _Off,
					_Val);	// fill in rest of values
				}
			else
				{	// insert not longer than prefix
				for (_Num = _Count; 0 < _Num; --_Num)
					push_front(begin()[_Count - 1]);	// push part of prefix

				_Mid = begin() + _Count;
				_Ty _Tmp = _Val;	// in case _Val is in sequence
				_Move(_Mid + _Count, _Mid + _Off,
					_Mid);	// copy rest of prefix
				_STD fill(begin() + _Off, _Mid + _Off,
					_Tmp);	// fill in values
				}
			_CATCH_ALL
			for (; _Oldsize < this->_Mysize; )
				pop_front();	// restore old size, at least
			_RERAISE;
			_CATCH_END
			}
		else
			{		// closer to back
			_TRY_BEGIN
			if (_Rem < _Count)
				{	// insert longer than suffix
				for (_Num = _Count - _Rem; 0 < _Num; --_Num)
					push_back(_Val);	// push excess values
				for (_Num = 0; _Num < _Rem; ++_Num)
					push_back(begin()[_Off + _Num]);	// push suffix

				_Mid = begin() + _Off;
				_STD fill(_Mid, _Mid + _Rem,
					_Val);	// fill in rest of values
				}
			else
				{	// insert not longer than prefix
				for (_Num = 0; _Num < _Count; ++_Num)
					push_back(begin()[_Off + _Rem
						- _Count + _Num]);	// push part of prefix

				_Mid = begin() + _Off;
				_Ty _Tmp = _Val;	// in case _Val is in sequence
				_Move_backward(_Mid, _Mid + _Rem - _Count,
					_Mid + _Rem);	// copy rest of prefix
				_STD fill(_Mid, _Mid + _Count,
					_Tmp);	// fill in values
				}
			_CATCH_ALL
			for (; _Oldsize < this->_Mysize; )
				pop_back();	// restore old size, at least
			_RERAISE;
			_CATCH_END
			}
		}

	__declspec(noreturn) void _Xlen() const
		{	// report a length_error
		_Xlength_error("deque<T> too long");
		}

	__declspec(noreturn) void _Xran() const
		{	// report an out_of_range error
		_Xout_of_range("invalid deque<T> subscript");
		}

	void _Growmap(size_type _Count)
		{	// grow map by _Count pointers
		if (max_size() / _DEQUESIZ - this->_Mapsize < _Count)
			_Xlen();	// result too long

		size_type _Inc = this->_Mapsize / 2;	// try to grow by 50%
		if (_Inc < _DEQUEMAPSIZ)
			_Inc = _DEQUEMAPSIZ;
		if (_Count < _Inc && this->_Mapsize <= max_size() / _DEQUESIZ - _Inc)
			_Count = _Inc;
		size_type _Myboff = this->_Myoff / _DEQUESIZ;
		_Mapptr _Newmap = this->_Almap.allocate(this->_Mapsize + _Count);
		_Mapptr _Myptr = _Newmap + _Myboff;

		_Myptr = _Uninitialized_copy(this->_Map + _Myboff,
			this->_Map + this->_Mapsize,
			_Myptr, this->_Almap);	// copy initial to end
		if (_Myboff <= _Count)
			{	// increment greater than offset of initial block
			_Myptr = _Uninitialized_copy(this->_Map,
				this->_Map + _Myboff,
				_Myptr, this->_Almap);	// copy rest of old
			_Uninitialized_default_fill_n(_Myptr, _Count - _Myboff,
				(pointer *)0, this->_Almap);	// clear suffix of new
			_Uninitialized_default_fill_n(_Newmap, _Myboff,
				(pointer *)0, this->_Almap);	// clear prefix of new
			}
		else
			{	// increment not greater than offset of initial block
			_Uninitialized_copy(this->_Map,
				this->_Map + _Count,
				_Myptr, this->_Almap);	// copy more old
			_Myptr = _Uninitialized_copy(this->_Map + _Count,
				this->_Map + _Myboff,
				_Newmap, this->_Almap);	// copy rest of old
			_Uninitialized_default_fill_n(_Myptr, _Count,
				(pointer *)0, this->_Almap);	// clear rest to initial block
			}

		_Destroy_range(this->_Map + _Myboff, this->_Map + this->_Mapsize,
			this->_Almap);
		if (this->_Map != 0)
			this->_Almap.deallocate(this->_Map,
				this->_Mapsize);	// free storage for old

		this->_Map = _Newmap;	// point at new
		this->_Mapsize += _Count;
		}

	void _Tidy()
		{	// free all storage
		while (!empty())
			pop_back();
		for (size_type _Count = this->_Mapsize; 0 < _Count; )
			{	// free storage for a block and destroy pointer
			if (*(this->_Map + --_Count) != 0)
				{	// free block and destroy its pointer
				this->_Alval.deallocate(*(this->_Map + _Count), _DEQUESIZ);
				_Dest_val(this->_Almap, this->_Map + _Count);
				}
			}

		if (this->_Map != 0)
			this->_Almap.deallocate(this->_Map,
				this->_Mapsize);	// free storage for map
		this->_Mapsize = 0;
		this->_Map = 0;
		}

 #if _ITERATOR_DEBUG_LEVEL == 2
	void _Orphan_off(size_type _Offlo) const
		{	// orphan iterators with specified offset(s)
		size_type _Offhigh = this->_Myoff + this->_Mysize <= _Offlo + 1
			? (size_type)(-1) : _Offlo;
		if (_Offlo == this->_Myoff)
			_Offlo = 0;

		_Lockit _Lock(_LOCK_DEBUG);
		const_iterator **_Pnext = (const_iterator **)this->_Getpfirst();
		if (_Pnext != 0)
			while (*_Pnext != 0)
				if ((*_Pnext)->_Myoff < _Offlo
					|| _Offhigh < (*_Pnext)->_Myoff)
					_Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
				else
					{	// orphan the iterator
					(*_Pnext)->_Clrcont();
					*_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
					}
		}
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
	};

	// deque TEMPLATE OPERATORS

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

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

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

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

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

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

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

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

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

 #pragma warning(pop)
 #pragma pack(pop)

#endif /* RC_INVOKED */
#endif /* _DEQUE_ */

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