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 iterator __old_begin = __base::begin(); 2033 iterator __i = __old_begin; 2034 if (__n > __pos) 2035 { 2036 for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size()) 2037 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v); 2038 __n = __pos; 2039 } 2040 if (__n > 0) 2041 { 2042 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2043 iterator __obn = __old_begin + __n; 2044 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt); 2045 if (__n < __pos) 2046 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt); 2047 _VSTD::fill_n(__old_begin, __n, *__vt); 2048 } 2049 } 2050 else 2051 { // insert by shifting things forward 2052 size_type __back_capacity = __back_spare(); 2053 if (__n > __back_capacity) 2054 __add_back_capacity(__n - __back_capacity); 2055 // __n <= __back_capacity 2056 iterator __old_end = __base::end(); 2057 iterator __i = __old_end; 2058 size_type __de = __base::size() - __pos; 2059 if (__n > __de) 2060 { 2061 for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size()) 2062 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2063 __n = __de; 2064 } 2065 if (__n > 0) 2066 { 2067 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2068 iterator __oen = __old_end - __n; 2069 __move_construct_and_check(__oen, __old_end, __i, __vt); 2070 if (__n < __de) 2071 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt); 2072 _VSTD::fill_n(__old_end - __n, __n, *__vt); 2073 } 2074 } 2075 return __base::begin() + __pos; 2076} 2077 2078template <class _Tp, class _Allocator> 2079template <class _InputIter> 2080typename deque<_Tp, _Allocator>::iterator 2081deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l, 2082 typename enable_if<__is_input_iterator<_InputIter>::value 2083 &&!__is_forward_iterator<_InputIter>::value>::type*) 2084{ 2085 __split_buffer<value_type, allocator_type&> __buf(__base::__alloc()); 2086 __buf.__construct_at_end(__f, __l); 2087 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi; 2088 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end())); 2089} 2090 2091template <class _Tp, class _Allocator> 2092template <class _ForwardIterator> 2093typename deque<_Tp, _Allocator>::iterator 2094deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l, 2095 typename enable_if<__is_forward_iterator<_ForwardIterator>::value 2096 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type*) 2097{ 2098 size_type __n = _VSTD::distance(__f, __l); 2099 __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc()); 2100 __buf.__construct_at_end(__f, __l); 2101 typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd; 2102 return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end())); 2103} 2104 2105template <class _Tp, class _Allocator> 2106template <class _BiIter> 2107typename deque<_Tp, _Allocator>::iterator 2108deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l, 2109 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*) 2110{ 2111 size_type __n = _VSTD::distance(__f, __l); 2112 size_type __pos = __p - __base::begin(); 2113 size_type __to_end = __base::size() - __pos; 2114 allocator_type& __a = __base::__alloc(); 2115 if (__pos < __to_end) 2116 { // insert by shifting things backward 2117 if (__n > __front_spare()) 2118 __add_front_capacity(__n - __front_spare()); 2119 // __n <= __front_spare() 2120 iterator __old_begin = __base::begin(); 2121 iterator __i = __old_begin; 2122 _BiIter __m = __f; 2123 if (__n > __pos) 2124 { 2125 __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos); 2126 for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size()) 2127 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j); 2128 __n = __pos; 2129 } 2130 if (__n > 0) 2131 { 2132 iterator __obn = __old_begin + __n; 2133 for (iterator __j = __obn; __j != __old_begin;) 2134 { 2135 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j)); 2136 --__base::__start_; 2137 ++__base::size(); 2138 } 2139 if (__n < __pos) 2140 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin); 2141 _VSTD::copy(__m, __l, __old_begin); 2142 } 2143 } 2144 else 2145 { // insert by shifting things forward 2146 size_type __back_capacity = __back_spare(); 2147 if (__n > __back_capacity) 2148 __add_back_capacity(__n - __back_capacity); 2149 // __n <= __back_capacity 2150 iterator __old_end = __base::end(); 2151 iterator __i = __old_end; 2152 _BiIter __m = __l; 2153 size_type __de = __base::size() - __pos; 2154 if (__n > __de) 2155 { 2156 __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de); 2157 for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size()) 2158 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j); 2159 __n = __de; 2160 } 2161 if (__n > 0) 2162 { 2163 iterator __oen = __old_end - __n; 2164 for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size()) 2165 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j)); 2166 if (__n < __de) 2167 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end); 2168 _VSTD::copy_backward(__f, __m, __old_end); 2169 } 2170 } 2171 return __base::begin() + __pos; 2172} 2173 2174template <class _Tp, class _Allocator> 2175template <class _InpIter> 2176void 2177deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l, 2178 typename enable_if<__is_input_iterator<_InpIter>::value && 2179 !__is_forward_iterator<_InpIter>::value>::type*) 2180{ 2181 for (; __f != __l; ++__f) 2182 push_back(*__f); 2183} 2184 2185template <class _Tp, class _Allocator> 2186template <class _ForIter> 2187void 2188deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l, 2189 typename enable_if<__is_forward_iterator<_ForIter>::value>::type*) 2190{ 2191 size_type __n = _VSTD::distance(__f, __l); 2192 allocator_type& __a = __base::__alloc(); 2193 size_type __back_capacity = __back_spare(); 2194 if (__n > __back_capacity) 2195 __add_back_capacity(__n - __back_capacity); 2196 // __n <= __back_capacity 2197 for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size()) 2198 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f); 2199} 2200 2201template <class _Tp, class _Allocator> 2202void 2203deque<_Tp, _Allocator>::__append(size_type __n) 2204{ 2205 allocator_type& __a = __base::__alloc(); 2206 size_type __back_capacity = __back_spare(); 2207 if (__n > __back_capacity) 2208 __add_back_capacity(__n - __back_capacity); 2209 // __n <= __back_capacity 2210 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size()) 2211 __alloc_traits::construct(__a, _VSTD::addressof(*__i)); 2212} 2213 2214template <class _Tp, class _Allocator> 2215void 2216deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v) 2217{ 2218 allocator_type& __a = __base::__alloc(); 2219 size_type __back_capacity = __back_spare(); 2220 if (__n > __back_capacity) 2221 __add_back_capacity(__n - __back_capacity); 2222 // __n <= __back_capacity 2223 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size()) 2224 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2225} 2226 2227// Create front capacity for one block of elements. 2228// Strong guarantee. Either do it or don't touch anything. 2229template <class _Tp, class _Allocator> 2230void 2231deque<_Tp, _Allocator>::__add_front_capacity() 2232{ 2233 allocator_type& __a = __base::__alloc(); 2234 if (__back_spare() >= __base::__block_size) 2235 { 2236 __base::__start_ += __base::__block_size; 2237 pointer __pt = __base::__map_.back(); 2238 __base::__map_.pop_back(); 2239 __base::__map_.push_front(__pt); 2240 } 2241 // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer 2242 else if (__base::__map_.size() < __base::__map_.capacity()) 2243 { // we can put the new buffer into the map, but don't shift things around 2244 // until all buffers are allocated. If we throw, we don't need to fix 2245 // anything up (any added buffers are undetectible) 2246 if (__base::__map_.__front_spare() > 0) 2247 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2248 else 2249 { 2250 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2251 // Done allocating, reorder capacity 2252 pointer __pt = __base::__map_.back(); 2253 __base::__map_.pop_back(); 2254 __base::__map_.push_front(__pt); 2255 } 2256 __base::__start_ = __base::__map_.size() == 1 ? 2257 __base::__block_size / 2 : 2258 __base::__start_ + __base::__block_size; 2259 } 2260 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2261 else 2262 { 2263 __split_buffer<pointer, typename __base::__pointer_allocator&> 2264 __buf(max<size_type>(2 * __base::__map_.capacity(), 1), 2265 0, __base::__map_.__alloc()); 2266 2267 typedef __allocator_destructor<_Allocator> _Dp; 2268 unique_ptr<pointer, _Dp> __hold( 2269 __alloc_traits::allocate(__a, __base::__block_size), 2270 _Dp(__a, __base::__block_size)); 2271 __buf.push_back(__hold.get()); 2272 __hold.release(); 2273 2274 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2275 __i != __base::__map_.end(); ++__i) 2276 __buf.push_back(*__i); 2277 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2278 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2279 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2280 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2281 __base::__start_ = __base::__map_.size() == 1 ? 2282 __base::__block_size / 2 : 2283 __base::__start_ + __base::__block_size; 2284 } 2285} 2286 2287// Create front capacity for __n elements. 2288// Strong guarantee. Either do it or don't touch anything. 2289template <class _Tp, class _Allocator> 2290void 2291deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) 2292{ 2293 allocator_type& __a = __base::__alloc(); 2294 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2295 // Number of unused blocks at back: 2296 size_type __back_capacity = __back_spare() / __base::__block_size; 2297 __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need 2298 __nb -= __back_capacity; // number of blocks need to allocate 2299 // If __nb == 0, then we have sufficient capacity. 2300 if (__nb == 0) 2301 { 2302 __base::__start_ += __base::__block_size * __back_capacity; 2303 for (; __back_capacity > 0; --__back_capacity) 2304 { 2305 pointer __pt = __base::__map_.back(); 2306 __base::__map_.pop_back(); 2307 __base::__map_.push_front(__pt); 2308 } 2309 } 2310 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2311 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2312 { // we can put the new buffers into the map, but don't shift things around 2313 // until all buffers are allocated. If we throw, we don't need to fix 2314 // anything up (any added buffers are undetectible) 2315 for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1)) 2316 { 2317 if (__base::__map_.__front_spare() == 0) 2318 break; 2319 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2320 } 2321 for (; __nb > 0; --__nb, ++__back_capacity) 2322 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2323 // Done allocating, reorder capacity 2324 __base::__start_ += __back_capacity * __base::__block_size; 2325 for (; __back_capacity > 0; --__back_capacity) 2326 { 2327 pointer __pt = __base::__map_.back(); 2328 __base::__map_.pop_back(); 2329 __base::__map_.push_front(__pt); 2330 } 2331 } 2332 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2333 else 2334 { 2335 size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty(); 2336 __split_buffer<pointer, typename __base::__pointer_allocator&> 2337 __buf(max<size_type>(2* __base::__map_.capacity(), 2338 __nb + __base::__map_.size()), 2339 0, __base::__map_.__alloc()); 2340#ifndef _LIBCPP_NO_EXCEPTIONS 2341 try 2342 { 2343#endif // _LIBCPP_NO_EXCEPTIONS 2344 for (; __nb > 0; --__nb) 2345 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2346#ifndef _LIBCPP_NO_EXCEPTIONS 2347 } 2348 catch (...) 2349 { 2350 for (typename __base::__map_pointer __i = __buf.begin(); 2351 __i != __buf.end(); ++__i) 2352 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2353 throw; 2354 } 2355#endif // _LIBCPP_NO_EXCEPTIONS 2356 for (; __back_capacity > 0; --__back_capacity) 2357 { 2358 __buf.push_back(__base::__map_.back()); 2359 __base::__map_.pop_back(); 2360 } 2361 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2362 __i != __base::__map_.end(); ++__i) 2363 __buf.push_back(*__i); 2364 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2365 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2366 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2367 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2368 __base::__start_ += __ds; 2369 } 2370} 2371 2372// Create back capacity for one block of elements. 2373// Strong guarantee. Either do it or don't touch anything. 2374template <class _Tp, class _Allocator> 2375void 2376deque<_Tp, _Allocator>::__add_back_capacity() 2377{ 2378 allocator_type& __a = __base::__alloc(); 2379 if (__front_spare() >= __base::__block_size) 2380 { 2381 __base::__start_ -= __base::__block_size; 2382 pointer __pt = __base::__map_.front(); 2383 __base::__map_.pop_front(); 2384 __base::__map_.push_back(__pt); 2385 } 2386 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2387 else if (__base::__map_.size() < __base::__map_.capacity()) 2388 { // we can put the new buffer into the map, but don't shift things around 2389 // until it is allocated. If we throw, we don't need to fix 2390 // anything up (any added buffers are undetectible) 2391 if (__base::__map_.__back_spare() != 0) 2392 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2393 else 2394 { 2395 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2396 // Done allocating, reorder capacity 2397 pointer __pt = __base::__map_.front(); 2398 __base::__map_.pop_front(); 2399 __base::__map_.push_back(__pt); 2400 } 2401 } 2402 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2403 else 2404 { 2405 __split_buffer<pointer, typename __base::__pointer_allocator&> 2406 __buf(max<size_type>(2* __base::__map_.capacity(), 1), 2407 __base::__map_.size(), 2408 __base::__map_.__alloc()); 2409 2410 typedef __allocator_destructor<_Allocator> _Dp; 2411 unique_ptr<pointer, _Dp> __hold( 2412 __alloc_traits::allocate(__a, __base::__block_size), 2413 _Dp(__a, __base::__block_size)); 2414 __buf.push_back(__hold.get()); 2415 __hold.release(); 2416 2417 for (typename __base::__map_pointer __i = __base::__map_.end(); 2418 __i != __base::__map_.begin();) 2419 __buf.push_front(*--__i); 2420 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2421 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2422 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2423 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2424 } 2425} 2426 2427// Create back capacity for __n elements. 2428// Strong guarantee. Either do it or don't touch anything. 2429template <class _Tp, class _Allocator> 2430void 2431deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) 2432{ 2433 allocator_type& __a = __base::__alloc(); 2434 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2435 // Number of unused blocks at front: 2436 size_type __front_capacity = __front_spare() / __base::__block_size; 2437 __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need 2438 __nb -= __front_capacity; // number of blocks need to allocate 2439 // If __nb == 0, then we have sufficient capacity. 2440 if (__nb == 0) 2441 { 2442 __base::__start_ -= __base::__block_size * __front_capacity; 2443 for (; __front_capacity > 0; --__front_capacity) 2444 { 2445 pointer __pt = __base::__map_.front(); 2446 __base::__map_.pop_front(); 2447 __base::__map_.push_back(__pt); 2448 } 2449 } 2450 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2451 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2452 { // we can put the new buffers into the map, but don't shift things around 2453 // until all buffers are allocated. If we throw, we don't need to fix 2454 // anything up (any added buffers are undetectible) 2455 for (; __nb > 0; --__nb) 2456 { 2457 if (__base::__map_.__back_spare() == 0) 2458 break; 2459 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2460 } 2461 for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ += 2462 __base::__block_size - (__base::__map_.size() == 1)) 2463 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2464 // Done allocating, reorder capacity 2465 __base::__start_ -= __base::__block_size * __front_capacity; 2466 for (; __front_capacity > 0; --__front_capacity) 2467 { 2468 pointer __pt = __base::__map_.front(); 2469 __base::__map_.pop_front(); 2470 __base::__map_.push_back(__pt); 2471 } 2472 } 2473 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2474 else 2475 { 2476 size_type __ds = __front_capacity * __base::__block_size; 2477 __split_buffer<pointer, typename __base::__pointer_allocator&> 2478 __buf(max<size_type>(2* __base::__map_.capacity(), 2479 __nb + __base::__map_.size()), 2480 __base::__map_.size() - __front_capacity, 2481 __base::__map_.__alloc()); 2482#ifndef _LIBCPP_NO_EXCEPTIONS 2483 try 2484 { 2485#endif // _LIBCPP_NO_EXCEPTIONS 2486 for (; __nb > 0; --__nb) 2487 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2488#ifndef _LIBCPP_NO_EXCEPTIONS 2489 } 2490 catch (...) 2491 { 2492 for (typename __base::__map_pointer __i = __buf.begin(); 2493 __i != __buf.end(); ++__i) 2494 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2495 throw; 2496 } 2497#endif // _LIBCPP_NO_EXCEPTIONS 2498 for (; __front_capacity > 0; --__front_capacity) 2499 { 2500 __buf.push_back(__base::__map_.front()); 2501 __base::__map_.pop_front(); 2502 } 2503 for (typename __base::__map_pointer __i = __base::__map_.end(); 2504 __i != __base::__map_.begin();) 2505 __buf.push_front(*--__i); 2506 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2507 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2508 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2509 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2510 __base::__start_ -= __ds; 2511 } 2512} 2513 2514template <class _Tp, class _Allocator> 2515void 2516deque<_Tp, _Allocator>::pop_front() 2517{ 2518 allocator_type& __a = __base::__alloc(); 2519 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() + 2520 __base::__start_ / __base::__block_size) + 2521 __base::__start_ % __base::__block_size)); 2522 --__base::size(); 2523 if (++__base::__start_ >= 2 * __base::__block_size) 2524 { 2525 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2526 __base::__map_.pop_front(); 2527 __base::__start_ -= __base::__block_size; 2528 } 2529} 2530 2531template <class _Tp, class _Allocator> 2532void 2533deque<_Tp, _Allocator>::pop_back() 2534{ 2535 allocator_type& __a = __base::__alloc(); 2536 size_type __p = __base::size() + __base::__start_ - 1; 2537 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() + 2538 __p / __base::__block_size) + 2539 __p % __base::__block_size)); 2540 --__base::size(); 2541 if (__back_spare() >= 2 * __base::__block_size) 2542 { 2543 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2544 __base::__map_.pop_back(); 2545 } 2546} 2547 2548// move assign [__f, __l) to [__r, __r + (__l-__f)). 2549// If __vt points into [__f, __l), then subtract (__f - __r) from __vt. 2550template <class _Tp, class _Allocator> 2551typename deque<_Tp, _Allocator>::iterator 2552deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, 2553 const_pointer& __vt) 2554{ 2555 // as if 2556 // for (; __f != __l; ++__f, ++__r) 2557 // *__r = _VSTD::move(*__f); 2558 difference_type __n = __l - __f; 2559 while (__n > 0) 2560 { 2561 pointer __fb = __f.__ptr_; 2562 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2563 difference_type __bs = __fe - __fb; 2564 if (__bs > __n) 2565 { 2566 __bs = __n; 2567 __fe = __fb + __bs; 2568 } 2569 if (__fb <= __vt && __vt < __fe) 2570 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_; 2571 __r = _VSTD::move(__fb, __fe, __r); 2572 __n -= __bs; 2573 __f += __bs; 2574 } 2575 return __r; 2576} 2577 2578// move assign [__f, __l) to [__r - (__l-__f), __r) backwards. 2579// If __vt points into [__f, __l), then add (__r - __l) to __vt. 2580template <class _Tp, class _Allocator> 2581typename deque<_Tp, _Allocator>::iterator 2582deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, 2583 const_pointer& __vt) 2584{ 2585 // as if 2586 // while (__f != __l) 2587 // *--__r = _VSTD::move(*--__l); 2588 difference_type __n = __l - __f; 2589 while (__n > 0) 2590 { 2591 --__l; 2592 pointer __lb = *__l.__m_iter_; 2593 pointer __le = __l.__ptr_ + 1; 2594 difference_type __bs = __le - __lb; 2595 if (__bs > __n) 2596 { 2597 __bs = __n; 2598 __lb = __le - __bs; 2599 } 2600 if (__lb <= __vt && __vt < __le) 2601 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_; 2602 __r = _VSTD::move_backward(__lb, __le, __r); 2603 __n -= __bs; 2604 __l -= __bs - 1; 2605 } 2606 return __r; 2607} 2608 2609// move construct [__f, __l) to [__r, __r + (__l-__f)). 2610// If __vt points into [__f, __l), then add (__r - __f) to __vt. 2611template <class _Tp, class _Allocator> 2612void 2613deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, 2614 iterator __r, const_pointer& __vt) 2615{ 2616 allocator_type& __a = __base::__alloc(); 2617 // as if 2618 // for (; __f != __l; ++__r, ++__f, ++__base::size()) 2619 // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f)); 2620 difference_type __n = __l - __f; 2621 while (__n > 0) 2622 { 2623 pointer __fb = __f.__ptr_; 2624 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2625 difference_type __bs = __fe - __fb; 2626 if (__bs > __n) 2627 { 2628 __bs = __n; 2629 __fe = __fb + __bs; 2630 } 2631 if (__fb <= __vt && __vt < __fe) 2632 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_; 2633 for (; __fb != __fe; ++__fb, ++__r, ++__base::size()) 2634 __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb)); 2635 __n -= __bs; 2636 __f += __bs; 2637 } 2638} 2639 2640// move construct [__f, __l) to [__r - (__l-__f), __r) backwards. 2641// If __vt points into [__f, __l), then subtract (__l - __r) from __vt. 2642template <class _Tp, class _Allocator> 2643void 2644deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l, 2645 iterator __r, const_pointer& __vt) 2646{ 2647 allocator_type& __a = __base::__alloc(); 2648 // as if 2649 // for (iterator __j = __l; __j != __f;) 2650 // { 2651 // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j)); 2652 // --__base::__start_; 2653 // ++__base::size(); 2654 // } 2655 difference_type __n = __l - __f; 2656 while (__n > 0) 2657 { 2658 --__l; 2659 pointer __lb = *__l.__m_iter_; 2660 pointer __le = __l.__ptr_ + 1; 2661 difference_type __bs = __le - __lb; 2662 if (__bs > __n) 2663 { 2664 __bs = __n; 2665 __lb = __le - __bs; 2666 } 2667 if (__lb <= __vt && __vt < __le) 2668 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_; 2669 while (__le != __lb) 2670 { 2671 __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le)); 2672 --__base::__start_; 2673 ++__base::size(); 2674 } 2675 __n -= __bs; 2676 __l -= __bs - 1; 2677 } 2678} 2679 2680template <class _Tp, class _Allocator> 2681typename deque<_Tp, _Allocator>::iterator 2682deque<_Tp, _Allocator>::erase(const_iterator __f) 2683{ 2684 iterator __b = __base::begin(); 2685 difference_type __pos = __f - __b; 2686 iterator __p = __b + __pos; 2687 allocator_type& __a = __base::__alloc(); 2688 if (__pos <= (__base::size() - 1) / 2) 2689 { // erase from front 2690 _VSTD::move_backward(__b, __p, _VSTD::next(__p)); 2691 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2692 --__base::size(); 2693 ++__base::__start_; 2694 if (__front_spare() >= 2 * __base::__block_size) 2695 { 2696 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2697 __base::__map_.pop_front(); 2698 __base::__start_ -= __base::__block_size; 2699 } 2700 } 2701 else 2702 { // erase from back 2703 iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p); 2704 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2705 --__base::size(); 2706 if (__back_spare() >= 2 * __base::__block_size) 2707 { 2708 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2709 __base::__map_.pop_back(); 2710 } 2711 } 2712 return __base::begin() + __pos; 2713} 2714 2715template <class _Tp, class _Allocator> 2716typename deque<_Tp, _Allocator>::iterator 2717deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) 2718{ 2719 difference_type __n = __l - __f; 2720 iterator __b = __base::begin(); 2721 difference_type __pos = __f - __b; 2722 iterator __p = __b + __pos; 2723 if (__n > 0) 2724 { 2725 allocator_type& __a = __base::__alloc(); 2726 if (__pos <= (__base::size() - __n) / 2) 2727 { // erase from front 2728 iterator __i = _VSTD::move_backward(__b, __p, __p + __n); 2729 for (; __b != __i; ++__b) 2730 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2731 __base::size() -= __n; 2732 __base::__start_ += __n; 2733 while (__front_spare() >= 2 * __base::__block_size) 2734 { 2735 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2736 __base::__map_.pop_front(); 2737 __base::__start_ -= __base::__block_size; 2738 } 2739 } 2740 else 2741 { // erase from back 2742 iterator __i = _VSTD::move(__p + __n, __base::end(), __p); 2743 for (iterator __e = __base::end(); __i != __e; ++__i) 2744 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2745 __base::size() -= __n; 2746 while (__back_spare() >= 2 * __base::__block_size) 2747 { 2748 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2749 __base::__map_.pop_back(); 2750 } 2751 } 2752 } 2753 return __base::begin() + __pos; 2754} 2755 2756template <class _Tp, class _Allocator> 2757void 2758deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f) 2759{ 2760 iterator __e = __base::end(); 2761 difference_type __n = __e - __f; 2762 if (__n > 0) 2763 { 2764 allocator_type& __a = __base::__alloc(); 2765 iterator __b = __base::begin(); 2766 difference_type __pos = __f - __b; 2767 for (iterator __p = __b + __pos; __p != __e; ++__p) 2768 __alloc_traits::destroy(__a, _VSTD::addressof(*__p)); 2769 __base::size() -= __n; 2770 while (__back_spare() >= 2 * __base::__block_size) 2771 { 2772 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2773 __base::__map_.pop_back(); 2774 } 2775 } 2776} 2777 2778template <class _Tp, class _Allocator> 2779inline _LIBCPP_INLINE_VISIBILITY 2780void 2781deque<_Tp, _Allocator>::swap(deque& __c) 2782#if _LIBCPP_STD_VER >= 14 2783 _NOEXCEPT 2784#else 2785 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2786 __is_nothrow_swappable<allocator_type>::value) 2787#endif 2788{ 2789 __base::swap(__c); 2790} 2791 2792template <class _Tp, class _Allocator> 2793inline _LIBCPP_INLINE_VISIBILITY 2794void 2795deque<_Tp, _Allocator>::clear() _NOEXCEPT 2796{ 2797 __base::clear(); 2798} 2799 2800template <class _Tp, class _Allocator> 2801inline _LIBCPP_INLINE_VISIBILITY 2802bool 2803operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2804{ 2805 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size(); 2806 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2807} 2808 2809template <class _Tp, class _Allocator> 2810inline _LIBCPP_INLINE_VISIBILITY 2811bool 2812operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2813{ 2814 return !(__x == __y); 2815} 2816 2817template <class _Tp, class _Allocator> 2818inline _LIBCPP_INLINE_VISIBILITY 2819bool 2820operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2821{ 2822 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2823} 2824 2825template <class _Tp, class _Allocator> 2826inline _LIBCPP_INLINE_VISIBILITY 2827bool 2828operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2829{ 2830 return __y < __x; 2831} 2832 2833template <class _Tp, class _Allocator> 2834inline _LIBCPP_INLINE_VISIBILITY 2835bool 2836operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2837{ 2838 return !(__x < __y); 2839} 2840 2841template <class _Tp, class _Allocator> 2842inline _LIBCPP_INLINE_VISIBILITY 2843bool 2844operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2845{ 2846 return !(__y < __x); 2847} 2848 2849template <class _Tp, class _Allocator> 2850inline _LIBCPP_INLINE_VISIBILITY 2851void 2852swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) 2853 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2854{ 2855 __x.swap(__y); 2856} 2857 2858_LIBCPP_END_NAMESPACE_STD 2859 2860#endif // _LIBCPP_DEQUE 2861