libcxx/include/deque

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