include/deque

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