deque

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

// deque standard header
#pragma once
#ifndef _DEQUE_
#define _DEQUE_
#ifndef RC_INVOKED
#include <memory>
#include <stdexcept>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)

_STD_BEGIN
	// DEQUE PARAMETERS
#define _DEQUEMAPSIZ	8	/* minimum map size, at least 1 */
#define _DEQUESIZ	(sizeof (value_type) <= 1 ? 16 \
	: sizeof (value_type) <= 2 ? 8 \
	: sizeof (value_type) <= 4 ? 4 \
	: sizeof (value_type) <= 8 ? 2 \
	: 1)	/* elements per block (a power of 2) */

template<class _Ty,
	class _Alloc>
	class deque;

		// TEMPLATE CLASS _Deque_unchecked_const_iterator
template<class _Ty,
	class _Alloc>
	class _Deque_unchecked_const_iterator

	{	// iterator for nonmutable deque
public:
	typedef _Deque_unchecked_const_iterator<_Ty, _Alloc> _Myiter;
	typedef deque<_Ty, _Alloc> _Mydeque;
	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::const_pointer pointer;
	typedef typename _Alloc::const_reference reference;

	_Deque_unchecked_const_iterator()
		{	// construct with null pointer
		_Mycont = 0;
		_Myoff = 0;
		}

	_Deque_unchecked_const_iterator(size_type _Off,
		const _Container_base12 *_Pdeque)
		{	// construct with offset _Off
		_Mycont = (_Mydeque *)_Pdeque;
		_Myoff = _Off;
		}

	reference operator*() const
		{	// return designated object
		size_type _Block = _Myoff / _DEQUESIZ;
		size_type _Off = _Myoff & (_DEQUESIZ - 1);	// assume power of 2

		if (_Mycont->_Mapsize <= _Block)
			_Block -= _Mycont->_Mapsize;
		return ((_Mycont->_Map)[_Block][_Off]);
		}

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

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

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

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

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

	_Myiter& operator+=(difference_type _Off)
		{	// increment by integer
		_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 _Myiter& _Right) const
		{	// return difference of iterators
		return (_Right._Myoff <= _Myoff
			? _Myoff - _Right._Myoff
			: -(difference_type)(_Right._Myoff - _Myoff));
		}

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

	bool operator==(const _Myiter& _Right) const
		{	// test for iterator equality
		return (_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
		return (_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));
		}

	const _Container_base12 *_Getcont() const
		{	// get container pointer
		return (_Mycont);
		}

	const _Mydeque *_Mycont;	// pointer to deque
	size_type _Myoff;	// offset of element in deque
	};

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

		// TEMPLATE CLASS _Deque_unchecked_iterator
template<class _Ty,
	class _Alloc>
	class _Deque_unchecked_iterator
		: public _Deque_unchecked_const_iterator<_Ty, _Alloc>
	{	// iterator for mutable deque
public:
	typedef _Deque_unchecked_iterator<_Ty, _Alloc> _Myiter;
	typedef _Deque_unchecked_const_iterator<_Ty, _Alloc> _Mybase;
	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_unchecked_iterator()
		{	// construct with null pointer
		}

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

	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
		*(_Mybase *)this += _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
	_Deque_unchecked_iterator<_Ty, _Alloc> operator+(
		typename _Deque_unchecked_iterator<_Ty, _Alloc>
			::difference_type _Off,
		_Deque_unchecked_iterator<_Ty, _Alloc> _Next)
	{	// add offset to iterator
	return (_Next += _Off);
	}

		// TEMPLATE CLASS _Deque_const_iterator
template<class _Ty,
	class _Alloc>
	class _Deque_const_iterator
		: public _Iterator_base12
	{	// iterator for nonmutable deque
public:
	typedef _Deque_const_iterator<_Ty, _Alloc> _Myiter;
	typedef deque<_Ty, _Alloc> _Mydeque;
	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::const_pointer pointer;
	typedef typename _Alloc::const_reference reference;

	_Deque_const_iterator()
		{	// construct with null pointer
		_Setcont(0);
		_Myoff = 0;
		}

	_Deque_const_iterator(size_type _Off, const _Container_base12 *_Pdeque)
		{	// construct with offset _Off in *_Pdeque
		_Setcont((_Mydeque *)_Pdeque);
		_Myoff = _Off;
		}

	typedef _Deque_unchecked_const_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(_Myoff, this->_Getcont()));
		}

	reference operator*() const
		{	// return designated object
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());

 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Mycont == 0
			|| this->_Myoff < _Mycont->_Myoff
			|| _Mycont->_Myoff + _Mycont->_Mysize <= this->_Myoff)
		{	// report error
		_DEBUG_ERROR("deque iterator not dereferencable");
		_SCL_SECURE_OUT_OF_RANGE;
		}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(_Mycont != 0);
		_SCL_SECURE_VALIDATE_RANGE(_Mycont->_Myoff <= this->_Myoff
			&& this->_Myoff < _Mycont->_Myoff + _Mycont->_Mysize);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		__analysis_assume(_Mycont != 0);

		size_type _Block = _Myoff / _DEQUESIZ;
		size_type _Off = _Myoff & (_DEQUESIZ - 1);	// assume power of 2

		if (_Mycont->_Mapsize <= _Block)
			_Block -= _Mycont->_Mapsize;
		return ((_Mycont->_Map)[_Block][_Off]);
		}

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

	_Myiter& operator++()
		{	// preincrement
 #if _ITERATOR_DEBUG_LEVEL == 2
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());
		if (_Mycont == 0
			|| _Mycont->_Myoff + _Mycont->_Mysize <= this->_Myoff)
		{	// report error
		_DEBUG_ERROR("deque iterator not incrementable");
		_SCL_SECURE_OUT_OF_RANGE;
		}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());
		_SCL_SECURE_VALIDATE(_Mycont != 0);
		_SCL_SECURE_VALIDATE_RANGE(
			this->_Myoff < _Mycont->_Myoff + _Mycont->_Mysize);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		++_Myoff;
		return (*this);
		}

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

	_Myiter& operator--()
		{	// predecrement
 #if _ITERATOR_DEBUG_LEVEL == 2
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());
		if (_Mycont == 0
			|| this->_Myoff <= _Mycont->_Myoff)
		{	// report error
		_DEBUG_ERROR("deque iterator not decrementable");
		_SCL_SECURE_OUT_OF_RANGE;
		}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());
		_SCL_SECURE_VALIDATE(_Mycont != 0);
		_SCL_SECURE_VALIDATE_RANGE(_Mycont->_Myoff < this->_Myoff);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		--_Myoff;
		return (*this);
		}

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

	_Myiter& operator+=(difference_type _Off)
		{	// increment by integer
 #if _ITERATOR_DEBUG_LEVEL == 2
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());
		if (_Mycont == 0
			|| this->_Myoff + _Off < _Mycont->_Myoff
			|| _Mycont->_Myoff + _Mycont->_Mysize < this->_Myoff + _Off)
			{	// report error
			_DEBUG_ERROR("deque iterator + offset out of range");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_Mydeque *_Mycont = ((_Mydeque *)this->_Getcont());
		_SCL_SECURE_VALIDATE(_Mycont != 0);
		_SCL_SECURE_VALIDATE_RANGE(_Mycont->_Myoff <= this->_Myoff + _Off
			&& this->_Myoff + _Off <= _Mycont->_Myoff + _Mycont->_Mysize);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		_Myoff += _Off;
		return (*this);
		}

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