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