deque

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

		}

	_Myiter& operator-=(difference_type _Off)
		{	// decrement by integer
		return (*this += -_Off);
		}

	_Myiter operator-(difference_type _Off) const
		{	// return this - integer
		_Myiter _Tmp = *this;
		return (_Tmp -= _Off);
		}

	difference_type operator-(const _Myiter& _Right) const
		{	// return difference of iterators
		_Compat(_Right);
		return (_Right._Myoff <= this->_Myoff
			? this->_Myoff - _Right._Myoff
			: -(difference_type)(_Right._Myoff - this->_Myoff));
		}

	reference operator[](difference_type _Off) const
		{	// subscript
		return (*(*this + _Off));
		}

	bool operator==(const _Myiter& _Right) const
		{	// test for iterator equality
		_Compat(_Right);
		return (this->_Myoff == _Right._Myoff);
		}

	bool operator!=(const _Myiter& _Right) const
		{	// test for iterator inequality
		return (!(*this == _Right));
		}

	bool operator<(const _Myiter& _Right) const
		{	// test if this < _Right
		_Compat(_Right);
		return (this->_Myoff < _Right._Myoff);
		}

	bool operator>(const _Myiter& _Right) const
		{	// test if this > _Right
		return (_Right < *this);
		}

	bool operator<=(const _Myiter& _Right) const
		{	// test if this <= _Right
		return (!(_Right < *this));
		}

	bool operator>=(const _Myiter& _Right) const
		{	// test if this >= _Right
		return (!(*this < _Right));
		}

 #if _ITERATOR_DEBUG_LEVEL == 2
	void _Compat(const _Myiter& _Right) const
		{	// test for compatible iterator pair
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());
		if (_Mycont == 0
			|| _Mycont != _Right._Getcont())
			{	// report error
			_DEBUG_ERROR("deque iterators incompatible");
			_SCL_SECURE_INVALID_ARGUMENT;
			}
		}

	void _Setcont(const _Mydeque *_Pdeque)
		{	// set container pointer
		this->_Adopt(_Pdeque);
		}

 #elif _ITERATOR_DEBUG_LEVEL == 1
	void _Compat(const _Myiter& _Right) const
		{	// test for compatible iterator pair
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());
		_SCL_SECURE_VALIDATE(_Mycont != 0);
		_SCL_SECURE_VALIDATE_RANGE(_Mycont == _Right._Getcont());
		}

	void _Setcont(const _Mydeque *_Pdeque)
		{	// set container pointer
		this->_Adopt(_Pdeque);
		}

 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
	void _Compat(const _Myiter&) const
		{	// test for compatible iterator pair
		}

	void _Setcont(const _Mydeque *_Pdeque)
		{	// set container pointer
		this->_Adopt(_Pdeque);
		}

 #endif /* _ITERATOR_DEBUG_LEVEL */

	size_type _Myoff;	// offset of element in deque
	};

template<class _Ty,
	class _Alloc> inline
	typename _Deque_const_iterator<_Ty, _Alloc>::_Unchecked_type
		_Unchecked(_Deque_const_iterator<_Ty, _Alloc> _Iter)
	{	// convert to unchecked
	return (_Iter._Unchecked());
	}

template<class _Ty,
	class _Alloc> inline
	_Deque_const_iterator<_Ty, _Alloc>&
		_Rechecked(_Deque_const_iterator<_Ty, _Alloc>& _Iter,
			typename _Deque_const_iterator<_Ty, _Alloc>
				::_Unchecked_type _Right)
	{	// convert to checked
	return (_Iter._Rechecked(_Right));
	}

template<class _Ty,
	class _Alloc> inline
	_Deque_const_iterator<_Ty, _Alloc> operator+(
		typename _Deque_const_iterator<_Ty, _Alloc>::difference_type _Off,
		_Deque_const_iterator<_Ty, _Alloc> _Next)
	{	// add offset to iterator
	return (_Next += _Off);
	}

		// TEMPLATE CLASS _Deque_iterator
