Debian Codegraph @

libcxx/include/__cxx03/deque

raw
1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _LIBCPP___CXX03_DEQUE
11 #define _LIBCPP___CXX03_DEQUE
12
13 /*
14 deque synopsis
15
16 namespace std
17 {
18
19 template <class T, class Allocator = allocator<T> >
20 class deque
21 {
22 public:
23 // types:
24 typedef T value_type;
25 typedef Allocator allocator_type;
26
27 typedef typename allocator_type::reference reference;
28 typedef typename allocator_type::const_reference const_reference;
29 typedef implementation-defined iterator;
30 typedef implementation-defined const_iterator;
31 typedef typename allocator_type::size_type size_type;
32 typedef typename allocator_type::difference_type difference_type;
33
34 typedef typename allocator_type::pointer pointer;
35 typedef typename allocator_type::const_pointer const_pointer;
36 typedef std::reverse_iterator<iterator> reverse_iterator;
37 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
38
39 // construct/copy/destroy:
40 deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);
41 explicit deque(const allocator_type& a);
42 explicit deque(size_type n);
43 explicit deque(size_type n, const allocator_type& a); // C++14
44 deque(size_type n, const value_type& v);
45 deque(size_type n, const value_type& v, const allocator_type& a);
46 template <class InputIterator>
47 deque(InputIterator f, InputIterator l);
48 template <class InputIterator>
49 deque(InputIterator f, InputIterator l, const allocator_type& a);
50 template<container-compatible-range<T> R>
51 deque(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
52 deque(const deque& c);
53 deque(deque&& c)
54 noexcept(is_nothrow_move_constructible<allocator_type>::value);
55 deque(initializer_list<value_type> il, const Allocator& a = allocator_type());
56 deque(const deque& c, const allocator_type& a);
57 deque(deque&& c, const allocator_type& a);
58 ~deque();
59
60 deque& operator=(const deque& c);
61 deque& operator=(deque&& c)
62 noexcept(
63 allocator_type::propagate_on_container_move_assignment::value &&
64 is_nothrow_move_assignable<allocator_type>::value);
65 deque& operator=(initializer_list<value_type> il);
66
67 template <class InputIterator>
68 void assign(InputIterator f, InputIterator l);
69 template<container-compatible-range<T> R>
70 void assign_range(R&& rg); // C++23
71 void assign(size_type n, const value_type& v);
72 void assign(initializer_list<value_type> il);
73
74 allocator_type get_allocator() const noexcept;
75
76 // iterators:
77
78 iterator begin() noexcept;
79 const_iterator begin() const noexcept;
80 iterator end() noexcept;
81 const_iterator end() const noexcept;
82
83 reverse_iterator rbegin() noexcept;
84 const_reverse_iterator rbegin() const noexcept;
85 reverse_iterator rend() noexcept;
86 const_reverse_iterator rend() const noexcept;
87
88 const_iterator cbegin() const noexcept;
89 const_iterator cend() const noexcept;
90 const_reverse_iterator crbegin() const noexcept;
91 const_reverse_iterator crend() const noexcept;
92
93 // capacity:
94 size_type size() const noexcept;
95 size_type max_size() const noexcept;
96 void resize(size_type n);
97 void resize(size_type n, const value_type& v);
98 void shrink_to_fit();
99 bool empty() const noexcept;
100
101 // element access:
102 reference operator[](size_type i);
103 const_reference operator[](size_type i) const;
104 reference at(size_type i);
105 const_reference at(size_type i) const;
106 reference front();
107 const_reference front() const;
108 reference back();
109 const_reference back() const;
110
111 // modifiers:
112 void push_front(const value_type& v);
113 void push_front(value_type&& v);
114 template<container-compatible-range<T> R>
115 void prepend_range(R&& rg); // C++23
116 void push_back(const value_type& v);
117 void push_back(value_type&& v);
118 template<container-compatible-range<T> R>
119 void append_range(R&& rg); // C++23
120 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
121 template <class... Args> reference emplace_back(Args&&... args); // reference in C++17
122 template <class... Args> iterator emplace(const_iterator p, Args&&... args);
123 iterator insert(const_iterator p, const value_type& v);
124 iterator insert(const_iterator p, value_type&& v);
125 iterator insert(const_iterator p, size_type n, const value_type& v);
126 template <class InputIterator>
127 iterator insert(const_iterator p, InputIterator f, InputIterator l);
128 template<container-compatible-range<T> R>
129 iterator insert_range(const_iterator position, R&& rg); // C++23
130 iterator insert(const_iterator p, initializer_list<value_type> il);
131 void pop_front();
132 void pop_back();
133 iterator erase(const_iterator p);
134 iterator erase(const_iterator f, const_iterator l);
135 void swap(deque& c)
136 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
137 void clear() noexcept;
138 };
139
140 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
141 deque(InputIterator, InputIterator, Allocator = Allocator())
142 -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
143
144 template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
145 deque(from_range_t, R&&, Allocator = Allocator())
146 -> deque<ranges::range_value_t<R>, Allocator>; // C++23
147
148 template <class T, class Allocator>
149 bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
150 template <class T, class Allocator>
151 bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20
152 template <class T, class Allocator>
153 bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20
154 template <class T, class Allocator>
155 bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20
156 template <class T, class Allocator>
157 bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20
158 template <class T, class Allocator>
159 bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20
160 template<class T, class Allocator>
161 synth-three-way-result<T> operator<=>(const deque<T, Allocator>& x,
162 const deque<T, Allocator>& y); // since C++20
163
164 // specialized algorithms:
165 template <class T, class Allocator>
166 void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)
167 noexcept(noexcept(x.swap(y)));
168
169 template <class T, class Allocator, class U>
170 typename deque<T, Allocator>::size_type
171 erase(deque<T, Allocator>& c, const U& value); // C++20
172 template <class T, class Allocator, class Predicate>
173 typename deque<T, Allocator>::size_type
174 erase_if(deque<T, Allocator>& c, Predicate pred); // C++20
175
176 } // std
177
178 */
179
180 #include <__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 includes
220
221 // [iterator.range]
222 #include <__cxx03/__iterator/access.h>
223
224 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
225 # pragma GCC system_header
226 #endif
227
228 _LIBCPP_PUSH_MACROS
229 #include <__cxx03/__undef_macros>
230
231 _LIBCPP_BEGIN_NAMESPACE_STD
232
233 template <class _ValueType, class _DiffType>
234 struct __deque_block_size {
235 static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;
236 };
237
238 template <class _ValueType,
239 class _Pointer,
240 class _Reference,
241 class _MapPointer,
242 class _DiffType,
243 _DiffType _BS =
244 #ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
245 // Keep template parameter to avoid changing all template declarations thoughout
246 // this file.
247 0
248 #else
249 __deque_block_size<_ValueType, _DiffType>::value
250 #endif
251 >
252 class _LIBCPP_TEMPLATE_VIS __deque_iterator {
253 typedef _MapPointer __map_iterator;
254
255 public:
256 typedef _Pointer pointer;
257 typedef _DiffType difference_type;
258
259 private:
260 __map_iterator __m_iter_;
261 pointer __ptr_;
262
263 static const difference_type __block_size;
264
265 public:
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_ABI
274 __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it) _NOEXCEPT
275 : __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
378 private:
379 _LIBCPP_HIDE_FROM_ABI explicit __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
380 : __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
392 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, class _DiffType, _DiffType _BlockSize>
393 struct __segmented_iterator_traits<
394 __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize> > {
395 private:
396 using _Iterator = __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize>;
397
398 public:
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
420 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, class _DiffType, _DiffType _BlockSize>
421 const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize>::__block_size =
422 __deque_block_size<_ValueType, _DiffType>::value;
423
424 template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
425 class _LIBCPP_TEMPLATE_VIS deque {
426 public:
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 relocatable
462 // - size_type: is always trivially relocatable, since it is required to be an integral type
463 // - allocator_type: may not be trivially relocatable, so it's checked
464 // 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
477 private:
478 struct __deque_block_range {
479 explicit _LIBCPP_HIDE_FROM_ABI __deque_block_range(pointer __b, pointer __e) _NOEXCEPT
480 : __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
542 public:
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
725 private:
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_ASAN
743 // __beg - index of the first item to annotate
744 // __end - index behind the last item to annotate (so last item + 1)
745 // __annotation_type - __asan_unposion or __asan_poison
746 // __place - __asan_front_moved or __asan_back_moved
747 // Note: All indexes in __map_
748 if (__beg == __end)
749 return;
750 // __annotations_beg_map - first chunk which annotations we want to modify
751 // __annotations_end_map - last chunk which annotations we want to modify
752 // NOTE: if __end % __block_size == 0, __annotations_end_map points at the next block, which may not exist
753 __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 container
758 // __old_c_end_index - index of the end of old container (last + 1)
759 // Note: may be outside the area we are annotating
760 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 element
770 // __old_c_end_map - memory block (chunk) with end of old container
771 // Note: if __old_c_end_index % __block_size == 0, __old_c_end_map points at the next block,
772 // which may not exist
773 __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 edge
778 // __new_edge_map - memory block (chunk) with new edge, it always equals to
779 // __annotations_beg_map or __annotations_end_map
780 // __old_edge_map - memory block (chunk) with old edge, it always equals to
781 // __old_c_beg_map or __old_c_end_map
782 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 anyway
792 break;
793
794 // The beginning and the end of the current memory block
795 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 modification
799 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 modification
803 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 else
807 __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 block
812 // If the edge is in a different chunk it points on corresponding end of the memory block
813 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 else
817 __new_edge = (__poisoning ^ __front) ? __mem_beg : __mem_end;
818
819 // Not modified edge of the container
820 // If the edge is in a different chunk it points on corresponding end of the memory block
821 const void* __old_edge;
822 if (__map_it == __old_edge_map)
823 __old_edge = __front ? __old_end : __old_beg;
824 else
825 __old_edge = __front ? __mem_end : __mem_beg;
826
827 // __new_beg - the beginning of memory-in-use in the memory block after container modification
828 // __new_end - the end of memory-in-use in the memory block after container modification
829 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_ASAN
836 }
837
838 _LIBCPP_HIDE_FROM_ABI void __annotate_new(size_type __current_size) const _NOEXCEPT {
839 (void)__current_size;
840 #ifndef _LIBCPP_HAS_NO_ASAN
841 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 #endif
848 }
849
850 _LIBCPP_HIDE_FROM_ABI void __annotate_delete() const _NOEXCEPT {
851 #ifndef _LIBCPP_HAS_NO_ASAN
852 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 #endif
861 }
862
863 _LIBCPP_HIDE_FROM_ABI void __annotate_increase_front(size_type __n) const _NOEXCEPT {
864 (void)__n;
865 #ifndef _LIBCPP_HAS_NO_ASAN
866 __annotate_from_to(__start_ - __n, __start_, __asan_unposion, __asan_front_moved);
867 #endif
868 }
869
870 _LIBCPP_HIDE_FROM_ABI void __annotate_increase_back(size_type __n) const _NOEXCEPT {
871 (void)__n;
872 #ifndef _LIBCPP_HAS_NO_ASAN
873 __annotate_from_to(__start_ + size(), __start_ + size() + __n, __asan_unposion, __asan_back_moved);
874 #endif
875 }
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_ASAN
881 __annotate_from_to(__old_start, __old_start + (__old_size - size()), __asan_poison, __asan_front_moved);
882 #endif
883 }
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_ASAN
889 __annotate_from_to(__old_start + size(), __old_start + __old_size, __asan_poison, __asan_back_moved);
890 #endif
891 }
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 void
898 __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_ASAN
902 __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 #endif
913 }
914 #if !defined(_LIBCPP_HAS_NO_ASAN)
915
916 public:
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 elements
937 // Those can be in different deque blocks
938 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 annotations
944 // Note that __p_end points *behind* the last item.
945
946 // - blocks before the first block with container elements
947 // - first block with items
948 // - last block with items
949 // - blocks after last block with ciontainer elements
950
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
975 private:
976 #endif // _LIBCPP_VERIFY_ASAN_DEQUE_ANNOTATIONS
977 _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 iterator
1014 __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 iterator
1037 __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 void
1040 __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
1061 template <class _Tp, class _Alloc>
1062 const typename allocator_traits<_Alloc>::difference_type deque<_Tp, _Alloc>::__block_size =
1063 __deque_block_size<value_type, difference_type>::value;
1064
1065 template <class _Tp, class _Allocator>
1066 deque<_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
1072 template <class _Tp, class _Allocator>
1073 deque<_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
1079 template <class _Tp, class _Allocator>
1080 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
1081 deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l) : __start_(0), __size_(0, __default_init_tag()) {
1082 __annotate_new(0);
1083 __append(__f, __l);
1084 }
1085
1086 template <class _Tp, class _Allocator>
1087 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
1088 deque<_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
1094 template <class _Tp, class _Allocator>
1095 deque<_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
1103 template <class _Tp, class _Allocator>
1104 deque<_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
1110 template <class _Tp, class _Allocator>
1111 deque<_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
1119 template <class _Tp, class _Allocator>
1120 template <class _InputIter,
1121 __enable_if_t<__has_input_iterator_category<_InputIter>::value &&
1122 !__has_random_access_iterator_category<_InputIter>::value,
1123 int> >
1124 void deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l) {
1125 __assign_with_sentinel(__f, __l);
1126 }
1127
1128 template <class _Tp, class _Allocator>
1129 template <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 else
1138 __erase_to_end(__i);
1139 }
1140
1141 template <class _Tp, class _Allocator>
1142 template <class _RAIter, __enable_if_t<__has_random_access_iterator_category<_RAIter>::value, int> >
1143 void deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l) {
1144 __assign_with_size_random_access(__f, __l - __f);
1145 }
1146
1147 template <class _Tp, class _Allocator>
1148 template <class _RandomAccessIterator>
1149 _LIBCPP_HIDE_FROM_ABI void
1150 deque<_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 } else
1156 __erase_to_end(std::copy_n(__f, __n, begin()));
1157 }
1158
1159 template <class _Tp, class _Allocator>
1160 template <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
1177 template <class _Tp, class _Allocator>
1178 void 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 } else
1184 __erase_to_end(std::fill_n(begin(), __n, __v));
1185 }
1186
1187 template <class _Tp, class _Allocator>
1188 inline _Allocator deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT {
1189 return __alloc();
1190 }
1191
1192 template <class _Tp, class _Allocator>
1193 void 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
1200 template <class _Tp, class _Allocator>
1201 void 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
1208 template <class _Tp, class _Allocator>
1209 void 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
1225 template <class _Tp, class _Allocator>
1226 inline 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
1232 template <class _Tp, class _Allocator>
1233 inline typename deque<_Tp, _Allocator>::const_reference
1234 deque<_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
1240 template <class _Tp, class _Allocator>
1241 inline 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
1248 template <class _Tp, class _Allocator>
1249 inline 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
1256 template <class _Tp, class _Allocator>
1257 inline 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
1262 template <class _Tp, class _Allocator>
1263 inline 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
1268 template <class _Tp, class _Allocator>
1269 inline 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
1275 template <class _Tp, class _Allocator>
1276 inline 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
1282 template <class _Tp, class _Allocator>
1283 void 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() >= 1
1288 __annotate_increase_back(1);
1289 __alloc_traits::construct(__a, std::addressof(*end()), __v);
1290 ++__size();
1291 }
1292
1293 template <class _Tp, class _Allocator>
1294 void 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() >= 1
1299 __annotate_increase_front(1);
1300 __alloc_traits::construct(__a, std::addressof(*--begin()), __v);
1301 --__start_;
1302 ++__size();
1303 }
1304
1305 template <class _Tp, class _Allocator>
1306 typename 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 backward
1311 if (__front_spare() == 0)
1312 __add_front_capacity();
1313 // __front_spare() >= 1
1314 __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 forward
1333 if (__back_spare() == 0)
1334 __add_back_capacity();
1335 // __back_capacity >= 1
1336 __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
1357 template <class _Tp, class _Allocator>
1358 typename deque<_Tp, _Allocator>::iterator
1359 deque<_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 backward
1364 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 forward
1384 size_type __back_capacity = __back_spare();
1385 if (__n > __back_capacity)
1386 __add_back_capacity(__n - __back_capacity);
1387 // __n <= __back_capacity
1388 __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
1409 template <class _Tp, class _Allocator>
1410 template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> >
1411 typename deque<_Tp, _Allocator>::iterator
1412 deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l) {
1413 return __insert_with_sentinel(__p, __f, __l);
1414 }
1415
1416 template <class _Tp, class _Allocator>
1417 template <class _Iterator, class _Sentinel>
1418 _LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator
1419 deque<_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
1426 template <class _Tp, class _Allocator>
1427 template <class _ForwardIterator, __enable_if_t<__has_exactly_forward_iterator_category<_ForwardIterator>::value, int> >
1428 typename deque<_Tp, _Allocator>::iterator
1429 deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l) {
1430 return __insert_with_size(__p, __f, std::distance(__f, __l));
1431 }
1432
1433 template <class _Tp, class _Allocator>
1434 template <class _Iterator>
1435 _LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator
1436 deque<_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
1443 template <class _Tp, class _Allocator>
1444 template <class _BiIter, __enable_if_t<__has_bidirectional_iterator_category<_BiIter>::value, int> >
1445 typename 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
1449 template <class _Tp, class _Allocator>
1450 template <class _BiIter, class _Sentinel>
1451 _LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator
1452 deque<_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
1456 template <class _Tp, class _Allocator>
1457 template <class _BiIter>
1458 _LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator
1459 deque<_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 backward
1464 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 forward
1489 size_type __back_capacity = __back_spare();
1490 if (__n > __back_capacity)
1491 __add_back_capacity(__n - __back_capacity);
1492 // __n <= __back_capacity
1493 __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
1516 template <class _Tp, class _Allocator>
1517 template <class _InpIter, __enable_if_t<__has_exactly_input_iterator_category<_InpIter>::value, int> >
1518 void deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l) {
1519 __append_with_sentinel(__f, __l);
1520 }
1521
1522 template <class _Tp, class _Allocator>
1523 template <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
1529 template <class _Tp, class _Allocator>
1530 template <class _ForIter, __enable_if_t<__has_forward_iterator_category<_ForIter>::value, int> >
1531 void deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l) {
1532 __append_with_size(__f, std::distance(__f, __l));
1533 }
1534
1535 template <class _Tp, class _Allocator>
1536 template <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_capacity
1544 __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
1553 template <class _Tp, class _Allocator>
1554 void 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_capacity
1560 __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
1569 template <class _Tp, class _Allocator>
1570 void 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_capacity
1576 __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.
1587 template <class _Tp, class _Allocator>
1588 void 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 buffer
1597 else if (__map_.size() < __map_.capacity()) { // we can put the new buffer into the map, but don't shift things around
1598 // until all buffers are allocated. If we throw, we don't need to fix
1599 // 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 capacity
1605 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.
1634 template <class _Tp, class _Allocator>
1635 void 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 need
1641 __nb -= __back_capacity; // number of blocks need to allocate
1642 // 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 buffers
1652 else if (__nb <= __map_.capacity() -
1653 __map_.size()) { // we can put the new buffers into the map, but don't shift things around
1654 // until all buffers are allocated. If we throw, we don't need to fix
1655 // 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 capacity
1665 __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_EXCEPTIONS
1679 try {
1680 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1681 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 block
1684 __annotate_poison_block(std::__to_address(__buf.back()), std::__to_address(__buf.back() + __block_size));
1685 }
1686 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1687 } 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_EXCEPTIONS
1694 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.
1710 template <class _Tp, class _Allocator>
1711 void 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 buffers
1720 else if (__map_.size() < __map_.capacity()) { // we can put the new buffer into the map, but don't shift things around
1721 // until it is allocated. If we throw, we don't need to fix
1722 // 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 capacity
1728 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.
1756 template <class _Tp, class _Allocator>
1757 void 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 need
1763 __nb -= __front_capacity; // number of blocks need to allocate
1764 // 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 buffers
1774 else if (__nb <= __map_.capacity() -
1775 __map_.size()) { // we can put the new buffers into the map, but don't shift things around
1776 // until all buffers are allocated. If we throw, we don't need to fix
1777 // 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 capacity
1789 __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_EXCEPTIONS
1804 try {
1805 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1806 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 block
1809 __annotate_poison_block(std::__to_address(__buf.back()), std::__to_address(__buf.back() + __block_size));
1810 }
1811 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1812 } 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_EXCEPTIONS
1819 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
1833 template <class _Tp, class _Allocator>
1834 void 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
1847 template <class _Tp, class _Allocator>
1848 void 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.
1862 template <class _Tp, class _Allocator>
1863 typename deque<_Tp, _Allocator>::iterator
1864 deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) {
1865 // as if
1866 // 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.
1888 template <class _Tp, class _Allocator>
1889 typename deque<_Tp, _Allocator>::iterator
1890 deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) {
1891 // as if
1892 // 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.
1915 template <class _Tp, class _Allocator>
1916 void deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, iterator __r, const_pointer& __vt) {
1917 allocator_type& __a = __alloc();
1918 // as if
1919 // 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.
1941 template <class _Tp, class _Allocator>
1942 void 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 if
1946 // 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
1974 template <class _Tp, class _Allocator>
1975 typename 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 front
1985 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 back
1992 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
2001 template <class _Tp, class _Allocator>
2002 typename 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 front
2013 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 back
2022 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
2034 template <class _Tp, class _Allocator>
2035 void 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
2053 template <class _Tp, class _Allocator>
2054 inline 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
2061 template <class _Tp, class _Allocator>
2062 inline 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
2083 template <class _Tp, class _Allocator>
2084 inline _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
2089 template <class _Tp, class _Allocator>
2090 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {
2091 return !(__x == __y);
2092 }
2093
2094 template <class _Tp, class _Allocator>
2095 inline _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
2099 template <class _Tp, class _Allocator>
2100 inline _LIBCPP_HIDE_FROM_ABI bool operator>(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {
2101 return __y < __x;
2102 }
2103
2104 template <class _Tp, class _Allocator>
2105 inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {
2106 return !(__x < __y);
2107 }
2108
2109 template <class _Tp, class _Allocator>
2110 inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) {
2111 return !(__y < __x);
2112 }
2113
2114 template <class _Tp, class _Allocator>
2115 inline _LIBCPP_HIDE_FROM_ABI void swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) {
2116 __x.swap(__y);
2117 }
2118
2119 _LIBCPP_END_NAMESPACE_STD
2120
2121 _LIBCPP_POP_MACROS
2122
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 #endif
2133
2134 #endif // _LIBCPP___CXX03_DEQUE