contrib/libc++/include/deque

   1 // -*- C++ -*-
   2 //===---------------------------- deque -----------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_DEQUE
  12 #define _LIBCPP_DEQUE
  13
  14 /*
  15     deque synopsis
  16
  17 namespace std
  18 {
  19
  20 template <class T, class Allocator = allocator<T> >
  21 class deque
  22 {
  23 public:
  24     // types:
  25     typedef T value_type;
  26     typedef Allocator allocator_type;
  27
  28     typedef typename allocator_type::reference       reference;
  29     typedef typename allocator_type::const_reference const_reference;
  30     typedef implementation-defined                   iterator;
  31     typedef implementation-defined                   const_iterator;
  32     typedef typename allocator_type::size_type       size_type;
  33     typedef typename allocator_type::difference_type difference_type;
  34
  35     typedef typename allocator_type::pointer         pointer;
  36     typedef typename allocator_type::const_pointer   const_pointer;
  37     typedef std::reverse_iterator<iterator>          reverse_iterator;
  38     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
  39
  40     // construct/copy/destroy:
  41     deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);
  42     explicit deque(const allocator_type& a);
  43     explicit deque(size_type n);
  44     explicit deque(size_type n, const allocator_type& a); // C++14
  45     deque(size_type n, const value_type& v);
  46     deque(size_type n, const value_type& v, const allocator_type& a);
  47     template <class InputIterator>
  48         deque(InputIterator f, InputIterator l);
  49     template <class InputIterator>
  50         deque(InputIterator f, InputIterator l, const allocator_type& a);
  51     deque(const deque& c);
  52     deque(deque&& c)
  53         noexcept(is_nothrow_move_constructible<allocator_type>::value);
  54     deque(initializer_list<value_type> il, const Allocator& a = allocator_type());
  55     deque(const deque& c, const allocator_type& a);
  56     deque(deque&& c, const allocator_type& a);
  57     ~deque();
  58
  59     deque& operator=(const deque& c);
  60     deque& operator=(deque&& c)
  61         noexcept(
  62              allocator_type::propagate_on_container_move_assignment::value &&
  63              is_nothrow_move_assignable<allocator_type>::value);
  64     deque& operator=(initializer_list<value_type> il);
  65
  66     template <class InputIterator>
  67         void assign(InputIterator f, InputIterator l);
  68     void assign(size_type n, const value_type& v);
  69     void assign(initializer_list<value_type> il);
  70
  71     allocator_type get_allocator() const noexcept;
  72
  73     // iterators:
  74
  75     iterator       begin() noexcept;
  76     const_iterator begin() const noexcept;
  77     iterator       end() noexcept;
  78     const_iterator end() const noexcept;
  79
  80     reverse_iterator       rbegin() noexcept;
  81     const_reverse_iterator rbegin() const noexcept;
  82     reverse_iterator       rend() noexcept;
  83     const_reverse_iterator rend() const noexcept;
  84
  85     const_iterator         cbegin() const noexcept;
  86     const_iterator         cend() const noexcept;
  87     const_reverse_iterator crbegin() const noexcept;
  88     const_reverse_iterator crend() const noexcept;
  89
  90     // capacity:
  91     size_type size() const noexcept;
  92     size_type max_size() const noexcept;
  93     void resize(size_type n);
  94     void resize(size_type n, const value_type& v);
  95     void shrink_to_fit();
  96     bool empty() const noexcept;
  97
  98     // element access:
  99     reference operator[](size_type i);
 100     const_reference operator[](size_type i) const;
 101     reference at(size_type i);
 102     const_reference at(size_type i) const;
 103     reference front();
 104     const_reference front() const;
 105     reference back();
 106     const_reference back() const;
 107
 108     // modifiers:
 109     void push_front(const value_type& v);
 110     void push_front(value_type&& v);
 111     void push_back(const value_type& v);
 112     void push_back(value_type&& v);
 113     template <class... Args> reference emplace_front(Args&&... args);  // reference in C++17
 114     template <class... Args> reference emplace_back(Args&&... args);   // reference in C++17
 115     template <class... Args> iterator emplace(const_iterator p, Args&&... args);
 116     iterator insert(const_iterator p, const value_type& v);
 117     iterator insert(const_iterator p, value_type&& v);
 118     iterator insert(const_iterator p, size_type n, const value_type& v);
 119     template <class InputIterator>
 120         iterator insert(const_iterator p, InputIterator f, InputIterator l);
 121     iterator insert(const_iterator p, initializer_list<value_type> il);
 122     void pop_front();
 123     void pop_back();
 124     iterator erase(const_iterator p);
 125     iterator erase(const_iterator f, const_iterator l);
 126     void swap(deque& c)
 127         noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
 128     void clear() noexcept;
 129 };
 130
 131 template <class T, class Allocator>
 132     bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
 133 template <class T, class Allocator>
 134     bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
 135 template <class T, class Allocator>
 136     bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
 137 template <class T, class Allocator>
 138     bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
 139 template <class T, class Allocator>
 140     bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
 141 template <class T, class Allocator>
 142     bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
 143
 144 // specialized algorithms:
 145 template <class T, class Allocator>
 146     void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)
 147          noexcept(noexcept(x.swap(y)));
 148
 149 }  // std
 150
 151 */
 152
 153 #include <__config>
 154 #include <__split_buffer>
 155 #include <type_traits>
 156 #include <initializer_list>
 157 #include <iterator>
 158 #include <algorithm>
 159 #include <stdexcept>
 160
 161 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 162 #pragma GCC system_header
 163 #endif
 164
 165 _LIBCPP_PUSH_MACROS
 166 #include <__undef_macros>
 167
 168
 169 _LIBCPP_BEGIN_NAMESPACE_STD
 170
 171 template <class _Tp, class _Allocator> class __deque_base;
 172 template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS deque;
 173
 174 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
 175           class _DiffType, _DiffType _BlockSize>
 176 class _LIBCPP_TEMPLATE_VIS __deque_iterator;
 177
 178 template <class _RAIter,
 179           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 180 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 181 copy(_RAIter __f,
 182      _RAIter __l,
 183      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 184      typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
 185
 186 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 187           class _OutputIterator>
 188 _OutputIterator
 189 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 190      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 191      _OutputIterator __r);
 192
 193 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 194           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 195 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 196 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 197      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 198      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 199
 200 template <class _RAIter,
 201           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 202 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 203 copy_backward(_RAIter __f,
 204               _RAIter __l,
 205               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 206               typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
 207
 208 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 209           class _OutputIterator>
 210 _OutputIterator
 211 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 212               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 213               _OutputIterator __r);
 214
 215 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 216           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 217 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 218 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 219               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 220               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 221
 222 template <class _RAIter,
 223           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 224 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 225 move(_RAIter __f,
 226      _RAIter __l,
 227      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 228      typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
 229
 230 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 231           class _OutputIterator>
 232 _OutputIterator
 233 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 234      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 235      _OutputIterator __r);
 236
 237 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 238           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 239 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 240 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 241      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 242      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 243
 244 template <class _RAIter,
 245           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 246 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 247 move_backward(_RAIter __f,
 248               _RAIter __l,
 249               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 250               typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
 251
 252 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 253           class _OutputIterator>
 254 _OutputIterator
 255 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 256               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 257               _OutputIterator __r);
 258
 259 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 260           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 261 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 262 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 263               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 264               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 265
 266 template <class _ValueType, class _DiffType>
 267 struct __deque_block_size {
 268   static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;
 269 };
 270
 271 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
 272           class _DiffType, _DiffType _BS =
 273 #ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
 274 // Keep template parameter to avoid changing all template declarations thoughout
 275 // this file.
 276                                0
 277 #else
 278                                __deque_block_size<_ValueType, _DiffType>::value
 279 #endif
 280           >
 281 class _LIBCPP_TEMPLATE_VIS __deque_iterator
 282 {
 283     typedef _MapPointer __map_iterator;
 284 public:
 285     typedef _Pointer  pointer;
 286     typedef _DiffType difference_type;
 287 private:
 288     __map_iterator __m_iter_;
 289     pointer        __ptr_;
 290
 291     static const difference_type __block_size;
 292 public:
 293     typedef _ValueType                  value_type;
 294     typedef random_access_iterator_tag  iterator_category;
 295     typedef _Reference                  reference;
 296
 297     _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT
 298 #if _LIBCPP_STD_VER > 11
 299      : __m_iter_(nullptr), __ptr_(nullptr)
 300 #endif
 301      {}
 302
 303     template <class _Pp, class _Rp, class _MP>
 304     _LIBCPP_INLINE_VISIBILITY
 305     __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it,
 306                 typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT
 307         : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}
 308
 309     _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;}
 310     _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;}
 311
 312     _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++()
 313     {
 314         if (++__ptr_ - *__m_iter_ == __block_size)
 315         {
 316             ++__m_iter_;
 317             __ptr_ = *__m_iter_;
 318         }
 319         return *this;
 320     }
 321
 322     _LIBCPP_INLINE_VISIBILITY __deque_iterator operator++(int)
 323     {
 324         __deque_iterator __tmp = *this;
 325         ++(*this);
 326         return __tmp;
 327     }
 328
 329     _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator--()
 330     {
 331         if (__ptr_ == *__m_iter_)
 332         {
 333             --__m_iter_;
 334             __ptr_ = *__m_iter_ + __block_size;
 335         }
 336         --__ptr_;
 337         return *this;
 338     }
 339
 340     _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int)
 341     {
 342         __deque_iterator __tmp = *this;
 343         --(*this);
 344         return __tmp;
 345     }
 346
 347     _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n)
 348     {
 349         if (__n != 0)
 350         {
 351             __n += __ptr_ - *__m_iter_;
 352             if (__n > 0)
 353             {
 354                 __m_iter_ += __n / __block_size;
 355                 __ptr_ = *__m_iter_ + __n % __block_size;
 356             }
 357             else // (__n < 0)
 358             {
 359                 difference_type __z = __block_size - 1 - __n;
 360                 __m_iter_ -= __z / __block_size;
 361                 __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);
 362             }
 363         }
 364         return *this;
 365     }
 366
 367     _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n)
 368     {
 369         return *this += -__n;
 370     }
 371
 372     _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const
 373     {
 374         __deque_iterator __t(*this);
 375         __t += __n;
 376         return __t;
 377     }
 378
 379     _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const
 380     {
 381         __deque_iterator __t(*this);
 382         __t -= __n;
 383         return __t;
 384     }
 385
 386     _LIBCPP_INLINE_VISIBILITY
 387     friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it)
 388         {return __it + __n;}
 389
 390     _LIBCPP_INLINE_VISIBILITY
 391     friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y)
 392     {
 393         if (__x != __y)
 394             return (__x.__m_iter_ - __y.__m_iter_) * __block_size
 395                  + (__x.__ptr_ - *__x.__m_iter_)
 396                  - (__y.__ptr_ - *__y.__m_iter_);
 397         return 0;
 398     }
 399
 400     _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
 401         {return *(*this + __n);}
 402
 403     _LIBCPP_INLINE_VISIBILITY friend
 404         bool operator==(const __deque_iterator& __x, const __deque_iterator& __y)
 405         {return __x.__ptr_ == __y.__ptr_;}
 406
 407     _LIBCPP_INLINE_VISIBILITY friend
 408         bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y)
 409         {return !(__x == __y);}
 410
 411     _LIBCPP_INLINE_VISIBILITY friend
 412         bool operator<(const __deque_iterator& __x, const __deque_iterator& __y)
 413         {return __x.__m_iter_ < __y.__m_iter_ ||
 414                (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);}
 415
 416     _LIBCPP_INLINE_VISIBILITY friend
 417         bool operator>(const __deque_iterator& __x, const __deque_iterator& __y)
 418         {return __y < __x;}
 419
 420     _LIBCPP_INLINE_VISIBILITY friend
 421         bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y)
 422         {return !(__y < __x);}
 423
 424     _LIBCPP_INLINE_VISIBILITY friend
 425         bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)
 426         {return !(__x < __y);}
 427
 428 private:
 429     _LIBCPP_INLINE_VISIBILITY __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
 430         : __m_iter_(__m), __ptr_(__p) {}
 431
 432     template <class _Tp, class _Ap> friend class __deque_base;
 433     template <class _Tp, class _Ap> friend class _LIBCPP_TEMPLATE_VIS deque;
 434     template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>
 435         friend class _LIBCPP_TEMPLATE_VIS __deque_iterator;
 436
 437     template <class _RAIter,
 438               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 439     friend
 440     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 441     copy(_RAIter __f,
 442          _RAIter __l,
 443          __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 444          typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
 445
 446     template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 447               class _OutputIterator>
 448     friend
 449     _OutputIterator
 450     copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 451          __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 452          _OutputIterator __r);
 453
 454     template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 455               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 456     friend
 457     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 458     copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 459          __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 460          __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 461
 462     template <class _RAIter,
 463               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 464     friend
 465     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 466     copy_backward(_RAIter __f,
 467                   _RAIter __l,
 468                   __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 469                   typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
 470
 471     template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 472               class _OutputIterator>
 473     friend
 474     _OutputIterator
 475     copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 476                   __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 477                   _OutputIterator __r);
 478
 479     template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 480               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 481     friend
 482     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 483     copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 484                   __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 485                   __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 486
 487     template <class _RAIter,
 488               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 489     friend
 490     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 491     move(_RAIter __f,
 492          _RAIter __l,
 493          __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 494          typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
 495
 496     template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 497               class _OutputIterator>
 498     friend
 499     _OutputIterator
 500     move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 501          __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 502          _OutputIterator __r);
 503
 504     template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 505               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 506     friend
 507     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 508     move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 509          __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 510          __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 511
 512     template <class _RAIter,
 513               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 514     friend
 515     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 516     move_backward(_RAIter __f,
 517                   _RAIter __l,
 518                   __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 519                   typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
 520
 521     template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 522               class _OutputIterator>
 523     friend
 524     _OutputIterator
 525     move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 526                   __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 527                   _OutputIterator __r);
 528
 529     template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 530               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 531     friend
 532     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 533     move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 534                   __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 535                   __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 536 };
 537
 538 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
 539           class _DiffType, _DiffType _BlockSize>
 540 const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
 541                                  _DiffType, _BlockSize>::__block_size =
 542     __deque_block_size<_ValueType, _DiffType>::value;
 543
 544 // copy
 545
 546 template <class _RAIter,
 547           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 548 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 549 copy(_RAIter __f,
 550      _RAIter __l,
 551      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 552      typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
 553 {
 554     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
 555     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
 556     const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
 557     while (__f != __l)
 558     {
 559         pointer __rb = __r.__ptr_;
 560         pointer __re = *__r.__m_iter_ + __block_size;
 561         difference_type __bs = __re - __rb;
 562         difference_type __n = __l - __f;
 563         _RAIter __m = __l;
 564         if (__n > __bs)
 565         {
 566             __n = __bs;
 567             __m = __f + __n;
 568         }
 569         _VSTD::copy(__f, __m, __rb);
 570         __f = __m;
 571         __r += __n;
 572     }
 573     return __r;
 574 }
 575
 576 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 577           class _OutputIterator>
 578 _OutputIterator
 579 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 580      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 581      _OutputIterator __r)
 582 {
 583     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
 584     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
 585     const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
 586     difference_type __n = __l - __f;
 587     while (__n > 0)
 588     {
 589         pointer __fb = __f.__ptr_;
 590         pointer __fe = *__f.__m_iter_ + __block_size;
 591         difference_type __bs = __fe - __fb;
 592         if (__bs > __n)
 593         {
 594             __bs = __n;
 595             __fe = __fb + __bs;
 596         }
 597         __r = _VSTD::copy(__fb, __fe, __r);
 598         __n -= __bs;
 599         __f += __bs;
 600     }
 601     return __r;
 602 }
 603
 604 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 605           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 606 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 607 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 608      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 609      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
 610 {
 611     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
 612     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
 613     const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
 614     difference_type __n = __l - __f;
 615     while (__n > 0)
 616     {
 617         pointer __fb = __f.__ptr_;
 618         pointer __fe = *__f.__m_iter_ + __block_size;
 619         difference_type __bs = __fe - __fb;
 620         if (__bs > __n)
 621         {
 622             __bs = __n;
 623             __fe = __fb + __bs;
 624         }
 625         __r = _VSTD::copy(__fb, __fe, __r);
 626         __n -= __bs;
 627         __f += __bs;
 628     }
 629     return __r;
 630 }
 631
 632 // copy_backward
 633
 634 template <class _RAIter,
 635           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 636 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 637 copy_backward(_RAIter __f,
 638               _RAIter __l,
 639               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 640               typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
 641 {
 642     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
 643     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
 644     while (__f != __l)
 645     {
 646         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
 647         pointer __rb = *__rp.__m_iter_;
 648         pointer __re = __rp.__ptr_ + 1;
 649         difference_type __bs = __re - __rb;
 650         difference_type __n = __l - __f;
 651         _RAIter __m = __f;
 652         if (__n > __bs)
 653         {
 654             __n = __bs;
 655             __m = __l - __n;
 656         }
 657         _VSTD::copy_backward(__m, __l, __re);
 658         __l = __m;
 659         __r -= __n;
 660     }
 661     return __r;
 662 }
 663
 664 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 665           class _OutputIterator>
 666 _OutputIterator
 667 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 668               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 669               _OutputIterator __r)
 670 {
 671     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
 672     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
 673     difference_type __n = __l - __f;
 674     while (__n > 0)
 675     {
 676         --__l;
 677         pointer __lb = *__l.__m_iter_;
 678         pointer __le = __l.__ptr_ + 1;
 679         difference_type __bs = __le - __lb;
 680         if (__bs > __n)
 681         {
 682             __bs = __n;
 683             __lb = __le - __bs;
 684         }
 685         __r = _VSTD::copy_backward(__lb, __le, __r);
 686         __n -= __bs;
 687         __l -= __bs - 1;
 688     }
 689     return __r;
 690 }
 691
 692 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 693           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 694 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 695 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 696               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 697               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
 698 {
 699     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
 700     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
 701     difference_type __n = __l - __f;
 702     while (__n > 0)
 703     {
 704         --__l;
 705         pointer __lb = *__l.__m_iter_;
 706         pointer __le = __l.__ptr_ + 1;
 707         difference_type __bs = __le - __lb;
 708         if (__bs > __n)
 709         {
 710             __bs = __n;
 711             __lb = __le - __bs;
 712         }
 713         __r = _VSTD::copy_backward(__lb, __le, __r);
 714         __n -= __bs;
 715         __l -= __bs - 1;
 716     }
 717     return __r;
 718 }
 719
 720 // move
 721
 722 template <class _RAIter,
 723           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 724 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 725 move(_RAIter __f,
 726      _RAIter __l,
 727      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 728      typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
 729 {
 730     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
 731     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
 732     const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
 733     while (__f != __l)
 734     {
 735         pointer __rb = __r.__ptr_;
 736         pointer __re = *__r.__m_iter_ + __block_size;
 737         difference_type __bs = __re - __rb;
 738         difference_type __n = __l - __f;
 739         _RAIter __m = __l;
 740         if (__n > __bs)
 741         {
 742             __n = __bs;
 743             __m = __f + __n;
 744         }
 745         _VSTD::move(__f, __m, __rb);
 746         __f = __m;
 747         __r += __n;
 748     }
 749     return __r;
 750 }
 751
 752 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 753           class _OutputIterator>
 754 _OutputIterator
 755 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 756      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 757      _OutputIterator __r)
 758 {
 759     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
 760     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
 761     const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
 762     difference_type __n = __l - __f;
 763     while (__n > 0)
 764     {
 765         pointer __fb = __f.__ptr_;
 766         pointer __fe = *__f.__m_iter_ + __block_size;
 767         difference_type __bs = __fe - __fb;
 768         if (__bs > __n)
 769         {
 770             __bs = __n;
 771             __fe = __fb + __bs;
 772         }
 773         __r = _VSTD::move(__fb, __fe, __r);
 774         __n -= __bs;
 775         __f += __bs;
 776     }
 777     return __r;
 778 }
 779
 780 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 781           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 782 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 783 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 784      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 785      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
 786 {
 787     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
 788     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
 789     const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
 790     difference_type __n = __l - __f;
 791     while (__n > 0)
 792     {
 793         pointer __fb = __f.__ptr_;
 794         pointer __fe = *__f.__m_iter_ + __block_size;
 795         difference_type __bs = __fe - __fb;
 796         if (__bs > __n)
 797         {
 798             __bs = __n;
 799             __fe = __fb + __bs;
 800         }
 801         __r = _VSTD::move(__fb, __fe, __r);
 802         __n -= __bs;
 803         __f += __bs;
 804     }
 805     return __r;
 806 }
 807
 808 // move_backward
 809
 810 template <class _RAIter,
 811           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 812 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 813 move_backward(_RAIter __f,
 814               _RAIter __l,
 815               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
 816               typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
 817 {
 818     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
 819     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
 820     while (__f != __l)
 821     {
 822         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
 823         pointer __rb = *__rp.__m_iter_;
 824         pointer __re = __rp.__ptr_ + 1;
 825         difference_type __bs = __re - __rb;
 826         difference_type __n = __l - __f;
 827         _RAIter __m = __f;
 828         if (__n > __bs)
 829         {
 830             __n = __bs;
 831             __m = __l - __n;
 832         }
 833         _VSTD::move_backward(__m, __l, __re);
 834         __l = __m;
 835         __r -= __n;
 836     }
 837     return __r;
 838 }
 839
 840 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 841           class _OutputIterator>
 842 _OutputIterator
 843 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 844               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 845               _OutputIterator __r)
 846 {
 847     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
 848     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
 849     difference_type __n = __l - __f;
 850     while (__n > 0)
 851     {
 852         --__l;
 853         pointer __lb = *__l.__m_iter_;
 854         pointer __le = __l.__ptr_ + 1;
 855         difference_type __bs = __le - __lb;
 856         if (__bs > __n)
 857         {
 858             __bs = __n;
 859             __lb = __le - __bs;
 860         }
 861         __r = _VSTD::move_backward(__lb, __le, __r);
 862         __n -= __bs;
 863         __l -= __bs - 1;
 864     }
 865     return __r;
 866 }
 867
 868 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
 869           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 870 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 871 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
 872               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
 873               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
 874 {
 875     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
 876     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
 877     difference_type __n = __l - __f;
 878     while (__n > 0)
 879     {
 880         --__l;
 881         pointer __lb = *__l.__m_iter_;
 882         pointer __le = __l.__ptr_ + 1;
 883         difference_type __bs = __le - __lb;
 884         if (__bs > __n)
 885         {
 886             __bs = __n;
 887             __lb = __le - __bs;
 888         }
 889         __r = _VSTD::move_backward(__lb, __le, __r);
 890         __n -= __bs;
 891         __l -= __bs - 1;
 892     }
 893     return __r;
 894 }
 895
 896 template <bool>
 897 class __deque_base_common
 898 {
 899 protected:
 900     _LIBCPP_NORETURN void __throw_length_error() const;
 901     _LIBCPP_NORETURN void __throw_out_of_range() const;
 902 };
 903
 904 template <bool __b>
 905 void
 906 __deque_base_common<__b>::__throw_length_error() const
 907 {
 908     _VSTD::__throw_length_error("deque");
 909 }
 910
 911 template <bool __b>
 912 void
 913 __deque_base_common<__b>::__throw_out_of_range() const
 914 {
 915     _VSTD::__throw_out_of_range("deque");
 916 }
 917
 918 template <class _Tp, class _Allocator>
 919 class __deque_base
 920     : protected __deque_base_common<true>
 921 {
 922     __deque_base(const __deque_base& __c);
 923     __deque_base& operator=(const __deque_base& __c);
 924 protected:
 925     typedef _Tp                                      value_type;
 926     typedef _Allocator                               allocator_type;
 927     typedef allocator_traits<allocator_type>         __alloc_traits;
 928     typedef value_type&                              reference;
 929     typedef const value_type&                        const_reference;
 930     typedef typename __alloc_traits::size_type       size_type;
 931     typedef typename __alloc_traits::difference_type difference_type;
 932     typedef typename __alloc_traits::pointer         pointer;
 933     typedef typename __alloc_traits::const_pointer   const_pointer;
 934
 935     static const difference_type __block_size;
 936
 937     typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator;
 938     typedef allocator_traits<__pointer_allocator>        __map_traits;
 939     typedef typename __map_traits::pointer               __map_pointer;
 940     typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator;
 941     typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;
 942     typedef __split_buffer<pointer, __pointer_allocator> __map;
 943
 944     typedef __deque_iterator<value_type, pointer, reference, __map_pointer,
 945                              difference_type>    iterator;
 946     typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
 947                              difference_type>    const_iterator;
 948
 949     __map __map_;
 950     size_type __start_;
 951     __compressed_pair<size_type, allocator_type> __size_;
 952
 953     iterator       begin() _NOEXCEPT;
 954     const_iterator begin() const _NOEXCEPT;
 955     iterator       end() _NOEXCEPT;
 956     const_iterator end() const _NOEXCEPT;
 957
 958     _LIBCPP_INLINE_VISIBILITY size_type&            size()          {return __size_.first();}
 959     _LIBCPP_INLINE_VISIBILITY
 960     const size_type& size() const _NOEXCEPT {return __size_.first();}
 961     _LIBCPP_INLINE_VISIBILITY allocator_type&       __alloc()       {return __size_.second();}
 962     _LIBCPP_INLINE_VISIBILITY
 963     const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();}
 964
 965     _LIBCPP_INLINE_VISIBILITY
 966     __deque_base()
 967         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
 968     _LIBCPP_INLINE_VISIBILITY
 969     explicit __deque_base(const allocator_type& __a);
 970 public:
 971     ~__deque_base();
 972
 973 #ifndef _LIBCPP_CXX03_LANG
 974     __deque_base(__deque_base&& __c)
 975         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
 976     __deque_base(__deque_base&& __c, const allocator_type& __a);
 977 #endif  // _LIBCPP_CXX03_LANG
 978
 979     void swap(__deque_base& __c)
 980 #if _LIBCPP_STD_VER >= 14
 981         _NOEXCEPT;
 982 #else
 983         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
 984                     __is_nothrow_swappable<allocator_type>::value);
 985 #endif
 986 protected:
 987     void clear() _NOEXCEPT;
 988
 989     bool __invariants() const;
 990
 991     _LIBCPP_INLINE_VISIBILITY
 992     void __move_assign(__deque_base& __c)
 993         _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
 994                    is_nothrow_move_assignable<allocator_type>::value)
 995     {
 996         __map_ = _VSTD::move(__c.__map_);
 997         __start_ = __c.__start_;
 998         size() = __c.size();
 999         __move_assign_alloc(__c);
1000         __c.__start_ = __c.size() = 0;
1001     }
1002
1003     _LIBCPP_INLINE_VISIBILITY
1004     void __move_assign_alloc(__deque_base& __c)
1005         _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
1006                    is_nothrow_move_assignable<allocator_type>::value)
1007         {__move_assign_alloc(__c, integral_constant<bool,
1008                       __alloc_traits::propagate_on_container_move_assignment::value>());}
1009
1010 private:
1011     _LIBCPP_INLINE_VISIBILITY
1012     void __move_assign_alloc(__deque_base& __c, true_type)
1013         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1014         {
1015             __alloc() = _VSTD::move(__c.__alloc());
1016         }
1017
1018     _LIBCPP_INLINE_VISIBILITY
1019     void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT
1020         {}
1021 };
1022
1023 template <class _Tp, class _Allocator>
1024 const typename __deque_base<_Tp, _Allocator>::difference_type
1025     __deque_base<_Tp, _Allocator>::__block_size =
1026         __deque_block_size<value_type, difference_type>::value;
1027
1028 template <class _Tp, class _Allocator>
1029 bool
1030 __deque_base<_Tp, _Allocator>::__invariants() const
1031 {
1032     if (!__map_.__invariants())
1033         return false;
1034     if (__map_.size() >= size_type(-1) / __block_size)
1035         return false;
1036     for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();
1037          __i != __e; ++__i)
1038         if (*__i == nullptr)
1039             return false;
1040     if (__map_.size() != 0)
1041     {
1042         if (size() >= __map_.size() * __block_size)
1043             return false;
1044         if (__start_ >= __map_.size() * __block_size - size())
1045             return false;
1046     }
1047     else
1048     {
1049         if (size() != 0)
1050             return false;
1051         if (__start_ != 0)
1052             return false;
1053     }
1054     return true;
1055 }
1056
1057 template <class _Tp, class _Allocator>
1058 typename __deque_base<_Tp, _Allocator>::iterator
1059 __deque_base<_Tp, _Allocator>::begin() _NOEXCEPT
1060 {
1061     __map_pointer __mp = __map_.begin() + __start_ / __block_size;
1062     return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1063 }
1064
1065 template <class _Tp, class _Allocator>
1066 typename __deque_base<_Tp, _Allocator>::const_iterator
1067 __deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT
1068 {
1069     __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);
1070     return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1071 }
1072
1073 template <class _Tp, class _Allocator>
1074 typename __deque_base<_Tp, _Allocator>::iterator
1075 __deque_base<_Tp, _Allocator>::end() _NOEXCEPT
1076 {
1077     size_type __p = size() + __start_;
1078     __map_pointer __mp = __map_.begin() + __p / __block_size;
1079     return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1080 }
1081
1082 template <class _Tp, class _Allocator>
1083 typename __deque_base<_Tp, _Allocator>::const_iterator
1084 __deque_base<_Tp, _Allocator>::end() const _NOEXCEPT
1085 {
1086     size_type __p = size() + __start_;
1087     __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);
1088     return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1089 }
1090
1091 template <class _Tp, class _Allocator>
1092 inline
1093 __deque_base<_Tp, _Allocator>::__deque_base()
1094     _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1095     : __start_(0), __size_(0) {}
1096
1097 template <class _Tp, class _Allocator>
1098 inline
1099 __deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a)
1100     : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}
1101
1102 template <class _Tp, class _Allocator>
1103 __deque_base<_Tp, _Allocator>::~__deque_base()
1104 {
1105     clear();
1106     typename __map::iterator __i = __map_.begin();
1107     typename __map::iterator __e = __map_.end();
1108     for (; __i != __e; ++__i)
1109         __alloc_traits::deallocate(__alloc(), *__i, __block_size);
1110 }
1111
1112 #ifndef _LIBCPP_CXX03_LANG
1113
1114 template <class _Tp, class _Allocator>
1115 __deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c)
1116     _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1117     : __map_(_VSTD::move(__c.__map_)),
1118       __start_(_VSTD::move(__c.__start_)),
1119       __size_(_VSTD::move(__c.__size_))
1120 {
1121     __c.__start_ = 0;
1122     __c.size() = 0;
1123 }
1124
1125 template <class _Tp, class _Allocator>
1126 __deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a)
1127     : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)),
1128       __start_(_VSTD::move(__c.__start_)),
1129       __size_(_VSTD::move(__c.size()), __a)
1130 {
1131     if (__a == __c.__alloc())
1132     {
1133         __c.__start_ = 0;
1134         __c.size() = 0;
1135     }
1136     else
1137     {
1138         __map_.clear();
1139         __start_ = 0;
1140         size() = 0;
1141     }
1142 }
1143
1144 #endif  // _LIBCPP_CXX03_LANG
1145
1146 template <class _Tp, class _Allocator>
1147 void
1148 __deque_base<_Tp, _Allocator>::swap(__deque_base& __c)
1149 #if _LIBCPP_STD_VER >= 14
1150         _NOEXCEPT
1151 #else
1152         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1153                     __is_nothrow_swappable<allocator_type>::value)
1154 #endif
1155 {
1156     __map_.swap(__c.__map_);
1157     _VSTD::swap(__start_, __c.__start_);
1158     _VSTD::swap(size(), __c.size());
1159     __swap_allocator(__alloc(), __c.__alloc());
1160 }
1161
1162 template <class _Tp, class _Allocator>
1163 void
1164 __deque_base<_Tp, _Allocator>::clear() _NOEXCEPT
1165 {
1166     allocator_type& __a = __alloc();
1167     for (iterator __i = begin(), __e = end(); __i != __e; ++__i)
1168         __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
1169     size() = 0;
1170     while (__map_.size() > 2)
1171     {
1172         __alloc_traits::deallocate(__a, __map_.front(), __block_size);
1173         __map_.pop_front();
1174     }
1175     switch (__map_.size())
1176     {
1177     case 1:
1178         __start_ = __block_size / 2;
1179         break;
1180     case 2:
1181         __start_ = __block_size;
1182         break;
1183     }
1184 }
1185
1186 template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
1187 class _LIBCPP_TEMPLATE_VIS deque
1188     : private __deque_base<_Tp, _Allocator>
1189 {
1190 public:
1191     // types:
1192
1193     typedef _Tp value_type;
1194     typedef _Allocator allocator_type;
1195
1196     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1197                   "Allocator::value_type must be same type as value_type");
1198
1199     typedef __deque_base<value_type, allocator_type> __base;
1200
1201     typedef typename __base::__alloc_traits        __alloc_traits;
1202     typedef typename __base::reference             reference;
1203     typedef typename __base::const_reference       const_reference;
1204     typedef typename __base::iterator              iterator;
1205     typedef typename __base::const_iterator        const_iterator;
1206     typedef typename __base::size_type             size_type;
1207     typedef typename __base::difference_type       difference_type;
1208
1209     typedef typename __base::pointer               pointer;
1210     typedef typename __base::const_pointer         const_pointer;
1211     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
1212     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1213
1214     // construct/copy/destroy:
1215     _LIBCPP_INLINE_VISIBILITY
1216     deque()
1217         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1218         {}
1219     _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {}
1220     explicit deque(size_type __n);
1221 #if _LIBCPP_STD_VER > 11
1222     explicit deque(size_type __n, const _Allocator& __a);
1223 #endif
1224     deque(size_type __n, const value_type& __v);
1225     deque(size_type __n, const value_type& __v, const allocator_type& __a);
1226     template <class _InputIter>
1227         deque(_InputIter __f, _InputIter __l,
1228               typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1229     template <class _InputIter>
1230         deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1231               typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1232     deque(const deque& __c);
1233     deque(const deque& __c, const allocator_type& __a);
1234
1235     deque& operator=(const deque& __c);
1236
1237 #ifndef _LIBCPP_CXX03_LANG
1238     deque(initializer_list<value_type> __il);
1239     deque(initializer_list<value_type> __il, const allocator_type& __a);
1240
1241     _LIBCPP_INLINE_VISIBILITY
1242     deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
1243
1244     _LIBCPP_INLINE_VISIBILITY
1245     deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
1246     _LIBCPP_INLINE_VISIBILITY
1247     deque(deque&& __c, const allocator_type& __a);
1248     _LIBCPP_INLINE_VISIBILITY
1249     deque& operator=(deque&& __c)
1250         _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1251                    is_nothrow_move_assignable<allocator_type>::value);
1252
1253     _LIBCPP_INLINE_VISIBILITY
1254     void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
1255 #endif  // _LIBCPP_CXX03_LANG
1256
1257     template <class _InputIter>
1258         void assign(_InputIter __f, _InputIter __l,
1259                     typename enable_if<__is_input_iterator<_InputIter>::value &&
1260                                       !__is_random_access_iterator<_InputIter>::value>::type* = 0);
1261     template <class _RAIter>
1262         void assign(_RAIter __f, _RAIter __l,
1263                     typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
1264     void assign(size_type __n, const value_type& __v);
1265
1266     _LIBCPP_INLINE_VISIBILITY
1267     allocator_type get_allocator() const _NOEXCEPT;
1268
1269     // iterators:
1270
1271     _LIBCPP_INLINE_VISIBILITY
1272     iterator       begin() _NOEXCEPT       {return __base::begin();}
1273     _LIBCPP_INLINE_VISIBILITY
1274     const_iterator begin() const _NOEXCEPT {return __base::begin();}
1275     _LIBCPP_INLINE_VISIBILITY
1276     iterator       end() _NOEXCEPT         {return __base::end();}
1277     _LIBCPP_INLINE_VISIBILITY
1278     const_iterator end()   const _NOEXCEPT {return __base::end();}
1279
1280     _LIBCPP_INLINE_VISIBILITY
1281     reverse_iterator       rbegin() _NOEXCEPT
1282         {return       reverse_iterator(__base::end());}
1283     _LIBCPP_INLINE_VISIBILITY
1284     const_reverse_iterator rbegin() const _NOEXCEPT
1285         {return const_reverse_iterator(__base::end());}
1286     _LIBCPP_INLINE_VISIBILITY
1287     reverse_iterator       rend() _NOEXCEPT
1288         {return       reverse_iterator(__base::begin());}
1289     _LIBCPP_INLINE_VISIBILITY
1290     const_reverse_iterator rend()   const _NOEXCEPT
1291         {return const_reverse_iterator(__base::begin());}
1292
1293     _LIBCPP_INLINE_VISIBILITY
1294     const_iterator         cbegin()  const _NOEXCEPT
1295         {return __base::begin();}
1296     _LIBCPP_INLINE_VISIBILITY
1297     const_iterator         cend()    const _NOEXCEPT
1298         {return __base::end();}
1299     _LIBCPP_INLINE_VISIBILITY
1300     const_reverse_iterator crbegin() const _NOEXCEPT
1301         {return const_reverse_iterator(__base::end());}
1302     _LIBCPP_INLINE_VISIBILITY
1303     const_reverse_iterator crend()   const _NOEXCEPT
1304         {return const_reverse_iterator(__base::begin());}
1305
1306     // capacity:
1307     _LIBCPP_INLINE_VISIBILITY
1308     size_type size() const _NOEXCEPT {return __base::size();}
1309     _LIBCPP_INLINE_VISIBILITY
1310     size_type max_size() const _NOEXCEPT
1311         {return std::min<size_type>(
1312             __alloc_traits::max_size(__base::__alloc()),
1313             numeric_limits<difference_type>::max());}
1314     void resize(size_type __n);
1315     void resize(size_type __n, const value_type& __v);
1316     void shrink_to_fit() _NOEXCEPT;
1317     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1318     bool empty() const _NOEXCEPT {return __base::size() == 0;}
1319
1320     // element access:
1321     _LIBCPP_INLINE_VISIBILITY
1322     reference operator[](size_type __i);
1323     _LIBCPP_INLINE_VISIBILITY
1324     const_reference operator[](size_type __i) const;
1325     _LIBCPP_INLINE_VISIBILITY
1326     reference at(size_type __i);
1327     _LIBCPP_INLINE_VISIBILITY
1328     const_reference at(size_type __i) const;
1329     _LIBCPP_INLINE_VISIBILITY
1330     reference front();
1331     _LIBCPP_INLINE_VISIBILITY
1332     const_reference front() const;
1333     _LIBCPP_INLINE_VISIBILITY
1334     reference back();
1335     _LIBCPP_INLINE_VISIBILITY
1336     const_reference back() const;
1337
1338     // 23.2.2.3 modifiers:
1339     void push_front(const value_type& __v);
1340     void push_back(const value_type& __v);
1341 #ifndef _LIBCPP_CXX03_LANG
1342 #if _LIBCPP_STD_VER > 14
1343     template <class... _Args> reference emplace_front(_Args&&... __args);
1344     template <class... _Args> reference emplace_back (_Args&&... __args);
1345 #else
1346     template <class... _Args> void      emplace_front(_Args&&... __args);
1347     template <class... _Args> void      emplace_back (_Args&&... __args);
1348 #endif
1349     template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args);
1350
1351     void push_front(value_type&& __v);
1352     void push_back(value_type&& __v);
1353     iterator insert(const_iterator __p, value_type&& __v);
1354
1355     _LIBCPP_INLINE_VISIBILITY
1356     iterator insert(const_iterator __p, initializer_list<value_type> __il)
1357         {return insert(__p, __il.begin(), __il.end());}
1358 #endif  // _LIBCPP_CXX03_LANG
1359     iterator insert(const_iterator __p, const value_type& __v);
1360     iterator insert(const_iterator __p, size_type __n, const value_type& __v);
1361     template <class _InputIter>
1362         iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
1363                          typename enable_if<__is_input_iterator<_InputIter>::value
1364                                          &&!__is_forward_iterator<_InputIter>::value>::type* = 0);
1365     template <class _ForwardIterator>
1366         iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
1367                                typename enable_if<__is_forward_iterator<_ForwardIterator>::value
1368                                          &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type* = 0);
1369     template <class _BiIter>
1370         iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
1371                          typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type* = 0);
1372
1373     void pop_front();
1374     void pop_back();
1375     iterator erase(const_iterator __p);
1376     iterator erase(const_iterator __f, const_iterator __l);
1377
1378     _LIBCPP_INLINE_VISIBILITY
1379     void swap(deque& __c)
1380 #if _LIBCPP_STD_VER >= 14
1381         _NOEXCEPT;
1382 #else
1383         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1384                    __is_nothrow_swappable<allocator_type>::value);
1385 #endif
1386     _LIBCPP_INLINE_VISIBILITY
1387     void clear() _NOEXCEPT;
1388
1389     _LIBCPP_INLINE_VISIBILITY
1390     bool __invariants() const {return __base::__invariants();}
1391 private:
1392     typedef typename __base::__map_const_pointer __map_const_pointer;
1393
1394     _LIBCPP_INLINE_VISIBILITY
1395     static size_type __recommend_blocks(size_type __n)
1396     {
1397         return __n / __base::__block_size + (__n % __base::__block_size != 0);
1398     }
1399     _LIBCPP_INLINE_VISIBILITY
1400     size_type __capacity() const
1401     {
1402         return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
1403     }
1404     _LIBCPP_INLINE_VISIBILITY
1405     size_type __front_spare() const
1406     {
1407         return __base::__start_;
1408     }
1409     _LIBCPP_INLINE_VISIBILITY
1410     size_type __back_spare() const
1411     {
1412         return __capacity() - (__base::__start_ + __base::size());
1413     }
1414
1415     template <class _InpIter>
1416         void __append(_InpIter __f, _InpIter __l,
1417                  typename enable_if<__is_input_iterator<_InpIter>::value &&
1418                                    !__is_forward_iterator<_InpIter>::value>::type* = 0);
1419     template <class _ForIter>
1420         void __append(_ForIter __f, _ForIter __l,
1421                       typename enable_if<__is_forward_iterator<_ForIter>::value>::type* = 0);
1422     void __append(size_type __n);
1423     void __append(size_type __n, const value_type& __v);
1424     void __erase_to_end(const_iterator __f);
1425     void __add_front_capacity();
1426     void __add_front_capacity(size_type __n);
1427     void __add_back_capacity();
1428     void __add_back_capacity(size_type __n);
1429     iterator __move_and_check(iterator __f, iterator __l, iterator __r,
1430                               const_pointer& __vt);
1431     iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r,
1432                                        const_pointer& __vt);
1433     void __move_construct_and_check(iterator __f, iterator __l,
1434                                     iterator __r, const_pointer& __vt);
1435     void __move_construct_backward_and_check(iterator __f, iterator __l,
1436                                              iterator __r, const_pointer& __vt);
1437
1438     _LIBCPP_INLINE_VISIBILITY
1439     void __copy_assign_alloc(const deque& __c)
1440         {__copy_assign_alloc(__c, integral_constant<bool,
1441                       __alloc_traits::propagate_on_container_copy_assignment::value>());}
1442
1443     _LIBCPP_INLINE_VISIBILITY
1444     void __copy_assign_alloc(const deque& __c, true_type)
1445         {
1446             if (__base::__alloc() != __c.__alloc())
1447             {
1448                 clear();
1449                 shrink_to_fit();
1450             }
1451             __base::__alloc() = __c.__alloc();
1452             __base::__map_.__alloc() = __c.__map_.__alloc();
1453         }
1454
1455     _LIBCPP_INLINE_VISIBILITY
1456     void __copy_assign_alloc(const deque&, false_type)
1457         {}
1458
1459     void __move_assign(deque& __c, true_type)
1460         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
1461     void __move_assign(deque& __c, false_type);
1462 };
1463
1464 template <class _Tp, class _Allocator>
1465 deque<_Tp, _Allocator>::deque(size_type __n)
1466 {
1467     if (__n > 0)
1468         __append(__n);
1469 }
1470
1471 #if _LIBCPP_STD_VER > 11
1472 template <class _Tp, class _Allocator>
1473 deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a)
1474     : __base(__a)
1475 {
1476     if (__n > 0)
1477         __append(__n);
1478 }
1479 #endif
1480
1481 template <class _Tp, class _Allocator>
1482 deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)
1483 {
1484     if (__n > 0)
1485         __append(__n, __v);
1486 }
1487
1488 template <class _Tp, class _Allocator>
1489 deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a)
1490     : __base(__a)
1491 {
1492     if (__n > 0)
1493         __append(__n, __v);
1494 }
1495
1496 template <class _Tp, class _Allocator>
1497 template <class _InputIter>
1498 deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l,
1499               typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1500 {
1501     __append(__f, __l);
1502 }
1503
1504 template <class _Tp, class _Allocator>
1505 template <class _InputIter>
1506 deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1507               typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1508     : __base(__a)
1509 {
1510     __append(__f, __l);
1511 }
1512
1513 template <class _Tp, class _Allocator>
1514 deque<_Tp, _Allocator>::deque(const deque& __c)
1515     : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))
1516 {
1517     __append(__c.begin(), __c.end());
1518 }
1519
1520 template <class _Tp, class _Allocator>
1521 deque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a)
1522     : __base(__a)
1523 {
1524     __append(__c.begin(), __c.end());
1525 }
1526
1527 template <class _Tp, class _Allocator>
1528 deque<_Tp, _Allocator>&
1529 deque<_Tp, _Allocator>::operator=(const deque& __c)
1530 {
1531     if (this != &__c)
1532     {
1533         __copy_assign_alloc(__c);
1534         assign(__c.begin(), __c.end());
1535     }
1536     return *this;
1537 }
1538
1539 #ifndef _LIBCPP_CXX03_LANG
1540
1541 template <class _Tp, class _Allocator>
1542 deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)
1543 {
1544     __append(__il.begin(), __il.end());
1545 }
1546
1547 template <class _Tp, class _Allocator>
1548 deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a)
1549     : __base(__a)
1550 {
1551     __append(__il.begin(), __il.end());
1552 }
1553
1554 template <class _Tp, class _Allocator>
1555 inline
1556 deque<_Tp, _Allocator>::deque(deque&& __c)
1557     _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1558     : __base(_VSTD::move(__c))
1559 {
1560 }
1561
1562 template <class _Tp, class _Allocator>
1563 inline
1564 deque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a)
1565     : __base(_VSTD::move(__c), __a)
1566 {
1567     if (__a != __c.__alloc())
1568     {
1569         typedef move_iterator<iterator> _Ip;
1570         assign(_Ip(__c.begin()), _Ip(__c.end()));
1571     }
1572 }
1573
1574 template <class _Tp, class _Allocator>
1575 inline
1576 deque<_Tp, _Allocator>&
1577 deque<_Tp, _Allocator>::operator=(deque&& __c)
1578         _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1579                    is_nothrow_move_assignable<allocator_type>::value)
1580 {
1581     __move_assign(__c, integral_constant<bool,
1582           __alloc_traits::propagate_on_container_move_assignment::value>());
1583     return *this;
1584 }
1585
1586 template <class _Tp, class _Allocator>
1587 void
1588 deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type)
1589 {
1590     if (__base::__alloc() != __c.__alloc())
1591     {
1592         typedef move_iterator<iterator> _Ip;
1593         assign(_Ip(__c.begin()), _Ip(__c.end()));
1594     }
1595     else
1596         __move_assign(__c, true_type());
1597 }
1598
1599 template <class _Tp, class _Allocator>
1600 void
1601 deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type)
1602     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1603 {
1604     clear();
1605     shrink_to_fit();
1606     __base::__move_assign(__c);
1607 }
1608
1609 #endif  // _LIBCPP_CXX03_LANG
1610
1611 template <class _Tp, class _Allocator>
1612 template <class _InputIter>
1613 void
1614 deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
1615                                typename enable_if<__is_input_iterator<_InputIter>::value &&
1616                                                  !__is_random_access_iterator<_InputIter>::value>::type*)
1617 {
1618     iterator __i = __base::begin();
1619     iterator __e = __base::end();
1620     for (; __f != __l && __i != __e; ++__f, (void) ++__i)
1621         *__i = *__f;
1622     if (__f != __l)
1623         __append(__f, __l);
1624     else
1625         __erase_to_end(__i);
1626 }
1627
1628 template <class _Tp, class _Allocator>
1629 template <class _RAIter>
1630 void
1631 deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
1632                                typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
1633 {
1634     if (static_cast<size_type>(__l - __f) > __base::size())
1635     {
1636         _RAIter __m = __f + __base::size();
1637         _VSTD::copy(__f, __m, __base::begin());
1638         __append(__m, __l);
1639     }
1640     else
1641         __erase_to_end(_VSTD::copy(__f, __l, __base::begin()));
1642 }
1643
1644 template <class _Tp, class _Allocator>
1645 void
1646 deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
1647 {
1648     if (__n > __base::size())
1649     {
1650         _VSTD::fill_n(__base::begin(), __base::size(), __v);
1651         __n -= __base::size();
1652         __append(__n, __v);
1653     }
1654     else
1655         __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v));
1656 }
1657
1658 template <class _Tp, class _Allocator>
1659 inline
1660 _Allocator
1661 deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
1662 {
1663     return __base::__alloc();
1664 }
1665
1666 template <class _Tp, class _Allocator>
1667 void
1668 deque<_Tp, _Allocator>::resize(size_type __n)
1669 {
1670     if (__n > __base::size())
1671         __append(__n - __base::size());
1672     else if (__n < __base::size())
1673         __erase_to_end(__base::begin() + __n);
1674 }
1675
1676 template <class _Tp, class _Allocator>
1677 void
1678 deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v)
1679 {
1680     if (__n > __base::size())
1681         __append(__n - __base::size(), __v);
1682     else if (__n < __base::size())
1683         __erase_to_end(__base::begin() + __n);
1684 }
1685
1686 template <class _Tp, class _Allocator>
1687 void
1688 deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1689 {
1690     allocator_type& __a = __base::__alloc();
1691     if (empty())
1692     {
1693         while (__base::__map_.size() > 0)
1694         {
1695             __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1696             __base::__map_.pop_back();
1697         }
1698         __base::__start_ = 0;
1699     }
1700     else
1701     {
1702         if (__front_spare() >= __base::__block_size)
1703         {
1704             __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
1705             __base::__map_.pop_front();
1706             __base::__start_ -= __base::__block_size;
1707         }
1708         if (__back_spare() >= __base::__block_size)
1709         {
1710             __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1711             __base::__map_.pop_back();
1712         }
1713     }
1714     __base::__map_.shrink_to_fit();
1715 }
1716
1717 template <class _Tp, class _Allocator>
1718 inline
1719 typename deque<_Tp, _Allocator>::reference
1720 deque<_Tp, _Allocator>::operator[](size_type __i)
1721 {
1722     size_type __p = __base::__start_ + __i;
1723     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1724 }
1725
1726 template <class _Tp, class _Allocator>
1727 inline
1728 typename deque<_Tp, _Allocator>::const_reference
1729 deque<_Tp, _Allocator>::operator[](size_type __i) const
1730 {
1731     size_type __p = __base::__start_ + __i;
1732     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1733 }
1734
1735 template <class _Tp, class _Allocator>
1736 inline
1737 typename deque<_Tp, _Allocator>::reference
1738 deque<_Tp, _Allocator>::at(size_type __i)
1739 {
1740     if (__i >= __base::size())
1741         __base::__throw_out_of_range();
1742     size_type __p = __base::__start_ + __i;
1743     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1744 }
1745
1746 template <class _Tp, class _Allocator>
1747 inline
1748 typename deque<_Tp, _Allocator>::const_reference
1749 deque<_Tp, _Allocator>::at(size_type __i) const
1750 {
1751     if (__i >= __base::size())
1752         __base::__throw_out_of_range();
1753     size_type __p = __base::__start_ + __i;
1754     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1755 }
1756
1757 template <class _Tp, class _Allocator>
1758 inline
1759 typename deque<_Tp, _Allocator>::reference
1760 deque<_Tp, _Allocator>::front()
1761 {
1762     return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1763                                       + __base::__start_ % __base::__block_size);
1764 }
1765
1766 template <class _Tp, class _Allocator>
1767 inline
1768 typename deque<_Tp, _Allocator>::const_reference
1769 deque<_Tp, _Allocator>::front() const
1770 {
1771     return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1772                                       + __base::__start_ % __base::__block_size);
1773 }
1774
1775 template <class _Tp, class _Allocator>
1776 inline
1777 typename deque<_Tp, _Allocator>::reference
1778 deque<_Tp, _Allocator>::back()
1779 {
1780     size_type __p = __base::size() + __base::__start_ - 1;
1781     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1782 }
1783
1784 template <class _Tp, class _Allocator>
1785 inline
1786 typename deque<_Tp, _Allocator>::const_reference
1787 deque<_Tp, _Allocator>::back() const
1788 {
1789     size_type __p = __base::size() + __base::__start_ - 1;
1790     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1791 }
1792
1793 template <class _Tp, class _Allocator>
1794 void
1795 deque<_Tp, _Allocator>::push_back(const value_type& __v)
1796 {
1797     allocator_type& __a = __base::__alloc();
1798     if (__back_spare() == 0)
1799         __add_back_capacity();
1800     // __back_spare() >= 1
1801     __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
1802     ++__base::size();
1803 }
1804
1805 template <class _Tp, class _Allocator>
1806 void
1807 deque<_Tp, _Allocator>::push_front(const value_type& __v)
1808 {
1809     allocator_type& __a = __base::__alloc();
1810     if (__front_spare() == 0)
1811         __add_front_capacity();
1812     // __front_spare() >= 1
1813     __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
1814     --__base::__start_;
1815     ++__base::size();
1816 }
1817
1818 #ifndef _LIBCPP_CXX03_LANG
1819 template <class _Tp, class _Allocator>
1820 void
1821 deque<_Tp, _Allocator>::push_back(value_type&& __v)
1822 {
1823     allocator_type& __a = __base::__alloc();
1824     if (__back_spare() == 0)
1825         __add_back_capacity();
1826     // __back_spare() >= 1
1827     __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
1828     ++__base::size();
1829 }
1830
1831 template <class _Tp, class _Allocator>
1832 template <class... _Args>
1833 #if _LIBCPP_STD_VER > 14
1834 typename deque<_Tp, _Allocator>::reference
1835 #else
1836 void
1837 #endif
1838 deque<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1839 {
1840     allocator_type& __a = __base::__alloc();
1841     if (__back_spare() == 0)
1842         __add_back_capacity();
1843     // __back_spare() >= 1
1844     __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()),
1845                               _VSTD::forward<_Args>(__args)...);
1846     ++__base::size();
1847 #if _LIBCPP_STD_VER > 14
1848     return *--__base::end();
1849 #endif
1850 }
1851
1852 template <class _Tp, class _Allocator>
1853 void
1854 deque<_Tp, _Allocator>::push_front(value_type&& __v)
1855 {
1856     allocator_type& __a = __base::__alloc();
1857     if (__front_spare() == 0)
1858         __add_front_capacity();
1859     // __front_spare() >= 1
1860     __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
1861     --__base::__start_;
1862     ++__base::size();
1863 }
1864
1865
1866 template <class _Tp, class _Allocator>
1867 template <class... _Args>
1868 #if _LIBCPP_STD_VER > 14
1869 typename deque<_Tp, _Allocator>::reference
1870 #else
1871 void
1872 #endif
1873 deque<_Tp, _Allocator>::emplace_front(_Args&&... __args)
1874 {
1875     allocator_type& __a = __base::__alloc();
1876     if (__front_spare() == 0)
1877         __add_front_capacity();
1878     // __front_spare() >= 1
1879     __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
1880     --__base::__start_;
1881     ++__base::size();
1882 #if _LIBCPP_STD_VER > 14
1883     return *__base::begin();
1884 #endif
1885 }
1886
1887 template <class _Tp, class _Allocator>
1888 typename deque<_Tp, _Allocator>::iterator
1889 deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v)
1890 {
1891     size_type __pos = __p - __base::begin();
1892     size_type __to_end = __base::size() - __pos;
1893     allocator_type& __a = __base::__alloc();
1894     if (__pos < __to_end)
1895     {   // insert by shifting things backward
1896         if (__front_spare() == 0)
1897             __add_front_capacity();
1898         // __front_spare() >= 1
1899         if (__pos == 0)
1900         {
1901             __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
1902             --__base::__start_;
1903             ++__base::size();
1904         }
1905         else
1906         {
1907             iterator __b = __base::begin();
1908             iterator __bm1 = _VSTD::prev(__b);
1909             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1910             --__base::__start_;
1911             ++__base::size();
1912             if (__pos > 1)
1913                 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1914             *__b = _VSTD::move(__v);
1915         }
1916     }
1917     else
1918     {   // insert by shifting things forward
1919         if (__back_spare() == 0)
1920             __add_back_capacity();
1921         // __back_capacity >= 1
1922         size_type __de = __base::size() - __pos;
1923         if (__de == 0)
1924         {
1925             __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
1926             ++__base::size();
1927         }
1928         else
1929         {
1930             iterator __e = __base::end();
1931             iterator __em1 = _VSTD::prev(__e);
1932             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
1933             ++__base::size();
1934             if (__de > 1)
1935                 __e = _VSTD::move_backward(__e - __de, __em1, __e);
1936             *--__e = _VSTD::move(__v);
1937         }
1938     }
1939     return __base::begin() + __pos;
1940 }
1941
1942 template <class _Tp, class _Allocator>
1943 template <class... _Args>
1944 typename deque<_Tp, _Allocator>::iterator
1945 deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args)
1946 {
1947     size_type __pos = __p - __base::begin();
1948     size_type __to_end = __base::size() - __pos;
1949     allocator_type& __a = __base::__alloc();
1950     if (__pos < __to_end)
1951     {   // insert by shifting things backward
1952         if (__front_spare() == 0)
1953             __add_front_capacity();
1954         // __front_spare() >= 1
1955         if (__pos == 0)
1956         {
1957             __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
1958             --__base::__start_;
1959             ++__base::size();
1960         }
1961         else
1962         {
1963             __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
1964             iterator __b = __base::begin();
1965             iterator __bm1 = _VSTD::prev(__b);
1966             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1967             --__base::__start_;
1968             ++__base::size();
1969             if (__pos > 1)
1970                 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1971             *__b = _VSTD::move(__tmp.get());
1972         }
1973     }
1974     else
1975     {   // insert by shifting things forward
1976         if (__back_spare() == 0)
1977             __add_back_capacity();
1978         // __back_capacity >= 1
1979         size_type __de = __base::size() - __pos;
1980         if (__de == 0)
1981         {
1982             __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
1983             ++__base::size();
1984         }
1985         else
1986         {
1987             __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
1988             iterator __e = __base::end();
1989             iterator __em1 = _VSTD::prev(__e);
1990             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
1991             ++__base::size();
1992             if (__de > 1)
1993                 __e = _VSTD::move_backward(__e - __de, __em1, __e);
1994             *--__e = _VSTD::move(__tmp.get());
1995         }
1996     }
1997     return __base::begin() + __pos;
1998 }
1999
2000 #endif  // _LIBCPP_CXX03_LANG
2001
2002
2003 template <class _Tp, class _Allocator>
2004 typename deque<_Tp, _Allocator>::iterator
2005 deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v)
2006 {
2007     size_type __pos = __p - __base::begin();
2008     size_type __to_end = __base::size() - __pos;
2009     allocator_type& __a = __base::__alloc();
2010     if (__pos < __to_end)
2011     {   // insert by shifting things backward
2012         if (__front_spare() == 0)
2013             __add_front_capacity();
2014         // __front_spare() >= 1
2015         if (__pos == 0)
2016         {
2017             __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
2018             --__base::__start_;
2019             ++__base::size();
2020         }
2021         else
2022         {
2023             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2024             iterator __b = __base::begin();
2025             iterator __bm1 = _VSTD::prev(__b);
2026             if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))
2027                 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);
2028             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
2029             --__base::__start_;
2030             ++__base::size();
2031             if (__pos > 1)
2032                 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt);
2033             *__b = *__vt;
2034         }
2035     }
2036     else
2037     {   // insert by shifting things forward
2038         if (__back_spare() == 0)
2039             __add_back_capacity();
2040         // __back_capacity >= 1
2041         size_type __de = __base::size() - __pos;
2042         if (__de == 0)
2043         {
2044             __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
2045             ++__base::size();
2046         }
2047         else
2048         {
2049             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2050             iterator __e = __base::end();
2051             iterator __em1 = _VSTD::prev(__e);
2052             if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))
2053                 __vt = pointer_traits<const_pointer>::pointer_to(*__e);
2054             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
2055             ++__base::size();
2056             if (__de > 1)
2057                 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);
2058             *--__e = *__vt;
2059         }
2060     }
2061     return __base::begin() + __pos;
2062 }
2063
2064 template <class _Tp, class _Allocator>
2065 typename deque<_Tp, _Allocator>::iterator
2066 deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v)
2067 {
2068     size_type __pos = __p - __base::begin();
2069     size_type __to_end = __base::size() - __pos;
2070     allocator_type& __a = __base::__alloc();
2071     if (__pos < __to_end)
2072     {   // insert by shifting things backward
2073         if (__n > __front_spare())
2074             __add_front_capacity(__n - __front_spare());
2075         // __n <= __front_spare()
2076         iterator __old_begin = __base::begin();
2077         iterator __i = __old_begin;
2078         if (__n > __pos)
2079         {
2080             for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size())
2081                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v);
2082             __n = __pos;
2083         }
2084         if (__n > 0)
2085         {
2086             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2087             iterator __obn = __old_begin + __n;
2088             __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);
2089             if (__n < __pos)
2090                 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);
2091             _VSTD::fill_n(__old_begin, __n, *__vt);
2092         }
2093     }
2094     else
2095     {   // insert by shifting things forward
2096         size_type __back_capacity = __back_spare();
2097         if (__n > __back_capacity)
2098             __add_back_capacity(__n - __back_capacity);
2099         // __n <= __back_capacity
2100         iterator __old_end = __base::end();
2101         iterator __i = __old_end;
2102         size_type __de = __base::size() - __pos;
2103         if (__n > __de)
2104         {
2105             for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size())
2106                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
2107             __n = __de;
2108         }
2109         if (__n > 0)
2110         {
2111             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2112             iterator __oen = __old_end - __n;
2113             __move_construct_and_check(__oen, __old_end, __i, __vt);
2114             if (__n < __de)
2115                 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);
2116             _VSTD::fill_n(__old_end - __n, __n, *__vt);
2117         }
2118     }
2119     return __base::begin() + __pos;
2120 }
2121
2122 template <class _Tp, class _Allocator>
2123 template <class _InputIter>
2124 typename deque<_Tp, _Allocator>::iterator
2125 deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
2126                                typename enable_if<__is_input_iterator<_InputIter>::value
2127                                                &&!__is_forward_iterator<_InputIter>::value>::type*)
2128 {
2129     __split_buffer<value_type, allocator_type&> __buf(__base::__alloc());
2130     __buf.__construct_at_end(__f, __l);
2131     typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
2132     return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
2133 }
2134
2135 template <class _Tp, class _Allocator>
2136 template <class _ForwardIterator>
2137 typename deque<_Tp, _Allocator>::iterator
2138 deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
2139                                typename enable_if<__is_forward_iterator<_ForwardIterator>::value
2140                                                &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type*)
2141 {
2142     size_type __n = _VSTD::distance(__f, __l);
2143     __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc());
2144     __buf.__construct_at_end(__f, __l);
2145     typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
2146     return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
2147 }
2148
2149 template <class _Tp, class _Allocator>
2150 template <class _BiIter>
2151 typename deque<_Tp, _Allocator>::iterator
2152 deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
2153                                typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*)
2154 {
2155     size_type __n = _VSTD::distance(__f, __l);
2156     size_type __pos = __p - __base::begin();
2157     size_type __to_end = __base::size() - __pos;
2158     allocator_type& __a = __base::__alloc();
2159     if (__pos < __to_end)
2160     {   // insert by shifting things backward
2161         if (__n > __front_spare())
2162             __add_front_capacity(__n - __front_spare());
2163         // __n <= __front_spare()
2164         iterator __old_begin = __base::begin();
2165         iterator __i = __old_begin;
2166         _BiIter __m = __f;
2167         if (__n > __pos)
2168         {
2169             __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
2170             for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size())
2171                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
2172             __n = __pos;
2173         }
2174         if (__n > 0)
2175         {
2176             iterator __obn = __old_begin + __n;
2177             for (iterator __j = __obn; __j != __old_begin;)
2178             {
2179                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
2180                 --__base::__start_;
2181                 ++__base::size();
2182             }
2183             if (__n < __pos)
2184                 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
2185             _VSTD::copy(__m, __l, __old_begin);
2186         }
2187     }
2188     else
2189     {   // insert by shifting things forward
2190         size_type __back_capacity = __back_spare();
2191         if (__n > __back_capacity)
2192             __add_back_capacity(__n - __back_capacity);
2193         // __n <= __back_capacity
2194         iterator __old_end = __base::end();
2195         iterator __i = __old_end;
2196         _BiIter __m = __l;
2197         size_type __de = __base::size() - __pos;
2198         if (__n > __de)
2199         {
2200             __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
2201             for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
2202                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
2203             __n = __de;
2204         }
2205         if (__n > 0)
2206         {
2207             iterator __oen = __old_end - __n;
2208             for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size())
2209                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
2210             if (__n < __de)
2211                 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
2212             _VSTD::copy_backward(__f, __m, __old_end);
2213         }
2214     }
2215     return __base::begin() + __pos;
2216 }
2217
2218 template <class _Tp, class _Allocator>
2219 template <class _InpIter>
2220 void
2221 deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
2222                                  typename enable_if<__is_input_iterator<_InpIter>::value &&
2223                                                    !__is_forward_iterator<_InpIter>::value>::type*)
2224 {
2225     for (; __f != __l; ++__f)
2226 #ifdef _LIBCPP_CXX03_LANG
2227         push_back(*__f);
2228 #else
2229         emplace_back(*__f);
2230 #endif
2231 }
2232
2233 template <class _Tp, class _Allocator>
2234 template <class _ForIter>
2235 void
2236 deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
2237                                  typename enable_if<__is_forward_iterator<_ForIter>::value>::type*)
2238 {
2239     size_type __n = _VSTD::distance(__f, __l);
2240     allocator_type& __a = __base::__alloc();
2241     size_type __back_capacity = __back_spare();
2242     if (__n > __back_capacity)
2243         __add_back_capacity(__n - __back_capacity);
2244     // __n <= __back_capacity
2245     for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size())
2246         __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f);
2247 }
2248
2249 template <class _Tp, class _Allocator>
2250 void
2251 deque<_Tp, _Allocator>::__append(size_type __n)
2252 {
2253     allocator_type& __a = __base::__alloc();
2254     size_type __back_capacity = __back_spare();
2255     if (__n > __back_capacity)
2256         __add_back_capacity(__n - __back_capacity);
2257     // __n <= __back_capacity
2258     for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
2259         __alloc_traits::construct(__a, _VSTD::addressof(*__i));
2260 }
2261
2262 template <class _Tp, class _Allocator>
2263 void
2264 deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
2265 {
2266     allocator_type& __a = __base::__alloc();
2267     size_type __back_capacity = __back_spare();
2268     if (__n > __back_capacity)
2269         __add_back_capacity(__n - __back_capacity);
2270     // __n <= __back_capacity
2271     for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
2272         __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
2273 }
2274
2275 // Create front capacity for one block of elements.
2276 // Strong guarantee.  Either do it or don't touch anything.
2277 template <class _Tp, class _Allocator>
2278 void
2279 deque<_Tp, _Allocator>::__add_front_capacity()
2280 {
2281     allocator_type& __a = __base::__alloc();
2282     if (__back_spare() >= __base::__block_size)
2283     {
2284         __base::__start_ += __base::__block_size;
2285         pointer __pt = __base::__map_.back();
2286         __base::__map_.pop_back();
2287         __base::__map_.push_front(__pt);
2288     }
2289     // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer
2290     else if (__base::__map_.size() < __base::__map_.capacity())
2291     {   // we can put the new buffer into the map, but don't shift things around
2292         // until all buffers are allocated.  If we throw, we don't need to fix
2293         // anything up (any added buffers are undetectible)
2294         if (__base::__map_.__front_spare() > 0)
2295             __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2296         else
2297         {
2298             __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2299             // Done allocating, reorder capacity
2300             pointer __pt = __base::__map_.back();
2301             __base::__map_.pop_back();
2302             __base::__map_.push_front(__pt);
2303         }
2304         __base::__start_ = __base::__map_.size() == 1 ?
2305                                __base::__block_size / 2 :
2306                                __base::__start_ + __base::__block_size;
2307     }
2308     // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2309     else
2310     {
2311         __split_buffer<pointer, typename __base::__pointer_allocator&>
2312             __buf(max<size_type>(2 * __base::__map_.capacity(), 1),
2313                   0, __base::__map_.__alloc());
2314
2315         typedef __allocator_destructor<_Allocator> _Dp;
2316         unique_ptr<pointer, _Dp> __hold(
2317             __alloc_traits::allocate(__a, __base::__block_size),
2318                 _Dp(__a, __base::__block_size));
2319         __buf.push_back(__hold.get());
2320         __hold.release();
2321
2322         for (typename __base::__map_pointer __i = __base::__map_.begin();
2323                 __i != __base::__map_.end(); ++__i)
2324             __buf.push_back(*__i);
2325         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2326         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2327         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2328         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2329         __base::__start_ = __base::__map_.size() == 1 ?
2330                                __base::__block_size / 2 :
2331                                __base::__start_ + __base::__block_size;
2332     }
2333 }
2334
2335 // Create front capacity for __n elements.
2336 // Strong guarantee.  Either do it or don't touch anything.
2337 template <class _Tp, class _Allocator>
2338 void
2339 deque<_Tp, _Allocator>::__add_front_capacity(size_type __n)
2340 {
2341     allocator_type& __a = __base::__alloc();
2342     size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2343     // Number of unused blocks at back:
2344     size_type __back_capacity = __back_spare() / __base::__block_size;
2345     __back_capacity = _VSTD::min(__back_capacity, __nb);  // don't take more than you need
2346     __nb -= __back_capacity;  // number of blocks need to allocate
2347     // If __nb == 0, then we have sufficient capacity.
2348     if (__nb == 0)
2349     {
2350         __base::__start_ += __base::__block_size * __back_capacity;
2351         for (; __back_capacity > 0; --__back_capacity)
2352         {
2353             pointer __pt = __base::__map_.back();
2354             __base::__map_.pop_back();
2355             __base::__map_.push_front(__pt);
2356         }
2357     }
2358     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2359     else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2360     {   // we can put the new buffers into the map, but don't shift things around
2361         // until all buffers are allocated.  If we throw, we don't need to fix
2362         // anything up (any added buffers are undetectible)
2363         for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1))
2364         {
2365             if (__base::__map_.__front_spare() == 0)
2366                 break;
2367             __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2368         }
2369         for (; __nb > 0; --__nb, ++__back_capacity)
2370             __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2371         // Done allocating, reorder capacity
2372         __base::__start_ += __back_capacity * __base::__block_size;
2373         for (; __back_capacity > 0; --__back_capacity)
2374         {
2375             pointer __pt = __base::__map_.back();
2376             __base::__map_.pop_back();
2377             __base::__map_.push_front(__pt);
2378         }
2379     }
2380     // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2381     else
2382     {
2383         size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty();
2384         __split_buffer<pointer, typename __base::__pointer_allocator&>
2385             __buf(max<size_type>(2* __base::__map_.capacity(),
2386                                  __nb + __base::__map_.size()),
2387                   0, __base::__map_.__alloc());
2388 #ifndef _LIBCPP_NO_EXCEPTIONS
2389         try
2390         {
2391 #endif  // _LIBCPP_NO_EXCEPTIONS
2392             for (; __nb > 0; --__nb)
2393                 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2394 #ifndef _LIBCPP_NO_EXCEPTIONS
2395         }
2396         catch (...)
2397         {
2398             for (typename __base::__map_pointer __i = __buf.begin();
2399                     __i != __buf.end(); ++__i)
2400                 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2401             throw;
2402         }
2403 #endif  // _LIBCPP_NO_EXCEPTIONS
2404         for (; __back_capacity > 0; --__back_capacity)
2405         {
2406             __buf.push_back(__base::__map_.back());
2407             __base::__map_.pop_back();
2408         }
2409         for (typename __base::__map_pointer __i = __base::__map_.begin();
2410                 __i != __base::__map_.end(); ++__i)
2411             __buf.push_back(*__i);
2412         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2413         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2414         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2415         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2416         __base::__start_ += __ds;
2417     }
2418 }
2419
2420 // Create back capacity for one block of elements.
2421 // Strong guarantee.  Either do it or don't touch anything.
2422 template <class _Tp, class _Allocator>
2423 void
2424 deque<_Tp, _Allocator>::__add_back_capacity()
2425 {
2426     allocator_type& __a = __base::__alloc();
2427     if (__front_spare() >= __base::__block_size)
2428     {
2429         __base::__start_ -= __base::__block_size;
2430         pointer __pt = __base::__map_.front();
2431         __base::__map_.pop_front();
2432         __base::__map_.push_back(__pt);
2433     }
2434     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2435     else if (__base::__map_.size() < __base::__map_.capacity())
2436     {   // we can put the new buffer into the map, but don't shift things around
2437         // until it is allocated.  If we throw, we don't need to fix
2438         // anything up (any added buffers are undetectible)
2439         if (__base::__map_.__back_spare() != 0)
2440             __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2441         else
2442         {
2443             __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2444             // Done allocating, reorder capacity
2445             pointer __pt = __base::__map_.front();
2446             __base::__map_.pop_front();
2447             __base::__map_.push_back(__pt);
2448         }
2449     }
2450     // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2451     else
2452     {
2453         __split_buffer<pointer, typename __base::__pointer_allocator&>
2454             __buf(max<size_type>(2* __base::__map_.capacity(), 1),
2455                   __base::__map_.size(),
2456                   __base::__map_.__alloc());
2457
2458         typedef __allocator_destructor<_Allocator> _Dp;
2459         unique_ptr<pointer, _Dp> __hold(
2460             __alloc_traits::allocate(__a, __base::__block_size),
2461                 _Dp(__a, __base::__block_size));
2462         __buf.push_back(__hold.get());
2463         __hold.release();
2464
2465         for (typename __base::__map_pointer __i = __base::__map_.end();
2466                 __i != __base::__map_.begin();)
2467             __buf.push_front(*--__i);
2468         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2469         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2470         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2471         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2472     }
2473 }
2474
2475 // Create back capacity for __n elements.
2476 // Strong guarantee.  Either do it or don't touch anything.
2477 template <class _Tp, class _Allocator>
2478 void
2479 deque<_Tp, _Allocator>::__add_back_capacity(size_type __n)
2480 {
2481     allocator_type& __a = __base::__alloc();
2482     size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2483     // Number of unused blocks at front:
2484     size_type __front_capacity = __front_spare() / __base::__block_size;
2485     __front_capacity = _VSTD::min(__front_capacity, __nb);  // don't take more than you need
2486     __nb -= __front_capacity;  // number of blocks need to allocate
2487     // If __nb == 0, then we have sufficient capacity.
2488     if (__nb == 0)
2489     {
2490         __base::__start_ -= __base::__block_size * __front_capacity;
2491         for (; __front_capacity > 0; --__front_capacity)
2492         {
2493             pointer __pt = __base::__map_.front();
2494             __base::__map_.pop_front();
2495             __base::__map_.push_back(__pt);
2496         }
2497     }
2498     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2499     else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2500     {   // we can put the new buffers into the map, but don't shift things around
2501         // until all buffers are allocated.  If we throw, we don't need to fix
2502         // anything up (any added buffers are undetectible)
2503         for (; __nb > 0; --__nb)
2504         {
2505             if (__base::__map_.__back_spare() == 0)
2506                 break;
2507             __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2508         }
2509         for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ +=
2510                                  __base::__block_size - (__base::__map_.size() == 1))
2511             __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2512         // Done allocating, reorder capacity
2513         __base::__start_ -= __base::__block_size * __front_capacity;
2514         for (; __front_capacity > 0; --__front_capacity)
2515         {
2516             pointer __pt = __base::__map_.front();
2517             __base::__map_.pop_front();
2518             __base::__map_.push_back(__pt);
2519         }
2520     }
2521     // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2522     else
2523     {
2524         size_type __ds = __front_capacity * __base::__block_size;
2525         __split_buffer<pointer, typename __base::__pointer_allocator&>
2526             __buf(max<size_type>(2* __base::__map_.capacity(),
2527                                  __nb + __base::__map_.size()),
2528                   __base::__map_.size() - __front_capacity,
2529                   __base::__map_.__alloc());
2530 #ifndef _LIBCPP_NO_EXCEPTIONS
2531         try
2532         {
2533 #endif  // _LIBCPP_NO_EXCEPTIONS
2534             for (; __nb > 0; --__nb)
2535                 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2536 #ifndef _LIBCPP_NO_EXCEPTIONS
2537         }
2538         catch (...)
2539         {
2540             for (typename __base::__map_pointer __i = __buf.begin();
2541                     __i != __buf.end(); ++__i)
2542                 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2543             throw;
2544         }
2545 #endif  // _LIBCPP_NO_EXCEPTIONS
2546         for (; __front_capacity > 0; --__front_capacity)
2547         {
2548             __buf.push_back(__base::__map_.front());
2549             __base::__map_.pop_front();
2550         }
2551         for (typename __base::__map_pointer __i = __base::__map_.end();
2552                 __i != __base::__map_.begin();)
2553             __buf.push_front(*--__i);
2554         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2555         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2556         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2557         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2558         __base::__start_ -= __ds;
2559     }
2560 }
2561
2562 template <class _Tp, class _Allocator>
2563 void
2564 deque<_Tp, _Allocator>::pop_front()
2565 {
2566     allocator_type& __a = __base::__alloc();
2567     __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2568                                                     __base::__start_ / __base::__block_size) +
2569                                                     __base::__start_ % __base::__block_size));
2570     --__base::size();
2571     if (++__base::__start_ >= 2 * __base::__block_size)
2572     {
2573         __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2574         __base::__map_.pop_front();
2575         __base::__start_ -= __base::__block_size;
2576     }
2577 }
2578
2579 template <class _Tp, class _Allocator>
2580 void
2581 deque<_Tp, _Allocator>::pop_back()
2582 {
2583     allocator_type& __a = __base::__alloc();
2584     size_type __p = __base::size() + __base::__start_ - 1;
2585     __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2586                                                     __p / __base::__block_size) +
2587                                                     __p % __base::__block_size));
2588     --__base::size();
2589     if (__back_spare() >= 2 * __base::__block_size)
2590     {
2591         __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2592         __base::__map_.pop_back();
2593     }
2594 }
2595
2596 // move assign [__f, __l) to [__r, __r + (__l-__f)).
2597 // If __vt points into [__f, __l), then subtract (__f - __r) from __vt.
2598 template <class _Tp, class _Allocator>
2599 typename deque<_Tp, _Allocator>::iterator
2600 deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r,
2601                                          const_pointer& __vt)
2602 {
2603     // as if
2604     //   for (; __f != __l; ++__f, ++__r)
2605     //       *__r = _VSTD::move(*__f);
2606     difference_type __n = __l - __f;
2607     while (__n > 0)
2608     {
2609         pointer __fb = __f.__ptr_;
2610         pointer __fe = *__f.__m_iter_ + __base::__block_size;
2611         difference_type __bs = __fe - __fb;
2612         if (__bs > __n)
2613         {
2614             __bs = __n;
2615             __fe = __fb + __bs;
2616         }
2617         if (__fb <= __vt && __vt < __fe)
2618             __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;
2619         __r = _VSTD::move(__fb, __fe, __r);
2620         __n -= __bs;
2621         __f += __bs;
2622     }
2623     return __r;
2624 }
2625
2626 // move assign [__f, __l) to [__r - (__l-__f), __r) backwards.
2627 // If __vt points into [__f, __l), then add (__r - __l) to __vt.
2628 template <class _Tp, class _Allocator>
2629 typename deque<_Tp, _Allocator>::iterator
2630 deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r,
2631                                                   const_pointer& __vt)
2632 {
2633     // as if
2634     //   while (__f != __l)
2635     //       *--__r = _VSTD::move(*--__l);
2636     difference_type __n = __l - __f;
2637     while (__n > 0)
2638     {
2639         --__l;
2640         pointer __lb = *__l.__m_iter_;
2641         pointer __le = __l.__ptr_ + 1;
2642         difference_type __bs = __le - __lb;
2643         if (__bs > __n)
2644         {
2645             __bs = __n;
2646             __lb = __le - __bs;
2647         }
2648         if (__lb <= __vt && __vt < __le)
2649             __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_;
2650         __r = _VSTD::move_backward(__lb, __le, __r);
2651         __n -= __bs;
2652         __l -= __bs - 1;
2653     }
2654     return __r;
2655 }
2656
2657 // move construct [__f, __l) to [__r, __r + (__l-__f)).
2658 // If __vt points into [__f, __l), then add (__r - __f) to __vt.
2659 template <class _Tp, class _Allocator>
2660 void
2661 deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l,
2662                                                    iterator __r, const_pointer& __vt)
2663 {
2664     allocator_type& __a = __base::__alloc();
2665     // as if
2666     //   for (; __f != __l; ++__r, ++__f, ++__base::size())
2667     //       __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f));
2668     difference_type __n = __l - __f;
2669     while (__n > 0)
2670     {
2671         pointer __fb = __f.__ptr_;
2672         pointer __fe = *__f.__m_iter_ + __base::__block_size;
2673         difference_type __bs = __fe - __fb;
2674         if (__bs > __n)
2675         {
2676             __bs = __n;
2677             __fe = __fb + __bs;
2678         }
2679         if (__fb <= __vt && __vt < __fe)
2680             __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;
2681         for (; __fb != __fe; ++__fb, ++__r, ++__base::size())
2682             __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb));
2683         __n -= __bs;
2684         __f += __bs;
2685     }
2686 }
2687
2688 // move construct [__f, __l) to [__r - (__l-__f), __r) backwards.
2689 // If __vt points into [__f, __l), then subtract (__l - __r) from __vt.
2690 template <class _Tp, class _Allocator>
2691 void
2692 deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l,
2693                                                             iterator __r, const_pointer& __vt)
2694 {
2695     allocator_type& __a = __base::__alloc();
2696     // as if
2697     //   for (iterator __j = __l; __j != __f;)
2698     //   {
2699     //       __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j));
2700     //       --__base::__start_;
2701     //       ++__base::size();
2702     //   }
2703     difference_type __n = __l - __f;
2704     while (__n > 0)
2705     {
2706         --__l;
2707         pointer __lb = *__l.__m_iter_;
2708         pointer __le = __l.__ptr_ + 1;
2709         difference_type __bs = __le - __lb;
2710         if (__bs > __n)
2711         {
2712             __bs = __n;
2713             __lb = __le - __bs;
2714         }
2715         if (__lb <= __vt && __vt < __le)
2716             __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;
2717         while (__le != __lb)
2718         {
2719             __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le));
2720             --__base::__start_;
2721             ++__base::size();
2722         }
2723         __n -= __bs;
2724         __l -= __bs - 1;
2725     }
2726 }
2727
2728 template <class _Tp, class _Allocator>
2729 typename deque<_Tp, _Allocator>::iterator
2730 deque<_Tp, _Allocator>::erase(const_iterator __f)
2731 {
2732     iterator __b = __base::begin();
2733     difference_type __pos = __f - __b;
2734     iterator __p = __b + __pos;
2735     allocator_type& __a = __base::__alloc();
2736     if (static_cast<size_t>(__pos) <= (__base::size() - 1) / 2)
2737     {   // erase from front
2738         _VSTD::move_backward(__b, __p, _VSTD::next(__p));
2739         __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2740         --__base::size();
2741         ++__base::__start_;
2742         if (__front_spare() >= 2 * __base::__block_size)
2743         {
2744             __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2745             __base::__map_.pop_front();
2746             __base::__start_ -= __base::__block_size;
2747         }
2748     }
2749     else
2750     {   // erase from back
2751         iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
2752         __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2753         --__base::size();
2754         if (__back_spare() >= 2 * __base::__block_size)
2755         {
2756             __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2757             __base::__map_.pop_back();
2758         }
2759     }
2760     return __base::begin() + __pos;
2761 }
2762
2763 template <class _Tp, class _Allocator>
2764 typename deque<_Tp, _Allocator>::iterator
2765 deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
2766 {
2767     difference_type __n = __l - __f;
2768     iterator __b = __base::begin();
2769     difference_type __pos = __f - __b;
2770     iterator __p = __b + __pos;
2771     if (__n > 0)
2772     {
2773         allocator_type& __a = __base::__alloc();
2774         if (static_cast<size_t>(__pos) <= (__base::size() - __n) / 2)
2775         {   // erase from front
2776             iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
2777             for (; __b != __i; ++__b)
2778                 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2779             __base::size() -= __n;
2780             __base::__start_ += __n;
2781             while (__front_spare() >= 2 * __base::__block_size)
2782             {
2783                 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2784                 __base::__map_.pop_front();
2785                 __base::__start_ -= __base::__block_size;
2786             }
2787         }
2788         else
2789         {   // erase from back
2790             iterator __i = _VSTD::move(__p + __n, __base::end(), __p);
2791             for (iterator __e = __base::end(); __i != __e; ++__i)
2792                 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2793             __base::size() -= __n;
2794             while (__back_spare() >= 2 * __base::__block_size)
2795             {
2796                 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2797                 __base::__map_.pop_back();
2798             }
2799         }
2800     }
2801     return __base::begin() + __pos;
2802 }
2803
2804 template <class _Tp, class _Allocator>
2805 void
2806 deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
2807 {
2808     iterator __e = __base::end();
2809     difference_type __n = __e - __f;
2810     if (__n > 0)
2811     {
2812         allocator_type& __a = __base::__alloc();
2813         iterator __b = __base::begin();
2814         difference_type __pos = __f - __b;
2815         for (iterator __p = __b + __pos; __p != __e; ++__p)
2816             __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
2817         __base::size() -= __n;
2818         while (__back_spare() >= 2 * __base::__block_size)
2819         {
2820             __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2821             __base::__map_.pop_back();
2822         }
2823     }
2824 }
2825
2826 template <class _Tp, class _Allocator>
2827 inline
2828 void
2829 deque<_Tp, _Allocator>::swap(deque& __c)
2830 #if _LIBCPP_STD_VER >= 14
2831         _NOEXCEPT
2832 #else
2833         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2834                     __is_nothrow_swappable<allocator_type>::value)
2835 #endif
2836 {
2837     __base::swap(__c);
2838 }
2839
2840 template <class _Tp, class _Allocator>
2841 inline
2842 void
2843 deque<_Tp, _Allocator>::clear() _NOEXCEPT
2844 {
2845     __base::clear();
2846 }
2847
2848 template <class _Tp, class _Allocator>
2849 inline _LIBCPP_INLINE_VISIBILITY
2850 bool
2851 operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2852 {
2853     const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();
2854     return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2855 }
2856
2857 template <class _Tp, class _Allocator>
2858 inline _LIBCPP_INLINE_VISIBILITY
2859 bool
2860 operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2861 {
2862     return !(__x == __y);
2863 }
2864
2865 template <class _Tp, class _Allocator>
2866 inline _LIBCPP_INLINE_VISIBILITY
2867 bool
2868 operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2869 {
2870     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2871 }
2872
2873 template <class _Tp, class _Allocator>
2874 inline _LIBCPP_INLINE_VISIBILITY
2875 bool
2876 operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2877 {
2878     return __y < __x;
2879 }
2880
2881 template <class _Tp, class _Allocator>
2882 inline _LIBCPP_INLINE_VISIBILITY
2883 bool
2884 operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2885 {
2886     return !(__x < __y);
2887 }
2888
2889 template <class _Tp, class _Allocator>
2890 inline _LIBCPP_INLINE_VISIBILITY
2891 bool
2892 operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2893 {
2894     return !(__y < __x);
2895 }
2896
2897 template <class _Tp, class _Allocator>
2898 inline _LIBCPP_INLINE_VISIBILITY
2899 void
2900 swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y)
2901     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2902 {
2903     __x.swap(__y);
2904 }
2905
2906 _LIBCPP_END_NAMESPACE_STD
2907
2908 _LIBCPP_POP_MACROS
2909
2910 #endif  // _LIBCPP_DEQUE