2135 lines · plain
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03_DEQUE11#define _LIBCPP___CXX03_DEQUE12 13/*14 deque synopsis15 16namespace std17{18 19template <class T, class Allocator = allocator<T> >20class deque21{22public:23 // types:24 typedef T value_type;25 typedef Allocator allocator_type;26 27 typedef typename allocator_type::reference reference;28 typedef typename allocator_type::const_reference const_reference;29 typedef implementation-defined iterator;30 typedef implementation-defined const_iterator;31 typedef typename allocator_type::size_type size_type;32 typedef typename allocator_type::difference_type difference_type;33 34 typedef typename allocator_type::pointer pointer;35 typedef typename allocator_type::const_pointer const_pointer;36 typedef std::reverse_iterator<iterator> reverse_iterator;37 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;38 39 // construct/copy/destroy:40 deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);41 explicit deque(const allocator_type& a);42 explicit deque(size_type n);43 explicit deque(size_type n, const allocator_type& a); // C++1444 deque(size_type n, const value_type& v);45 deque(size_type n, const value_type& v, const allocator_type& a);46 template <class InputIterator>47 deque(InputIterator f, InputIterator l);48 template <class InputIterator>49 deque(InputIterator f, InputIterator l, const allocator_type& a);50 template<container-compatible-range<T> R>51 deque(from_range_t, R&& rg, const Allocator& = Allocator()); // C++2352 deque(const deque& c);53 deque(deque&& c)54 noexcept(is_nothrow_move_constructible<allocator_type>::value);55 deque(initializer_list<value_type> il, const Allocator& a = allocator_type());56 deque(const deque& c, const allocator_type& a);57 deque(deque&& c, const allocator_type& a);58 ~deque();59 60 deque& operator=(const deque& c);61 deque& operator=(deque&& c)62 noexcept(63 allocator_type::propagate_on_container_move_assignment::value &&64 is_nothrow_move_assignable<allocator_type>::value);65 deque& operator=(initializer_list<value_type> il);66 67 template <class InputIterator>68 void assign(InputIterator f, InputIterator l);69 template<container-compatible-range<T> R>70 void assign_range(R&& rg); // C++2371 void assign(size_type n, const value_type& v);72 void assign(initializer_list<value_type> il);73 74 allocator_type get_allocator() const noexcept;75 76 // iterators:77 78 iterator begin() noexcept;79 const_iterator begin() const noexcept;80 iterator end() noexcept;81 const_iterator end() const noexcept;82 83 reverse_iterator rbegin() noexcept;84 const_reverse_iterator rbegin() const noexcept;85 reverse_iterator rend() noexcept;86 const_reverse_iterator rend() const noexcept;87 88 const_iterator cbegin() const noexcept;89 const_iterator cend() const noexcept;90 const_reverse_iterator crbegin() const noexcept;91 const_reverse_iterator crend() const noexcept;92 93 // capacity:94 size_type size() const noexcept;95 size_type max_size() const noexcept;96 void resize(size_type n);97 void resize(size_type n, const value_type& v);98 void shrink_to_fit();99 bool empty() const noexcept;100 101 // element access:102 reference operator[](size_type i);103 const_reference operator[](size_type i) const;104 reference at(size_type i);105 const_reference at(size_type i) const;106 reference front();107 const_reference front() const;108 reference back();109 const_reference back() const;110 111 // modifiers:112 void push_front(const value_type& v);113 void push_front(value_type&& v);114 template<container-compatible-range<T> R>115 void prepend_range(R&& rg); // C++23116 void push_back(const value_type& v);117 void push_back(value_type&& v);118 template<container-compatible-range<T> R>119 void append_range(R&& rg); // C++23120 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17121 template <class... Args> reference emplace_back(Args&&... args); // reference in C++17122 template <class... Args> iterator emplace(const_iterator p, Args&&... args);123 iterator insert(const_iterator p, const value_type& v);124 iterator insert(const_iterator p, value_type&& v);125 iterator insert(const_iterator p, size_type n, const value_type& v);126 template <class InputIterator>127 iterator insert(const_iterator p, InputIterator f, InputIterator l);128 template<container-compatible-range<T> R>129 iterator insert_range(const_iterator position, R&& rg); // C++23130 iterator insert(const_iterator p, initializer_list<value_type> il);131 void pop_front();132 void pop_back();133 iterator erase(const_iterator p);134 iterator erase(const_iterator f, const_iterator l);135 void swap(deque& c)136 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17137 void clear() noexcept;138};139 140template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>141 deque(InputIterator, InputIterator, Allocator = Allocator())142 -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17143 144template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>145 deque(from_range_t, R&&, Allocator = Allocator())146 -> deque<ranges::range_value_t<R>, Allocator>; // C++23147 148template <class T, class Allocator>149 bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);150template <class T, class Allocator>151 bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20152template <class T, class Allocator>153 bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20154template <class T, class Allocator>155 bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20156template <class T, class Allocator>157 bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20158template <class T, class Allocator>159 bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20160template<class T, class Allocator>161 synth-three-way-result<T> operator<=>(const deque<T, Allocator>& x,162 const deque<T, Allocator>& y); // since C++20163 164// specialized algorithms:165template <class T, class Allocator>166 void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)167 noexcept(noexcept(x.swap(y)));168 169template <class T, class Allocator, class U>170 typename deque<T, Allocator>::size_type171 erase(deque<T, Allocator>& c, const U& value); // C++20172template <class T, class Allocator, class Predicate>173 typename deque<T, Allocator>::size_type174 erase_if(deque<T, Allocator>& c, Predicate pred); // C++20175 176} // std177 178*/179 180#include <__cxx03/__algorithm/copy.h>181#include <__cxx03/__algorithm/copy_backward.h>182#include <__cxx03/__algorithm/copy_n.h>183#include <__cxx03/__algorithm/equal.h>184#include <__cxx03/__algorithm/fill_n.h>185#include <__cxx03/__algorithm/lexicographical_compare.h>186#include <__cxx03/__algorithm/min.h>187#include <__cxx03/__algorithm/remove.h>188#include <__cxx03/__algorithm/remove_if.h>189#include <__cxx03/__algorithm/unwrap_iter.h>190#include <__cxx03/__assert>191#include <__cxx03/__config>192#include <__cxx03/__debug_utils/sanitizers.h>193#include <__cxx03/__fwd/deque.h>194#include <__cxx03/__iterator/distance.h>195#include <__cxx03/__iterator/iterator_traits.h>196#include <__cxx03/__iterator/next.h>197#include <__cxx03/__iterator/prev.h>198#include <__cxx03/__iterator/reverse_iterator.h>199#include <__cxx03/__iterator/segmented_iterator.h>200#include <__cxx03/__memory/addressof.h>201#include <__cxx03/__memory/allocator_destructor.h>202#include <__cxx03/__memory/pointer_traits.h>203#include <__cxx03/__memory/temp_value.h>204#include <__cxx03/__memory/unique_ptr.h>205#include <__cxx03/__split_buffer>206#include <__cxx03/__type_traits/is_allocator.h>207#include <__cxx03/__type_traits/is_convertible.h>208#include <__cxx03/__type_traits/is_same.h>209#include <__cxx03/__type_traits/is_swappable.h>210#include <__cxx03/__type_traits/type_identity.h>211#include <__cxx03/__utility/forward.h>212#include <__cxx03/__utility/move.h>213#include <__cxx03/__utility/pair.h>214#include <__cxx03/__utility/swap.h>215#include <__cxx03/limits>216#include <__cxx03/stdexcept>217#include <__cxx03/version>218 219// standard-mandated includes220 221// [iterator.range]222#include <__cxx03/__iterator/access.h>223 224#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)225# pragma GCC system_header226#endif227 228_LIBCPP_PUSH_MACROS229#include <__cxx03/__undef_macros>230 231_LIBCPP_BEGIN_NAMESPACE_STD232 233template <class _ValueType, class _DiffType>234struct __deque_block_size {235 static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;236};237 238template <class _ValueType,239 class _Pointer,240 class _Reference,241 class _MapPointer,242 class _DiffType,243 _DiffType _BS =244#ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE245 // Keep template parameter to avoid changing all template declarations thoughout246 // this file.247 0248#else249 __deque_block_size<_ValueType, _DiffType>::value250#endif251 >252class _LIBCPP_TEMPLATE_VIS __deque_iterator {253 typedef _MapPointer __map_iterator;254 255public:256 typedef _Pointer pointer;257 typedef _DiffType difference_type;258 259private:260 __map_iterator __m_iter_;261 pointer __ptr_;262 263 static const difference_type __block_size;264 265public:266 typedef _ValueType value_type;267 typedef random_access_iterator_tag iterator_category;268 typedef _Reference reference;269 270 _LIBCPP_HIDE_FROM_ABI __deque_iterator() _NOEXCEPT {}271 272 template <class _Pp, class _Rp, class _MP, __enable_if_t<is_convertible<_Pp, pointer>::value, int> = 0>273 _LIBCPP_HIDE_FROM_ABI274 __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it) _NOEXCEPT275 : __m_iter_(__it.__m_iter_),276 __ptr_(__it.__ptr_) {}277 278 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *__ptr_; }279 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return __ptr_; }280 281 _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator++() {282 if (++__ptr_ - *__m_iter_ == __block_size) {283 ++__m_iter_;284 __ptr_ = *__m_iter_;285 }286 return *this;287 }288 289 _LIBCPP_HIDE_FROM_ABI __deque_iterator operator++(int) {290 __deque_iterator __tmp = *this;291 ++(*this);292 return __tmp;293 }294 295 _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator--() {296 if (__ptr_ == *__m_iter_) {297 --__m_iter_;298 __ptr_ = *__m_iter_ + __block_size;299 }300 --__ptr_;301 return *this;302 }303 304 _LIBCPP_HIDE_FROM_ABI __deque_iterator operator--(int) {305 __deque_iterator __tmp = *this;306 --(*this);307 return __tmp;308 }309 310 _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator+=(difference_type __n) {311 if (__n != 0) {312 __n += __ptr_ - *__m_iter_;313 if (__n > 0) {314 __m_iter_ += __n / __block_size;315 __ptr_ = *__m_iter_ + __n % __block_size;316 } else // (__n < 0)317 {318 difference_type __z = __block_size - 1 - __n;319 __m_iter_ -= __z / __block_size;320 __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);321 }322 }323 return *this;324 }325 326 _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator-=(difference_type __n) { return *this += -__n; }327 328 _LIBCPP_HIDE_FROM_ABI __deque_iterator operator+(difference_type __n) const {329 __deque_iterator __t(*this);330 __t += __n;331 return __t;332 }333 334 _LIBCPP_HIDE_FROM_ABI __deque_iterator operator-(difference_type __n) const {335 __deque_iterator __t(*this);336 __t -= __n;337 return __t;338 }339 340 _LIBCPP_HIDE_FROM_ABI friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it) {341 return __it + __n;342 }343 344 _LIBCPP_HIDE_FROM_ABI friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y) {345 if (__x != __y)346 return (__x.__m_iter_ - __y.__m_iter_) * __block_size + (__x.__ptr_ - *__x.__m_iter_) -347 (__y.__ptr_ - *__y.__m_iter_);348 return 0;349 }350 351 _LIBCPP_HIDE_FROM_ABI reference operator[](difference_type __n) const { return *(*this + __n); }352 353 _LIBCPP_HIDE_FROM_ABI friend bool operator==(const __deque_iterator& __x, const __deque_iterator& __y) {354 return __x.__ptr_ == __y.__ptr_;355 }356 357 _LIBCPP_HIDE_FROM_ABI friend bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y) {358 return !(__x == __y);359 }360 361 // TODO(mordante) disable these overloads in the LLVM 20 release.362 _LIBCPP_HIDE_FROM_ABI friend bool operator<(const __deque_iterator& __x, const __deque_iterator& __y) {363 return __x.__m_iter_ < __y.__m_iter_ || (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);364 }365 366 _LIBCPP_HIDE_FROM_ABI friend bool operator>(const __deque_iterator& __x, const __deque_iterator& __y) {367 return __y < __x;368 }369 370 _LIBCPP_HIDE_FROM_ABI friend bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y) {371 return !(__y < __x);372 }373 374 _LIBCPP_HIDE_FROM_ABI friend bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y) {375 return !(__x < __y);376 }377 378private:379 _LIBCPP_HIDE_FROM_ABI explicit __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT380 : __m_iter_(__m),381 __ptr_(__p) {}382 383 template <class _Tp, class _Ap>384 friend class _LIBCPP_TEMPLATE_VIS deque;385 template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>386 friend class _LIBCPP_TEMPLATE_VIS __deque_iterator;387 388 template <class>389 friend struct __segmented_iterator_traits;390};391 392template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, class _DiffType, _DiffType _BlockSize>393struct __segmented_iterator_traits<394 __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize> > {395private:396 using _Iterator = __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize>;397 398public:399 using __is_segmented_iterator = true_type;400 using __segment_iterator = _MapPointer;401 using __local_iterator = _Pointer;402 403 static _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_Iterator __iter) { return __iter.__m_iter_; }404 static _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_Iterator __iter) { return __iter.__ptr_; }405 static _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) { return *__iter; }406 407 static _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {408 return *__iter + _Iterator::__block_size;409 }410 411 static _LIBCPP_HIDE_FROM_ABI _Iterator __compose(__segment_iterator __segment, __local_iterator __local) {412 if (__segment && __local == __end(__segment)) {413 ++__segment;414 return _Iterator(__segment, *__segment);415 }416 return _Iterator(__segment, __local);417 }418};419 420template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, class _DiffType, _DiffType _BlockSize>421const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize>::__block_size =422 __deque_block_size<_ValueType, _DiffType>::value;423 424template <class _Tp, class _Allocator /*= allocator<_Tp>*/>425class _LIBCPP_TEMPLATE_VIS deque {426public:427 // types:428 429 using value_type = _Tp;430 431 using allocator_type = _Allocator;432 using __alloc_traits = allocator_traits<allocator_type>;433 static_assert(__check_valid_allocator<allocator_type>::value, "");434 static_assert(is_same<typename allocator_type::value_type, value_type>::value,435 "Allocator::value_type must be same type as value_type");436 437 using size_type = typename __alloc_traits::size_type;438 using difference_type = typename __alloc_traits::difference_type;439 440 using pointer = typename __alloc_traits::pointer;441 using const_pointer = typename __alloc_traits::const_pointer;442 443 using __pointer_allocator = __rebind_alloc<__alloc_traits, pointer>;444 using __const_pointer_allocator = __rebind_alloc<__alloc_traits, const_pointer>;445 using __map = __split_buffer<pointer, __pointer_allocator>;446 using __map_alloc_traits = allocator_traits<__pointer_allocator>;447 using __map_pointer = typename __map_alloc_traits::pointer;448 using __map_const_pointer = typename allocator_traits<__const_pointer_allocator>::const_pointer;449 using __map_const_iterator = typename __map::const_iterator;450 451 using reference = value_type&;452 using const_reference = const value_type&;453 454 using iterator = __deque_iterator<value_type, pointer, reference, __map_pointer, difference_type>;455 using const_iterator =456 __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer, difference_type>;457 using reverse_iterator = std::reverse_iterator<iterator>;458 using const_reverse_iterator = std::reverse_iterator<const_iterator>;459 460 // A deque contains the following members which may be trivially relocatable:461 // - __map: is a `__split_buffer`, see `__split_buffer` for more information on when it is trivially relocatable462 // - size_type: is always trivially relocatable, since it is required to be an integral type463 // - allocator_type: may not be trivially relocatable, so it's checked464 // None of these are referencing the `deque` itself, so if all of them are trivially relocatable, `deque` is too.465 using __trivially_relocatable = __conditional_t<466 __libcpp_is_trivially_relocatable<__map>::value && __libcpp_is_trivially_relocatable<allocator_type>::value,467 deque,468 void>;469 470 static_assert(is_nothrow_default_constructible<allocator_type>::value ==471 is_nothrow_default_constructible<__pointer_allocator>::value,472 "rebinding an allocator should not change exception guarantees");473 static_assert(is_nothrow_move_constructible<allocator_type>::value ==474 is_nothrow_move_constructible<typename __map::allocator_type>::value,475 "rebinding an allocator should not change exception guarantees");476 477private:478 struct __deque_block_range {479 explicit _LIBCPP_HIDE_FROM_ABI __deque_block_range(pointer __b, pointer __e) _NOEXCEPT480 : __begin_(__b),481 __end_(__e) {}482 const pointer __begin_;483 const pointer __end_;484 };485 486 struct __deque_range {487 iterator __pos_;488 const iterator __end_;489 490 _LIBCPP_HIDE_FROM_ABI __deque_range(iterator __pos, iterator __e) _NOEXCEPT : __pos_(__pos), __end_(__e) {}491 492 explicit _LIBCPP_HIDE_FROM_ABI operator bool() const _NOEXCEPT { return __pos_ != __end_; }493 494 _LIBCPP_HIDE_FROM_ABI __deque_range begin() const { return *this; }495 496 _LIBCPP_HIDE_FROM_ABI __deque_range end() const { return __deque_range(__end_, __end_); }497 _LIBCPP_HIDE_FROM_ABI __deque_block_range operator*() const _NOEXCEPT {498 if (__pos_.__m_iter_ == __end_.__m_iter_) {499 return __deque_block_range(__pos_.__ptr_, __end_.__ptr_);500 }501 return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size);502 }503 504 _LIBCPP_HIDE_FROM_ABI __deque_range& operator++() _NOEXCEPT {505 if (__pos_.__m_iter_ == __end_.__m_iter_) {506 __pos_ = __end_;507 } else {508 ++__pos_.__m_iter_;509 __pos_.__ptr_ = *__pos_.__m_iter_;510 }511 return *this;512 }513 514 _LIBCPP_HIDE_FROM_ABI friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) {515 return __lhs.__pos_ == __rhs.__pos_;516 }517 _LIBCPP_HIDE_FROM_ABI friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) {518 return !(__lhs == __rhs);519 }520 };521 522 struct _ConstructTransaction {523 _LIBCPP_HIDE_FROM_ABI _ConstructTransaction(deque* __db, __deque_block_range& __r)524 : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {}525 526 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { __base_->__size() += (__pos_ - __begin_); }527 528 pointer __pos_;529 const pointer __end_;530 531 private:532 const pointer __begin_;533 deque* const __base_;534 };535 536 static const difference_type __block_size;537 538 __map __map_;539 size_type __start_;540 __compressed_pair<size_type, allocator_type> __size_;541 542public:543 // construct/copy/destroy:544 _LIBCPP_HIDE_FROM_ABI deque() : __start_(0), __size_(0, __default_init_tag()) { __annotate_new(0); }545 546 _LIBCPP_HIDE_FROM_ABI ~deque() {547 clear();548 __annotate_delete();549 typename __map::iterator __i = __map_.begin();550 typename __map::iterator __e = __map_.end();551 for (; __i != __e; ++__i)552 __alloc_traits::deallocate(__alloc(), *__i, __block_size);553 }554 555 _LIBCPP_HIDE_FROM_ABI explicit deque(const allocator_type& __a)556 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {557 __annotate_new(0);558 }559 560 explicit _LIBCPP_HIDE_FROM_ABI deque(size_type __n);561 _LIBCPP_HIDE_FROM_ABI deque(size_type __n, const value_type& __v);562 563 template <__enable_if_t<__is_allocator<_Allocator>::value, int> = 0>564 _LIBCPP_HIDE_FROM_ABI deque(size_type __n, const value_type& __v, const allocator_type& __a)565 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {566 __annotate_new(0);567 if (__n > 0)568 __append(__n, __v);569 }570 571 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>572 _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l);573 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>574 _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l, const allocator_type& __a);575 576 _LIBCPP_HIDE_FROM_ABI deque(const deque& __c);577 _LIBCPP_HIDE_FROM_ABI deque(const deque& __c, const __type_identity_t<allocator_type>& __a);578 579 _LIBCPP_HIDE_FROM_ABI deque& operator=(const deque& __c);580 581 template <class _InputIter,582 __enable_if_t<__has_input_iterator_category<_InputIter>::value &&583 !__has_random_access_iterator_category<_InputIter>::value,584 int> = 0>585 _LIBCPP_HIDE_FROM_ABI void assign(_InputIter __f, _InputIter __l);586 template <class _RAIter, __enable_if_t<__has_random_access_iterator_category<_RAIter>::value, int> = 0>587 _LIBCPP_HIDE_FROM_ABI void assign(_RAIter __f, _RAIter __l);588 589 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);590 591 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT;592 _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __size_.second(); }593 _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __size_.second(); }594 595 // iterators:596 597 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT {598 __map_pointer __mp = __map_.begin() + __start_ / __block_size;599 return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);600 }601 602 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {603 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);604 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);605 }606 607 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT {608 size_type __p = size() + __start_;609 __map_pointer __mp = __map_.begin() + __p / __block_size;610 return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);611 }612 613 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT {614 size_type __p = size() + __start_;615 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);616 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);617 }618 619 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }620 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }621 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }622 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }623 624 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }625 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }626 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }627 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return const_reverse_iterator(begin()); }628 629 // capacity:630 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size(); }631 632 _LIBCPP_HIDE_FROM_ABI size_type& __size() _NOEXCEPT { return __size_.first(); }633 _LIBCPP_HIDE_FROM_ABI const size_type& __size() const _NOEXCEPT { return __size_.first(); }634 635 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {636 return std::min<size_type>(__alloc_traits::max_size(__alloc()), numeric_limits<difference_type>::max());637 }638 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);639 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v);640 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;641 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return size() == 0; }642 643 // element access:644 _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __i) _NOEXCEPT;645 _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_type __i) const _NOEXCEPT;646 _LIBCPP_HIDE_FROM_ABI reference at(size_type __i);647 _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __i) const;648 _LIBCPP_HIDE_FROM_ABI reference front() _NOEXCEPT;649 _LIBCPP_HIDE_FROM_ABI const_reference front() const _NOEXCEPT;650 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT;651 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT;652 653 // 23.2.2.3 modifiers:654 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);655 _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __v);656 657 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v);658 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __v);659 template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> = 0>660 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InputIter __f, _InputIter __l);661 template <class _ForwardIterator,662 __enable_if_t<__has_exactly_forward_iterator_category<_ForwardIterator>::value, int> = 0>663 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l);664 template <class _BiIter, __enable_if_t<__has_bidirectional_iterator_category<_BiIter>::value, int> = 0>665 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _BiIter __f, _BiIter __l);666 667 _LIBCPP_HIDE_FROM_ABI void pop_front();668 _LIBCPP_HIDE_FROM_ABI void pop_back();669 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);670 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);671 672 _LIBCPP_HIDE_FROM_ABI void swap(deque& __c);673 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;674 675 _LIBCPP_HIDE_FROM_ABI bool __invariants() const {676 if (!__map_.__invariants())677 return false;678 if (__map_.size() >= size_type(-1) / __block_size)679 return false;680 for (__map_const_iterator __i = __map_.begin(), __e = __map_.end(); __i != __e; ++__i)681 if (*__i == nullptr)682 return false;683 if (__map_.size() != 0) {684 if (size() >= __map_.size() * __block_size)685 return false;686 if (__start_ >= __map_.size() * __block_size - size())687 return false;688 } else {689 if (size() != 0)690 return false;691 if (__start_ != 0)692 return false;693 }694 return true;695 }696 697 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(deque& __c) {698 __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());699 }700 701 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(deque& __c, true_type) { __alloc() = std::move(__c.__alloc()); }702 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(deque&, false_type) _NOEXCEPT {}703 704 _LIBCPP_HIDE_FROM_ABI void __move_assign(deque& __c) {705 __map_ = std::move(__c.__map_);706 __start_ = __c.__start_;707 __size() = __c.size();708 __move_assign_alloc(__c);709 __c.__start_ = __c.__size() = 0;710 }711 712 _LIBCPP_HIDE_FROM_ABI static size_type __recommend_blocks(size_type __n) {713 return __n / __block_size + (__n % __block_size != 0);714 }715 _LIBCPP_HIDE_FROM_ABI size_type __capacity() const {716 return __map_.size() == 0 ? 0 : __map_.size() * __block_size - 1;717 }718 _LIBCPP_HIDE_FROM_ABI size_type __block_count() const { return __map_.size(); }719 720 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const { return __start_; }721 _LIBCPP_HIDE_FROM_ABI size_type __front_spare_blocks() const { return __front_spare() / __block_size; }722 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const { return __capacity() - (__start_ + size()); }723 _LIBCPP_HIDE_FROM_ABI size_type __back_spare_blocks() const { return __back_spare() / __block_size; }724 725private:726 enum __asan_annotation_type { __asan_unposion, __asan_poison };727 728 enum __asan_annotation_place {729 __asan_front_moved,730 __asan_back_moved,731 };732 733 _LIBCPP_HIDE_FROM_ABI void __annotate_from_to(734 size_type __beg,735 size_type __end,736 __asan_annotation_type __annotation_type,737 __asan_annotation_place __place) const _NOEXCEPT {738 (void)__beg;739 (void)__end;740 (void)__annotation_type;741 (void)__place;742#ifndef _LIBCPP_HAS_NO_ASAN743 // __beg - index of the first item to annotate744 // __end - index behind the last item to annotate (so last item + 1)745 // __annotation_type - __asan_unposion or __asan_poison746 // __place - __asan_front_moved or __asan_back_moved747 // Note: All indexes in __map_748 if (__beg == __end)749 return;750 // __annotations_beg_map - first chunk which annotations we want to modify751 // __annotations_end_map - last chunk which annotations we want to modify752 // NOTE: if __end % __block_size == 0, __annotations_end_map points at the next block, which may not exist753 __map_const_iterator __annotations_beg_map = __map_.begin() + __beg / __block_size;754 __map_const_iterator __annotations_end_map = __map_.begin() + __end / __block_size;755 756 bool const __poisoning = __annotation_type == __asan_poison;757 // __old_c_beg_index - index of the first element in old container758 // __old_c_end_index - index of the end of old container (last + 1)759 // Note: may be outside the area we are annotating760 size_t __old_c_beg_index = (__poisoning && __place == __asan_front_moved) ? __beg : __start_;761 size_t __old_c_end_index = (__poisoning && __place == __asan_back_moved) ? __end : __start_ + size();762 bool const __front = __place == __asan_front_moved;763 764 if (__poisoning && empty()) {765 // Special case: we shouldn't trust __start_766 __old_c_beg_index = __beg;767 __old_c_end_index = __end;768 }769 // __old_c_beg_map - memory block (chunk) with first element770 // __old_c_end_map - memory block (chunk) with end of old container771 // Note: if __old_c_end_index % __block_size == 0, __old_c_end_map points at the next block,772 // which may not exist773 __map_const_iterator __old_c_beg_map = __map_.begin() + __old_c_beg_index / __block_size;774 __map_const_iterator __old_c_end_map = __map_.begin() + __old_c_end_index / __block_size;775 776 // One edge (front/end) of the container was moved and one was not modified.777 // __new_edge_index - index of new edge778 // __new_edge_map - memory block (chunk) with new edge, it always equals to779 // __annotations_beg_map or __annotations_end_map780 // __old_edge_map - memory block (chunk) with old edge, it always equals to781 // __old_c_beg_map or __old_c_end_map782 size_t __new_edge_index = (__poisoning ^ __front) ? __beg : __end;783 __map_const_iterator __new_edge_map = __map_.begin() + __new_edge_index / __block_size;784 __map_const_iterator __old_edge_map = __front ? __old_c_end_map : __old_c_beg_map;785 786 // We iterate over map pointers (chunks) and fully poison all memory blocks between the first and the last.787 // First and last chunk may be partially poisoned.788 // __annotate_end_map may point at not existing chunk, therefore we have to have a check for it.789 for (__map_const_iterator __map_it = __annotations_beg_map; __map_it <= __annotations_end_map; ++__map_it) {790 if (__map_it == __annotations_end_map && __end % __block_size == 0)791 // Chunk may not exist, but nothing to do here anyway792 break;793 794 // The beginning and the end of the current memory block795 const void* __mem_beg = std::__to_address(*__map_it);796 const void* __mem_end = std::__to_address(*__map_it + __block_size);797 798 // The beginning of memory-in-use in the memory block before container modification799 const void* __old_beg =800 (__map_it == __old_c_beg_map) ? std::__to_address(*__map_it + (__old_c_beg_index % __block_size)) : __mem_beg;801 802 // The end of memory-in-use in the memory block before container modification803 const void* __old_end;804 if (__map_it < __old_c_beg_map || __map_it > __old_c_end_map || (!__poisoning && empty()))805 __old_end = __old_beg;806 else807 __old_end = (__map_it == __old_c_end_map)808 ? std::__to_address(*__map_it + (__old_c_end_index % __block_size))809 : __mem_end;810 811 // New edge of the container in current memory block812 // If the edge is in a different chunk it points on corresponding end of the memory block813 const void* __new_edge;814 if (__map_it == __new_edge_map)815 __new_edge = std::__to_address(*__map_it + (__new_edge_index % __block_size));816 else817 __new_edge = (__poisoning ^ __front) ? __mem_beg : __mem_end;818 819 // Not modified edge of the container820 // If the edge is in a different chunk it points on corresponding end of the memory block821 const void* __old_edge;822 if (__map_it == __old_edge_map)823 __old_edge = __front ? __old_end : __old_beg;824 else825 __old_edge = __front ? __mem_end : __mem_beg;826 827 // __new_beg - the beginning of memory-in-use in the memory block after container modification828 // __new_end - the end of memory-in-use in the memory block after container modification829 const void* __new_beg = __front ? __new_edge : __old_edge;830 const void* __new_end = __front ? __old_edge : __new_edge;831 832 std::__annotate_double_ended_contiguous_container<_Allocator>(833 __mem_beg, __mem_end, __old_beg, __old_end, __new_beg, __new_end);834 }835#endif // !_LIBCPP_HAS_NO_ASAN836 }837 838 _LIBCPP_HIDE_FROM_ABI void __annotate_new(size_type __current_size) const _NOEXCEPT {839 (void)__current_size;840#ifndef _LIBCPP_HAS_NO_ASAN841 if (__current_size == 0)842 __annotate_from_to(0, __map_.size() * __block_size, __asan_poison, __asan_back_moved);843 else {844 __annotate_from_to(0, __start_, __asan_poison, __asan_front_moved);845 __annotate_from_to(__start_ + __current_size, __map_.size() * __block_size, __asan_poison, __asan_back_moved);846 }847#endif848 }849 850 _LIBCPP_HIDE_FROM_ABI void __annotate_delete() const _NOEXCEPT {851#ifndef _LIBCPP_HAS_NO_ASAN852 if (empty()) {853 for (size_t __i = 0; __i < __map_.size(); ++__i) {854 __annotate_whole_block(__i, __asan_unposion);855 }856 } else {857 __annotate_from_to(0, __start_, __asan_unposion, __asan_front_moved);858 __annotate_from_to(__start_ + size(), __map_.size() * __block_size, __asan_unposion, __asan_back_moved);859 }860#endif861 }862 863 _LIBCPP_HIDE_FROM_ABI void __annotate_increase_front(size_type __n) const _NOEXCEPT {864 (void)__n;865#ifndef _LIBCPP_HAS_NO_ASAN866 __annotate_from_to(__start_ - __n, __start_, __asan_unposion, __asan_front_moved);867#endif868 }869 870 _LIBCPP_HIDE_FROM_ABI void __annotate_increase_back(size_type __n) const _NOEXCEPT {871 (void)__n;872#ifndef _LIBCPP_HAS_NO_ASAN873 __annotate_from_to(__start_ + size(), __start_ + size() + __n, __asan_unposion, __asan_back_moved);874#endif875 }876 877 _LIBCPP_HIDE_FROM_ABI void __annotate_shrink_front(size_type __old_size, size_type __old_start) const _NOEXCEPT {878 (void)__old_size;879 (void)__old_start;880#ifndef _LIBCPP_HAS_NO_ASAN881 __annotate_from_to(__old_start, __old_start + (__old_size - size()), __asan_poison, __asan_front_moved);882#endif883 }884 885 _LIBCPP_HIDE_FROM_ABI void __annotate_shrink_back(size_type __old_size, size_type __old_start) const _NOEXCEPT {886 (void)__old_size;887 (void)__old_start;888#ifndef _LIBCPP_HAS_NO_ASAN889 __annotate_from_to(__old_start + size(), __old_start + __old_size, __asan_poison, __asan_back_moved);890#endif891 }892 893 _LIBCPP_HIDE_FROM_ABI void __annotate_poison_block(const void* __beginning, const void* __end) const _NOEXCEPT {894 std::__annotate_double_ended_contiguous_container<_Allocator>(__beginning, __end, __beginning, __end, __end, __end);895 }896 897 _LIBCPP_HIDE_FROM_ABI void898 __annotate_whole_block(size_t __block_index, __asan_annotation_type __annotation_type) const _NOEXCEPT {899 (void)__block_index;900 (void)__annotation_type;901#ifndef _LIBCPP_HAS_NO_ASAN902 __map_const_iterator __block_it = __map_.begin() + __block_index;903 const void* __block_start = std::__to_address(*__block_it);904 const void* __block_end = std::__to_address(*__block_it + __block_size);905 906 if (__annotation_type == __asan_poison)907 __annotate_poison_block(__block_start, __block_end);908 else {909 std::__annotate_double_ended_contiguous_container<_Allocator>(910 __block_start, __block_end, __block_start, __block_start, __block_start, __block_end);911 }912#endif913 }914#if !defined(_LIBCPP_HAS_NO_ASAN)915 916public:917 _LIBCPP_HIDE_FROM_ABI bool __verify_asan_annotations() const _NOEXCEPT {918 // This function tests deque object annotations.919 if (empty()) {920 for (__map_const_iterator __it = __map_.begin(); __it != __map_.end(); ++__it) {921 if (!__sanitizer_verify_double_ended_contiguous_container(922 std::__to_address(*__it),923 std::__to_address(*__it),924 std::__to_address(*__it),925 std::__to_address(*__it + __block_size)))926 return false;927 }928 929 return true;930 }931 932 size_type __end = __start_ + size();933 __map_const_iterator __first_mp = __map_.begin() + __start_ / __block_size;934 __map_const_iterator __last_mp = __map_.begin() + (__end - 1) / __block_size;935 936 // Pointers to first and after last elements937 // Those can be in different deque blocks938 const void* __p_beg = std::__to_address(*__first_mp + (__start_ % __block_size));939 const void* __p_end =940 std::__to_address(*__last_mp + ((__end % __block_size == 0) ? __block_size : __end % __block_size));941 942 for (__map_const_iterator __it = __map_.begin(); __it != __map_.end(); ++__it) {943 // Go over all blocks, find the place we are in and verify its annotations944 // Note that __p_end points *behind* the last item.945 946 // - blocks before the first block with container elements947 // - first block with items948 // - last block with items949 // - blocks after last block with ciontainer elements950 951 // Is the block before or after deque blocks that contain elements?952 if (__it < __first_mp || __it > __last_mp) {953 if (!__sanitizer_verify_double_ended_contiguous_container(954 std::__to_address(*__it),955 std::__to_address(*__it),956 std::__to_address(*__it),957 std::__to_address(*__it + __block_size)))958 return false;959 } else {960 const void* __containers_buffer_beg = (__it == __first_mp) ? __p_beg : (const void*)std::__to_address(*__it);961 const void* __containers_buffer_end =962 (__it == __last_mp) ? __p_end : (const void*)std::__to_address(*__it + __block_size);963 if (!__sanitizer_verify_double_ended_contiguous_container(964 std::__to_address(*__it),965 __containers_buffer_beg,966 __containers_buffer_end,967 std::__to_address(*__it + __block_size))) {968 return false;969 }970 }971 }972 return true;973 }974 975private:976#endif // _LIBCPP_VERIFY_ASAN_DEQUE_ANNOTATIONS977 _LIBCPP_HIDE_FROM_ABI bool __maybe_remove_front_spare(bool __keep_one = true) {978 if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) {979 __annotate_whole_block(0, __asan_unposion);980 __alloc_traits::deallocate(__alloc(), __map_.front(), __block_size);981 __map_.pop_front();982 __start_ -= __block_size;983 return true;984 }985 return false;986 }987 988 _LIBCPP_HIDE_FROM_ABI bool __maybe_remove_back_spare(bool __keep_one = true) {989 if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) {990 __annotate_whole_block(__map_.size() - 1, __asan_unposion);991 __alloc_traits::deallocate(__alloc(), __map_.back(), __block_size);992 __map_.pop_back();993 return true;994 }995 return false;996 }997 998 template <class _Iterator, class _Sentinel>999 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __f, _Sentinel __l);1000 1001 template <class _RandomAccessIterator>1002 _LIBCPP_HIDE_FROM_ABI void __assign_with_size_random_access(_RandomAccessIterator __f, difference_type __n);1003 template <class _Iterator>1004 _LIBCPP_HIDE_FROM_ABI void __assign_with_size(_Iterator __f, difference_type __n);1005 1006 template <class _Iterator, class _Sentinel>1007 _LIBCPP_HIDE_FROM_ABI iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l);1008 1009 template <class _Iterator>1010 _LIBCPP_HIDE_FROM_ABI iterator __insert_with_size(const_iterator __p, _Iterator __f, size_type __n);1011 1012 template <class _BiIter, class _Sentinel>1013 _LIBCPP_HIDE_FROM_ABI iterator1014 __insert_bidirectional(const_iterator __p, _BiIter __f, _Sentinel __sent, size_type __n);1015 template <class _BiIter>1016 _LIBCPP_HIDE_FROM_ABI iterator __insert_bidirectional(const_iterator __p, _BiIter __f, _BiIter __l, size_type __n);1017 1018 template <class _InpIter, __enable_if_t<__has_exactly_input_iterator_category<_InpIter>::value, int> = 0>1019 _LIBCPP_HIDE_FROM_ABI void __append(_InpIter __f, _InpIter __l);1020 template <class _ForIter, __enable_if_t<__has_forward_iterator_category<_ForIter>::value, int> = 0>1021 _LIBCPP_HIDE_FROM_ABI void __append(_ForIter __f, _ForIter __l);1022 1023 template <class _InputIterator>1024 _LIBCPP_HIDE_FROM_ABI void __append_with_size(_InputIterator __from, size_type __n);1025 template <class _InputIterator, class _Sentinel>1026 _LIBCPP_HIDE_FROM_ABI void __append_with_sentinel(_InputIterator __f, _Sentinel __l);1027 1028 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n);1029 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const value_type& __v);1030 _LIBCPP_HIDE_FROM_ABI void __erase_to_end(const_iterator __f);1031 _LIBCPP_HIDE_FROM_ABI void __add_front_capacity();1032 _LIBCPP_HIDE_FROM_ABI void __add_front_capacity(size_type __n);1033 _LIBCPP_HIDE_FROM_ABI void __add_back_capacity();1034 _LIBCPP_HIDE_FROM_ABI void __add_back_capacity(size_type __n);1035 _LIBCPP_HIDE_FROM_ABI iterator __move_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt);1036 _LIBCPP_HIDE_FROM_ABI iterator1037 __move_backward_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt);1038 _LIBCPP_HIDE_FROM_ABI void __move_construct_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt);1039 _LIBCPP_HIDE_FROM_ABI void1040 __move_construct_backward_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt);1041 1042 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const deque& __c) {1043 __copy_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_copy_assignment::value>());1044 }1045 1046 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const deque& __c, true_type) {1047 if (__alloc() != __c.__alloc()) {1048 clear();1049 shrink_to_fit();1050 }1051 __alloc() = __c.__alloc();1052 __map_.__alloc() = __c.__map_.__alloc();1053 }1054 1055 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const deque&, false_type) {}1056 1057 _LIBCPP_HIDE_FROM_ABI void __move_assign(deque& __c, true_type);1058 _LIBCPP_HIDE_FROM_ABI void __move_assign(deque& __c, false_type);1059};1060 1061template <class _Tp, class _Alloc>1062const typename allocator_traits<_Alloc>::difference_type deque<_Tp, _Alloc>::__block_size =1063 __deque_block_size<value_type, difference_type>::value;1064 1065template <class _Tp, class _Allocator>1066deque<_Tp, _Allocator>::deque(size_type __n) : __start_(0), __size_(0, __default_init_tag()) {1067 __annotate_new(0);1068 if (__n > 0)1069 __append(__n);1070}1071 1072template <class _Tp, class _Allocator>1073deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v) : __start_(0), __size_(0, __default_init_tag()) {1074 __annotate_new(0);1075 if (__n > 0)1076 __append(__n, __v);1077}1078 1079template <class _Tp, class _Allocator>1080template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >1081deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l) : __start_(0), __size_(0, __default_init_tag()) {1082 __annotate_new(0);1083 __append(__f, __l);1084}1085 1086template <class _Tp, class _Allocator>1087template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >1088deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a)1089 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {1090 __annotate_new(0);1091 __append(__f, __l);1092}1093 1094template <class _Tp, class _Allocator>1095deque<_Tp, _Allocator>::deque(const deque& __c)1096 : __map_(__pointer_allocator(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))),1097 __start_(0),1098 __size_(0, __map_.__alloc()) {1099 __annotate_new(0);1100 __append(__c.begin(), __c.end());1101}1102 1103template <class _Tp, class _Allocator>1104deque<_Tp, _Allocator>::deque(const deque& __c, const __type_identity_t<allocator_type>& __a)1105 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {1106 __annotate_new(0);1107 __append(__c.begin(), __c.end());1108}1109 1110template <class _Tp, class _Allocator>1111deque<_Tp, _Allocator>& deque<_Tp, _Allocator>::operator=(const deque& __c) {1112 if (this != std::addressof(__c)) {1113 __copy_assign_alloc(__c);1114 assign(__c.begin(), __c.end());1115 }1116 return *this;1117}1118 1119template <class _Tp, class _Allocator>1120template <class _InputIter,1121 __enable_if_t<__has_input_iterator_category<_InputIter>::value &&1122 !__has_random_access_iterator_category<_InputIter>::value,1123 int> >1124void deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l) {1125 __assign_with_sentinel(__f, __l);1126}1127 1128template <class _Tp, class _Allocator>1129template <class _Iterator, class _Sentinel>1130_LIBCPP_HIDE_FROM_ABI void deque<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) {1131 iterator __i = begin();1132 iterator __e = end();1133 for (; __f != __l && __i != __e; ++__f, (void)++__i)1134 *__i = *__f;1135 if (__f != __l)1136 __append_with_sentinel(std::move(__f), std::move(__l));1137 else1138 __erase_to_end(__i);1139}1140 1141template <class _Tp, class _Allocator>1142template <class _RAIter, __enable_if_t<__has_random_access_iterator_category<_RAIter>::value, int> >1143void deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l) {1144 __assign_with_size_random_access(__f, __l - __f);1145}1146 1147template <class _Tp, class _Allocator>1148template <class _RandomAccessIterator>1149_LIBCPP_HIDE_FROM_ABI void1150deque<_Tp, _Allocator>::__assign_with_size_random_access(_RandomAccessIterator __f, difference_type __n) {1151 if (static_cast<size_type>(__n) > size()) {1152 auto __l = __f + size();1153 std::copy(__f, __l, begin());1154 __append_with_size(__l, __n - size());1155 } else1156 __erase_to_end(std::copy_n(__f, __n, begin()));1157}1158 1159template <class _Tp, class _Allocator>1160template <class _Iterator>1161_LIBCPP_HIDE_FROM_ABI void deque<_Tp, _Allocator>::__assign_with_size(_Iterator __f, difference_type __n) {1162 if (static_cast<size_type>(__n) > size()) {1163 auto __added_size = __n - size();1164 1165 auto __i = begin();1166 for (auto __count = size(); __count != 0; --__count) {1167 *__i++ = *__f++;1168 }1169 1170 __append_with_size(__f, __added_size);1171 1172 } else {1173 __erase_to_end(std::copy_n(__f, __n, begin()));1174 }1175}1176 1177template <class _Tp, class _Allocator>1178void deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v) {1179 if (__n > size()) {1180 std::fill_n(begin(), size(), __v);1181 __n -= size();1182 __append(__n, __v);1183 } else1184 __erase_to_end(std::fill_n(begin(), __n, __v));1185}1186 1187template <class _Tp, class _Allocator>1188inline _Allocator deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT {1189 return __alloc();1190}1191 1192template <class _Tp, class _Allocator>1193void deque<_Tp, _Allocator>::resize(size_type __n) {1194 if (__n > size())1195 __append(__n - size());1196 else if (__n < size())1197 __erase_to_end(begin() + __n);1198}1199 1200template <class _Tp, class _Allocator>1201void deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v) {1202 if (__n > size())1203 __append(__n - size(), __v);1204 else if (__n < size())1205 __erase_to_end(begin() + __n);1206}1207 1208template <class _Tp, class _Allocator>1209void deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT {1210 allocator_type& __a = __alloc();1211 if (empty()) {1212 __annotate_delete();1213 while (__map_.size() > 0) {1214 __alloc_traits::deallocate(__a, __map_.back(), __block_size);1215 __map_.pop_back();1216 }1217 __start_ = 0;1218 } else {1219 __maybe_remove_front_spare(/*__keep_one=*/false);1220 __maybe_remove_back_spare(/*__keep_one=*/false);1221 }1222 __map_.shrink_to_fit();1223}1224 1225template <class _Tp, class _Allocator>1226inline typename deque<_Tp, _Allocator>::reference deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT {1227 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i < size(), "deque::operator[] index out of bounds");1228 size_type __p = __start_ + __i;1229 return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);1230}1231 1232template <class _Tp, class _Allocator>1233inline typename deque<_Tp, _Allocator>::const_reference1234deque<_Tp, _Allocator>::operator[](size_type __i) const _NOEXCEPT {1235 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i < size(), "deque::operator[] index out of bounds");1236 size_type __p = __start_ + __i;1237 return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);1238}1239 1240template <class _Tp, class _Allocator>1241inline typename deque<_Tp, _Allocator>::reference deque<_Tp, _Allocator>::at(size_type __i) {1242 if (__i >= size())1243 std::__throw_out_of_range("deque");1244 size_type __p = __start_ + __i;1245 return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);1246}1247 1248template <class _Tp, class _Allocator>1249inline typename deque<_Tp, _Allocator>::const_reference deque<_Tp, _Allocator>::at(size_type __i) const {1250 if (__i >= size())1251 std::__throw_out_of_range("deque");1252 size_type __p = __start_ + __i;1253 return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);1254}1255 1256template <class _Tp, class _Allocator>1257inline typename deque<_Tp, _Allocator>::reference deque<_Tp, _Allocator>::front() _NOEXCEPT {1258 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::front called on an empty deque");1259 return *(*(__map_.begin() + __start_ / __block_size) + __start_ % __block_size);1260}1261 1262template <class _Tp, class _Allocator>1263inline typename deque<_Tp, _Allocator>::const_reference deque<_Tp, _Allocator>::front() const _NOEXCEPT {1264 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::front called on an empty deque");1265 return *(*(__map_.begin() + __start_ / __block_size) + __start_ % __block_size);1266}1267 1268template <class _Tp, class _Allocator>1269inline typename deque<_Tp, _Allocator>::reference deque<_Tp, _Allocator>::back() _NOEXCEPT {1270 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::back called on an empty deque");1271 size_type __p = size() + __start_ - 1;1272 return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);1273}1274 1275template <class _Tp, class _Allocator>1276inline typename deque<_Tp, _Allocator>::const_reference deque<_Tp, _Allocator>::back() const _NOEXCEPT {1277 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::back called on an empty deque");1278 size_type __p = size() + __start_ - 1;1279 return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);1280}1281 1282template <class _Tp, class _Allocator>1283void deque<_Tp, _Allocator>::push_back(const value_type& __v) {1284 allocator_type& __a = __alloc();1285 if (__back_spare() == 0)1286 __add_back_capacity();1287 // __back_spare() >= 11288 __annotate_increase_back(1);1289 __alloc_traits::construct(__a, std::addressof(*end()), __v);1290 ++__size();1291}1292 1293template <class _Tp, class _Allocator>1294void deque<_Tp, _Allocator>::push_front(const value_type& __v) {1295 allocator_type& __a = __alloc();1296 if (__front_spare() == 0)1297 __add_front_capacity();1298 // __front_spare() >= 11299 __annotate_increase_front(1);1300 __alloc_traits::construct(__a, std::addressof(*--begin()), __v);1301 --__start_;1302 ++__size();1303}1304 1305template <class _Tp, class _Allocator>1306typename deque<_Tp, _Allocator>::iterator deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v) {1307 size_type __pos = __p - begin();1308 size_type __to_end = size() - __pos;1309 allocator_type& __a = __alloc();1310 if (__pos < __to_end) { // insert by shifting things backward1311 if (__front_spare() == 0)1312 __add_front_capacity();1313 // __front_spare() >= 11314 __annotate_increase_front(1);1315 if (__pos == 0) {1316 __alloc_traits::construct(__a, std::addressof(*--begin()), __v);1317 --__start_;1318 ++__size();1319 } else {1320 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);1321 iterator __b = begin();1322 iterator __bm1 = std::prev(__b);1323 if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))1324 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);1325 __alloc_traits::construct(__a, std::addressof(*__bm1), std::move(*__b));1326 --__start_;1327 ++__size();1328 if (__pos > 1)1329 __b = __move_and_check(std::next(__b), __b + __pos, __b, __vt);1330 *__b = *__vt;1331 }1332 } else { // insert by shifting things forward1333 if (__back_spare() == 0)1334 __add_back_capacity();1335 // __back_capacity >= 11336 __annotate_increase_back(1);1337 size_type __de = size() - __pos;1338 if (__de == 0) {1339 __alloc_traits::construct(__a, std::addressof(*end()), __v);1340 ++__size();1341 } else {1342 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);1343 iterator __e = end();1344 iterator __em1 = std::prev(__e);1345 if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))1346 __vt = pointer_traits<const_pointer>::pointer_to(*__e);1347 __alloc_traits::construct(__a, std::addressof(*__e), std::move(*__em1));1348 ++__size();1349 if (__de > 1)1350 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);1351 *--__e = *__vt;1352 }1353 }1354 return begin() + __pos;1355}1356 1357template <class _Tp, class _Allocator>1358typename deque<_Tp, _Allocator>::iterator1359deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v) {1360 size_type __pos = __p - begin();1361 size_type __to_end = __size() - __pos;1362 allocator_type& __a = __alloc();1363 if (__pos < __to_end) { // insert by shifting things backward1364 if (__n > __front_spare())1365 __add_front_capacity(__n - __front_spare());1366 // __n <= __front_spare()1367 __annotate_increase_front(__n);1368 iterator __old_begin = begin();1369 iterator __i = __old_begin;1370 if (__n > __pos) {1371 for (size_type __m = __n - __pos; __m; --__m, --__start_, ++__size())1372 __alloc_traits::construct(__a, std::addressof(*--__i), __v);1373 __n = __pos;1374 }1375 if (__n > 0) {1376 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);1377 iterator __obn = __old_begin + __n;1378 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);1379 if (__n < __pos)1380 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);1381 std::fill_n(__old_begin, __n, *__vt);1382 }1383 } else { // insert by shifting things forward1384 size_type __back_capacity = __back_spare();1385 if (__n > __back_capacity)1386 __add_back_capacity(__n - __back_capacity);1387 // __n <= __back_capacity1388 __annotate_increase_back(__n);1389 iterator __old_end = end();1390 iterator __i = __old_end;1391 size_type __de = size() - __pos;1392 if (__n > __de) {1393 for (size_type __m = __n - __de; __m; --__m, (void)++__i, ++__size())1394 __alloc_traits::construct(__a, std::addressof(*__i), __v);1395 __n = __de;1396 }1397 if (__n > 0) {1398 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);1399 iterator __oen = __old_end - __n;1400 __move_construct_and_check(__oen, __old_end, __i, __vt);1401 if (__n < __de)1402 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);1403 std::fill_n(__old_end - __n, __n, *__vt);1404 }1405 }1406 return begin() + __pos;1407}1408 1409template <class _Tp, class _Allocator>1410template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> >1411typename deque<_Tp, _Allocator>::iterator1412deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l) {1413 return __insert_with_sentinel(__p, __f, __l);1414}1415 1416template <class _Tp, class _Allocator>1417template <class _Iterator, class _Sentinel>1418_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator1419deque<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) {1420 __split_buffer<value_type, allocator_type&> __buf(__alloc());1421 __buf.__construct_at_end_with_sentinel(std::move(__f), std::move(__l));1422 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;1423 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));1424}1425 1426template <class _Tp, class _Allocator>1427template <class _ForwardIterator, __enable_if_t<__has_exactly_forward_iterator_category<_ForwardIterator>::value, int> >1428typename deque<_Tp, _Allocator>::iterator1429deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l) {1430 return __insert_with_size(__p, __f, std::distance(__f, __l));1431}1432 1433template <class _Tp, class _Allocator>1434template <class _Iterator>1435_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator1436deque<_Tp, _Allocator>::__insert_with_size(const_iterator __p, _Iterator __f, size_type __n) {1437 __split_buffer<value_type, allocator_type&> __buf(__n, 0, __alloc());1438 __buf.__construct_at_end_with_size(__f, __n);1439 typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;1440 return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));1441}1442 1443template <class _Tp, class _Allocator>1444template <class _BiIter, __enable_if_t<__has_bidirectional_iterator_category<_BiIter>::value, int> >1445typename deque<_Tp, _Allocator>::iterator deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l) {1446 return __insert_bidirectional(__p, __f, __l, std::distance(__f, __l));1447}1448 1449template <class _Tp, class _Allocator>1450template <class _BiIter, class _Sentinel>1451_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator1452deque<_Tp, _Allocator>::__insert_bidirectional(const_iterator __p, _BiIter __f, _Sentinel, size_type __n) {1453 return __insert_bidirectional(__p, __f, std::next(__f, __n), __n);1454}1455 1456template <class _Tp, class _Allocator>1457template <class _BiIter>1458_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator1459deque<_Tp, _Allocator>::__insert_bidirectional(const_iterator __p, _BiIter __f, _BiIter __l, size_type __n) {1460 size_type __pos = __p - begin();1461 size_type __to_end = size() - __pos;1462 allocator_type& __a = __alloc();1463 if (__pos < __to_end) { // insert by shifting things backward1464 if (__n > __front_spare())1465 __add_front_capacity(__n - __front_spare());1466 // __n <= __front_spare()1467 __annotate_increase_front(__n);1468 iterator __old_begin = begin();1469 iterator __i = __old_begin;1470 _BiIter __m = __f;1471 if (__n > __pos) {1472 __m = __pos < __n / 2 ? std::prev(__l, __pos) : std::next(__f, __n - __pos);1473 for (_BiIter __j = __m; __j != __f; --__start_, ++__size())1474 __alloc_traits::construct(__a, std::addressof(*--__i), *--__j);1475 __n = __pos;1476 }1477 if (__n > 0) {1478 iterator __obn = __old_begin + __n;1479 for (iterator __j = __obn; __j != __old_begin;) {1480 __alloc_traits::construct(__a, std::addressof(*--__i), std::move(*--__j));1481 --__start_;1482 ++__size();1483 }1484 if (__n < __pos)1485 __old_begin = std::move(__obn, __old_begin + __pos, __old_begin);1486 std::copy(__m, __l, __old_begin);1487 }1488 } else { // insert by shifting things forward1489 size_type __back_capacity = __back_spare();1490 if (__n > __back_capacity)1491 __add_back_capacity(__n - __back_capacity);1492 // __n <= __back_capacity1493 __annotate_increase_back(__n);1494 iterator __old_end = end();1495 iterator __i = __old_end;1496 _BiIter __m = __l;1497 size_type __de = size() - __pos;1498 if (__n > __de) {1499 __m = __de < __n / 2 ? std::next(__f, __de) : std::prev(__l, __n - __de);1500 for (_BiIter __j = __m; __j != __l; ++__i, (void)++__j, ++__size())1501 __alloc_traits::construct(__a, std::addressof(*__i), *__j);1502 __n = __de;1503 }1504 if (__n > 0) {1505 iterator __oen = __old_end - __n;1506 for (iterator __j = __oen; __j != __old_end; ++__i, (void)++__j, ++__size())1507 __alloc_traits::construct(__a, std::addressof(*__i), std::move(*__j));1508 if (__n < __de)1509 __old_end = std::move_backward(__old_end - __de, __oen, __old_end);1510 std::copy_backward(__f, __m, __old_end);1511 }1512 }1513 return begin() + __pos;1514}1515 1516template <class _Tp, class _Allocator>1517template <class _InpIter, __enable_if_t<__has_exactly_input_iterator_category<_InpIter>::value, int> >1518void deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l) {1519 __append_with_sentinel(__f, __l);1520}1521 1522template <class _Tp, class _Allocator>1523template <class _InputIterator, class _Sentinel>1524_LIBCPP_HIDE_FROM_ABI void deque<_Tp, _Allocator>::__append_with_sentinel(_InputIterator __f, _Sentinel __l) {1525 for (; __f != __l; ++__f)1526 push_back(*__f);1527}1528 1529template <class _Tp, class _Allocator>1530template <class _ForIter, __enable_if_t<__has_forward_iterator_category<_ForIter>::value, int> >1531void deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l) {1532 __append_with_size(__f, std::distance(__f, __l));1533}1534 1535template <class _Tp, class _Allocator>1536template <class _InputIterator>1537_LIBCPP_HIDE_FROM_ABI void deque<_Tp, _Allocator>::__append_with_size(_InputIterator __f, size_type __n) {1538 allocator_type& __a = __alloc();1539 size_type __back_capacity = __back_spare();1540 if (__n > __back_capacity)1541 __add_back_capacity(__n - __back_capacity);1542 1543 // __n <= __back_capacity1544 __annotate_increase_back(__n);1545 for (__deque_block_range __br : __deque_range(end(), end() + __n)) {1546 _ConstructTransaction __tx(this, __br);1547 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) {1548 __alloc_traits::construct(__a, std::__to_address(__tx.__pos_), *__f);1549 }1550 }1551}1552 1553template <class _Tp, class _Allocator>1554void deque<_Tp, _Allocator>::__append(size_type __n) {1555 allocator_type& __a = __alloc();1556 size_type __back_capacity = __back_spare();1557 if (__n > __back_capacity)1558 __add_back_capacity(__n - __back_capacity);1559 // __n <= __back_capacity1560 __annotate_increase_back(__n);1561 for (__deque_block_range __br : __deque_range(end(), end() + __n)) {1562 _ConstructTransaction __tx(this, __br);1563 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {1564 __alloc_traits::construct(__a, std::__to_address(__tx.__pos_));1565 }1566 }1567}1568 1569template <class _Tp, class _Allocator>1570void deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v) {1571 allocator_type& __a = __alloc();1572 size_type __back_capacity = __back_spare();1573 if (__n > __back_capacity)1574 __add_back_capacity(__n - __back_capacity);1575 // __n <= __back_capacity1576 __annotate_increase_back(__n);1577 for (__deque_block_range __br : __deque_range(end(), end() + __n)) {1578 _ConstructTransaction __tx(this, __br);1579 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {1580 __alloc_traits::construct(__a, std::__to_address(__tx.__pos_), __v);1581 }1582 }1583}1584 1585// Create front capacity for one block of elements.1586// Strong guarantee. Either do it or don't touch anything.1587template <class _Tp, class _Allocator>1588void deque<_Tp, _Allocator>::__add_front_capacity() {1589 allocator_type& __a = __alloc();1590 if (__back_spare() >= __block_size) {1591 __start_ += __block_size;1592 pointer __pt = __map_.back();1593 __map_.pop_back();1594 __map_.push_front(__pt);1595 }1596 // Else if __map_.size() < __map_.capacity() then we need to allocate 1 buffer1597 else if (__map_.size() < __map_.capacity()) { // we can put the new buffer into the map, but don't shift things around1598 // until all buffers are allocated. If we throw, we don't need to fix1599 // anything up (any added buffers are undetectible)1600 if (__map_.__front_spare() > 0)1601 __map_.push_front(__alloc_traits::allocate(__a, __block_size));1602 else {1603 __map_.push_back(__alloc_traits::allocate(__a, __block_size));1604 // Done allocating, reorder capacity1605 pointer __pt = __map_.back();1606 __map_.pop_back();1607 __map_.push_front(__pt);1608 }1609 __start_ = __map_.size() == 1 ? __block_size / 2 : __start_ + __block_size;1610 }1611 // Else need to allocate 1 buffer, *and* we need to reallocate __map_.1612 else {1613 __split_buffer<pointer, __pointer_allocator&> __buf(1614 std::max<size_type>(2 * __map_.capacity(), 1), 0, __map_.__alloc());1615 1616 typedef __allocator_destructor<_Allocator> _Dp;1617 unique_ptr<pointer, _Dp> __hold(__alloc_traits::allocate(__a, __block_size), _Dp(__a, __block_size));1618 __buf.push_back(__hold.get());1619 __hold.release();1620 1621 for (__map_pointer __i = __map_.begin(); __i != __map_.end(); ++__i)1622 __buf.push_back(*__i);1623 std::swap(__map_.__first_, __buf.__first_);1624 std::swap(__map_.__begin_, __buf.__begin_);1625 std::swap(__map_.__end_, __buf.__end_);1626 std::swap(__map_.__end_cap(), __buf.__end_cap());1627 __start_ = __map_.size() == 1 ? __block_size / 2 : __start_ + __block_size;1628 }1629 __annotate_whole_block(0, __asan_poison);1630}1631 1632// Create front capacity for __n elements.1633// Strong guarantee. Either do it or don't touch anything.1634template <class _Tp, class _Allocator>1635void deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) {1636 allocator_type& __a = __alloc();1637 size_type __nb = __recommend_blocks(__n + __map_.empty());1638 // Number of unused blocks at back:1639 size_type __back_capacity = __back_spare() / __block_size;1640 __back_capacity = std::min(__back_capacity, __nb); // don't take more than you need1641 __nb -= __back_capacity; // number of blocks need to allocate1642 // If __nb == 0, then we have sufficient capacity.1643 if (__nb == 0) {1644 __start_ += __block_size * __back_capacity;1645 for (; __back_capacity > 0; --__back_capacity) {1646 pointer __pt = __map_.back();1647 __map_.pop_back();1648 __map_.push_front(__pt);1649 }1650 }1651 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers1652 else if (__nb <= __map_.capacity() -1653 __map_.size()) { // we can put the new buffers into the map, but don't shift things around1654 // until all buffers are allocated. If we throw, we don't need to fix1655 // anything up (any added buffers are undetectible)1656 for (; __nb > 0; --__nb, __start_ += __block_size - (__map_.size() == 1)) {1657 if (__map_.__front_spare() == 0)1658 break;1659 __map_.push_front(__alloc_traits::allocate(__a, __block_size));1660 __annotate_whole_block(0, __asan_poison);1661 }1662 for (; __nb > 0; --__nb, ++__back_capacity)1663 __map_.push_back(__alloc_traits::allocate(__a, __block_size));1664 // Done allocating, reorder capacity1665 __start_ += __back_capacity * __block_size;1666 for (; __back_capacity > 0; --__back_capacity) {1667 pointer __pt = __map_.back();1668 __map_.pop_back();1669 __map_.push_front(__pt);1670 __annotate_whole_block(0, __asan_poison);1671 }1672 }1673 // Else need to allocate __nb buffers, *and* we need to reallocate __map_.1674 else {1675 size_type __ds = (__nb + __back_capacity) * __block_size - __map_.empty();1676 __split_buffer<pointer, __pointer_allocator&> __buf(1677 std::max<size_type>(2 * __map_.capacity(), __nb + __map_.size()), 0, __map_.__alloc());1678#ifndef _LIBCPP_HAS_NO_EXCEPTIONS1679 try {1680#endif // _LIBCPP_HAS_NO_EXCEPTIONS1681 for (; __nb > 0; --__nb) {1682 __buf.push_back(__alloc_traits::allocate(__a, __block_size));1683 // ASan: this is empty container, we have to poison whole block1684 __annotate_poison_block(std::__to_address(__buf.back()), std::__to_address(__buf.back() + __block_size));1685 }1686#ifndef _LIBCPP_HAS_NO_EXCEPTIONS1687 } catch (...) {1688 __annotate_delete();1689 for (__map_pointer __i = __buf.begin(); __i != __buf.end(); ++__i)1690 __alloc_traits::deallocate(__a, *__i, __block_size);1691 throw;1692 }1693#endif // _LIBCPP_HAS_NO_EXCEPTIONS1694 for (; __back_capacity > 0; --__back_capacity) {1695 __buf.push_back(__map_.back());1696 __map_.pop_back();1697 }1698 for (__map_pointer __i = __map_.begin(); __i != __map_.end(); ++__i)1699 __buf.push_back(*__i);1700 std::swap(__map_.__first_, __buf.__first_);1701 std::swap(__map_.__begin_, __buf.__begin_);1702 std::swap(__map_.__end_, __buf.__end_);1703 std::swap(__map_.__end_cap(), __buf.__end_cap());1704 __start_ += __ds;1705 }1706}1707 1708// Create back capacity for one block of elements.1709// Strong guarantee. Either do it or don't touch anything.1710template <class _Tp, class _Allocator>1711void deque<_Tp, _Allocator>::__add_back_capacity() {1712 allocator_type& __a = __alloc();1713 if (__front_spare() >= __block_size) {1714 __start_ -= __block_size;1715 pointer __pt = __map_.front();1716 __map_.pop_front();1717 __map_.push_back(__pt);1718 }1719 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers1720 else if (__map_.size() < __map_.capacity()) { // we can put the new buffer into the map, but don't shift things around1721 // until it is allocated. If we throw, we don't need to fix1722 // anything up (any added buffers are undetectible)1723 if (__map_.__back_spare() != 0)1724 __map_.push_back(__alloc_traits::allocate(__a, __block_size));1725 else {1726 __map_.push_front(__alloc_traits::allocate(__a, __block_size));1727 // Done allocating, reorder capacity1728 pointer __pt = __map_.front();1729 __map_.pop_front();1730 __map_.push_back(__pt);1731 }1732 __annotate_whole_block(__map_.size() - 1, __asan_poison);1733 }1734 // Else need to allocate 1 buffer, *and* we need to reallocate __map_.1735 else {1736 __split_buffer<pointer, __pointer_allocator&> __buf(1737 std::max<size_type>(2 * __map_.capacity(), 1), __map_.size(), __map_.__alloc());1738 1739 typedef __allocator_destructor<_Allocator> _Dp;1740 unique_ptr<pointer, _Dp> __hold(__alloc_traits::allocate(__a, __block_size), _Dp(__a, __block_size));1741 __buf.push_back(__hold.get());1742 __hold.release();1743 1744 for (__map_pointer __i = __map_.end(); __i != __map_.begin();)1745 __buf.push_front(*--__i);1746 std::swap(__map_.__first_, __buf.__first_);1747 std::swap(__map_.__begin_, __buf.__begin_);1748 std::swap(__map_.__end_, __buf.__end_);1749 std::swap(__map_.__end_cap(), __buf.__end_cap());1750 __annotate_whole_block(__map_.size() - 1, __asan_poison);1751 }1752}1753 1754// Create back capacity for __n elements.1755// Strong guarantee. Either do it or don't touch anything.1756template <class _Tp, class _Allocator>1757void deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) {1758 allocator_type& __a = __alloc();1759 size_type __nb = __recommend_blocks(__n + __map_.empty());1760 // Number of unused blocks at front:1761 size_type __front_capacity = __front_spare() / __block_size;1762 __front_capacity = std::min(__front_capacity, __nb); // don't take more than you need1763 __nb -= __front_capacity; // number of blocks need to allocate1764 // If __nb == 0, then we have sufficient capacity.1765 if (__nb == 0) {1766 __start_ -= __block_size * __front_capacity;1767 for (; __front_capacity > 0; --__front_capacity) {1768 pointer __pt = __map_.front();1769 __map_.pop_front();1770 __map_.push_back(__pt);1771 }1772 }1773 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers1774 else if (__nb <= __map_.capacity() -1775 __map_.size()) { // we can put the new buffers into the map, but don't shift things around1776 // until all buffers are allocated. If we throw, we don't need to fix1777 // anything up (any added buffers are undetectible)1778 for (; __nb > 0; --__nb) {1779 if (__map_.__back_spare() == 0)1780 break;1781 __map_.push_back(__alloc_traits::allocate(__a, __block_size));1782 __annotate_whole_block(__map_.size() - 1, __asan_poison);1783 }1784 for (; __nb > 0; --__nb, ++__front_capacity, __start_ += __block_size - (__map_.size() == 1)) {1785 __map_.push_front(__alloc_traits::allocate(__a, __block_size));1786 __annotate_whole_block(0, __asan_poison);1787 }1788 // Done allocating, reorder capacity1789 __start_ -= __block_size * __front_capacity;1790 for (; __front_capacity > 0; --__front_capacity) {1791 pointer __pt = __map_.front();1792 __map_.pop_front();1793 __map_.push_back(__pt);1794 }1795 }1796 // Else need to allocate __nb buffers, *and* we need to reallocate __map_.1797 else {1798 size_type __ds = __front_capacity * __block_size;1799 __split_buffer<pointer, __pointer_allocator&> __buf(1800 std::max<size_type>(2 * __map_.capacity(), __nb + __map_.size()),1801 __map_.size() - __front_capacity,1802 __map_.__alloc());1803#ifndef _LIBCPP_HAS_NO_EXCEPTIONS1804 try {1805#endif // _LIBCPP_HAS_NO_EXCEPTIONS1806 for (; __nb > 0; --__nb) {1807 __buf.push_back(__alloc_traits::allocate(__a, __block_size));1808 // ASan: this is an empty container, we have to poison the whole block1809 __annotate_poison_block(std::__to_address(__buf.back()), std::__to_address(__buf.back() + __block_size));1810 }1811#ifndef _LIBCPP_HAS_NO_EXCEPTIONS1812 } catch (...) {1813 __annotate_delete();1814 for (__map_pointer __i = __buf.begin(); __i != __buf.end(); ++__i)1815 __alloc_traits::deallocate(__a, *__i, __block_size);1816 throw;1817 }1818#endif // _LIBCPP_HAS_NO_EXCEPTIONS1819 for (; __front_capacity > 0; --__front_capacity) {1820 __buf.push_back(__map_.front());1821 __map_.pop_front();1822 }1823 for (__map_pointer __i = __map_.end(); __i != __map_.begin();)1824 __buf.push_front(*--__i);1825 std::swap(__map_.__first_, __buf.__first_);1826 std::swap(__map_.__begin_, __buf.__begin_);1827 std::swap(__map_.__end_, __buf.__end_);1828 std::swap(__map_.__end_cap(), __buf.__end_cap());1829 __start_ -= __ds;1830 }1831}1832 1833template <class _Tp, class _Allocator>1834void deque<_Tp, _Allocator>::pop_front() {1835 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::pop_front called on an empty deque");1836 size_type __old_sz = size();1837 size_type __old_start = __start_;1838 allocator_type& __a = __alloc();1839 __alloc_traits::destroy(1840 __a, std::__to_address(*(__map_.begin() + __start_ / __block_size) + __start_ % __block_size));1841 --__size();1842 ++__start_;1843 __annotate_shrink_front(__old_sz, __old_start);1844 __maybe_remove_front_spare();1845}1846 1847template <class _Tp, class _Allocator>1848void deque<_Tp, _Allocator>::pop_back() {1849 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "deque::pop_back called on an empty deque");1850 size_type __old_sz = size();1851 size_type __old_start = __start_;1852 allocator_type& __a = __alloc();1853 size_type __p = size() + __start_ - 1;1854 __alloc_traits::destroy(__a, std::__to_address(*(__map_.begin() + __p / __block_size) + __p % __block_size));1855 --__size();1856 __annotate_shrink_back(__old_sz, __old_start);1857 __maybe_remove_back_spare();1858}1859 1860// move assign [__f, __l) to [__r, __r + (__l-__f)).1861// If __vt points into [__f, __l), then subtract (__f - __r) from __vt.1862template <class _Tp, class _Allocator>1863typename deque<_Tp, _Allocator>::iterator1864deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) {1865 // as if1866 // for (; __f != __l; ++__f, ++__r)1867 // *__r = std::move(*__f);1868 difference_type __n = __l - __f;1869 while (__n > 0) {1870 pointer __fb = __f.__ptr_;1871 pointer __fe = *__f.__m_iter_ + __block_size;1872 difference_type __bs = __fe - __fb;1873 if (__bs > __n) {1874 __bs = __n;1875 __fe = __fb + __bs;1876 }1877 if (__fb <= __vt && __vt < __fe)1878 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;1879 __r = std::move(__fb, __fe, __r);1880 __n -= __bs;1881 __f += __bs;1882 }1883 return __r;1884}1885 1886// move assign [__f, __l) to [__r - (__l-__f), __r) backwards.1887// If __vt points into [__f, __l), then add (__r - __l) to __vt.1888template <class _Tp, class _Allocator>1889typename deque<_Tp, _Allocator>::iterator1890deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) {1891 // as if1892 // while (__f != __l)1893 // *--__r = std::move(*--__l);1894 difference_type __n = __l - __f;1895 while (__n > 0) {1896 --__l;1897 pointer __lb = *__l.__m_iter_;1898 pointer __le = __l.__ptr_ + 1;1899 difference_type __bs = __le - __lb;1900 if (__bs > __n) {1901 __bs = __n;1902 __lb = __le - __bs;1903 }1904 if (__lb <= __vt && __vt < __le)1905 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_;1906 __r = std::move_backward(__lb, __le, __r);1907 __n -= __bs;1908 __l -= __bs - 1;1909 }1910 return __r;1911}1912 1913// move construct [__f, __l) to [__r, __r + (__l-__f)).1914// If __vt points into [__f, __l), then add (__r - __f) to __vt.1915template <class _Tp, class _Allocator>1916void deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) {1917 allocator_type& __a = __alloc();1918 // as if1919 // for (; __f != __l; ++__r, ++__f, ++__size())1920 // __alloc_traits::construct(__a, std::addressof(*__r), std::move(*__f));1921 difference_type __n = __l - __f;1922 while (__n > 0) {1923 pointer __fb = __f.__ptr_;1924 pointer __fe = *__f.__m_iter_ + __block_size;1925 difference_type __bs = __fe - __fb;1926 if (__bs > __n) {1927 __bs = __n;1928 __fe = __fb + __bs;1929 }1930 if (__fb <= __vt && __vt < __fe)1931 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;1932 for (; __fb != __fe; ++__fb, ++__r, ++__size())1933 __alloc_traits::construct(__a, std::addressof(*__r), std::move(*__fb));1934 __n -= __bs;1935 __f += __bs;1936 }1937}1938 1939// move construct [__f, __l) to [__r - (__l-__f), __r) backwards.1940// If __vt points into [__f, __l), then subtract (__l - __r) from __vt.1941template <class _Tp, class _Allocator>1942void deque<_Tp, _Allocator>::__move_construct_backward_and_check(1943 iterator __f, iterator __l, iterator __r, const_pointer& __vt) {1944 allocator_type& __a = __alloc();1945 // as if1946 // for (iterator __j = __l; __j != __f;)1947 // {1948 // __alloc_traitsconstruct(__a, std::addressof(*--__r), std::move(*--__j));1949 // --__start_;1950 // ++__size();1951 // }1952 difference_type __n = __l - __f;1953 while (__n > 0) {1954 --__l;1955 pointer __lb = *__l.__m_iter_;1956 pointer __le = __l.__ptr_ + 1;1957 difference_type __bs = __le - __lb;1958 if (__bs > __n) {1959 __bs = __n;1960 __lb = __le - __bs;1961 }1962 if (__lb <= __vt && __vt < __le)1963 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;1964 while (__le != __lb) {1965 __alloc_traits::construct(__a, std::addressof(*--__r), std::move(*--__le));1966 --__start_;1967 ++__size();1968 }1969 __n -= __bs;1970 __l -= __bs - 1;1971 }1972}1973 1974template <class _Tp, class _Allocator>1975typename deque<_Tp, _Allocator>::iterator deque<_Tp, _Allocator>::erase(const_iterator __f) {1976 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(1977 __f != end(), "deque::erase(iterator) called with a non-dereferenceable iterator");1978 size_type __old_sz = size();1979 size_type __old_start = __start_;1980 iterator __b = begin();1981 difference_type __pos = __f - __b;1982 iterator __p = __b + __pos;1983 allocator_type& __a = __alloc();1984 if (static_cast<size_t>(__pos) <= (size() - 1) / 2) { // erase from front1985 std::move_backward(__b, __p, std::next(__p));1986 __alloc_traits::destroy(__a, std::addressof(*__b));1987 --__size();1988 ++__start_;1989 __annotate_shrink_front(__old_sz, __old_start);1990 __maybe_remove_front_spare();1991 } else { // erase from back1992 iterator __i = std::move(std::next(__p), end(), __p);1993 __alloc_traits::destroy(__a, std::addressof(*__i));1994 --__size();1995 __annotate_shrink_back(__old_sz, __old_start);1996 __maybe_remove_back_spare();1997 }1998 return begin() + __pos;1999}2000 2001template <class _Tp, class _Allocator>2002typename deque<_Tp, _Allocator>::iterator deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) {2003 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__f <= __l, "deque::erase(first, last) called with an invalid range");2004 size_type __old_sz = size();2005 size_type __old_start = __start_;2006 difference_type __n = __l - __f;2007 iterator __b = begin();2008 difference_type __pos = __f - __b;2009 iterator __p = __b + __pos;2010 if (__n > 0) {2011 allocator_type& __a = __alloc();2012 if (static_cast<size_t>(__pos) <= (size() - __n) / 2) { // erase from front2013 iterator __i = std::move_backward(__b, __p, __p + __n);2014 for (; __b != __i; ++__b)2015 __alloc_traits::destroy(__a, std::addressof(*__b));2016 __size() -= __n;2017 __start_ += __n;2018 __annotate_shrink_front(__old_sz, __old_start);2019 while (__maybe_remove_front_spare()) {2020 }2021 } else { // erase from back2022 iterator __i = std::move(__p + __n, end(), __p);2023 for (iterator __e = end(); __i != __e; ++__i)2024 __alloc_traits::destroy(__a, std::addressof(*__i));2025 __size() -= __n;2026 __annotate_shrink_back(__old_sz, __old_start);2027 while (__maybe_remove_back_spare()) {2028 }2029 }2030 }2031 return begin() + __pos;2032}2033 2034template <class _Tp, class _Allocator>2035void deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f) {2036 size_type __old_sz = size();2037 size_type __old_start = __start_;2038 iterator __e = end();2039 difference_type __n = __e - __f;2040 if (__n > 0) {2041 allocator_type& __a = __alloc();2042 iterator __b = begin();2043 difference_type __pos = __f - __b;2044 for (iterator __p = __b + __pos; __p != __e; ++__p)2045 __alloc_traits::destroy(__a, std::addressof(*__p));2046 __size() -= __n;2047 __annotate_shrink_back(__old_sz, __old_start);2048 while (__maybe_remove_back_spare()) {2049 }2050 }2051}2052 2053template <class _Tp, class _Allocator>2054inline void deque<_Tp, _Allocator>::swap(deque& __c) {2055 __map_.swap(__c.__map_);2056 std::swap(__start_, __c.__start_);2057 std::swap(__size(), __c.__size());2058 std::__swap_allocator(__alloc(), __c.__alloc());2059}2060 2061template <class _Tp, class _Allocator>2062inline void deque<_Tp, _Allocator>::clear() _NOEXCEPT {2063 __annotate_delete();2064 allocator_type& __a = __alloc();2065 for (iterator __i = begin(), __e = end(); __i != __e; ++__i)2066 __alloc_traits::destroy(__a, std::addressof(*__i));2067 __size() = 0;2068 while (__map_.size() > 2) {2069 __alloc_traits::deallocate(__a, __map_.front(), __block_size);2070 __map_.pop_front();2071 }2072 switch (__map_.size()) {2073 case 1:2074 __start_ = __block_size / 2;2075 break;2076 case 2:2077 __start_ = __block_size;2078 break;2079 }2080 __annotate_new(0);2081}2082 2083template <class _Tp, class _Allocator>2084inline _LIBCPP_HIDE_FROM_ABI bool operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {2085 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();2086 return __sz == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());2087}2088 2089template <class _Tp, class _Allocator>2090inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {2091 return !(__x == __y);2092}2093 2094template <class _Tp, class _Allocator>2095inline _LIBCPP_HIDE_FROM_ABI bool operator<(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {2096 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());2097}2098 2099template <class _Tp, class _Allocator>2100inline _LIBCPP_HIDE_FROM_ABI bool operator>(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {2101 return __y < __x;2102}2103 2104template <class _Tp, class _Allocator>2105inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {2106 return !(__x < __y);2107}2108 2109template <class _Tp, class _Allocator>2110inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {2111 return !(__y < __x);2112}2113 2114template <class _Tp, class _Allocator>2115inline _LIBCPP_HIDE_FROM_ABI void swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) {2116 __x.swap(__y);2117}2118 2119_LIBCPP_END_NAMESPACE_STD2120 2121_LIBCPP_POP_MACROS2122 2123#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)2124# include <__cxx03/algorithm>2125# include <__cxx03/atomic>2126# include <__cxx03/cstdlib>2127# include <__cxx03/functional>2128# include <__cxx03/iosfwd>2129# include <__cxx03/iterator>2130# include <__cxx03/type_traits>2131# include <__cxx03/typeinfo>2132#endif2133 2134#endif // _LIBCPP___CXX03_DEQUE2135