diff options
Diffstat (limited to 'third_party/libcxx/include/c++/v1/deque')
| -rw-r--r-- | third_party/libcxx/include/c++/v1/deque | 2559 |
1 files changed, 2559 insertions, 0 deletions
diff --git a/third_party/libcxx/include/c++/v1/deque b/third_party/libcxx/include/c++/v1/deque new file mode 100644 index 0000000..c8c6889 --- /dev/null +++ b/third_party/libcxx/include/c++/v1/deque @@ -0,0 +1,2559 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP_DEQUE +#define _LIBCPP_DEQUE + +/* + deque synopsis + +namespace std +{ + +template <class T, class Allocator = allocator<T> > +class deque +{ +public: + // types: + typedef T value_type; + typedef Allocator allocator_type; + + typedef typename allocator_type::reference reference; + typedef typename allocator_type::const_reference const_reference; + typedef implementation-defined iterator; + typedef implementation-defined const_iterator; + typedef typename allocator_type::size_type size_type; + typedef typename allocator_type::difference_type difference_type; + + typedef typename allocator_type::pointer pointer; + typedef typename allocator_type::const_pointer const_pointer; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + + // construct/copy/destroy: + deque() noexcept(is_nothrow_default_constructible<allocator_type>::value); + explicit deque(const allocator_type& a); + explicit deque(size_type n); + explicit deque(size_type n, const allocator_type& a); // C++14 + deque(size_type n, const value_type& v); + deque(size_type n, const value_type& v, const allocator_type& a); + template <class InputIterator> + deque(InputIterator f, InputIterator l); + template <class InputIterator> + deque(InputIterator f, InputIterator l, const allocator_type& a); + template<container-compatible-range<T> R> + deque(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 + deque(const deque& c); + deque(deque&& c) + noexcept(is_nothrow_move_constructible<allocator_type>::value); + deque(initializer_list<value_type> il, const Allocator& a = allocator_type()); + deque(const deque& c, const allocator_type& a); + deque(deque&& c, const allocator_type& a); + ~deque(); + + deque& operator=(const deque& c); + deque& operator=(deque&& c) + noexcept((allocator_traits<allocator_type>::propagate_on_container_move_assignment::value && + is_nothrow_move_assignable<allocator_type>::value) || + allocator_traits<allocator_type>::is_always_equal::value); + deque& operator=(initializer_list<value_type> il); + + template <class InputIterator> + void assign(InputIterator f, InputIterator l); + template<container-compatible-range<T> R> + void assign_range(R&& rg); // C++23 + void assign(size_type n, const value_type& v); + void assign(initializer_list<value_type> il); + + allocator_type get_allocator() const noexcept; + + // iterators: + + iterator begin() noexcept; + const_iterator begin() const noexcept; + iterator end() noexcept; + const_iterator end() const noexcept; + + reverse_iterator rbegin() noexcept; + const_reverse_iterator rbegin() const noexcept; + reverse_iterator rend() noexcept; + const_reverse_iterator rend() const noexcept; + + const_iterator cbegin() const noexcept; + const_iterator cend() const noexcept; + const_reverse_iterator crbegin() const noexcept; + const_reverse_iterator crend() const noexcept; + + // capacity: + size_type size() const noexcept; + size_type max_size() const noexcept; + void resize(size_type n); + void resize(size_type n, const value_type& v); + void shrink_to_fit(); + bool empty() const noexcept; + + // element access: + reference operator[](size_type i); + const_reference operator[](size_type i) const; + reference at(size_type i); + const_reference at(size_type i) const; + reference front(); + const_reference front() const; + reference back(); + const_reference back() const; + + // modifiers: + void push_front(const value_type& v); + void push_front(value_type&& v); + template<container-compatible-range<T> R> + void prepend_range(R&& rg); // C++23 + void push_back(const value_type& v); + void push_back(value_type&& v); + template<container-compatible-range<T> R> + void append_range(R&& rg); // C++23 + template <class... Args> reference emplace_front(Args&&... args); // reference in C++17 + template <class... Args> reference emplace_back(Args&&... args); // reference in C++17 + template <class... Args> iterator emplace(const_iterator p, Args&&... args); + iterator insert(const_iterator p, const value_type& v); + iterator insert(const_iterator p, value_type&& v); + iterator insert(const_iterator p, size_type n, const value_type& v); + template <class InputIterator> + iterator insert(const_iterator p, InputIterator f, InputIterator l); + template<container-compatible-range<T> R> + iterator insert_range(const_iterator position, R&& rg); // C++23 + iterator insert(const_iterator p, initializer_list<value_type> il); + void pop_front(); + void pop_back(); + iterator erase(const_iterator p); + iterator erase(const_iterator f, const_iterator l); + void swap(deque& c) + noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 + void clear() noexcept; +}; + +template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> + deque(InputIterator, InputIterator, Allocator = Allocator()) + -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17 + +template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> + deque(from_range_t, R&&, Allocator = Allocator()) + -> deque<ranges::range_value_t<R>, Allocator>; // C++23 + +template <class T, class Allocator> + bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y); +template <class T, class Allocator> + bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20 +template <class T, class Allocator> + bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20 +template <class T, class Allocator> + bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20 +template <class T, class Allocator> + bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20 +template <class T, class Allocator> + bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20 +template<class T, class Allocator> + synth-three-way-result<T> operator<=>(const deque<T, Allocator>& x, + const deque<T, Allocator>& y); // since C++20 + +// specialized algorithms: +template <class T, class Allocator> + void swap(deque<T,Allocator>& x, deque<T,Allocator>& y) + noexcept(noexcept(x.swap(y))); + +template <class T, class Allocator, class U> + typename deque<T, Allocator>::size_type + erase(deque<T, Allocator>& c, const U& value); // C++20 +template <class T, class Allocator, class Predicate> + typename deque<T, Allocator>::size_type + erase_if(deque<T, Allocator>& c, Predicate pred); // C++20 + +} // std + +*/ + +#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) +# include <__cxx03/deque> +#else +# include <__algorithm/copy.h> +# include <__algorithm/copy_backward.h> +# include <__algorithm/copy_n.h> +# include <__algorithm/equal.h> +# include <__algorithm/fill_n.h> +# include <__algorithm/lexicographical_compare.h> +# include <__algorithm/lexicographical_compare_three_way.h> +# include <__algorithm/max.h> +# include <__algorithm/min.h> +# include <__algorithm/move.h> +# include <__algorithm/move_backward.h> +# include <__algorithm/ranges_copy_n.h> +# include <__algorithm/remove.h> +# include <__algorithm/remove_if.h> +# include <__assert> +# include <__config> +# include <__debug_utils/sanitizers.h> +# include <__format/enable_insertable.h> +# include <__fwd/deque.h> +# include <__iterator/distance.h> +# include <__iterator/iterator_traits.h> +# include <__iterator/move_iterator.h> +# include <__iterator/next.h> +# include <__iterator/prev.h> +# include <__iterator/reverse_iterator.h> +# include <__iterator/segmented_iterator.h> +# include <__memory/addressof.h> +# include <__memory/allocator.h> +# include <__memory/allocator_destructor.h> +# include <__memory/allocator_traits.h> +# include <__memory/compressed_pair.h> +# include <__memory/pointer_traits.h> +# include <__memory/swap_allocator.h> +# include <__memory/temp_value.h> +# include <__memory/unique_ptr.h> +# include <__memory_resource/polymorphic_allocator.h> +# include <__ranges/access.h> +# include <__ranges/concepts.h> +# include <__ranges/container_compatible_range.h> +# include <__ranges/from_range.h> +# include <__split_buffer> +# include <__type_traits/conditional.h> +# include <__type_traits/container_traits.h> +# include <__type_traits/enable_if.h> +# include <__type_traits/is_allocator.h> +# include <__type_traits/is_convertible.h> +# include <__type_traits/is_nothrow_assignable.h> +# include <__type_traits/is_nothrow_constructible.h> +# include <__type_traits/is_same.h> +# include <__type_traits/is_swappable.h> +# include <__type_traits/is_trivially_relocatable.h> +# include <__type_traits/type_identity.h> +# include <__utility/exception_guard.h> +# include <__utility/forward.h> +# include <__utility/move.h> +# include <__utility/pair.h> +# include <__utility/swap.h> +# include <limits> +# include <stdexcept> +# include <version> + +// standard-mandated includes + +// [iterator.range] +# include <__iterator/access.h> +# include <__iterator/data.h> +# include <__iterator/empty.h> +# include <__iterator/reverse_access.h> +# include <__iterator/size.h> + +// [deque.syn] +# include <compare> +# include <initializer_list> + +# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +# endif + +_LIBCPP_PUSH_MACROS +# include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class _ValueType, class _DiffType> +struct __deque_block_size { + static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16; +}; + +template <class _ValueType, + class _Pointer, + class _Reference, + class _MapPointer, + class _DiffType, + _DiffType _BS = +# ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE + // Keep template parameter to avoid changing all template declarations thoughout + // this file. + 0 +# else + __deque_block_size<_ValueType, _DiffType>::value +# endif + > +class __deque_iterator { + using __map_iterator _LIBCPP_NODEBUG = __rebind_pointer_t<_Pointer, const __rebind_pointer_t<_Pointer, _ValueType> >; + +// TODO(LLVM 25): Remove this check +# ifndef _LIBCPP_ABI_DEQUE_ITERATORS + static_assert( + sizeof(__map_iterator) == sizeof(_MapPointer) && _LIBCPP_ALIGNOF(__map_iterator) == _LIBCPP_ALIGNOF(_MapPointer), + "It looks like you are using fancy pointers such that FancyPtr<const FancyPtr<const value_type>> is not " + "layout-compatible with FancyPtr<FancyPtr<value_type>> or FancyPtr<const FancyPtr<value_type>>. " + "This means that your ABI is being broken between LLVM 22 and LLVM 23 if deque::iterator or " + "deque::const_iterator is used. If you don't care about your ABI being broken, define the " + "_LIBCPP_ABI_DEQUE_ITERATORS macro to silence this diagnostic."); +# endif + +public: + typedef _Pointer pointer; + typedef _DiffType difference_type; + +private: + __map_iterator __m_iter_; + pointer __ptr_; + + static const difference_type __block_size; + +public: + typedef _ValueType value_type; + typedef random_access_iterator_tag iterator_category; + typedef _Reference reference; + + _LIBCPP_HIDE_FROM_ABI __deque_iterator() _NOEXCEPT +# if _LIBCPP_STD_VER >= 14 + : __m_iter_(nullptr), + __ptr_(nullptr) +# endif + { + } + + template <class _Pp, class _Rp, class _MP, __enable_if_t<is_convertible<_Pp, pointer>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI + __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it) _NOEXCEPT + : __m_iter_(__it.__m_iter_), + __ptr_(__it.__ptr_) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *__ptr_; } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return __ptr_; } + + _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator++() { + if (++__ptr_ - *__m_iter_ == __block_size) { + ++__m_iter_; + __ptr_ = *__m_iter_; + } + return *this; + } + + _LIBCPP_HIDE_FROM_ABI __deque_iterator operator++(int) { + __deque_iterator __tmp = *this; + ++(*this); + return __tmp; + } + + _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator--() { + if (__ptr_ == *__m_iter_) { + --__m_iter_; + __ptr_ = *__m_iter_ + __block_size; + } + --__ptr_; + return *this; + } + + _LIBCPP_HIDE_FROM_ABI __deque_iterator operator--(int) { + __deque_iterator __tmp = *this; + --(*this); + return __tmp; + } + + _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator+=(difference_type __n) { + if (__n != 0) { + __n += __ptr_ - *__m_iter_; + if (__n > 0) { + __m_iter_ += __n / __block_size; + __ptr_ = *__m_iter_ + __n % __block_size; + } else // (__n < 0) + { + difference_type __z = __block_size - 1 - __n; + __m_iter_ -= __z / __block_size; + __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size); + } + } + return *this; + } + + _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator-=(difference_type __n) { return *this += -__n; } + + _LIBCPP_HIDE_FROM_ABI __deque_iterator operator+(difference_type __n) const { + __deque_iterator __t(*this); + __t += __n; + return __t; + } + + _LIBCPP_HIDE_FROM_ABI __deque_iterator operator-(difference_type __n) const { + __deque_iterator __t(*this); + __t -= __n; + return __t; + } + + _LIBCPP_HIDE_FROM_ABI friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it) { + return __it + __n; + } + + _LIBCPP_HIDE_FROM_ABI friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y) { + if (__x != __y) + return (__x.__m_iter_ - __y.__m_iter_) * __block_size + (__x.__ptr_ - *__x.__m_iter_) - + (__y.__ptr_ - *__y.__m_iter_); + return 0; + } + + _LIBCPP_HIDE_FROM_ABI reference operator[](difference_type __n) const { return *(*this + __n); } + + _LIBCPP_HIDE_FROM_ABI friend bool operator==(const __deque_iterator& __x, const __deque_iterator& __y) { + return __x.__ptr_ == __y.__ptr_; + } + +# if _LIBCPP_STD_VER <= 17 + _LIBCPP_HIDE_FROM_ABI friend bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y) { + return !(__x == __y); + } + _LIBCPP_HIDE_FROM_ABI friend bool operator<(const __deque_iterator& __x, const __deque_iterator& __y) { + return __x.__m_iter_ < __y.__m_iter_ || (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_); + } + + _LIBCPP_HIDE_FROM_ABI friend bool operator>(const __deque_iterator& __x, const __deque_iterator& __y) { + return __y < __x; + } + + _LIBCPP_HIDE_FROM_ABI friend bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y) { + return !(__y < __x); + } + + _LIBCPP_HIDE_FROM_ABI friend bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y) { + return !(__x < __y); + } + +# else + + _LIBCPP_HIDE_FROM_ABI friend strong_ordering operator<=>(const __deque_iterator& __x, const __deque_iterator& __y) { + if (__x.__m_iter_ < __y.__m_iter_) + return strong_ordering::less; + + if (__x.__m_iter_ == __y.__m_iter_) { + if constexpr (three_way_comparable<pointer, strong_ordering>) { + return __x.__ptr_ <=> __y.__ptr_; + } else { + if (__x.__ptr_ < __y.__ptr_) + return strong_ordering::less; + + if (__x.__ptr_ == __y.__ptr_) + return strong_ordering::equal; + + return strong_ordering::greater; + } + } + + return strong_ordering::greater; + } +# endif // _LIBCPP_STD_VER >= 20 + +private: + _LIBCPP_HIDE_FROM_ABI explicit __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT + : __m_iter_(__m), + __ptr_(__p) {} + + template <class _Tp, class _Ap> + friend class deque; + template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp> + friend class __deque_iterator; + + template <class> + friend struct __segmented_iterator_traits; +}; + +template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, class _DiffType, _DiffType _BlockSize> +struct __segmented_iterator_traits< + __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize> > { +private: + using _Iterator _LIBCPP_NODEBUG = + __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize>; + +public: + using __segment_iterator _LIBCPP_NODEBUG = typename _Iterator::__map_iterator; + using __local_iterator _LIBCPP_NODEBUG = _Pointer; + + static _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_Iterator __iter) { return __iter.__m_iter_; } + static _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_Iterator __iter) { return __iter.__ptr_; } + static _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) { return *__iter; } + + static _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) { + return *__iter + _Iterator::__block_size; + } + + static _LIBCPP_HIDE_FROM_ABI _Iterator __compose(__segment_iterator __segment, __local_iterator __local) { + if (__segment && __local == __end(__segment)) { + ++__segment; + return _Iterator(__segment, *__segment); + } + return _Iterator(__segment, __local); + } +}; + +template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, class _DiffType, _DiffType _BlockSize> +const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize>::__block_size = + __deque_block_size<_ValueType, _DiffType>::value; + +template <class _Tp, class _Allocator /*= allocator<_Tp>*/> +class deque { + template <class _Up, class _Alloc> + using __split_buffer _LIBCPP_NODEBUG = std::__split_buffer<_Up, _Alloc, __split_buffer_pointer_layout>; + +public: + // types: + + using value_type = _Tp; + + using allocator_type = _Allocator; + using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>; + static_assert(__check_valid_allocator<allocator_type>::value, ""); + static_assert(is_same<typename allocator_type::value_type, value_type>::value, + "Allocator::value_type must be same type as value_type"); + + using size_type = typename __alloc_traits::size_type; + using difference_type = typename __alloc_traits::difference_type; + + using pointer = typename __alloc_traits::pointer; + using const_pointer = typename __alloc_traits::const_pointer; + + using __pointer_allocator _LIBCPP_NODEBUG = __rebind_alloc<__alloc_traits, pointer>; + using __const_pointer_allocator _LIBCPP_NODEBUG = __rebind_alloc<__alloc_traits, const_pointer>; + using __map _LIBCPP_NODEBUG = __split_buffer<pointer, __pointer_allocator>; + using __map_alloc_traits _LIBCPP_NODEBUG = allocator_traits<__pointer_allocator>; + using __map_pointer _LIBCPP_NODEBUG = typename __map_alloc_traits::pointer; + using __map_const_pointer _LIBCPP_NODEBUG = typename allocator_traits<__const_pointer_allocator>::const_pointer; + using __map_const_iterator _LIBCPP_NODEBUG = typename __map::const_iterator; + + using reference = value_type&; + using const_reference = const value_type&; + + using iterator = __deque_iterator<value_type, pointer, reference, __map_pointer, difference_type>; + using const_iterator = + __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer, difference_type>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + + // A deque contains the following members which may be trivially relocatable: + // - __map: is a `__split_buffer`, see `__split_buffer` for more information on when it is trivially relocatable + // - size_type: is always trivially relocatable, since it is required to be an integral type + // - allocator_type: may not be trivially relocatable, so it's checked + // None of these are referencing the `deque` itself, so if all of them are trivially relocatable, `deque` is too. + using __trivially_relocatable _LIBCPP_NODEBUG = __conditional_t< + __libcpp_is_trivially_relocatable<__map>::value && __libcpp_is_trivially_relocatable<allocator_type>::value, + deque, + void>; + + static_assert(is_nothrow_default_constructible<allocator_type>::value == + is_nothrow_default_constructible<__pointer_allocator>::value, + "rebinding an allocator should not change exception guarantees"); + static_assert(is_nothrow_move_constructible<allocator_type>::value == + is_nothrow_move_constructible<typename __map::allocator_type>::value, + "rebinding an allocator should not change exception guarantees"); + +private: + struct __deque_block_range { + explicit _LIBCPP_HIDE_FROM_ABI __deque_block_range(pointer __b, pointer __e) _NOEXCEPT + : __begin_(__b), + __end_(__e) {} + const pointer __begin_; + const pointer __end_; + }; + + struct __deque_range { + iterator __pos_; + const iterator __end_; + + _LIBCPP_HIDE_FROM_ABI __deque_range(iterator __pos, iterator __e) _NOEXCEPT : __pos_(__pos), __end_(__e) {} + + explicit _LIBCPP_HIDE_FROM_ABI operator bool() const _NOEXCEPT { return __pos_ != __end_; } + + _LIBCPP_HIDE_FROM_ABI __deque_range begin() const { return *this; } + + _LIBCPP_HIDE_FROM_ABI __deque_range end() const { return __deque_range(__end_, __end_); } + _LIBCPP_HIDE_FROM_ABI __deque_block_range operator*() const _NOEXCEPT { + if (__pos_.__m_iter_ == __end_.__m_iter_) { + return __deque_block_range(__pos_.__ptr_, __end_.__ptr_); + } + return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size); + } + + _LIBCPP_HIDE_FROM_ABI __deque_range& operator++() _NOEXCEPT { + if (__pos_.__m_iter_ == __end_.__m_iter_) { + __pos_ = __end_; + } else { + ++__pos_.__m_iter_; + __pos_.__ptr_ = *__pos_.__m_iter_; + } + return *this; + } + + _LIBCPP_HIDE_FROM_ABI friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) { + return __lhs.__pos_ == __rhs.__pos_; + } + _LIBCPP_HIDE_FROM_ABI friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) { + return !(__lhs == __rhs); + } + }; + + struct _ConstructTransaction { + _LIBCPP_HIDE_FROM_ABI _ConstructTransaction(deque* __db, __deque_block_range& __r) + : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {} + + _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { __base_->__size() += (__pos_ - __begin_); } + + pointer __pos_; + const pointer __end_; + + private: + const pointer __begin_; + deque* const __base_; + }; + + static const difference_type __block_size; + + __map __map_; + size_type __start_; + _LIBCPP_COMPRESSED_PAIR(size_type, __size_, allocator_type, __alloc_); + +public: + // construct/copy/destroy: + _LIBCPP_HIDE_FROM_ABI deque() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) + : __start_(0), __size_(0) { + __annotate_new(0); + } + + _LIBCPP_HIDE_FROM_ABI ~deque() { + clear(); + __annotate_delete(); + typename __map::iterator __i = __map_.begin(); + typename __map::iterator __e = __map_.end(); + for (; __i != __e; ++__i) + __alloc_traits::deallocate(__alloc(), *__i, __block_size); + } + + _LIBCPP_HIDE_FROM_ABI explicit deque(const allocator_type& __a) + : __map_(__pointer_allocator(__a)), __start_(0), __size_(0), __alloc_(__a) { + __annotate_new(0); + } + + explicit _LIBCPP_HIDE_FROM_ABI deque(size_type __n); +# if _LIBCPP_STD_VER >= 14 + explicit _LIBCPP_HIDE_FROM_ABI deque(size_type __n, const _Allocator& __a); +# endif + _LIBCPP_HIDE_FROM_ABI deque(size_type __n, const value_type& __v); + + template <__enable_if_t<__is_allocator_v<_Allocator>, int> = 0> + _LIBCPP_HIDE_FROM_ABI deque(size_type __n, const value_type& __v, const allocator_type& __a) + : __map_(__pointer_allocator(__a)), __start_(0), __size_(0), __alloc_(__a) { + __annotate_new(0); + if (__n > 0) + __append(__n, __v); + } + + template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l); + template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l, const allocator_type& __a); + +# if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI deque(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type()) + : __map_(__pointer_allocator(__a)), __start_(0), __size_(0), __alloc_(__a) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + __append_with_size(ranges::begin(__range), ranges::distance(__range)); + + } else { + for (auto&& __e : __range) { + emplace_back(std::forward<decltype(__e)>(__e)); + } + } + } +# endif + + _LIBCPP_HIDE_FROM_ABI deque(const deque& __c); + _LIBCPP_HIDE_FROM_ABI deque(const deque& __c, const __type_identity_t<allocator_type>& __a); + + _LIBCPP_HIDE_FROM_ABI deque& operator=(const deque& __c); + +# ifndef _LIBCPP_CXX03_LANG + _LIBCPP_HIDE_FROM_ABI deque(initializer_list<value_type> __il); + _LIBCPP_HIDE_FROM_ABI deque(initializer_list<value_type> __il, const allocator_type& __a); + + _LIBCPP_HIDE_FROM_ABI deque& operator=(initializer_list<value_type> __il) { + assign(__il); + return *this; + } + + _LIBCPP_HIDE_FROM_ABI deque(deque&& __c) noexcept(is_nothrow_move_constructible<allocator_type>::value); + _LIBCPP_HIDE_FROM_ABI deque(deque&& __c, const __type_identity_t<allocator_type>& __a); + _LIBCPP_HIDE_FROM_ABI deque& operator=(deque&& __c) noexcept( + (__alloc_traits::propagate_on_container_move_assignment::value && + is_nothrow_move_assignable<allocator_type>::value) || + __alloc_traits::is_always_equal::value); + + _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il) { assign(__il.begin(), __il.end()); } +# endif // _LIBCPP_CXX03_LANG + + template <class _InputIter, + __enable_if_t<__has_input_iterator_category<_InputIter>::value && + !__has_random_access_iterator_category<_InputIter>::value, + int> = 0> + _LIBCPP_HIDE_FROM_ABI void assign(_InputIter __f, _InputIter __l); + template <class _RAIter, __enable_if_t<__has_random_access_iterator_category<_RAIter>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI void assign(_RAIter __f, _RAIter __l); + +# if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) { + if constexpr (ranges::random_access_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + __assign_with_size_random_access(ranges::begin(__range), __n); + + } else if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = ranges::distance(__range); + auto __first = ranges::begin(__range); + + auto __result = std::ranges::copy_n(std::move(__first), std::min<size_t>(__n, size()), begin()); + + if (static_cast<size_type>(__n) > size()) { + __append_with_size(std::move(__result.in), __n - size()); + } else { + __erase_to_end(__result.out); + } + + } else { + __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +# endif + + _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v); + + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT; + _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __alloc_; } + _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __alloc_; } + + // iterators: + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { + auto __mp = __map_.begin() + __start_ / __block_size; + return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size); + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { + auto __mp = __map_.begin() + __start_ / __block_size; + return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size); + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { + size_type __p = size() + __start_; + auto __mp = __map_.begin() + __p / __block_size; + return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size); + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { + size_type __p = size() + __start_; + auto __mp = __map_.begin() + __p / __block_size; + return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size); + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { + return const_reverse_iterator(end()); + } + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { + return const_reverse_iterator(begin()); + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { + return const_reverse_iterator(end()); + } + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { + return const_reverse_iterator(begin()); + } + + // capacity: + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size(); } + + _LIBCPP_HIDE_FROM_ABI size_type& __size() _NOEXCEPT { return __size_; } + _LIBCPP_HIDE_FROM_ABI const size_type& __size() const _NOEXCEPT { return __size_; } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { + return std::min<size_type>(__alloc_traits::max_size(__alloc()), numeric_limits<difference_type>::max()); + } + _LIBCPP_HIDE_FROM_ABI void resize(size_type __n); + _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v); + _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT; + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return size() == 0; } + + // element access: + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __i) _NOEXCEPT; + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_type __i) const _NOEXCEPT; + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reference at(size_type __i); + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __i) const; + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reference front() _NOEXCEPT; + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reference front() const _NOEXCEPT; + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT; + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT; + + // 23.2.2.3 modifiers: + _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v); + _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __v); + + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI iterator __emplace(const_iterator __p, _Args&&... __args); + +# ifndef _LIBCPP_CXX03_LANG +# if _LIBCPP_STD_VER >= 17 + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args); + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI reference emplace_back(_Args&&... __args); +# else + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args); + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args); +# endif + + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args) { + return __emplace(__p, std::forward<_Args>(__args)...); + } + + _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v); + _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __v); + +# if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) { + insert_range(begin(), std::forward<_Range>(__range)); + } + + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI void append_range(_Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + __append_with_size(ranges::begin(__range), ranges::distance(__range)); + } else { + __append_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +# endif + + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { return __emplace(__p, std::move(__v)); } + + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, initializer_list<value_type> __il) { + return insert(__p, __il.begin(), __il.end()); + } +# endif // _LIBCPP_CXX03_LANG + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { return __emplace(__p, __v); } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __v); + template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InputIter __f, _InputIter __l); + template <class _ForwardIterator, + __enable_if_t<__has_exactly_forward_iterator_category<_ForwardIterator>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l); + template <class _BiIter, __enable_if_t<__has_bidirectional_iterator_category<_BiIter>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _BiIter __f, _BiIter __l); + +# if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI iterator insert_range(const_iterator __position, _Range&& __range) { + if constexpr (ranges::bidirectional_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + return __insert_bidirectional(__position, ranges::begin(__range), ranges::end(__range), __n); + + } else if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + return __insert_with_size(__position, ranges::begin(__range), __n); + + } else { + return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); + } + } +# endif + + _LIBCPP_HIDE_FROM_ABI void pop_front(); + _LIBCPP_HIDE_FROM_ABI void pop_back(); + _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p); + _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l); + + _LIBCPP_HIDE_FROM_ABI void swap(deque& __c) +# if _LIBCPP_STD_VER >= 14 + _NOEXCEPT; +# else + _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>); +# endif + _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT; + + _LIBCPP_HIDE_FROM_ABI bool __invariants() const { + if (!__map_.__invariants()) + return false; + if (__map_.size() >= size_type(-1) / __block_size) + return false; + for (__map_const_iterator __i = __map_.begin(), __e = __map_.end(); __i != __e; ++__i) + if (*__i == nullptr) + return false; + if (__map_.size() != 0) { + if (size() >= __map_.size() * __block_size) + return false; + if (__start_ >= __map_.size() * __block_size - size()) + return false; + } else { + if (size() != 0) + return false; + if (__start_ != 0) + return false; + } + return true; + } + + _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(deque& __c) + _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value || + is_nothrow_move_assignable<allocator_type>::value) { + __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>()); + } + + _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(deque& __c, true_type) + _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) { + __alloc() = std::move(__c.__alloc()); + } + + _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(deque&, false_type) _NOEXCEPT {} + + _LIBCPP_HIDE_FROM_ABI void __move_assign(deque& __c) + _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value&& + is_nothrow_move_assignable<allocator_type>::value) { + __map_ = std::move(__c.__map_); + __start_ = __c.__start_; + __size() = __c.size(); + __move_assign_alloc(__c); + __c.__start_ = __c.__size() = 0; + } + + _LIBCPP_HIDE_FROM_ABI static size_type __recommend_blocks(size_type __n) { + return __n / __block_size + (__n % __block_size != 0); + } + _LIBCPP_HIDE_FROM_ABI size_type __capacity() const { + return __map_.size() == 0 ? 0 : __map_.size() * __block_size - 1; + } + _LIBCPP_HIDE_FROM_ABI size_type __block_count() const { return __map_.size(); } + + _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const { return __start_; } + _LIBCPP_HIDE_FROM_ABI size_type __front_spare_blocks() const { return __front_spare() / __block_size; } + _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const { return __capacity() - (__start_ + size()); } + _LIBCPP_HIDE_FROM_ABI size_type __back_spare_blocks() const { return __back_spare() / __block_size; } + +private: + enum __asan_annotation_type { __asan_unposion, __asan_poison }; + + enum __asan_annotation_place { + __asan_front_moved, + __asan_back_moved, + }; + + _LIBCPP_HIDE_FROM_ABI void __annotate_from_to( + size_type __beg, + size_type __end, + __asan_annotation_type __annotation_type, + __asan_annotation_place __place) const _NOEXCEPT { + (void)__beg; + (void)__end; + (void)__annotation_type; + (void)__place; +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + // __beg - index of the first item to annotate + // __end - index behind the last item to annotate (so last item + 1) + // __annotation_type - __asan_unposion or __asan_poison + // __place - __asan_front_moved or __asan_back_moved + // Note: All indexes in __map_ + if (__beg == __end) + return; + // __annotations_beg_map - first chunk which annotations we want to modify + // __annotations_end_map - last chunk which annotations we want to modify + // NOTE: if __end % __block_size == 0, __annotations_end_map points at the next block, which may not exist + __map_const_iterator __annotations_beg_map = __map_.begin() + __beg / __block_size; + __map_const_iterator __annotations_end_map = __map_.begin() + __end / __block_size; + + bool const __poisoning = __annotation_type == __asan_poison; + // __old_c_beg_index - index of the first element in old container + // __old_c_end_index - index of the end of old container (last + 1) + // Note: may be outside the area we are annotating + size_t __old_c_beg_index = (__poisoning && __place == __asan_front_moved) ? __beg : __start_; + size_t __old_c_end_index = (__poisoning && __place == __asan_back_moved) ? __end : __start_ + size(); + bool const __front = __place == __asan_front_moved; + + if (__poisoning && empty()) { + // Special case: we shouldn't trust __start_ + __old_c_beg_index = __beg; + __old_c_end_index = __end; + } + // __old_c_beg_map - memory block (chunk) with first element + // __old_c_end_map - memory block (chunk) with end of old container + // Note: if __old_c_end_index % __block_size == 0, __old_c_end_map points at the next block, + // which may not exist + __map_const_iterator __old_c_beg_map = __map_.begin() + __old_c_beg_index / __block_size; + __map_const_iterator __old_c_end_map = __map_.begin() + __old_c_end_index / __block_size; + + // One edge (front/end) of the container was moved and one was not modified. + // __new_edge_index - index of new edge + // __new_edge_map - memory block (chunk) with new edge, it always equals to + // __annotations_beg_map or __annotations_end_map + // __old_edge_map - memory block (chunk) with old edge, it always equals to + // __old_c_beg_map or __old_c_end_map + size_t __new_edge_index = (__poisoning ^ __front) ? __beg : __end; + __map_const_iterator __new_edge_map = __map_.begin() + __new_edge_index / __block_size; + __map_const_iterator __old_edge_map = __front ? __old_c_end_map : __old_c_beg_map; + + // We iterate over map pointers (chunks) and fully poison all memory blocks between the first and the last. + // First and last chunk may be partially poisoned. + // __annotate_end_map may point at not existing chunk, therefore we have to have a check for it. + for (__map_const_iterator __map_it = __annotations_beg_map; __map_it <= __annotations_end_map; ++__map_it) { + if (__map_it == __annotations_end_map && __end % __block_size == 0) + // Chunk may not exist, but nothing to do here anyway + break; + + // The beginning and the end of the current memory block + const void* __mem_beg = std::__to_address(*__map_it); + const void* __mem_end = std::__to_address(*__map_it + __block_size); + + // The beginning of memory-in-use in the memory block before container modification + const void* __old_beg = + (__map_it == __old_c_beg_map) ? std::__to_address(*__map_it + (__old_c_beg_index % __block_size)) : __mem_beg; + + // The end of memory-in-use in the memory block before container modification + const void* __old_end; + if (__map_it < __old_c_beg_map || __map_it > __old_c_end_map || (!__poisoning && empty())) + __old_end = __old_beg; + else + __old_end = (__map_it == __old_c_end_map) + ? std::__to_address(*__map_it + (__old_c_end_index % __block_size)) + : __mem_end; + + // New edge of the container in current memory block + // If the edge is in a different chunk it points on corresponding end of the memory block + const void* __new_edge; + if (__map_it == __new_edge_map) + __new_edge = std::__to_address(*__map_it + (__new_edge_index % __block_size)); + else + __new_edge = (__poisoning ^ __front) ? __mem_beg : __mem_end; + + // Not modified edge of the container + // If the edge is in a different chunk it points on corresponding end of the memory block + const void* __old_edge; + if (__map_it == __old_edge_map) + __old_edge = __front ? __old_end : __old_beg; + else + __old_edge = __front ? __mem_end : __mem_beg; + + // __new_beg - the beginning of memory-in-use in the memory block after container modification + // __new_end - the end of memory-in-use in the memory block after container modification + const void* __new_beg = __front ? __new_edge : __old_edge; + const void* __new_end = __front ? __old_edge : __new_edge; + + std::__annotate_double_ended_contiguous_container<_Allocator>( + __mem_beg, __mem_end, __old_beg, __old_end, __new_beg, __new_end); + } +# endif // _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + } + + _LIBCPP_HIDE_FROM_ABI void __annotate_new(size_type __current_size) const _NOEXCEPT { + (void)__current_size; +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + if (__current_size == 0) + __annotate_from_to(0, __map_.size() * __block_size, __asan_poison, __asan_back_moved); + else { + __annotate_from_to(0, __start_, __asan_poison, __asan_front_moved); + __annotate_from_to(__start_ + __current_size, __map_.size() * __block_size, __asan_poison, __asan_back_moved); + } +# endif // _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + } + + _LIBCPP_HIDE_FROM_ABI void __annotate_delete() const _NOEXCEPT { +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + if (empty()) { + for (size_t __i = 0; __i < __map_.size(); ++__i) { + __annotate_whole_block(__i, __asan_unposion); + } + } else { + __annotate_from_to(0, __start_, __asan_unposion, __asan_front_moved); + __annotate_from_to(__start_ + size(), __map_.size() * __block_size, __asan_unposion, __asan_back_moved); + } +# endif // _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + } + + _LIBCPP_HIDE_FROM_ABI void __annotate_increase_front(size_type __n) const _NOEXCEPT { + (void)__n; +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + __annotate_from_to(__start_ - __n, __start_, __asan_unposion, __asan_front_moved); +# endif + } + + _LIBCPP_HIDE_FROM_ABI void __annotate_increase_back(size_type __n) const _NOEXCEPT { + (void)__n; +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + __annotate_from_to(__start_ + size(), __start_ + size() + __n, __asan_unposion, __asan_back_moved); +# endif + } + + _LIBCPP_HIDE_FROM_ABI void __annotate_shrink_front(size_type __old_size, size_type __old_start) const _NOEXCEPT { + (void)__old_size; + (void)__old_start; +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + __annotate_from_to(__old_start, __old_start + (__old_size - size()), __asan_poison, __asan_front_moved); +# endif + } + + _LIBCPP_HIDE_FROM_ABI void __annotate_shrink_back(size_type __old_size, size_type __old_start) const _NOEXCEPT { + (void)__old_size; + (void)__old_start; +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + __annotate_from_to(__old_start + size(), __old_start + __old_size, __asan_poison, __asan_back_moved); +# endif + } + + _LIBCPP_HIDE_FROM_ABI void __annotate_poison_block(const void* __beginning, const void* __end) const _NOEXCEPT { + std::__annotate_double_ended_contiguous_container<_Allocator>(__beginning, __end, __beginning, __end, __end, __end); + } + + _LIBCPP_HIDE_FROM_ABI void + __annotate_whole_block(size_t __block_index, __asan_annotation_type __annotation_type) const _NOEXCEPT { + (void)__block_index; + (void)__annotation_type; +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + __map_const_iterator __block_it = __map_.begin() + __block_index; + const void* __block_start = std::__to_address(*__block_it); + const void* __block_end = std::__to_address(*__block_it + __block_size); + + if (__annotation_type == __asan_poison) + __annotate_poison_block(__block_start, __block_end); + else { + std::__annotate_double_ended_contiguous_container<_Allocator>( + __block_start, __block_end, __block_start, __block_start, __block_start, __block_end); + } +# endif + } +# if _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + +public: + _LIBCPP_HIDE_FROM_ABI bool __verify_asan_annotations() const _NOEXCEPT { + // This function tests deque object annotations. + if (empty()) { + for (__map_const_iterator __it = __map_.begin(); __it != __map_.end(); ++__it) { + if (!::__sanitizer_verify_double_ended_contiguous_container( + std::__to_address(*__it), + std::__to_address(*__it), + std::__to_address(*__it), + std::__to_address(*__it + __block_size))) + return false; + } + + return true; + } + + size_type __end = __start_ + size(); + __map_const_iterator __first_mp = __map_.begin() + __start_ / __block_size; + __map_const_iterator __last_mp = __map_.begin() + (__end - 1) / __block_size; + + // Pointers to first and after last elements + // Those can be in different deque blocks + const void* __p_beg = std::__to_address(*__first_mp + (__start_ % __block_size)); + const void* __p_end = + std::__to_address(*__last_mp + ((__end % __block_size == 0) ? __block_size : __end % __block_size)); + + for (__map_const_iterator __it = __map_.begin(); __it != __map_.end(); ++__it) { + // Go over all blocks, find the place we are in and verify its annotations + // Note that __p_end points *behind* the last item. + + // - blocks before the first block with container elements + // - first block with items + // - last block with items + // - blocks after last block with ciontainer elements + + // Is the block before or after deque blocks that contain elements? + if (__it < __first_mp || __it > __last_mp) { + if (!::__sanitizer_verify_double_ended_contiguous_container( + std::__to_address(*__it), + std::__to_address(*__it), + std::__to_address(*__it), + std::__to_address(*__it + __block_size))) + return false; + } else { + const void* __containers_buffer_beg = (__it == __first_mp) ? __p_beg : (const void*)std::__to_address(*__it); + const void* __containers_buffer_end = + (__it == __last_mp) ? __p_end : (const void*)std::__to_address(*__it + __block_size); + if (!::__sanitizer_verify_double_ended_contiguous_container( + std::__to_address(*__it), + __containers_buffer_beg, + __containers_buffer_end, + std::__to_address(*__it + __block_size))) { + return false; + } + } + } + return true; + } + +private: +# endif // _LIBCPP_ENABLE_ASAN_CONTAINER_CHECKS + _LIBCPP_HIDE_FROM_ABI bool __maybe_remove_front_spare(bool __keep_one = true) { + if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) { + __annotate_whole_block(0, __asan_unposion); + __alloc_traits::deallocate(__alloc(), __map_.front(), __block_size); + __map_.pop_front(); + __start_ -= __block_size; + return true; + } + return false; + } + + _LIBCPP_HIDE_FROM_ABI bool __maybe_remove_back_spare(bool __keep_one = true) { + if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) { + __annotate_whole_block(__map_.size() - 1, __asan_unposion); + __alloc_traits::deallocate(__alloc(), __map_.back(), __block_size); + __map_.pop_back(); + return true; + } + return false; + } + + template <class _Iterator, class _Sentinel> + _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __f, _Sentinel __l); + + template <class _RandomAccessIterator> + _LIBCPP_HIDE_FROM_ABI void __assign_with_size_random_access(_RandomAccessIterator __f, difference_type __n); + template <class _AlgPolicy, class _Iterator> + _LIBCPP_HIDE_FROM_ABI void __assign_with_size(_Iterator __f, difference_type __n); + + template <class _Iterator, class _Sentinel> + _LIBCPP_HIDE_FROM_ABI iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l); + + template <class _Iterator> + _LIBCPP_HIDE_FROM_ABI iterator __insert_with_size(const_iterator __p, _Iterator __f, size_type __n); + + template <class _BiIter, class _Sentinel> + _LIBCPP_HIDE_FROM_ABI iterator + __insert_bidirectional(const_iterator __p, _BiIter __f, _Sentinel __sent, size_type __n); + template <class _BiIter> + _LIBCPP_HIDE_FROM_ABI iterator __insert_bidirectional(const_iterator __p, _BiIter __f, _BiIter __l, size_type __n); + + template <class _InpIter, __enable_if_t<__has_exactly_input_iterator_category<_InpIter>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI void __append(_InpIter __f, _InpIter __l); + template <class _ForIter, __enable_if_t<__has_forward_iterator_category<_ForIter>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI void __append(_ForIter __f, _ForIter __l); + + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI void __append_with_size(_InputIterator __from, size_type __n); + template <class _InputIterator, class _Sentinel> + _LIBCPP_HIDE_FROM_ABI void __append_with_sentinel(_InputIterator __f, _Sentinel __l); + + _LIBCPP_HIDE_FROM_ABI void __append(size_type __n); + _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const value_type& __v); + _LIBCPP_HIDE_FROM_ABI void __erase_to_end(const_iterator __f); + _LIBCPP_HIDE_FROM_ABI void __add_front_capacity(); + _LIBCPP_HIDE_FROM_ABI void __add_front_capacity(size_type __n); + _LIBCPP_HIDE_FROM_ABI void __add_back_capacity(); + _LIBCPP_HIDE_FROM_ABI void __add_back_capacity(size_type __n); + _LIBCPP_HIDE_FROM_ABI iterator __move_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt); + _LIBCPP_HIDE_FROM_ABI iterator + __move_backward_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt); + _LIBCPP_HIDE_FROM_ABI void __move_construct_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt); + _LIBCPP_HIDE_FROM_ABI void + __move_construct_backward_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt); + + _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const deque& __c) { + __copy_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_copy_assignment::value>()); + } + + _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const deque& __c, true_type) { + if (__alloc() != __c.__alloc()) { + clear(); + shrink_to_fit(); + } + __alloc() = __c.__alloc(); + __map_.__get_allocator() = __c.__map_.__get_allocator(); + } + + _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const deque&, false_type) {} + + _LIBCPP_HIDE_FROM_ABI void __move_assign(deque& __c, true_type) + _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); + _LIBCPP_HIDE_FROM_ABI void __move_assign(deque& __c, false_type); +}; + +template <class _Tp, class _Alloc> +_LIBCPP_CONSTEXPR const typename allocator_traits<_Alloc>::difference_type deque<_Tp, _Alloc>::__block_size = + __deque_block_size<value_type, difference_type>::value; + +# if _LIBCPP_STD_VER >= 17 +template <class _InputIterator, + class _Alloc = allocator<__iterator_value_type<_InputIterator>>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, + class = enable_if_t<__is_allocator_v<_Alloc>>> +deque(_InputIterator, _InputIterator) -> deque<__iterator_value_type<_InputIterator>, _Alloc>; + +template <class _InputIterator, + class _Alloc, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, + class = enable_if_t<__is_allocator_v<_Alloc>>> +deque(_InputIterator, _InputIterator, _Alloc) -> deque<__iterator_value_type<_InputIterator>, _Alloc>; +# endif + +# if _LIBCPP_STD_VER >= 23 +template <ranges::input_range _Range, + class _Alloc = allocator<ranges::range_value_t<_Range>>, + class = enable_if_t<__is_allocator_v<_Alloc>>> +deque(from_range_t, _Range&&, _Alloc = _Alloc()) -> deque<ranges::range_value_t<_Range>, _Alloc>; +# endif + +template <class _Tp, class _Allocator> +deque<_Tp, _Allocator>::deque(size_type __n) : __start_(0), __size_(0) { + __annotate_new(0); + if (__n > 0) + __append(__n); +} + +# if _LIBCPP_STD_VER >= 14 +template <class _Tp, class _Allocator> +deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a) + : __map_(__pointer_allocator(__a)), __start_(0), __size_(0), __alloc_(__a) { + __annotate_new(0); + if (__n > 0) + __append(__n); +} +# endif + +template <class _Tp, class _Allocator> +deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v) : __start_(0), __size_(0) { + __annotate_new(0); + if (__n > 0) + __append(__n, __v); +} + +template <class _Tp, class _Allocator> +template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> > +deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l) : __start_(0), __size_(0) { + __annotate_new(0); + __append(__f, __l); +} + +template <class _Tp, class _Allocator> +template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> > +deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a) + : __map_(__pointer_allocator(__a)), __start_(0), __size_(0), __alloc_(__a) { + __annotate_new(0); + __append(__f, __l); +} + +template <class _Tp, class _Allocator> +deque<_Tp, _Allocator>::deque(const deque& __c) + : __map_(__pointer_allocator(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))), + __start_(0), + __size_(0), + __alloc_(__map_.__get_allocator()) { + __annotate_new(0); + __append(__c.begin(), __c.end()); +} + +template <class _Tp, class _Allocator> +deque<_Tp, _Allocator>::deque(const deque& __c, const __type_identity_t<allocator_type>& __a) + : __map_(__pointer_allocator(__a)), __start_(0), __size_(0), __alloc_(__a) { + __annotate_new(0); + __append(__c.begin(), __c.end()); +} + +template <class _Tp, class _Allocator> +deque<_Tp, _Allocator>& deque<_Tp, _Allocator>::operator=(const deque& __c) { + if (this != std::addressof(__c)) { + __copy_assign_alloc(__c); + assign(__c.begin(), __c.end()); + } + return *this; +} + +# ifndef _LIBCPP_CXX03_LANG + +template <class _Tp, class _Allocator> +deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il) : __start_(0), __size_(0) { + __annotate_new(0); + __append(__il.begin(), __il.end()); +} + +template <class _Tp, class _Allocator> +deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a) + : __map_(__pointer_allocator(__a)), __start_(0), __size_(0), __alloc_(__a) { + __annotate_new(0); + __append(__il.begin(), __il.end()); +} + +template <class _Tp, class _Allocator> +inline deque<_Tp, _Allocator>::deque(deque&& __c) noexcept(is_nothrow_move_constructible<allocator_type>::value) + : __map_(std::move(__c.__map_)), + __start_(std::move(__c.__start_)), + __size_(std::move(__c.__size_)), + __alloc_(std::move(__c.__alloc_)) { + __c.__start_ = 0; + __c.__size() = 0; +} + +template <class _Tp, class _Allocator> +inline deque<_Tp, _Allocator>::deque(deque&& __c, const __type_identity_t<allocator_type>& __a) + : __map_(std::move(__c.__map_), __pointer_allocator(__a)), + __start_(std::move(__c.__start_)), + __size_(std::move(__c.__size_)), + __alloc_(__a) { + if (__a == __c.__alloc()) { + __c.__start_ = 0; + __c.__size() = 0; + } else { + __map_.clear(); + __start_ = 0; + __size() = 0; + typedef move_iterator<iterator> _Ip; + assign(_Ip(__c.begin()), _Ip(__c.end())); + } +} + +template <class _Tp, class _Allocator> +inline deque<_Tp, _Allocator>& deque<_Tp, _Allocator>::operator=(deque&& __c) noexcept( + (__alloc_traits::propagate_on_container_move_assignment::value && + is_nothrow_move_assignable<allocator_type>::value) || + __alloc_traits::is_always_equal::value) { + __move_assign(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>()); + return *this; +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type) { + if (__alloc() != __c.__alloc()) { + typedef move_iterator<iterator> _Ip; + assign(_Ip(__c.begin()), _Ip(__c.end())); + } else + __move_assign(__c, true_type()); +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__move_assign(deque& __c, + true_type) noexcept(is_nothrow_move_assignable<allocator_type>::value) { + clear(); + shrink_to_fit(); + __move_assign(__c); +} + +# endif // _LIBCPP_CXX03_LANG + +template <class _Tp, class _Allocator> +template <class _InputIter, + __enable_if_t<__has_input_iterator_category<_InputIter>::value && + !__has_random_access_iterator_category<_InputIter>::value, + int> > +void deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l) { + __assign_with_sentinel(__f, __l); +} + +template <class _Tp, class _Allocator> +template <class _Iterator, class _Sentinel> +_LIBCPP_HIDE_FROM_ABI void deque<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) { + iterator __i = begin(); + iterator __e = end(); + for (; __f != __l && __i != __e; ++__f, (void)++__i) + *__i = *__f; + if (__f != __l) + __append_with_sentinel(std::move(__f), std::move(__l)); + else + __erase_to_end(__i); +} + +template <class _Tp, class _Allocator> +template <class _RAIter, __enable_if_t<__has_random_access_iterator_category<_RAIter>::value, int> > +void deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l) { + __assign_with_size_random_access(__f, __l - __f); +} + +template <class _Tp, class _Allocator> +template <class _RandomAccessIterator> +_LIBCPP_HIDE_FROM_ABI void +deque<_Tp, _Allocator>::__assign_with_size_random_access(_RandomAccessIterator __f, difference_type __n) { + if (static_cast<size_type>(__n) > size()) { + auto __l = __f + size(); + std::copy(__f, __l, begin()); + __append_with_size(__l, __n - size()); + } else + __erase_to_end(std::copy_n(__f, __n, begin())); +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v) { + if (__n > size()) { + std::fill_n(begin(), size(), __v); + __n -= size(); + __append(__n, __v); + } else + __erase_to_end(std::fill_n(begin(), __n, __v)); +} + +template <class _Tp, class _Allocator> +inline _Allocator deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT { + return __alloc(); +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::resize(size_type __n) { + if (__n > size()) + __append(__n - size()); + else if (__n < size()) + __erase_to_end(begin() + __n); +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v) { + if (__n > size()) + __append(__n - size(), __v); + else if (__n < size()) + __erase_to_end(begin() + __n); +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT { + allocator_type& __a = __alloc(); + if (empty()) { + __annotate_delete(); + while (__map_.size() > 0) { + __alloc_traits::deallocate(__a, __map_.back(), __block_size); + __map_.pop_back(); + } + __start_ = 0; + } else { + __maybe_remove_front_spare(/*__keep_one=*/false); + __maybe_remove_back_spare(/*__keep_one=*/false); + } + __map_.shrink_to_fit(); +} + +template <class _Tp, class _Allocator> +inline typename deque<_Tp, _Allocator>::reference deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i < size(), "deque::operator[] index out of bounds"); + size_type __p = __start_ + __i; + return *(*(__map_.begin() + __p / __block_size) + __p % __block_size); +} + +template <class _Tp, class _Allocator> +inline typename deque<_Tp, _Allocator>::const_reference +deque<_Tp, _Allocator>::operator[](size_type __i) const _NOEXCEPT { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i < size(), "deque::operator[] index out of bounds"); + size_type __p = __start_ + __i; + return *(*(__map_.begin() + __p / __block_size) + __p % __block_size); +} + +template <class _Tp, class _Allocator> +inline typename deque<_Tp, _Allocator>::reference deque<_Tp, _Allocator>::at(size_type __i) { + if (__i >= size()) + std::__throw_out_of_range("deque"); + size_type __p = __start_ + __i; + return *(*(__map_.begin() + __p / __block_size) + __p % __block_size); +} + +template <class _Tp, class _Allocator> +inline typename deque<_Tp, _Allocator>::const_reference deque<_Tp, _Allocator>::at(size_type __i) const { + if (__i >= size()) + std::__throw_out_of_range("deque"); + size_type __p = __start_ + __i; + return *(*(__map_.begin() + __p / __block_size) + __p % __block_size); +} + +template <class _Tp, class _Allocator> +inline typename deque<_Tp, _Allocator>::reference deque<_Tp, _Allocator>::front() _NOEXCEPT { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::front called on an empty deque"); + return *(*(__map_.begin() + __start_ / __block_size) + __start_ % __block_size); +} + +template <class _Tp, class _Allocator> +inline typename deque<_Tp, _Allocator>::const_reference deque<_Tp, _Allocator>::front() const _NOEXCEPT { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::front called on an empty deque"); + return *(*(__map_.begin() + __start_ / __block_size) + __start_ % __block_size); +} + +template <class _Tp, class _Allocator> +inline typename deque<_Tp, _Allocator>::reference deque<_Tp, _Allocator>::back() _NOEXCEPT { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::back called on an empty deque"); + size_type __p = size() + __start_ - 1; + return *(*(__map_.begin() + __p / __block_size) + __p % __block_size); +} + +template <class _Tp, class _Allocator> +inline typename deque<_Tp, _Allocator>::const_reference deque<_Tp, _Allocator>::back() const _NOEXCEPT { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::back called on an empty deque"); + size_type __p = size() + __start_ - 1; + return *(*(__map_.begin() + __p / __block_size) + __p % __block_size); +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::push_back(const value_type& __v) { + allocator_type& __a = __alloc(); + if (__back_spare() == 0) + __add_back_capacity(); + // __back_spare() >= 1 + __annotate_increase_back(1); + __alloc_traits::construct(__a, std::addressof(*end()), __v); + ++__size(); +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::push_front(const value_type& __v) { + allocator_type& __a = __alloc(); + if (__front_spare() == 0) + __add_front_capacity(); + // __front_spare() >= 1 + __annotate_increase_front(1); + __alloc_traits::construct(__a, std::addressof(*--begin()), __v); + --__start_; + ++__size(); +} + +# ifndef _LIBCPP_CXX03_LANG +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::push_back(value_type&& __v) { + allocator_type& __a = __alloc(); + if (__back_spare() == 0) + __add_back_capacity(); + // __back_spare() >= 1 + __annotate_increase_back(1); + __alloc_traits::construct(__a, std::addressof(*end()), std::move(__v)); + ++__size(); +} + +template <class _Tp, class _Allocator> +template <class... _Args> +# if _LIBCPP_STD_VER >= 17 +typename deque<_Tp, _Allocator>::reference +# else +void +# endif +deque<_Tp, _Allocator>::emplace_back(_Args&&... __args) { + allocator_type& __a = __alloc(); + if (__back_spare() == 0) + __add_back_capacity(); + // __back_spare() >= 1 + __annotate_increase_back(1); + __alloc_traits::construct(__a, std::addressof(*end()), std::forward<_Args>(__args)...); + ++__size(); +# if _LIBCPP_STD_VER >= 17 + return *--end(); +# endif +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::push_front(value_type&& __v) { + allocator_type& __a = __alloc(); + if (__front_spare() == 0) + __add_front_capacity(); + // __front_spare() >= 1 + __annotate_increase_front(1); + __alloc_traits::construct(__a, std::addressof(*--begin()), std::move(__v)); + --__start_; + ++__size(); +} + +template <class _Tp, class _Allocator> +template <class... _Args> +# if _LIBCPP_STD_VER >= 17 +typename deque<_Tp, _Allocator>::reference +# else +void +# endif +deque<_Tp, _Allocator>::emplace_front(_Args&&... __args) { + allocator_type& __a = __alloc(); + if (__front_spare() == 0) + __add_front_capacity(); + // __front_spare() >= 1 + __annotate_increase_front(1); + __alloc_traits::construct(__a, std::addressof(*--begin()), std::forward<_Args>(__args)...); + --__start_; + ++__size(); +# if _LIBCPP_STD_VER >= 17 + return *begin(); +# endif +} +# endif // _LIBCPP_CXX03_LANG + +template <class _Tp, class _Allocator> +template <class... _Args> +typename deque<_Tp, _Allocator>::iterator deque<_Tp, _Allocator>::__emplace(const_iterator __p, _Args&&... __args) { + size_type __pos = __p - begin(); + size_type __to_end = size() - __pos; + allocator_type& __a = __alloc(); + if (__pos < __to_end) { // insert by shifting things backward + if (__front_spare() == 0) + __add_front_capacity(); + // __front_spare() >= 1 + __annotate_increase_front(1); + if (__pos == 0) { + __alloc_traits::construct(__a, std::addressof(*--begin()), std::forward<_Args>(__args)...); + --__start_; + ++__size(); + } else { + __temp_value<value_type, _Allocator> __tmp(__alloc(), std::forward<_Args>(__args)...); + iterator __b = begin(); + iterator __bm1 = std::prev(__b); + __alloc_traits::construct(__a, std::addressof(*__bm1), std::move(*__b)); + --__start_; + ++__size(); + if (__pos > 1) + __b = std::move(std::next(__b), __b + __pos, __b); + *__b = std::move(__tmp.get()); + } + } else { // insert by shifting things forward + if (__back_spare() == 0) + __add_back_capacity(); + // __back_capacity >= 1 + __annotate_increase_back(1); + size_type __de = size() - __pos; + if (__de == 0) { + __alloc_traits::construct(__a, std::addressof(*end()), std::forward<_Args>(__args)...); + ++__size(); + } else { + __temp_value<value_type, _Allocator> __tmp(__alloc(), std::forward<_Args>(__args)...); + iterator __e = end(); + iterator __em1 = std::prev(__e); + __alloc_traits::construct(__a, std::addressof(*__e), std::move(*__em1)); + ++__size(); + if (__de > 1) + __e = std::move_backward(__e - __de, __em1, __e); + *--__e = std::move(__tmp.get()); + } + } + return begin() + __pos; +} + +template <class _Tp, class _Allocator> +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v) { + size_type __pos = __p - begin(); + size_type __to_end = __size() - __pos; + allocator_type& __a = __alloc(); + if (__pos < __to_end) { // insert by shifting things backward + if (__n > __front_spare()) + __add_front_capacity(__n - __front_spare()); + // __n <= __front_spare() + __annotate_increase_front(__n); + iterator __old_begin = begin(); + iterator __i = __old_begin; + if (__n > __pos) { + for (size_type __m = __n - __pos; __m; --__m, --__start_, ++__size()) + __alloc_traits::construct(__a, std::addressof(*--__i), __v); + __n = __pos; + } + if (__n > 0) { + const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); + iterator __obn = __old_begin + __n; + __move_construct_backward_and_check(__old_begin, __obn, __i, __vt); + if (__n < __pos) + __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt); + std::fill_n(__old_begin, __n, *__vt); + } + } else { // insert by shifting things forward + size_type __back_capacity = __back_spare(); + if (__n > __back_capacity) + __add_back_capacity(__n - __back_capacity); + // __n <= __back_capacity + __annotate_increase_back(__n); + iterator __old_end = end(); + iterator __i = __old_end; + size_type __de = size() - __pos; + if (__n > __de) { + for (size_type __m = __n - __de; __m; --__m, (void)++__i, ++__size()) + __alloc_traits::construct(__a, std::addressof(*__i), __v); + __n = __de; + } + if (__n > 0) { + const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); + iterator __oen = __old_end - __n; + __move_construct_and_check(__oen, __old_end, __i, __vt); + if (__n < __de) + __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt); + std::fill_n(__old_end - __n, __n, *__vt); + } + } + return begin() + __pos; +} + +template <class _Tp, class _Allocator> +template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> > +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l) { + return __insert_with_sentinel(__p, __f, __l); +} + +template <class _Tp, class _Allocator> +template <class _Iterator, class _Sentinel> +_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) { + __split_buffer<value_type, allocator_type> __buf(__alloc()); + __buf.__construct_at_end_with_sentinel(std::move(__f), std::move(__l)); + typedef typename __split_buffer<value_type, allocator_type>::iterator __bi; + return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end())); +} + +template <class _Tp, class _Allocator> +template <class _ForwardIterator, __enable_if_t<__has_exactly_forward_iterator_category<_ForwardIterator>::value, int> > +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l) { + return __insert_with_size(__p, __f, std::distance(__f, __l)); +} + +template <class _Tp, class _Allocator> +template <class _Iterator> +_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__insert_with_size(const_iterator __p, _Iterator __f, size_type __n) { + __split_buffer<value_type, allocator_type> __buf(__n, 0, __alloc()); + __buf.__construct_at_end_with_size(std::move(__f), __n); + typedef typename __split_buffer<value_type, allocator_type>::iterator __fwd; + return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end())); +} + +template <class _Tp, class _Allocator> +template <class _BiIter, __enable_if_t<__has_bidirectional_iterator_category<_BiIter>::value, int> > +typename deque<_Tp, _Allocator>::iterator deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l) { + return __insert_bidirectional(__p, __f, __l, std::distance(__f, __l)); +} + +template <class _Tp, class _Allocator> +template <class _BiIter, class _Sentinel> +_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__insert_bidirectional(const_iterator __p, _BiIter __f, _Sentinel, size_type __n) { + return __insert_bidirectional(__p, __f, std::next(__f, __n), __n); +} + +template <class _Tp, class _Allocator> +template <class _BiIter> +_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__insert_bidirectional(const_iterator __p, _BiIter __f, _BiIter __l, size_type __n) { + size_type __pos = __p - begin(); + size_type __to_end = size() - __pos; + allocator_type& __a = __alloc(); + if (__pos < __to_end) { // insert by shifting things backward + if (__n > __front_spare()) + __add_front_capacity(__n - __front_spare()); + // __n <= __front_spare() + __annotate_increase_front(__n); + iterator __old_begin = begin(); + iterator __i = __old_begin; + _BiIter __m = __f; + if (__n > __pos) { + __m = __pos < __n / 2 ? std::prev(__l, __pos) : std::next(__f, __n - __pos); + for (_BiIter __j = __m; __j != __f; --__start_, ++__size()) + __alloc_traits::construct(__a, std::addressof(*--__i), *--__j); + __n = __pos; + } + if (__n > 0) { + iterator __obn = __old_begin + __n; + for (iterator __j = __obn; __j != __old_begin;) { + __alloc_traits::construct(__a, std::addressof(*--__i), std::move(*--__j)); + --__start_; + ++__size(); + } + if (__n < __pos) + __old_begin = std::move(__obn, __old_begin + __pos, __old_begin); + std::copy(__m, __l, __old_begin); + } + } else { // insert by shifting things forward + size_type __back_capacity = __back_spare(); + if (__n > __back_capacity) + __add_back_capacity(__n - __back_capacity); + // __n <= __back_capacity + __annotate_increase_back(__n); + iterator __old_end = end(); + iterator __i = __old_end; + _BiIter __m = __l; + size_type __de = size() - __pos; + if (__n > __de) { + __m = __de < __n / 2 ? std::next(__f, __de) : std::prev(__l, __n - __de); + for (_BiIter __j = __m; __j != __l; ++__i, (void)++__j, ++__size()) + __alloc_traits::construct(__a, std::addressof(*__i), *__j); + __n = __de; + } + if (__n > 0) { + iterator __oen = __old_end - __n; + for (iterator __j = __oen; __j != __old_end; ++__i, (void)++__j, ++__size()) + __alloc_traits::construct(__a, std::addressof(*__i), std::move(*__j)); + if (__n < __de) + __old_end = std::move_backward(__old_end - __de, __oen, __old_end); + std::copy_backward(__f, __m, __old_end); + } + } + return begin() + __pos; +} + +template <class _Tp, class _Allocator> +template <class _InpIter, __enable_if_t<__has_exactly_input_iterator_category<_InpIter>::value, int> > +void deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l) { + __append_with_sentinel(__f, __l); +} + +template <class _Tp, class _Allocator> +template <class _InputIterator, class _Sentinel> +_LIBCPP_HIDE_FROM_ABI void deque<_Tp, _Allocator>::__append_with_sentinel(_InputIterator __f, _Sentinel __l) { + for (; __f != __l; ++__f) +# ifdef _LIBCPP_CXX03_LANG + push_back(*__f); +# else + emplace_back(*__f); +# endif +} + +template <class _Tp, class _Allocator> +template <class _ForIter, __enable_if_t<__has_forward_iterator_category<_ForIter>::value, int> > +void deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l) { + __append_with_size(__f, std::distance(__f, __l)); +} + +template <class _Tp, class _Allocator> +template <class _InputIterator> +_LIBCPP_HIDE_FROM_ABI void deque<_Tp, _Allocator>::__append_with_size(_InputIterator __f, size_type __n) { + allocator_type& __a = __alloc(); + size_type __back_capacity = __back_spare(); + if (__n > __back_capacity) + __add_back_capacity(__n - __back_capacity); + + // __n <= __back_capacity + __annotate_increase_back(__n); + for (__deque_block_range __br : __deque_range(end(), end() + __n)) { + _ConstructTransaction __tx(this, __br); + for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) { + __alloc_traits::construct(__a, std::__to_address(__tx.__pos_), *__f); + } + } +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__append(size_type __n) { + allocator_type& __a = __alloc(); + size_type __back_capacity = __back_spare(); + if (__n > __back_capacity) + __add_back_capacity(__n - __back_capacity); + // __n <= __back_capacity + __annotate_increase_back(__n); + for (__deque_block_range __br : __deque_range(end(), end() + __n)) { + _ConstructTransaction __tx(this, __br); + for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { + __alloc_traits::construct(__a, std::__to_address(__tx.__pos_)); + } + } +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v) { + allocator_type& __a = __alloc(); + size_type __back_capacity = __back_spare(); + if (__n > __back_capacity) + __add_back_capacity(__n - __back_capacity); + // __n <= __back_capacity + __annotate_increase_back(__n); + for (__deque_block_range __br : __deque_range(end(), end() + __n)) { + _ConstructTransaction __tx(this, __br); + for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { + __alloc_traits::construct(__a, std::__to_address(__tx.__pos_), __v); + } + } +} + +// Create front capacity for one block of elements. +// Strong guarantee. Either do it or don't touch anything. +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__add_front_capacity() { + allocator_type& __a = __alloc(); + if (__back_spare() >= __block_size) { + __start_ += __block_size; + pointer __pt = __map_.back(); + __map_.pop_back(); + __map_.emplace_front(__pt); + } + // Else if __map_.size() < __map_.capacity() then we need to allocate 1 buffer + else if (__map_.size() < __map_.capacity()) { // we can put the new buffer into the map, but don't shift things around + // until all buffers are allocated. If we throw, we don't need to fix + // anything up (any added buffers are undetectible) + if (__map_.__front_spare() > 0) + __map_.emplace_front(__alloc_traits::allocate(__a, __block_size)); + else { + __map_.emplace_back(__alloc_traits::allocate(__a, __block_size)); + // Done allocating, reorder capacity + pointer __pt = __map_.back(); + __map_.pop_back(); + __map_.emplace_front(__pt); + } + __start_ = __map_.size() == 1 ? __block_size / 2 : __start_ + __block_size; + } + // Else need to allocate 1 buffer, *and* we need to reallocate __map_. + else { + __split_buffer<pointer, __pointer_allocator> __buf( + std::max<size_type>(2 * __map_.capacity(), 1), 0, __map_.__get_allocator()); + + typedef __allocator_destructor<_Allocator> _Dp; + unique_ptr<pointer, _Dp> __hold(__alloc_traits::allocate(__a, __block_size), _Dp(__a, __block_size)); + __buf.emplace_back(__hold.get()); + __hold.release(); + + for (__map_pointer __i = __map_.begin(); __i != __map_.end(); ++__i) + __buf.emplace_back(*__i); + __map_.__swap_without_allocator(__buf); + __start_ = __map_.size() == 1 ? __block_size / 2 : __start_ + __block_size; + } + __annotate_whole_block(0, __asan_poison); +} + +// Create front capacity for __n elements. +// Strong guarantee. Either do it or don't touch anything. +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) { + allocator_type& __a = __alloc(); + size_type __nb = __recommend_blocks(__n + __map_.empty()); + // Number of unused blocks at back: + size_type __back_capacity = __back_spare() / __block_size; + __back_capacity = std::min(__back_capacity, __nb); // don't take more than you need + __nb -= __back_capacity; // number of blocks need to allocate + // If __nb == 0, then we have sufficient capacity. + if (__nb == 0) { + __start_ += __block_size * __back_capacity; + for (; __back_capacity > 0; --__back_capacity) { + pointer __pt = __map_.back(); + __map_.pop_back(); + __map_.emplace_front(__pt); + } + } + // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers + else if (__nb <= __map_.capacity() - + __map_.size()) { // we can put the new buffers into the map, but don't shift things around + // until all buffers are allocated. If we throw, we don't need to fix + // anything up (any added buffers are undetectible) + for (; __nb > 0; --__nb, __start_ += __block_size - (__map_.size() == 1)) { + if (__map_.__front_spare() == 0) + break; + __map_.emplace_front(__alloc_traits::allocate(__a, __block_size)); + __annotate_whole_block(0, __asan_poison); + } + for (; __nb > 0; --__nb, ++__back_capacity) + __map_.emplace_back(__alloc_traits::allocate(__a, __block_size)); + // Done allocating, reorder capacity + __start_ += __back_capacity * __block_size; + for (; __back_capacity > 0; --__back_capacity) { + pointer __pt = __map_.back(); + __map_.pop_back(); + __map_.emplace_front(__pt); + __annotate_whole_block(0, __asan_poison); + } + } + // Else need to allocate __nb buffers, *and* we need to reallocate __map_. + else { + size_type __ds = (__nb + __back_capacity) * __block_size - __map_.empty(); + __split_buffer<pointer, __pointer_allocator> __buf( + std::max<size_type>(2 * __map_.capacity(), __nb + __map_.size()), 0, __map_.__get_allocator()); + auto __guard = std::__make_exception_guard([&] { + __annotate_delete(); + for (__map_pointer __i = __buf.begin(); __i != __buf.end(); ++__i) + __alloc_traits::deallocate(__a, *__i, __block_size); + }); + for (; __nb > 0; --__nb) { + __buf.emplace_back(__alloc_traits::allocate(__a, __block_size)); + // ASan: this is empty container, we have to poison whole block + __annotate_poison_block(std::__to_address(__buf.back()), std::__to_address(__buf.back() + __block_size)); + } + __guard.__complete(); + for (; __back_capacity > 0; --__back_capacity) { + __buf.emplace_back(__map_.back()); + __map_.pop_back(); + } + for (__map_pointer __i = __map_.begin(); __i != __map_.end(); ++__i) + __buf.emplace_back(*__i); + __map_.__swap_without_allocator(__buf); + __start_ += __ds; + } +} + +// Create back capacity for one block of elements. +// Strong guarantee. Either do it or don't touch anything. +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__add_back_capacity() { + allocator_type& __a = __alloc(); + if (__front_spare() >= __block_size) { + __start_ -= __block_size; + pointer __pt = __map_.front(); + __map_.pop_front(); + __map_.emplace_back(__pt); + } + // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers + else if (__map_.size() < __map_.capacity()) { // we can put the new buffer into the map, but don't shift things around + // until it is allocated. If we throw, we don't need to fix + // anything up (any added buffers are undetectible) + if (__map_.__back_spare() != 0) + __map_.emplace_back(__alloc_traits::allocate(__a, __block_size)); + else { + __map_.emplace_front(__alloc_traits::allocate(__a, __block_size)); + // Done allocating, reorder capacity + pointer __pt = __map_.front(); + __map_.pop_front(); + __map_.emplace_back(__pt); + } + __annotate_whole_block(__map_.size() - 1, __asan_poison); + } + // Else need to allocate 1 buffer, *and* we need to reallocate __map_. + else { + __split_buffer<pointer, __pointer_allocator> __buf( + std::max<size_type>(2 * __map_.capacity(), 1), __map_.size(), __map_.__get_allocator()); + + typedef __allocator_destructor<_Allocator> _Dp; + unique_ptr<pointer, _Dp> __hold(__alloc_traits::allocate(__a, __block_size), _Dp(__a, __block_size)); + __buf.emplace_back(__hold.get()); + __hold.release(); + + for (__map_pointer __i = __map_.end(); __i != __map_.begin();) + __buf.emplace_front(*--__i); + __map_.__swap_without_allocator(__buf); + __annotate_whole_block(__map_.size() - 1, __asan_poison); + } +} + +// Create back capacity for __n elements. +// Strong guarantee. Either do it or don't touch anything. +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) { + allocator_type& __a = __alloc(); + size_type __nb = __recommend_blocks(__n + __map_.empty()); + // Number of unused blocks at front: + size_type __front_capacity = __front_spare() / __block_size; + __front_capacity = std::min(__front_capacity, __nb); // don't take more than you need + __nb -= __front_capacity; // number of blocks need to allocate + // If __nb == 0, then we have sufficient capacity. + if (__nb == 0) { + __start_ -= __block_size * __front_capacity; + for (; __front_capacity > 0; --__front_capacity) { + pointer __pt = __map_.front(); + __map_.pop_front(); + __map_.emplace_back(__pt); + } + } + // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers + else if (__nb <= __map_.capacity() - + __map_.size()) { // we can put the new buffers into the map, but don't shift things around + // until all buffers are allocated. If we throw, we don't need to fix + // anything up (any added buffers are undetectible) + for (; __nb > 0; --__nb) { + if (__map_.__back_spare() == 0) + break; + __map_.emplace_back(__alloc_traits::allocate(__a, __block_size)); + __annotate_whole_block(__map_.size() - 1, __asan_poison); + } + for (; __nb > 0; --__nb, ++__front_capacity, __start_ += __block_size - (__map_.size() == 1)) { + __map_.emplace_front(__alloc_traits::allocate(__a, __block_size)); + __annotate_whole_block(0, __asan_poison); + } + // Done allocating, reorder capacity + __start_ -= __block_size * __front_capacity; + for (; __front_capacity > 0; --__front_capacity) { + pointer __pt = __map_.front(); + __map_.pop_front(); + __map_.emplace_back(__pt); + } + } + // Else need to allocate __nb buffers, *and* we need to reallocate __map_. + else { + size_type __ds = __front_capacity * __block_size; + __split_buffer<pointer, __pointer_allocator> __buf( + std::max<size_type>(2 * __map_.capacity(), __nb + __map_.size()), + __map_.size() - __front_capacity, + __map_.__get_allocator()); + auto __guard = std::__make_exception_guard([&] { + __annotate_delete(); + for (__map_pointer __i = __buf.begin(); __i != __buf.end(); ++__i) + __alloc_traits::deallocate(__a, *__i, __block_size); + }); + for (; __nb > 0; --__nb) { + __buf.emplace_back(__alloc_traits::allocate(__a, __block_size)); + // ASan: this is an empty container, we have to poison the whole block + __annotate_poison_block(std::__to_address(__buf.back()), std::__to_address(__buf.back() + __block_size)); + } + __guard.__complete(); + for (; __front_capacity > 0; --__front_capacity) { + __buf.emplace_back(__map_.front()); + __map_.pop_front(); + } + for (__map_pointer __i = __map_.end(); __i != __map_.begin();) + __buf.emplace_front(*--__i); + __map_.__swap_without_allocator(__buf); + __start_ -= __ds; + } +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::pop_front() { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::pop_front called on an empty deque"); + size_type __old_sz = size(); + size_type __old_start = __start_; + allocator_type& __a = __alloc(); + __alloc_traits::destroy( + __a, std::__to_address(*(__map_.begin() + __start_ / __block_size) + __start_ % __block_size)); + --__size(); + ++__start_; + __annotate_shrink_front(__old_sz, __old_start); + __maybe_remove_front_spare(); +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::pop_back() { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::pop_back called on an empty deque"); + size_type __old_sz = size(); + size_type __old_start = __start_; + allocator_type& __a = __alloc(); + size_type __p = size() + __start_ - 1; + __alloc_traits::destroy(__a, std::__to_address(*(__map_.begin() + __p / __block_size) + __p % __block_size)); + --__size(); + __annotate_shrink_back(__old_sz, __old_start); + __maybe_remove_back_spare(); +} + +// move assign [__f, __l) to [__r, __r + (__l-__f)). +// If __vt points into [__f, __l), then subtract (__f - __r) from __vt. +template <class _Tp, class _Allocator> +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) { + // as if + // for (; __f != __l; ++__f, ++__r) + // *__r = std::move(*__f); + difference_type __n = __l - __f; + while (__n > 0) { + pointer __fb = __f.__ptr_; + pointer __fe = *__f.__m_iter_ + __block_size; + difference_type __bs = __fe - __fb; + if (__bs > __n) { + __bs = __n; + __fe = __fb + __bs; + } + if (__fb <= __vt && __vt < __fe) + __vt = (const_iterator(__f.__m_iter_, __vt) -= __f - __r).__ptr_; + __r = std::move(__fb, __fe, __r); + __n -= __bs; + __f += __bs; + } + return __r; +} + +// move assign [__f, __l) to [__r - (__l-__f), __r) backwards. +// If __vt points into [__f, __l), then add (__r - __l) to __vt. +template <class _Tp, class _Allocator> +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) { + // as if + // while (__f != __l) + // *--__r = std::move(*--__l); + difference_type __n = __l - __f; + while (__n > 0) { + --__l; + pointer __lb = *__l.__m_iter_; + pointer __le = __l.__ptr_ + 1; + difference_type __bs = __le - __lb; + if (__bs > __n) { + __bs = __n; + __lb = __le - __bs; + } + if (__lb <= __vt && __vt < __le) + __vt = (const_iterator(__l.__m_iter_, __vt) += __r - __l - 1).__ptr_; + __r = std::move_backward(__lb, __le, __r); + __n -= __bs; + __l -= __bs - 1; + } + return __r; +} + +// move construct [__f, __l) to [__r, __r + (__l-__f)). +// If __vt points into [__f, __l), then add (__r - __f) to __vt. +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) { + allocator_type& __a = __alloc(); + // as if + // for (; __f != __l; ++__r, ++__f, ++__size()) + // __alloc_traits::construct(__a, std::addressof(*__r), std::move(*__f)); + difference_type __n = __l - __f; + while (__n > 0) { + pointer __fb = __f.__ptr_; + pointer __fe = *__f.__m_iter_ + __block_size; + difference_type __bs = __fe - __fb; + if (__bs > __n) { + __bs = __n; + __fe = __fb + __bs; + } + if (__fb <= __vt && __vt < __fe) + __vt = (const_iterator(__f.__m_iter_, __vt) += __r - __f).__ptr_; + for (; __fb != __fe; ++__fb, ++__r, ++__size()) + __alloc_traits::construct(__a, std::addressof(*__r), std::move(*__fb)); + __n -= __bs; + __f += __bs; + } +} + +// move construct [__f, __l) to [__r - (__l-__f), __r) backwards. +// If __vt points into [__f, __l), then subtract (__l - __r) from __vt. +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__move_construct_backward_and_check( + iterator __f, iterator __l, iterator __r, const_pointer& __vt) { + allocator_type& __a = __alloc(); + // as if + // for (iterator __j = __l; __j != __f;) + // { + // __alloc_traitsconstruct(__a, std::addressof(*--__r), std::move(*--__j)); + // --__start_; + // ++__size(); + // } + difference_type __n = __l - __f; + while (__n > 0) { + --__l; + pointer __lb = *__l.__m_iter_; + pointer __le = __l.__ptr_ + 1; + difference_type __bs = __le - __lb; + if (__bs > __n) { + __bs = __n; + __lb = __le - __bs; + } + if (__lb <= __vt && __vt < __le) + __vt = (const_iterator(__l.__m_iter_, __vt) -= __l - __r + 1).__ptr_; + while (__le != __lb) { + __alloc_traits::construct(__a, std::addressof(*--__r), std::move(*--__le)); + --__start_; + ++__size(); + } + __n -= __bs; + __l -= __bs - 1; + } +} + +template <class _Tp, class _Allocator> +typename deque<_Tp, _Allocator>::iterator deque<_Tp, _Allocator>::erase(const_iterator __f) { + _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( + __f != end(), "deque::erase(iterator) called with a non-dereferenceable iterator"); + size_type __old_sz = size(); + size_type __old_start = __start_; + iterator __b = begin(); + difference_type __pos = __f - __b; + iterator __p = __b + __pos; + allocator_type& __a = __alloc(); + if (static_cast<size_type>(__pos) <= (size() - 1) / 2) { // erase from front + std::move_backward(__b, __p, std::next(__p)); + __alloc_traits::destroy(__a, std::addressof(*__b)); + --__size(); + ++__start_; + __annotate_shrink_front(__old_sz, __old_start); + __maybe_remove_front_spare(); + } else { // erase from back + iterator __i = std::move(std::next(__p), end(), __p); + __alloc_traits::destroy(__a, std::addressof(*__i)); + --__size(); + __annotate_shrink_back(__old_sz, __old_start); + __maybe_remove_back_spare(); + } + return begin() + __pos; +} + +template <class _Tp, class _Allocator> +typename deque<_Tp, _Allocator>::iterator deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) { + _LIBCPP_ASSERT_VALID_INPUT_RANGE(__f <= __l, "deque::erase(first, last) called with an invalid range"); + size_type __old_sz = size(); + size_type __old_start = __start_; + difference_type __n = __l - __f; + iterator __b = begin(); + difference_type __pos = __f - __b; + iterator __p = __b + __pos; + if (__n > 0) { + allocator_type& __a = __alloc(); + if (static_cast<size_type>(__pos) <= (size() - __n) / 2) { // erase from front + iterator __i = std::move_backward(__b, __p, __p + __n); + for (; __b != __i; ++__b) + __alloc_traits::destroy(__a, std::addressof(*__b)); + __size() -= __n; + __start_ += __n; + __annotate_shrink_front(__old_sz, __old_start); + while (__maybe_remove_front_spare()) { + } + } else { // erase from back + iterator __i = std::move(__p + __n, end(), __p); + for (iterator __e = end(); __i != __e; ++__i) + __alloc_traits::destroy(__a, std::addressof(*__i)); + __size() -= __n; + __annotate_shrink_back(__old_sz, __old_start); + while (__maybe_remove_back_spare()) { + } + } + } + return begin() + __pos; +} + +template <class _Tp, class _Allocator> +void deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f) { + size_type __old_sz = size(); + size_type __old_start = __start_; + iterator __e = end(); + difference_type __n = __e - __f; + if (__n > 0) { + allocator_type& __a = __alloc(); + iterator __b = begin(); + difference_type __pos = __f - __b; + for (iterator __p = __b + __pos; __p != __e; ++__p) + __alloc_traits::destroy(__a, std::addressof(*__p)); + __size() -= __n; + __annotate_shrink_back(__old_sz, __old_start); + while (__maybe_remove_back_spare()) { + } + } +} + +template <class _Tp, class _Allocator> +inline void deque<_Tp, _Allocator>::swap(deque& __c) +# if _LIBCPP_STD_VER >= 14 + _NOEXCEPT +# else + _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>) +# endif +{ + __map_.swap(__c.__map_); + std::swap(__start_, __c.__start_); + std::swap(__size(), __c.__size()); + std::__swap_allocator(__alloc(), __c.__alloc()); +} + +template <class _Tp, class _Allocator> +inline void deque<_Tp, _Allocator>::clear() _NOEXCEPT { + __annotate_delete(); + allocator_type& __a = __alloc(); + for (iterator __i = begin(), __e = end(); __i != __e; ++__i) + __alloc_traits::destroy(__a, std::addressof(*__i)); + __size() = 0; + while (__map_.size() > 2) { + __alloc_traits::deallocate(__a, __map_.front(), __block_size); + __map_.pop_front(); + } + switch (__map_.size()) { + case 1: + __start_ = __block_size / 2; + break; + case 2: + __start_ = __block_size; + break; + } + __annotate_new(0); +} + +template <class _Tp, class _Allocator> +inline _LIBCPP_HIDE_FROM_ABI bool operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) { + const typename deque<_Tp, _Allocator>::size_type __sz = __x.size(); + return __sz == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); +} + +# if _LIBCPP_STD_VER <= 17 + +template <class _Tp, class _Allocator> +inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) { + return !(__x == __y); +} + +template <class _Tp, class _Allocator> +inline _LIBCPP_HIDE_FROM_ABI bool operator<(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) { + return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); +} + +template <class _Tp, class _Allocator> +inline _LIBCPP_HIDE_FROM_ABI bool operator>(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) { + return __y < __x; +} + +template <class _Tp, class _Allocator> +inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) { + return !(__x < __y); +} + +template <class _Tp, class _Allocator> +inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) { + return !(__y < __x); +} + +# else // _LIBCPP_STD_VER <= 17 + +template <class _Tp, class _Allocator> +_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp> +operator<=>(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) { + return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way); +} + +# endif // _LIBCPP_STD_VER <= 17 + +template <class _Tp, class _Allocator> +inline _LIBCPP_HIDE_FROM_ABI void swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) + _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { + __x.swap(__y); +} + +# if _LIBCPP_STD_VER >= 20 +template <class _Tp, class _Allocator, class _Up> +inline _LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::size_type +erase(deque<_Tp, _Allocator>& __c, const _Up& __v) { + auto __old_size = __c.size(); + __c.erase(std::remove(__c.begin(), __c.end(), __v), __c.end()); + return __old_size - __c.size(); +} + +template <class _Tp, class _Allocator, class _Predicate> +inline _LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::size_type +erase_if(deque<_Tp, _Allocator>& __c, _Predicate __pred) { + auto __old_size = __c.size(); + __c.erase(std::remove_if(__c.begin(), __c.end(), __pred), __c.end()); + return __old_size - __c.size(); +} + +template <> +inline constexpr bool __format::__enable_insertable<std::deque<char>> = true; +# if _LIBCPP_HAS_WIDE_CHARACTERS +template <> +inline constexpr bool __format::__enable_insertable<std::deque<wchar_t>> = true; +# endif + +# endif // _LIBCPP_STD_VER >= 20 + +template <class _Tp, class _Allocator> +struct __container_traits<deque<_Tp, _Allocator> > { + // http://eel.is/c++draft/deque.modifiers#3 + // If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move + // assignment operator of T, there are no effects. If an exception is thrown while inserting a single element at + // either end, there are no effects. Otherwise, if an exception is thrown by the move constructor of a + // non-Cpp17CopyInsertable T, the effects are unspecified. + static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = + is_nothrow_move_constructible<_Tp>::value || __is_cpp17_copy_insertable_v<_Allocator>; + + static _LIBCPP_CONSTEXPR const bool __reservable = false; +}; + +_LIBCPP_END_NAMESPACE_STD + +# if _LIBCPP_STD_VER >= 17 +_LIBCPP_BEGIN_NAMESPACE_STD +namespace pmr { +template <class _ValueT> +using deque _LIBCPP_AVAILABILITY_PMR = std::deque<_ValueT, polymorphic_allocator<_ValueT>>; +} // namespace pmr +_LIBCPP_END_NAMESPACE_STD +# endif + +_LIBCPP_POP_MACROS + +# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 +# include <algorithm> +# include <atomic> +# include <concepts> +# include <cstdlib> +# include <functional> +# include <iosfwd> +# include <iterator> +# include <type_traits> +# include <typeinfo> +# endif +#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) + +#endif // _LIBCPP_DEQUE |