[libc++] Remove __deque_base

[philnik]

Summary

This patch simplifies the implementation of deque by removing the __deque_base class which results in a lot less indirections and removes the need for __base::.

[philnik]

• Fix CI

[philnik]

• Fix CI

[philnik]

• Add C++03 spaces

[philnik]

• Use TEST_ALIGNOF

[philnik]

• Try to fix CI

[ldionne]

Looks mostly good, but I'd like to see it again before it goes in.

libcxx/include/deque

1046

We need to spam _LIBCPP_HIDE_FROM_ABI here and in other places. Fine to do in a follow-up.

1066–1068

I would not use default member initalizers because that is a potential change in semantics. I'd be fine with the change if it were done in its separate patch where we can focus on the potential effects of it.

In particular, undoing this should force you to really "copy" the definition of the various __deque_base constructors, which I can see have changed in the current version of the patch.

[philnik]

• Address comments

[philnik]

libcxx/include/deque

1046

See D132320.

[philnik]

• Try to get the right ABI numbers

[ldionne]

LGTM with green CI and my comments applied.

libcxx/include/deque

1054–1057

I had never noticed this, but we have two allocators. One is in the __compressed_pair we see right here, and the other one is in the __map, which is a __split_buffer. This is weird.

I think this means that we can actually be lying when we set the noexcept-ness of deque() and friends. I think we should add this:

static_assert(is_nothrow_default_constructible<allocator_type>::value == is_nothrow_default_constructible<_SplitBufferAllocator>::value, "");
static_assert(is_nothrow_move_constructible<allocator_type>::value == is_nothrow_move_constructible<_SplitBufferAllocator>::value, "");
// etc...

I can't imagine this not being true, however this would provide guard rails and it would nicely document the code.

[philnik]

• Address comments

[philnik]

• Rebased

[philnik]

• Fix CI

[philnik]

• Next try

[brooksmoses]

I'm seeing new compilation errors from the moved allocator static_assert in this patch.

Reduced test case:

#include <deque>
#include <memory>
BaseContainerTtemplate <typename T> struct CustomAllocator : public std::allocator<T> {};
void foo() {std::deque<int, CustomAllocator<int>> bar;}

Error:

include/c++/v1/deque:974:3: error: static assertion failed due to requirement 'is_same<CustomAllocator<int>, std::allocator<int>>::value': rebinding an allocator to value_type should result in the original allocator
  static_assert(is_same<allocator_type, typename __rebind_alloc_helper<__alloc_traits, value_type>::type>::value,
  ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
test.cc:4:51: note: in instantiation of template class 'std::deque<int, CustomAllocator<int>>' requested here
void foo() {std::deque<int, CustomAllocator<int>> bar;}
                                                  ^

Could you please investigate?

[philnik]

In D132081#3772577, @brooksmoses wrote:

I'm seeing new compilation errors from the moved allocator static_assert in this patch.

Reduced test case:

#include <deque>
#include <memory>
BaseContainerTtemplate <typename T> struct CustomAllocator : public std::allocator<T> {};
void foo() {std::deque<int, CustomAllocator<int>> bar;}

Error:

include/c++/v1/deque:974:3: error: static assertion failed due to requirement 'is_same<CustomAllocator<int>, std::allocator<int>>::value': rebinding an allocator to value_type should result in the original allocator
  static_assert(is_same<allocator_type, typename __rebind_alloc_helper<__alloc_traits, value_type>::type>::value,
  ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
test.cc:4:51: note: in instantiation of template class 'std::deque<int, CustomAllocator<int>>' requested here
void foo() {std::deque<int, CustomAllocator<int>> bar;}
                                                  ^

Could you please investigate?

The static_assert wasn't moved, it was added. As the error message says, rebinding an allocator to the same type has to result in the same allocator. You have to add something like

template <class U>
struct rebind {
    using other = allocator<U>;
};

to your allocator pre-C++20.

[brooksmoses]

Thanks, @philnik ; that patch indeed works. I appreciate the quick reply, too.

libcxx/include/deque

 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Tp, class _Allocator> class __deque_base;
 template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS deque;
 
 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
           class _DiffType, _DiffType _BlockSize>
 class _LIBCPP_TEMPLATE_VIS __deque_iterator;
 
 template <class _RAIter,
           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
#endif
     _LIBCPP_INLINE_VISIBILITY friend
         bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)
         {return !(__x < __y);}
 
 private:
     _LIBCPP_INLINE_VISIBILITY explicit __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_TEMPLATE_VIS deque;
     template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>
         friend class _LIBCPP_TEMPLATE_VIS __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>
while (__n > 0)
         }
         __r = _VSTD::move_backward(__lb, __le, __r);
         __n -= __bs;
         __l -= __bs - 1;
     }
     return __r;
 }
 
-template <class _Tp, class _Allocator>
-class __deque_base
+template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
+class _LIBCPP_TEMPLATE_VIS deque
 {
-    __deque_base(const __deque_base& __c);
-    __deque_base& operator=(const __deque_base& __c);
 public:
-    typedef _Allocator                                allocator_type;
-    typedef allocator_traits<allocator_type>          __alloc_traits;
-    typedef typename __alloc_traits::size_type        size_type;
-
-    typedef _Tp                                       value_type;
-    typedef value_type&                               reference;
-    typedef const value_type&                         const_reference;
-    typedef typename __alloc_traits::difference_type  difference_type;
-    typedef typename __alloc_traits::pointer          pointer;
-    typedef typename __alloc_traits::const_pointer    const_pointer;
+    // types:
 
-    static const difference_type __block_size;
+  using value_type = _Tp;
 
-    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>    iterator;
-    typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
-                             difference_type>    const_iterator;
+  static_assert((is_same<typename _Allocator::value_type, value_type>::value),
+                "Allocator::value_type must be same type as value_type");
 
-    struct __deque_block_range {
-      explicit __deque_block_range(pointer __b, pointer __e) _NOEXCEPT : __begin_(__b), __end_(__e) {}
-      const pointer __begin_;
-      const pointer __end_;
-    };
+  using allocator_type = _Allocator;
+  using __alloc_traits = allocator_traits<allocator_type>;
+
+  using size_type       = typename __alloc_traits::size_type;
+  using difference_type = typename __alloc_traits::difference_type;
+
+  using pointer       = typename __alloc_traits::pointer;
+  using const_pointer = typename __alloc_traits::const_pointer;
+
+  using __pointer_allocator       = typename __rebind_alloc_helper<__alloc_traits, pointer>::type;
+  using __const_pointer_allocator = typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type;
+  using __map                     = __split_buffer<pointer, __pointer_allocator>;
+  using __map_alloc_traits        = allocator_traits<__pointer_allocator>;
+  using __map_pointer             = typename __map_alloc_traits::pointer;
+  using __map_const_pointer       = typename allocator_traits<__const_pointer_allocator>::const_pointer;
+
+  using reference       = value_type&;
+  using const_reference = const value_type&;
+
+  using iterator = __deque_iterator<value_type, pointer, reference, __map_pointer, difference_type>;
+  using const_iterator =
+      __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer, difference_type>;
+  using reverse_iterator       = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+  static_assert(is_same<allocator_type, typename __rebind_alloc_helper<__alloc_traits, value_type>::type>::value,
+                "rebinding an allocator to value_type should result in the original allocator");
+  static_assert(is_nothrow_default_constructible<allocator_type>::value ==
+                    is_nothrow_default_constructible<__pointer_allocator>::value,
+                "rebinding an allocator should not change excpetion guarantees");
+  static_assert(is_nothrow_move_constructible<allocator_type>::value ==
+                    is_nothrow_move_constructible<typename __map::allocator_type>::value,
+                "rebinding an allocator should not change excpetion guarantees");
+
+private:
 
-    struct __deque_range {
-      iterator __pos_;
-      const iterator __end_;
 
-      __deque_range(iterator __pos, iterator __e) _NOEXCEPT
-        : __pos_(__pos), __end_(__e) {}
 
-      explicit operator bool() const _NOEXCEPT {
-        return __pos_ != __end_;
-      }
 
-      __deque_range begin() const {
-        return *this;
-      }
 
-      __deque_range end() const {
-        return __deque_range(__end_, __end_);
-      }
-      __deque_block_range operator*() const _NOEXCEPT {
-         if (__pos_.__m_iter_ == __end_.__m_iter_) {
-          return __deque_block_range(__pos_.__ptr_, __end_.__ptr_);
-        }
-        return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size);
-      }
 
-      __deque_range& operator++() _NOEXCEPT {
-        if (__pos_.__m_iter_ == __end_.__m_iter_) {
-          __pos_ = __end_;
-        } else {
-          ++__pos_.__m_iter_;
-          __pos_.__ptr_ = *__pos_.__m_iter_;
-        }
-        return *this;
-      }
 
 
-      _LIBCPP_HIDE_FROM_ABI friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) {
-        return __lhs.__pos_ == __rhs.__pos_;
-      }
-      _LIBCPP_HIDE_FROM_ABI friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) {
-        return !(__lhs == __rhs);
-      }
-    };
 
