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 __allocator_traits<allocator_type>::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 deque(size_type __n, const value_type& __v, const allocator_type& __a); 1293 template <class _InputIter> 1294 deque(_InputIter __f, _InputIter __l, 1295 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0); 1296 template <class _InputIter> 1297 deque(_InputIter __f, _InputIter __l, const allocator_type& __a, 1298 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0); 1299 deque(const deque& __c); 1300 deque(const deque& __c, const __identity_t<allocator_type>& __a); 1301 1302 deque& operator=(const deque& __c); 1303 1304#ifndef _LIBCPP_CXX03_LANG 1305 deque(initializer_list<value_type> __il); 1306 deque(initializer_list<value_type> __il, const allocator_type& __a); 1307 1308 _LIBCPP_INLINE_VISIBILITY 1309 deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;} 1310 1311 _LIBCPP_INLINE_VISIBILITY 1312 deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value); 1313 _LIBCPP_INLINE_VISIBILITY 1314 deque(deque&& __c, const __identity_t<allocator_type>& __a); 1315 _LIBCPP_INLINE_VISIBILITY 1316 deque& operator=(deque&& __c) 1317 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1318 is_nothrow_move_assignable<allocator_type>::value); 1319 1320 _LIBCPP_INLINE_VISIBILITY 1321 void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());} 1322#endif // _LIBCPP_CXX03_LANG 1323 1324 template <class _InputIter> 1325 void assign(_InputIter __f, _InputIter __l, 1326 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value && 1327 !__is_cpp17_random_access_iterator<_InputIter>::value>::type* = 0); 1328 template <class _RAIter> 1329 void assign(_RAIter __f, _RAIter __l, 1330 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0); 1331 void assign(size_type __n, const value_type& __v); 1332 1333 _LIBCPP_INLINE_VISIBILITY 1334 allocator_type get_allocator() const _NOEXCEPT; 1335 1336 // iterators: 1337 1338 _LIBCPP_INLINE_VISIBILITY 1339 iterator begin() _NOEXCEPT {return __base::begin();} 1340 _LIBCPP_INLINE_VISIBILITY 1341 const_iterator begin() const _NOEXCEPT {return __base::begin();} 1342 _LIBCPP_INLINE_VISIBILITY 1343 iterator end() _NOEXCEPT {return __base::end();} 1344 _LIBCPP_INLINE_VISIBILITY 1345 const_iterator end() const _NOEXCEPT {return __base::end();} 1346 1347 _LIBCPP_INLINE_VISIBILITY 1348 reverse_iterator rbegin() _NOEXCEPT 1349 {return reverse_iterator(__base::end());} 1350 _LIBCPP_INLINE_VISIBILITY 1351 const_reverse_iterator rbegin() const _NOEXCEPT 1352 {return const_reverse_iterator(__base::end());} 1353 _LIBCPP_INLINE_VISIBILITY 1354 reverse_iterator rend() _NOEXCEPT 1355 {return reverse_iterator(__base::begin());} 1356 _LIBCPP_INLINE_VISIBILITY 1357 const_reverse_iterator rend() const _NOEXCEPT 1358 {return const_reverse_iterator(__base::begin());} 1359 1360 _LIBCPP_INLINE_VISIBILITY 1361 const_iterator cbegin() const _NOEXCEPT 1362 {return __base::begin();} 1363 _LIBCPP_INLINE_VISIBILITY 1364 const_iterator cend() const _NOEXCEPT 1365 {return __base::end();} 1366 _LIBCPP_INLINE_VISIBILITY 1367 const_reverse_iterator crbegin() const _NOEXCEPT 1368 {return const_reverse_iterator(__base::end());} 1369 _LIBCPP_INLINE_VISIBILITY 1370 const_reverse_iterator crend() const _NOEXCEPT 1371 {return const_reverse_iterator(__base::begin());} 1372 1373 // capacity: 1374 _LIBCPP_INLINE_VISIBILITY 1375 size_type size() const _NOEXCEPT {return __base::size();} 1376 _LIBCPP_INLINE_VISIBILITY 1377 size_type max_size() const _NOEXCEPT 1378 {return _VSTD::min<size_type>( 1379 __alloc_traits::max_size(__base::__alloc()), 1380 numeric_limits<difference_type>::max());} 1381 void resize(size_type __n); 1382 void resize(size_type __n, const value_type& __v); 1383 void shrink_to_fit() _NOEXCEPT; 1384 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1385 bool empty() const _NOEXCEPT {return __base::size() == 0;} 1386 1387 // element access: 1388 _LIBCPP_INLINE_VISIBILITY 1389 reference operator[](size_type __i) _NOEXCEPT; 1390 _LIBCPP_INLINE_VISIBILITY 1391 const_reference operator[](size_type __i) const _NOEXCEPT; 1392 _LIBCPP_INLINE_VISIBILITY 1393 reference at(size_type __i); 1394 _LIBCPP_INLINE_VISIBILITY 1395 const_reference at(size_type __i) const; 1396 _LIBCPP_INLINE_VISIBILITY 1397 reference front() _NOEXCEPT; 1398 _LIBCPP_INLINE_VISIBILITY 1399 const_reference front() const _NOEXCEPT; 1400 _LIBCPP_INLINE_VISIBILITY 1401 reference back() _NOEXCEPT; 1402 _LIBCPP_INLINE_VISIBILITY 1403 const_reference back() const _NOEXCEPT; 1404 1405 // 23.2.2.3 modifiers: 1406 void push_front(const value_type& __v); 1407 void push_back(const value_type& __v); 1408#ifndef _LIBCPP_CXX03_LANG 1409#if _LIBCPP_STD_VER > 14 1410 template <class... _Args> reference emplace_front(_Args&&... __args); 1411 template <class... _Args> reference emplace_back (_Args&&... __args); 1412#else 1413 template <class... _Args> void emplace_front(_Args&&... __args); 1414 template <class... _Args> void emplace_back (_Args&&... __args); 1415#endif 1416 template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args); 1417 1418 void push_front(value_type&& __v); 1419 void push_back(value_type&& __v); 1420 iterator insert(const_iterator __p, value_type&& __v); 1421 1422 _LIBCPP_INLINE_VISIBILITY 1423 iterator insert(const_iterator __p, initializer_list<value_type> __il) 1424 {return insert(__p, __il.begin(), __il.end());} 1425#endif // _LIBCPP_CXX03_LANG 1426 iterator insert(const_iterator __p, const value_type& __v); 1427 iterator insert(const_iterator __p, size_type __n, const value_type& __v); 1428 template <class _InputIter> 1429 iterator insert(const_iterator __p, _InputIter __f, _InputIter __l, 1430 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value 1431 &&!__is_cpp17_forward_iterator<_InputIter>::value>::type* = 0); 1432 template <class _ForwardIterator> 1433 iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l, 1434 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value 1435 &&!__is_cpp17_bidirectional_iterator<_ForwardIterator>::value>::type* = 0); 1436 template <class _BiIter> 1437 iterator insert(const_iterator __p, _BiIter __f, _BiIter __l, 1438 typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type* = 0); 1439 1440 void pop_front(); 1441 void pop_back(); 1442 iterator erase(const_iterator __p); 1443 iterator erase(const_iterator __f, const_iterator __l); 1444 1445 _LIBCPP_INLINE_VISIBILITY 1446 void swap(deque& __c) 1447#if _LIBCPP_STD_VER >= 14 1448 _NOEXCEPT; 1449#else 1450 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1451 __is_nothrow_swappable<allocator_type>::value); 1452#endif 1453 _LIBCPP_INLINE_VISIBILITY 1454 void clear() _NOEXCEPT; 1455 1456 _LIBCPP_INLINE_VISIBILITY 1457 bool __invariants() const {return __base::__invariants();} 1458 1459 typedef typename __base::__map_const_pointer __map_const_pointer; 1460 1461 _LIBCPP_INLINE_VISIBILITY 1462 static size_type __recommend_blocks(size_type __n) 1463 { 1464 return __n / __base::__block_size + (__n % __base::__block_size != 0); 1465 } 1466 _LIBCPP_INLINE_VISIBILITY 1467 size_type __capacity() const 1468 { 1469 return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1; 1470 } 1471 _LIBCPP_INLINE_VISIBILITY 1472 size_type __block_count() const 1473 { 1474 return __base::__map_.size(); 1475 } 1476 1477 _LIBCPP_INLINE_VISIBILITY 1478 size_type __front_spare() const 1479 { 1480 return __base::__start_; 1481 } 1482 _LIBCPP_INLINE_VISIBILITY 1483 size_type __front_spare_blocks() const { 1484 return __front_spare() / __base::__block_size; 1485 } 1486 _LIBCPP_INLINE_VISIBILITY 1487 size_type __back_spare() const 1488 { 1489 return __capacity() - (__base::__start_ + __base::size()); 1490 } 1491 _LIBCPP_INLINE_VISIBILITY 1492 size_type __back_spare_blocks() const { 1493 return __back_spare() / __base::__block_size; 1494 } 1495 1496 private: 1497 _LIBCPP_INLINE_VISIBILITY 1498 bool __maybe_remove_front_spare(bool __keep_one = true) { 1499 if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) { 1500 __alloc_traits::deallocate(__base::__alloc(), __base::__map_.front(), 1501 __base::__block_size); 1502 __base::__map_.pop_front(); 1503 __base::__start_ -= __base::__block_size; 1504 return true; 1505 } 1506 return false; 1507 } 1508 1509 _LIBCPP_INLINE_VISIBILITY 1510 bool __maybe_remove_back_spare(bool __keep_one = true) { 1511 if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) { 1512 __alloc_traits::deallocate(__base::__alloc(), __base::__map_.back(), 1513 __base::__block_size); 1514 __base::__map_.pop_back(); 1515 return true; 1516 } 1517 return false; 1518 } 1519 1520 template <class _InpIter> 1521 void __append(_InpIter __f, _InpIter __l, 1522 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value && 1523 !__is_cpp17_forward_iterator<_InpIter>::value>::type* = 0); 1524 template <class _ForIter> 1525 void __append(_ForIter __f, _ForIter __l, 1526 typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type* = 0); 1527 void __append(size_type __n); 1528 void __append(size_type __n, const value_type& __v); 1529 void __erase_to_end(const_iterator __f); 1530 void __add_front_capacity(); 1531 void __add_front_capacity(size_type __n); 1532 void __add_back_capacity(); 1533 void __add_back_capacity(size_type __n); 1534 iterator __move_and_check(iterator __f, iterator __l, iterator __r, 1535 const_pointer& __vt); 1536 iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r, 1537 const_pointer& __vt); 1538 void __move_construct_and_check(iterator __f, iterator __l, 1539 iterator __r, const_pointer& __vt); 1540 void __move_construct_backward_and_check(iterator __f, iterator __l, 1541 iterator __r, const_pointer& __vt); 1542 1543 _LIBCPP_INLINE_VISIBILITY 1544 void __copy_assign_alloc(const deque& __c) 1545 {__copy_assign_alloc(__c, integral_constant<bool, 1546 __alloc_traits::propagate_on_container_copy_assignment::value>());} 1547 1548 _LIBCPP_INLINE_VISIBILITY 1549 void __copy_assign_alloc(const deque& __c, true_type) 1550 { 1551 if (__base::__alloc() != __c.__alloc()) 1552 { 1553 clear(); 1554 shrink_to_fit(); 1555 } 1556 __base::__alloc() = __c.__alloc(); 1557 __base::__map_.__alloc() = __c.__map_.__alloc(); 1558 } 1559 1560 _LIBCPP_INLINE_VISIBILITY 1561 void __copy_assign_alloc(const deque&, false_type) 1562 {} 1563 1564 void __move_assign(deque& __c, true_type) 1565 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 1566 void __move_assign(deque& __c, false_type); 1567}; 1568 1569#if _LIBCPP_STD_VER >= 17 1570template<class _InputIterator, 1571 class _Alloc = allocator<__iter_value_type<_InputIterator>>, 1572 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1573 class = enable_if_t<__is_allocator<_Alloc>::value> 1574 > 1575deque(_InputIterator, _InputIterator) 1576 -> deque<__iter_value_type<_InputIterator>, _Alloc>; 1577 1578template<class _InputIterator, 1579 class _Alloc, 1580 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1581 class = enable_if_t<__is_allocator<_Alloc>::value> 1582 > 1583deque(_InputIterator, _InputIterator, _Alloc) 1584 -> deque<__iter_value_type<_InputIterator>, _Alloc>; 1585#endif 1586 1587template <class _Tp, class _Allocator> 1588deque<_Tp, _Allocator>::deque(size_type __n) 1589{ 1590 if (__n > 0) 1591 __append(__n); 1592} 1593 1594#if _LIBCPP_STD_VER > 11 1595template <class _Tp, class _Allocator> 1596deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a) 1597 : __base(__a) 1598{ 1599 if (__n > 0) 1600 __append(__n); 1601} 1602#endif 1603 1604template <class _Tp, class _Allocator> 1605deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v) 1606{ 1607 if (__n > 0) 1608 __append(__n, __v); 1609} 1610 1611template <class _Tp, class _Allocator> 1612deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a) 1613 : __base(__a) 1614{ 1615 if (__n > 0) 1616 __append(__n, __v); 1617} 1618 1619template <class _Tp, class _Allocator> 1620template <class _InputIter> 1621deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, 1622 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type*) 1623{ 1624 __append(__f, __l); 1625} 1626 1627template <class _Tp, class _Allocator> 1628template <class _InputIter> 1629deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a, 1630 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type*) 1631 : __base(__a) 1632{ 1633 __append(__f, __l); 1634} 1635 1636template <class _Tp, class _Allocator> 1637deque<_Tp, _Allocator>::deque(const deque& __c) 1638 : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc())) 1639{ 1640 __append(__c.begin(), __c.end()); 1641} 1642 1643template <class _Tp, class _Allocator> 1644deque<_Tp, _Allocator>::deque(const deque& __c, const __identity_t<allocator_type>& __a) 1645 : __base(__a) 1646{ 1647 __append(__c.begin(), __c.end()); 1648} 1649 1650template <class _Tp, class _Allocator> 1651deque<_Tp, _Allocator>& 1652deque<_Tp, _Allocator>::operator=(const deque& __c) 1653{ 1654 if (this != _VSTD::addressof(__c)) 1655 { 1656 __copy_assign_alloc(__c); 1657 assign(__c.begin(), __c.end()); 1658 } 1659 return *this; 1660} 1661 1662#ifndef _LIBCPP_CXX03_LANG 1663 1664template <class _Tp, class _Allocator> 1665deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il) 1666{ 1667 __append(__il.begin(), __il.end()); 1668} 1669 1670template <class _Tp, class _Allocator> 1671deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a) 1672 : __base(__a) 1673{ 1674 __append(__il.begin(), __il.end()); 1675} 1676 1677template <class _Tp, class _Allocator> 1678inline 1679deque<_Tp, _Allocator>::deque(deque&& __c) 1680 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1681 : __base(_VSTD::move(__c)) 1682{ 1683} 1684 1685template <class _Tp, class _Allocator> 1686inline 1687deque<_Tp, _Allocator>::deque(deque&& __c, const __identity_t<allocator_type>& __a) 1688 : __base(_VSTD::move(__c), __a) 1689{ 1690 if (__a != __c.__alloc()) 1691 { 1692 typedef move_iterator<iterator> _Ip; 1693 assign(_Ip(__c.begin()), _Ip(__c.end())); 1694 } 1695} 1696 1697template <class _Tp, class _Allocator> 1698inline 1699deque<_Tp, _Allocator>& 1700deque<_Tp, _Allocator>::operator=(deque&& __c) 1701 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1702 is_nothrow_move_assignable<allocator_type>::value) 1703{ 1704 __move_assign(__c, integral_constant<bool, 1705 __alloc_traits::propagate_on_container_move_assignment::value>()); 1706 return *this; 1707} 1708 1709template <class _Tp, class _Allocator> 1710void 1711deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type) 1712{ 1713 if (__base::__alloc() != __c.__alloc()) 1714 { 1715 typedef move_iterator<iterator> _Ip; 1716 assign(_Ip(__c.begin()), _Ip(__c.end())); 1717 } 1718 else 1719 __move_assign(__c, true_type()); 1720} 1721 1722template <class _Tp, class _Allocator> 1723void 1724deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type) 1725 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1726{ 1727 clear(); 1728 shrink_to_fit(); 1729 __base::__move_assign(__c); 1730} 1731 1732#endif // _LIBCPP_CXX03_LANG 1733 1734template <class _Tp, class _Allocator> 1735template <class _InputIter> 1736void 1737deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l, 1738 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value && 1739 !__is_cpp17_random_access_iterator<_InputIter>::value>::type*) 1740{ 1741 iterator __i = __base::begin(); 1742 iterator __e = __base::end(); 1743 for (; __f != __l && __i != __e; ++__f, (void) ++__i) 1744 *__i = *__f; 1745 if (__f != __l) 1746 __append(__f, __l); 1747 else 1748 __erase_to_end(__i); 1749} 1750 1751template <class _Tp, class _Allocator> 1752template <class _RAIter> 1753void 1754deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l, 1755 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*) 1756{ 1757 if (static_cast<size_type>(__l - __f) > __base::size()) 1758 { 1759 _RAIter __m = __f + __base::size(); 1760 _VSTD::copy(__f, __m, __base::begin()); 1761 __append(__m, __l); 1762 } 1763 else 1764 __erase_to_end(_VSTD::copy(__f, __l, __base::begin())); 1765} 1766 1767template <class _Tp, class _Allocator> 1768void 1769deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v) 1770{ 1771 if (__n > __base::size()) 1772 { 1773 _VSTD::fill_n(__base::begin(), __base::size(), __v); 1774 __n -= __base::size(); 1775 __append(__n, __v); 1776 } 1777 else 1778 __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v)); 1779} 1780 1781template <class _Tp, class _Allocator> 1782inline 1783_Allocator 1784deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT 1785{ 1786 return __base::__alloc(); 1787} 1788 1789template <class _Tp, class _Allocator> 1790void 1791deque<_Tp, _Allocator>::resize(size_type __n) 1792{ 1793 if (__n > __base::size()) 1794 __append(__n - __base::size()); 1795 else if (__n < __base::size()) 1796 __erase_to_end(__base::begin() + __n); 1797} 1798 1799template <class _Tp, class _Allocator> 1800void 1801deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v) 1802{ 1803 if (__n > __base::size()) 1804 __append(__n - __base::size(), __v); 1805 else if (__n < __base::size()) 1806 __erase_to_end(__base::begin() + __n); 1807} 1808 1809template <class _Tp, class _Allocator> 1810void 1811deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 1812{ 1813 allocator_type& __a = __base::__alloc(); 1814 if (empty()) 1815 { 1816 while (__base::__map_.size() > 0) 1817 { 1818 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 1819 __base::__map_.pop_back(); 1820 } 1821 __base::__start_ = 0; 1822 } 1823 else 1824 { 1825 __maybe_remove_front_spare(/*__keep_one=*/false); 1826 __maybe_remove_back_spare(/*__keep_one=*/false); 1827 } 1828 __base::__map_.shrink_to_fit(); 1829} 1830 1831template <class _Tp, class _Allocator> 1832inline 1833typename deque<_Tp, _Allocator>::reference 1834deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT 1835{ 1836 size_type __p = __base::__start_ + __i; 1837 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1838} 1839 1840template <class _Tp, class _Allocator> 1841inline 1842typename deque<_Tp, _Allocator>::const_reference 1843deque<_Tp, _Allocator>::operator[](size_type __i) const _NOEXCEPT 1844{ 1845 size_type __p = __base::__start_ + __i; 1846 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1847} 1848 1849template <class _Tp, class _Allocator> 1850inline 1851typename deque<_Tp, _Allocator>::reference 1852deque<_Tp, _Allocator>::at(size_type __i) 1853{ 1854 if (__i >= __base::size()) 1855 _VSTD::__throw_out_of_range("deque"); 1856 size_type __p = __base::__start_ + __i; 1857 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1858} 1859 1860template <class _Tp, class _Allocator> 1861inline 1862typename deque<_Tp, _Allocator>::const_reference 1863deque<_Tp, _Allocator>::at(size_type __i) const 1864{ 1865 if (__i >= __base::size()) 1866 _VSTD::__throw_out_of_range("deque"); 1867 size_type __p = __base::__start_ + __i; 1868 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1869} 1870 1871template <class _Tp, class _Allocator> 1872inline 1873typename deque<_Tp, _Allocator>::reference 1874deque<_Tp, _Allocator>::front() _NOEXCEPT 1875{ 1876 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size) 1877 + __base::__start_ % __base::__block_size); 1878} 1879 1880template <class _Tp, class _Allocator> 1881inline 1882typename deque<_Tp, _Allocator>::const_reference 1883deque<_Tp, _Allocator>::front() const _NOEXCEPT 1884{ 1885 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size) 1886 + __base::__start_ % __base::__block_size); 1887} 1888 1889template <class _Tp, class _Allocator> 1890inline 1891typename deque<_Tp, _Allocator>::reference 1892deque<_Tp, _Allocator>::back() _NOEXCEPT 1893{ 1894 size_type __p = __base::size() + __base::__start_ - 1; 1895 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1896} 1897 1898template <class _Tp, class _Allocator> 1899inline 1900typename deque<_Tp, _Allocator>::const_reference 1901deque<_Tp, _Allocator>::back() const _NOEXCEPT 1902{ 1903 size_type __p = __base::size() + __base::__start_ - 1; 1904 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1905} 1906 1907template <class _Tp, class _Allocator> 1908void 1909deque<_Tp, _Allocator>::push_back(const value_type& __v) 1910{ 1911 allocator_type& __a = __base::__alloc(); 1912 if (__back_spare() == 0) 1913 __add_back_capacity(); 1914 // __back_spare() >= 1 1915 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v); 1916 ++__base::size(); 1917} 1918 1919template <class _Tp, class _Allocator> 1920void 1921deque<_Tp, _Allocator>::push_front(const value_type& __v) 1922{ 1923 allocator_type& __a = __base::__alloc(); 1924 if (__front_spare() == 0) 1925 __add_front_capacity(); 1926 // __front_spare() >= 1 1927 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v); 1928 --__base::__start_; 1929 ++__base::size(); 1930} 1931 1932#ifndef _LIBCPP_CXX03_LANG 1933template <class _Tp, class _Allocator> 1934void 1935deque<_Tp, _Allocator>::push_back(value_type&& __v) 1936{ 1937 allocator_type& __a = __base::__alloc(); 1938 if (__back_spare() == 0) 1939 __add_back_capacity(); 1940 // __back_spare() >= 1 1941 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v)); 1942 ++__base::size(); 1943} 1944 1945template <class _Tp, class _Allocator> 1946template <class... _Args> 1947#if _LIBCPP_STD_VER > 14 1948typename deque<_Tp, _Allocator>::reference 1949#else 1950void 1951#endif 1952deque<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1953{ 1954 allocator_type& __a = __base::__alloc(); 1955 if (__back_spare() == 0) 1956 __add_back_capacity(); 1957 // __back_spare() >= 1 1958 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), 1959 _VSTD::forward<_Args>(__args)...); 1960 ++__base::size(); 1961#if _LIBCPP_STD_VER > 14 1962 return *--__base::end(); 1963#endif 1964} 1965 1966template <class _Tp, class _Allocator> 1967void 1968deque<_Tp, _Allocator>::push_front(value_type&& __v) 1969{ 1970 allocator_type& __a = __base::__alloc(); 1971 if (__front_spare() == 0) 1972 __add_front_capacity(); 1973 // __front_spare() >= 1 1974 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v)); 1975 --__base::__start_; 1976 ++__base::size(); 1977} 1978 1979 1980template <class _Tp, class _Allocator> 1981template <class... _Args> 1982#if _LIBCPP_STD_VER > 14 1983typename deque<_Tp, _Allocator>::reference 1984#else 1985void 1986#endif 1987deque<_Tp, _Allocator>::emplace_front(_Args&&... __args) 1988{ 1989 allocator_type& __a = __base::__alloc(); 1990 if (__front_spare() == 0) 1991 __add_front_capacity(); 1992 // __front_spare() >= 1 1993 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...); 1994 --__base::__start_; 1995 ++__base::size(); 1996#if _LIBCPP_STD_VER > 14 1997 return *__base::begin(); 1998#endif 1999} 2000 2001template <class _Tp, class _Allocator> 2002typename deque<_Tp, _Allocator>::iterator 2003deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v) 2004{ 2005 size_type __pos = __p - __base::begin(); 2006 size_type __to_end = __base::size() - __pos; 2007 allocator_type& __a = __base::__alloc(); 2008 if (__pos < __to_end) 2009 { // insert by shifting things backward 2010 if (__front_spare() == 0) 2011 __add_front_capacity(); 2012 // __front_spare() >= 1 2013 if (__pos == 0) 2014 { 2015 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v)); 2016 --__base::__start_; 2017 ++__base::size(); 2018 } 2019 else 2020 { 2021 iterator __b = __base::begin(); 2022 iterator __bm1 = _VSTD::prev(__b); 2023 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 2024 --__base::__start_; 2025 ++__base::size(); 2026 if (__pos > 1) 2027 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 2028 *__b = _VSTD::move(__v); 2029 } 2030 } 2031 else 2032 { // insert by shifting things forward 2033 if (__back_spare() == 0) 2034 __add_back_capacity(); 2035 // __back_capacity >= 1 2036 size_type __de = __base::size() - __pos; 2037 if (__de == 0) 2038 { 2039 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v)); 2040 ++__base::size(); 2041 } 2042 else 2043 { 2044 iterator __e = __base::end(); 2045 iterator __em1 = _VSTD::prev(__e); 2046 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 2047 ++__base::size(); 2048 if (__de > 1) 2049 __e = _VSTD::move_backward(__e - __de, __em1, __e); 2050 *--__e = _VSTD::move(__v); 2051 } 2052 } 2053 return __base::begin() + __pos; 2054} 2055 2056template <class _Tp, class _Allocator> 2057template <class... _Args> 2058typename deque<_Tp, _Allocator>::iterator 2059deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args) 2060{ 2061 size_type __pos = __p - __base::begin(); 2062 size_type __to_end = __base::size() - __pos; 2063 allocator_type& __a = __base::__alloc(); 2064 if (__pos < __to_end) 2065 { // insert by shifting things backward 2066 if (__front_spare() == 0) 2067 __add_front_capacity(); 2068 // __front_spare() >= 1 2069 if (__pos == 0) 2070 { 2071 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...); 2072 --__base::__start_; 2073 ++__base::size(); 2074 } 2075 else 2076 { 2077 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); 2078 iterator __b = __base::begin(); 2079 iterator __bm1 = _VSTD::prev(__b); 2080 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 2081 --__base::__start_; 2082 ++__base::size(); 2083 if (__pos > 1) 2084 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 2085 *__b = _VSTD::move(__tmp.get()); 2086 } 2087 } 2088 else 2089 { // insert by shifting things forward 2090 if (__back_spare() == 0) 2091 __add_back_capacity(); 2092 // __back_capacity >= 1 2093 size_type __de = __base::size() - __pos; 2094 if (__de == 0) 2095 { 2096 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...); 2097 ++__base::size(); 2098 } 2099 else 2100 { 2101 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); 2102 iterator __e = __base::end(); 2103 iterator __em1 = _VSTD::prev(__e); 2104 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 2105 ++__base::size(); 2106 if (__de > 1) 2107 __e = _VSTD::move_backward(__e - __de, __em1, __e); 2108 *--__e = _VSTD::move(__tmp.get()); 2109 } 2110 } 2111 return __base::begin() + __pos; 2112} 2113 2114#endif // _LIBCPP_CXX03_LANG 2115 2116 2117template <class _Tp, class _Allocator> 2118typename deque<_Tp, _Allocator>::iterator 2119deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v) 2120{ 2121 size_type __pos = __p - __base::begin(); 2122 size_type __to_end = __base::size() - __pos; 2123 allocator_type& __a = __base::__alloc(); 2124 if (__pos < __to_end) 2125 { // insert by shifting things backward 2126 if (__front_spare() == 0) 2127 __add_front_capacity(); 2128 // __front_spare() >= 1 2129 if (__pos == 0) 2130 { 2131 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v); 2132 --__base::__start_; 2133 ++__base::size(); 2134 } 2135 else 2136 { 2137 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2138 iterator __b = __base::begin(); 2139 iterator __bm1 = _VSTD::prev(__b); 2140 if (__vt == pointer_traits<const_pointer>::pointer_to(*__b)) 2141 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1); 2142 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 2143 --__base::__start_; 2144 ++__base::size(); 2145 if (__pos > 1) 2146 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt); 2147 *__b = *__vt; 2148 } 2149 } 2150 else 2151 { // insert by shifting things forward 2152 if (__back_spare() == 0) 2153 __add_back_capacity(); 2154 // __back_capacity >= 1 2155 size_type __de = __base::size() - __pos; 2156 if (__de == 0) 2157 { 2158 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v); 2159 ++__base::size(); 2160 } 2161 else 2162 { 2163 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2164 iterator __e = __base::end(); 2165 iterator __em1 = _VSTD::prev(__e); 2166 if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1)) 2167 __vt = pointer_traits<const_pointer>::pointer_to(*__e); 2168 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 2169 ++__base::size(); 2170 if (__de > 1) 2171 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt); 2172 *--__e = *__vt; 2173 } 2174 } 2175 return __base::begin() + __pos; 2176} 2177 2178template <class _Tp, class _Allocator> 2179typename deque<_Tp, _Allocator>::iterator 2180deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v) 2181{ 2182 size_type __pos = __p - __base::begin(); 2183 size_type __to_end = __base::size() - __pos; 2184 allocator_type& __a = __base::__alloc(); 2185 if (__pos < __to_end) 2186 { // insert by shifting things backward 2187 if (__n > __front_spare()) 2188 __add_front_capacity(__n - __front_spare()); 2189 // __n <= __front_spare() 2190 iterator __old_begin = __base::begin(); 2191 iterator __i = __old_begin; 2192 if (__n > __pos) 2193 { 2194 for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size()) 2195 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v); 2196 __n = __pos; 2197 } 2198 if (__n > 0) 2199 { 2200 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2201 iterator __obn = __old_begin + __n; 2202 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt); 2203 if (__n < __pos) 2204 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt); 2205 _VSTD::fill_n(__old_begin, __n, *__vt); 2206 } 2207 } 2208 else 2209 { // insert by shifting things forward 2210 size_type __back_capacity = __back_spare(); 2211 if (__n > __back_capacity) 2212 __add_back_capacity(__n - __back_capacity); 2213 // __n <= __back_capacity 2214 iterator __old_end = __base::end(); 2215 iterator __i = __old_end; 2216 size_type __de = __base::size() - __pos; 2217 if (__n > __de) 2218 { 2219 for (size_type __m = __n - __de; __m; --__m, (void) ++__i, ++__base::size()) 2220 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2221 __n = __de; 2222 } 2223 if (__n > 0) 2224 { 2225 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2226 iterator __oen = __old_end - __n; 2227 __move_construct_and_check(__oen, __old_end, __i, __vt); 2228 if (__n < __de) 2229 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt); 2230 _VSTD::fill_n(__old_end - __n, __n, *__vt); 2231 } 2232 } 2233 return __base::begin() + __pos; 2234} 2235 2236template <class _Tp, class _Allocator> 2237template <class _InputIter> 2238typename deque<_Tp, _Allocator>::iterator 2239deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l, 2240 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value 2241 &&!__is_cpp17_forward_iterator<_InputIter>::value>::type*) 2242{ 2243 __split_buffer<value_type, allocator_type&> __buf(__base::__alloc()); 2244 __buf.__construct_at_end(__f, __l); 2245 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi; 2246 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end())); 2247} 2248 2249template <class _Tp, class _Allocator> 2250template <class _ForwardIterator> 2251typename deque<_Tp, _Allocator>::iterator 2252deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l, 2253 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value 2254 &&!__is_cpp17_bidirectional_iterator<_ForwardIterator>::value>::type*) 2255{ 2256 size_type __n = _VSTD::distance(__f, __l); 2257 __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc()); 2258 __buf.__construct_at_end(__f, __l); 2259 typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd; 2260 return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end())); 2261} 2262 2263template <class _Tp, class _Allocator> 2264template <class _BiIter> 2265typename deque<_Tp, _Allocator>::iterator 2266deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l, 2267 typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type*) 2268{ 2269 size_type __n = _VSTD::distance(__f, __l); 2270 size_type __pos = __p - __base::begin(); 2271 size_type __to_end = __base::size() - __pos; 2272 allocator_type& __a = __base::__alloc(); 2273 if (__pos < __to_end) 2274 { // insert by shifting things backward 2275 if (__n > __front_spare()) 2276 __add_front_capacity(__n - __front_spare()); 2277 // __n <= __front_spare() 2278 iterator __old_begin = __base::begin(); 2279 iterator __i = __old_begin; 2280 _BiIter __m = __f; 2281 if (__n > __pos) 2282 { 2283 __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos); 2284 for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size()) 2285 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j); 2286 __n = __pos; 2287 } 2288 if (__n > 0) 2289 { 2290 iterator __obn = __old_begin + __n; 2291 for (iterator __j = __obn; __j != __old_begin;) 2292 { 2293 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j)); 2294 --__base::__start_; 2295 ++__base::size(); 2296 } 2297 if (__n < __pos) 2298 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin); 2299 _VSTD::copy(__m, __l, __old_begin); 2300 } 2301 } 2302 else 2303 { // insert by shifting things forward 2304 size_type __back_capacity = __back_spare(); 2305 if (__n > __back_capacity) 2306 __add_back_capacity(__n - __back_capacity); 2307 // __n <= __back_capacity 2308 iterator __old_end = __base::end(); 2309 iterator __i = __old_end; 2310 _BiIter __m = __l; 2311 size_type __de = __base::size() - __pos; 2312 if (__n > __de) 2313 { 2314 __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de); 2315 for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size()) 2316 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j); 2317 __n = __de; 2318 } 2319 if (__n > 0) 2320 { 2321 iterator __oen = __old_end - __n; 2322 for (iterator __j = __oen; __j != __old_end; ++__i, (void) ++__j, ++__base::size()) 2323 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j)); 2324 if (__n < __de) 2325 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end); 2326 _VSTD::copy_backward(__f, __m, __old_end); 2327 } 2328 } 2329 return __base::begin() + __pos; 2330} 2331 2332template <class _Tp, class _Allocator> 2333template <class _InpIter> 2334void 2335deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l, 2336 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value && 2337 !__is_cpp17_forward_iterator<_InpIter>::value>::type*) 2338{ 2339 for (; __f != __l; ++__f) 2340#ifdef _LIBCPP_CXX03_LANG 2341 push_back(*__f); 2342#else 2343 emplace_back(*__f); 2344#endif 2345} 2346 2347template <class _Tp, class _Allocator> 2348template <class _ForIter> 2349void 2350deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l, 2351 typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type*) 2352{ 2353 size_type __n = _VSTD::distance(__f, __l); 2354 allocator_type& __a = __base::__alloc(); 2355 size_type __back_capacity = __back_spare(); 2356 if (__n > __back_capacity) 2357 __add_back_capacity(__n - __back_capacity); 2358 // __n <= __back_capacity 2359 for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) { 2360 _ConstructTransaction __tx(this, __br); 2361 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) { 2362 __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), *__f); 2363 } 2364 } 2365} 2366 2367template <class _Tp, class _Allocator> 2368void 2369deque<_Tp, _Allocator>::__append(size_type __n) 2370{ 2371 allocator_type& __a = __base::__alloc(); 2372 size_type __back_capacity = __back_spare(); 2373 if (__n > __back_capacity) 2374 __add_back_capacity(__n - __back_capacity); 2375 // __n <= __back_capacity 2376 for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) { 2377 _ConstructTransaction __tx(this, __br); 2378 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { 2379 __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_)); 2380 } 2381 } 2382} 2383 2384template <class _Tp, class _Allocator> 2385void 2386deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v) 2387{ 2388 allocator_type& __a = __base::__alloc(); 2389 size_type __back_capacity = __back_spare(); 2390 if (__n > __back_capacity) 2391 __add_back_capacity(__n - __back_capacity); 2392 // __n <= __back_capacity 2393 for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) { 2394 _ConstructTransaction __tx(this, __br); 2395 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { 2396 __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), __v); 2397 } 2398 } 2399 2400} 2401 2402// Create front capacity for one block of elements. 2403// Strong guarantee. Either do it or don't touch anything. 2404template <class _Tp, class _Allocator> 2405void 2406deque<_Tp, _Allocator>::__add_front_capacity() 2407{ 2408 allocator_type& __a = __base::__alloc(); 2409 if (__back_spare() >= __base::__block_size) 2410 { 2411 __base::__start_ += __base::__block_size; 2412 pointer __pt = __base::__map_.back(); 2413 __base::__map_.pop_back(); 2414 __base::__map_.push_front(__pt); 2415 } 2416 // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer 2417 else if (__base::__map_.size() < __base::__map_.capacity()) 2418 { // we can put the new buffer into the map, but don't shift things around 2419 // until all buffers are allocated. If we throw, we don't need to fix 2420 // anything up (any added buffers are undetectible) 2421 if (__base::__map_.__front_spare() > 0) 2422 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2423 else 2424 { 2425 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2426 // Done allocating, reorder capacity 2427 pointer __pt = __base::__map_.back(); 2428 __base::__map_.pop_back(); 2429 __base::__map_.push_front(__pt); 2430 } 2431 __base::__start_ = __base::__map_.size() == 1 ? 2432 __base::__block_size / 2 : 2433 __base::__start_ + __base::__block_size; 2434 } 2435 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2436 else 2437 { 2438 __split_buffer<pointer, typename __base::__pointer_allocator&> 2439 __buf(max<size_type>(2 * __base::__map_.capacity(), 1), 2440 0, __base::__map_.__alloc()); 2441 2442 typedef __allocator_destructor<_Allocator> _Dp; 2443 unique_ptr<pointer, _Dp> __hold( 2444 __alloc_traits::allocate(__a, __base::__block_size), 2445 _Dp(__a, __base::__block_size)); 2446 __buf.push_back(__hold.get()); 2447 __hold.release(); 2448 2449 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2450 __i != __base::__map_.end(); ++__i) 2451 __buf.push_back(*__i); 2452 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2453 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2454 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2455 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2456 __base::__start_ = __base::__map_.size() == 1 ? 2457 __base::__block_size / 2 : 2458 __base::__start_ + __base::__block_size; 2459 } 2460} 2461 2462// Create front capacity for __n elements. 2463// Strong guarantee. Either do it or don't touch anything. 2464template <class _Tp, class _Allocator> 2465void 2466deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) 2467{ 2468 allocator_type& __a = __base::__alloc(); 2469 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2470 // Number of unused blocks at back: 2471 size_type __back_capacity = __back_spare() / __base::__block_size; 2472 __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need 2473 __nb -= __back_capacity; // number of blocks need to allocate 2474 // If __nb == 0, then we have sufficient capacity. 2475 if (__nb == 0) 2476 { 2477 __base::__start_ += __base::__block_size * __back_capacity; 2478 for (; __back_capacity > 0; --__back_capacity) 2479 { 2480 pointer __pt = __base::__map_.back(); 2481 __base::__map_.pop_back(); 2482 __base::__map_.push_front(__pt); 2483 } 2484 } 2485 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2486 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2487 { // we can put the new buffers into the map, but don't shift things around 2488 // until all buffers are allocated. If we throw, we don't need to fix 2489 // anything up (any added buffers are undetectible) 2490 for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1)) 2491 { 2492 if (__base::__map_.__front_spare() == 0) 2493 break; 2494 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2495 } 2496 for (; __nb > 0; --__nb, ++__back_capacity) 2497 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2498 // Done allocating, reorder capacity 2499 __base::__start_ += __back_capacity * __base::__block_size; 2500 for (; __back_capacity > 0; --__back_capacity) 2501 { 2502 pointer __pt = __base::__map_.back(); 2503 __base::__map_.pop_back(); 2504 __base::__map_.push_front(__pt); 2505 } 2506 } 2507 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2508 else 2509 { 2510 size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty(); 2511 __split_buffer<pointer, typename __base::__pointer_allocator&> 2512 __buf(max<size_type>(2* __base::__map_.capacity(), 2513 __nb + __base::__map_.size()), 2514 0, __base::__map_.__alloc()); 2515#ifndef _LIBCPP_NO_EXCEPTIONS 2516 try 2517 { 2518#endif // _LIBCPP_NO_EXCEPTIONS 2519 for (; __nb > 0; --__nb) 2520 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2521#ifndef _LIBCPP_NO_EXCEPTIONS 2522 } 2523 catch (...) 2524 { 2525 for (typename __base::__map_pointer __i = __buf.begin(); 2526 __i != __buf.end(); ++__i) 2527 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2528 throw; 2529 } 2530#endif // _LIBCPP_NO_EXCEPTIONS 2531 for (; __back_capacity > 0; --__back_capacity) 2532 { 2533 __buf.push_back(__base::__map_.back()); 2534 __base::__map_.pop_back(); 2535 } 2536 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2537 __i != __base::__map_.end(); ++__i) 2538 __buf.push_back(*__i); 2539 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2540 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2541 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2542 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2543 __base::__start_ += __ds; 2544 } 2545} 2546 2547// Create back capacity for one block of elements. 2548// Strong guarantee. Either do it or don't touch anything. 2549template <class _Tp, class _Allocator> 2550void 2551deque<_Tp, _Allocator>::__add_back_capacity() 2552{ 2553 allocator_type& __a = __base::__alloc(); 2554 if (__front_spare() >= __base::__block_size) 2555 { 2556 __base::__start_ -= __base::__block_size; 2557 pointer __pt = __base::__map_.front(); 2558 __base::__map_.pop_front(); 2559 __base::__map_.push_back(__pt); 2560 } 2561 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2562 else if (__base::__map_.size() < __base::__map_.capacity()) 2563 { // we can put the new buffer into the map, but don't shift things around 2564 // until it is allocated. If we throw, we don't need to fix 2565 // anything up (any added buffers are undetectible) 2566 if (__base::__map_.__back_spare() != 0) 2567 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2568 else 2569 { 2570 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2571 // Done allocating, reorder capacity 2572 pointer __pt = __base::__map_.front(); 2573 __base::__map_.pop_front(); 2574 __base::__map_.push_back(__pt); 2575 } 2576 } 2577 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2578 else 2579 { 2580 __split_buffer<pointer, typename __base::__pointer_allocator&> 2581 __buf(max<size_type>(2* __base::__map_.capacity(), 1), 2582 __base::__map_.size(), 2583 __base::__map_.__alloc()); 2584 2585 typedef __allocator_destructor<_Allocator> _Dp; 2586 unique_ptr<pointer, _Dp> __hold( 2587 __alloc_traits::allocate(__a, __base::__block_size), 2588 _Dp(__a, __base::__block_size)); 2589 __buf.push_back(__hold.get()); 2590 __hold.release(); 2591 2592 for (typename __base::__map_pointer __i = __base::__map_.end(); 2593 __i != __base::__map_.begin();) 2594 __buf.push_front(*--__i); 2595 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2596 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2597 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2598 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2599 } 2600} 2601 2602// Create back capacity for __n elements. 2603// Strong guarantee. Either do it or don't touch anything. 2604template <class _Tp, class _Allocator> 2605void 2606deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) 2607{ 2608 allocator_type& __a = __base::__alloc(); 2609 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2610 // Number of unused blocks at front: 2611 size_type __front_capacity = __front_spare() / __base::__block_size; 2612 __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need 2613 __nb -= __front_capacity; // number of blocks need to allocate 2614 // If __nb == 0, then we have sufficient capacity. 2615 if (__nb == 0) 2616 { 2617 __base::__start_ -= __base::__block_size * __front_capacity; 2618 for (; __front_capacity > 0; --__front_capacity) 2619 { 2620 pointer __pt = __base::__map_.front(); 2621 __base::__map_.pop_front(); 2622 __base::__map_.push_back(__pt); 2623 } 2624 } 2625 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2626 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2627 { // we can put the new buffers into the map, but don't shift things around 2628 // until all buffers are allocated. If we throw, we don't need to fix 2629 // anything up (any added buffers are undetectible) 2630 for (; __nb > 0; --__nb) 2631 { 2632 if (__base::__map_.__back_spare() == 0) 2633 break; 2634 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2635 } 2636 for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ += 2637 __base::__block_size - (__base::__map_.size() == 1)) 2638 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2639 // Done allocating, reorder capacity 2640 __base::__start_ -= __base::__block_size * __front_capacity; 2641 for (; __front_capacity > 0; --__front_capacity) 2642 { 2643 pointer __pt = __base::__map_.front(); 2644 __base::__map_.pop_front(); 2645 __base::__map_.push_back(__pt); 2646 } 2647 } 2648 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2649 else 2650 { 2651 size_type __ds = __front_capacity * __base::__block_size; 2652 __split_buffer<pointer, typename __base::__pointer_allocator&> 2653 __buf(max<size_type>(2* __base::__map_.capacity(), 2654 __nb + __base::__map_.size()), 2655 __base::__map_.size() - __front_capacity, 2656 __base::__map_.__alloc()); 2657#ifndef _LIBCPP_NO_EXCEPTIONS 2658 try 2659 { 2660#endif // _LIBCPP_NO_EXCEPTIONS 2661 for (; __nb > 0; --__nb) 2662 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2663#ifndef _LIBCPP_NO_EXCEPTIONS 2664 } 2665 catch (...) 2666 { 2667 for (typename __base::__map_pointer __i = __buf.begin(); 2668 __i != __buf.end(); ++__i) 2669 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2670 throw; 2671 } 2672#endif // _LIBCPP_NO_EXCEPTIONS 2673 for (; __front_capacity > 0; --__front_capacity) 2674 { 2675 __buf.push_back(__base::__map_.front()); 2676 __base::__map_.pop_front(); 2677 } 2678 for (typename __base::__map_pointer __i = __base::__map_.end(); 2679 __i != __base::__map_.begin();) 2680 __buf.push_front(*--__i); 2681 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2682 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2683 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2684 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2685 __base::__start_ -= __ds; 2686 } 2687} 2688 2689template <class _Tp, class _Allocator> 2690void 2691deque<_Tp, _Allocator>::pop_front() 2692{ 2693 allocator_type& __a = __base::__alloc(); 2694 __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() + 2695 __base::__start_ / __base::__block_size) + 2696 __base::__start_ % __base::__block_size)); 2697 --__base::size(); 2698 ++__base::__start_; 2699 __maybe_remove_front_spare(); 2700} 2701 2702template <class _Tp, class _Allocator> 2703void 2704deque<_Tp, _Allocator>::pop_back() 2705{ 2706 _LIBCPP_ASSERT(!empty(), "deque::pop_back called on an empty deque"); 2707 allocator_type& __a = __base::__alloc(); 2708 size_type __p = __base::size() + __base::__start_ - 1; 2709 __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() + 2710 __p / __base::__block_size) + 2711 __p % __base::__block_size)); 2712 --__base::size(); 2713 __maybe_remove_back_spare(); 2714} 2715 2716// move assign [__f, __l) to [__r, __r + (__l-__f)). 2717// If __vt points into [__f, __l), then subtract (__f - __r) from __vt. 2718template <class _Tp, class _Allocator> 2719typename deque<_Tp, _Allocator>::iterator 2720deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, 2721 const_pointer& __vt) 2722{ 2723 // as if 2724 // for (; __f != __l; ++__f, ++__r) 2725 // *__r = _VSTD::move(*__f); 2726 difference_type __n = __l - __f; 2727 while (__n > 0) 2728 { 2729 pointer __fb = __f.__ptr_; 2730 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2731 difference_type __bs = __fe - __fb; 2732 if (__bs > __n) 2733 { 2734 __bs = __n; 2735 __fe = __fb + __bs; 2736 } 2737 if (__fb <= __vt && __vt < __fe) 2738 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_; 2739 __r = _VSTD::move(__fb, __fe, __r); 2740 __n -= __bs; 2741 __f += __bs; 2742 } 2743 return __r; 2744} 2745 2746// move assign [__f, __l) to [__r - (__l-__f), __r) backwards. 2747// If __vt points into [__f, __l), then add (__r - __l) to __vt. 2748template <class _Tp, class _Allocator> 2749typename deque<_Tp, _Allocator>::iterator 2750deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, 2751 const_pointer& __vt) 2752{ 2753 // as if 2754 // while (__f != __l) 2755 // *--__r = _VSTD::move(*--__l); 2756 difference_type __n = __l - __f; 2757 while (__n > 0) 2758 { 2759 --__l; 2760 pointer __lb = *__l.__m_iter_; 2761 pointer __le = __l.__ptr_ + 1; 2762 difference_type __bs = __le - __lb; 2763 if (__bs > __n) 2764 { 2765 __bs = __n; 2766 __lb = __le - __bs; 2767 } 2768 if (__lb <= __vt && __vt < __le) 2769 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_; 2770 __r = _VSTD::move_backward(__lb, __le, __r); 2771 __n -= __bs; 2772 __l -= __bs - 1; 2773 } 2774 return __r; 2775} 2776 2777// move construct [__f, __l) to [__r, __r + (__l-__f)). 2778// If __vt points into [__f, __l), then add (__r - __f) to __vt. 2779template <class _Tp, class _Allocator> 2780void 2781deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, 2782 iterator __r, const_pointer& __vt) 2783{ 2784 allocator_type& __a = __base::__alloc(); 2785 // as if 2786 // for (; __f != __l; ++__r, ++__f, ++__base::size()) 2787 // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f)); 2788 difference_type __n = __l - __f; 2789 while (__n > 0) 2790 { 2791 pointer __fb = __f.__ptr_; 2792 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2793 difference_type __bs = __fe - __fb; 2794 if (__bs > __n) 2795 { 2796 __bs = __n; 2797 __fe = __fb + __bs; 2798 } 2799 if (__fb <= __vt && __vt < __fe) 2800 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_; 2801 for (; __fb != __fe; ++__fb, ++__r, ++__base::size()) 2802 __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb)); 2803 __n -= __bs; 2804 __f += __bs; 2805 } 2806} 2807 2808// move construct [__f, __l) to [__r - (__l-__f), __r) backwards. 2809// If __vt points into [__f, __l), then subtract (__l - __r) from __vt. 2810template <class _Tp, class _Allocator> 2811void 2812deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l, 2813 iterator __r, const_pointer& __vt) 2814{ 2815 allocator_type& __a = __base::__alloc(); 2816 // as if 2817 // for (iterator __j = __l; __j != __f;) 2818 // { 2819 // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j)); 2820 // --__base::__start_; 2821 // ++__base::size(); 2822 // } 2823 difference_type __n = __l - __f; 2824 while (__n > 0) 2825 { 2826 --__l; 2827 pointer __lb = *__l.__m_iter_; 2828 pointer __le = __l.__ptr_ + 1; 2829 difference_type __bs = __le - __lb; 2830 if (__bs > __n) 2831 { 2832 __bs = __n; 2833 __lb = __le - __bs; 2834 } 2835 if (__lb <= __vt && __vt < __le) 2836 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_; 2837 while (__le != __lb) 2838 { 2839 __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le)); 2840 --__base::__start_; 2841 ++__base::size(); 2842 } 2843 __n -= __bs; 2844 __l -= __bs - 1; 2845 } 2846} 2847 2848template <class _Tp, class _Allocator> 2849typename deque<_Tp, _Allocator>::iterator 2850deque<_Tp, _Allocator>::erase(const_iterator __f) 2851{ 2852 iterator __b = __base::begin(); 2853 difference_type __pos = __f - __b; 2854 iterator __p = __b + __pos; 2855 allocator_type& __a = __base::__alloc(); 2856 if (static_cast<size_t>(__pos) <= (__base::size() - 1) / 2) 2857 { // erase from front 2858 _VSTD::move_backward(__b, __p, _VSTD::next(__p)); 2859 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2860 --__base::size(); 2861 ++__base::__start_; 2862 __maybe_remove_front_spare(); 2863 } 2864 else 2865 { // erase from back 2866 iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p); 2867 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2868 --__base::size(); 2869 __maybe_remove_back_spare(); 2870 } 2871 return __base::begin() + __pos; 2872} 2873 2874template <class _Tp, class _Allocator> 2875typename deque<_Tp, _Allocator>::iterator 2876deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) 2877{ 2878 difference_type __n = __l - __f; 2879 iterator __b = __base::begin(); 2880 difference_type __pos = __f - __b; 2881 iterator __p = __b + __pos; 2882 if (__n > 0) 2883 { 2884 allocator_type& __a = __base::__alloc(); 2885 if (static_cast<size_t>(__pos) <= (__base::size() - __n) / 2) 2886 { // erase from front 2887 iterator __i = _VSTD::move_backward(__b, __p, __p + __n); 2888 for (; __b != __i; ++__b) 2889 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2890 __base::size() -= __n; 2891 __base::__start_ += __n; 2892 while (__maybe_remove_front_spare()) { 2893 } 2894 } 2895 else 2896 { // erase from back 2897 iterator __i = _VSTD::move(__p + __n, __base::end(), __p); 2898 for (iterator __e = __base::end(); __i != __e; ++__i) 2899 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2900 __base::size() -= __n; 2901 while (__maybe_remove_back_spare()) { 2902 } 2903 } 2904 } 2905 return __base::begin() + __pos; 2906} 2907 2908template <class _Tp, class _Allocator> 2909void 2910deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f) 2911{ 2912 iterator __e = __base::end(); 2913 difference_type __n = __e - __f; 2914 if (__n > 0) 2915 { 2916 allocator_type& __a = __base::__alloc(); 2917 iterator __b = __base::begin(); 2918 difference_type __pos = __f - __b; 2919 for (iterator __p = __b + __pos; __p != __e; ++__p) 2920 __alloc_traits::destroy(__a, _VSTD::addressof(*__p)); 2921 __base::size() -= __n; 2922 while (__maybe_remove_back_spare()) { 2923 } 2924 } 2925} 2926 2927template <class _Tp, class _Allocator> 2928inline 2929void 2930deque<_Tp, _Allocator>::swap(deque& __c) 2931#if _LIBCPP_STD_VER >= 14 2932 _NOEXCEPT 2933#else 2934 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2935 __is_nothrow_swappable<allocator_type>::value) 2936#endif 2937{ 2938 __base::swap(__c); 2939} 2940 2941template <class _Tp, class _Allocator> 2942inline 2943void 2944deque<_Tp, _Allocator>::clear() _NOEXCEPT 2945{ 2946 __base::clear(); 2947} 2948 2949template <class _Tp, class _Allocator> 2950inline _LIBCPP_INLINE_VISIBILITY 2951bool 2952operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2953{ 2954 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size(); 2955 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2956} 2957 2958template <class _Tp, class _Allocator> 2959inline _LIBCPP_INLINE_VISIBILITY 2960bool 2961operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2962{ 2963 return !(__x == __y); 2964} 2965 2966template <class _Tp, class _Allocator> 2967inline _LIBCPP_INLINE_VISIBILITY 2968bool 2969operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2970{ 2971 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2972} 2973 2974template <class _Tp, class _Allocator> 2975inline _LIBCPP_INLINE_VISIBILITY 2976bool 2977operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2978{ 2979 return __y < __x; 2980} 2981 2982template <class _Tp, class _Allocator> 2983inline _LIBCPP_INLINE_VISIBILITY 2984bool 2985operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2986{ 2987 return !(__x < __y); 2988} 2989 2990template <class _Tp, class _Allocator> 2991inline _LIBCPP_INLINE_VISIBILITY 2992bool 2993operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2994{ 2995 return !(__y < __x); 2996} 2997 2998template <class _Tp, class _Allocator> 2999inline _LIBCPP_INLINE_VISIBILITY 3000void 3001swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) 3002 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 3003{ 3004 __x.swap(__y); 3005} 3006 3007#if _LIBCPP_STD_VER > 17 3008template <class _Tp, class _Allocator, class _Up> 3009inline _LIBCPP_INLINE_VISIBILITY typename deque<_Tp, _Allocator>::size_type 3010erase(deque<_Tp, _Allocator>& __c, const _Up& __v) { 3011 auto __old_size = __c.size(); 3012 __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end()); 3013 return __old_size - __c.size(); 3014} 3015 3016template <class _Tp, class _Allocator, class _Predicate> 3017inline _LIBCPP_INLINE_VISIBILITY typename deque<_Tp, _Allocator>::size_type 3018erase_if(deque<_Tp, _Allocator>& __c, _Predicate __pred) { 3019 auto __old_size = __c.size(); 3020 __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end()); 3021 return __old_size - __c.size(); 3022} 3023#endif 3024 3025 3026_LIBCPP_END_NAMESPACE_STD 3027 3028_LIBCPP_POP_MACROS 3029 3030#endif // _LIBCPP_DEQUE 3031