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