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