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