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