-
-
-    struct _ConstructTransaction {
-      _ConstructTransaction(__deque_base* __db, __deque_block_range& __r)
-        : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {}
+    _ConstructTransaction(deque* __db, __deque_block_range& __r)
 
 
-      ~_ConstructTransaction() {
-        __base_->size() += (__pos_ - __begin_);
-      }
+      __base_->__size() += (__pos_ - __begin_);
 
-      pointer __pos_;
-      const pointer __end_;
-    private:
-      const pointer __begin_;
-      __deque_base * const __base_;
-    };
+    deque* const __base_;
 
-protected:
-    __map __map_;
-    size_type __start_;
-    __compressed_pair<size_type, allocator_type> __size_;
+  static const difference_type __block_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();}
-
-    _LIBCPP_INLINE_VISIBILITY
-    __deque_base()
-        _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
-    _LIBCPP_INLINE_VISIBILITY
-    explicit __deque_base(const allocator_type& __a);
 public:
-    ~__deque_base();
-
-#ifndef _LIBCPP_CXX03_LANG
-    __deque_base(__deque_base&& __c)
-        _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
-    __deque_base(__deque_base&& __c, const allocator_type& __a);
-#endif // _LIBCPP_CXX03_LANG
-
-    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());
-        }
 
+    // construct/copy/destroy:
     _LIBCPP_INLINE_VISIBILITY
-    void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT
-        {}
-};
-
-template <class _Tp, class _Allocator>
-const typename __deque_base<_Tp, _Allocator>::difference_type
-    __deque_base<_Tp, _Allocator>::__block_size =
-        __deque_block_size<value_type, difference_type>::value;
-
-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
-__deque_base<_Tp, _Allocator>::__deque_base()
-    _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
+    deque() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
         : __start_(0), __size_(0, __default_init_tag()) {}
 
-template <class _Tp, class _Allocator>
-inline
-__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()
-{
+    _LIBCPP_HIDE_FROM_ABI ~deque() {
       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_CXX03_LANG
-
-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_CXX03_LANG
-
-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());
-    _VSTD::__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_TEMPLATE_VIS deque
-    : private __deque_base<_Tp, _Allocator>
-{
-public:
-    // types:
-
-    typedef _Tp value_type;
-    typedef _Allocator allocator_type;
-
-    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
-                  "Allocator::value_type must be same type as value_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;
-
-    using typename __base::__deque_range;
-    using typename __base::__deque_block_range;
-    using typename __base::_ConstructTransaction;
+    _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a)
+        : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}
 
-    // 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);
 
     template <class = __enable_if_t<__is_allocator<_Allocator>::value> >
-    deque(size_type __n, const value_type& __v, const allocator_type& __a) : __base(__a)
+    deque(size_type __n, const value_type& __v, const allocator_type& __a)
+        : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
     {
         if (__n > 0)
             __append(__n, __v);
     }
 
     template <class _InputIter>
         deque(_InputIter __f, _InputIter __l,
               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
     template <class _InputIter>
         deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
     deque(const deque& __c);
     deque(const deque& __c, const __type_identity_t<allocator_type>& __a);
 
     deque& operator=(const deque& __c);
 
 #ifndef _LIBCPP_CXX03_LANG
     deque(initializer_list<value_type> __il);
     deque(initializer_list<value_type> __il, const allocator_type& __a);
 
     _LIBCPP_INLINE_VISIBILITY
     deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
 
     _LIBCPP_INLINE_VISIBILITY
-    deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
+    deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
     _LIBCPP_INLINE_VISIBILITY
     deque(deque&& __c, const __type_identity_t<allocator_type>& __a);
     _LIBCPP_INLINE_VISIBILITY
     deque& operator=(deque&& __c)
         _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
                    is_nothrow_move_assignable<allocator_type>::value);
 
     _LIBCPP_INLINE_VISIBILITY
     void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
 #endif // _LIBCPP_CXX03_LANG
 
     template <class _InputIter>
         void assign(_InputIter __f, _InputIter __l,
                     typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
                                       !__is_cpp17_random_access_iterator<_InputIter>::value>::type* = 0);
     template <class _RAIter>
         void assign(_RAIter __f, _RAIter __l,
                     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
     void assign(size_type __n, const value_type& __v);
 
     _LIBCPP_INLINE_VISIBILITY
     allocator_type get_allocator() const _NOEXCEPT;
+  _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __size_.second(); }
+  _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __size_.second(); }
 
-    // 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_HIDE_FROM_ABI iterator begin() _NOEXCEPT {
+      __map_pointer __mp = __map_.begin() + __start_ / __block_size;
+      return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI const_iterator 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);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI iterator 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);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI const_iterator 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);
+  }
 
     _LIBCPP_INLINE_VISIBILITY
     reverse_iterator       rbegin() _NOEXCEPT
-        {return       reverse_iterator(__base::end());}
+        {return       reverse_iterator(end());}
     _LIBCPP_INLINE_VISIBILITY
     const_reverse_iterator rbegin() const _NOEXCEPT
-        {return const_reverse_iterator(__base::end());}
+        {return const_reverse_iterator(end());}
     _LIBCPP_INLINE_VISIBILITY
     reverse_iterator       rend() _NOEXCEPT
-        {return       reverse_iterator(__base::begin());}
+        {return       reverse_iterator(begin());}
     _LIBCPP_INLINE_VISIBILITY
     const_reverse_iterator rend()   const _NOEXCEPT
-        {return const_reverse_iterator(__base::begin());}
+        {return const_reverse_iterator(begin());}
 
     _LIBCPP_INLINE_VISIBILITY
     const_iterator         cbegin()  const _NOEXCEPT
-        {return __base::begin();}
+        {return begin();}
     _LIBCPP_INLINE_VISIBILITY
     const_iterator         cend()    const _NOEXCEPT
-        {return __base::end();}
+        {return end();}
     _LIBCPP_INLINE_VISIBILITY
     const_reverse_iterator crbegin() const _NOEXCEPT
-        {return const_reverse_iterator(__base::end());}
+        {return const_reverse_iterator(end());}
     _LIBCPP_INLINE_VISIBILITY
     const_reverse_iterator crend()   const _NOEXCEPT
-        {return const_reverse_iterator(__base::begin());}
+        {return const_reverse_iterator(begin());}
 
     // capacity:
     _LIBCPP_INLINE_VISIBILITY
-    size_type size() const _NOEXCEPT {return __base::size();}
+    size_type size() const _NOEXCEPT {return __size();}
+
+  _LIBCPP_HIDE_FROM_ABI size_type& __size() _NOEXCEPT { return __size_.first(); }
+  _LIBCPP_HIDE_FROM_ABI const size_type& __size() const _NOEXCEPT { return __size_.first(); }
+
     _LIBCPP_INLINE_VISIBILITY
     size_type max_size() const _NOEXCEPT
         {return _VSTD::min<size_type>(
-            __alloc_traits::max_size(__base::__alloc()),
+            __alloc_traits::max_size(__alloc()),
             numeric_limits<difference_type>::max());}
     void resize(size_type __n);
     void resize(size_type __n, const value_type& __v);
     void shrink_to_fit() _NOEXCEPT;
     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
-    bool empty() const _NOEXCEPT {return __base::size() == 0;}
+    bool empty() const _NOEXCEPT {return size() == 0;}
 
     // element access:
     _LIBCPP_INLINE_VISIBILITY
     reference operator[](size_type __i) _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     const_reference operator[](size_type __i) const _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     reference at(size_type __i);

 #else
         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
                    __is_nothrow_swappable<allocator_type>::value);
 #endif
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY
-    bool __invariants() const {return __base::__invariants();}
+    bool __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;
+    }
 
-    typedef typename __base::__map_const_pointer __map_const_pointer;
+    _LIBCPP_INLINE_VISIBILITY
+    void __move_assign_alloc(deque& __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>());}
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __move_assign_alloc(deque& __c, true_type)
+        _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
+        {
+            __alloc() = _VSTD::move(__c.__alloc());
+        }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __move_assign_alloc(deque&, false_type) _NOEXCEPT
+        {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __move_assign(deque& __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
     static size_type __recommend_blocks(size_type __n)
     {
-        return __n / __base::__block_size + (__n % __base::__block_size != 0);
+        return __n / __block_size + (__n % __block_size != 0);
     }
     _LIBCPP_INLINE_VISIBILITY
     size_type __capacity() const
     {
-        return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
+        return __map_.size() == 0 ? 0 : __map_.size() * __block_size - 1;
     }
     _LIBCPP_INLINE_VISIBILITY
     size_type __block_count() const
     {
-        return __base::__map_.size();
+        return __map_.size();
     }
 
     _LIBCPP_INLINE_VISIBILITY
     size_type __front_spare() const
     {
-        return __base::__start_;
+        return __start_;
     }
     _LIBCPP_INLINE_VISIBILITY
     size_type __front_spare_blocks() const {
-      return __front_spare() / __base::__block_size;
+      return __front_spare() / __block_size;
     }
     _LIBCPP_INLINE_VISIBILITY
     size_type __back_spare() const
     {
-        return __capacity() - (__base::__start_ + __base::size());
+        return __capacity() - (__start_ + size());
     }
     _LIBCPP_INLINE_VISIBILITY
     size_type __back_spare_blocks() const {
-      return __back_spare() / __base::__block_size;
+      return __back_spare() / __block_size;
     }
 
  private:
     _LIBCPP_INLINE_VISIBILITY
     bool __maybe_remove_front_spare(bool __keep_one = true) {
       if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) {
-        __alloc_traits::deallocate(__base::__alloc(), __base::__map_.front(),
-                                   __base::__block_size);
-        __base::__map_.pop_front();
-        __base::__start_ -= __base::__block_size;
+        __alloc_traits::deallocate(__alloc(), __map_.front(),
+                                   __block_size);
+        __map_.pop_front();
+        __start_ -= __block_size;
         return true;
       }
       return false;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     bool __maybe_remove_back_spare(bool __keep_one = true) {
       if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) {
-        __alloc_traits::deallocate(__base::__alloc(), __base::__map_.back(),
-                                   __base::__block_size);
-        __base::__map_.pop_back();
+        __alloc_traits::deallocate(__alloc(), __map_.back(),
+                                   __block_size);
+        __map_.pop_back();
         return true;
       }
       return false;
     }
 
     template <class _InpIter>
         void __append(_InpIter __f, _InpIter __l,
                  typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type* = 0);
private:
     _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())
