LCOM1920-T02G10

// -*- C++ -*-

//===---------------------------- deque -----------------------------------===//

//

//                     The LLVM Compiler Infrastructure

//

// This file is dual licensed under the MIT and the University of Illinois Open

// Source Licenses. See LICENSE.TXT for details.

//

//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_DEQUE

#define _LIBCPP_DEQUE

/*

    deque synopsis

namespace std

{

template <class T, class Allocator = allocator<T> >

class deque

{

public:

    // types:

    typedef T value_type;

    typedef Allocator allocator_type;

    typedef typename allocator_type::reference       reference;

    typedef typename allocator_type::const_reference const_reference;

    typedef implementation-defined                   iterator;

    typedef implementation-defined                   const_iterator;

    typedef typename allocator_type::size_type       size_type;

    typedef typename allocator_type::difference_type difference_type;

    typedef typename allocator_type::pointer         pointer;

    typedef typename allocator_type::const_pointer   const_pointer;

    typedef std::reverse_iterator<iterator>          reverse_iterator;

    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;

    // construct/copy/destroy:

    deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);

    explicit deque(const allocator_type& a);

    explicit deque(size_type n);

    explicit deque(size_type n, const allocator_type& a); // C++14

    deque(size_type n, const value_type& v);

    deque(size_type n, const value_type& v, const allocator_type& a);

    template <class InputIterator>

        deque(InputIterator f, InputIterator l);

    template <class InputIterator>

        deque(InputIterator f, InputIterator l, const allocator_type& a);

    deque(const deque& c);

    deque(deque&& c)

        noexcept(is_nothrow_move_constructible<allocator_type>::value);

    deque(initializer_list<value_type> il, const Allocator& a = allocator_type());

    deque(const deque& c, const allocator_type& a);

    deque(deque&& c, const allocator_type& a);

    ~deque();

    deque& operator=(const deque& c);

    deque& operator=(deque&& c)

        noexcept(

             allocator_type::propagate_on_container_move_assignment::value &&

             is_nothrow_move_assignable<allocator_type>::value);

    deque& operator=(initializer_list<value_type> il);

    template <class InputIterator>

        void assign(InputIterator f, InputIterator l);

    void assign(size_type n, const value_type& v);

    void assign(initializer_list<value_type> il);

    allocator_type get_allocator() const noexcept;

    // iterators:

    iterator       begin() noexcept;

    const_iterator begin() const noexcept;

    iterator       end() noexcept;

    const_iterator end() const noexcept;

    reverse_iterator       rbegin() noexcept;

    const_reverse_iterator rbegin() const noexcept;

    reverse_iterator       rend() noexcept;

    const_reverse_iterator rend() const noexcept;

    const_iterator         cbegin() const noexcept;

    const_iterator         cend() const noexcept;

    const_reverse_iterator crbegin() const noexcept;

    const_reverse_iterator crend() const noexcept;

    // capacity:

    size_type size() const noexcept;

    size_type max_size() const noexcept;

    void resize(size_type n);

    void resize(size_type n, const value_type& v);

    void shrink_to_fit();

    bool empty() const noexcept;

    // element access:

    reference operator[](size_type i);

    const_reference operator[](size_type i) const;

    reference at(size_type i);

    const_reference at(size_type i) const;

    reference front();

    const_reference front() const;

    reference back();

    const_reference back() const;

    // modifiers:

    void push_front(const value_type& v);

    void push_front(value_type&& v);

    void push_back(const value_type& v);

    void push_back(value_type&& v);

    template <class... Args> void emplace_front(Args&&... args);

    template <class... Args> void emplace_back(Args&&... args);

    template <class... Args> iterator emplace(const_iterator p, Args&&... args);

    iterator insert(const_iterator p, const value_type& v);

    iterator insert(const_iterator p, value_type&& v);

    iterator insert(const_iterator p, size_type n, const value_type& v);

    template <class InputIterator>

        iterator insert(const_iterator p, InputIterator f, InputIterator l);

    iterator insert(const_iterator p, initializer_list<value_type> il);

    void pop_front();

    void pop_back();

    iterator erase(const_iterator p);

    iterator erase(const_iterator f, const_iterator l);

    void swap(deque& c)

        noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17

    void clear() noexcept;

};

template <class T, class Allocator>

    bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator>

    bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator>

    bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator>

    bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator>

    bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator>

    bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

// specialized algorithms:

template <class T, class Allocator>

    void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)

         noexcept(noexcept(x.swap(y)));

}  // std

*/

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

#pragma GCC system_header

#endif

#include <__config>

#include <__split_buffer>

#include <type_traits>

#include <initializer_list>

#include <iterator>

#include <algorithm>

#include <stdexcept>

#include <__undef_min_max>

_LIBCPP_BEGIN_NAMESPACE_STD