template<class _Ty,
	class _Alloc>
	class _Deque_iterator
		: public _Deque_const_iterator<_Ty, _Alloc>
		{	// iterator for mutable deque
public:
	typedef _Deque_iterator<_Ty, _Alloc> _Myiter;
	typedef _Deque_const_iterator<_Ty, _Alloc> _Mybase;
	typedef _Deque_unchecked_iterator<_Ty, _Alloc> _Deque_unchecked_type;
	typedef random_access_iterator_tag iterator_category;

	typedef typename _Alloc::value_type value_type;
	typedef typename _Alloc::size_type size_type;
	typedef typename _Alloc::difference_type difference_type;
	typedef typename _Alloc::pointer pointer;
	typedef typename _Alloc::reference reference;

	_Deque_iterator()
		{	// construct with null deque pointer
		}

	_Deque_iterator(size_type _Off, const _Container_base12 *_Pdeque)
		: _Mybase(_Off, _Pdeque)
		{	// construct with offset _Off in *_Pdeque
		}

	typedef _Deque_unchecked_iterator<_Ty, _Alloc> _Unchecked_type;

	_Myiter& _Rechecked(_Unchecked_type _Right)
		{	// reset from unchecked iterator
		this->_Myoff = _Right._Myoff;
		return (*this);
		}

	_Unchecked_type _Unchecked() const
		{	// make an unchecked iterator
		return (_Unchecked_type(this->_Myoff, this->_Getcont()));
		}

	reference operator*() const
		{	// return designated object
		return ((reference)**(_Mybase *)this);
		}

	pointer operator->() const
		{	// return pointer to class object
		return (&**this);
		}

	_Myiter& operator++()
		{	// preincrement
		++*(_Mybase *)this;
		return (*this);
		}

	_Myiter operator++(int)
		{	// postincrement
		_Myiter _Tmp = *this;
		++*this;
		return (_Tmp);
		}

	_Myiter& operator--()
		{	// predecrement
		--*(_Mybase *)this;
		return (*this);
		}

	_Myiter operator--(int)
		{	// postdecrement
		_Myiter _Tmp = *this;
		--*this;
		return (_Tmp);
		}

	_Myiter& operator+=(difference_type _Off)
		{	// increment by integer
		this->_Myoff += _Off;
		return (*this);
		}

	_Myiter operator+(difference_type _Off) const
		{	// return this + integer
		_Myiter _Tmp = *this;
		return (_Tmp += _Off);
		}

	_Myiter& operator-=(difference_type _Off)
		{	// decrement by integer
		return (*this += -_Off);
		}

	_Myiter operator-(difference_type _Off) const
		{	// return this - integer
		_Myiter _Tmp = *this;
		return (_Tmp -= _Off);
		}

	difference_type operator-(const _Mybase& _Right) const
		{	// return difference of iterators
		return (*(_Mybase *)this - _Right);
		}

	reference operator[](difference_type _Off) const
		{	// subscript
		return (*(*this + _Off));
		}
	};

template<class _Ty,
	class _Alloc> inline
	typename _Deque_iterator<_Ty, _Alloc>::_Unchecked_type
		_Unchecked(_Deque_iterator<_Ty, _Alloc> _Iter)
	{	// convert to unchecked
	return (_Iter._Unchecked());
	}

template<class _Ty,
	class _Alloc> inline
	_Deque_iterator<_Ty, _Alloc>&
		_Rechecked(_Deque_iterator<_Ty, _Alloc>& _Iter,
			typename _Deque_iterator<_Ty, _Alloc>
				::_Unchecked_type _Right)
	{	// convert to checked
	return (_Iter._Rechecked(_Right));
	}

template<class _Ty,
	class _Alloc> inline
	_Deque_iterator<_Ty, _Alloc> operator+(
		typename _Deque_iterator<_Ty, _Alloc>::difference_type _Off,
		_Deque_iterator<_Ty, _Alloc> _Next)
	{	// add offset to iterator
	return (_Next += _Off);
	}

		// TEMPLATE CLASS _Deque_val
