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