contrib/libc++/include/deque

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