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