+            if (__alloc() != __c.__alloc())
             {
                 clear();
                 shrink_to_fit();
             }
-            __base::__alloc() = __c.__alloc();
-            __base::__map_.__alloc() = __c.__map_.__alloc();
+            __alloc() = __c.__alloc();
+            __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 _Alloc>
+_LIBCPP_CONSTEXPR const typename allocator_traits<_Alloc>::difference_type deque<_Tp, _Alloc>::__block_size =
+    __deque_block_size<value_type, difference_type>::value;
+
 #if _LIBCPP_STD_VER >= 17
 template<class _InputIterator,
          class _Alloc = allocator<__iter_value_type<_InputIterator>>,
          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
          class = enable_if_t<__is_allocator<_Alloc>::value>
          >
 deque(_InputIterator, _InputIterator)
   -> deque<__iter_value_type<_InputIterator>, _Alloc>;
 
 template<class _InputIterator,
          class _Alloc,
          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
          class = enable_if_t<__is_allocator<_Alloc>::value>
          >
 deque(_InputIterator, _InputIterator, _Alloc)
   -> deque<__iter_value_type<_InputIterator>, _Alloc>;
 #endif
 
 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>::deque(size_type __n)
+    : __start_(0), __size_(0, __default_init_tag())
 {
     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)
+    : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
 {
     if (__n > 0)
         __append(__n);
 }
 #endif
 
 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)
+    : __start_(0), __size_(0, __default_init_tag())
 {
     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_cpp17_input_iterator<_InputIter>::value>::type*)
+    : __start_(0), __size_(0, __default_init_tag())
 {
     __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_cpp17_input_iterator<_InputIter>::value>::type*)
-    : __base(__a)
+    : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __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()))
+    : __map_(__pointer_allocator(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))),
+      __start_(0),
+      __size_(0, __map_.__alloc())
 {
     __append(__c.begin(), __c.end());
 }
 
 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>::deque(const deque& __c, const __type_identity_t<allocator_type>& __a)
-    : __base(__a)
+    : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
 {
     __append(__c.begin(), __c.end());
 }
 
 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>&
 deque<_Tp, _Allocator>::operator=(const deque& __c)
 {
     if (this != _VSTD::addressof(__c))
     {
         __copy_assign_alloc(__c);
         assign(__c.begin(), __c.end());
     }
     return *this;
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)
+    : __start_(0), __size_(0, __default_init_tag())
 {
     __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)
+    : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
 {
     __append(__il.begin(), __il.end());
 }
 
 template <class _Tp, class _Allocator>
 inline
 deque<_Tp, _Allocator>::deque(deque&& __c)
-    _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
-    : __base(_VSTD::move(__c))
+    _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
+    : __map_(std::move(__c.__map_)), __start_(std::move(__c.__start_)), __size_(std::move(__c.__size_))
 {
+  __c.__start_ = 0;
+  __c.__size() = 0;
 }
 
 template <class _Tp, class _Allocator>
 inline
 deque<_Tp, _Allocator>::deque(deque&& __c, const __type_identity_t<allocator_type>& __a)
-    : __base(_VSTD::move(__c), __a)
+    : __map_(std::move(__c.__map_), __pointer_allocator(__a)),
+      __start_(std::move(__c.__start_)),
+      __size_(std::move(__c.__size()), __a)
 {
-    if (__a != __c.__alloc())
+    if (__a == __c.__alloc())
+    {
+        __c.__start_ = 0;
+        __c.__size() = 0;
+    }
+    else
     {
+        __map_.clear();
+        __start_ = 0;
+        __size() = 0;
         typedef move_iterator<iterator> _Ip;
         assign(_Ip(__c.begin()), _Ip(__c.end()));
     }
 }
 
 template <class _Tp, class _Allocator>
 inline
 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())
+    if (__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);
+    __move_assign(__c);
 }
 
 #endif // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Allocator>
 template <class _InputIter>
 void
 deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
                                typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
                                                  !__is_cpp17_random_access_iterator<_InputIter>::value>::type*)
 {
-    iterator __i = __base::begin();
-    iterator __e = __base::end();
+    iterator __i = begin();
+    iterator __e = 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>
 template <class _RAIter>
 void
 deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
                                typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
 {
-    if (static_cast<size_type>(__l - __f) > __base::size())
+    if (static_cast<size_type>(__l - __f) > size())
     {
-        _RAIter __m = __f + __base::size();
-        _VSTD::copy(__f, __m, __base::begin());
+        _RAIter __m = __f + size();
+        _VSTD::copy(__f, __m, begin());
         __append(__m, __l);
     }
     else
-        __erase_to_end(_VSTD::copy(__f, __l, __base::begin()));
+        __erase_to_end(_VSTD::copy(__f, __l, begin()));
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
 {
-    if (__n > __base::size())
+    if (__n > size())
     {
-        _VSTD::fill_n(__base::begin(), __base::size(), __v);
-        __n -= __base::size();
+        _VSTD::fill_n(begin(), size(), __v);
+        __n -= size();
         __append(__n, __v);
     }
     else
-        __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v));
+        __erase_to_end(_VSTD::fill_n(begin(), __n, __v));
 }
 
 template <class _Tp, class _Allocator>
 inline
 _Allocator
 deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
 {
-    return __base::__alloc();
+    return __alloc();
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::resize(size_type __n)
 {
-    if (__n > __base::size())
-        __append(__n - __base::size());
-    else if (__n < __base::size())
-        __erase_to_end(__base::begin() + __n);
+    if (__n > size())
+        __append(__n - size());
+    else if (__n < size())
+        __erase_to_end(begin() + __n);
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v)
 {
-    if (__n > __base::size())
-        __append(__n - __base::size(), __v);
-    else if (__n < __base::size())
-        __erase_to_end(__base::begin() + __n);
+    if (__n > size())
+        __append(__n - size(), __v);
+    else if (__n < size())
+        __erase_to_end(begin() + __n);
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     if (empty())
     {
-        while (__base::__map_.size() > 0)
+        while (__map_.size() > 0)
         {
-            __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
-            __base::__map_.pop_back();
+            __alloc_traits::deallocate(__a, __map_.back(), __block_size);
+            __map_.pop_back();
         }
-        __base::__start_ = 0;
+        __start_ = 0;
     }
     else
     {
       __maybe_remove_front_spare(/*__keep_one=*/false);
       __maybe_remove_back_spare(/*__keep_one=*/false);
     }
-    __base::__map_.shrink_to_fit();
+    __map_.shrink_to_fit();
 }
 
 template <class _Tp, class _Allocator>
 inline
 typename deque<_Tp, _Allocator>::reference
 deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT
 {
-    size_type __p = __base::__start_ + __i;
-    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
+    size_type __p = __start_ + __i;
+    return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
 }
 
 template <class _Tp, class _Allocator>
 inline
 typename deque<_Tp, _Allocator>::const_reference
 deque<_Tp, _Allocator>::operator[](size_type __i) const _NOEXCEPT
 {
-    size_type __p = __base::__start_ + __i;
-    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
+    size_type __p = __start_ + __i;
+    return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
 }
 
 template <class _Tp, class _Allocator>
 inline
 typename deque<_Tp, _Allocator>::reference
 deque<_Tp, _Allocator>::at(size_type __i)
 {
-    if (__i >= __base::size())
+    if (__i >= size())
         _VSTD::__throw_out_of_range("deque");
-    size_type __p = __base::__start_ + __i;
-    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
+    size_type __p = __start_ + __i;
+    return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
 }
 
 template <class _Tp, class _Allocator>
 inline
 typename deque<_Tp, _Allocator>::const_reference
 deque<_Tp, _Allocator>::at(size_type __i) const
 {
-    if (__i >= __base::size())
+    if (__i >= size())
         _VSTD::__throw_out_of_range("deque");
-    size_type __p = __base::__start_ + __i;
-    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
+    size_type __p = __start_ + __i;
+    return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
 }
 
 template <class _Tp, class _Allocator>
 inline
 typename deque<_Tp, _Allocator>::reference
 deque<_Tp, _Allocator>::front() _NOEXCEPT
 {
-    return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
-                                      + __base::__start_ % __base::__block_size);
+    return *(*(__map_.begin() + __start_ / __block_size)
+                                    + __start_ % __block_size);
 }
 
 template <class _Tp, class _Allocator>
 inline
 typename deque<_Tp, _Allocator>::const_reference
 deque<_Tp, _Allocator>::front() const _NOEXCEPT
 {
-    return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
-                                      + __base::__start_ % __base::__block_size);
+    return *(*(__map_.begin() + __start_ / __block_size)
+                                      + __start_ % __block_size);
 }
 
 template <class _Tp, class _Allocator>
 inline
 typename deque<_Tp, _Allocator>::reference
 deque<_Tp, _Allocator>::back() _NOEXCEPT
 {
-    size_type __p = __base::size() + __base::__start_ - 1;
-    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
+    size_type __p = size() + __start_ - 1;
+    return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
 }
 
 template <class _Tp, class _Allocator>
 inline
 typename deque<_Tp, _Allocator>::const_reference
 deque<_Tp, _Allocator>::back() const _NOEXCEPT
 {
-    size_type __p = __base::size() + __base::__start_ - 1;
-    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
+    size_type __p = size() + __start_ - 1;
+    return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::push_back(const value_type& __v)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     if (__back_spare() == 0)
         __add_back_capacity();
     // __back_spare() >= 1
-    __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
-    ++__base::size();
+    __alloc_traits::construct(__a, _VSTD::addressof(*end()), __v);
+    ++__size();
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::push_front(const value_type& __v)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     if (__front_spare() == 0)
         __add_front_capacity();
     // __front_spare() >= 1
-    __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
-    --__base::__start_;
-    ++__base::size();
+    __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), __v);
+    --__start_;
+    ++__size();
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::push_back(value_type&& __v)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     if (__back_spare() == 0)
         __add_back_capacity();
     // __back_spare() >= 1