template <class _Tp, class _Allocator> class __deque_base;

template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY deque;

template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,

          class _DiffType, _DiffType _BlockSize>

class _LIBCPP_TYPE_VIS_ONLY __deque_iterator;

template <class _RAIter,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

copy(_RAIter __f,

     _RAIter __l,

     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

     typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _OutputIterator>

_OutputIterator

copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

     _OutputIterator __r);

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);

template <class _RAIter,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

copy_backward(_RAIter __f,

              _RAIter __l,

              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

              typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _OutputIterator>

_OutputIterator

copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

              _OutputIterator __r);

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);

template <class _RAIter,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

move(_RAIter __f,

     _RAIter __l,

     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

     typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _OutputIterator>

_OutputIterator

move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

     _OutputIterator __r);

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);

template <class _RAIter,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

move_backward(_RAIter __f,

              _RAIter __l,

              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

              typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _OutputIterator>

_OutputIterator

move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

              _OutputIterator __r);

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);

template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,

          class _DiffType, _DiffType _BlockSize>

class _LIBCPP_TYPE_VIS_ONLY __deque_iterator

{

    typedef _MapPointer __map_iterator;

public:

    typedef _Pointer  pointer;

    typedef _DiffType difference_type;

private:

    __map_iterator __m_iter_;

    pointer        __ptr_;

    static const difference_type __block_size = _BlockSize;

public:

    typedef _ValueType                  value_type;

    typedef random_access_iterator_tag  iterator_category;

    typedef _Reference                  reference;

    _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT

#if _LIBCPP_STD_VER > 11

     : __m_iter_(nullptr), __ptr_(nullptr)

#endif

     {}

    template <class _Pp, class _Rp, class _MP>

    _LIBCPP_INLINE_VISIBILITY

    __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, __block_size>& __it,

                typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT

        : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}

    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;}

    _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;}

    _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++()

    {

        if (++__ptr_ - *__m_iter_ == __block_size)

        {

            ++__m_iter_;

            __ptr_ = *__m_iter_;

        }

        return *this;

    }

    _LIBCPP_INLINE_VISIBILITY __deque_iterator operator++(int)

    {

        __deque_iterator __tmp = *this;

        ++(*this);

        return __tmp;

    }

    _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator--()

    {

        if (__ptr_ == *__m_iter_)

        {

            --__m_iter_;

            __ptr_ = *__m_iter_ + __block_size;

        }

        --__ptr_;

        return *this;

    }

    _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int)

    {

        __deque_iterator __tmp = *this;

        --(*this);

        return __tmp;

    }

    _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n)

    {

        if (__n != 0)

        {

            __n += __ptr_ - *__m_iter_;

            if (__n > 0)

            {

                __m_iter_ += __n / __block_size;

                __ptr_ = *__m_iter_ + __n % __block_size;

            }

            else // (__n < 0)

            {

                difference_type __z = __block_size - 1 - __n;

                __m_iter_ -= __z / __block_size;

                __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);

            }

        }

        return *this;

    }

    _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n)

    {

        return *this += -__n;

    }

    _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const

    {

        __deque_iterator __t(*this);

        __t += __n;

        return __t;

    }

    _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const

    {

        __deque_iterator __t(*this);

        __t -= __n;

        return __t;

    }

    _LIBCPP_INLINE_VISIBILITY

    friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it)

        {return __it + __n;}

    _LIBCPP_INLINE_VISIBILITY

    friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y)

    {

        if (__x != __y)

            return (__x.__m_iter_ - __y.__m_iter_) * __block_size

                 + (__x.__ptr_ - *__x.__m_iter_)

                 - (__y.__ptr_ - *__y.__m_iter_);

        return 0;

    }

    _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const

        {return *(*this + __n);}

    _LIBCPP_INLINE_VISIBILITY friend

        bool operator==(const __deque_iterator& __x, const __deque_iterator& __y)

        {return __x.__ptr_ == __y.__ptr_;}

    _LIBCPP_INLINE_VISIBILITY friend

        bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y)

        {return !(__x == __y);}

    _LIBCPP_INLINE_VISIBILITY friend

        bool operator<(const __deque_iterator& __x, const __deque_iterator& __y)

        {return __x.__m_iter_ < __y.__m_iter_ ||

               (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);}

    _LIBCPP_INLINE_VISIBILITY friend

        bool operator>(const __deque_iterator& __x, const __deque_iterator& __y)

        {return __y < __x;}

    _LIBCPP_INLINE_VISIBILITY friend

        bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y)

        {return !(__y < __x);}

    _LIBCPP_INLINE_VISIBILITY friend

        bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)

        {return !(__x < __y);}

