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