-    __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
-    ++__base::size();
+    __alloc_traits::construct(__a, _VSTD::addressof(*end()), _VSTD::move(__v));
+    ++__size();
 }
 
 template <class _Tp, class _Allocator>
 template <class... _Args>
 #if _LIBCPP_STD_VER > 14
 typename deque<_Tp, _Allocator>::reference
 #else
 void
 #endif
 deque<_Tp, _Allocator>::emplace_back(_Args&&... __args)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     if (__back_spare() == 0)
         __add_back_capacity();
     // __back_spare() >= 1
-    __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()),
+    __alloc_traits::construct(__a, _VSTD::addressof(*end()),
                               _VSTD::forward<_Args>(__args)...);
-    ++__base::size();
+    ++__size();
 #if _LIBCPP_STD_VER > 14
-    return *--__base::end();
+    return *--end();
 #endif
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::push_front(value_type&& __v)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     if (__front_spare() == 0)
         __add_front_capacity();
     // __front_spare() >= 1
-    __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
-    --__base::__start_;
-    ++__base::size();
+    __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), _VSTD::move(__v));
+    --__start_;
+    ++__size();
 }
 
 
 template <class _Tp, class _Allocator>
 template <class... _Args>
 #if _LIBCPP_STD_VER > 14
 typename deque<_Tp, _Allocator>::reference
 #else
 void
 #endif
 deque<_Tp, _Allocator>::emplace_front(_Args&&... __args)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     if (__front_spare() == 0)
         __add_front_capacity();
     // __front_spare() >= 1
-    __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
-    --__base::__start_;
-    ++__base::size();
+    __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), _VSTD::forward<_Args>(__args)...);
+    --__start_;
+    ++__size();
 #if _LIBCPP_STD_VER > 14
-    return *__base::begin();
+    return *begin();
 #endif
 }
 
 template <class _Tp, class _Allocator>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v)
 {
-    size_type __pos = __p - __base::begin();
-    size_type __to_end = __base::size() - __pos;
-    allocator_type& __a = __base::__alloc();
+    size_type __pos = __p - begin();
+    size_type __to_end = size() - __pos;
+    allocator_type& __a = __alloc();
     if (__pos < __to_end)
     {   // insert by shifting things backward
         if (__front_spare() == 0)
             __add_front_capacity();
         // __front_spare() >= 1
         if (__pos == 0)
         {
-            __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
-            --__base::__start_;
-            ++__base::size();
+            __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), _VSTD::move(__v));
+            --__start_;
+            ++__size();
         }
         else
         {
-            iterator __b = __base::begin();
+            iterator __b = begin();
             iterator __bm1 = _VSTD::prev(__b);
             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
-            --__base::__start_;
-            ++__base::size();
+            --__start_;
+            ++__size();
             if (__pos > 1)
                 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
             *__b = _VSTD::move(__v);
         }
     }
     else
     {   // insert by shifting things forward
         if (__back_spare() == 0)
             __add_back_capacity();
         // __back_capacity >= 1
-        size_type __de = __base::size() - __pos;
+        size_type __de = size() - __pos;
         if (__de == 0)
         {
-            __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
-            ++__base::size();
+            __alloc_traits::construct(__a, _VSTD::addressof(*end()), _VSTD::move(__v));
+            ++__size();
         }
         else
         {
-            iterator __e = __base::end();
+            iterator __e = end();
             iterator __em1 = _VSTD::prev(__e);
             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
-            ++__base::size();
+            ++__size();
             if (__de > 1)
                 __e = _VSTD::move_backward(__e - __de, __em1, __e);
             *--__e = _VSTD::move(__v);
         }
     }
-    return __base::begin() + __pos;
+    return begin() + __pos;
 }
 
 template <class _Tp, class _Allocator>
 template <class... _Args>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args)
 {
-    size_type __pos = __p - __base::begin();
-    size_type __to_end = __base::size() - __pos;
-    allocator_type& __a = __base::__alloc();
+    size_type __pos = __p - begin();
+    size_type __to_end = size() - __pos;
+    allocator_type& __a = __alloc();
     if (__pos < __to_end)
     {   // insert by shifting things backward
         if (__front_spare() == 0)
             __add_front_capacity();
         // __front_spare() >= 1
         if (__pos == 0)
         {
-            __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
-            --__base::__start_;
-            ++__base::size();
+            __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), _VSTD::forward<_Args>(__args)...);
+            --__start_;
+            ++__size();
         }
         else
         {
-            __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
-            iterator __b = __base::begin();
+            __temp_value<value_type, _Allocator> __tmp(__alloc(), _VSTD::forward<_Args>(__args)...);
+            iterator __b = begin();
             iterator __bm1 = _VSTD::prev(__b);
             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
-            --__base::__start_;
-            ++__base::size();
+            --__start_;
+            ++__size();
             if (__pos > 1)
                 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
             *__b = _VSTD::move(__tmp.get());
         }
     }
     else
     {   // insert by shifting things forward
         if (__back_spare() == 0)
             __add_back_capacity();
         // __back_capacity >= 1
-        size_type __de = __base::size() - __pos;
+        size_type __de = size() - __pos;
         if (__de == 0)
         {
-            __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
-            ++__base::size();
+            __alloc_traits::construct(__a, _VSTD::addressof(*end()), _VSTD::forward<_Args>(__args)...);
+            ++__size();
         }
         else
         {
-            __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
-            iterator __e = __base::end();
+            __temp_value<value_type, _Allocator> __tmp(__alloc(), _VSTD::forward<_Args>(__args)...);
+            iterator __e = end();
             iterator __em1 = _VSTD::prev(__e);
             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
-            ++__base::size();
+            ++__size();
             if (__de > 1)
                 __e = _VSTD::move_backward(__e - __de, __em1, __e);
             *--__e = _VSTD::move(__tmp.get());
         }
     }
-    return __base::begin() + __pos;
+    return begin() + __pos;
 }
 
 #endif // _LIBCPP_CXX03_LANG
 
 
 template <class _Tp, class _Allocator>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v)
 {
-    size_type __pos = __p - __base::begin();
-    size_type __to_end = __base::size() - __pos;
-    allocator_type& __a = __base::__alloc();
+    size_type __pos = __p - begin();
+    size_type __to_end = size() - __pos;
+    allocator_type& __a = __alloc();
     if (__pos < __to_end)
     {   // insert by shifting things backward
         if (__front_spare() == 0)
             __add_front_capacity();
         // __front_spare() >= 1
         if (__pos == 0)
         {
-            __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
-            --__base::__start_;
-            ++__base::size();
+            __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), __v);
+            --__start_;
+            ++__size();
         }
         else
         {
             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
-            iterator __b = __base::begin();
+            iterator __b = begin();
             iterator __bm1 = _VSTD::prev(__b);
             if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))
                 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);
             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
-            --__base::__start_;
-            ++__base::size();
+            --__start_;
+            ++__size();
             if (__pos > 1)
                 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt);
             *__b = *__vt;
         }
     }
     else
     {   // insert by shifting things forward
         if (__back_spare() == 0)
             __add_back_capacity();
         // __back_capacity >= 1
-        size_type __de = __base::size() - __pos;
+        size_type __de = size() - __pos;
         if (__de == 0)
         {
-            __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
-            ++__base::size();
+            __alloc_traits::construct(__a, _VSTD::addressof(*end()), __v);
+            ++__size();
         }
         else
         {
             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
-            iterator __e = __base::end();
+            iterator __e = end();
             iterator __em1 = _VSTD::prev(__e);
             if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))
                 __vt = pointer_traits<const_pointer>::pointer_to(*__e);
             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
