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