libcxx/include/deque

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