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