-            ++__base::size();
+            ++__size();
             if (__de > 1)
                 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);
             *--__e = *__vt;
         }
     }
-    return __base::begin() + __pos;
+    return begin() + __pos;
 }
 
 template <class _Tp, class _Allocator>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v)
 {
-    size_type __pos = __p - __base::begin();
-    size_type __to_end = __base::size() - __pos;
-    allocator_type& __a = __base::__alloc();
+    size_type __pos = __p - begin();
+    size_type __to_end = __size() - __pos;
+    allocator_type& __a = __alloc();
     if (__pos < __to_end)
     {   // insert by shifting things backward
         if (__n > __front_spare())
             __add_front_capacity(__n - __front_spare());
         // __n <= __front_spare()
-        iterator __old_begin = __base::begin();
+        iterator __old_begin = begin();
         iterator __i = __old_begin;
         if (__n > __pos)
         {
-            for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size())
+            for (size_type __m = __n - __pos; __m; --__m, --__start_, ++__size())
                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v);
             __n = __pos;
         }
         if (__n > 0)
         {
             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
             iterator __obn = __old_begin + __n;
             __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);
             if (__n < __pos)
                 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);
             _VSTD::fill_n(__old_begin, __n, *__vt);
         }
     }
     else
     {   // insert by shifting things forward
         size_type __back_capacity = __back_spare();
         if (__n > __back_capacity)
             __add_back_capacity(__n - __back_capacity);
         // __n <= __back_capacity
-        iterator __old_end = __base::end();
+        iterator __old_end = end();
         iterator __i = __old_end;
-        size_type __de = __base::size() - __pos;
+        size_type __de = size() - __pos;
         if (__n > __de)
         {
-            for (size_type __m = __n - __de; __m; --__m, (void) ++__i, ++__base::size())
+            for (size_type __m = __n - __de; __m; --__m, (void) ++__i, ++__size())
                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
             __n = __de;
         }
         if (__n > 0)
         {
             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
             iterator __oen = __old_end - __n;
             __move_construct_and_check(__oen, __old_end, __i, __vt);
             if (__n < __de)
                 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);
             _VSTD::fill_n(__old_end - __n, __n, *__vt);
         }
     }
-    return __base::begin() + __pos;
+    return begin() + __pos;
 }
 
 template <class _Tp, class _Allocator>
 template <class _InputIter>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
                                typename enable_if<__is_exactly_cpp17_input_iterator<_InputIter>::value>::type*)
 {
-    __split_buffer<value_type, allocator_type&> __buf(__base::__alloc());
+    __split_buffer<value_type, allocator_type&> __buf(__alloc());
     __buf.__construct_at_end(__f, __l);
     typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
     return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
 }
 
 template <class _Tp, class _Allocator>
 template <class _ForwardIterator>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
                                typename enable_if<__is_exactly_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
 {
     size_type __n = _VSTD::distance(__f, __l);
-    __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc());
+    __split_buffer<value_type, allocator_type&> __buf(__n, 0, __alloc());
     __buf.__construct_at_end(__f, __l);
     typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
     return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
 }
 
 template <class _Tp, class _Allocator>
 template <class _BiIter>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
                                typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type*)
 {
     size_type __n = _VSTD::distance(__f, __l);
-    size_type __pos = __p - __base::begin();
-    size_type __to_end = __base::size() - __pos;
-    allocator_type& __a = __base::__alloc();
+    size_type __pos = __p - begin();
+    size_type __to_end = size() - __pos;
+    allocator_type& __a = __alloc();
     if (__pos < __to_end)
     {   // insert by shifting things backward
         if (__n > __front_spare())
             __add_front_capacity(__n - __front_spare());
         // __n <= __front_spare()
-        iterator __old_begin = __base::begin();
+        iterator __old_begin = begin();
         iterator __i = __old_begin;
         _BiIter __m = __f;
         if (__n > __pos)
         {
             __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
-            for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size())
+            for (_BiIter __j = __m; __j != __f; --__start_, ++__size())
                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
             __n = __pos;
         }
         if (__n > 0)
         {
             iterator __obn = __old_begin + __n;
             for (iterator __j = __obn; __j != __old_begin;)
             {
                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
-                --__base::__start_;
-                ++__base::size();
+                --__start_;
+                ++__size();
             }
             if (__n < __pos)
                 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
             _VSTD::copy(__m, __l, __old_begin);
         }
     }
     else
     {   // insert by shifting things forward
         size_type __back_capacity = __back_spare();
         if (__n > __back_capacity)
             __add_back_capacity(__n - __back_capacity);
         // __n <= __back_capacity
-        iterator __old_end = __base::end();
+        iterator __old_end = end();
         iterator __i = __old_end;
         _BiIter __m = __l;
-        size_type __de = __base::size() - __pos;
+        size_type __de = size() - __pos;
         if (__n > __de)
         {
             __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
-            for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
+            for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__size())
                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
             __n = __de;
         }
         if (__n > 0)
         {
             iterator __oen = __old_end - __n;
-            for (iterator __j = __oen; __j != __old_end; ++__i, (void) ++__j, ++__base::size())
+            for (iterator __j = __oen; __j != __old_end; ++__i, (void) ++__j, ++__size())
                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
             if (__n < __de)
                 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
             _VSTD::copy_backward(__f, __m, __old_end);
         }
     }
-    return __base::begin() + __pos;
+    return begin() + __pos;
 }
 
 template <class _Tp, class _Allocator>
 template <class _InpIter>
 void
 deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
                                  typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type*)
 {
     for (; __f != __l; ++__f)
 #ifdef _LIBCPP_CXX03_LANG
         push_back(*__f);
 #else
         emplace_back(*__f);
 #endif
 }
 
 template <class _Tp, class _Allocator>
 template <class _ForIter>
 void
 deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
                                  typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type*)
 {
     size_type __n = _VSTD::distance(__f, __l);
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     size_type __back_capacity = __back_spare();
     if (__n > __back_capacity)
         __add_back_capacity(__n - __back_capacity);
     // __n <= __back_capacity
-    for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
+    for (__deque_block_range __br : __deque_range(end(), end() + __n)) {
       _ConstructTransaction __tx(this, __br);
       for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) {
         __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), *__f);
       }
     }
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__append(size_type __n)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     size_type __back_capacity = __back_spare();
     if (__n > __back_capacity)
         __add_back_capacity(__n - __back_capacity);
     // __n <= __back_capacity
-    for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
+    for (__deque_block_range __br : __deque_range(end(), end() + __n)) {
       _ConstructTransaction __tx(this, __br);
       for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
         __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_));
       }
     }
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     size_type __back_capacity = __back_spare();
     if (__n > __back_capacity)
         __add_back_capacity(__n - __back_capacity);
     // __n <= __back_capacity
-    for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
+    for (__deque_block_range __br : __deque_range(end(), end() + __n)) {
       _ConstructTransaction __tx(this, __br);
       for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
         __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), __v);
       }
     }
 
 }
 
 // Create front capacity for one block of elements.
 // Strong guarantee.  Either do it or don't touch anything.
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__add_front_capacity()
 {
-    allocator_type& __a = __base::__alloc();
-    if (__back_spare() >= __base::__block_size)
+    allocator_type& __a = __alloc();
+    if (__back_spare() >= __block_size)
     {
-        __base::__start_ += __base::__block_size;
-        pointer __pt = __base::__map_.back();
-        __base::__map_.pop_back();
-        __base::__map_.push_front(__pt);
+        __start_ += __block_size;
+        pointer __pt = __map_.back();
+        __map_.pop_back();
+        __map_.push_front(__pt);
     }
-    // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer
-    else if (__base::__map_.size() < __base::__map_.capacity())
+    // Else if __map_.size() < __map_.capacity() then we need to allocate 1 buffer
+    else if (__map_.size() < __map_.capacity())
     {   // we can put the new buffer into the map, but don't shift things around
         // until all buffers are allocated.  If we throw, we don't need to fix
         // anything up (any added buffers are undetectible)
-        if (__base::__map_.__front_spare() > 0)
-            __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
+        if (__map_.__front_spare() > 0)
+            __map_.push_front(__alloc_traits::allocate(__a, __block_size));
         else
         {
-            __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
+            __map_.push_back(__alloc_traits::allocate(__a, __block_size));
             // Done allocating, reorder capacity
-            pointer __pt = __base::__map_.back();
-            __base::__map_.pop_back();
-            __base::__map_.push_front(__pt);
-        }
-        __base::__start_ = __base::__map_.size() == 1 ?
-                               __base::__block_size / 2 :
-                               __base::__start_ + __base::__block_size;
+            pointer __pt = __map_.back();
+            __map_.pop_back();
+            __map_.push_front(__pt);
+        }
+        __start_ = __map_.size() == 1 ?
+                               __block_size / 2 :
+                               __start_ + __block_size;
     }
     // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
     else
     {
-        __split_buffer<pointer, typename __base::__pointer_allocator&>
-            __buf(max<size_type>(2 * __base::__map_.capacity(), 1),
-                  0, __base::__map_.__alloc());
+        __split_buffer<pointer, __pointer_allocator&>
+            __buf(max<size_type>(2 * __map_.capacity(), 1),
+                  0, __map_.__alloc());
 
         typedef __allocator_destructor<_Allocator> _Dp;
         unique_ptr<pointer, _Dp> __hold(
-            __alloc_traits::allocate(__a, __base::__block_size),
-                _Dp(__a, __base::__block_size));
+            __alloc_traits::allocate(__a, __block_size),
+                _Dp(__a, __block_size));
         __buf.push_back(__hold.get());
         __hold.release();
 
