brintos / llvm-project-archived public Read only

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