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

#if _HAS_CXX17
 #include <xpolymorphic_allocator.h>
#endif /* _HAS_CXX17 */

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,_STL_WARNING_LEVEL)
 #pragma warning(disable: _STL_DISABLED_WARNINGS)
 _STL_DISABLE_CLANG_WARNINGS
 #pragma push_macro("new")
 #undef new

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

		// CLASS TEMPLATE _Deque_unchecked_const_iterator
template<class _Mydeque>
	class _Deque_unchecked_const_iterator
	{	// iterator for nonmutable deque
private:
	using _Size_type = typename _Mydeque::size_type;
public:
	using iterator_category = random_access_iterator_tag;

	using value_type = typename _Mydeque::value_type;
	using difference_type = typename _Mydeque::difference_type;
	using pointer = typename _Mydeque::const_pointer;
	using reference = const value_type&;

	_Deque_unchecked_const_iterator()
		: _Mycont(),
		_Myoff(0)
		{	// construct with null pointer
		}

	_Deque_unchecked_const_iterator(_Size_type _Off,
		const _Container_base12 *_Pdeque)
		: _Mycont(static_cast<const _Mydeque *>(_Pdeque)),
		_Myoff(_Off)
		{	// construct with offset _Off
		}

	_NODISCARD reference operator*() const
		{	// return designated object
		_Size_type _Block = _Mycont->_Getblock(_Myoff);
		_Size_type _Off = _Myoff % _DEQUESIZ;
		return (_Mycont->_Map[_Block][_Off]);
		}

	_NODISCARD pointer operator->() const
		{	// return pointer to class object
		return (pointer_traits<pointer>::pointer_to(**this));
		}

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

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

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

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

	_Deque_unchecked_const_iterator& operator+=(const difference_type _Off)
		{	// increment by integer
		_Myoff += _Off;
		return (*this);
		}

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

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

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

	_NODISCARD difference_type operator-(const _Deque_unchecked_const_iterator& _Right) const
		{	// return difference of iterators
		return (static_cast<difference_type>(_Myoff - _Right._Myoff));
		}

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

	_NODISCARD bool operator==(const _Deque_unchecked_const_iterator& _Right) const
		{	// test for iterator equality
		return (_Myoff == _Right._Myoff);
		}

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

	_NODISCARD bool operator<(const _Deque_unchecked_const_iterator& _Right) const
		{	// test if this < _Right
		return (_Myoff < _Right._Myoff);
		}

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

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

	_NODISCARD bool operator>=(const _Deque_unchecked_const_iterator& _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 _Mydeque>
	_NODISCARD inline _Deque_unchecked_const_iterator<_Mydeque> operator+(
		typename _Deque_unchecked_const_iterator<_Mydeque>
			::difference_type _Off,
		_Deque_unchecked_const_iterator<_Mydeque> _Next)
	{	// add offset to iterator
	return (_Next += _Off);
	}

		// CLASS TEMPLATE _Deque_unchecked_iterator
template<class _Mydeque>
	class _Deque_unchecked_iterator
		: public _Deque_unchecked_const_iterator<_Mydeque>
	{	// iterator for mutable deque
private:
	using _Size_type = typename _Mydeque::size_type;
	using _Mybase = _Deque_unchecked_const_iterator<_Mydeque>;

public:
	using iterator_category = random_access_iterator_tag;

	using value_type = typename _Mydeque::value_type;
	using difference_type = typename _Mydeque::difference_type;
	using pointer = typename _Mydeque::pointer;
	using reference = value_type&;

	_Deque_unchecked_iterator()
		{	// construct with null pointer
		}

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

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

	_NODISCARD pointer operator->() const
		{	// return pointer to class object
		return (pointer_traits<pointer>::pointer_to(**this));
		}

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

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

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

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

	_Deque_unchecked_iterator& operator+=(const difference_type _Off)
		{	// increment by integer
		*(_Mybase *)this += _Off;
		return (*this);
		}

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

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

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

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

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

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

		// CLASS TEMPLATE _Deque_const_iterator
template<class _Mydeque>
	class _Deque_const_iterator
		: public _Iterator_base12
	{	// iterator for nonmutable deque
private:
	using _Size_type = typename _Mydeque::size_type;

public:
	using iterator_category = random_access_iterator_tag;

	using value_type = typename _Mydeque::value_type;
	using difference_type = typename _Mydeque::difference_type;
	using pointer = typename _Mydeque::const_pointer;
	using reference = const value_type&;

	using _Mydeque_t = _Mydeque;	// helper for expression evaluator
	enum {_EEN_DS = _DEQUESIZ};	// helper for expression evaluator
	_Deque_const_iterator()
		: _Myoff(0)
		{	// construct with null pointer
		_Setcont(nullptr);
		}

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

	_NODISCARD reference operator*() const
		{	// return designated object
		const auto _Mycont = static_cast<const _Mydeque *>(this->_Getcont());
 #if _ITERATOR_DEBUG_LEVEL != 0
		_STL_VERIFY(_Mycont, "cannot dereference value-initialized deque iterator");
		_STL_VERIFY(_Mycont->_Myoff <= this->_Myoff
			&& this->_Myoff < _Mycont->_Myoff + _Mycont->_Mysize,
			"cannot deference out of range deque iterator");
 #endif /* _ITERATOR_DEBUG_LEVEL != 0 */

		_Size_type _Block = _Mycont->_Getblock(_Myoff);
		_Size_type _Off = _Myoff % _DEQUESIZ;
		return (_Mycont->_Map[_Block][_Off]);
		}

	_NODISCARD pointer operator->() const
		{	// return pointer to class object
		return (pointer_traits<pointer>::pointer_to(**this));
		}

	_Deque_const_iterator& operator++()
		{	// preincrement
 #if _ITERATOR_DEBUG_LEVEL != 0
		const auto _Mycont = static_cast<const _Mydeque *>(this->_Getcont());
		_STL_VERIFY(_Mycont, "cannot increment value-initialized deque iterator");
		_STL_VERIFY(this->_Myoff < _Mycont->_Myoff + _Mycont->_Mysize,
			"cannot increment deque iterator past end");
 #endif /* _ITERATOR_DEBUG_LEVEL != 0 */

		++_Myoff;
		return (*this);
		}

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

	_Deque_const_iterator& operator--()
		{	// predecrement
 #if _ITERATOR_DEBUG_LEVEL != 0
		const auto _Mycont = static_cast<const _Mydeque *>(this->_Getcont());
		_STL_VERIFY(_Mycont, "cannot decrement value-initialized deque iterator");
		_STL_VERIFY(_Mycont->_Myoff < this->_Myoff, "cannot decrement deque iterator before begin");
 #endif /* _ITERATOR_DEBUG_LEVEL != 0 */

		--_Myoff;
		return (*this);
		}

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

	_Deque_const_iterator& operator+=(const difference_type _Off)
		{	// increment by integer
 #if _ITERATOR_DEBUG_LEVEL != 0
		if (_Off != 0)
			{
			const auto _Mycont = static_cast<const _Mydeque *>(this->_Getcont());
			_STL_VERIFY(_Mycont, "cannot seek value-initialized deque iterator");
			_STL_VERIFY(_Mycont->_Myoff <= this->_Myoff + _Off
				&& this->_Myoff + _Off <= _Mycont->_Myoff + _Mycont->_Mysize,
				"cannot seek deque iterator out of range");
			}
 #endif /* _ITERATOR_DEBUG_LEVEL != 0 */

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

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

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

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

	_NODISCARD difference_type operator-(const _Deque_const_iterator& _Right) const
		{	// return difference of iterators
		_Compat(_Right);
		return (static_cast<difference_type>(this->_Myoff - _Right._Myoff));
		}

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

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

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

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

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

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

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

	void _Compat(const _Deque_const_iterator& _Right) const
		{	// test for compatible iterator pair
 #if _ITERATOR_DEBUG_LEVEL == 0
		(void)_Right;
 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
		_STL_VERIFY(this->_Getcont() == _Right._Getcont(), "deque iterators incompatible");
 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */
		}

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

	_NODISCARD _Deque_unchecked_const_iterator<_Mydeque> _Unwrapped() const
		{
		return {this->_Myoff, this->_Getcont()};
		}

	void _Verify_offset(const difference_type _Off) const noexcept
		{
 #if _ITERATOR_DEBUG_LEVEL == 0
		(void)_Off;
 #else /* ^^^ _ITERATOR_DEBUG_LEVEL == 0 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 0 vvv */
		if (_Off != 0)
			{
			const auto _Mycont = static_cast<const _Mydeque *>(this->_Getcont());
			_STL_VERIFY(_Mycont, "cannot use value-initialized deque iterator");
			_STL_VERIFY(_Mycont->_Myoff <= this->_Myoff + _Off
				&& this->_Myoff + _Off <= _Mycont->_Myoff + _Mycont->_Mysize,
				"cannot seek deque iterator out of range");
			}
 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */
		}

 #if _ITERATOR_DEBUG_LEVEL != 0
	friend void _Verify_range(const _Deque_const_iterator& _First, const _Deque_const_iterator& _Last)
		{
		// note _Compat check inside operator<=
		_STL_VERIFY(_First <= _Last, "deque iterators transposed");
		}
 #endif /* _ITERATOR_DEBUG_LEVEL != 0 */

	void _Seek_to(const _Deque_unchecked_const_iterator<_Mydeque>& _UIt)
		{
		_Myoff = _UIt._Myoff;
		}

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

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

		// CLASS TEMPLATE _Deque_iterator
template<class _Mydeque>
	class _Deque_iterator
		: public _Deque_const_iterator<_Mydeque>
		{	// iterator for mutable deque
private:
	using _Size_type = typename _Mydeque::size_type;
	using _Mybase = _Deque_const_iterator<_Mydeque>;

public:
	using _Deque_unchecked_type = _Deque_unchecked_iterator<_Mydeque>;
	using iterator_category = random_access_iterator_tag;

	using value_type = typename _Mydeque::value_type;
	using difference_type = typename _Mydeque::difference_type;
	using pointer = typename _Mydeque::pointer;
	using reference = value_type&;

	_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
		}

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

	_NODISCARD pointer operator->() const
		{	// return pointer to class object
		return (pointer_traits<pointer>::pointer_to(**this));
		}

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

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

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

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

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

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

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

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

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

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

	_NODISCARD _Deque_unchecked_iterator<_Mydeque> _Unwrapped() const
		{
		return {this->_Myoff, this->_Getcont()};
		}
	};

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

		// deque TYPE WRAPPERS
template<class _Value_type,
	class _Size_type,
	class _Difference_type,
	class _Pointer,
	class _Const_pointer,
	class _Reference,
	class _Const_reference,
	class _Mapptr_type>
	struct _Deque_iter_types
	{	// wraps types needed by iterators
	using value_type = _Value_type;
	using size_type = _Size_type;
	using difference_type = _Difference_type;
	using pointer = _Pointer;
	using const_pointer = _Const_pointer;
	using _Mapptr = _Mapptr_type;
	};

template<class _Ty>
	struct _Deque_simple_types
		: public _Simple_types<_Ty>
	{	// wraps types needed by iterators
	using _Mapptr = _Ty **;
	};

template<class _Ty,
	class _Alloc>
	struct _Deque_base_types
	{	// types needed for a container base
	using _Alty = _Rebind_alloc_t<_Alloc, _Ty>;
	using _Alty_traits = allocator_traits<_Alty>;
	using _Alpty = _Rebind_alloc_t<_Alloc, typename _Alty_traits::pointer>;
	using _Alpty_traits = allocator_traits<_Alpty>;
	using _Mapptr = typename _Alpty_traits::pointer;

	using _Val_types = conditional_t<_Is_simple_alloc_v<_Alty>,
		_Deque_simple_types<_Ty>,
		_Deque_iter_types<_Ty,
			typename _Alty_traits::size_type,
			typename _Alty_traits::difference_type,
			typename _Alty_traits::pointer,
			typename _Alty_traits::const_pointer,
			_Ty&,
			const _Ty&,
			_Mapptr>>;
	};

		// CLASS TEMPLATE _Deque_val
template<class _Val_types>
	class _Deque_val
		: public _Container_base12
	{	// base class for deque to hold data
public:
	using value_type = typename _Val_types::value_type;
	using size_type = typename _Val_types::size_type;
	using difference_type = typename _Val_types::difference_type;
	using pointer = typename _Val_types::pointer;
	using const_pointer = typename _Val_types::const_pointer;
	using reference = value_type&;
	using const_reference = const value_type&;
	using _Mapptr = typename _Val_types::_Mapptr;

	_Deque_val()
		: _Map(),
		_Mapsize(0),
		_Myoff(0),
		_Mysize(0)
		{	// initialize values
		}

	size_type _Getblock(size_type _Off) const
		{	// determine block from offset
			// NB: _Mapsize and _DEQUESIZ are guaranteed to be powers of 2
		return ((_Off / _DEQUESIZ) & (_Mapsize - 1));
		}

	_Mapptr _Map;		// pointer to array of pointers to blocks
	size_type _Mapsize;	// size of map array, zero or 2^N
	size_type _Myoff;	// offset of initial element
	size_type _Mysize;	// current length of sequence
	};

		// CLASS TEMPLATE _Deque_alloc
template<class _Alloc_types>
	class _Deque_alloc
	{	// base class for deque to hold allocator
public:
	using _Alty = typename _Alloc_types::_Alty;
	using _Alty_traits = typename _Alloc_types::_Alty_traits;
	using _Alpty = typename _Alloc_types::_Alpty;
	using _Alpty_traits = typename _Alloc_types::_Alpty_traits;
	using _Alproxy = _Rebind_alloc_t<_Alty, _Container_proxy>;
	using _Alproxy_traits = allocator_traits<_Alproxy>;
	using _Val_types = typename _Alloc_types::_Val_types;

	using size_type = typename _Val_types::size_type;
	using difference_type = typename _Val_types::difference_type;
	using pointer = typename _Val_types::pointer;
	using const_pointer = typename _Val_types::const_pointer;
	using _Mapptr = typename _Val_types::_Mapptr;

	using iterator = _Deque_iterator<_Deque_val<_Val_types>>;
	using const_iterator = _Deque_const_iterator<_Deque_val<_Val_types>>;
	using _Unchecked_iterator = _Deque_unchecked_iterator<_Deque_val<_Val_types>>;
	using _Unchecked_const_iterator = _Deque_unchecked_const_iterator<_Deque_val<_Val_types>>;

	size_type _Getblock(size_type _Off) const
		{	// determine block from offset
		return (_Get_data()._Getblock(_Off));
		}

	_Deque_alloc()
		: _Mypair(_Zero_then_variadic_args_t())
		{	// default construct allocator
		_Alloc_proxy();
		}

	template<class _Any_alloc,
		class = enable_if_t<!is_same_v<remove_cv_t<remove_reference_t<_Any_alloc>>, _Deque_alloc>>>
		_Deque_alloc(_Any_alloc&& _Al)
		: _Mypair(_One_then_variadic_args_t(),
			_STD forward<_Any_alloc>(_Al))
		{	// construct allocator from _Al
		_Alloc_proxy();
		}

	~_Deque_alloc() noexcept
		{	// destroy proxy
		_Free_proxy();
		}

	void _Copy_alloc(const _Alty& _Al)
		{	// replace old allocator
		const bool _Reload = _Alty_traits::propagate_on_container_copy_assignment::value
			&& _Getal() != _Al;

		if (_Reload)
			{
			_Free_proxy();
			}

		_Pocca(_Getal(), _Al);

		if (_Reload)
			{
			_Alloc_proxy();
			}
		}

	void _Move_alloc(_Alty& _Al)
		{	// replace old allocator
		const bool _Reload = _Alty_traits::propagate_on_container_move_assignment::value
			&& _Getal() != _Al;

		if (_Reload)
			{
			_Free_proxy();
			}

		_Pocma(_Getal(), _Al);

		if (_Reload)
			{
			_Alloc_proxy();
			}
		}

	void _Alloc_proxy()
		{	// construct proxy
		_Alproxy _Proxy_allocator(_Getal());
		_Myproxy() = _Unfancy(_Proxy_allocator.allocate(1));
		_Alproxy_traits::construct(_Proxy_allocator, _Myproxy(), _Container_proxy());
		_Myproxy()->_Mycont = _STD addressof(_Get_data());
		}

	void _Free_proxy()
		{	// destroy proxy
		_Alproxy _Proxy_allocator(_Getal());
		_Orphan_all();
		_Alproxy_traits::destroy(_Proxy_allocator, _Myproxy());
		_Deallocate_plain(_Proxy_allocator, _Myproxy());
		_Myproxy() = nullptr;
		}

	_Iterator_base12 **_Getpfirst() const
		{	// get address of iterator chain
		return (_Get_data()._Getpfirst());
		}

	_Container_proxy * & _Myproxy() noexcept
		{	// return reference to _Myproxy
		return (_Get_data()._Myproxy);
		}

	_Container_proxy * const & _Myproxy() const noexcept
		{	// return const reference to _Myproxy
		return (_Get_data()._Myproxy);
		}

	void _Orphan_all()
		{	// orphan all iterators
		_Get_data()._Orphan_all();
		}

	void _Swap_all(_Deque_alloc& _Right)
		{	// swap all iterators
		_Get_data()._Swap_all(_Right._Get_data());
		}

	_Alty& _Getal() noexcept
		{	// return reference to allocator
		return (_Mypair._Get_first());
		}

	const _Alty& _Getal() const noexcept
		{	// return const reference to allocator
		return (_Mypair._Get_first());
		}

	_Deque_val<_Val_types>& _Get_data() noexcept
		{	// return reference to _Deque_val
		return (_Mypair._Get_second());
		}

	const _Deque_val<_Val_types>& _Get_data() const noexcept
		{	// return const reference to _Deque_val
		return (_Mypair._Get_second());
		}

	_Mapptr& _Map() noexcept
		{	// return reference to _Map
		return (_Get_data()._Map);
		}

	const _Mapptr& _Map() const noexcept
		{	// return const reference to _Map
		return (_Get_data()._Map);
		}

	size_type& _Mapsize() noexcept
		{	// return reference to _Mapsize
		return (_Get_data()._Mapsize);
		}

	const size_type& _Mapsize() const noexcept
		{	// return const reference to _Mapsize
		return (_Get_data()._Mapsize);
		}

	size_type& _Myoff() noexcept
		{	// return reference to _Myoff
		return (_Get_data()._Myoff);
		}

	const size_type& _Myoff() const noexcept
		{	// return const reference to _Myoff
		return (_Get_data()._Myoff);
		}

	size_type& _Mysize() noexcept
		{	// return reference to _Mysize
		return (_Get_data()._Mysize);
		}

	const size_type& _Mysize() const noexcept
		{	// return const reference to _Mysize
		return (_Get_data()._Mysize);
		}

private:
	_Compressed_pair<_Alty, _Deque_val<_Val_types>> _Mypair;
	};

		// CLASS TEMPLATE deque
template<class _Ty,
	class _Alloc = allocator<_Ty>>
	class deque
		: public _Deque_alloc<_Deque_base_types<_Ty, _Alloc>>
	{	// circular queue of pointers to blocks
private:
	using _Mybase = _Deque_alloc<_Deque_base_types<_Ty, _Alloc>>;

public:
	static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<_Ty, typename _Alloc::value_type>,
		_MISMATCHED_ALLOCATOR_MESSAGE("deque<T, Allocator>", "T"));

	using allocator_type = _Alloc;

	using _Alty = typename _Mybase::_Alty;
	using _Alty_traits = typename _Mybase::_Alty_traits;
	using _Alpty = typename _Mybase::_Alpty;
	using _Alpty_traits = typename _Mybase::_Alpty_traits;
	using _Mapptr = typename _Mybase::_Mapptr;

	using value_type = _Ty;
	using size_type = typename _Mybase::size_type;
	using difference_type = typename _Mybase::difference_type;
	using pointer = typename _Mybase::pointer;
	using const_pointer = typename _Mybase::const_pointer;
	using reference = _Ty&;
	using const_reference = const _Ty&;

	using iterator = typename _Mybase::iterator;
	using const_iterator = typename _Mybase::const_iterator;
	using _Unchecked_iterator = typename _Mybase::_Unchecked_iterator;
	using _Unchecked_const_iterator = typename _Mybase::_Unchecked_const_iterator;

	using reverse_iterator = _STD reverse_iterator<iterator>;
	using const_reverse_iterator = _STD reverse_iterator<const_iterator>;
	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(_CRT_GUARDOVERFLOW size_type _Count, const _Alloc& _Al = _Alloc())
		: _Mybase(_Al)
		{	// construct from _Count * _Ty(), optional allocator
		resize(_Count);
		}

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

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

	deque(const deque& _Right)
		: _Mybase(_Alty_traits::select_on_container_copy_construction(_Right._Getal()))
		{	// construct by copying _Right
		_Construct(_Right.begin(), _Right.end());
		}

	deque(const deque& _Right, const _Alloc& _Al)
		: _Mybase(_Al)
		{	// construct by copying _Right
		_Construct(_Right.begin(), _Right.end());
		}

	template<class _Iter,
		class = enable_if_t<_Is_iterator_v<_Iter>>>
		deque(_Iter _First, _Iter _Last)
		: _Mybase()
		{	// construct from [_First, _Last)
		_Construct(_First, _Last);
		}

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

	template<class _Iter>
		void _Construct(_Iter _First, _Iter _Last)
		{	// initialize from [_First, _Last), input iterators
		_TRY_BEGIN
		for (; _First != _Last; ++_First)
			{
			emplace_back(*_First);
			}

		_CATCH_ALL
		_Tidy();
		_RERAISE;
		_CATCH_END
		}

	void _Construct_n(size_type _Count, const _Ty& _Val)
		{	// construct from _Count * _Val
		_TRY_BEGIN
		for (; 0 < _Count; --_Count)
			{
			push_back(_Val);
			}

		_CATCH_ALL
		_Tidy();
		_RERAISE;
		_CATCH_END
		}

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

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

#define _PUSH_BACK_BEGIN \
	if ((this->_Myoff() + this->_Mysize()) % _DEQUESIZ == 0 \
		&& this->_Mapsize() <= (this->_Mysize() + _DEQUESIZ) / _DEQUESIZ) \
		_Growmap(1); \
	this->_Myoff() &= this->_Mapsize() * _DEQUESIZ - 1; \
	size_type _Newoff = this->_Myoff() + this->_Mysize(); \
	size_type _Block = this->_Getblock(_Newoff); \
	if (this->_Map()[_Block] == pointer()) \
		this->_Map()[_Block] = this->_Getal().allocate(_DEQUESIZ)

#define _PUSH_BACK_END \
	++this->_Mysize()

	deque(deque&& _Right)
		: _Mybase(_STD move(_Right._Getal()))
		{	// construct by moving _Right
		_Assign_rv(_STD move(_Right), true_type());
		}

	deque(deque&& _Right, const _Alloc& _Al)
		: _Mybase(_Al)
		{	// construct by moving _Right
		_Assign_rv(_STD move(_Right), typename _Alty_traits::is_always_equal());
		}

	deque& operator=(deque&& _Right)
		_NOEXCEPT_COND(_Alty_traits::is_always_equal::value)
		{	// assign by moving _Right
		if (this != _STD addressof(_Right))
			{	// different, assign it
			_Tidy();
			this->_Move_alloc(_Right._Getal());
			_Assign_rv(_STD move(_Right), bool_constant<_Always_equal_after_move<_Alty>>{});
			}
		return (*this);
		}

	void _Assign_rv(deque&& _Right, true_type) noexcept
		{	// move from _Right, stealing its contents
		this->_Swap_all(_Right);
		this->_Map() = _Right._Map();
		this->_Mapsize() = _Right._Mapsize();
		this->_Myoff() = _Right._Myoff();
		this->_Mysize() = _Right._Mysize();

		_Right._Map() = _Mapptr();
		_Right._Mapsize() = 0;
		_Right._Myoff() = 0;
		_Right._Mysize() = 0;
		}

	void _Assign_rv(deque&& _Right, false_type)
		{	// move from _Right, possibly moving its contents
		if (this->_Getal() == _Right._Getal())
			{
			_Assign_rv(_STD move(_Right), true_type());
			}
		else
			{
			_Construct(_STD make_move_iterator(_Right.begin()),
				_STD make_move_iterator(_Right.end()));
			}
		}

	void push_front(_Ty&& _Val)
		{	// insert element at beginning
		this->_Orphan_all();
		_PUSH_FRONT_BEGIN;
		_Alty_traits::construct(this->_Getal(),
			_Unfancy(this->_Map()[_Block] + _Newoff % _DEQUESIZ),
			_STD move(_Val));
		_PUSH_FRONT_END;
		}

	void push_back(_Ty&& _Val)
		{	// insert element at end
		this->_Orphan_all();
		_PUSH_BACK_BEGIN;
		_Alty_traits::construct(this->_Getal(),
			_Unfancy(this->_Map()[_Block] + _Newoff % _DEQUESIZ),
			_STD move(_Val));
		_PUSH_BACK_END;
		}

	iterator insert(const_iterator _Where, _Ty&& _Val)
		{	// insert _Val at _Where
		return (emplace(_Where, _STD move(_Val)));
		}

	template<class... _Valty>
		decltype(auto) emplace_front(_Valty&&... _Val)
		{	// insert element at beginning
		this->_Orphan_all();
		_PUSH_FRONT_BEGIN;
		_Alty_traits::construct(this->_Getal(),
			_Unfancy(this->_Map()[_Block] + _Newoff % _DEQUESIZ),
			_STD forward<_Valty>(_Val)...);
		_PUSH_FRONT_END;

#if _HAS_CXX17
		return (front());
#endif /* _HAS_CXX17 */
		}

	template<class... _Valty>
		decltype(auto) emplace_back(_Valty&&... _Val)
		{	// insert element at end
		this->_Orphan_all();
		_PUSH_BACK_BEGIN;
		_Alty_traits::construct(this->_Getal(),
			_Unfancy(this->_Map()[_Block] + _Newoff % _DEQUESIZ),
			_STD forward<_Valty>(_Val)...);
		_PUSH_BACK_END;

#if _HAS_CXX17
		return (back());
#endif /* _HAS_CXX17 */
		}

	template<class... _Valty>
		iterator emplace(const_iterator _Where, _Valty&&... _Val)
		{	// insert element at _Where
		const auto _Off = static_cast<size_type>(_Where - begin());

 #if _ITERATOR_DEBUG_LEVEL == 2
		_STL_VERIFY(_Off <= this->_Mysize(), "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() + static_cast<difference_type>(1 + _Off));
			}
		else
			{	// closer to back, push to back then rotate
			emplace_back(_STD forward<_Valty>(_Val)...);
			_STD rotate(begin() + static_cast<difference_type>(_Off), end() - 1, end());
			}
		return (begin() + static_cast<difference_type>(_Off));
		}

	deque(initializer_list<_Ty> _Ilist, const _Alloc& _Al = allocator_type())
		: _Mybase(_Al)
		{	// construct from initializer_list
		_Construct(_Ilist.begin(), _Ilist.end());
		}

	deque& operator=(initializer_list<_Ty> _Ilist)
		{	// assign initializer_list
		assign(_Ilist.begin(), _Ilist.end());
		return (*this);
		}

	void assign(initializer_list<_Ty> _Ilist)
		{	// assign initializer_list
		assign(_Ilist.begin(), _Ilist.end());
		}

	iterator insert(const_iterator _Where, initializer_list<_Ty> _Ilist)
		{	// insert initializer_list
		return (insert(_Where, _Ilist.begin(), _Ilist.end()));
		}

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

	deque& operator=(const deque& _Right)
		{	// assign _Right
		if (this != _STD addressof(_Right))
			{	// different, assign it
#pragma warning(push)
#pragma warning(disable: 4127)	// conditional expression is constant
			if (_Alty_traits::propagate_on_container_copy_assignment::value
				&& this->_Getal() != _Right._Getal())
				{	// change allocator before copying
				_Tidy();
				}
#pragma warning(pop)

			this->_Copy_alloc(_Right._Getal());

			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() + static_cast<difference_type>(this->_Mysize());
				_STD copy(_Right.begin(), _Mid, begin());
				insert(end(), _Mid, _Right.end());
				}
			}
		return (*this);
		}

	_NODISCARD iterator begin() noexcept
		{	// return iterator for beginning of mutable sequence
		return (iterator(this->_Myoff(), _STD addressof(this->_Get_data())));
		}

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

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

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

	_Unchecked_iterator _Unchecked_begin() noexcept
		{	// return unchecked iterator for beginning of mutable sequence
		return (_Unchecked_iterator(this->_Myoff(), _STD addressof(this->_Get_data())));
		}

	_Unchecked_const_iterator _Unchecked_begin() const noexcept
		{	// return unchecked iterator for beginning of nonmutable sequence
		return (_Unchecked_const_iterator(this->_Myoff(), _STD addressof(this->_Get_data())));
		}

	_Unchecked_iterator _Unchecked_end() noexcept
		{	// return unchecked iterator for end of mutable sequence
		return (_Unchecked_iterator(this->_Myoff() + this->_Mysize(),
			_STD addressof(this->_Get_data())));
		}

	_Unchecked_const_iterator _Unchecked_end() const noexcept
		{	// return unchecked iterator for end of nonmutable sequence
		return (_Unchecked_const_iterator(this->_Myoff() + this->_Mysize(),
			_STD addressof(this->_Get_data())));
		}

	iterator _Make_iter(const_iterator _Where) const
		{	// make iterator from const_iterator
		return (iterator(_Where._Myoff, _STD addressof(this->_Get_data())));
		}

	_NODISCARD reverse_iterator rbegin() noexcept
		{	// return iterator for beginning of reversed mutable sequence
		return (reverse_iterator(end()));
		}

	_NODISCARD const_reverse_iterator rbegin() const noexcept
		{	// return iterator for beginning of reversed nonmutable sequence
		return (const_reverse_iterator(end()));
		}

	_NODISCARD reverse_iterator rend() noexcept
		{	// return iterator for end of reversed mutable sequence
		return (reverse_iterator(begin()));
		}

	_NODISCARD const_reverse_iterator rend() const noexcept
		{	// return iterator for end of reversed nonmutable sequence
		return (const_reverse_iterator(begin()));
		}

	_NODISCARD const_iterator cbegin() const noexcept
		{	// return iterator for beginning of nonmutable sequence
		return (begin());
		}

	_NODISCARD const_iterator cend() const noexcept
		{	// return iterator for end of nonmutable sequence
		return (end());
		}

	_NODISCARD const_reverse_iterator crbegin() const noexcept
		{	// return iterator for beginning of reversed nonmutable sequence
		return (rbegin());
		}

	_NODISCARD const_reverse_iterator crend() const noexcept
		{	// return iterator for end of reversed nonmutable sequence
		return (rend());
		}

	void shrink_to_fit()
		{	// reduce capacity
		size_type _Oldcapacity = _DEQUESIZ * this->_Mapsize();
		size_type _Newcapacity = _Oldcapacity / 2;

		if (_Newcapacity < _DEQUESIZ * _DEQUEMAPSIZ)
			_Newcapacity = _DEQUESIZ * _DEQUEMAPSIZ;

		if ((empty() && 0 < this->_Mapsize())
			|| (!empty()
				&& size() <= _Newcapacity
				&& _Newcapacity < _Oldcapacity))
			{	// worth shrinking, do it
			deque _Tmp(_STD make_move_iterator(begin()), _STD make_move_iterator(end()));
			swap(_Tmp);
			}
		}

	void resize(_CRT_GUARDOVERFLOW size_type _Newsize)
		{	// determine new length, padding as needed
		while (this->_Mysize() < _Newsize)
			{
			emplace_back();
			}

		while (_Newsize < this->_Mysize())
			{
			pop_back();
			}
		}

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

		while (_Newsize < this->_Mysize())
			{
			pop_back();
			}
		}

	_NODISCARD size_type size() const noexcept
		{	// return length of sequence
		return (this->_Mysize());
		}

	_NODISCARD size_type max_size() const noexcept
		{	// return maximum possible length of sequence
		return (_Alty_traits::max_size(this->_Getal()));
		}

	_NODISCARD bool empty() const noexcept
		{	// test if sequence is empty
		return (this->_Mysize() == 0);
		}

	_NODISCARD allocator_type get_allocator() const noexcept
		{	// return allocator object for values
		return (static_cast<allocator_type>(this->_Getal()));
		}

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

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

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

		return (*(begin() + static_cast<difference_type>(_Pos)));
		}

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

		return (*(begin() + static_cast<difference_type>(_Pos)));
		}

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

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

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

	_NODISCARD 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;
		_Alty_traits::construct(this->_Getal(),
			_Unfancy(this->_Map()[_Block] + _Newoff % _DEQUESIZ), _Val);
		_PUSH_FRONT_END;
		}

	void pop_front()
		{	// erase element at beginning
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (empty())
			{
			_STL_REPORT_ERROR("deque empty before pop");
			}
		else
			{	// something to erase, do it
			_Orphan_off(this->_Myoff());
			size_type _Block = this->_Getblock(this->_Myoff());
			_Alty_traits::destroy(this->_Getal(),
				_Unfancy(this->_Map()[_Block] + this->_Myoff() % _DEQUESIZ));
			if (--this->_Mysize() == 0)
				{
				this->_Myoff() = 0;
				}
			else
				{
				++this->_Myoff();
				}
			}

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
		size_type _Block = this->_Getblock(this->_Myoff());
		_Alty_traits::destroy(this->_Getal(),
			_Unfancy(this->_Map()[_Block] + this->_Myoff() % _DEQUESIZ));
		if (--this->_Mysize() == 0)
			{
			this->_Myoff() = 0;
			}
		else
			{
			++this->_Myoff();
			}
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
		}

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

	void pop_back()
		{	// erase element at end
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (empty())
			{
			_STL_REPORT_ERROR("deque empty before pop");
			}
		else
			{	// something to erase, do it
			size_type _Newoff = this->_Myoff() + this->_Mysize() - 1;
			_Orphan_off(_Newoff);
			size_type _Block = this->_Getblock(_Newoff);
			_Alty_traits::destroy(this->_Getal(),
				_Unfancy(this->_Map()[_Block] + _Newoff % _DEQUESIZ));
			if (--this->_Mysize() == 0)
				{
				this->_Myoff() = 0;
				}
			}

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
		size_type _Newoff = this->_Myoff() + this->_Mysize() - 1;
		size_type _Block = this->_Getblock(_Newoff);
		_Alty_traits::destroy(this->_Getal(),
			_Unfancy(this->_Map()[_Block] + _Newoff % _DEQUESIZ));
		if (--this->_Mysize() == 0)
			{
			this->_Myoff() = 0;
			}
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
		}

	template<class _Iter,
		class = enable_if_t<_Is_iterator_v<_Iter>>>
		void assign(_Iter _First, _Iter _Last)
		{	// assign [_First, _Last), input iterators
		clear();
		for (; _First != _Last; ++_First)
			{
			emplace_back(*_First);
			}
		}

	void assign(_CRT_GUARDOVERFLOW size_type _Count, const _Ty& _Val)
		{	// assign _Count * _Val
		erase(begin(), end());
		_Insert_n(begin(), _Count, _Val);
		}

	iterator insert(const_iterator _Where,
		const _Ty& _Val)
		{	// insert _Val at _Where
		size_type _Off = static_cast<size_type>(_Where - begin());

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

		if (_Off <= this->_Mysize() / 2)
			{	// closer to front, push to front then copy
			push_front(_Val);
			_STD rotate(begin(), begin() + 1, begin() + static_cast<difference_type>(1 + _Off));
			}
		else
			{	// closer to back, push to back then copy
			push_back(_Val);
			_STD rotate(begin() + static_cast<difference_type>(_Off), end() - 1, end());
			}

		return (begin() + static_cast<difference_type>(_Off));
		}

	iterator insert(const_iterator _Where, _CRT_GUARDOVERFLOW size_type _Count,
		const _Ty& _Val)
		{	// insert _Count * _Val at _Where
		size_type _Off = static_cast<size_type>(_Where - begin());
		_Insert_n(_Where, _Count, _Val);
		return (begin() + static_cast<difference_type>(_Off));
		}

	template<class _Iter,
		class = enable_if_t<_Is_iterator_v<_Iter>>>
		iterator insert(const_iterator _Where, _Iter _First, _Iter _Last)
		{	// insert [_First, _Last) at _Where, input iterators
		size_type _Off = static_cast<size_type>(_Where - begin());

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

		_Adl_verify_range(_First, _Last);
		auto _UFirst = _Get_unwrapped(_First);
		const auto _ULast = _Get_unwrapped(_Last);

		size_type _Oldsize = this->_Mysize();

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

				_CATCH_ALL
				while (_Oldsize < this->_Mysize())
					{
					pop_front();	// restore old size, at least
					}

				_RERAISE;
				_CATCH_END

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

				_CATCH_ALL
				while (_Oldsize < this->_Mysize())
					{
					pop_back();	// restore old size, at least
					}

				_RERAISE;
				_CATCH_END

				_STD rotate(begin() + static_cast<difference_type>(_Off),
					begin() + static_cast<difference_type>(_Oldsize), end());
				}
			}

		return (begin() + static_cast<difference_type>(_Off));
		}

	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
		_STL_VERIFY(_First <= _Last && begin() <= _First && _Last <= end(), "deque erase iterator outside range");
		_Adl_verify_range(_First, _Last);

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

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

		if (_Off < static_cast<size_type>(end() - _Last))
			{	// closer to front
			_STD move_backward(begin(), _First, _Last);	// copy over hole
			for (; 0 < _Count; --_Count)
				{
				pop_front();	// pop copied elements
				}
			}
		else
			{	// closer to back
			_STD 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() + static_cast<difference_type>(_Off));
		}

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

	void swap(deque& _Right) noexcept // strengthened
		{	// exchange contents with _Right
		if (this != _STD addressof(_Right))
			{	// (maybe) swap allocators, swap control information
			_Pocs(this->_Getal(), _Right._Getal());
			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());
			}
		}