-        for (typename __base::__map_pointer __i = __base::__map_.begin();
-                __i != __base::__map_.end(); ++__i)
+        for (__map_pointer __i = __map_.begin();
+                __i != __map_.end(); ++__i)
             __buf.push_back(*__i);
-        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
-        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
-        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
-        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
-        __base::__start_ = __base::__map_.size() == 1 ?
-                               __base::__block_size / 2 :
-                               __base::__start_ + __base::__block_size;
+        _VSTD::swap(__map_.__first_, __buf.__first_);
+        _VSTD::swap(__map_.__begin_, __buf.__begin_);
+        _VSTD::swap(__map_.__end_, __buf.__end_);
+        _VSTD::swap(__map_.__end_cap(), __buf.__end_cap());
+        __start_ = __map_.size() == 1 ?
+                               __block_size / 2 :
+                               __start_ + __block_size;
     }
 }
 
 // Create front capacity for __n elements.
 // Strong guarantee.  Either do it or don't touch anything.
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__add_front_capacity(size_type __n)
 {
-    allocator_type& __a = __base::__alloc();
-    size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
+    allocator_type& __a = __alloc();
+    size_type __nb = __recommend_blocks(__n + __map_.empty());
     // Number of unused blocks at back:
-    size_type __back_capacity = __back_spare() / __base::__block_size;
+    size_type __back_capacity = __back_spare() / __block_size;
     __back_capacity = _VSTD::min(__back_capacity, __nb);  // don't take more than you need
     __nb -= __back_capacity;  // number of blocks need to allocate
     // If __nb == 0, then we have sufficient capacity.
     if (__nb == 0)
     {
-        __base::__start_ += __base::__block_size * __back_capacity;
+        __start_ += __block_size * __back_capacity;
         for (; __back_capacity > 0; --__back_capacity)
         {
-            pointer __pt = __base::__map_.back();
-            __base::__map_.pop_back();
-            __base::__map_.push_front(__pt);
+            pointer __pt = __map_.back();
+            __map_.pop_back();
+            __map_.push_front(__pt);
         }
     }
     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
-    else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
+    else if (__nb <= __map_.capacity() - __map_.size())
     {   // we can put the new buffers into the map, but don't shift things around
         // until all buffers are allocated.  If we throw, we don't need to fix
         // anything up (any added buffers are undetectible)
-        for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1))
+        for (; __nb > 0; --__nb, __start_ += __block_size - (__map_.size() == 1))
         {
-            if (__base::__map_.__front_spare() == 0)
+            if (__map_.__front_spare() == 0)
                 break;
-            __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
+            __map_.push_front(__alloc_traits::allocate(__a, __block_size));
         }
         for (; __nb > 0; --__nb, ++__back_capacity)
-            __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
+            __map_.push_back(__alloc_traits::allocate(__a, __block_size));
         // Done allocating, reorder capacity
