contrib/llvm-project/libcxx/include/deque

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