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