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