deque

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

		&& this->_Mapsize <= (this->_Mysize + _DEQUESIZ) / _DEQUESIZ) \
		_Growmap(1); \
	size_type _Newoff = this->_Myoff + this->_Mysize; \
	size_type _Block = _Newoff / _DEQUESIZ; \
	if (this->_Mapsize <= _Block) \
		_Block -= this->_Mapsize; \
	if (this->_Map[_Block] == 0) \
		this->_Map[_Block] = this->_Alval.allocate(_DEQUESIZ)

#define _PUSH_BACK_END \
	++this->_Mysize

	deque(_Myt&& _Right)
		: _Mybase(_Right._Alval)
		{	// construct by moving _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)
			;
		else if (get_allocator() != _Right.get_allocator())
			{	// move construct a copy
			clear();
			for (iterator _Next = _Right.begin(); _Next != _Right.end();
				++_Next)
				push_back(_STD forward<_Ty>(*_Next));
			}
		else
			{	// clear this and steal from _Right
			_Tidy();
			this->_Swap_all((_Myt&)_Right);
			this->_Map = _Right._Map;
			this->_Mapsize = _Right._Mapsize;
			this->_Myoff = _Right._Myoff;
			this->_Mysize = _Right._Mysize;

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

	void push_front(_Ty&& _Val)
		{	// insert element at beginning
		this->_Orphan_all();
		_PUSH_FRONT_BEGIN;
		_Cons_val(this->_Alval,
			this->_Map[_Block] + _Newoff % _DEQUESIZ,
			_STD forward<_Ty>(_Val));
		_PUSH_FRONT_END;
		}

	void push_back(_Ty&& _Val)
		{	// insert element at end
		this->_Orphan_all();
		_PUSH_BACK_BEGIN;
		_Cons_val(this->_Alval,
			this->_Map[_Block] + _Newoff % _DEQUESIZ,
			_STD forward<_Ty>(_Val));
		_PUSH_BACK_END;
		}

	template<class _Valty>
		void emplace_front(_Valty&& _Val)
		{	// insert element at beginning
		this->_Orphan_all();
		_PUSH_FRONT_BEGIN;
		_Cons_val(this->_Alval,
			this->_Map[_Block] + _Newoff % _DEQUESIZ,
			_STD forward<_Valty>(_Val));
		_PUSH_FRONT_END;
		}

	template<class _Valty>
		void emplace_back(_Valty&& _Val)
		{	// insert element at end
		this->_Orphan_all();
		_PUSH_BACK_BEGIN;
		_Cons_val(this->_Alval,
			this->_Map[_Block] + _Newoff % _DEQUESIZ,
			_STD forward<_Valty>(_Val));
		_PUSH_BACK_END;
		}

	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
		size_type _Off = _Where - begin();

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

		if (_Off <= this->_Mysize / 2)
			{	// closer to front, push to front then rotate
			emplace_front(_STD forward<_Valty>(_Val));
			_STD rotate(begin(), begin() + 1, begin() + 1 + _Off);
			}
		else
			{	// closer to back, push to back then rotate
			emplace_back(_STD forward<_Valty>(_Val));
			_STD rotate(begin() + _Off, end() - 1, end());
			}
		return (begin() + _Off);
		}

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

	~deque()
		{	// destroy the deque
		_Tidy();
		}

	_Myt& operator=(const _Myt& _Right)
		{	// assign _Right
		if (this != &_Right)
			{	// worth doing
			this->_Orphan_all();

			if (_Right._Mysize == 0)
				clear();
			else if (_Right._Mysize <= this->_Mysize)
				{	// enough elements, copy new and destroy old
				iterator _Mid = _STD copy(_Right.begin(), _Right.end(),
					begin());
				erase(_Mid, end());
				}
			else
				{	// new sequence longer, copy and construct new
				const_iterator _Mid = _Right.begin() + this->_Mysize;
				_STD copy(_Right.begin(), _Mid, begin());
				insert(end(), _Mid, _Right.end());
				}
			}
		return (*this);
		}

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

	const_iterator begin() const
		{	// return iterator for beginning of nonmutable sequence
		return (const_iterator(this->_Myoff, this));
		}

	iterator end()
		{	// return iterator for end of mutable sequence
		return (iterator(this->_Myoff + this->_Mysize, this));
		}

	const_iterator end() const
		{	// return iterator for end of nonmutable sequence
		return (const_iterator(this->_Myoff + this->_Mysize, this));
		}

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

	void shrink_to_fit()
		{	// reduce capacity
		_Myt _Tmp(*this);
		swap(_Tmp);
		}
 #endif /* _HAS_CPP0X */

	void resize(size_type _Newsize)
		{	// determine new length, padding with _Ty() elements as needed
		if (_Newsize < this->_Mysize)
			erase(begin() + _Newsize, end());
		else if (this->_Mysize < _Newsize)
			{	// appemd default-constructed elements
			this->_Orphan_all();
			while (this->_Mysize < _Newsize)
				{	// push_back default-constructed element
				_PUSH_BACK_BEGIN;
				_Uninitialized_default_fill_n(
					this->_Map[_Block] + _Newoff % _DEQUESIZ,
					1, (_Ty *)0, this->_Alval);
				_PUSH_BACK_END;
				}
			}
		}

	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 if (_Newsize < this->_Mysize)
			erase(begin() + _Newsize, end());
		}

	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);
		}

	const_reference at(size_type _Pos) const
		{	// subscript nonmutable sequence with checking
		if (this->_Mysize <= _Pos)
			_Xran();
		return (*(begin() + _Pos));
		}

	reference at(size_type _Pos)
		{	// subscript mutable sequence with checking
		if (this->_Mysize <= _Pos)
			_Xran();
		return (*(begin() + _Pos));
		}

	const_reference operator[](size_type _Pos) const
		{	// subscript nonmutable sequence
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Mysize <= _Pos)
			_DEBUG_ERROR("deque subscript out of range");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		return (*(begin() + _Pos));
		}

	reference operator[](size_type _Pos)
		{	// subscript mutable sequence
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Mysize <= _Pos)
			_DEBUG_ERROR("deque subscript out of range");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		return (*(begin() + _Pos));
		}

	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() - 1));
		}

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

	void push_front(const _Ty& _Val)
		{	// insert element at beginning
		this->_Orphan_all();
		_PUSH_FRONT_BEGIN;
		_Cons_val(this->_Alval,
			this->_Map[_Block] + _Newoff % _DEQUESIZ, _Val);
		_PUSH_FRONT_END;
		}

	void pop_front()
		{	// erase element at beginning
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (empty())
			_DEBUG_ERROR("deque empty before pop");
		else
			{	// something to erase, do it
			_Orphan_off(this->_Myoff);
			size_type _Block = this->_Myoff / _DEQUESIZ;
			_Dest_val(this->_Alval,
				this->_Map[_Block] + this->_Myoff % _DEQUESIZ);
			if (this->_Mapsize * _DEQUESIZ <= ++this->_Myoff)
				this->_Myoff = 0;
			if (--this->_Mysize == 0)
				this->_Myoff = 0;
			}

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
		if (!empty())
			{	// something to erase, do it
			size_type _Block = this->_Myoff / _DEQUESIZ;
			_Dest_val(this->_Alval,
				this->_Map[_Block] + this->_Myoff % _DEQUESIZ);
			if (this->_Mapsize * _DEQUESIZ <= ++this->_Myoff)
				this->_Myoff = 0;
			if (--this->_Mysize == 0)
				this->_Myoff = 0;
			}
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
		}

	void push_back(const _Ty& _Val)
		{	// insert element at end
		this->_Orphan_all();
		_PUSH_BACK_BEGIN;
		_Cons_val(this->_Alval,
			this->_Map[_Block] + _Newoff % _DEQUESIZ, _Val);
		_PUSH_BACK_END;
		}

	void pop_back()
		{	// erase element at end
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (empty())
			_DEBUG_ERROR("deque empty before pop");
		else
			{	// something to erase, do it
			_Orphan_off(this->_Myoff + this->_Mysize - 1);
			size_type _Newoff = this->_Mysize + this->_Myoff - 1;
			size_type _Block = _Newoff / _DEQUESIZ;
			if (this->_Mapsize <= _Block)
				_Block -= this->_Mapsize;
			_Dest_val(this->_Alval,
				this->_Map[_Block] + _Newoff % _DEQUESIZ);
			if (--this->_Mysize == 0)
				this->_Myoff = 0;
			}

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
		if (!empty())
			{	// something to erase, do it
			size_type _Newoff = this->_Mysize + this->_Myoff - 1;
			size_type _Block = _Newoff / _DEQUESIZ;
			if (this->_Mapsize <= _Block)
				_Block -= this->_Mapsize;
			_Dest_val(this->_Alval,
				this->_Map[_Block] + _Newoff % _DEQUESIZ);
			if (--this->_Mysize == 0)
				this->_Myoff = 0;
			}
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
		}

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

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

	template<class _It>
		void _Assign(_It _First, _It _Last, input_iterator_tag)
		{	// assign [_First, _Last), input iterators
		erase(begin(), end());
		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
		size_type _Off = _Where - begin();

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

		if (_Off <= this->_Mysize / 2)
			{	// closer to front, push to front then copy