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