private:

    _LIBCPP_INLINE_VISIBILITY __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT

        : __m_iter_(__m), __ptr_(__p) {}

    template <class _Tp, class _Ap> friend class __deque_base;

    template <class _Tp, class _Ap> friend class _LIBCPP_TYPE_VIS_ONLY deque;

    template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>

        friend class _LIBCPP_TYPE_VIS_ONLY __deque_iterator;

    template <class _RAIter,

              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

    friend

    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

    copy(_RAIter __f,

         _RAIter __l,

         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

         typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);

    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

              class _OutputIterator>

    friend

    _OutputIterator

    copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

         _OutputIterator __r);

    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

    friend

    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

    copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);

    template <class _RAIter,

              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

    friend

    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

    copy_backward(_RAIter __f,

                  _RAIter __l,

                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

                  typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);

    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

              class _OutputIterator>

    friend

    _OutputIterator

    copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

                  _OutputIterator __r);

    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

    friend

    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

    copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);

    template <class _RAIter,

              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

    friend

    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

    move(_RAIter __f,

         _RAIter __l,

         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

         typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);

    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

              class _OutputIterator>

    friend

    _OutputIterator

    move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

         _OutputIterator __r);

    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

    friend

    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

    move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);

    template <class _RAIter,

              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

    friend

    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

    move_backward(_RAIter __f,

                  _RAIter __l,

                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

                  typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);

    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

              class _OutputIterator>

    friend

    _OutputIterator

    move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

                  _OutputIterator __r);

    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

    friend

    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

    move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);

};

// copy

template <class _RAIter,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

copy(_RAIter __f,

     _RAIter __l,

     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

     typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)

{

    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;

    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;

    while (__f != __l)

    {

        pointer __rb = __r.__ptr_;

        pointer __re = *__r.__m_iter_ + _B2;

        difference_type __bs = __re - __rb;

        difference_type __n = __l - __f;

        _RAIter __m = __l;

        if (__n > __bs)

        {

            __n = __bs;

            __m = __f + __n;

        }

        _VSTD::copy(__f, __m, __rb);

        __f = __m;

        __r += __n;

    }

    return __r;

}

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _OutputIterator>

_OutputIterator

copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

     _OutputIterator __r)

{

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;

    difference_type __n = __l - __f;

    while (__n > 0)

    {

        pointer __fb = __f.__ptr_;

        pointer __fe = *__f.__m_iter_ + _B1;

        difference_type __bs = __fe - __fb;

        if (__bs > __n)

        {

            __bs = __n;

            __fe = __fb + __bs;

        }

        __r = _VSTD::copy(__fb, __fe, __r);

        __n -= __bs;

        __f += __bs;

    }

    return __r;

}

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)

{

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;

    difference_type __n = __l - __f;

    while (__n > 0)

    {

        pointer __fb = __f.__ptr_;

        pointer __fe = *__f.__m_iter_ + _B1;

        difference_type __bs = __fe - __fb;

        if (__bs > __n)

        {

            __bs = __n;

            __fe = __fb + __bs;

        }

        __r = _VSTD::copy(__fb, __fe, __r);

        __n -= __bs;

        __f += __bs;

    }

    return __r;

}

// copy_backward

template <class _RAIter,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

copy_backward(_RAIter __f,

              _RAIter __l,

              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

              typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)

{

    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;

    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;

    while (__f != __l)

    {

        __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);

        pointer __rb = *__rp.__m_iter_;

        pointer __re = __rp.__ptr_ + 1;

        difference_type __bs = __re - __rb;

        difference_type __n = __l - __f;

        _RAIter __m = __f;

        if (__n > __bs)

        {

            __n = __bs;

            __m = __l - __n;

        }

        _VSTD::copy_backward(__m, __l, __re);

        __l = __m;

        __r -= __n;

    }

    return __r;

}

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _OutputIterator>

_OutputIterator

copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

              _OutputIterator __r)

{

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;

    difference_type __n = __l - __f;

    while (__n > 0)

    {

        --__l;

        pointer __lb = *__l.__m_iter_;

        pointer __le = __l.__ptr_ + 1;

        difference_type __bs = __le - __lb;

        if (__bs > __n)

        {

            __bs = __n;

            __lb = __le - __bs;

        }

        __r = _VSTD::copy_backward(__lb, __le, __r);

        __n -= __bs;

        __l -= __bs - 1;

    }

    return __r;

}

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)

{

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;

    difference_type __n = __l - __f;

    while (__n > 0)

    {

        --__l;

        pointer __lb = *__l.__m_iter_;

        pointer __le = __l.__ptr_ + 1;

        difference_type __bs = __le - __lb;

        if (__bs > __n)

        {

            __bs = __n;

            __lb = __le - __bs;

        }

        __r = _VSTD::copy_backward(__lb, __le, __r);

        __n -= __bs;

        __l -= __bs - 1;

    }

    return __r;

}

// move

template <class _RAIter,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

