Line data Source code
1 : // -*- C++ -*-
2 : //===----------------------------------------------------------------------===//
3 : //
4 : // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 : // See https://llvm.org/LICENSE.txt for license information.
6 : // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
10 : #ifndef _LIBCPP_DEQUE
11 : #define _LIBCPP_DEQUE
12 :
13 : /*
14 : deque synopsis
15 :
16 : namespace std
17 : {
18 :
19 : template <class T, class Allocator = allocator<T> >
20 : class deque
21 : {
22 : public:
23 : // types:
24 : typedef T value_type;
25 : typedef Allocator allocator_type;
26 :
27 : typedef typename allocator_type::reference reference;
28 : typedef typename allocator_type::const_reference const_reference;
29 : typedef implementation-defined iterator;
30 : typedef implementation-defined const_iterator;
31 : typedef typename allocator_type::size_type size_type;
32 : typedef typename allocator_type::difference_type difference_type;
33 :
34 : typedef typename allocator_type::pointer pointer;
35 : typedef typename allocator_type::const_pointer const_pointer;
36 : typedef std::reverse_iterator<iterator> reverse_iterator;
37 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
38 :
39 : // construct/copy/destroy:
40 : deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);
41 : explicit deque(const allocator_type& a);
42 : explicit deque(size_type n);
43 : explicit deque(size_type n, const allocator_type& a); // C++14
44 : deque(size_type n, const value_type& v);
45 : deque(size_type n, const value_type& v, const allocator_type& a);
46 : template <class InputIterator>
47 : deque(InputIterator f, InputIterator l);
48 : template <class InputIterator>
49 : deque(InputIterator f, InputIterator l, const allocator_type& a);
50 : deque(const deque& c);
51 : deque(deque&& c)
52 : noexcept(is_nothrow_move_constructible<allocator_type>::value);
53 : deque(initializer_list<value_type> il, const Allocator& a = allocator_type());
54 : deque(const deque& c, const allocator_type& a);
55 : deque(deque&& c, const allocator_type& a);
56 : ~deque();
57 :
58 : deque& operator=(const deque& c);
59 : deque& operator=(deque&& c)
60 : noexcept(
61 : allocator_type::propagate_on_container_move_assignment::value &&
62 : is_nothrow_move_assignable<allocator_type>::value);
63 : deque& operator=(initializer_list<value_type> il);
64 :
65 : template <class InputIterator>
66 : void assign(InputIterator f, InputIterator l);
67 : void assign(size_type n, const value_type& v);
68 : void assign(initializer_list<value_type> il);
69 :
70 : allocator_type get_allocator() const noexcept;
71 :
72 : // iterators:
73 :
74 : iterator begin() noexcept;
75 : const_iterator begin() const noexcept;
76 : iterator end() noexcept;
77 : const_iterator end() const noexcept;
78 :
79 : reverse_iterator rbegin() noexcept;
80 : const_reverse_iterator rbegin() const noexcept;
81 : reverse_iterator rend() noexcept;
82 : const_reverse_iterator rend() const noexcept;
83 :
84 : const_iterator cbegin() const noexcept;
85 : const_iterator cend() const noexcept;
86 : const_reverse_iterator crbegin() const noexcept;
87 : const_reverse_iterator crend() const noexcept;
88 :
89 : // capacity:
90 : size_type size() const noexcept;
91 : size_type max_size() const noexcept;
92 : void resize(size_type n);
93 : void resize(size_type n, const value_type& v);
94 : void shrink_to_fit();
95 : bool empty() const noexcept;
96 :
97 : // element access:
98 : reference operator[](size_type i);
99 : const_reference operator[](size_type i) const;
100 : reference at(size_type i);
101 : const_reference at(size_type i) const;
102 : reference front();
103 : const_reference front() const;
104 : reference back();
105 : const_reference back() const;
106 :
107 : // modifiers:
108 : void push_front(const value_type& v);
109 : void push_front(value_type&& v);
110 : void push_back(const value_type& v);
111 : void push_back(value_type&& v);
112 : template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
113 : template <class... Args> reference emplace_back(Args&&... args); // reference in C++17
114 : template <class... Args> iterator emplace(const_iterator p, Args&&... args);
115 : iterator insert(const_iterator p, const value_type& v);
116 : iterator insert(const_iterator p, value_type&& v);
117 : iterator insert(const_iterator p, size_type n, const value_type& v);
118 : template <class InputIterator>
119 : iterator insert(const_iterator p, InputIterator f, InputIterator l);
120 : iterator insert(const_iterator p, initializer_list<value_type> il);
121 : void pop_front();
122 : void pop_back();
123 : iterator erase(const_iterator p);
124 : iterator erase(const_iterator f, const_iterator l);
125 : void swap(deque& c)
126 : noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
127 : void clear() noexcept;
128 : };
129 :
130 : template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
131 : deque(InputIterator, InputIterator, Allocator = Allocator())
132 : -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
133 :
134 : template <class T, class Allocator>
135 : bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
136 : template <class T, class Allocator>
137 : bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
138 : template <class T, class Allocator>
139 : bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
140 : template <class T, class Allocator>
141 : bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
142 : template <class T, class Allocator>
143 : bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
144 : template <class T, class Allocator>
145 : bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
146 :
147 : // specialized algorithms:
148 : template <class T, class Allocator>
149 : void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)
150 : noexcept(noexcept(x.swap(y)));
151 :
152 : template <class T, class Allocator, class U>
153 : typename deque<T, Allocator>::size_type
154 : erase(deque<T, Allocator>& c, const U& value); // C++20
155 : template <class T, class Allocator, class Predicate>
156 : typename deque<T, Allocator>::size_type
157 : erase_if(deque<T, Allocator>& c, Predicate pred); // C++20
158 :
159 : } // std
160 :
161 : */
162 :
163 : #include <__algorithm/copy.h>
164 : #include <__algorithm/copy_backward.h>
165 : #include <__algorithm/equal.h>
166 : #include <__algorithm/fill_n.h>
167 : #include <__algorithm/lexicographical_compare.h>
168 : #include <__algorithm/min.h>
169 : #include <__algorithm/remove.h>
170 : #include <__algorithm/remove_if.h>
171 : #include <__algorithm/unwrap_iter.h>
172 : #include <__assert> // all public C++ headers provide the assertion handler
173 : #include <__config>
174 : #include <__format/enable_insertable.h>
175 : #include <__iterator/iterator_traits.h>
176 : #include <__iterator/next.h>
177 : #include <__iterator/prev.h>
178 : #include <__iterator/reverse_iterator.h>
179 : #include <__iterator/segmented_iterator.h>
180 : #include <__memory/allocator_destructor.h>
181 : #include <__memory/pointer_traits.h>
182 : #include <__memory/temp_value.h>
183 : #include <__memory/unique_ptr.h>
184 : #include <__memory_resource/polymorphic_allocator.h>
185 : #include <__split_buffer>
186 : #include <__type_traits/is_allocator.h>
187 : #include <__utility/forward.h>
188 : #include <__utility/move.h>
189 : #include <__utility/swap.h>
190 : #include <limits>
191 : #include <stdexcept>
192 : #include <type_traits>
193 : #include <version>
194 :
195 : // standard-mandated includes
196 :
197 : // [iterator.range]
198 : #include <__iterator/access.h>
199 : #include <__iterator/data.h>
200 : #include <__iterator/empty.h>
201 : #include <__iterator/reverse_access.h>
202 : #include <__iterator/size.h>
203 :
204 : // [deque.syn]
205 : #include <compare>
206 : #include <initializer_list>
207 :
208 : #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
209 : # pragma GCC system_header
210 : #endif
211 :
212 : _LIBCPP_PUSH_MACROS
213 : #include <__undef_macros>
214 :
215 :
216 : _LIBCPP_BEGIN_NAMESPACE_STD
217 :
218 : template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS deque;
219 :
220 : template <class _ValueType, class _DiffType>
221 : struct __deque_block_size {
222 : static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;
223 : };
224 :
225 : template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
226 : class _DiffType, _DiffType _BS =
227 : #ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
228 : // Keep template parameter to avoid changing all template declarations thoughout
229 : // this file.
230 : 0
231 : #else
232 : __deque_block_size<_ValueType, _DiffType>::value
233 : #endif
234 : >
235 : class _LIBCPP_TEMPLATE_VIS __deque_iterator
236 : {
237 : typedef _MapPointer __map_iterator;
238 : public:
239 : typedef _Pointer pointer;
240 : typedef _DiffType difference_type;
241 : private:
242 : __map_iterator __m_iter_;
243 : pointer __ptr_;
244 :
245 : static const difference_type __block_size;
246 : public:
247 : typedef _ValueType value_type;
248 : typedef random_access_iterator_tag iterator_category;
249 : typedef _Reference reference;
250 :
251 : _LIBCPP_HIDE_FROM_ABI __deque_iterator() _NOEXCEPT
252 : #if _LIBCPP_STD_VER > 11
253 : : __m_iter_(nullptr), __ptr_(nullptr)
254 : #endif
255 : {}
256 :
257 : template <class _Pp, class _Rp, class _MP>
258 : _LIBCPP_HIDE_FROM_ABI
259 : __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it,
260 : typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT
261 : : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}
262 :
263 56 : _LIBCPP_HIDE_FROM_ABI reference operator*() const {return *__ptr_;}
264 : _LIBCPP_HIDE_FROM_ABI pointer operator->() const {return __ptr_;}
265 :
266 : _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator++()
267 : {
268 : if (++__ptr_ - *__m_iter_ == __block_size)
269 : {
270 : ++__m_iter_;
271 : __ptr_ = *__m_iter_;
272 : }
273 : return *this;
274 : }
275 :
276 : _LIBCPP_HIDE_FROM_ABI __deque_iterator operator++(int)
277 : {
278 : __deque_iterator __tmp = *this;
279 : ++(*this);
280 : return __tmp;
281 : }
282 :
283 : _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator--()
284 : {
285 : if (__ptr_ == *__m_iter_)
286 : {
287 : --__m_iter_;
288 : __ptr_ = *__m_iter_ + __block_size;
289 : }
290 : --__ptr_;
291 : return *this;
292 : }
293 :
294 : _LIBCPP_HIDE_FROM_ABI __deque_iterator operator--(int)
295 : {
296 : __deque_iterator __tmp = *this;
297 : --(*this);
298 : return __tmp;
299 : }
300 :
301 : _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator+=(difference_type __n)
302 : {
303 : if (__n != 0)
304 : {
305 : __n += __ptr_ - *__m_iter_;
306 : if (__n > 0)
307 : {
308 : __m_iter_ += __n / __block_size;
309 : __ptr_ = *__m_iter_ + __n % __block_size;
310 : }
311 : else // (__n < 0)
312 : {
313 : difference_type __z = __block_size - 1 - __n;
314 : __m_iter_ -= __z / __block_size;
315 : __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);
316 : }
317 : }
318 : return *this;
319 : }
320 :
321 : _LIBCPP_HIDE_FROM_ABI __deque_iterator& operator-=(difference_type __n)
322 : {
323 : return *this += -__n;
324 : }
325 :
326 : _LIBCPP_HIDE_FROM_ABI __deque_iterator operator+(difference_type __n) const
327 : {
328 : __deque_iterator __t(*this);
329 : __t += __n;
330 : return __t;
331 : }
332 :
333 : _LIBCPP_HIDE_FROM_ABI __deque_iterator operator-(difference_type __n) const
334 : {
335 : __deque_iterator __t(*this);
336 : __t -= __n;
337 : return __t;
338 : }
339 :
340 : _LIBCPP_HIDE_FROM_ABI
341 : friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it)
342 : {return __it + __n;}
343 :
344 : _LIBCPP_HIDE_FROM_ABI
345 : friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y)
346 : {
347 : if (__x != __y)
348 : return (__x.__m_iter_ - __y.__m_iter_) * __block_size
349 : + (__x.__ptr_ - *__x.__m_iter_)
350 : - (__y.__ptr_ - *__y.__m_iter_);
351 : return 0;
352 : }
353 :
354 : _LIBCPP_HIDE_FROM_ABI reference operator[](difference_type __n) const
355 : {return *(*this + __n);}
356 :
357 : _LIBCPP_HIDE_FROM_ABI friend
358 : bool operator==(const __deque_iterator& __x, const __deque_iterator& __y)
359 : {return __x.__ptr_ == __y.__ptr_;}
360 :
361 : _LIBCPP_HIDE_FROM_ABI friend
362 : bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y)
363 : {return !(__x == __y);}
364 :
365 : _LIBCPP_HIDE_FROM_ABI friend
366 : bool operator<(const __deque_iterator& __x, const __deque_iterator& __y)
367 : {return __x.__m_iter_ < __y.__m_iter_ ||
368 : (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);}
369 :
370 : _LIBCPP_HIDE_FROM_ABI friend
371 : bool operator>(const __deque_iterator& __x, const __deque_iterator& __y)
372 : {return __y < __x;}
373 :
374 : _LIBCPP_HIDE_FROM_ABI friend
375 : bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y)
376 : {return !(__y < __x);}
377 :
378 : _LIBCPP_HIDE_FROM_ABI friend
379 : bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)
380 : {return !(__x < __y);}
381 :
382 : private:
383 112 : _LIBCPP_HIDE_FROM_ABI explicit __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
384 112 : : __m_iter_(__m), __ptr_(__p) {}
385 :
386 : template <class _Tp, class _Ap> friend class _LIBCPP_TEMPLATE_VIS deque;
387 : template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>
388 : friend class _LIBCPP_TEMPLATE_VIS __deque_iterator;
389 :
390 : template <class>
391 : friend struct __segmented_iterator_traits;
392 : };
393 :
394 : template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, class _DiffType, _DiffType _BlockSize>
395 : struct __segmented_iterator_traits<
396 : __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize> > {
397 : private:
398 : using _Iterator = __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize>;
399 :
400 : public:
401 : using __is_segmented_iterator = true_type;
402 : using __segment_iterator = _MapPointer;
403 : using __local_iterator = _Pointer;
404 :
405 : static _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_Iterator __iter) { return __iter.__m_iter_; }
406 : static _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_Iterator __iter) { return __iter.__ptr_; }
407 : static _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) { return *__iter; }
408 :
409 : static _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {
410 : return *__iter + _Iterator::__block_size;
411 : }
412 :
413 : static _LIBCPP_HIDE_FROM_ABI _Iterator __compose(__segment_iterator __segment, __local_iterator __local) {
414 : if (__local == __end(__segment)) {
415 : ++__segment;
416 : return _Iterator(__segment, *__segment);
417 : }
418 : return _Iterator(__segment, __local);
419 : }
420 : };
421 :
422 : template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
423 : class _DiffType, _DiffType _BlockSize>
424 : const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
425 : _DiffType, _BlockSize>::__block_size =
426 : __deque_block_size<_ValueType, _DiffType>::value;
427 :
428 : template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
429 : class _LIBCPP_TEMPLATE_VIS deque
430 : {
431 : public:
432 : // types:
433 :
434 : using value_type = _Tp;
435 :
436 : static_assert((is_same<typename _Allocator::value_type, value_type>::value),
437 : "Allocator::value_type must be same type as value_type");
438 :
439 : using allocator_type = _Allocator;
440 : using __alloc_traits = allocator_traits<allocator_type>;
441 :
442 : using size_type = typename __alloc_traits::size_type;
443 : using difference_type = typename __alloc_traits::difference_type;
444 :
445 : using pointer = typename __alloc_traits::pointer;
446 : using const_pointer = typename __alloc_traits::const_pointer;
447 :
448 : using __pointer_allocator = __rebind_alloc<__alloc_traits, pointer>;
449 : using __const_pointer_allocator = __rebind_alloc<__alloc_traits, const_pointer>;
450 : using __map = __split_buffer<pointer, __pointer_allocator>;
451 : using __map_alloc_traits = allocator_traits<__pointer_allocator>;
452 : using __map_pointer = typename __map_alloc_traits::pointer;
453 : using __map_const_pointer = typename allocator_traits<__const_pointer_allocator>::const_pointer;
454 :
455 : using reference = value_type&;
456 : using const_reference = const value_type&;
457 :
458 : using iterator = __deque_iterator<value_type, pointer, reference, __map_pointer, difference_type>;
459 : using const_iterator =
460 : __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer, difference_type>;
461 : using reverse_iterator = std::reverse_iterator<iterator>;
462 : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
463 :
464 : static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
465 : "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
466 : "original allocator");
467 : static_assert(is_nothrow_default_constructible<allocator_type>::value ==
468 : is_nothrow_default_constructible<__pointer_allocator>::value,
469 : "rebinding an allocator should not change excpetion guarantees");
470 : static_assert(is_nothrow_move_constructible<allocator_type>::value ==
471 : is_nothrow_move_constructible<typename __map::allocator_type>::value,
472 : "rebinding an allocator should not change excpetion guarantees");
473 :
474 : private:
475 : struct __deque_block_range {
476 : explicit _LIBCPP_HIDE_FROM_ABI
477 : __deque_block_range(pointer __b, pointer __e) _NOEXCEPT : __begin_(__b), __end_(__e) {}
478 : const pointer __begin_;
479 : const pointer __end_;
480 : };
481 :
482 : struct __deque_range {
483 : iterator __pos_;
484 : const iterator __end_;
485 :
486 : _LIBCPP_HIDE_FROM_ABI __deque_range(iterator __pos, iterator __e) _NOEXCEPT
487 : : __pos_(__pos), __end_(__e) {}
488 :
489 : explicit _LIBCPP_HIDE_FROM_ABI operator bool() const _NOEXCEPT {
490 : return __pos_ != __end_;
491 : }
492 :
493 : _LIBCPP_HIDE_FROM_ABI __deque_range begin() const {
494 : return *this;
495 : }
496 :
497 : _LIBCPP_HIDE_FROM_ABI __deque_range end() const {
498 : return __deque_range(__end_, __end_);
499 : }
500 : _LIBCPP_HIDE_FROM_ABI __deque_block_range operator*() const _NOEXCEPT {
501 : if (__pos_.__m_iter_ == __end_.__m_iter_) {
502 : return __deque_block_range(__pos_.__ptr_, __end_.__ptr_);
503 : }
504 : return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size);
505 : }
506 :
507 : _LIBCPP_HIDE_FROM_ABI __deque_range& operator++() _NOEXCEPT {
508 : if (__pos_.__m_iter_ == __end_.__m_iter_) {
509 : __pos_ = __end_;
510 : } else {
511 : ++__pos_.__m_iter_;
512 : __pos_.__ptr_ = *__pos_.__m_iter_;
513 : }
514 : return *this;
515 : }
516 :
517 :
518 : _LIBCPP_HIDE_FROM_ABI friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) {
519 : return __lhs.__pos_ == __rhs.__pos_;
520 : }
521 : _LIBCPP_HIDE_FROM_ABI friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) {
522 : return !(__lhs == __rhs);
523 : }
524 : };
525 :
526 : struct _ConstructTransaction {
527 : _LIBCPP_HIDE_FROM_ABI _ConstructTransaction(deque* __db, __deque_block_range& __r)
528 : : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {}
529 :
530 :
531 : _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() {
532 : __base_->__size() += (__pos_ - __begin_);
533 : }
534 :
535 : pointer __pos_;
536 : const pointer __end_;
537 : private:
538 : const pointer __begin_;
539 : deque* const __base_;
540 : };
541 :
542 : static const difference_type __block_size;
543 :
544 : __map __map_;
545 : size_type __start_;
546 : __compressed_pair<size_type, allocator_type> __size_;
547 :
548 : public:
549 :
550 : // construct/copy/destroy:
551 : _LIBCPP_HIDE_FROM_ABI
552 6 : deque() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
553 6 : : __start_(0), __size_(0, __default_init_tag()) {}
554 :
555 : _LIBCPP_HIDE_FROM_ABI ~deque() {
556 : clear();
557 : typename __map::iterator __i = __map_.begin();
558 : typename __map::iterator __e = __map_.end();
559 : for (; __i != __e; ++__i)
560 : __alloc_traits::deallocate(__alloc(), *__i, __block_size);
561 : }
562 :
563 : _LIBCPP_HIDE_FROM_ABI explicit deque(const allocator_type& __a)
564 : : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}
565 :
566 : explicit _LIBCPP_HIDE_FROM_ABI deque(size_type __n);
567 : #if _LIBCPP_STD_VER > 11
568 : explicit _LIBCPP_HIDE_FROM_ABI deque(size_type __n, const _Allocator& __a);
569 : #endif
570 : _LIBCPP_HIDE_FROM_ABI deque(size_type __n, const value_type& __v);
571 :
572 : template <class = __enable_if_t<__is_allocator<_Allocator>::value> >
573 : _LIBCPP_HIDE_FROM_ABI deque(size_type __n, const value_type& __v, const allocator_type& __a)
574 : : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
575 : {
576 : if (__n > 0)
577 : __append(__n, __v);
578 : }
579 :
580 : template <class _InputIter>
581 : _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l,
582 : typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
583 : template <class _InputIter>
584 : _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
585 : typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
586 : _LIBCPP_HIDE_FROM_ABI deque(const deque& __c);
587 : _LIBCPP_HIDE_FROM_ABI deque(const deque& __c, const __type_identity_t<allocator_type>& __a);
588 :
589 : _LIBCPP_HIDE_FROM_ABI deque& operator=(const deque& __c);
590 :
591 : #ifndef _LIBCPP_CXX03_LANG
592 : _LIBCPP_HIDE_FROM_ABI deque(initializer_list<value_type> __il);
593 : _LIBCPP_HIDE_FROM_ABI deque(initializer_list<value_type> __il, const allocator_type& __a);
594 :
595 : _LIBCPP_HIDE_FROM_ABI
596 : deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
597 :
598 : _LIBCPP_HIDE_FROM_ABI
599 : deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
600 : _LIBCPP_HIDE_FROM_ABI
601 : deque(deque&& __c, const __type_identity_t<allocator_type>& __a);
602 : _LIBCPP_HIDE_FROM_ABI
603 : deque& operator=(deque&& __c)
604 : _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
605 : is_nothrow_move_assignable<allocator_type>::value);
606 :
607 : _LIBCPP_HIDE_FROM_ABI
608 : void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
609 : #endif // _LIBCPP_CXX03_LANG
610 :
611 : template <class _InputIter>
612 : _LIBCPP_HIDE_FROM_ABI void assign(_InputIter __f, _InputIter __l,
613 : typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
614 : !__is_cpp17_random_access_iterator<_InputIter>::value>::type* = 0);
615 : template <class _RAIter>
616 : _LIBCPP_HIDE_FROM_ABI void assign(_RAIter __f, _RAIter __l,
617 : typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
618 : _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);
619 :
620 : _LIBCPP_HIDE_FROM_ABI
621 : allocator_type get_allocator() const _NOEXCEPT;
622 115 : _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __size_.second(); }
623 : _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __size_.second(); }
624 :
625 : // iterators:
626 :
627 : _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT {
628 : __map_pointer __mp = __map_.begin() + __start_ / __block_size;
629 : return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
630 : }
631 :
632 : _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {
633 : __map_const_pointer __mp =
634 : static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);
635 : return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
636 : }
637 :
638 56 : _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT {
639 56 : size_type __p = size() + __start_;
640 56 : __map_pointer __mp = __map_.begin() + __p / __block_size;
641 56 : return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
642 0 : }
643 :
644 : _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT {
645 : size_type __p = size() + __start_;
646 : __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);
647 : return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
648 : }
649 :
650 : _LIBCPP_HIDE_FROM_ABI
651 : reverse_iterator rbegin() _NOEXCEPT
652 : {return reverse_iterator(end());}
653 : _LIBCPP_HIDE_FROM_ABI
654 : const_reverse_iterator rbegin() const _NOEXCEPT
655 : {return const_reverse_iterator(end());}
656 : _LIBCPP_HIDE_FROM_ABI
657 : reverse_iterator rend() _NOEXCEPT
658 : {return reverse_iterator(begin());}
659 : _LIBCPP_HIDE_FROM_ABI
660 : const_reverse_iterator rend() const _NOEXCEPT
661 : {return const_reverse_iterator(begin());}
662 :
663 : _LIBCPP_HIDE_FROM_ABI
664 : const_iterator cbegin() const _NOEXCEPT
665 : {return begin();}
666 : _LIBCPP_HIDE_FROM_ABI
667 : const_iterator cend() const _NOEXCEPT
668 : {return end();}
669 : _LIBCPP_HIDE_FROM_ABI
670 : const_reverse_iterator crbegin() const _NOEXCEPT
671 : {return const_reverse_iterator(end());}
672 : _LIBCPP_HIDE_FROM_ABI
673 : const_reverse_iterator crend() const _NOEXCEPT
674 : {return const_reverse_iterator(begin());}
675 :
676 : // capacity:
677 : _LIBCPP_HIDE_FROM_ABI
678 733 : size_type size() const _NOEXCEPT {return __size();}
679 :
680 112 : _LIBCPP_HIDE_FROM_ABI size_type& __size() _NOEXCEPT { return __size_.first(); }
681 733 : _LIBCPP_HIDE_FROM_ABI const size_type& __size() const _NOEXCEPT { return __size_.first(); }
682 :
683 : _LIBCPP_HIDE_FROM_ABI
684 : size_type max_size() const _NOEXCEPT
685 : {return _VSTD::min<size_type>(
686 : __alloc_traits::max_size(__alloc()),
687 : numeric_limits<difference_type>::max());}
688 : _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
689 : _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v);
690 : _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;
691 : _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI
692 : bool empty() const _NOEXCEPT {return size() == 0;}
693 :
694 : // element access:
695 : _LIBCPP_HIDE_FROM_ABI
696 : reference operator[](size_type __i) _NOEXCEPT;
697 : _LIBCPP_HIDE_FROM_ABI
698 : const_reference operator[](size_type __i) const _NOEXCEPT;
699 : _LIBCPP_HIDE_FROM_ABI
700 : reference at(size_type __i);
701 : _LIBCPP_HIDE_FROM_ABI
702 : const_reference at(size_type __i) const;
703 : _LIBCPP_HIDE_FROM_ABI
704 : reference front() _NOEXCEPT;
705 : _LIBCPP_HIDE_FROM_ABI
706 : const_reference front() const _NOEXCEPT;
707 : _LIBCPP_HIDE_FROM_ABI
708 : reference back() _NOEXCEPT;
709 : _LIBCPP_HIDE_FROM_ABI
710 : const_reference back() const _NOEXCEPT;
711 :
712 : // 23.2.2.3 modifiers:
713 : _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);
714 : _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __v);
715 : #ifndef _LIBCPP_CXX03_LANG
716 : #if _LIBCPP_STD_VER > 14
717 : template <class... _Args> _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
718 : template <class... _Args> _LIBCPP_HIDE_FROM_ABI reference emplace_back (_Args&&... __args);
719 : #else
720 : template <class... _Args> _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
721 : template <class... _Args> _LIBCPP_HIDE_FROM_ABI void emplace_back (_Args&&... __args);
722 : #endif
723 : template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args);
724 :
725 : _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v);
726 : _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __v);
727 : _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v);
728 :
729 : _LIBCPP_HIDE_FROM_ABI
730 : iterator insert(const_iterator __p, initializer_list<value_type> __il)
731 : {return insert(__p, __il.begin(), __il.end());}
732 : #endif // _LIBCPP_CXX03_LANG
733 : _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v);
734 : _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __v);
735 : template <class _InputIter>
736 : _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
737 : typename enable_if<__is_exactly_cpp17_input_iterator<_InputIter>::value>::type* = 0);
738 : template <class _ForwardIterator>
739 : _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
740 : typename enable_if<__is_exactly_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
741 : template <class _BiIter>
742 : _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
743 : typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type* = 0);
744 :
745 : _LIBCPP_HIDE_FROM_ABI void pop_front();
746 : _LIBCPP_HIDE_FROM_ABI void pop_back();
747 : _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
748 : _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);
749 :
750 : _LIBCPP_HIDE_FROM_ABI
751 : void swap(deque& __c)
752 : #if _LIBCPP_STD_VER >= 14
753 : _NOEXCEPT;
754 : #else
755 : _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
756 : __is_nothrow_swappable<allocator_type>::value);
757 : #endif
758 : _LIBCPP_HIDE_FROM_ABI
759 : void clear() _NOEXCEPT;
760 :
761 : _LIBCPP_HIDE_FROM_ABI
762 : bool __invariants() const {
763 : if (!__map_.__invariants())
764 : return false;
765 : if (__map_.size() >= size_type(-1) / __block_size)
766 : return false;
767 : for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();
768 : __i != __e; ++__i)
769 : if (*__i == nullptr)
770 : return false;
771 : if (__map_.size() != 0)
772 : {
773 : if (size() >= __map_.size() * __block_size)
774 : return false;
775 : if (__start_ >= __map_.size() * __block_size - size())
776 : return false;
777 : }
778 : else
779 : {
780 : if (size() != 0)
781 : return false;
782 : if (__start_ != 0)
783 : return false;
784 : }
785 : return true;
786 : }
787 :
788 : _LIBCPP_HIDE_FROM_ABI
789 : void __move_assign_alloc(deque& __c)
790 : _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
791 : is_nothrow_move_assignable<allocator_type>::value)
792 : {__move_assign_alloc(__c, integral_constant<bool,
793 : __alloc_traits::propagate_on_container_move_assignment::value>());}
794 :
795 : _LIBCPP_HIDE_FROM_ABI
796 : void __move_assign_alloc(deque& __c, true_type)
797 : _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
798 : {
799 : __alloc() = _VSTD::move(__c.__alloc());
800 : }
801 :
802 : _LIBCPP_HIDE_FROM_ABI
803 : void __move_assign_alloc(deque&, false_type) _NOEXCEPT
804 : {}
805 :
806 : _LIBCPP_HIDE_FROM_ABI
807 : void __move_assign(deque& __c)
808 : _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
809 : is_nothrow_move_assignable<allocator_type>::value)
810 : {
811 : __map_ = _VSTD::move(__c.__map_);
812 : __start_ = __c.__start_;
813 : __size() = __c.size();
814 : __move_assign_alloc(__c);
815 : __c.__start_ = __c.__size() = 0;
816 : }
817 :
818 : _LIBCPP_HIDE_FROM_ABI
819 : static size_type __recommend_blocks(size_type __n)
820 : {
821 : return __n / __block_size + (__n % __block_size != 0);
822 : }
823 : _LIBCPP_HIDE_FROM_ABI
824 112 : size_type __capacity() const
825 : {
826 112 : return __map_.size() == 0 ? 0 : __map_.size() * __block_size - 1;
827 : }
828 : _LIBCPP_HIDE_FROM_ABI
829 : size_type __block_count() const
830 : {
831 : return __map_.size();
832 : }
833 :
834 : _LIBCPP_HIDE_FROM_ABI
835 3 : size_type __front_spare() const
836 : {
837 3 : return __start_;
838 : }
839 : _LIBCPP_HIDE_FROM_ABI
840 : size_type __front_spare_blocks() const {
841 : return __front_spare() / __block_size;
842 : }
843 : _LIBCPP_HIDE_FROM_ABI
844 112 : size_type __back_spare() const
845 : {
846 112 : return __capacity() - (__start_ + size());
847 : }
848 : _LIBCPP_HIDE_FROM_ABI
849 56 : size_type __back_spare_blocks() const {
850 56 : return __back_spare() / __block_size;
851 : }
852 :
853 : private:
854 : _LIBCPP_HIDE_FROM_ABI
855 : bool __maybe_remove_front_spare(bool __keep_one = true) {
856 : if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) {
857 : __alloc_traits::deallocate(__alloc(), __map_.front(),
858 : __block_size);
859 : __map_.pop_front();
860 : __start_ -= __block_size;
861 : return true;
862 : }
863 : return false;
864 : }
865 :
866 : _LIBCPP_HIDE_FROM_ABI
867 56 : bool __maybe_remove_back_spare(bool __keep_one = true) {
868 56 : if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) {
869 0 : __alloc_traits::deallocate(__alloc(), __map_.back(),
870 : __block_size);
871 0 : __map_.pop_back();
872 0 : return true;
873 : }
874 56 : return false;
875 56 : }
876 :
877 : template <class _InpIter>
878 : _LIBCPP_HIDE_FROM_ABI void __append(_InpIter __f, _InpIter __l,
879 : typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type* = 0);
880 : template <class _ForIter>
881 : _LIBCPP_HIDE_FROM_ABI void __append(_ForIter __f, _ForIter __l,
882 : typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type* = 0);
883 : _LIBCPP_HIDE_FROM_ABI void __append(size_type __n);
884 : _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const value_type& __v);
885 : _LIBCPP_HIDE_FROM_ABI void __erase_to_end(const_iterator __f);
886 : _LIBCPP_HIDE_FROM_ABI void __add_front_capacity();
887 : _LIBCPP_HIDE_FROM_ABI void __add_front_capacity(size_type __n);
888 : _LIBCPP_HIDE_FROM_ABI void __add_back_capacity();
889 : _LIBCPP_HIDE_FROM_ABI void __add_back_capacity(size_type __n);
890 : _LIBCPP_HIDE_FROM_ABI iterator __move_and_check(iterator __f, iterator __l, iterator __r,
891 : const_pointer& __vt);
892 : _LIBCPP_HIDE_FROM_ABI iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r,
893 : const_pointer& __vt);
894 : _LIBCPP_HIDE_FROM_ABI void __move_construct_and_check(iterator __f, iterator __l,
895 : iterator __r, const_pointer& __vt);
896 : _LIBCPP_HIDE_FROM_ABI void __move_construct_backward_and_check(iterator __f, iterator __l,
897 : iterator __r, const_pointer& __vt);
898 :
899 : _LIBCPP_HIDE_FROM_ABI
900 : void __copy_assign_alloc(const deque& __c)
901 : {__copy_assign_alloc(__c, integral_constant<bool,
902 : __alloc_traits::propagate_on_container_copy_assignment::value>());}
903 :
904 : _LIBCPP_HIDE_FROM_ABI
905 : void __copy_assign_alloc(const deque& __c, true_type)
906 : {
907 : if (__alloc() != __c.__alloc())
908 : {
909 : clear();
910 : shrink_to_fit();
911 : }
912 : __alloc() = __c.__alloc();
913 : __map_.__alloc() = __c.__map_.__alloc();
914 : }
915 :
916 : _LIBCPP_HIDE_FROM_ABI
917 : void __copy_assign_alloc(const deque&, false_type)
918 : {}
919 :
920 : _LIBCPP_HIDE_FROM_ABI void __move_assign(deque& __c, true_type)
921 : _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
922 : _LIBCPP_HIDE_FROM_ABI void __move_assign(deque& __c, false_type);
923 : };
924 :
925 : template <class _Tp, class _Alloc>
926 : _LIBCPP_CONSTEXPR const typename allocator_traits<_Alloc>::difference_type deque<_Tp, _Alloc>::__block_size =
927 : __deque_block_size<value_type, difference_type>::value;
928 :
929 : #if _LIBCPP_STD_VER >= 17
930 : template<class _InputIterator,
931 : class _Alloc = allocator<__iter_value_type<_InputIterator>>,
932 : class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
933 : class = enable_if_t<__is_allocator<_Alloc>::value>
934 : >
935 : deque(_InputIterator, _InputIterator)
936 : -> deque<__iter_value_type<_InputIterator>, _Alloc>;
937 :
938 : template<class _InputIterator,
939 : class _Alloc,
940 : class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
941 : class = enable_if_t<__is_allocator<_Alloc>::value>
942 : >
943 : deque(_InputIterator, _InputIterator, _Alloc)
944 : -> deque<__iter_value_type<_InputIterator>, _Alloc>;
945 : #endif
946 :
947 : template <class _Tp, class _Allocator>
948 : deque<_Tp, _Allocator>::deque(size_type __n)
949 : : __start_(0), __size_(0, __default_init_tag())
950 : {
951 : if (__n > 0)
952 : __append(__n);
953 : }
954 :
955 : #if _LIBCPP_STD_VER > 11
956 : template <class _Tp, class _Allocator>
957 : deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a)
958 : : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
959 : {
960 : if (__n > 0)
961 : __append(__n);
962 : }
963 : #endif
964 :
965 : template <class _Tp, class _Allocator>
966 : deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)
967 : : __start_(0), __size_(0, __default_init_tag())
968 : {
969 : if (__n > 0)
970 : __append(__n, __v);
971 : }
972 :
973 : template <class _Tp, class _Allocator>
974 : template <class _InputIter>
975 : deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l,
976 : typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type*)
977 : : __start_(0), __size_(0, __default_init_tag())
978 : {
979 : __append(__f, __l);
980 : }
981 :
982 : template <class _Tp, class _Allocator>
983 : template <class _InputIter>
984 : deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
985 : typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type*)
986 : : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
987 : {
988 : __append(__f, __l);
989 : }
990 :
991 : template <class _Tp, class _Allocator>
992 : deque<_Tp, _Allocator>::deque(const deque& __c)
993 : : __map_(__pointer_allocator(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))),
994 : __start_(0),
995 : __size_(0, __map_.__alloc())
996 : {
997 : __append(__c.begin(), __c.end());
998 : }
999 :
1000 : template <class _Tp, class _Allocator>
1001 : deque<_Tp, _Allocator>::deque(const deque& __c, const __type_identity_t<allocator_type>& __a)
1002 : : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
1003 : {
1004 : __append(__c.begin(), __c.end());
1005 : }
1006 :
1007 : template <class _Tp, class _Allocator>
1008 : deque<_Tp, _Allocator>&
1009 : deque<_Tp, _Allocator>::operator=(const deque& __c)
1010 : {
1011 : if (this != _VSTD::addressof(__c))
1012 : {
1013 : __copy_assign_alloc(__c);
1014 : assign(__c.begin(), __c.end());
1015 : }
1016 : return *this;
1017 : }
1018 :
1019 : #ifndef _LIBCPP_CXX03_LANG
1020 :
1021 : template <class _Tp, class _Allocator>
1022 : deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)
1023 : : __start_(0), __size_(0, __default_init_tag())
1024 : {
1025 : __append(__il.begin(), __il.end());
1026 : }
1027 :
1028 : template <class _Tp, class _Allocator>
1029 : deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a)
1030 : : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a)
1031 : {
1032 : __append(__il.begin(), __il.end());
1033 : }
1034 :
1035 : template <class _Tp, class _Allocator>
1036 : inline
1037 : deque<_Tp, _Allocator>::deque(deque&& __c)
1038 : _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1039 : : __map_(std::move(__c.__map_)), __start_(std::move(__c.__start_)), __size_(std::move(__c.__size_))
1040 : {
1041 : __c.__start_ = 0;
1042 : __c.__size() = 0;
1043 : }
1044 :
1045 : template <class _Tp, class _Allocator>
1046 : inline
1047 : deque<_Tp, _Allocator>::deque(deque&& __c, const __type_identity_t<allocator_type>& __a)
1048 : : __map_(std::move(__c.__map_), __pointer_allocator(__a)),
1049 : __start_(std::move(__c.__start_)),
1050 : __size_(std::move(__c.__size()), __a)
1051 : {
1052 : if (__a == __c.__alloc())
1053 : {
1054 : __c.__start_ = 0;
1055 : __c.__size() = 0;
1056 : }
1057 : else
1058 : {
1059 : __map_.clear();
1060 : __start_ = 0;
1061 : __size() = 0;
1062 : typedef move_iterator<iterator> _Ip;
1063 : assign(_Ip(__c.begin()), _Ip(__c.end()));
1064 : }
1065 : }
1066 :
1067 : template <class _Tp, class _Allocator>
1068 : inline
1069 : deque<_Tp, _Allocator>&
1070 : deque<_Tp, _Allocator>::operator=(deque&& __c)
1071 : _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1072 : is_nothrow_move_assignable<allocator_type>::value)
1073 : {
1074 : __move_assign(__c, integral_constant<bool,
1075 : __alloc_traits::propagate_on_container_move_assignment::value>());
1076 : return *this;
1077 : }
1078 :
1079 : template <class _Tp, class _Allocator>
1080 : void
1081 : deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type)
1082 : {
1083 : if (__alloc() != __c.__alloc())
1084 : {
1085 : typedef move_iterator<iterator> _Ip;
1086 : assign(_Ip(__c.begin()), _Ip(__c.end()));
1087 : }
1088 : else
1089 : __move_assign(__c, true_type());
1090 : }
1091 :
1092 : template <class _Tp, class _Allocator>
1093 : void
1094 : deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type)
1095 : _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1096 : {
1097 : clear();
1098 : shrink_to_fit();
1099 : __move_assign(__c);
1100 : }
1101 :
1102 : #endif // _LIBCPP_CXX03_LANG
1103 :
1104 : template <class _Tp, class _Allocator>
1105 : template <class _InputIter>
1106 : void
1107 : deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
1108 : typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
1109 : !__is_cpp17_random_access_iterator<_InputIter>::value>::type*)
1110 : {
1111 : iterator __i = begin();
1112 : iterator __e = end();
1113 : for (; __f != __l && __i != __e; ++__f, (void) ++__i)
1114 : *__i = *__f;
1115 : if (__f != __l)
1116 : __append(__f, __l);
1117 : else
1118 : __erase_to_end(__i);
1119 : }
1120 :
1121 : template <class _Tp, class _Allocator>
1122 : template <class _RAIter>
1123 : void
1124 : deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
1125 : typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
1126 : {
1127 : if (static_cast<size_type>(__l - __f) > size())
1128 : {
1129 : _RAIter __m = __f + size();
1130 : _VSTD::copy(__f, __m, begin());
1131 : __append(__m, __l);
1132 : }
1133 : else
1134 : __erase_to_end(_VSTD::copy(__f, __l, begin()));
1135 : }
1136 :
1137 : template <class _Tp, class _Allocator>
1138 : void
1139 : deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
1140 : {
1141 : if (__n > size())
1142 : {
1143 : _VSTD::fill_n(begin(), size(), __v);
1144 : __n -= size();
1145 : __append(__n, __v);
1146 : }
1147 : else
1148 : __erase_to_end(_VSTD::fill_n(begin(), __n, __v));
1149 : }
1150 :
1151 : template <class _Tp, class _Allocator>
1152 : inline
1153 : _Allocator
1154 : deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
1155 : {
1156 : return __alloc();
1157 : }
1158 :
1159 : template <class _Tp, class _Allocator>
1160 : void
1161 : deque<_Tp, _Allocator>::resize(size_type __n)
1162 : {
1163 : if (__n > size())
1164 : __append(__n - size());
1165 : else if (__n < size())
1166 : __erase_to_end(begin() + __n);
1167 : }
1168 :
1169 : template <class _Tp, class _Allocator>
1170 : void
1171 : deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v)
1172 : {
1173 : if (__n > size())
1174 : __append(__n - size(), __v);
1175 : else if (__n < size())
1176 : __erase_to_end(begin() + __n);
1177 : }
1178 :
1179 : template <class _Tp, class _Allocator>
1180 : void
1181 : deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1182 : {
1183 : allocator_type& __a = __alloc();
1184 : if (empty())
1185 : {
1186 : while (__map_.size() > 0)
1187 : {
1188 : __alloc_traits::deallocate(__a, __map_.back(), __block_size);
1189 : __map_.pop_back();
1190 : }
1191 : __start_ = 0;
1192 : }
1193 : else
1194 : {
1195 : __maybe_remove_front_spare(/*__keep_one=*/false);
1196 : __maybe_remove_back_spare(/*__keep_one=*/false);
1197 : }
1198 : __map_.shrink_to_fit();
1199 : }
1200 :
1201 : template <class _Tp, class _Allocator>
1202 : inline
1203 : typename deque<_Tp, _Allocator>::reference
1204 : deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT
1205 : {
1206 : size_type __p = __start_ + __i;
1207 : return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
1208 : }
1209 :
1210 : template <class _Tp, class _Allocator>
1211 : inline
1212 : typename deque<_Tp, _Allocator>::const_reference
1213 : deque<_Tp, _Allocator>::operator[](size_type __i) const _NOEXCEPT
1214 : {
1215 : size_type __p = __start_ + __i;
1216 : return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
1217 : }
1218 :
1219 : template <class _Tp, class _Allocator>
1220 : inline
1221 : typename deque<_Tp, _Allocator>::reference
1222 : deque<_Tp, _Allocator>::at(size_type __i)
1223 : {
1224 : if (__i >= size())
1225 : _VSTD::__throw_out_of_range("deque");
1226 : size_type __p = __start_ + __i;
1227 : return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
1228 : }
1229 :
1230 : template <class _Tp, class _Allocator>
1231 : inline
1232 : typename deque<_Tp, _Allocator>::const_reference
1233 : deque<_Tp, _Allocator>::at(size_type __i) const
1234 : {
1235 : if (__i >= size())
1236 : _VSTD::__throw_out_of_range("deque");
1237 : size_type __p = __start_ + __i;
1238 : return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
1239 : }
1240 :
1241 : template <class _Tp, class _Allocator>
1242 : inline
1243 : typename deque<_Tp, _Allocator>::reference
1244 : deque<_Tp, _Allocator>::front() _NOEXCEPT
1245 : {
1246 : return *(*(__map_.begin() + __start_ / __block_size)
1247 : + __start_ % __block_size);
1248 : }
1249 :
1250 : template <class _Tp, class _Allocator>
1251 : inline
1252 : typename deque<_Tp, _Allocator>::const_reference
1253 : deque<_Tp, _Allocator>::front() const _NOEXCEPT
1254 : {
1255 : return *(*(__map_.begin() + __start_ / __block_size)
1256 : + __start_ % __block_size);
1257 : }
1258 :
1259 : template <class _Tp, class _Allocator>
1260 : inline
1261 : typename deque<_Tp, _Allocator>::reference
1262 109 : deque<_Tp, _Allocator>::back() _NOEXCEPT
1263 : {
1264 109 : size_type __p = size() + __start_ - 1;
1265 109 : return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
1266 : }
1267 :
1268 : template <class _Tp, class _Allocator>
1269 : inline
1270 : typename deque<_Tp, _Allocator>::const_reference
1271 : deque<_Tp, _Allocator>::back() const _NOEXCEPT
1272 : {
1273 : size_type __p = size() + __start_ - 1;
1274 : return *(*(__map_.begin() + __p / __block_size) + __p % __block_size);
1275 : }
1276 :
1277 : template <class _Tp, class _Allocator>
1278 : void
1279 56 : deque<_Tp, _Allocator>::push_back(const value_type& __v)
1280 : {
1281 56 : allocator_type& __a = __alloc();
1282 56 : if (__back_spare() == 0)
1283 3 : __add_back_capacity();
1284 : // __back_spare() >= 1
1285 56 : __alloc_traits::construct(__a, _VSTD::addressof(*end()), __v);
1286 56 : ++__size();
1287 56 : }
1288 :
1289 : template <class _Tp, class _Allocator>
1290 : void
1291 : deque<_Tp, _Allocator>::push_front(const value_type& __v)
1292 : {
1293 : allocator_type& __a = __alloc();
1294 : if (__front_spare() == 0)
1295 : __add_front_capacity();
1296 : // __front_spare() >= 1
1297 : __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), __v);
1298 : --__start_;
1299 : ++__size();
1300 : }
1301 :
1302 : #ifndef _LIBCPP_CXX03_LANG
1303 : template <class _Tp, class _Allocator>
1304 : void
1305 : deque<_Tp, _Allocator>::push_back(value_type&& __v)
1306 : {
1307 : allocator_type& __a = __alloc();
1308 : if (__back_spare() == 0)
1309 : __add_back_capacity();
1310 : // __back_spare() >= 1
1311 : __alloc_traits::construct(__a, _VSTD::addressof(*end()), _VSTD::move(__v));
1312 : ++__size();
1313 : }
1314 :
1315 : template <class _Tp, class _Allocator>
1316 : template <class... _Args>
1317 : #if _LIBCPP_STD_VER > 14
1318 : typename deque<_Tp, _Allocator>::reference
1319 : #else
1320 : void
1321 : #endif
1322 : deque<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1323 : {
1324 : allocator_type& __a = __alloc();
1325 : if (__back_spare() == 0)
1326 : __add_back_capacity();
1327 : // __back_spare() >= 1
1328 : __alloc_traits::construct(__a, _VSTD::addressof(*end()),
1329 : _VSTD::forward<_Args>(__args)...);
1330 : ++__size();
1331 : #if _LIBCPP_STD_VER > 14
1332 : return *--end();
1333 : #endif
1334 : }
1335 :
1336 : template <class _Tp, class _Allocator>
1337 : void
1338 : deque<_Tp, _Allocator>::push_front(value_type&& __v)
1339 : {
1340 : allocator_type& __a = __alloc();
1341 : if (__front_spare() == 0)
1342 : __add_front_capacity();
1343 : // __front_spare() >= 1
1344 : __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), _VSTD::move(__v));
1345 : --__start_;
1346 : ++__size();
1347 : }
1348 :
1349 :
1350 : template <class _Tp, class _Allocator>
1351 : template <class... _Args>
1352 : #if _LIBCPP_STD_VER > 14
1353 : typename deque<_Tp, _Allocator>::reference
1354 : #else
1355 : void
1356 : #endif
1357 : deque<_Tp, _Allocator>::emplace_front(_Args&&... __args)
1358 : {
1359 : allocator_type& __a = __alloc();
1360 : if (__front_spare() == 0)
1361 : __add_front_capacity();
1362 : // __front_spare() >= 1
1363 : __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), _VSTD::forward<_Args>(__args)...);
1364 : --__start_;
1365 : ++__size();
1366 : #if _LIBCPP_STD_VER > 14
1367 : return *begin();
1368 : #endif
1369 : }
1370 :
1371 : template <class _Tp, class _Allocator>
1372 : typename deque<_Tp, _Allocator>::iterator
1373 : deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v)
1374 : {
1375 : size_type __pos = __p - begin();
1376 : size_type __to_end = size() - __pos;
1377 : allocator_type& __a = __alloc();
1378 : if (__pos < __to_end)
1379 : { // insert by shifting things backward
1380 : if (__front_spare() == 0)
1381 : __add_front_capacity();
1382 : // __front_spare() >= 1
1383 : if (__pos == 0)
1384 : {
1385 : __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), _VSTD::move(__v));
1386 : --__start_;
1387 : ++__size();
1388 : }
1389 : else
1390 : {
1391 : iterator __b = begin();
1392 : iterator __bm1 = _VSTD::prev(__b);
1393 : __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1394 : --__start_;
1395 : ++__size();
1396 : if (__pos > 1)
1397 : __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1398 : *__b = _VSTD::move(__v);
1399 : }
1400 : }
1401 : else
1402 : { // insert by shifting things forward
1403 : if (__back_spare() == 0)
1404 : __add_back_capacity();
1405 : // __back_capacity >= 1
1406 : size_type __de = size() - __pos;
1407 : if (__de == 0)
1408 : {
1409 : __alloc_traits::construct(__a, _VSTD::addressof(*end()), _VSTD::move(__v));
1410 : ++__size();
1411 : }
1412 : else
1413 : {
1414 : iterator __e = end();
1415 : iterator __em1 = _VSTD::prev(__e);
1416 : __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
1417 : ++__size();
1418 : if (__de > 1)
1419 : __e = _VSTD::move_backward(__e - __de, __em1, __e);
1420 : *--__e = _VSTD::move(__v);
1421 : }
1422 : }
1423 : return begin() + __pos;
1424 : }
1425 :
1426 : template <class _Tp, class _Allocator>
1427 : template <class... _Args>
1428 : typename deque<_Tp, _Allocator>::iterator
1429 : deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args)
1430 : {
1431 : size_type __pos = __p - begin();
1432 : size_type __to_end = size() - __pos;
1433 : allocator_type& __a = __alloc();
1434 : if (__pos < __to_end)
1435 : { // insert by shifting things backward
1436 : if (__front_spare() == 0)
1437 : __add_front_capacity();
1438 : // __front_spare() >= 1
1439 : if (__pos == 0)
1440 : {
1441 : __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), _VSTD::forward<_Args>(__args)...);
1442 : --__start_;
1443 : ++__size();
1444 : }
1445 : else
1446 : {
1447 : __temp_value<value_type, _Allocator> __tmp(__alloc(), _VSTD::forward<_Args>(__args)...);
1448 : iterator __b = begin();
1449 : iterator __bm1 = _VSTD::prev(__b);
1450 : __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1451 : --__start_;
1452 : ++__size();
1453 : if (__pos > 1)
1454 : __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1455 : *__b = _VSTD::move(__tmp.get());
1456 : }
1457 : }
1458 : else
1459 : { // insert by shifting things forward
1460 : if (__back_spare() == 0)
1461 : __add_back_capacity();
1462 : // __back_capacity >= 1
1463 : size_type __de = size() - __pos;
1464 : if (__de == 0)
1465 : {
1466 : __alloc_traits::construct(__a, _VSTD::addressof(*end()), _VSTD::forward<_Args>(__args)...);
1467 : ++__size();
1468 : }
1469 : else
1470 : {
1471 : __temp_value<value_type, _Allocator> __tmp(__alloc(), _VSTD::forward<_Args>(__args)...);
1472 : iterator __e = end();
1473 : iterator __em1 = _VSTD::prev(__e);
1474 : __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
1475 : ++__size();
1476 : if (__de > 1)
1477 : __e = _VSTD::move_backward(__e - __de, __em1, __e);
1478 : *--__e = _VSTD::move(__tmp.get());
1479 : }
1480 : }
1481 : return begin() + __pos;
1482 : }
1483 :
1484 : #endif // _LIBCPP_CXX03_LANG
1485 :
1486 :
1487 : template <class _Tp, class _Allocator>
1488 : typename deque<_Tp, _Allocator>::iterator
1489 : deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v)
1490 : {
1491 : size_type __pos = __p - begin();
1492 : size_type __to_end = size() - __pos;
1493 : allocator_type& __a = __alloc();
1494 : if (__pos < __to_end)
1495 : { // insert by shifting things backward
1496 : if (__front_spare() == 0)
1497 : __add_front_capacity();
1498 : // __front_spare() >= 1
1499 : if (__pos == 0)
1500 : {
1501 : __alloc_traits::construct(__a, _VSTD::addressof(*--begin()), __v);
1502 : --__start_;
1503 : ++__size();
1504 : }
1505 : else
1506 : {
1507 : const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1508 : iterator __b = begin();
1509 : iterator __bm1 = _VSTD::prev(__b);
1510 : if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))
1511 : __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);
1512 : __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1513 : --__start_;
1514 : ++__size();
1515 : if (__pos > 1)
1516 : __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt);
1517 : *__b = *__vt;
1518 : }
1519 : }
1520 : else
1521 : { // insert by shifting things forward
1522 : if (__back_spare() == 0)
1523 : __add_back_capacity();
1524 : // __back_capacity >= 1
1525 : size_type __de = size() - __pos;
1526 : if (__de == 0)
1527 : {
1528 : __alloc_traits::construct(__a, _VSTD::addressof(*end()), __v);
1529 : ++__size();
1530 : }
1531 : else
1532 : {
1533 : const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1534 : iterator __e = end();
1535 : iterator __em1 = _VSTD::prev(__e);
1536 : if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))
1537 : __vt = pointer_traits<const_pointer>::pointer_to(*__e);
1538 : __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
1539 : ++__size();
1540 : if (__de > 1)
1541 : __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);
1542 : *--__e = *__vt;
1543 : }
1544 : }
1545 : return begin() + __pos;
1546 : }
1547 :
1548 : template <class _Tp, class _Allocator>
1549 : typename deque<_Tp, _Allocator>::iterator
1550 : deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v)
1551 : {
1552 : size_type __pos = __p - begin();
1553 : size_type __to_end = __size() - __pos;
1554 : allocator_type& __a = __alloc();
1555 : if (__pos < __to_end)
1556 : { // insert by shifting things backward
1557 : if (__n > __front_spare())
1558 : __add_front_capacity(__n - __front_spare());
1559 : // __n <= __front_spare()
1560 : iterator __old_begin = begin();
1561 : iterator __i = __old_begin;
1562 : if (__n > __pos)
1563 : {
1564 : for (size_type __m = __n - __pos; __m; --__m, --__start_, ++__size())
1565 : __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v);
1566 : __n = __pos;
1567 : }
1568 : if (__n > 0)
1569 : {
1570 : const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1571 : iterator __obn = __old_begin + __n;
1572 : __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);
1573 : if (__n < __pos)
1574 : __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);
1575 : _VSTD::fill_n(__old_begin, __n, *__vt);
1576 : }
1577 : }
1578 : else
1579 : { // insert by shifting things forward
1580 : size_type __back_capacity = __back_spare();
1581 : if (__n > __back_capacity)
1582 : __add_back_capacity(__n - __back_capacity);
1583 : // __n <= __back_capacity
1584 : iterator __old_end = end();
1585 : iterator __i = __old_end;
1586 : size_type __de = size() - __pos;
1587 : if (__n > __de)
1588 : {
1589 : for (size_type __m = __n - __de; __m; --__m, (void) ++__i, ++__size())
1590 : __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
1591 : __n = __de;
1592 : }
1593 : if (__n > 0)
1594 : {
1595 : const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1596 : iterator __oen = __old_end - __n;
1597 : __move_construct_and_check(__oen, __old_end, __i, __vt);
1598 : if (__n < __de)
1599 : __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);
1600 : _VSTD::fill_n(__old_end - __n, __n, *__vt);
1601 : }
1602 : }
1603 : return begin() + __pos;
1604 : }
1605 :
1606 : template <class _Tp, class _Allocator>
1607 : template <class _InputIter>
1608 : typename deque<_Tp, _Allocator>::iterator
1609 : deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
1610 : typename enable_if<__is_exactly_cpp17_input_iterator<_InputIter>::value>::type*)
1611 : {
1612 : __split_buffer<value_type, allocator_type&> __buf(__alloc());
1613 : __buf.__construct_at_end(__f, __l);
1614 : typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
1615 : return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
1616 : }
1617 :
1618 : template <class _Tp, class _Allocator>
1619 : template <class _ForwardIterator>
1620 : typename deque<_Tp, _Allocator>::iterator
1621 : deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
1622 : typename enable_if<__is_exactly_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
1623 : {
1624 : size_type __n = _VSTD::distance(__f, __l);
1625 : __split_buffer<value_type, allocator_type&> __buf(__n, 0, __alloc());
1626 : __buf.__construct_at_end(__f, __l);
1627 : typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
1628 : return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
1629 : }
1630 :
1631 : template <class _Tp, class _Allocator>
1632 : template <class _BiIter>
1633 : typename deque<_Tp, _Allocator>::iterator
1634 : deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
1635 : typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type*)
1636 : {
1637 : size_type __n = _VSTD::distance(__f, __l);
1638 : size_type __pos = __p - begin();
1639 : size_type __to_end = size() - __pos;
1640 : allocator_type& __a = __alloc();
1641 : if (__pos < __to_end)
1642 : { // insert by shifting things backward
1643 : if (__n > __front_spare())
1644 : __add_front_capacity(__n - __front_spare());
1645 : // __n <= __front_spare()
1646 : iterator __old_begin = begin();
1647 : iterator __i = __old_begin;
1648 : _BiIter __m = __f;
1649 : if (__n > __pos)
1650 : {
1651 : __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
1652 : for (_BiIter __j = __m; __j != __f; --__start_, ++__size())
1653 : __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
1654 : __n = __pos;
1655 : }
1656 : if (__n > 0)
1657 : {
1658 : iterator __obn = __old_begin + __n;
1659 : for (iterator __j = __obn; __j != __old_begin;)
1660 : {
1661 : __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
1662 : --__start_;
1663 : ++__size();
1664 : }
1665 : if (__n < __pos)
1666 : __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
1667 : _VSTD::copy(__m, __l, __old_begin);
1668 : }
1669 : }
1670 : else
1671 : { // insert by shifting things forward
1672 : size_type __back_capacity = __back_spare();
1673 : if (__n > __back_capacity)
1674 : __add_back_capacity(__n - __back_capacity);
1675 : // __n <= __back_capacity
1676 : iterator __old_end = end();
1677 : iterator __i = __old_end;
1678 : _BiIter __m = __l;
1679 : size_type __de = size() - __pos;
1680 : if (__n > __de)
1681 : {
1682 : __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
1683 : for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__size())
1684 : __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
1685 : __n = __de;
1686 : }
1687 : if (__n > 0)
1688 : {
1689 : iterator __oen = __old_end - __n;
1690 : for (iterator __j = __oen; __j != __old_end; ++__i, (void) ++__j, ++__size())
1691 : __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
1692 : if (__n < __de)
1693 : __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
1694 : _VSTD::copy_backward(__f, __m, __old_end);
1695 : }
1696 : }
1697 : return begin() + __pos;
1698 : }
1699 :
1700 : template <class _Tp, class _Allocator>
1701 : template <class _InpIter>
1702 : void
1703 : deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
1704 : typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type*)
1705 : {
1706 : for (; __f != __l; ++__f)
1707 : #ifdef _LIBCPP_CXX03_LANG
1708 : push_back(*__f);
1709 : #else
1710 : emplace_back(*__f);
1711 : #endif
1712 : }
1713 :
1714 : template <class _Tp, class _Allocator>
1715 : template <class _ForIter>
1716 : void
1717 : deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
1718 : typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type*)
1719 : {
1720 : size_type __n = _VSTD::distance(__f, __l);
1721 : allocator_type& __a = __alloc();
1722 : size_type __back_capacity = __back_spare();
1723 : if (__n > __back_capacity)
1724 : __add_back_capacity(__n - __back_capacity);
1725 : // __n <= __back_capacity
1726 : for (__deque_block_range __br : __deque_range(end(), end() + __n)) {
1727 : _ConstructTransaction __tx(this, __br);
1728 : for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) {
1729 : __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), *__f);
1730 : }
1731 : }
1732 : }
1733 :
1734 : template <class _Tp, class _Allocator>
1735 : void
1736 : deque<_Tp, _Allocator>::__append(size_type __n)
1737 : {
1738 : allocator_type& __a = __alloc();
1739 : size_type __back_capacity = __back_spare();
1740 : if (__n > __back_capacity)
1741 : __add_back_capacity(__n - __back_capacity);
1742 : // __n <= __back_capacity
1743 : for (__deque_block_range __br : __deque_range(end(), end() + __n)) {
1744 : _ConstructTransaction __tx(this, __br);
1745 : for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
1746 : __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_));
1747 : }
1748 : }
1749 : }
1750 :
1751 : template <class _Tp, class _Allocator>
1752 : void
1753 : deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
1754 : {
1755 : allocator_type& __a = __alloc();
1756 : size_type __back_capacity = __back_spare();
1757 : if (__n > __back_capacity)
1758 : __add_back_capacity(__n - __back_capacity);
1759 : // __n <= __back_capacity
1760 : for (__deque_block_range __br : __deque_range(end(), end() + __n)) {
1761 : _ConstructTransaction __tx(this, __br);
1762 : for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
1763 : __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), __v);
1764 : }
1765 : }
1766 :
1767 : }
1768 :
1769 : // Create front capacity for one block of elements.
1770 : // Strong guarantee. Either do it or don't touch anything.
1771 : template <class _Tp, class _Allocator>
1772 : void
1773 : deque<_Tp, _Allocator>::__add_front_capacity()
1774 : {
1775 : allocator_type& __a = __alloc();
1776 : if (__back_spare() >= __block_size)
1777 : {
1778 : __start_ += __block_size;
1779 : pointer __pt = __map_.back();
1780 : __map_.pop_back();
1781 : __map_.push_front(__pt);
1782 : }
1783 : // Else if __map_.size() < __map_.capacity() then we need to allocate 1 buffer
1784 : else if (__map_.size() < __map_.capacity())
1785 : { // we can put the new buffer into the map, but don't shift things around
1786 : // until all buffers are allocated. If we throw, we don't need to fix
1787 : // anything up (any added buffers are undetectible)
1788 : if (__map_.__front_spare() > 0)
1789 : __map_.push_front(__alloc_traits::allocate(__a, __block_size));
1790 : else
1791 : {
1792 : __map_.push_back(__alloc_traits::allocate(__a, __block_size));
1793 : // Done allocating, reorder capacity
1794 : pointer __pt = __map_.back();
1795 : __map_.pop_back();
1796 : __map_.push_front(__pt);
1797 : }
1798 : __start_ = __map_.size() == 1 ?
1799 : __block_size / 2 :
1800 : __start_ + __block_size;
1801 : }
1802 : // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
1803 : else
1804 : {
1805 : __split_buffer<pointer, __pointer_allocator&>
1806 : __buf(std::max<size_type>(2 * __map_.capacity(), 1),
1807 : 0, __map_.__alloc());
1808 :
1809 : typedef __allocator_destructor<_Allocator> _Dp;
1810 : unique_ptr<pointer, _Dp> __hold(
1811 : __alloc_traits::allocate(__a, __block_size),
1812 : _Dp(__a, __block_size));
1813 : __buf.push_back(__hold.get());
1814 : __hold.release();
1815 :
1816 : for (__map_pointer __i = __map_.begin();
1817 : __i != __map_.end(); ++__i)
1818 : __buf.push_back(*__i);
1819 : _VSTD::swap(__map_.__first_, __buf.__first_);
1820 : _VSTD::swap(__map_.__begin_, __buf.__begin_);
1821 : _VSTD::swap(__map_.__end_, __buf.__end_);
1822 : _VSTD::swap(__map_.__end_cap(), __buf.__end_cap());
1823 : __start_ = __map_.size() == 1 ?
1824 : __block_size / 2 :
1825 : __start_ + __block_size;
1826 : }
1827 : }
1828 :
1829 : // Create front capacity for __n elements.
1830 : // Strong guarantee. Either do it or don't touch anything.
1831 : template <class _Tp, class _Allocator>
1832 : void
1833 : deque<_Tp, _Allocator>::__add_front_capacity(size_type __n)
1834 : {
1835 : allocator_type& __a = __alloc();
1836 : size_type __nb = __recommend_blocks(__n + __map_.empty());
1837 : // Number of unused blocks at back:
1838 : size_type __back_capacity = __back_spare() / __block_size;
1839 : __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need
1840 : __nb -= __back_capacity; // number of blocks need to allocate
1841 : // If __nb == 0, then we have sufficient capacity.
1842 : if (__nb == 0)
1843 : {
1844 : __start_ += __block_size * __back_capacity;
1845 : for (; __back_capacity > 0; --__back_capacity)
1846 : {
1847 : pointer __pt = __map_.back();
1848 : __map_.pop_back();
1849 : __map_.push_front(__pt);
1850 : }
1851 : }
1852 : // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
1853 : else if (__nb <= __map_.capacity() - __map_.size())
1854 : { // we can put the new buffers into the map, but don't shift things around
1855 : // until all buffers are allocated. If we throw, we don't need to fix
1856 : // anything up (any added buffers are undetectible)
1857 : for (; __nb > 0; --__nb, __start_ += __block_size - (__map_.size() == 1))
1858 : {
1859 : if (__map_.__front_spare() == 0)
1860 : break;
1861 : __map_.push_front(__alloc_traits::allocate(__a, __block_size));
1862 : }
1863 : for (; __nb > 0; --__nb, ++__back_capacity)
1864 : __map_.push_back(__alloc_traits::allocate(__a, __block_size));
1865 : // Done allocating, reorder capacity
1866 : __start_ += __back_capacity * __block_size;
1867 : for (; __back_capacity > 0; --__back_capacity)
1868 : {
1869 : pointer __pt = __map_.back();
1870 : __map_.pop_back();
1871 : __map_.push_front(__pt);
1872 : }
1873 : }
1874 : // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
1875 : else
1876 : {
1877 : size_type __ds = (__nb + __back_capacity) * __block_size - __map_.empty();
1878 : __split_buffer<pointer, __pointer_allocator&>
1879 : __buf(std::max<size_type>(2* __map_.capacity(),
1880 : __nb + __map_.size()),
1881 : 0, __map_.__alloc());
1882 : #ifndef _LIBCPP_NO_EXCEPTIONS
1883 : try
1884 : {
1885 : #endif // _LIBCPP_NO_EXCEPTIONS
1886 : for (; __nb > 0; --__nb)
1887 : __buf.push_back(__alloc_traits::allocate(__a, __block_size));
1888 : #ifndef _LIBCPP_NO_EXCEPTIONS
1889 : }
1890 : catch (...)
1891 : {
1892 : for (__map_pointer __i = __buf.begin();
1893 : __i != __buf.end(); ++__i)
1894 : __alloc_traits::deallocate(__a, *__i, __block_size);
1895 : throw;
1896 : }
1897 : #endif // _LIBCPP_NO_EXCEPTIONS
1898 : for (; __back_capacity > 0; --__back_capacity)
1899 : {
1900 : __buf.push_back(__map_.back());
1901 : __map_.pop_back();
1902 : }
1903 : for (__map_pointer __i = __map_.begin();
1904 : __i != __map_.end(); ++__i)
1905 : __buf.push_back(*__i);
1906 : _VSTD::swap(__map_.__first_, __buf.__first_);
1907 : _VSTD::swap(__map_.__begin_, __buf.__begin_);
1908 : _VSTD::swap(__map_.__end_, __buf.__end_);
1909 : _VSTD::swap(__map_.__end_cap(), __buf.__end_cap());
1910 : __start_ += __ds;
1911 : }
1912 : }
1913 :
1914 : // Create back capacity for one block of elements.
1915 : // Strong guarantee. Either do it or don't touch anything.
1916 : template <class _Tp, class _Allocator>
1917 : void
1918 3 : deque<_Tp, _Allocator>::__add_back_capacity()
1919 : {
1920 3 : allocator_type& __a = __alloc();
1921 3 : if (__front_spare() >= __block_size)
1922 : {
1923 0 : __start_ -= __block_size;
1924 0 : pointer __pt = __map_.front();
1925 0 : __map_.pop_front();
1926 0 : __map_.push_back(__pt);
1927 0 : }
1928 : // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
1929 3 : else if (__map_.size() < __map_.capacity())
1930 : { // we can put the new buffer into the map, but don't shift things around
1931 : // until it is allocated. If we throw, we don't need to fix
1932 : // anything up (any added buffers are undetectible)
1933 0 : if (__map_.__back_spare() != 0)
1934 0 : __map_.push_back(__alloc_traits::allocate(__a, __block_size));
1935 : else
1936 : {
1937 0 : __map_.push_front(__alloc_traits::allocate(__a, __block_size));
1938 : // Done allocating, reorder capacity
1939 0 : pointer __pt = __map_.front();
1940 0 : __map_.pop_front();
1941 0 : __map_.push_back(__pt);
1942 : }
1943 0 : }
1944 : // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
1945 : else
1946 : {
1947 : __split_buffer<pointer, __pointer_allocator&>
1948 6 : __buf(std::max<size_type>(2* __map_.capacity(), 1),
1949 3 : __map_.size(),
1950 3 : __map_.__alloc());
1951 :
1952 : typedef __allocator_destructor<_Allocator> _Dp;
1953 3 : unique_ptr<pointer, _Dp> __hold(
1954 3 : __alloc_traits::allocate(__a, __block_size),
1955 3 : _Dp(__a, __block_size));
1956 3 : __buf.push_back(__hold.get());
1957 3 : __hold.release();
1958 :
1959 3 : for (__map_pointer __i = __map_.end();
1960 3 : __i != __map_.begin();)
1961 0 : __buf.push_front(*--__i);
1962 3 : _VSTD::swap(__map_.__first_, __buf.__first_);
1963 3 : _VSTD::swap(__map_.__begin_, __buf.__begin_);
1964 3 : _VSTD::swap(__map_.__end_, __buf.__end_);
1965 3 : _VSTD::swap(__map_.__end_cap(), __buf.__end_cap());
1966 3 : }
1967 3 : }
1968 :
1969 : // Create back capacity for __n elements.
1970 : // Strong guarantee. Either do it or don't touch anything.
1971 : template <class _Tp, class _Allocator>
1972 : void
1973 : deque<_Tp, _Allocator>::__add_back_capacity(size_type __n)
1974 : {
1975 : allocator_type& __a = __alloc();
1976 : size_type __nb = __recommend_blocks(__n + __map_.empty());
1977 : // Number of unused blocks at front:
1978 : size_type __front_capacity = __front_spare() / __block_size;
1979 : __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need
1980 : __nb -= __front_capacity; // number of blocks need to allocate
1981 : // If __nb == 0, then we have sufficient capacity.
1982 : if (__nb == 0)
1983 : {
1984 : __start_ -= __block_size * __front_capacity;
1985 : for (; __front_capacity > 0; --__front_capacity)
1986 : {
1987 : pointer __pt = __map_.front();
1988 : __map_.pop_front();
1989 : __map_.push_back(__pt);
1990 : }
1991 : }
1992 : // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
1993 : else if (__nb <= __map_.capacity() - __map_.size())
1994 : { // we can put the new buffers into the map, but don't shift things around
1995 : // until all buffers are allocated. If we throw, we don't need to fix
1996 : // anything up (any added buffers are undetectible)
1997 : for (; __nb > 0; --__nb)
1998 : {
1999 : if (__map_.__back_spare() == 0)
2000 : break;
2001 : __map_.push_back(__alloc_traits::allocate(__a, __block_size));
2002 : }
2003 : for (; __nb > 0; --__nb, ++__front_capacity, __start_ +=
2004 : __block_size - (__map_.size() == 1))
2005 : __map_.push_front(__alloc_traits::allocate(__a, __block_size));
2006 : // Done allocating, reorder capacity
2007 : __start_ -= __block_size * __front_capacity;
2008 : for (; __front_capacity > 0; --__front_capacity)
2009 : {
2010 : pointer __pt = __map_.front();
2011 : __map_.pop_front();
2012 : __map_.push_back(__pt);
2013 : }
2014 : }
2015 : // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2016 : else
2017 : {
2018 : size_type __ds = __front_capacity * __block_size;
2019 : __split_buffer<pointer, __pointer_allocator&>
2020 : __buf(std::max<size_type>(2* __map_.capacity(),
2021 : __nb + __map_.size()),
2022 : __map_.size() - __front_capacity,
2023 : __map_.__alloc());
2024 : #ifndef _LIBCPP_NO_EXCEPTIONS
2025 : try
2026 : {
2027 : #endif // _LIBCPP_NO_EXCEPTIONS
2028 : for (; __nb > 0; --__nb)
2029 : __buf.push_back(__alloc_traits::allocate(__a, __block_size));
2030 : #ifndef _LIBCPP_NO_EXCEPTIONS
2031 : }
2032 : catch (...)
2033 : {
2034 : for (__map_pointer __i = __buf.begin();
2035 : __i != __buf.end(); ++__i)
2036 : __alloc_traits::deallocate(__a, *__i, __block_size);
2037 : throw;
2038 : }
2039 : #endif // _LIBCPP_NO_EXCEPTIONS
2040 : for (; __front_capacity > 0; --__front_capacity)
2041 : {
2042 : __buf.push_back(__map_.front());
2043 : __map_.pop_front();
2044 : }
2045 : for (__map_pointer __i = __map_.end();
2046 : __i != __map_.begin();)
2047 : __buf.push_front(*--__i);
2048 : _VSTD::swap(__map_.__first_, __buf.__first_);
2049 : _VSTD::swap(__map_.__begin_, __buf.__begin_);
2050 : _VSTD::swap(__map_.__end_, __buf.__end_);
2051 : _VSTD::swap(__map_.__end_cap(), __buf.__end_cap());
2052 : __start_ -= __ds;
2053 : }
2054 : }
2055 :
2056 : template <class _Tp, class _Allocator>
2057 : void
2058 : deque<_Tp, _Allocator>::pop_front()
2059 : {
2060 : allocator_type& __a = __alloc();
2061 : __alloc_traits::destroy(__a, _VSTD::__to_address(*(__map_.begin() +
2062 : __start_ / __block_size) +
2063 : __start_ % __block_size));
2064 : --__size();
2065 : ++__start_;
2066 : __maybe_remove_front_spare();
2067 : }
2068 :
2069 : template <class _Tp, class _Allocator>
2070 : void
2071 56 : deque<_Tp, _Allocator>::pop_back()
2072 : {
2073 : _LIBCPP_ASSERT(!empty(), "deque::pop_back called on an empty deque");
2074 56 : allocator_type& __a = __alloc();
2075 56 : size_type __p = size() + __start_ - 1;
2076 168 : __alloc_traits::destroy(__a, _VSTD::__to_address(*(__map_.begin() +
2077 112 : __p / __block_size) +
2078 56 : __p % __block_size));
2079 56 : --__size();
2080 56 : __maybe_remove_back_spare();
2081 56 : }
2082 :
2083 : // move assign [__f, __l) to [__r, __r + (__l-__f)).
2084 : // If __vt points into [__f, __l), then subtract (__f - __r) from __vt.
2085 : template <class _Tp, class _Allocator>
2086 : typename deque<_Tp, _Allocator>::iterator
2087 : deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r,
2088 : const_pointer& __vt)
2089 : {
2090 : // as if
2091 : // for (; __f != __l; ++__f, ++__r)
2092 : // *__r = _VSTD::move(*__f);
2093 : difference_type __n = __l - __f;
2094 : while (__n > 0)
2095 : {
2096 : pointer __fb = __f.__ptr_;
2097 : pointer __fe = *__f.__m_iter_ + __block_size;
2098 : difference_type __bs = __fe - __fb;
2099 : if (__bs > __n)
2100 : {
2101 : __bs = __n;
2102 : __fe = __fb + __bs;
2103 : }
2104 : if (__fb <= __vt && __vt < __fe)
2105 : __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;
2106 : __r = _VSTD::move(__fb, __fe, __r);
2107 : __n -= __bs;
2108 : __f += __bs;
2109 : }
2110 : return __r;
2111 : }
2112 :
2113 : // move assign [__f, __l) to [__r - (__l-__f), __r) backwards.
2114 : // If __vt points into [__f, __l), then add (__r - __l) to __vt.
2115 : template <class _Tp, class _Allocator>
2116 : typename deque<_Tp, _Allocator>::iterator
2117 : deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r,
2118 : const_pointer& __vt)
2119 : {
2120 : // as if
2121 : // while (__f != __l)
2122 : // *--__r = _VSTD::move(*--__l);
2123 : difference_type __n = __l - __f;
2124 : while (__n > 0)
2125 : {
2126 : --__l;
2127 : pointer __lb = *__l.__m_iter_;
2128 : pointer __le = __l.__ptr_ + 1;
2129 : difference_type __bs = __le - __lb;
2130 : if (__bs > __n)
2131 : {
2132 : __bs = __n;
2133 : __lb = __le - __bs;
2134 : }
2135 : if (__lb <= __vt && __vt < __le)
2136 : __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_;
2137 : __r = _VSTD::move_backward(__lb, __le, __r);
2138 : __n -= __bs;
2139 : __l -= __bs - 1;
2140 : }
2141 : return __r;
2142 : }
2143 :
2144 : // move construct [__f, __l) to [__r, __r + (__l-__f)).
2145 : // If __vt points into [__f, __l), then add (__r - __f) to __vt.
2146 : template <class _Tp, class _Allocator>
2147 : void
2148 : deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l,
2149 : iterator __r, const_pointer& __vt)
2150 : {
2151 : allocator_type& __a = __alloc();
2152 : // as if
2153 : // for (; __f != __l; ++__r, ++__f, ++__size())
2154 : // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f));
2155 : difference_type __n = __l - __f;
2156 : while (__n > 0)
2157 : {
2158 : pointer __fb = __f.__ptr_;
2159 : pointer __fe = *__f.__m_iter_ + __block_size;
2160 : difference_type __bs = __fe - __fb;
2161 : if (__bs > __n)
2162 : {
2163 : __bs = __n;
2164 : __fe = __fb + __bs;
2165 : }
2166 : if (__fb <= __vt && __vt < __fe)
2167 : __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;
2168 : for (; __fb != __fe; ++__fb, ++__r, ++__size())
2169 : __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb));
2170 : __n -= __bs;
2171 : __f += __bs;
2172 : }
2173 : }
2174 :
2175 : // move construct [__f, __l) to [__r - (__l-__f), __r) backwards.
2176 : // If __vt points into [__f, __l), then subtract (__l - __r) from __vt.
2177 : template <class _Tp, class _Allocator>
2178 : void
2179 : deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l,
2180 : iterator __r, const_pointer& __vt)
2181 : {
2182 : allocator_type& __a = __alloc();
2183 : // as if
2184 : // for (iterator __j = __l; __j != __f;)
2185 : // {
2186 : // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j));
2187 : // --__start_;
2188 : // ++__size();
2189 : // }
2190 : difference_type __n = __l - __f;
2191 : while (__n > 0)
2192 : {
2193 : --__l;
2194 : pointer __lb = *__l.__m_iter_;
2195 : pointer __le = __l.__ptr_ + 1;
2196 : difference_type __bs = __le - __lb;
2197 : if (__bs > __n)
2198 : {
2199 : __bs = __n;
2200 : __lb = __le - __bs;
2201 : }
2202 : if (__lb <= __vt && __vt < __le)
2203 : __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;
2204 : while (__le != __lb)
2205 : {
2206 : __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le));
2207 : --__start_;
2208 : ++__size();
2209 : }
2210 : __n -= __bs;
2211 : __l -= __bs - 1;
2212 : }
2213 : }
2214 :
2215 : template <class _Tp, class _Allocator>
2216 : typename deque<_Tp, _Allocator>::iterator
2217 : deque<_Tp, _Allocator>::erase(const_iterator __f)
2218 : {
2219 : iterator __b = begin();
2220 : difference_type __pos = __f - __b;
2221 : iterator __p = __b + __pos;
2222 : allocator_type& __a = __alloc();
2223 : if (static_cast<size_t>(__pos) <= (size() - 1) / 2)
2224 : { // erase from front
2225 : _VSTD::move_backward(__b, __p, _VSTD::next(__p));
2226 : __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2227 : --__size();
2228 : ++__start_;
2229 : __maybe_remove_front_spare();
2230 : }
2231 : else
2232 : { // erase from back
2233 : iterator __i = _VSTD::move(_VSTD::next(__p), end(), __p);
2234 : __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2235 : --__size();
2236 : __maybe_remove_back_spare();
2237 : }
2238 : return begin() + __pos;
2239 : }
2240 :
2241 : template <class _Tp, class _Allocator>
2242 : typename deque<_Tp, _Allocator>::iterator
2243 : deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
2244 : {
2245 : difference_type __n = __l - __f;
2246 : iterator __b = begin();
2247 : difference_type __pos = __f - __b;
2248 : iterator __p = __b + __pos;
2249 : if (__n > 0)
2250 : {
2251 : allocator_type& __a = __alloc();
2252 : if (static_cast<size_t>(__pos) <= (size() - __n) / 2)
2253 : { // erase from front
2254 : iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
2255 : for (; __b != __i; ++__b)
2256 : __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2257 : __size() -= __n;
2258 : __start_ += __n;
2259 : while (__maybe_remove_front_spare()) {
2260 : }
2261 : }
2262 : else
2263 : { // erase from back
2264 : iterator __i = _VSTD::move(__p + __n, end(), __p);
2265 : for (iterator __e = end(); __i != __e; ++__i)
2266 : __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2267 : __size() -= __n;
2268 : while (__maybe_remove_back_spare()) {
2269 : }
2270 : }
2271 : }
2272 : return begin() + __pos;
2273 : }
2274 :
2275 : template <class _Tp, class _Allocator>
2276 : void
2277 : deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
2278 : {
2279 : iterator __e = end();
2280 : difference_type __n = __e - __f;
2281 : if (__n > 0)
2282 : {
2283 : allocator_type& __a = __alloc();
2284 : iterator __b = begin();
2285 : difference_type __pos = __f - __b;
2286 : for (iterator __p = __b + __pos; __p != __e; ++__p)
2287 : __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
2288 : __size() -= __n;
2289 : while (__maybe_remove_back_spare()) {
2290 : }
2291 : }
2292 : }
2293 :
2294 : template <class _Tp, class _Allocator>
2295 : inline
2296 : void
2297 : deque<_Tp, _Allocator>::swap(deque& __c)
2298 : #if _LIBCPP_STD_VER >= 14
2299 : _NOEXCEPT
2300 : #else
2301 : _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2302 : __is_nothrow_swappable<allocator_type>::value)
2303 : #endif
2304 : {
2305 : __map_.swap(__c.__map_);
2306 : _VSTD::swap(__start_, __c.__start_);
2307 : _VSTD::swap(__size(), __c.__size());
2308 : _VSTD::__swap_allocator(__alloc(), __c.__alloc());
2309 : }
2310 :
2311 : template <class _Tp, class _Allocator>
2312 : inline
2313 : void
2314 : deque<_Tp, _Allocator>::clear() _NOEXCEPT
2315 : {
2316 : allocator_type& __a = __alloc();
2317 : for (iterator __i = begin(), __e = end(); __i != __e; ++__i)
2318 : __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2319 : __size() = 0;
2320 : while (__map_.size() > 2)
2321 : {
2322 : __alloc_traits::deallocate(__a, __map_.front(), __block_size);
2323 : __map_.pop_front();
2324 : }
2325 : switch (__map_.size())
2326 : {
2327 : case 1:
2328 : __start_ = __block_size / 2;
2329 : break;
2330 : case 2:
2331 : __start_ = __block_size;
2332 : break;
2333 : }
2334 : }
2335 :
2336 : template <class _Tp, class _Allocator>
2337 : inline _LIBCPP_HIDE_FROM_ABI
2338 : bool
2339 : operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2340 : {
2341 : const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();
2342 : return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2343 : }
2344 :
2345 : template <class _Tp, class _Allocator>
2346 : inline _LIBCPP_HIDE_FROM_ABI
2347 : bool
2348 : operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2349 : {
2350 : return !(__x == __y);
2351 : }
2352 :
2353 : template <class _Tp, class _Allocator>
2354 : inline _LIBCPP_HIDE_FROM_ABI
2355 : bool
2356 : operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2357 : {
2358 : return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2359 : }
2360 :
2361 : template <class _Tp, class _Allocator>
2362 : inline _LIBCPP_HIDE_FROM_ABI
2363 : bool
2364 : operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2365 : {
2366 : return __y < __x;
2367 : }
2368 :
2369 : template <class _Tp, class _Allocator>
2370 : inline _LIBCPP_HIDE_FROM_ABI
2371 : bool
2372 : operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2373 : {
2374 : return !(__x < __y);
2375 : }
2376 :
2377 : template <class _Tp, class _Allocator>
2378 : inline _LIBCPP_HIDE_FROM_ABI
2379 : bool
2380 : operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2381 : {
2382 : return !(__y < __x);
2383 : }
2384 :
2385 : template <class _Tp, class _Allocator>
2386 : inline _LIBCPP_HIDE_FROM_ABI
2387 : void
2388 : swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y)
2389 : _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2390 : {
2391 : __x.swap(__y);
2392 : }
2393 :
2394 : #if _LIBCPP_STD_VER > 17
2395 : template <class _Tp, class _Allocator, class _Up>
2396 : inline _LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::size_type
2397 : erase(deque<_Tp, _Allocator>& __c, const _Up& __v) {
2398 : auto __old_size = __c.size();
2399 : __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end());
2400 : return __old_size - __c.size();
2401 : }
2402 :
2403 : template <class _Tp, class _Allocator, class _Predicate>
2404 : inline _LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::size_type
2405 : erase_if(deque<_Tp, _Allocator>& __c, _Predicate __pred) {
2406 : auto __old_size = __c.size();
2407 : __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end());
2408 : return __old_size - __c.size();
2409 : }
2410 :
2411 : template <>
2412 : inline constexpr bool __format::__enable_insertable<std::deque<char>> = true;
2413 : #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
2414 : template <>
2415 : inline constexpr bool __format::__enable_insertable<std::deque<wchar_t>> = true;
2416 : #endif
2417 :
2418 : #endif // _LIBCPP_STD_VER > 17
2419 :
2420 : _LIBCPP_END_NAMESPACE_STD
2421 :
2422 : #if _LIBCPP_STD_VER > 14
2423 : _LIBCPP_BEGIN_NAMESPACE_STD
2424 : namespace pmr {
2425 : template <class _ValueT>
2426 : using deque = std::deque<_ValueT, polymorphic_allocator<_ValueT>>;
2427 : } // namespace pmr
2428 : _LIBCPP_END_NAMESPACE_STD
2429 : #endif
2430 :
2431 : _LIBCPP_POP_MACROS
2432 :
2433 : #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2434 : # include <algorithm>
2435 : # include <atomic>
2436 : # include <concepts>
2437 : # include <functional>
2438 : # include <iosfwd>
2439 : # include <iterator>
2440 : # include <typeinfo>
2441 : #endif
2442 :
2443 : #endif // _LIBCPP_DEQUE
|
