headers/libs/libc++/deque

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