move(_RAIter __f,

     _RAIter __l,

     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

     typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)

{

    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;

    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;

    while (__f != __l)

    {

        pointer __rb = __r.__ptr_;

        pointer __re = *__r.__m_iter_ + _B2;

        difference_type __bs = __re - __rb;

        difference_type __n = __l - __f;

        _RAIter __m = __l;

        if (__n > __bs)

        {

            __n = __bs;

            __m = __f + __n;

        }

        _VSTD::move(__f, __m, __rb);

        __f = __m;

        __r += __n;

    }

    return __r;

}

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _OutputIterator>

_OutputIterator

move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

     _OutputIterator __r)

{

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;

    difference_type __n = __l - __f;

    while (__n > 0)

    {

        pointer __fb = __f.__ptr_;

        pointer __fe = *__f.__m_iter_ + _B1;

        difference_type __bs = __fe - __fb;

        if (__bs > __n)

        {

            __bs = __n;

            __fe = __fb + __bs;

        }

        __r = _VSTD::move(__fb, __fe, __r);

        __n -= __bs;

        __f += __bs;

    }

    return __r;

}

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)

{

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;

    difference_type __n = __l - __f;

    while (__n > 0)

    {

        pointer __fb = __f.__ptr_;

        pointer __fe = *__f.__m_iter_ + _B1;

        difference_type __bs = __fe - __fb;

        if (__bs > __n)

        {

            __bs = __n;

            __fe = __fb + __bs;

        }

        __r = _VSTD::move(__fb, __fe, __r);

        __n -= __bs;

        __f += __bs;

    }

    return __r;

}

// move_backward

template <class _RAIter,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

move_backward(_RAIter __f,

              _RAIter __l,

              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,

              typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)

{

    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;

    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;

    while (__f != __l)

    {

        __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);

        pointer __rb = *__rp.__m_iter_;

        pointer __re = __rp.__ptr_ + 1;

        difference_type __bs = __re - __rb;

        difference_type __n = __l - __f;

        _RAIter __m = __f;

        if (__n > __bs)

        {

            __n = __bs;

            __m = __l - __n;

        }

        _VSTD::move_backward(__m, __l, __re);

        __l = __m;

        __r -= __n;

    }

    return __r;

}

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _OutputIterator>

_OutputIterator

move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

              _OutputIterator __r)

{

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;

    difference_type __n = __l - __f;

    while (__n > 0)

    {

        --__l;

        pointer __lb = *__l.__m_iter_;

        pointer __le = __l.__ptr_ + 1;

        difference_type __bs = __le - __lb;

        if (__bs > __n)

        {

            __bs = __n;

            __lb = __le - __bs;

        }

        __r = _VSTD::move_backward(__lb, __le, __r);

        __n -= __bs;

        __l -= __bs - 1;

    }

    return __r;

}

template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,

          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>

__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>

move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,

              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,

              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)

{

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;

    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;

    difference_type __n = __l - __f;

    while (__n > 0)

    {

        --__l;

        pointer __lb = *__l.__m_iter_;

        pointer __le = __l.__ptr_ + 1;

        difference_type __bs = __le - __lb;

        if (__bs > __n)

        {

            __bs = __n;

            __lb = __le - __bs;

        }

        __r = _VSTD::move_backward(__lb, __le, __r);

        __n -= __bs;

        __l -= __bs - 1;

    }

    return __r;

}

template <bool>

class __deque_base_common

{

protected:

    void __throw_length_error() const;

    void __throw_out_of_range() const;

};

template <bool __b>

void

__deque_base_common<__b>::__throw_length_error() const

{

#ifndef _LIBCPP_NO_EXCEPTIONS

    throw length_error("deque");

#endif

}

template <bool __b>

void

__deque_base_common<__b>::__throw_out_of_range() const

{

#ifndef _LIBCPP_NO_EXCEPTIONS

    throw out_of_range("deque");

#endif

}

template <class _Tp, class _Allocator>

class __deque_base

    : protected __deque_base_common<true>

