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