template<class _Ty,
	class _Alloc>
	class _Deque_val
		: public _Container_base12
	{	// base class for deque to hold data
public:
	typedef typename _Alloc::template rebind<_Ty>::other _Alty;
	typedef typename _Alty::pointer _Tptr;
	typedef typename _Alloc::template rebind<_Tptr>::other _Tptr_alloc;
	typedef typename _Tptr_alloc::pointer _Mapptr;

	_Deque_val(_Alloc _Al = _Alloc())
		: _Alval(_Al), _Almap(_Al)
		{	// construct allocators from _Al
		typename _Alloc::template rebind<_Container_proxy>::other
			_Alproxy(_Alval);
		this->_Myproxy = _Alproxy.allocate(1);
		_Cons_val(_Alproxy, this->_Myproxy, _Container_proxy());
		this->_Myproxy->_Mycont = this;

		_Map = 0;
		_Mapsize = 0;
		_Myoff = 0;
		_Mysize = 0;
		}

	~_Deque_val()
		{	// destroy proxy
		typename _Alloc::template rebind<_Container_proxy>::other
			_Alproxy(_Alval);
		this->_Orphan_all();
		_Dest_val(_Alproxy, this->_Myproxy);
		_Alproxy.deallocate(this->_Myproxy, 1);
		this->_Myproxy = 0;
		}

	typedef typename _Alty::value_type value_type;
	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;

	_Mapptr _Map;		// pointer to array of pointers to blocks
	size_type _Mapsize;	// size of map array
	size_type _Myoff;	// offset of initial element
	size_type _Mysize;	// current length of sequence
	_Alty _Alval;	// allocator object for stored elements

	_Tptr_alloc _Almap;	// allocator object for maps
	};

		// TEMPLATE CLASS deque
template<class _Ty,
	class _Ax = allocator<_Ty> >
	class deque
		: public _Deque_val<_Ty, _Ax>
	{	// circular queue of pointers to blocks
public:
	typedef deque<_Ty, _Ax> _Myt;
	typedef _Deque_val<_Ty, _Ax> _Mybase;
	typedef typename _Mybase::_Alty _Alloc;

	typedef _Alloc allocator_type;
	typedef typename _Alloc::value_type value_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 _Mybase::_Mapptr _Mapptr;

	typedef _Deque_iterator<_Ty, _Alloc> iterator;
	typedef _Deque_const_iterator<_Ty, _Alloc> const_iterator;

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

	static const int _EEM_DS = _DEQUESIZ;
	enum {_EEN_DS = _DEQUESIZ};	// helper for expression evaluator
	deque()
		: _Mybase()
		{	// construct empty deque
		}

	explicit deque(const _Alloc& _Al)
		: _Mybase(_Al)
		{	// construct empty deque with allocator
		}

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

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

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

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

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

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

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

	template<class _It>
		void _Construct(_It _First, _It _Last, input_iterator_tag)
		{	// initialize 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
		}

#define _PUSH_FRONT_BEGIN \
	if (this->_Myoff % _DEQUESIZ == 0 \
		&& this->_Mapsize <= (this->_Mysize + _DEQUESIZ) / _DEQUESIZ) \
		_Growmap(1); \
	size_type _Newoff = this->_Myoff != 0 ? this->_Myoff \
		: this->_Mapsize * _DEQUESIZ; \
	size_type _Block = --_Newoff / _DEQUESIZ; \
	if (this->_Map[_Block] == 0) \
		this->_Map[_Block] = this->_Alval.allocate(_DEQUESIZ)

#define _PUSH_FRONT_END \
	this->_Myoff = _Newoff; \
	++this->_Mysize

#define _PUSH_BACK_BEGIN \
	if ((this->_Myoff + this->_Mysize) % _DEQUESIZ == 0 \