{

    __deque_base(const __deque_base& __c);

    __deque_base& operator=(const __deque_base& __c);

protected:

    typedef _Tp                                      value_type;

    typedef _Allocator                               allocator_type;

    typedef allocator_traits<allocator_type>         __alloc_traits;

    typedef value_type&                              reference;

    typedef const value_type&                        const_reference;

    typedef typename __alloc_traits::size_type       size_type;

    typedef typename __alloc_traits::difference_type difference_type;

    typedef typename __alloc_traits::pointer         pointer;

    typedef typename __alloc_traits::const_pointer   const_pointer;

    static const difference_type __block_size = sizeof(value_type) < 256 ? 4096 / sizeof(value_type) : 16;

    typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator;

    typedef allocator_traits<__pointer_allocator>        __map_traits;

    typedef typename __map_traits::pointer               __map_pointer;

    typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator;

    typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;

    typedef __split_buffer<pointer, __pointer_allocator> __map;

    typedef __deque_iterator<value_type, pointer, reference, __map_pointer,

                             difference_type, __block_size>    iterator;

    typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,

                             difference_type, __block_size>    const_iterator;

    __map __map_;

    size_type __start_;

    __compressed_pair<size_type, allocator_type> __size_;

    iterator       begin() _NOEXCEPT;

    const_iterator begin() const _NOEXCEPT;

    iterator       end() _NOEXCEPT;

    const_iterator end() const _NOEXCEPT;

    _LIBCPP_INLINE_VISIBILITY size_type&            size()          {return __size_.first();}

    _LIBCPP_INLINE_VISIBILITY

    const size_type& size() const _NOEXCEPT {return __size_.first();}

    _LIBCPP_INLINE_VISIBILITY allocator_type&       __alloc()       {return __size_.second();}

    _LIBCPP_INLINE_VISIBILITY

    const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();}

    __deque_base()

        _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);

    explicit __deque_base(const allocator_type& __a);

public:

    ~__deque_base();

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    __deque_base(__deque_base&& __c)

        _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);

    __deque_base(__deque_base&& __c, const allocator_type& __a);

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    void swap(__deque_base& __c)

#if _LIBCPP_STD_VER >= 14

        _NOEXCEPT;

#else

        _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 

                    __is_nothrow_swappable<allocator_type>::value);

#endif

protected:

    void clear() _NOEXCEPT;

    bool __invariants() const;

    _LIBCPP_INLINE_VISIBILITY

    void __move_assign(__deque_base& __c)

        _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&

                   is_nothrow_move_assignable<allocator_type>::value)

    {

        __map_ = _VSTD::move(__c.__map_);

        __start_ = __c.__start_;

        size() = __c.size();

        __move_assign_alloc(__c);

        __c.__start_ = __c.size() = 0;

    }

    _LIBCPP_INLINE_VISIBILITY

    void __move_assign_alloc(__deque_base& __c)

        _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||

                   is_nothrow_move_assignable<allocator_type>::value)

        {__move_assign_alloc(__c, integral_constant<bool,

                      __alloc_traits::propagate_on_container_move_assignment::value>());}

private:

    _LIBCPP_INLINE_VISIBILITY

    void __move_assign_alloc(__deque_base& __c, true_type)

        _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)

        {

            __alloc() = _VSTD::move(__c.__alloc());

        }

    _LIBCPP_INLINE_VISIBILITY

    void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT

        {}

};

template <class _Tp, class _Allocator>

bool

__deque_base<_Tp, _Allocator>::__invariants() const

{

    if (!__map_.__invariants())

        return false;

    if (__map_.size() >= size_type(-1) / __block_size)

        return false;

    for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();

         __i != __e; ++__i)

        if (*__i == nullptr)

            return false;

    if (__map_.size() != 0)

    {

        if (size() >= __map_.size() * __block_size)

            return false;

        if (__start_ >= __map_.size() * __block_size - size())

            return false;

    }

    else

    {

        if (size() != 0)

            return false;

        if (__start_ != 0)

            return false;

    }

    return true;

}

template <class _Tp, class _Allocator>

typename __deque_base<_Tp, _Allocator>::iterator

__deque_base<_Tp, _Allocator>::begin() _NOEXCEPT

{

    __map_pointer __mp = __map_.begin() + __start_ / __block_size;

    return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);

}

template <class _Tp, class _Allocator>

typename __deque_base<_Tp, _Allocator>::const_iterator

__deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT

{

    __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);

    return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);

}

template <class _Tp, class _Allocator>

typename __deque_base<_Tp, _Allocator>::iterator

__deque_base<_Tp, _Allocator>::end() _NOEXCEPT

{

    size_type __p = size() + __start_;

    __map_pointer __mp = __map_.begin() + __p / __block_size;

    return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);

}

template <class _Tp, class _Allocator>

typename __deque_base<_Tp, _Allocator>::const_iterator

__deque_base<_Tp, _Allocator>::end() const _NOEXCEPT

{

    size_type __p = size() + __start_;

    __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);

    return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);

}

template <class _Tp, class _Allocator>

inline _LIBCPP_INLINE_VISIBILITY

__deque_base<_Tp, _Allocator>::__deque_base()

    _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)

    : __start_(0), __size_(0) {}

template <class _Tp, class _Allocator>

inline _LIBCPP_INLINE_VISIBILITY

__deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a)

    : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}

template <class _Tp, class _Allocator>

__deque_base<_Tp, _Allocator>::~__deque_base()

{

    clear();

    typename __map::iterator __i = __map_.begin();

    typename __map::iterator __e = __map_.end();

    for (; __i != __e; ++__i)

        __alloc_traits::deallocate(__alloc(), *__i, __block_size);

}

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