protected:
	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 = static_cast<size_type>(_Where - begin());
		size_type _Oldsize = this->_Mysize();
		size_type _Rem = _Oldsize - _Off;

 #if _ITERATOR_DEBUG_LEVEL == 2
		_STL_VERIFY(_Off <= _Oldsize, "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()[static_cast<difference_type>(_Count - 1)]);	// push prefix
					}

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

				_Mid = begin() + static_cast<difference_type>(_Count);
				_Ty _Tmp = _Val;	// in case _Val is in sequence
				_STD move(_Mid + static_cast<difference_type>(_Count),
					_Mid + static_cast<difference_type>(_Off), _Mid);	// copy rest of prefix
				_STD fill(begin() + static_cast<difference_type>(_Off),
					_Mid + static_cast<difference_type>(_Off), _Tmp);	// fill in values
				}
			_CATCH_ALL
			while (_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()[static_cast<difference_type>(_Off + _Num)]);	// push suffix
					}

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

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

			_RERAISE;
			_CATCH_END
			}
		}

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

	[[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 at least _Count pointers, _Mapsize() a power of 2
		static_assert(1 < _DEQUEMAPSIZ,
			"The _Xlen() test should always be performed.");

		_Alpty _Almap(this->_Getal());
		size_type _Newsize = 0 < this->_Mapsize() ? this->_Mapsize() : 1;
		while (_Newsize - this->_Mapsize() < _Count
			|| _Newsize < _DEQUEMAPSIZ)
			{	// scale _Newsize to 2^N >= _Mapsize() + _Count
			if (max_size() / _DEQUESIZ - _Newsize < _Newsize)
				{
				_Xlen();	// result too long
				}

			_Newsize *= 2;
			}
		_Count = _Newsize - this->_Mapsize();

		size_type _Myboff = this->_Myoff() / _DEQUESIZ;
		_Mapptr _Newmap = _Almap.allocate(this->_Mapsize() + _Count);
		_Mapptr _Myptr = _Newmap + _Myboff;

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

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

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

	void _Tidy()
		{	// free all storage
		_Alpty _Almap(this->_Getal());
		while (!empty())
			{
			pop_back();
			}

		for (size_type _Block = this->_Mapsize(); 0 < _Block; )
			{	// free storage for a block and destroy pointer
			if (this->_Map()[--_Block] != pointer())
				{	// free block and destroy its pointer
				this->_Getal().deallocate(this->_Map()[_Block], _DEQUESIZ);
				_Alpty_traits::destroy(_Almap, _STD addressof(this->_Map()[_Block]));
				}
			}

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

		this->_Mapsize() = 0;
		this->_Map() = _Mapptr();
		}

 #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 != nullptr)
			{
			while (*_Pnext != nullptr)
				{
				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 */
	};

#if _HAS_CXX17
template<class _Iter,
	class _Alloc = allocator<_Iter_value_t<_Iter>>,
	enable_if_t<conjunction_v<
		_Is_iterator<_Iter>,
		_Is_allocator<_Alloc>
	>, int> = 0>
	deque(_Iter, _Iter, _Alloc = _Alloc())
		-> deque<_Iter_value_t<_Iter>, _Alloc>;
#endif /* _HAS_CXX17 */

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

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

template<class _Ty,
	class _Alloc>
	_NODISCARD 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>
	_NODISCARD inline bool operator<(const deque<_Ty, _Alloc>& _Left,
		const deque<_Ty, _Alloc>& _Right)
	{	// test if _Left < _Right for deques
	return (_STD lexicographical_compare(_Left.begin(), _Left.end(),
		_Right.begin(), _Right.end()));
	}

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

#if _HAS_CXX17
namespace pmr {
template<class _Ty>
	using deque = _STD deque<_Ty, polymorphic_allocator<_Ty>>;
} // namespace pmr
#endif /* _HAS_CXX17 */
_STD_END

 #pragma pop_macro("new")
 _STL_RESTORE_CLANG_WARNINGS
 #pragma warning(pop)
 #pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _DEQUE_ */

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */