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