template <class _Tp, class _Allocator>

__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c)

    _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)

    : __map_(_VSTD::move(__c.__map_)),

      __start_(_VSTD::move(__c.__start_)),

      __size_(_VSTD::move(__c.__size_))

{

    __c.__start_ = 0;

    __c.size() = 0;

}

template <class _Tp, class _Allocator>

__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a)

    : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)),

      __start_(_VSTD::move(__c.__start_)),

      __size_(_VSTD::move(__c.size()), __a)

{

    if (__a == __c.__alloc())

    {

        __c.__start_ = 0;

        __c.size() = 0;

    }

    else

    {

        __map_.clear();

        __start_ = 0;

        size() = 0;

    }

}

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

template <class _Tp, class _Allocator>

void

__deque_base<_Tp, _Allocator>::swap(__deque_base& __c)

#if _LIBCPP_STD_VER >= 14

        _NOEXCEPT

#else

        _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 

                    __is_nothrow_swappable<allocator_type>::value)

#endif

{

    __map_.swap(__c.__map_);

    _VSTD::swap(__start_, __c.__start_);

    _VSTD::swap(size(), __c.size());

    __swap_allocator(__alloc(), __c.__alloc());

}

template <class _Tp, class _Allocator>

void

__deque_base<_Tp, _Allocator>::clear() _NOEXCEPT

{

    allocator_type& __a = __alloc();

    for (iterator __i = begin(), __e = end(); __i != __e; ++__i)

        __alloc_traits::destroy(__a, _VSTD::addressof(*__i));

    size() = 0;

    while (__map_.size() > 2)

    {

        __alloc_traits::deallocate(__a, __map_.front(), __block_size);

        __map_.pop_front();

    }

    switch (__map_.size())

    {

    case 1:

        __start_ = __block_size / 2;

        break;

    case 2:

        __start_ = __block_size;

        break;

    }

}

template <class _Tp, class _Allocator /*= allocator<_Tp>*/>

class _LIBCPP_TYPE_VIS_ONLY deque

    : private __deque_base<_Tp, _Allocator>

{

public:

    // types:

    typedef _Tp value_type;

    typedef _Allocator allocator_type;

    typedef __deque_base<value_type, allocator_type> __base;

    typedef typename __base::__alloc_traits        __alloc_traits;

    typedef typename __base::reference             reference;

    typedef typename __base::const_reference       const_reference;

    typedef typename __base::iterator              iterator;

    typedef typename __base::const_iterator        const_iterator;

    typedef typename __base::size_type             size_type;

    typedef typename __base::difference_type       difference_type;

    typedef typename __base::pointer               pointer;

    typedef typename __base::const_pointer         const_pointer;

    typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;

    typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;

    // construct/copy/destroy:

    _LIBCPP_INLINE_VISIBILITY

    deque()

        _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)

        {}

    _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {}

    explicit deque(size_type __n);

#if _LIBCPP_STD_VER > 11

    explicit deque(size_type __n, const _Allocator& __a);

#endif

    deque(size_type __n, const value_type& __v);

    deque(size_type __n, const value_type& __v, const allocator_type& __a);

    template <class _InputIter>

        deque(_InputIter __f, _InputIter __l,

              typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);

    template <class _InputIter>

        deque(_InputIter __f, _InputIter __l, const allocator_type& __a,

              typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);

    deque(const deque& __c);

    deque(const deque& __c, const allocator_type& __a);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    deque(initializer_list<value_type> __il);

    deque(initializer_list<value_type> __il, const allocator_type& __a);

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    deque& operator=(const deque& __c);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}

