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_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_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_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_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_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_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_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_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_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_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_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_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 protected:
 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 protected:
 960     __map __map_;
 961     size_type __start_;
 962     __compressed_pair<size_type, allocator_type> __size_;
 963
 964     iterator       begin() _NOEXCEPT;
 965     const_iterator begin() const _NOEXCEPT;
 966     iterator       end() _NOEXCEPT;
 967     const_iterator end() const _NOEXCEPT;
 968
 969     _LIBCPP_INLINE_VISIBILITY size_type&            size()          {return __size_.first();}
 970     _LIBCPP_INLINE_VISIBILITY
 971     const size_type& size() const _NOEXCEPT {return __size_.first();}
 972     _LIBCPP_INLINE_VISIBILITY allocator_type&       __alloc()       {return __size_.second();}
 973     _LIBCPP_INLINE_VISIBILITY
 974     const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();}
 975
 976     _LIBCPP_INLINE_VISIBILITY
 977     __deque_base()
 978         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
 979     _LIBCPP_INLINE_VISIBILITY
 980     explicit __deque_base(const allocator_type& __a);
 981 public:
 982     ~__deque_base();
 983
 984 #ifndef _LIBCPP_CXX03_LANG
 985     __deque_base(__deque_base&& __c)
 986         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
 987     __deque_base(__deque_base&& __c, const allocator_type& __a);
 988 #endif  // _LIBCPP_CXX03_LANG
 989
 990     void swap(__deque_base& __c)
 991 #if _LIBCPP_STD_VER >= 14
 992         _NOEXCEPT;
 993 #else
 994         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
 995                     __is_nothrow_swappable<allocator_type>::value);
 996 #endif
 997 protected:
 998     void clear() _NOEXCEPT;
 999
