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