#endif   // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);

    deque(deque&& __c, const allocator_type& __a);

    deque& operator=(deque&& __c)

        _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&

                   is_nothrow_move_assignable<allocator_type>::value);

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    template <class _InputIter>

        void assign(_InputIter __f, _InputIter __l,

                    typename enable_if<__is_input_iterator<_InputIter>::value &&

                                      !__is_random_access_iterator<_InputIter>::value>::type* = 0);

    template <class _RAIter>

        void assign(_RAIter __f, _RAIter __l,

                    typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);

    void assign(size_type __n, const value_type& __v);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    allocator_type get_allocator() const _NOEXCEPT;

    // iterators:

    _LIBCPP_INLINE_VISIBILITY

    iterator       begin() _NOEXCEPT       {return __base::begin();}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator begin() const _NOEXCEPT {return __base::begin();}

    _LIBCPP_INLINE_VISIBILITY

    iterator       end() _NOEXCEPT         {return __base::end();}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator end()   const _NOEXCEPT {return __base::end();}

    _LIBCPP_INLINE_VISIBILITY

    reverse_iterator       rbegin() _NOEXCEPT

        {return       reverse_iterator(__base::end());}

    _LIBCPP_INLINE_VISIBILITY

    const_reverse_iterator rbegin() const _NOEXCEPT

        {return const_reverse_iterator(__base::end());}

    _LIBCPP_INLINE_VISIBILITY

    reverse_iterator       rend() _NOEXCEPT

        {return       reverse_iterator(__base::begin());}

    _LIBCPP_INLINE_VISIBILITY

    const_reverse_iterator rend()   const _NOEXCEPT

        {return const_reverse_iterator(__base::begin());}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator         cbegin()  const _NOEXCEPT

        {return __base::begin();}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator         cend()    const _NOEXCEPT

        {return __base::end();}

    _LIBCPP_INLINE_VISIBILITY

    const_reverse_iterator crbegin() const _NOEXCEPT

        {return const_reverse_iterator(__base::end());}

    _LIBCPP_INLINE_VISIBILITY

    const_reverse_iterator crend()   const _NOEXCEPT

        {return const_reverse_iterator(__base::begin());}

    // capacity:

    _LIBCPP_INLINE_VISIBILITY

    size_type size() const _NOEXCEPT {return __base::size();}

    _LIBCPP_INLINE_VISIBILITY

    size_type max_size() const _NOEXCEPT

        {return __alloc_traits::max_size(__base::__alloc());}

    void resize(size_type __n);

    void resize(size_type __n, const value_type& __v);

    void shrink_to_fit() _NOEXCEPT;

    _LIBCPP_INLINE_VISIBILITY

    bool empty() const _NOEXCEPT {return __base::size() == 0;}

    // element access:

    reference operator[](size_type __i);

    const_reference operator[](size_type __i) const;

    reference at(size_type __i);

    const_reference at(size_type __i) const;

    reference front();

    const_reference front() const;

    reference back();

    const_reference back() const;

    // 23.2.2.3 modifiers:

    void push_front(const value_type& __v);

    void push_back(const value_type& __v);

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

#ifndef _LIBCPP_HAS_NO_VARIADICS

    template <class... _Args> void emplace_front(_Args&&... __args);

    template <class... _Args> void emplace_back(_Args&&... __args);

    template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args);

#endif  // _LIBCPP_HAS_NO_VARIADICS

    void push_front(value_type&& __v);

    void push_back(value_type&& __v);

    iterator insert(const_iterator __p, value_type&& __v);

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    iterator insert(const_iterator __p, const value_type& __v);

    iterator insert(const_iterator __p, size_type __n, const value_type& __v);

    template <class _InputIter>

        iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,

                         typename enable_if<__is_input_iterator<_InputIter>::value

                                         &&!__is_forward_iterator<_InputIter>::value>::type* = 0);

    template <class _ForwardIterator>

        iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,

                               typename enable_if<__is_forward_iterator<_ForwardIterator>::value

                                         &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type* = 0);

    template <class _BiIter>

        iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,

                         typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type* = 0);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    iterator insert(const_iterator __p, initializer_list<value_type> __il)

        {return insert(__p, __il.begin(), __il.end());}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    void pop_front();

    void pop_back();

    iterator erase(const_iterator __p);

    iterator erase(const_iterator __f, const_iterator __l);

    void swap(deque& __c)

#if _LIBCPP_STD_VER >= 14

        _NOEXCEPT;

#else

        _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||

                   __is_nothrow_swappable<allocator_type>::value);

#endif

    void clear() _NOEXCEPT;

    _LIBCPP_INLINE_VISIBILITY

    bool __invariants() const {return __base::__invariants();}