-        __base::__start_ += __back_capacity * __base::__block_size;
+        __start_ += __back_capacity * __block_size;
         for (; __back_capacity > 0; --__back_capacity)
         {
-            pointer __pt = __base::__map_.back();
-            __base::__map_.pop_back();
-            __base::__map_.push_front(__pt);
+            pointer __pt = __map_.back();
+            __map_.pop_back();
+            __map_.push_front(__pt);
         }
     }
     // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
     else
     {
-        size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty();
-        __split_buffer<pointer, typename __base::__pointer_allocator&>
-            __buf(max<size_type>(2* __base::__map_.capacity(),
-                                 __nb + __base::__map_.size()),
-                  0, __base::__map_.__alloc());
+        size_type __ds = (__nb + __back_capacity) * __block_size - __map_.empty();
+        __split_buffer<pointer, __pointer_allocator&>
+            __buf(max<size_type>(2* __map_.capacity(),
+                                 __nb + __map_.size()),
+                  0, __map_.__alloc());
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif // _LIBCPP_NO_EXCEPTIONS
             for (; __nb > 0; --__nb)
-                __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
+                __buf.push_back(__alloc_traits::allocate(__a, __block_size));
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
-            for (typename __base::__map_pointer __i = __buf.begin();
+            for (__map_pointer __i = __buf.begin();
                     __i != __buf.end(); ++__i)
-                __alloc_traits::deallocate(__a, *__i, __base::__block_size);
+                __alloc_traits::deallocate(__a, *__i, __block_size);
             throw;
         }
 #endif // _LIBCPP_NO_EXCEPTIONS
         for (; __back_capacity > 0; --__back_capacity)
         {
-            __buf.push_back(__base::__map_.back());
-            __base::__map_.pop_back();
+            __buf.push_back(__map_.back());
+            __map_.pop_back();
         }
-        for (typename __base::__map_pointer __i = __base::__map_.begin();
-                __i != __base::__map_.end(); ++__i)
+        for (__map_pointer __i = __map_.begin();
+                __i != __map_.end(); ++__i)
             __buf.push_back(*__i);
-        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
-        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
-        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
-        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
-        __base::__start_ += __ds;
+        _VSTD::swap(__map_.__first_, __buf.__first_);
+        _VSTD::swap(__map_.__begin_, __buf.__begin_);
+        _VSTD::swap(__map_.__end_, __buf.__end_);
+        _VSTD::swap(__map_.__end_cap(), __buf.__end_cap());
+        __start_ += __ds;
     }
 }
 
 // Create back capacity for one block of elements.
 // Strong guarantee.  Either do it or don't touch anything.
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__add_back_capacity()
 {
-    allocator_type& __a = __base::__alloc();
-    if (__front_spare() >= __base::__block_size)
+    allocator_type& __a = __alloc();
+    if (__front_spare() >= __block_size)
     {
-        __base::__start_ -= __base::__block_size;
-        pointer __pt = __base::__map_.front();
-        __base::__map_.pop_front();
-        __base::__map_.push_back(__pt);
+        __start_ -= __block_size;
+        pointer __pt = __map_.front();
+        __map_.pop_front();
+        __map_.push_back(__pt);
     }
     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
-    else if (__base::__map_.size() < __base::__map_.capacity())
+    else if (__map_.size() < __map_.capacity())
     {   // we can put the new buffer into the map, but don't shift things around
         // until it is allocated.  If we throw, we don't need to fix
         // anything up (any added buffers are undetectible)
-        if (__base::__map_.__back_spare() != 0)
-            __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
+        if (__map_.__back_spare() != 0)
+            __map_.push_back(__alloc_traits::allocate(__a, __block_size));
         else
         {
-            __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
+            __map_.push_front(__alloc_traits::allocate(__a, __block_size));
             // Done allocating, reorder capacity
-            pointer __pt = __base::__map_.front();
-            __base::__map_.pop_front();
-            __base::__map_.push_back(__pt);
+            pointer __pt = __map_.front();
+            __map_.pop_front();
+            __map_.push_back(__pt);
         }
     }
     // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
     else
     {
-        __split_buffer<pointer, typename __base::__pointer_allocator&>
-            __buf(max<size_type>(2* __base::__map_.capacity(), 1),
-                  __base::__map_.size(),
-                  __base::__map_.__alloc());
+        __split_buffer<pointer, __pointer_allocator&>
+            __buf(max<size_type>(2* __map_.capacity(), 1),
+                  __map_.size(),
+                  __map_.__alloc());
 
         typedef __allocator_destructor<_Allocator> _Dp;
         unique_ptr<pointer, _Dp> __hold(
-            __alloc_traits::allocate(__a, __base::__block_size),
-                _Dp(__a, __base::__block_size));
+            __alloc_traits::allocate(__a, __block_size),
+                _Dp(__a, __block_size));
         __buf.push_back(__hold.get());
         __hold.release();
 
-        for (typename __base::__map_pointer __i = __base::__map_.end();
-                __i != __base::__map_.begin();)
+        for (__map_pointer __i = __map_.end();
+                __i != __map_.begin();)
             __buf.push_front(*--__i);
-        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
-        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
-        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
-        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
+        _VSTD::swap(__map_.__first_, __buf.__first_);
+        _VSTD::swap(__map_.__begin_, __buf.__begin_);
+        _VSTD::swap(__map_.__end_, __buf.__end_);
+        _VSTD::swap(__map_.__end_cap(), __buf.__end_cap());
     }
 }
 
 // Create back capacity for __n elements.
 // Strong guarantee.  Either do it or don't touch anything.
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__add_back_capacity(size_type __n)
 {
-    allocator_type& __a = __base::__alloc();
-    size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
+    allocator_type& __a = __alloc();
+    size_type __nb = __recommend_blocks(__n + __map_.empty());
     // Number of unused blocks at front:
-    size_type __front_capacity = __front_spare() / __base::__block_size;
+    size_type __front_capacity = __front_spare() / __block_size;
     __front_capacity = _VSTD::min(__front_capacity, __nb);  // don't take more than you need
     __nb -= __front_capacity;  // number of blocks need to allocate
     // If __nb == 0, then we have sufficient capacity.
     if (__nb == 0)
     {
-        __base::__start_ -= __base::__block_size * __front_capacity;
+        __start_ -= __block_size * __front_capacity;
         for (; __front_capacity > 0; --__front_capacity)
         {
-            pointer __pt = __base::__map_.front();
-            __base::__map_.pop_front();
-            __base::__map_.push_back(__pt);
+            pointer __pt = __map_.front();
+            __map_.pop_front();
+            __map_.push_back(__pt);
         }
     }
     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
-    else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
+    else if (__nb <= __map_.capacity() - __map_.size())
     {   // we can put the new buffers into the map, but don't shift things around
         // until all buffers are allocated.  If we throw, we don't need to fix
         // anything up (any added buffers are undetectible)
         for (; __nb > 0; --__nb)
         {
-            if (__base::__map_.__back_spare() == 0)
+            if (__map_.__back_spare() == 0)
                 break;
-            __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
+            __map_.push_back(__alloc_traits::allocate(__a, __block_size));
         }
-        for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ +=
-                                 __base::__block_size - (__base::__map_.size() == 1))
-            __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
+        for (; __nb > 0; --__nb, ++__front_capacity, __start_ +=
+                                 __block_size - (__map_.size() == 1))
+            __map_.push_front(__alloc_traits::allocate(__a, __block_size));
         // Done allocating, reorder capacity
-        __base::__start_ -= __base::__block_size * __front_capacity;
+        __start_ -= __block_size * __front_capacity;
         for (; __front_capacity > 0; --__front_capacity)
         {
-            pointer __pt = __base::__map_.front();
-            __base::__map_.pop_front();
-            __base::__map_.push_back(__pt);
+            pointer __pt = __map_.front();
+            __map_.pop_front();
+            __map_.push_back(__pt);
         }
     }
     // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
     else
     {
-        size_type __ds = __front_capacity * __base::__block_size;
-        __split_buffer<pointer, typename __base::__pointer_allocator&>
-            __buf(max<size_type>(2* __base::__map_.capacity(),
-                                 __nb + __base::__map_.size()),
-                  __base::__map_.size() - __front_capacity,
-                  __base::__map_.__alloc());
+        size_type __ds = __front_capacity * __block_size;
+        __split_buffer<pointer, __pointer_allocator&>
+            __buf(max<size_type>(2* __map_.capacity(),
+                                 __nb + __map_.size()),
+                  __map_.size() - __front_capacity,
+                  __map_.__alloc());
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif // _LIBCPP_NO_EXCEPTIONS
             for (; __nb > 0; --__nb)
-                __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
+                __buf.push_back(__alloc_traits::allocate(__a, __block_size));
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
-            for (typename __base::__map_pointer __i = __buf.begin();
+            for (__map_pointer __i = __buf.begin();
                     __i != __buf.end(); ++__i)
-                __alloc_traits::deallocate(__a, *__i, __base::__block_size);
+                __alloc_traits::deallocate(__a, *__i, __block_size);
             throw;
         }
 #endif // _LIBCPP_NO_EXCEPTIONS
         for (; __front_capacity > 0; --__front_capacity)
         {
-            __buf.push_back(__base::__map_.front());
-            __base::__map_.pop_front();
+            __buf.push_back(__map_.front());
+            __map_.pop_front();
         }
-        for (typename __base::__map_pointer __i = __base::__map_.end();
-                __i != __base::__map_.begin();)
+        for (__map_pointer __i = __map_.end();
+                __i != __map_.begin();)
             __buf.push_front(*--__i);
-        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
-        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
-        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
-        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
-        __base::__start_ -= __ds;
+        _VSTD::swap(__map_.__first_, __buf.__first_);
+        _VSTD::swap(__map_.__begin_, __buf.__begin_);
+        _VSTD::swap(__map_.__end_, __buf.__end_);
+        _VSTD::swap(__map_.__end_cap(), __buf.__end_cap());
+        __start_ -= __ds;
     }
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::pop_front()
 {
-    allocator_type& __a = __base::__alloc();
-    __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() +
-                                                    __base::__start_ / __base::__block_size) +
-                                                    __base::__start_ % __base::__block_size));
-    --__base::size();
-    ++__base::__start_;
+    allocator_type& __a = __alloc();
+    __alloc_traits::destroy(__a, _VSTD::__to_address(*(__map_.begin() +
+                                                    __start_ / __block_size) +
+                                                    __start_ % __block_size));
+    --__size();
+    ++__start_;
     __maybe_remove_front_spare();
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::pop_back()
 {
     _LIBCPP_ASSERT(!empty(), "deque::pop_back called on an empty deque");
-    allocator_type& __a = __base::__alloc();
-    size_type __p = __base::size() + __base::__start_ - 1;
-    __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() +
-                                                    __p / __base::__block_size) +
-                                                    __p % __base::__block_size));
-    --__base::size();
+    allocator_type& __a = __alloc();
+    size_type __p = size() + __start_ - 1;
+    __alloc_traits::destroy(__a, _VSTD::__to_address(*(__map_.begin() +
+                                                    __p / __block_size) +
+                                                    __p % __block_size));
+    --__size();
     __maybe_remove_back_spare();
 }
 
 // move assign [__f, __l) to [__r, __r + (__l-__f)).
 // If __vt points into [__f, __l), then subtract (__f - __r) from __vt.
 template <class _Tp, class _Allocator>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r,
                                          const_pointer& __vt)
 {
     // as if
     //   for (; __f != __l; ++__f, ++__r)
     //       *__r = _VSTD::move(*__f);
     difference_type __n = __l - __f;
     while (__n > 0)
     {
         pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + __base::__block_size;
+        pointer __fe = *__f.__m_iter_ + __block_size;
         difference_type __bs = __fe - __fb;
         if (__bs > __n)
         {
             __bs = __n;
             __fe = __fb + __bs;
         }
         if (__fb <= __vt && __vt < __fe)
             __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;

 
 // move construct [__f, __l) to [__r, __r + (__l-__f)).
 // If __vt points into [__f, __l), then add (__r - __f) to __vt.
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l,
                                                    iterator __r, const_pointer& __vt)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     // as if
-    //   for (; __f != __l; ++__r, ++__f, ++__base::size())
+    //   for (; __f != __l; ++__r, ++__f, ++__size())
     //       __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f));
     difference_type __n = __l - __f;
     while (__n > 0)
     {
         pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + __base::__block_size;
+        pointer __fe = *__f.__m_iter_ + __block_size;
         difference_type __bs = __fe - __fb;
         if (__bs > __n)
         {
             __bs = __n;
             __fe = __fb + __bs;
         }
         if (__fb <= __vt && __vt < __fe)
             __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;
-        for (; __fb != __fe; ++__fb, ++__r, ++__base::size())
+        for (; __fb != __fe; ++__fb, ++__r, ++__size())
             __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb));
         __n -= __bs;
         __f += __bs;
     }
 }
 
 // move construct [__f, __l) to [__r - (__l-__f), __r) backwards.
 // If __vt points into [__f, __l), then subtract (__l - __r) from __vt.
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l,
                                                             iterator __r, const_pointer& __vt)
 {
-    allocator_type& __a = __base::__alloc();
+    allocator_type& __a = __alloc();
     // as if
     //   for (iterator __j = __l; __j != __f;)
     //   {
     //       __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j));
-    //       --__base::__start_;
-    //       ++__base::size();
+    //       --__start_;
+    //       ++__size();
     //   }
     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;
         }
         if (__lb <= __vt && __vt < __le)
             __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;
         while (__le != __lb)
         {
             __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le));