1000     bool __invariants() const;
1001
1002     _LIBCPP_INLINE_VISIBILITY
1003     void __move_assign(__deque_base& __c)
1004         _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1005                    is_nothrow_move_assignable<allocator_type>::value)
1006     {
1007         __map_ = _VSTD::move(__c.__map_);
1008         __start_ = __c.__start_;
1009         size() = __c.size();
1010         __move_assign_alloc(__c);
1011         __c.__start_ = __c.size() = 0;
1012     }
1013
1014     _LIBCPP_INLINE_VISIBILITY
1015     void __move_assign_alloc(__deque_base& __c)
1016         _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
1017                    is_nothrow_move_assignable<allocator_type>::value)
1018         {__move_assign_alloc(__c, integral_constant<bool,
1019                       __alloc_traits::propagate_on_container_move_assignment::value>());}
1020
1021 private:
1022     _LIBCPP_INLINE_VISIBILITY
1023     void __move_assign_alloc(__deque_base& __c, true_type)
1024         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1025         {
1026             __alloc() = _VSTD::move(__c.__alloc());
1027         }
1028
1029     _LIBCPP_INLINE_VISIBILITY
1030     void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT
1031         {}
1032 };
1033
1034 template <class _Tp, class _Allocator>
1035 const typename __deque_base<_Tp, _Allocator>::difference_type
1036     __deque_base<_Tp, _Allocator>::__block_size =
1037         __deque_block_size<value_type, difference_type>::value;
1038
1039 template <class _Tp, class _Allocator>
1040 bool
1041 __deque_base<_Tp, _Allocator>::__invariants() const
1042 {
1043     if (!__map_.__invariants())
1044         return false;
1045     if (__map_.size() >= size_type(-1) / __block_size)
1046         return false;
1047     for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();
1048          __i != __e; ++__i)
1049         if (*__i == nullptr)
1050             return false;
1051     if (__map_.size() != 0)
1052     {
1053         if (size() >= __map_.size() * __block_size)
1054             return false;
1055         if (__start_ >= __map_.size() * __block_size - size())
1056             return false;
1057     }
1058     else
1059     {
1060         if (size() != 0)
1061             return false;
1062         if (__start_ != 0)
1063             return false;
1064     }
1065     return true;
1066 }
1067
1068 template <class _Tp, class _Allocator>
1069 typename __deque_base<_Tp, _Allocator>::iterator
1070 __deque_base<_Tp, _Allocator>::begin() _NOEXCEPT
1071 {
1072     __map_pointer __mp = __map_.begin() + __start_ / __block_size;
1073     return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1074 }
1075
1076 template <class _Tp, class _Allocator>
1077 typename __deque_base<_Tp, _Allocator>::const_iterator
1078 __deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT
1079 {
1080     __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);
1081     return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1082 }
1083
1084 template <class _Tp, class _Allocator>
1085 typename __deque_base<_Tp, _Allocator>::iterator
1086 __deque_base<_Tp, _Allocator>::end() _NOEXCEPT
1087 {
1088     size_type __p = size() + __start_;
1089     __map_pointer __mp = __map_.begin() + __p / __block_size;
1090     return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1091 }
1092
1093 template <class _Tp, class _Allocator>
1094 typename __deque_base<_Tp, _Allocator>::const_iterator
1095 __deque_base<_Tp, _Allocator>::end() const _NOEXCEPT
1096 {
1097     size_type __p = size() + __start_;
1098     __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);
1099     return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1100 }
1101
1102 template <class _Tp, class _Allocator>
1103 inline
1104 __deque_base<_Tp, _Allocator>::__deque_base()
1105     _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1106     : __start_(0), __size_(0) {}
1107
1108 template <class _Tp, class _Allocator>
1109 inline
1110 __deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a)
1111     : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}
1112
1113 template <class _Tp, class _Allocator>
1114 __deque_base<_Tp, _Allocator>::~__deque_base()
1115 {
1116     clear();
1117     typename __map::iterator __i = __map_.begin();
1118     typename __map::iterator __e = __map_.end();
1119     for (; __i != __e; ++__i)
1120         __alloc_traits::deallocate(__alloc(), *__i, __block_size);
1121 }
1122
1123 #ifndef _LIBCPP_CXX03_LANG
1124
1125 template <class _Tp, class _Allocator>
1126 __deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c)
1127     _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1128     : __map_(_VSTD::move(__c.__map_)),
1129       __start_(_VSTD::move(__c.__start_)),
1130       __size_(_VSTD::move(__c.__size_))
1131 {
1132     __c.__start_ = 0;
1133     __c.size() = 0;
1134 }
1135
1136 template <class _Tp, class _Allocator>
1137 __deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a)
1138     : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)),
1139       __start_(_VSTD::move(__c.__start_)),
1140       __size_(_VSTD::move(__c.size()), __a)
1141 {
1142     if (__a == __c.__alloc())
1143     {
1144         __c.__start_ = 0;
1145         __c.size() = 0;
1146     }
1147     else
1148     {
1149         __map_.clear();
1150         __start_ = 0;
1151         size() = 0;
1152     }
1153 }
1154
1155 #endif  // _LIBCPP_CXX03_LANG
1156
1157 template <class _Tp, class _Allocator>
1158 void
1159 __deque_base<_Tp, _Allocator>::swap(__deque_base& __c)
1160 #if _LIBCPP_STD_VER >= 14
1161         _NOEXCEPT
1162 #else
1163         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1164                     __is_nothrow_swappable<allocator_type>::value)
1165 #endif
1166 {
1167     __map_.swap(__c.__map_);
1168     _VSTD::swap(__start_, __c.__start_);
1169     _VSTD::swap(size(), __c.size());
1170     __swap_allocator(__alloc(), __c.__alloc());
1171 }
1172
1173 template <class _Tp, class _Allocator>
1174 void
1175 __deque_base<_Tp, _Allocator>::clear() _NOEXCEPT
1176 {
1177     allocator_type& __a = __alloc();
1178     for (iterator __i = begin(), __e = end(); __i != __e; ++__i)
1179         __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
1180     size() = 0;
1181     while (__map_.size() > 2)
1182     {
1183         __alloc_traits::deallocate(__a, __map_.front(), __block_size);
1184         __map_.pop_front();
1185     }
1186     switch (__map_.size())
1187     {
1188     case 1:
1189         __start_ = __block_size / 2;
1190         break;
1191     case 2:
1192         __start_ = __block_size;
1193         break;
1194     }
1195 }
1196
1197 template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
1198 class _LIBCPP_TEMPLATE_VIS deque
1199     : private __deque_base<_Tp, _Allocator>
1200 {
1201 public:
1202     // types:
1203
1204     typedef _Tp value_type;
1205     typedef _Allocator allocator_type;
1206
1207     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1208                   "Allocator::value_type must be same type as value_type");
1209
1210     typedef __deque_base<value_type, allocator_type> __base;
1211
1212     typedef typename __base::__alloc_traits        __alloc_traits;
1213     typedef typename __base::reference             reference;
1214     typedef typename __base::const_reference       const_reference;
1215     typedef typename __base::iterator              iterator;
1216     typedef typename __base::const_iterator        const_iterator;
1217     typedef typename __base::size_type             size_type;
1218     typedef typename __base::difference_type       difference_type;
1219
1220     typedef typename __base::pointer               pointer;
1221     typedef typename __base::const_pointer         const_pointer;
1222     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
1223     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1224
1225     // construct/copy/destroy:
1226     _LIBCPP_INLINE_VISIBILITY
1227     deque()
1228         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1229         {}
1230     _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {}
1231     explicit deque(size_type __n);
1232 #if _LIBCPP_STD_VER > 11
1233     explicit deque(size_type __n, const _Allocator& __a);
1234 #endif
1235     deque(size_type __n, const value_type& __v);
1236     deque(size_type __n, const value_type& __v, const allocator_type& __a);
1237     template <class _InputIter>
1238         deque(_InputIter __f, _InputIter __l,
1239               typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1240     template <class _InputIter>
1241         deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1242               typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1243     deque(const deque& __c);
1244     deque(const deque& __c, const allocator_type& __a);
1245
1246     deque& operator=(const deque& __c);
1247
1248 #ifndef _LIBCPP_CXX03_LANG
1249     deque(initializer_list<value_type> __il);
1250     deque(initializer_list<value_type> __il, const allocator_type& __a);
1251
1252     _LIBCPP_INLINE_VISIBILITY
1253     deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
1254
1255     _LIBCPP_INLINE_VISIBILITY
1256     deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
1257     _LIBCPP_INLINE_VISIBILITY
1258     deque(deque&& __c, const allocator_type& __a);
1259     _LIBCPP_INLINE_VISIBILITY
1260     deque& operator=(deque&& __c)
1261         _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1262                    is_nothrow_move_assignable<allocator_type>::value);
1263
1264     _LIBCPP_INLINE_VISIBILITY
1265     void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
1266 #endif  // _LIBCPP_CXX03_LANG
1267
1268     template <class _InputIter>
1269         void assign(_InputIter __f, _InputIter __l,
1270                     typename enable_if<__is_input_iterator<_InputIter>::value &&
1271                                       !__is_random_access_iterator<_InputIter>::value>::type* = 0);
1272     template <class _RAIter>
1273         void assign(_RAIter __f, _RAIter __l,
1274                     typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
1275     void assign(size_type __n, const value_type& __v);
1276
1277     _LIBCPP_INLINE_VISIBILITY
1278     allocator_type get_allocator() const _NOEXCEPT;
1279
1280     // iterators:
1281
1282     _LIBCPP_INLINE_VISIBILITY
1283     iterator       begin() _NOEXCEPT       {return __base::begin();}
1284     _LIBCPP_INLINE_VISIBILITY
1285     const_iterator begin() const _NOEXCEPT {return __base::begin();}
1286     _LIBCPP_INLINE_VISIBILITY
1287     iterator       end() _NOEXCEPT         {return __base::end();}
1288     _LIBCPP_INLINE_VISIBILITY
1289     const_iterator end()   const _NOEXCEPT {return __base::end();}
1290
1291     _LIBCPP_INLINE_VISIBILITY
1292     reverse_iterator       rbegin() _NOEXCEPT
1293         {return       reverse_iterator(__base::end());}
1294     _LIBCPP_INLINE_VISIBILITY
1295     const_reverse_iterator rbegin() const _NOEXCEPT
1296         {return const_reverse_iterator(__base::end());}
1297     _LIBCPP_INLINE_VISIBILITY
1298     reverse_iterator       rend() _NOEXCEPT
1299         {return       reverse_iterator(__base::begin());}
1300     _LIBCPP_INLINE_VISIBILITY
1301     const_reverse_iterator rend()   const _NOEXCEPT
1302         {return const_reverse_iterator(__base::begin());}
1303
1304     _LIBCPP_INLINE_VISIBILITY
1305     const_iterator         cbegin()  const _NOEXCEPT
1306         {return __base::begin();}
1307     _LIBCPP_INLINE_VISIBILITY
1308     const_iterator         cend()    const _NOEXCEPT
1309         {return __base::end();}
1310     _LIBCPP_INLINE_VISIBILITY
1311     const_reverse_iterator crbegin() const _NOEXCEPT
1312         {return const_reverse_iterator(__base::end());}
1313     _LIBCPP_INLINE_VISIBILITY
1314     const_reverse_iterator crend()   const _NOEXCEPT
1315         {return const_reverse_iterator(__base::begin());}
1316
1317     // capacity:
1318     _LIBCPP_INLINE_VISIBILITY
1319     size_type size() const _NOEXCEPT {return __base::size();}
1320     _LIBCPP_INLINE_VISIBILITY
1321     size_type max_size() const _NOEXCEPT
1322         {return std::min<size_type>(
1323             __alloc_traits::max_size(__base::__alloc()),
1324             numeric_limits<difference_type>::max());}
1325     void resize(size_type __n);
1326     void resize(size_type __n, const value_type& __v);
1327     void shrink_to_fit() _NOEXCEPT;
1328     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1329     bool empty() const _NOEXCEPT {return __base::size() == 0;}
1330
1331     // element access:
1332     _LIBCPP_INLINE_VISIBILITY
1333     reference operator[](size_type __i) _NOEXCEPT;
1334     _LIBCPP_INLINE_VISIBILITY
1335     const_reference operator[](size_type __i) const _NOEXCEPT;
1336     _LIBCPP_INLINE_VISIBILITY
1337     reference at(size_type __i);
1338     _LIBCPP_INLINE_VISIBILITY
1339     const_reference at(size_type __i) const;
1340     _LIBCPP_INLINE_VISIBILITY
1341     reference front() _NOEXCEPT;
1342     _LIBCPP_INLINE_VISIBILITY
1343     const_reference front() const _NOEXCEPT;
1344     _LIBCPP_INLINE_VISIBILITY
1345     reference back() _NOEXCEPT;
1346     _LIBCPP_INLINE_VISIBILITY
1347     const_reference back() const _NOEXCEPT;
1348
1349     // 23.2.2.3 modifiers:
1350     void push_front(const value_type& __v);
1351     void push_back(const value_type& __v);
1352 #ifndef _LIBCPP_CXX03_LANG
1353 #if _LIBCPP_STD_VER > 14
1354     template <class... _Args> reference emplace_front(_Args&&... __args);
1355     template <class... _Args> reference emplace_back (_Args&&... __args);
1356 #else
1357     template <class... _Args> void      emplace_front(_Args&&... __args);
1358     template <class... _Args> void      emplace_back (_Args&&... __args);
1359 #endif
1360     template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args);
1361
1362     void push_front(value_type&& __v);
1363     void push_back(value_type&& __v);
1364     iterator insert(const_iterator __p, value_type&& __v);
1365
1366     _LIBCPP_INLINE_VISIBILITY
1367     iterator insert(const_iterator __p, initializer_list<value_type> __il)
1368         {return insert(__p, __il.begin(), __il.end());}
1369 #endif  // _LIBCPP_CXX03_LANG
1370     iterator insert(const_iterator __p, const value_type& __v);
1371     iterator insert(const_iterator __p, size_type __n, const value_type& __v);
1372     template <class _InputIter>
1373         iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
1374                          typename enable_if<__is_input_iterator<_InputIter>::value
1375                                          &&!__is_forward_iterator<_InputIter>::value>::type* = 0);
1376     template <class _ForwardIterator>
1377         iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
1378                                typename enable_if<__is_forward_iterator<_ForwardIterator>::value
1379                                          &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type* = 0);
1380     template <class _BiIter>
1381         iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
1382                          typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type* = 0);
1383
1384     void pop_front();
1385     void pop_back();
1386     iterator erase(const_iterator __p);
1387     iterator erase(const_iterator __f, const_iterator __l);
1388
1389     _LIBCPP_INLINE_VISIBILITY
1390     void swap(deque& __c)
1391 #if _LIBCPP_STD_VER >= 14
1392         _NOEXCEPT;
1393 #else
1394         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1395                    __is_nothrow_swappable<allocator_type>::value);
1396 #endif
1397     _LIBCPP_INLINE_VISIBILITY
1398     void clear() _NOEXCEPT;
1399
1400     _LIBCPP_INLINE_VISIBILITY
1401     bool __invariants() const {return __base::__invariants();}
1402 private:
1403     typedef typename __base::__map_const_pointer __map_const_pointer;
1404
1405     _LIBCPP_INLINE_VISIBILITY
1406     static size_type __recommend_blocks(size_type __n)
1407     {
1408         return __n / __base::__block_size + (__n % __base::__block_size != 0);
1409     }
1410     _LIBCPP_INLINE_VISIBILITY
1411     size_type __capacity() const
1412     {
1413         return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
1414     }
1415     _LIBCPP_INLINE_VISIBILITY
1416     size_type __front_spare() const
1417     {
1418         return __base::__start_;
1419     }
1420     _LIBCPP_INLINE_VISIBILITY
1421     size_type __back_spare() const
1422     {
1423         return __capacity() - (__base::__start_ + __base::size());
1424     }
1425
1426     template <class _InpIter>
1427         void __append(_InpIter __f, _InpIter __l,
1428                  typename enable_if<__is_input_iterator<_InpIter>::value &&
1429                                    !__is_forward_iterator<_InpIter>::value>::type* = 0);
1430     template <class _ForIter>
1431         void __append(_ForIter __f, _ForIter __l,
1432                       typename enable_if<__is_forward_iterator<_ForIter>::value>::type* = 0);
1433     void __append(size_type __n);
1434     void __append(size_type __n, const value_type& __v);
1435     void __erase_to_end(const_iterator __f);
1436     void __add_front_capacity();
1437     void __add_front_capacity(size_type __n);
1438     void __add_back_capacity();
1439     void __add_back_capacity(size_type __n);
1440     iterator __move_and_check(iterator __f, iterator __l, iterator __r,
1441                               const_pointer& __vt);
1442     iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r,
1443                                        const_pointer& __vt);
1444     void __move_construct_and_check(iterator __f, iterator __l,
1445                                     iterator __r, const_pointer& __vt);
1446     void __move_construct_backward_and_check(iterator __f, iterator __l,
1447                                              iterator __r, const_pointer& __vt);
1448
1449     _LIBCPP_INLINE_VISIBILITY
1450     void __copy_assign_alloc(const deque& __c)
1451         {__copy_assign_alloc(__c, integral_constant<bool,
1452                       __alloc_traits::propagate_on_container_copy_assignment::value>());}
1453
1454     _LIBCPP_INLINE_VISIBILITY
1455     void __copy_assign_alloc(const deque& __c, true_type)
1456         {
1457             if (__base::__alloc() != __c.__alloc())
1458             {
1459                 clear();
1460                 shrink_to_fit();
1461             }
1462             __base::__alloc() = __c.__alloc();
1463             __base::__map_.__alloc() = __c.__map_.__alloc();
1464         }
1465
1466     _LIBCPP_INLINE_VISIBILITY
1467     void __copy_assign_alloc(const deque&, false_type)
1468         {}
1469
1470     void __move_assign(deque& __c, true_type)
1471         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
1472     void __move_assign(deque& __c, false_type);
1473 };
1474
1475 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1476 template<class _InputIterator,
1477          class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
1478          class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
1479          >
1480 deque(_InputIterator, _InputIterator)
1481   -> deque<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
1482
1483 template<class _InputIterator,
1484          class _Alloc,
1485          class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
1486          >
1487 deque(_InputIterator, _InputIterator, _Alloc)
1488   -> deque<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
1489 #endif
1490
1491
1492 template <class _Tp, class _Allocator>
1493 deque<_Tp, _Allocator>::deque(size_type __n)
1494 {
1495     if (__n > 0)
1496         __append(__n);
1497 }
1498
1499 #if _LIBCPP_STD_VER > 11
1500 template <class _Tp, class _Allocator>
1501 deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a)
1502     : __base(__a)
1503 {
1504     if (__n > 0)
1505         __append(__n);
1506 }
1507 #endif
1508
1509 template <class _Tp, class _Allocator>
1510 deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)
1511 {
1512     if (__n > 0)
1513         __append(__n, __v);
1514 }
1515
1516 template <class _Tp, class _Allocator>
1517 deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a)
1518     : __base(__a)
1519 {
1520     if (__n > 0)
1521         __append(__n, __v);
1522 }
1523
1524 template <class _Tp, class _Allocator>
1525 template <class _InputIter>
1526 deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l,
1527               typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1528 {
1529     __append(__f, __l);
1530 }
1531
1532 template <class _Tp, class _Allocator>
1533 template <class _InputIter>
1534 deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1535               typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1536     : __base(__a)
1537 {
1538     __append(__f, __l);
1539 }
1540
1541 template <class _Tp, class _Allocator>
1542 deque<_Tp, _Allocator>::deque(const deque& __c)
1543     : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))
1544 {
1545     __append(__c.begin(), __c.end());
1546 }
1547
1548 template <class _Tp, class _Allocator>
1549 deque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a)
1550     : __base(__a)
1551 {
1552     __append(__c.begin(), __c.end());
1553 }
1554
1555 template <class _Tp, class _Allocator>
1556 deque<_Tp, _Allocator>&
1557 deque<_Tp, _Allocator>::operator=(const deque& __c)
1558 {
1559     if (this != &__c)
1560     {
1561         __copy_assign_alloc(__c);
1562         assign(__c.begin(), __c.end());
1563     }
1564     return *this;
1565 }
1566
1567 #ifndef _LIBCPP_CXX03_LANG
1568
1569 template <class _Tp, class _Allocator>
1570 deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)
1571 {
1572     __append(__il.begin(), __il.end());
1573 }
1574
1575 template <class _Tp, class _Allocator>
1576 deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a)
1577     : __base(__a)
1578 {
1579     __append(__il.begin(), __il.end());
1580 }
1581
1582 template <class _Tp, class _Allocator>
1583 inline
1584 deque<_Tp, _Allocator>::deque(deque&& __c)
1585     _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1586     : __base(_VSTD::move(__c))
1587 {
1588 }
1589
1590 template <class _Tp, class _Allocator>
1591 inline
1592 deque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a)
1593     : __base(_VSTD::move(__c), __a)
1594 {
1595     if (__a != __c.__alloc())
1596     {
1597         typedef move_iterator<iterator> _Ip;
1598         assign(_Ip(__c.begin()), _Ip(__c.end()));
1599     }
1600 }
1601
1602 template <class _Tp, class _Allocator>
1603 inline
1604 deque<_Tp, _Allocator>&
1605 deque<_Tp, _Allocator>::operator=(deque&& __c)
1606         _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1607                    is_nothrow_move_assignable<allocator_type>::value)
1608 {
1609     __move_assign(__c, integral_constant<bool,
1610           __alloc_traits::propagate_on_container_move_assignment::value>());
1611     return *this;
1612 }
1613
1614 template <class _Tp, class _Allocator>
1615 void
1616 deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type)
1617 {
1618     if (__base::__alloc() != __c.__alloc())
1619     {
1620         typedef move_iterator<iterator> _Ip;
1621         assign(_Ip(__c.begin()), _Ip(__c.end()));
1622     }
1623     else
1624         __move_assign(__c, true_type());
1625 }
1626
1627 template <class _Tp, class _Allocator>
1628 void
1629 deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type)
1630     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1631 {
1632     clear();
1633     shrink_to_fit();
1634     __base::__move_assign(__c);
1635 }
1636
1637 #endif  // _LIBCPP_CXX03_LANG
1638
1639 template <class _Tp, class _Allocator>
1640 template <class _InputIter>
1641 void
1642 deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
1643                                typename enable_if<__is_input_iterator<_InputIter>::value &&
1644                                                  !__is_random_access_iterator<_InputIter>::value>::type*)
1645 {
1646     iterator __i = __base::begin();
1647     iterator __e = __base::end();
1648     for (; __f != __l && __i != __e; ++__f, (void) ++__i)
1649         *__i = *__f;
1650     if (__f != __l)
1651         __append(__f, __l);
1652     else
1653         __erase_to_end(__i);
1654 }
1655
1656 template <class _Tp, class _Allocator>
1657 template <class _RAIter>
1658 void
1659 deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
1660                                typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
1661 {
1662     if (static_cast<size_type>(__l - __f) > __base::size())
1663     {
1664         _RAIter __m = __f + __base::size();
1665         _VSTD::copy(__f, __m, __base::begin());
1666         __append(__m, __l);
1667     }
1668     else
1669         __erase_to_end(_VSTD::copy(__f, __l, __base::begin()));
1670 }
1671
1672 template <class _Tp, class _Allocator>
1673 void
1674 deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
1675 {
1676     if (__n > __base::size())
1677     {
1678         _VSTD::fill_n(__base::begin(), __base::size(), __v);
1679         __n -= __base::size();
1680         __append(__n, __v);
1681     }
1682     else
1683         __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v));
1684 }
1685
1686 template <class _Tp, class _Allocator>
1687 inline
1688 _Allocator
1689 deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
1690 {
1691     return __base::__alloc();
1692 }
1693
1694 template <class _Tp, class _Allocator>
1695 void
1696 deque<_Tp, _Allocator>::resize(size_type __n)
1697 {
1698     if (__n > __base::size())
1699         __append(__n - __base::size());
1700     else if (__n < __base::size())
1701         __erase_to_end(__base::begin() + __n);
1702 }
1703
1704 template <class _Tp, class _Allocator>
1705 void
1706 deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v)
1707 {
1708     if (__n > __base::size())
1709         __append(__n - __base::size(), __v);
1710     else if (__n < __base::size())
1711         __erase_to_end(__base::begin() + __n);
1712 }
1713
1714 template <class _Tp, class _Allocator>
1715 void
1716 deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1717 {
1718     allocator_type& __a = __base::__alloc();
1719     if (empty())
1720     {
1721         while (__base::__map_.size() > 0)
1722         {
1723             __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1724             __base::__map_.pop_back();
1725         }
1726         __base::__start_ = 0;
1727     }
1728     else
1729     {
1730         if (__front_spare() >= __base::__block_size)
1731         {
1732             __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
1733             __base::__map_.pop_front();
1734             __base::__start_ -= __base::__block_size;
1735         }
1736         if (__back_spare() >= __base::__block_size)
1737         {
1738             __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1739             __base::__map_.pop_back();
1740         }
1741     }
1742     __base::__map_.shrink_to_fit();
1743 }
1744
1745 template <class _Tp, class _Allocator>
1746 inline
1747 typename deque<_Tp, _Allocator>::reference
1748 deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT
1749 {
1750     size_type __p = __base::__start_ + __i;
1751     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1752 }
1753
1754 template <class _Tp, class _Allocator>
1755 inline
1756 typename deque<_Tp, _Allocator>::const_reference
1757 deque<_Tp, _Allocator>::operator[](size_type __i) const _NOEXCEPT
1758 {
1759     size_type __p = __base::__start_ + __i;
1760     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1761 }
1762
1763 template <class _Tp, class _Allocator>
1764 inline
1765 typename deque<_Tp, _Allocator>::reference
1766 deque<_Tp, _Allocator>::at(size_type __i)
1767 {
1768     if (__i >= __base::size())
1769         __base::__throw_out_of_range();
1770     size_type __p = __base::__start_ + __i;
1771     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1772 }
1773
1774 template <class _Tp, class _Allocator>
1775 inline
1776 typename deque<_Tp, _Allocator>::const_reference
1777 deque<_Tp, _Allocator>::at(size_type __i) const
1778 {
1779     if (__i >= __base::size())
1780         __base::__throw_out_of_range();
1781     size_type __p = __base::__start_ + __i;
1782     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1783 }
1784
1785 template <class _Tp, class _Allocator>
1786 inline
1787 typename deque<_Tp, _Allocator>::reference
1788 deque<_Tp, _Allocator>::front() _NOEXCEPT
1789 {
1790     return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1791                                       + __base::__start_ % __base::__block_size);
1792 }
1793
1794 template <class _Tp, class _Allocator>
1795 inline
1796 typename deque<_Tp, _Allocator>::const_reference
1797 deque<_Tp, _Allocator>::front() const _NOEXCEPT
1798 {
1799     return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1800                                       + __base::__start_ % __base::__block_size);
1801 }
1802
1803 template <class _Tp, class _Allocator>
1804 inline
1805 typename deque<_Tp, _Allocator>::reference
1806 deque<_Tp, _Allocator>::back() _NOEXCEPT
1807 {
1808     size_type __p = __base::size() + __base::__start_ - 1;
1809     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1810 }
1811
1812 template <class _Tp, class _Allocator>
1813 inline
1814 typename deque<_Tp, _Allocator>::const_reference
1815 deque<_Tp, _Allocator>::back() const _NOEXCEPT
1816 {
1817     size_type __p = __base::size() + __base::__start_ - 1;
1818     return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1819 }
1820
1821 template <class _Tp, class _Allocator>
1822 void
1823 deque<_Tp, _Allocator>::push_back(const value_type& __v)
1824 {
1825     allocator_type& __a = __base::__alloc();
1826     if (__back_spare() == 0)
1827         __add_back_capacity();
1828     // __back_spare() >= 1
1829     __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
1830     ++__base::size();
1831 }
1832
1833 template <class _Tp, class _Allocator>
1834 void
1835 deque<_Tp, _Allocator>::push_front(const value_type& __v)
1836 {
1837     allocator_type& __a = __base::__alloc();
1838     if (__front_spare() == 0)
1839         __add_front_capacity();
1840     // __front_spare() >= 1
1841     __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
1842     --__base::__start_;
1843     ++__base::size();
1844 }
1845
1846 #ifndef _LIBCPP_CXX03_LANG
1847 template <class _Tp, class _Allocator>
1848 void
1849 deque<_Tp, _Allocator>::push_back(value_type&& __v)
1850 {
1851     allocator_type& __a = __base::__alloc();
1852     if (__back_spare() == 0)
1853         __add_back_capacity();
1854     // __back_spare() >= 1
1855     __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
1856     ++__base::size();
1857 }
1858
1859 template <class _Tp, class _Allocator>
1860 template <class... _Args>
1861 #if _LIBCPP_STD_VER > 14
1862 typename deque<_Tp, _Allocator>::reference
1863 #else
1864 void
1865 #endif
1866 deque<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1867 {
1868     allocator_type& __a = __base::__alloc();
1869     if (__back_spare() == 0)
1870         __add_back_capacity();
1871     // __back_spare() >= 1
1872     __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()),
1873                               _VSTD::forward<_Args>(__args)...);
1874     ++__base::size();
1875 #if _LIBCPP_STD_VER > 14
1876     return *--__base::end();
1877 #endif
1878 }
1879
1880 template <class _Tp, class _Allocator>
1881 void
1882 deque<_Tp, _Allocator>::push_front(value_type&& __v)
1883 {
1884     allocator_type& __a = __base::__alloc();
1885     if (__front_spare() == 0)
1886         __add_front_capacity();
1887     // __front_spare() >= 1
1888     __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
1889     --__base::__start_;
1890     ++__base::size();
1891 }
1892
1893
1894 template <class _Tp, class _Allocator>
1895 template <class... _Args>
1896 #if _LIBCPP_STD_VER > 14
1897 typename deque<_Tp, _Allocator>::reference
1898 #else
1899 void
1900 #endif
1901 deque<_Tp, _Allocator>::emplace_front(_Args&&... __args)
1902 {
1903     allocator_type& __a = __base::__alloc();
1904     if (__front_spare() == 0)
1905         __add_front_capacity();
1906     // __front_spare() >= 1
1907     __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
1908     --__base::__start_;
1909     ++__base::size();
1910 #if _LIBCPP_STD_VER > 14
1911     return *__base::begin();
1912 #endif
1913 }
1914
1915 template <class _Tp, class _Allocator>
1916 typename deque<_Tp, _Allocator>::iterator
1917 deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v)
1918 {
1919     size_type __pos = __p - __base::begin();
1920     size_type __to_end = __base::size() - __pos;
1921     allocator_type& __a = __base::__alloc();
1922     if (__pos < __to_end)
1923     {   // insert by shifting things backward
1924         if (__front_spare() == 0)
1925             __add_front_capacity();
1926         // __front_spare() >= 1
1927         if (__pos == 0)
1928         {
1929             __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
1930             --__base::__start_;
1931             ++__base::size();
1932         }
1933         else
1934         {
1935             iterator __b = __base::begin();
1936             iterator __bm1 = _VSTD::prev(__b);
1937             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1938             --__base::__start_;
1939             ++__base::size();
1940             if (__pos > 1)
1941                 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1942             *__b = _VSTD::move(__v);
1943         }
1944     }
1945     else
1946     {   // insert by shifting things forward
1947         if (__back_spare() == 0)
1948             __add_back_capacity();
1949         // __back_capacity >= 1
1950         size_type __de = __base::size() - __pos;
1951         if (__de == 0)
1952         {
1953             __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
1954             ++__base::size();
1955         }
1956         else
1957         {
1958             iterator __e = __base::end();
1959             iterator __em1 = _VSTD::prev(__e);
1960             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
1961             ++__base::size();
1962             if (__de > 1)
1963                 __e = _VSTD::move_backward(__e - __de, __em1, __e);
1964             *--__e = _VSTD::move(__v);
1965         }
1966     }
1967     return __base::begin() + __pos;
1968 }
1969
1970 template <class _Tp, class _Allocator>
1971 template <class... _Args>
1972 typename deque<_Tp, _Allocator>::iterator
1973 deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args)
1974 {
1975     size_type __pos = __p - __base::begin();
1976     size_type __to_end = __base::size() - __pos;
1977     allocator_type& __a = __base::__alloc();
1978     if (__pos < __to_end)
1979     {   // insert by shifting things backward
1980         if (__front_spare() == 0)
1981             __add_front_capacity();
1982         // __front_spare() >= 1
1983         if (__pos == 0)
1984         {
1985             __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
1986             --__base::__start_;
1987             ++__base::size();
1988         }
1989         else
1990         {
1991             __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
1992             iterator __b = __base::begin();
1993             iterator __bm1 = _VSTD::prev(__b);
1994             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1995             --__base::__start_;
1996             ++__base::size();
1997             if (__pos > 1)
1998                 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1999             *__b = _VSTD::move(__tmp.get());
2000         }
2001     }
2002     else
2003     {   // insert by shifting things forward
2004         if (__back_spare() == 0)
2005             __add_back_capacity();
2006         // __back_capacity >= 1
2007         size_type __de = __base::size() - __pos;
2008         if (__de == 0)
2009         {
2010             __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
2011             ++__base::size();
2012         }
2013         else
2014         {
2015             __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
2016             iterator __e = __base::end();
2017             iterator __em1 = _VSTD::prev(__e);
2018             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
2019             ++__base::size();
2020             if (__de > 1)
2021                 __e = _VSTD::move_backward(__e - __de, __em1, __e);
2022             *--__e = _VSTD::move(__tmp.get());
2023         }
2024     }
2025     return __base::begin() + __pos;
2026 }
2027
2028 #endif  // _LIBCPP_CXX03_LANG
2029
2030
2031 template <class _Tp, class _Allocator>
2032 typename deque<_Tp, _Allocator>::iterator
2033 deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v)
2034 {
2035     size_type __pos = __p - __base::begin();
2036     size_type __to_end = __base::size() - __pos;
2037     allocator_type& __a = __base::__alloc();
2038     if (__pos < __to_end)
2039     {   // insert by shifting things backward
2040         if (__front_spare() == 0)
2041             __add_front_capacity();
2042         // __front_spare() >= 1
2043         if (__pos == 0)
2044         {
2045             __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
2046             --__base::__start_;
2047             ++__base::size();
2048         }
2049         else
2050         {
2051             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2052             iterator __b = __base::begin();
2053             iterator __bm1 = _VSTD::prev(__b);
2054             if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))
2055                 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);
2056             __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
2057             --__base::__start_;
2058             ++__base::size();
2059             if (__pos > 1)
2060                 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt);
2061             *__b = *__vt;
2062         }
2063     }
2064     else
2065     {   // insert by shifting things forward
2066         if (__back_spare() == 0)
2067             __add_back_capacity();
2068         // __back_capacity >= 1
2069         size_type __de = __base::size() - __pos;
2070         if (__de == 0)
2071         {
2072             __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
2073             ++__base::size();
2074         }
2075         else
2076         {
2077             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2078             iterator __e = __base::end();
2079             iterator __em1 = _VSTD::prev(__e);
2080             if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))
2081                 __vt = pointer_traits<const_pointer>::pointer_to(*__e);
2082             __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
2083             ++__base::size();
2084             if (__de > 1)
2085                 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);
2086             *--__e = *__vt;
2087         }
2088     }
2089     return __base::begin() + __pos;
2090 }
2091
2092 template <class _Tp, class _Allocator>
2093 typename deque<_Tp, _Allocator>::iterator
2094 deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v)
2095 {
2096     size_type __pos = __p - __base::begin();
2097     size_type __to_end = __base::size() - __pos;
2098     allocator_type& __a = __base::__alloc();
2099     if (__pos < __to_end)
2100     {   // insert by shifting things backward
2101         if (__n > __front_spare())
2102             __add_front_capacity(__n - __front_spare());
2103         // __n <= __front_spare()
2104         iterator __old_begin = __base::begin();
2105         iterator __i = __old_begin;
2106         if (__n > __pos)
2107         {
2108             for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size())
2109                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v);
2110             __n = __pos;
2111         }
2112         if (__n > 0)
2113         {
2114             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2115             iterator __obn = __old_begin + __n;
2116             __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);
2117             if (__n < __pos)
2118                 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);
2119             _VSTD::fill_n(__old_begin, __n, *__vt);
2120         }
2121     }
2122     else
2123     {   // insert by shifting things forward
2124         size_type __back_capacity = __back_spare();
2125         if (__n > __back_capacity)
2126             __add_back_capacity(__n - __back_capacity);
2127         // __n <= __back_capacity
2128         iterator __old_end = __base::end();
2129         iterator __i = __old_end;
2130         size_type __de = __base::size() - __pos;
2131         if (__n > __de)
2132         {
2133             for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size())
2134                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
2135             __n = __de;
2136         }
2137         if (__n > 0)
2138         {
2139             const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2140             iterator __oen = __old_end - __n;
2141             __move_construct_and_check(__oen, __old_end, __i, __vt);
2142             if (__n < __de)
2143                 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);
2144             _VSTD::fill_n(__old_end - __n, __n, *__vt);
2145         }
2146     }
2147     return __base::begin() + __pos;
2148 }
2149
2150 template <class _Tp, class _Allocator>
2151 template <class _InputIter>
2152 typename deque<_Tp, _Allocator>::iterator
2153 deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
2154                                typename enable_if<__is_input_iterator<_InputIter>::value
2155                                                &&!__is_forward_iterator<_InputIter>::value>::type*)
2156 {
2157     __split_buffer<value_type, allocator_type&> __buf(__base::__alloc());
2158     __buf.__construct_at_end(__f, __l);
2159     typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
2160     return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
2161 }
2162
2163 template <class _Tp, class _Allocator>
2164 template <class _ForwardIterator>
2165 typename deque<_Tp, _Allocator>::iterator
2166 deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
2167                                typename enable_if<__is_forward_iterator<_ForwardIterator>::value
2168                                                &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type*)
2169 {
2170     size_type __n = _VSTD::distance(__f, __l);
2171     __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc());
2172     __buf.__construct_at_end(__f, __l);
2173     typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
2174     return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
2175 }
2176
2177 template <class _Tp, class _Allocator>
2178 template <class _BiIter>
2179 typename deque<_Tp, _Allocator>::iterator
2180 deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
2181                                typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*)
2182 {
2183     size_type __n = _VSTD::distance(__f, __l);
2184     size_type __pos = __p - __base::begin();
2185     size_type __to_end = __base::size() - __pos;
2186     allocator_type& __a = __base::__alloc();
2187     if (__pos < __to_end)
2188     {   // insert by shifting things backward
2189         if (__n > __front_spare())
2190             __add_front_capacity(__n - __front_spare());
2191         // __n <= __front_spare()
2192         iterator __old_begin = __base::begin();
2193         iterator __i = __old_begin;
2194         _BiIter __m = __f;
2195         if (__n > __pos)
2196         {
2197             __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
2198             for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size())
2199                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
2200             __n = __pos;
2201         }
2202         if (__n > 0)
2203         {
2204             iterator __obn = __old_begin + __n;
2205             for (iterator __j = __obn; __j != __old_begin;)
2206             {
2207                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
2208                 --__base::__start_;
2209                 ++__base::size();
2210             }
2211             if (__n < __pos)
2212                 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
2213             _VSTD::copy(__m, __l, __old_begin);
2214         }
2215     }
2216     else
2217     {   // insert by shifting things forward
2218         size_type __back_capacity = __back_spare();
2219         if (__n > __back_capacity)
2220             __add_back_capacity(__n - __back_capacity);
2221         // __n <= __back_capacity
2222         iterator __old_end = __base::end();
2223         iterator __i = __old_end;
2224         _BiIter __m = __l;
2225         size_type __de = __base::size() - __pos;
2226         if (__n > __de)
2227         {
2228             __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
2229             for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
2230                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
2231             __n = __de;
2232         }
2233         if (__n > 0)
2234         {
2235             iterator __oen = __old_end - __n;
2236             for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size())
2237                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
2238             if (__n < __de)
2239                 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
2240             _VSTD::copy_backward(__f, __m, __old_end);
2241         }
2242     }
2243     return __base::begin() + __pos;
2244 }
2245
2246 template <class _Tp, class _Allocator>
2247 template <class _InpIter>
2248 void
2249 deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
2250                                  typename enable_if<__is_input_iterator<_InpIter>::value &&
2251                                                    !__is_forward_iterator<_InpIter>::value>::type*)
2252 {
2253     for (; __f != __l; ++__f)
2254 #ifdef _LIBCPP_CXX03_LANG
2255         push_back(*__f);
2256 #else
2257         emplace_back(*__f);
2258 #endif
2259 }
2260
2261 template <class _Tp, class _Allocator>
2262 template <class _ForIter>
2263 void
2264 deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
2265                                  typename enable_if<__is_forward_iterator<_ForIter>::value>::type*)
2266 {
2267     size_type __n = _VSTD::distance(__f, __l);
2268     allocator_type& __a = __base::__alloc();
2269     size_type __back_capacity = __back_spare();
2270     if (__n > __back_capacity)
2271         __add_back_capacity(__n - __back_capacity);
2272     // __n <= __back_capacity
2273     for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size())
2274         __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f);
2275 }
2276
2277 template <class _Tp, class _Allocator>
2278 void
2279 deque<_Tp, _Allocator>::__append(size_type __n)
2280 {
2281     allocator_type& __a = __base::__alloc();
2282     size_type __back_capacity = __back_spare();
2283     if (__n > __back_capacity)
2284         __add_back_capacity(__n - __back_capacity);
2285     // __n <= __back_capacity
2286     for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
2287         __alloc_traits::construct(__a, _VSTD::addressof(*__i));
2288 }
2289
2290 template <class _Tp, class _Allocator>
2291 void
2292 deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
2293 {
2294     allocator_type& __a = __base::__alloc();
2295     size_type __back_capacity = __back_spare();
2296     if (__n > __back_capacity)
2297         __add_back_capacity(__n - __back_capacity);
2298     // __n <= __back_capacity
2299     for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
2300         __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
2301 }
2302
2303 // Create front capacity for one block of elements.
2304 // Strong guarantee.  Either do it or don't touch anything.
2305 template <class _Tp, class _Allocator>
2306 void
2307 deque<_Tp, _Allocator>::__add_front_capacity()
2308 {
2309     allocator_type& __a = __base::__alloc();
2310     if (__back_spare() >= __base::__block_size)
2311     {
2312         __base::__start_ += __base::__block_size;
2313         pointer __pt = __base::__map_.back();
2314         __base::__map_.pop_back();
2315         __base::__map_.push_front(__pt);
2316     }
2317     // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer
2318     else if (__base::__map_.size() < __base::__map_.capacity())
2319     {   // we can put the new buffer into the map, but don't shift things around
2320         // until all buffers are allocated.  If we throw, we don't need to fix
2321         // anything up (any added buffers are undetectible)
2322         if (__base::__map_.__front_spare() > 0)
2323             __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2324         else
2325         {
2326             __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2327             // Done allocating, reorder capacity
2328             pointer __pt = __base::__map_.back();
2329             __base::__map_.pop_back();
2330             __base::__map_.push_front(__pt);
2331         }
2332         __base::__start_ = __base::__map_.size() == 1 ?
2333                                __base::__block_size / 2 :
2334                                __base::__start_ + __base::__block_size;
2335     }
2336     // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2337     else
2338     {
2339         __split_buffer<pointer, typename __base::__pointer_allocator&>
2340             __buf(max<size_type>(2 * __base::__map_.capacity(), 1),
2341                   0, __base::__map_.__alloc());
2342
2343         typedef __allocator_destructor<_Allocator> _Dp;
2344         unique_ptr<pointer, _Dp> __hold(
2345             __alloc_traits::allocate(__a, __base::__block_size),
2346                 _Dp(__a, __base::__block_size));
2347         __buf.push_back(__hold.get());
2348         __hold.release();
2349
2350         for (typename __base::__map_pointer __i = __base::__map_.begin();
2351                 __i != __base::__map_.end(); ++__i)
2352             __buf.push_back(*__i);
2353         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2354         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2355         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2356         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2357         __base::__start_ = __base::__map_.size() == 1 ?
2358                                __base::__block_size / 2 :
2359                                __base::__start_ + __base::__block_size;
2360     }
2361 }
2362
2363 // Create front capacity for __n elements.
2364 // Strong guarantee.  Either do it or don't touch anything.
2365 template <class _Tp, class _Allocator>
2366 void
2367 deque<_Tp, _Allocator>::__add_front_capacity(size_type __n)
2368 {
2369     allocator_type& __a = __base::__alloc();
2370     size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2371     // Number of unused blocks at back:
2372     size_type __back_capacity = __back_spare() / __base::__block_size;
2373     __back_capacity = _VSTD::min(__back_capacity, __nb);  // don't take more than you need
2374     __nb -= __back_capacity;  // number of blocks need to allocate
2375     // If __nb == 0, then we have sufficient capacity.
2376     if (__nb == 0)
2377     {
2378         __base::__start_ += __base::__block_size * __back_capacity;
2379         for (; __back_capacity > 0; --__back_capacity)
2380         {
2381             pointer __pt = __base::__map_.back();
2382             __base::__map_.pop_back();
2383             __base::__map_.push_front(__pt);
2384         }
2385     }
2386     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2387     else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2388     {   // we can put the new buffers into the map, but don't shift things around
2389         // until all buffers are allocated.  If we throw, we don't need to fix
2390         // anything up (any added buffers are undetectible)
2391         for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1))
2392         {
2393             if (__base::__map_.__front_spare() == 0)
2394                 break;
2395             __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2396         }
2397         for (; __nb > 0; --__nb, ++__back_capacity)
2398             __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2399         // Done allocating, reorder capacity
2400         __base::__start_ += __back_capacity * __base::__block_size;
2401         for (; __back_capacity > 0; --__back_capacity)
2402         {
2403             pointer __pt = __base::__map_.back();
2404             __base::__map_.pop_back();
2405             __base::__map_.push_front(__pt);
2406         }
2407     }
2408     // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2409     else
2410     {
2411         size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty();
2412         __split_buffer<pointer, typename __base::__pointer_allocator&>
2413             __buf(max<size_type>(2* __base::__map_.capacity(),
2414                                  __nb + __base::__map_.size()),
2415                   0, __base::__map_.__alloc());
2416 #ifndef _LIBCPP_NO_EXCEPTIONS
2417         try
2418         {
2419 #endif  // _LIBCPP_NO_EXCEPTIONS
2420             for (; __nb > 0; --__nb)
2421                 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2422 #ifndef _LIBCPP_NO_EXCEPTIONS
2423         }
2424         catch (...)
2425         {
2426             for (typename __base::__map_pointer __i = __buf.begin();
2427                     __i != __buf.end(); ++__i)
2428                 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2429             throw;
2430         }
2431 #endif  // _LIBCPP_NO_EXCEPTIONS
2432         for (; __back_capacity > 0; --__back_capacity)
2433         {
2434             __buf.push_back(__base::__map_.back());
2435             __base::__map_.pop_back();
2436         }
2437         for (typename __base::__map_pointer __i = __base::__map_.begin();
2438                 __i != __base::__map_.end(); ++__i)
2439             __buf.push_back(*__i);
2440         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2441         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2442         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2443         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2444         __base::__start_ += __ds;
2445     }
2446 }
2447
2448 // Create back capacity for one block of elements.
2449 // Strong guarantee.  Either do it or don't touch anything.
2450 template <class _Tp, class _Allocator>
2451 void
2452 deque<_Tp, _Allocator>::__add_back_capacity()
2453 {
2454     allocator_type& __a = __base::__alloc();
2455     if (__front_spare() >= __base::__block_size)
2456     {
2457         __base::__start_ -= __base::__block_size;
2458         pointer __pt = __base::__map_.front();
2459         __base::__map_.pop_front();
2460         __base::__map_.push_back(__pt);
2461     }
2462     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2463     else if (__base::__map_.size() < __base::__map_.capacity())
2464     {   // we can put the new buffer into the map, but don't shift things around
2465         // until it is allocated.  If we throw, we don't need to fix
2466         // anything up (any added buffers are undetectible)
2467         if (__base::__map_.__back_spare() != 0)
2468             __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2469         else
2470         {
2471             __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2472             // Done allocating, reorder capacity
2473             pointer __pt = __base::__map_.front();
2474             __base::__map_.pop_front();
2475             __base::__map_.push_back(__pt);
2476         }
2477     }
2478     // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2479     else
2480     {
2481         __split_buffer<pointer, typename __base::__pointer_allocator&>
2482             __buf(max<size_type>(2* __base::__map_.capacity(), 1),
2483                   __base::__map_.size(),
2484                   __base::__map_.__alloc());
2485
2486         typedef __allocator_destructor<_Allocator> _Dp;
2487         unique_ptr<pointer, _Dp> __hold(
2488             __alloc_traits::allocate(__a, __base::__block_size),
2489                 _Dp(__a, __base::__block_size));
2490         __buf.push_back(__hold.get());
2491         __hold.release();
2492
2493         for (typename __base::__map_pointer __i = __base::__map_.end();
2494                 __i != __base::__map_.begin();)
2495             __buf.push_front(*--__i);
2496         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2497         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2498         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2499         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2500     }
2501 }
2502
2503 // Create back capacity for __n elements.
2504 // Strong guarantee.  Either do it or don't touch anything.
2505 template <class _Tp, class _Allocator>
2506 void
2507 deque<_Tp, _Allocator>::__add_back_capacity(size_type __n)
2508 {
2509     allocator_type& __a = __base::__alloc();
2510     size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2511     // Number of unused blocks at front:
2512     size_type __front_capacity = __front_spare() / __base::__block_size;
2513     __front_capacity = _VSTD::min(__front_capacity, __nb);  // don't take more than you need
2514     __nb -= __front_capacity;  // number of blocks need to allocate
2515     // If __nb == 0, then we have sufficient capacity.
2516     if (__nb == 0)
2517     {
2518         __base::__start_ -= __base::__block_size * __front_capacity;
2519         for (; __front_capacity > 0; --__front_capacity)
2520         {
2521             pointer __pt = __base::__map_.front();
2522             __base::__map_.pop_front();
2523             __base::__map_.push_back(__pt);
2524         }
2525     }
2526     // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2527     else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2528     {   // we can put the new buffers into the map, but don't shift things around
2529         // until all buffers are allocated.  If we throw, we don't need to fix
2530         // anything up (any added buffers are undetectible)
2531         for (; __nb > 0; --__nb)
2532         {
2533             if (__base::__map_.__back_spare() == 0)
2534                 break;
2535             __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2536         }
2537         for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ +=
2538                                  __base::__block_size - (__base::__map_.size() == 1))
2539             __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2540         // Done allocating, reorder capacity
2541         __base::__start_ -= __base::__block_size * __front_capacity;
2542         for (; __front_capacity > 0; --__front_capacity)
2543         {
2544             pointer __pt = __base::__map_.front();
2545             __base::__map_.pop_front();
2546             __base::__map_.push_back(__pt);
2547         }
2548     }
2549     // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2550     else
2551     {
2552         size_type __ds = __front_capacity * __base::__block_size;
2553         __split_buffer<pointer, typename __base::__pointer_allocator&>
2554             __buf(max<size_type>(2* __base::__map_.capacity(),
2555                                  __nb + __base::__map_.size()),
2556                   __base::__map_.size() - __front_capacity,
2557                   __base::__map_.__alloc());
2558 #ifndef _LIBCPP_NO_EXCEPTIONS
2559         try
2560         {
2561 #endif  // _LIBCPP_NO_EXCEPTIONS
2562             for (; __nb > 0; --__nb)
2563                 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2564 #ifndef _LIBCPP_NO_EXCEPTIONS
2565         }
2566         catch (...)
2567         {
2568             for (typename __base::__map_pointer __i = __buf.begin();
2569                     __i != __buf.end(); ++__i)
2570                 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2571             throw;
2572         }
2573 #endif  // _LIBCPP_NO_EXCEPTIONS
2574         for (; __front_capacity > 0; --__front_capacity)
2575         {
2576             __buf.push_back(__base::__map_.front());
2577             __base::__map_.pop_front();
2578         }
2579         for (typename __base::__map_pointer __i = __base::__map_.end();
2580                 __i != __base::__map_.begin();)
2581             __buf.push_front(*--__i);
2582         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2583         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2584         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2585         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2586         __base::__start_ -= __ds;
2587     }
2588 }
2589
2590 template <class _Tp, class _Allocator>
2591 void
2592 deque<_Tp, _Allocator>::pop_front()
2593 {
2594     allocator_type& __a = __base::__alloc();
2595     __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2596                                                     __base::__start_ / __base::__block_size) +
2597                                                     __base::__start_ % __base::__block_size));
2598     --__base::size();
2599     if (++__base::__start_ >= 2 * __base::__block_size)
2600     {
2601         __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2602         __base::__map_.pop_front();
2603         __base::__start_ -= __base::__block_size;
2604     }
2605 }
2606
2607 template <class _Tp, class _Allocator>
2608 void
2609 deque<_Tp, _Allocator>::pop_back()
2610 {
2611     _LIBCPP_ASSERT(!empty(), "deque::pop_back called for empty deque");
2612     allocator_type& __a = __base::__alloc();
2613     size_type __p = __base::size() + __base::__start_ - 1;
2614     __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2615                                                     __p / __base::__block_size) +
2616                                                     __p % __base::__block_size));
2617     --__base::size();
2618     if (__back_spare() >= 2 * __base::__block_size)
2619     {
2620         __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2621         __base::__map_.pop_back();
2622     }
2623 }
2624
2625 // move assign [__f, __l) to [__r, __r + (__l-__f)).
2626 // If __vt points into [__f, __l), then subtract (__f - __r) from __vt.
2627 template <class _Tp, class _Allocator>
2628 typename deque<_Tp, _Allocator>::iterator
2629 deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r,
2630                                          const_pointer& __vt)
2631 {
2632     // as if
2633     //   for (; __f != __l; ++__f, ++__r)
2634     //       *__r = _VSTD::move(*__f);
2635     difference_type __n = __l - __f;
2636     while (__n > 0)
2637     {
2638         pointer __fb = __f.__ptr_;
2639         pointer __fe = *__f.__m_iter_ + __base::__block_size;
2640         difference_type __bs = __fe - __fb;
2641         if (__bs > __n)
2642         {
2643             __bs = __n;
2644             __fe = __fb + __bs;
2645         }
2646         if (__fb <= __vt && __vt < __fe)
2647             __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;
2648         __r = _VSTD::move(__fb, __fe, __r);
2649         __n -= __bs;
2650         __f += __bs;
2651     }
2652     return __r;
2653 }
2654
2655 // move assign [__f, __l) to [__r - (__l-__f), __r) backwards.
2656 // If __vt points into [__f, __l), then add (__r - __l) to __vt.
2657 template <class _Tp, class _Allocator>
2658 typename deque<_Tp, _Allocator>::iterator
2659 deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r,
2660                                                   const_pointer& __vt)
2661 {
2662     // as if
2663     //   while (__f != __l)
2664     //       *--__r = _VSTD::move(*--__l);
2665     difference_type __n = __l - __f;
2666     while (__n > 0)
2667     {
2668         --__l;
2669         pointer __lb = *__l.__m_iter_;
2670         pointer __le = __l.__ptr_ + 1;
2671         difference_type __bs = __le - __lb;
2672         if (__bs > __n)
2673         {
2674             __bs = __n;
2675             __lb = __le - __bs;
2676         }
2677         if (__lb <= __vt && __vt < __le)
2678             __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_;
2679         __r = _VSTD::move_backward(__lb, __le, __r);
2680         __n -= __bs;
2681         __l -= __bs - 1;
2682     }
2683     return __r;
2684 }
2685
2686 // move construct [__f, __l) to [__r, __r + (__l-__f)).
2687 // If __vt points into [__f, __l), then add (__r - __f) to __vt.
2688 template <class _Tp, class _Allocator>
2689 void
2690 deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l,
2691                                                    iterator __r, const_pointer& __vt)
2692 {
2693     allocator_type& __a = __base::__alloc();
2694     // as if
2695     //   for (; __f != __l; ++__r, ++__f, ++__base::size())
2696     //       __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f));
2697     difference_type __n = __l - __f;
2698     while (__n > 0)
2699     {
2700         pointer __fb = __f.__ptr_;
2701         pointer __fe = *__f.__m_iter_ + __base::__block_size;
2702         difference_type __bs = __fe - __fb;
2703         if (__bs > __n)
2704         {
2705             __bs = __n;
2706             __fe = __fb + __bs;
2707         }
2708         if (__fb <= __vt && __vt < __fe)
2709             __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;
2710         for (; __fb != __fe; ++__fb, ++__r, ++__base::size())
2711             __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb));
2712         __n -= __bs;
2713         __f += __bs;
2714     }
2715 }
2716
2717 // move construct [__f, __l) to [__r - (__l-__f), __r) backwards.
2718 // If __vt points into [__f, __l), then subtract (__l - __r) from __vt.
2719 template <class _Tp, class _Allocator>
2720 void
2721 deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l,
2722                                                             iterator __r, const_pointer& __vt)
2723 {
2724     allocator_type& __a = __base::__alloc();
2725     // as if
2726     //   for (iterator __j = __l; __j != __f;)
2727     //   {
2728     //       __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j));
2729     //       --__base::__start_;
2730     //       ++__base::size();
2731     //   }
2732     difference_type __n = __l - __f;
2733     while (__n > 0)
2734     {
2735         --__l;
2736         pointer __lb = *__l.__m_iter_;
2737         pointer __le = __l.__ptr_ + 1;
2738         difference_type __bs = __le - __lb;
2739         if (__bs > __n)
2740         {
2741             __bs = __n;
2742             __lb = __le - __bs;
2743         }
2744         if (__lb <= __vt && __vt < __le)
2745             __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;
2746         while (__le != __lb)
2747         {
2748             __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le));
2749             --__base::__start_;
2750             ++__base::size();
2751         }
2752         __n -= __bs;
2753         __l -= __bs - 1;
2754     }
2755 }
2756
2757 template <class _Tp, class _Allocator>
2758 typename deque<_Tp, _Allocator>::iterator
2759 deque<_Tp, _Allocator>::erase(const_iterator __f)
2760 {
2761     iterator __b = __base::begin();
2762     difference_type __pos = __f - __b;
2763     iterator __p = __b + __pos;
2764     allocator_type& __a = __base::__alloc();
2765     if (static_cast<size_t>(__pos) <= (__base::size() - 1) / 2)
2766     {   // erase from front
2767         _VSTD::move_backward(__b, __p, _VSTD::next(__p));
2768         __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2769         --__base::size();
2770         ++__base::__start_;
2771         if (__front_spare() >= 2 * __base::__block_size)
2772         {
2773             __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2774             __base::__map_.pop_front();
2775             __base::__start_ -= __base::__block_size;
2776         }
2777     }
2778     else
2779     {   // erase from back
2780         iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
2781         __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2782         --__base::size();
2783         if (__back_spare() >= 2 * __base::__block_size)
2784         {
2785             __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2786             __base::__map_.pop_back();
2787         }
2788     }
2789     return __base::begin() + __pos;
2790 }
2791
2792 template <class _Tp, class _Allocator>
2793 typename deque<_Tp, _Allocator>::iterator
2794 deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
2795 {
2796     difference_type __n = __l - __f;
2797     iterator __b = __base::begin();
2798     difference_type __pos = __f - __b;
2799     iterator __p = __b + __pos;
2800     if (__n > 0)
2801     {
2802         allocator_type& __a = __base::__alloc();
2803         if (static_cast<size_t>(__pos) <= (__base::size() - __n) / 2)
2804         {   // erase from front
2805             iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
2806             for (; __b != __i; ++__b)
2807                 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2808             __base::size() -= __n;
2809             __base::__start_ += __n;
2810             while (__front_spare() >= 2 * __base::__block_size)
2811             {
2812                 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2813                 __base::__map_.pop_front();
2814                 __base::__start_ -= __base::__block_size;
2815             }
2816         }
2817         else
2818         {   // erase from back
2819             iterator __i = _VSTD::move(__p + __n, __base::end(), __p);
2820             for (iterator __e = __base::end(); __i != __e; ++__i)
2821                 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2822             __base::size() -= __n;
2823             while (__back_spare() >= 2 * __base::__block_size)
2824             {
2825                 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2826                 __base::__map_.pop_back();
2827             }
2828         }
2829     }
2830     return __base::begin() + __pos;
2831 }
2832
2833 template <class _Tp, class _Allocator>
2834 void
2835 deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
2836 {
2837     iterator __e = __base::end();
2838     difference_type __n = __e - __f;
2839     if (__n > 0)
2840     {
2841         allocator_type& __a = __base::__alloc();
2842         iterator __b = __base::begin();
2843         difference_type __pos = __f - __b;
2844         for (iterator __p = __b + __pos; __p != __e; ++__p)
2845             __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
2846         __base::size() -= __n;
2847         while (__back_spare() >= 2 * __base::__block_size)
2848         {
2849             __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2850             __base::__map_.pop_back();
2851         }
2852     }
2853 }
2854
2855 template <class _Tp, class _Allocator>
2856 inline
2857 void
2858 deque<_Tp, _Allocator>::swap(deque& __c)
2859 #if _LIBCPP_STD_VER >= 14
2860         _NOEXCEPT
2861 #else
2862         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2863                     __is_nothrow_swappable<allocator_type>::value)
2864 #endif
2865 {
2866     __base::swap(__c);
2867 }
2868
2869 template <class _Tp, class _Allocator>
2870 inline
2871 void
2872 deque<_Tp, _Allocator>::clear() _NOEXCEPT
2873 {
2874     __base::clear();
2875 }
2876
2877 template <class _Tp, class _Allocator>
2878 inline _LIBCPP_INLINE_VISIBILITY
2879 bool
2880 operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2881 {
2882     const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();
2883     return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2884 }
2885
2886 template <class _Tp, class _Allocator>
2887 inline _LIBCPP_INLINE_VISIBILITY
2888 bool
2889 operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2890 {
2891     return !(__x == __y);
2892 }
2893
2894 template <class _Tp, class _Allocator>
2895 inline _LIBCPP_INLINE_VISIBILITY
2896 bool
2897 operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2898 {
2899     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2900 }
2901
2902 template <class _Tp, class _Allocator>
2903 inline _LIBCPP_INLINE_VISIBILITY
2904 bool
2905 operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2906 {
2907     return __y < __x;
2908 }
2909
2910 template <class _Tp, class _Allocator>
2911 inline _LIBCPP_INLINE_VISIBILITY
2912 bool
2913 operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2914 {
2915     return !(__x < __y);
2916 }
2917
2918 template <class _Tp, class _Allocator>
2919 inline _LIBCPP_INLINE_VISIBILITY
2920 bool
2921 operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2922 {
2923     return !(__y < __x);
2924 }
2925
2926 template <class _Tp, class _Allocator>
2927 inline _LIBCPP_INLINE_VISIBILITY
2928 void
2929 swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y)
2930     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2931 {
2932     __x.swap(__y);
2933 }
2934
2935 #if _LIBCPP_STD_VER > 17
2936 template <class _Tp, class _Allocator, class _Up>
2937 inline _LIBCPP_INLINE_VISIBILITY
2938 void erase(deque<_Tp, _Allocator>& __c, const _Up& __v)
2939 { __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end()); }
2940
2941 template <class _Tp, class _Allocator, class _Predicate>
2942 inline _LIBCPP_INLINE_VISIBILITY
2943 void erase_if(deque<_Tp, _Allocator>& __c, _Predicate __pred)
2944 { __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end()); }
2945 #endif
2946
2947
2948 _LIBCPP_END_NAMESPACE_STD
2949
2950 _LIBCPP_POP_MACROS
2951
2952 #endif  // _LIBCPP_DEQUE