private:

    typedef typename __base::__map_const_pointer __map_const_pointer;

    _LIBCPP_INLINE_VISIBILITY

    static size_type __recommend_blocks(size_type __n)

    {

        return __n / __base::__block_size + (__n % __base::__block_size != 0);

    }

    _LIBCPP_INLINE_VISIBILITY

    size_type __capacity() const

    {

        return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;

    }

    _LIBCPP_INLINE_VISIBILITY

    size_type __front_spare() const

    {

        return __base::__start_;

    }

    _LIBCPP_INLINE_VISIBILITY

    size_type __back_spare() const

    {

        return __capacity() - (__base::__start_ + __base::size());

    }

    template <class _InpIter>

        void __append(_InpIter __f, _InpIter __l,

                 typename enable_if<__is_input_iterator<_InpIter>::value &&

                                   !__is_forward_iterator<_InpIter>::value>::type* = 0);

    template <class _ForIter>

        void __append(_ForIter __f, _ForIter __l,

                      typename enable_if<__is_forward_iterator<_ForIter>::value>::type* = 0);

    void __append(size_type __n);

    void __append(size_type __n, const value_type& __v);

    void __erase_to_end(const_iterator __f);

    void __add_front_capacity();

    void __add_front_capacity(size_type __n);

    void __add_back_capacity();

    void __add_back_capacity(size_type __n);

    iterator __move_and_check(iterator __f, iterator __l, iterator __r,

                              const_pointer& __vt);

    iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r,

                                       const_pointer& __vt);

    void __move_construct_and_check(iterator __f, iterator __l,

                                    iterator __r, const_pointer& __vt);

    void __move_construct_backward_and_check(iterator __f, iterator __l,

                                             iterator __r, const_pointer& __vt);

    _LIBCPP_INLINE_VISIBILITY

    void __copy_assign_alloc(const deque& __c)

        {__copy_assign_alloc(__c, integral_constant<bool,

                      __alloc_traits::propagate_on_container_copy_assignment::value>());}

    _LIBCPP_INLINE_VISIBILITY

    void __copy_assign_alloc(const deque& __c, true_type)

        {

            if (__base::__alloc() != __c.__alloc())

            {

                clear();

                shrink_to_fit();

            }

            __base::__alloc() = __c.__alloc();

            __base::__map_.__alloc() = __c.__map_.__alloc();

        }

    _LIBCPP_INLINE_VISIBILITY

    void __copy_assign_alloc(const deque&, false_type)

        {}

    void __move_assign(deque& __c, true_type)

        _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);

    void __move_assign(deque& __c, false_type);

};

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>::deque(size_type __n)

{

    if (__n > 0)

        __append(__n);

}

#if _LIBCPP_STD_VER > 11

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a)

    : __base(__a)

{

    if (__n > 0)

        __append(__n);

}

#endif

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)

{

    if (__n > 0)

        __append(__n, __v);

}

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a)

    : __base(__a)

{

    if (__n > 0)

        __append(__n, __v);

}

template <class _Tp, class _Allocator>

template <class _InputIter>

deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l,

              typename enable_if<__is_input_iterator<_InputIter>::value>::type*)

{

    __append(__f, __l);

}

template <class _Tp, class _Allocator>

template <class _InputIter>

deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a,

              typename enable_if<__is_input_iterator<_InputIter>::value>::type*)

    : __base(__a)

{

    __append(__f, __l);

}

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>::deque(const deque& __c)

    : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))

{

    __append(__c.begin(), __c.end());

}

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a)

    : __base(__a)

{

    __append(__c.begin(), __c.end());

}

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)

{

    __append(__il.begin(), __il.end());

}

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a)

    : __base(__a)

{

    __append(__il.begin(), __il.end());

}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

template <class _Tp, class _Allocator>

deque<_Tp, _Allocator>&

deque<_Tp, _Allocator>::operator=(const deque& __c)

{

    if (this != &__c)

    {

        __copy_assign_alloc(__c);

        assign(__c.begin(), __c.end());

    }

    return *this;

}

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

template <class _Tp, class _Allocator>

inline _LIBCPP_INLINE_VISIBILITY

deque<_Tp, _Allocator>::deque(deque&& __c)

    _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)

    : __base(_VSTD::move(__c))

{

}

template <class _Tp, class _Allocator>

inline _LIBCPP_INLINE_VISIBILITY

deque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a)

    : __base(_VSTD::move(__c), __a)

{

    if (__a != __c.__alloc())

    {

        typedef move_iterator<iterator> _Ip;

        assign(_Ip(__c.begin()), _Ip(__c.end()));

    }

}

template <class _Tp, class _Allocator>

inline _LIBCPP_INLINE_VISIBILITY

deque<_Tp, _Allocator>&

deque<_Tp, _Allocator>::operator=(deque&& __c)

        _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&

                   is_nothrow_move_assignable<allocator_type>::value)

{

    __move_assign(__c, integral_constant<bool,

          __alloc_traits::propagate_on_container_move_assignment::value>());

    return *this;

}

template <class _Tp, class _Allocator>

void

deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type)

{

    if (__base::__alloc() != __c.__alloc())

    {

        typedef move_iterator<iterator> _Ip;

        assign(_Ip(__c.begin()), _Ip(__c.end()));

    }

    else

        __move_assign(__c, true_type());

}

template <class _Tp, class _Allocator>

void

deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type)

    _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)

{

    clear();

    shrink_to_fit();

    __base::__move_assign(__c);

}

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

template <class _Tp, class _Allocator>

template <class _InputIter>

void

deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,

                               typename enable_if<__is_input_iterator<_InputIter>::value &&

                                                 !__is_random_access_iterator<_InputIter>::value>::type*)

{

    iterator __i = __base::begin();

    iterator __e = __base::end();

    for (; __f != __l && __i != __e; ++__f, (void) ++__i)

        *__i = *__f;

    if (__f != __l)

        __append(__f, __l);

    else

        __erase_to_end(__i);

}

template <class _Tp, class _Allocator>