-            --__base::__start_;
-            ++__base::size();
+            --__start_;
+            ++__size();
         }
         __n -= __bs;
         __l -= __bs - 1;
     }
 }
 
 template <class _Tp, class _Allocator>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::erase(const_iterator __f)
 {
-    iterator __b = __base::begin();
+    iterator __b = begin();
     difference_type __pos = __f - __b;
     iterator __p = __b + __pos;
-    allocator_type& __a = __base::__alloc();
-    if (static_cast<size_t>(__pos) <= (__base::size() - 1) / 2)
+    allocator_type& __a = __alloc();
+    if (static_cast<size_t>(__pos) <= (size() - 1) / 2)
     {   // erase from front
         _VSTD::move_backward(__b, __p, _VSTD::next(__p));
         __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
-        --__base::size();
-        ++__base::__start_;
+        --__size();
+        ++__start_;
         __maybe_remove_front_spare();
     }
     else
     {   // erase from back
-        iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
+        iterator __i = _VSTD::move(_VSTD::next(__p), end(), __p);
         __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
-        --__base::size();
+        --__size();
         __maybe_remove_back_spare();
     }
-    return __base::begin() + __pos;
+    return begin() + __pos;
 }
 
 template <class _Tp, class _Allocator>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
 {
     difference_type __n = __l - __f;
-    iterator __b = __base::begin();
+    iterator __b = begin();
     difference_type __pos = __f - __b;
     iterator __p = __b + __pos;
     if (__n > 0)
     {
-        allocator_type& __a = __base::__alloc();
-        if (static_cast<size_t>(__pos) <= (__base::size() - __n) / 2)
+        allocator_type& __a = __alloc();
+        if (static_cast<size_t>(__pos) <= (size() - __n) / 2)
         {   // erase from front
             iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
             for (; __b != __i; ++__b)
                 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
-            __base::size() -= __n;
-            __base::__start_ += __n;
+            __size() -= __n;
+            __start_ += __n;
             while (__maybe_remove_front_spare()) {
             }
         }
         else
         {   // erase from back
-            iterator __i = _VSTD::move(__p + __n, __base::end(), __p);
-            for (iterator __e = __base::end(); __i != __e; ++__i)
+            iterator __i = _VSTD::move(__p + __n, end(), __p);
+            for (iterator __e = end(); __i != __e; ++__i)
                 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
-            __base::size() -= __n;
+            __size() -= __n;
             while (__maybe_remove_back_spare()) {
             }
         }
     }
-    return __base::begin() + __pos;
+    return begin() + __pos;
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
 {
-    iterator __e = __base::end();
+    iterator __e = end();
     difference_type __n = __e - __f;
     if (__n > 0)
     {
-        allocator_type& __a = __base::__alloc();
-        iterator __b = __base::begin();
+        allocator_type& __a = __alloc();
+        iterator __b = begin();
         difference_type __pos = __f - __b;
         for (iterator __p = __b + __pos; __p != __e; ++__p)
             __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
-        __base::size() -= __n;
+        __size() -= __n;
         while (__maybe_remove_back_spare()) {
         }
     }
 }
 
 template <class _Tp, class _Allocator>
 inline
 void
 deque<_Tp, _Allocator>::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
 {
-    __base::swap(__c);
+    __map_.swap(__c.__map_);
+    _VSTD::swap(__start_, __c.__start_);
+    _VSTD::swap(__size(), __c.__size());
+    _VSTD::__swap_allocator(__alloc(), __c.__alloc());
 }
 
 template <class _Tp, class _Allocator>
 inline
 void
 deque<_Tp, _Allocator>::clear() _NOEXCEPT
 {
-    __base::clear();
+    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>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
 {
     const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();

libcxx/test/std/containers/container.adaptors/queue/queue.cons/ctor_iterators.pass.cpp

 
 #include "test_allocator.h"
 
 static_assert(!std::is_constructible_v<std::queue<int>, int, int, std::allocator<int>>);
 static_assert(!std::is_constructible_v<std::queue<int>, int*, int*, int>);
 static_assert( std::is_constructible_v<std::queue<int, std::deque<int, test_allocator<int>>>, int*, int*, test_allocator<int>>);
 static_assert(!std::is_constructible_v<std::queue<int, std::deque<int, test_allocator<int>>>, int*, int*, std::allocator<int>>);
 
-struct alloc : test_allocator<int> {
+template <class T>
+struct alloc : test_allocator<T> {
   alloc(test_allocator_statistics* a);
+
+  template <class U>
+  struct rebind {
+    using other = alloc<U>;
+  };
 };
-static_assert( std::is_constructible_v<std::queue<int, std::deque<int, alloc>>, int*, int*, test_allocator_statistics*>);
+static_assert(
+    std::is_constructible_v<std::queue<int, std::deque<int, alloc<int>>>, int*, int*, test_allocator_statistics*>);
 
 int main(int, char**) {
   const int a[] = {4, 3, 2, 1};
   std::queue<int> queue(a, a + 4);
   assert(queue.front() == 4);
   queue.pop();
   assert(queue.front() == 3);
   queue.pop();
   assert(queue.front() == 2);
   queue.pop();
   assert(queue.front() == 1);
   queue.pop();
   assert(queue.empty());
 
   return 0;
 }

libcxx/test/std/containers/container.adaptors/stack/stack.cons/ctor_iterators.pass.cpp

 
 #include "test_allocator.h"
 
 static_assert(!std::is_constructible_v<std::stack<int>, int, int, std::allocator<int>>);
 static_assert(!std::is_constructible_v<std::stack<int>, int*, int*, int>);
 static_assert( std::is_constructible_v<std::stack<int, std::deque<int, test_allocator<int>>>, int*, int*, test_allocator<int>>);
 static_assert(!std::is_constructible_v<std::stack<int, std::deque<int, test_allocator<int>>>, int*, int*, std::allocator<int>>);
 
-struct alloc : test_allocator<int> {
+template <class T>
+struct alloc : test_allocator<T> {
+  template <class U>
+  struct rebind {
+    using other = alloc<U>;
+  };
   alloc(test_allocator_statistics* a);
 };
-static_assert( std::is_constructible_v<std::stack<int, std::deque<int, alloc>>, int*, int*, test_allocator_statistics*>);
+static_assert(
+    std::is_constructible_v<std::stack<int, std::deque<int, alloc<int>>>, int*, int*, test_allocator_statistics*>);
 
 int main(int, char**) {
   const int a[] = {4, 3, 2, 1};
   std::stack<int> stack(a, a + 4);
   assert(stack.top() == 1);
   stack.pop();
   assert(stack.top() == 2);
   stack.pop();
   assert(stack.top() == 3);
   stack.pop();
   assert(stack.top() == 4);
   stack.pop();
   assert(stack.empty());
 
   return 0;
 }

libcxx/test/std/containers/sequences/deque/abi.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <deque>
+
+#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
+
+template <class T>
+class small_pointer {
+  uint16_t offset;
+};
+
+template <class T>
+class small_iter_allocator {
+public:
+  using value_type      = T;
+  using pointer         = small_pointer<T>;
+  using size_type       = int16_t;
+  using difference_type = int16_t;
+
+  small_iter_allocator() TEST_NOEXCEPT {}
+
+  template <class U>
+  small_iter_allocator(small_iter_allocator<U>) TEST_NOEXCEPT {}
+
+  T* allocate(std::size_t n);
+  void deallocate(T* p, std::size_t);
+
+  friend bool operator==(small_iter_allocator, small_iter_allocator) { return true; }
+  friend bool operator!=(small_iter_allocator, small_iter_allocator) { return false; }
+};
+
+#if __SIZE_WIDTH__ == 64
+
+static_assert(sizeof(std::deque<int>) == 48, "");
+static_assert(sizeof(std::deque<int, min_allocator<int> >) == 48, "");
+static_assert(sizeof(std::deque<int, test_allocator<int> >) == 80, "");
+static_assert(sizeof(std::deque<int, small_iter_allocator<int> >) == 12, "");
+
+static_assert(sizeof(std::deque<char>) == 48, "");
+static_assert(sizeof(std::deque<char, min_allocator<char> >) == 48, "");
+static_assert(sizeof(std::deque<char, test_allocator<char> >) == 80, "");
+static_assert(sizeof(std::deque<char, small_iter_allocator<char> >) == 12, "");
+
+static_assert(TEST_ALIGNOF(std::deque<int>) == 8, "");
+static_assert(TEST_ALIGNOF(std::deque<int, min_allocator<int> >) == 8, "");
+static_assert(TEST_ALIGNOF(std::deque<int, test_allocator<int> >) == 8, "");
+static_assert(TEST_ALIGNOF(std::deque<int, small_iter_allocator<int> >) == 2, "");
+
+static_assert(TEST_ALIGNOF(std::deque<char>) == 8, "");
+static_assert(TEST_ALIGNOF(std::deque<char, min_allocator<char> >) == 8, "");
+static_assert(TEST_ALIGNOF(std::deque<char, test_allocator<char> >) == 8, "");
+static_assert(TEST_ALIGNOF(std::deque<char, small_iter_allocator<char> >) == 2, "");
+
+#elif __SIZE_WIDTH__ == 32
+
+static_assert(sizeof(std::deque<int>) == 24, "");
+static_assert(sizeof(std::deque<int, min_allocator<int> >) == 24, "");
+static_assert(sizeof(std::deque<int, test_allocator<int> >) == 48, "");
+static_assert(sizeof(std::deque<int, small_iter_allocator<int> >) == 12, "");
+
+static_assert(sizeof(std::deque<char>) == 24, "");
+static_assert(sizeof(std::deque<char, min_allocator<char> >) == 24, "");
+static_assert(sizeof(std::deque<char, test_allocator<char> >) == 48, "");
+static_assert(sizeof(std::deque<char, small_iter_allocator<char> >) == 12, "");
+
+static_assert(TEST_ALIGNOF(std::deque<int>) == 4, "");
+static_assert(TEST_ALIGNOF(std::deque<int, min_allocator<int> >) == 4, "");
+static_assert(TEST_ALIGNOF(std::deque<int, test_allocator<int> >) == 4, "");
+static_assert(TEST_ALIGNOF(std::deque<int, small_iter_allocator<int> >) == 2, "");
+
+static_assert(TEST_ALIGNOF(std::deque<char>) == 4, "");
+static_assert(TEST_ALIGNOF(std::deque<char, min_allocator<char> >) == 4, "");
+static_assert(TEST_ALIGNOF(std::deque<char, test_allocator<char> >) == 4, "");
+static_assert(TEST_ALIGNOF(std::deque<char, small_iter_allocator<char> >) == 2, "");
+
+#else
+#  error size_t has an unexpected size
+#endif