2 //===---------------------------- deque -----------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
20 template <class T, class Allocator = allocator<T> >
26 typedef Allocator allocator_type;
28 typedef typename allocator_type::reference reference;
29 typedef typename allocator_type::const_reference const_reference;
30 typedef implementation-defined iterator;
31 typedef implementation-defined const_iterator;
32 typedef typename allocator_type::size_type size_type;
33 typedef typename allocator_type::difference_type difference_type;
35 typedef typename allocator_type::pointer pointer;
36 typedef typename allocator_type::const_pointer const_pointer;
37 typedef std::reverse_iterator<iterator> reverse_iterator;
38 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
40 // construct/copy/destroy:
41 deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);
42 explicit deque(const allocator_type& a);
43 explicit deque(size_type n);
44 explicit deque(size_type n, const allocator_type& a); // C++14
45 deque(size_type n, const value_type& v);
46 deque(size_type n, const value_type& v, const allocator_type& a);
47 template <class InputIterator>
48 deque(InputIterator f, InputIterator l);
49 template <class InputIterator>
50 deque(InputIterator f, InputIterator l, const allocator_type& a);
51 deque(const deque& c);
53 noexcept(is_nothrow_move_constructible<allocator_type>::value);
54 deque(initializer_list<value_type> il, const Allocator& a = allocator_type());
55 deque(const deque& c, const allocator_type& a);
56 deque(deque&& c, const allocator_type& a);
59 deque& operator=(const deque& c);
60 deque& operator=(deque&& c)
62 allocator_type::propagate_on_container_move_assignment::value &&
63 is_nothrow_move_assignable<allocator_type>::value);
64 deque& operator=(initializer_list<value_type> il);
66 template <class InputIterator>
67 void assign(InputIterator f, InputIterator l);
68 void assign(size_type n, const value_type& v);
69 void assign(initializer_list<value_type> il);
71 allocator_type get_allocator() const noexcept;
75 iterator begin() noexcept;
76 const_iterator begin() const noexcept;
77 iterator end() noexcept;
78 const_iterator end() const noexcept;
80 reverse_iterator rbegin() noexcept;
81 const_reverse_iterator rbegin() const noexcept;
82 reverse_iterator rend() noexcept;
83 const_reverse_iterator rend() const noexcept;
85 const_iterator cbegin() const noexcept;
86 const_iterator cend() const noexcept;
87 const_reverse_iterator crbegin() const noexcept;
88 const_reverse_iterator crend() const noexcept;
91 size_type size() const noexcept;
92 size_type max_size() const noexcept;
93 void resize(size_type n);
94 void resize(size_type n, const value_type& v);
96 bool empty() const noexcept;
99 reference operator[](size_type i);
100 const_reference operator[](size_type i) const;
101 reference at(size_type i);
102 const_reference at(size_type i) const;
104 const_reference front() const;
106 const_reference back() const;
109 void push_front(const value_type& v);
110 void push_front(value_type&& v);
111 void push_back(const value_type& v);
112 void push_back(value_type&& v);
113 template <class... Args> void emplace_front(Args&&... args);
114 template <class... Args> void emplace_back(Args&&... args);
115 template <class... Args> iterator emplace(const_iterator p, Args&&... args);
116 iterator insert(const_iterator p, const value_type& v);
117 iterator insert(const_iterator p, value_type&& v);
118 iterator insert(const_iterator p, size_type n, const value_type& v);
119 template <class InputIterator>
120 iterator insert(const_iterator p, InputIterator f, InputIterator l);
121 iterator insert(const_iterator p, initializer_list<value_type> il);
124 iterator erase(const_iterator p);
125 iterator erase(const_iterator f, const_iterator l);
127 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
128 void clear() noexcept;
131 template <class T, class Allocator>
132 bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
133 template <class T, class Allocator>
134 bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
135 template <class T, class Allocator>
136 bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
137 template <class T, class Allocator>
138 bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
139 template <class T, class Allocator>
140 bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
141 template <class T, class Allocator>
142 bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
144 // specialized algorithms:
145 template <class T, class Allocator>
146 void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)
147 noexcept(noexcept(x.swap(y)));
153 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
154 #pragma GCC system_header
158 #include <__split_buffer>
159 #include <type_traits>
160 #include <initializer_list>
165 #include <__undef_min_max>
167 _LIBCPP_BEGIN_NAMESPACE_STD
169 template <class _Tp, class _Allocator> class __deque_base;
170 template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY deque;
172 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
173 class _DiffType, _DiffType _BlockSize>
174 class _LIBCPP_TYPE_VIS_ONLY __deque_iterator;
176 template <class _RAIter,
177 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
178 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
181 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
182 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
184 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
185 class _OutputIterator>
187 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
188 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
189 _OutputIterator __r);
191 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
192 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
193 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
194 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
195 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
196 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
198 template <class _RAIter,
199 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
200 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
201 copy_backward(_RAIter __f,
203 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
204 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
206 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
207 class _OutputIterator>
209 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
210 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
211 _OutputIterator __r);
213 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
214 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
215 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
216 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
217 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
218 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
220 template <class _RAIter,
221 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
222 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
225 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
226 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
228 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
229 class _OutputIterator>
231 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
232 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
233 _OutputIterator __r);
235 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
236 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
237 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
238 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
239 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
240 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
242 template <class _RAIter,
243 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
244 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
245 move_backward(_RAIter __f,
247 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
248 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
250 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
251 class _OutputIterator>
253 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
254 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
255 _OutputIterator __r);
257 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
258 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
259 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
260 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
261 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
262 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
264 template <class _ValueType, class _DiffType>
265 struct __deque_block_size {
266 static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;
269 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
270 class _DiffType, _DiffType _BS =
271 #ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
272 // Keep template parameter to avoid changing all template declarations thoughout
276 __deque_block_size<_ValueType, _DiffType>::value
279 class _LIBCPP_TYPE_VIS_ONLY __deque_iterator
281 typedef _MapPointer __map_iterator;
283 typedef _Pointer pointer;
284 typedef _DiffType difference_type;
286 __map_iterator __m_iter_;
289 static const difference_type __block_size;
291 typedef _ValueType value_type;
292 typedef random_access_iterator_tag iterator_category;
293 typedef _Reference reference;
295 _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT
296 #if _LIBCPP_STD_VER > 11
297 : __m_iter_(nullptr), __ptr_(nullptr)
301 template <class _Pp, class _Rp, class _MP>
302 _LIBCPP_INLINE_VISIBILITY
303 __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it,
304 typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT
305 : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}
307 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;}
308 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;}
310 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++()
312 if (++__ptr_ - *__m_iter_ == __block_size)
320 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator++(int)
322 __deque_iterator __tmp = *this;
327 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator--()
329 if (__ptr_ == *__m_iter_)
332 __ptr_ = *__m_iter_ + __block_size;
338 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int)
340 __deque_iterator __tmp = *this;
345 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n)
349 __n += __ptr_ - *__m_iter_;
352 __m_iter_ += __n / __block_size;
353 __ptr_ = *__m_iter_ + __n % __block_size;
357 difference_type __z = __block_size - 1 - __n;
358 __m_iter_ -= __z / __block_size;
359 __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);
365 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n)
367 return *this += -__n;
370 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const
372 __deque_iterator __t(*this);
377 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const
379 __deque_iterator __t(*this);
384 _LIBCPP_INLINE_VISIBILITY
385 friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it)
388 _LIBCPP_INLINE_VISIBILITY
389 friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y)
392 return (__x.__m_iter_ - __y.__m_iter_) * __block_size
393 + (__x.__ptr_ - *__x.__m_iter_)
394 - (__y.__ptr_ - *__y.__m_iter_);
398 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
399 {return *(*this + __n);}
401 _LIBCPP_INLINE_VISIBILITY friend
402 bool operator==(const __deque_iterator& __x, const __deque_iterator& __y)
403 {return __x.__ptr_ == __y.__ptr_;}
405 _LIBCPP_INLINE_VISIBILITY friend
406 bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y)
407 {return !(__x == __y);}
409 _LIBCPP_INLINE_VISIBILITY friend
410 bool operator<(const __deque_iterator& __x, const __deque_iterator& __y)
411 {return __x.__m_iter_ < __y.__m_iter_ ||
412 (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);}
414 _LIBCPP_INLINE_VISIBILITY friend
415 bool operator>(const __deque_iterator& __x, const __deque_iterator& __y)
418 _LIBCPP_INLINE_VISIBILITY friend
419 bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y)
420 {return !(__y < __x);}
422 _LIBCPP_INLINE_VISIBILITY friend
423 bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)
424 {return !(__x < __y);}
427 _LIBCPP_INLINE_VISIBILITY __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
428 : __m_iter_(__m), __ptr_(__p) {}
430 template <class _Tp, class _Ap> friend class __deque_base;
431 template <class _Tp, class _Ap> friend class _LIBCPP_TYPE_VIS_ONLY deque;
432 template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>
433 friend class _LIBCPP_TYPE_VIS_ONLY __deque_iterator;
435 template <class _RAIter,
436 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
438 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
441 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
442 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
444 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
445 class _OutputIterator>
448 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
449 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
450 _OutputIterator __r);
452 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
453 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
455 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
456 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
457 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
458 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
460 template <class _RAIter,
461 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
463 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
464 copy_backward(_RAIter __f,
466 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
467 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
469 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
470 class _OutputIterator>
473 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
474 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
475 _OutputIterator __r);
477 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
478 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
480 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
481 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
482 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
483 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
485 template <class _RAIter,
486 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
488 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
491 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
492 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
494 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
495 class _OutputIterator>
498 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
499 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
500 _OutputIterator __r);
502 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
503 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
505 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
506 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
507 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
508 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
510 template <class _RAIter,
511 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
513 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
514 move_backward(_RAIter __f,
516 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
517 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
519 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
520 class _OutputIterator>
523 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
524 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
525 _OutputIterator __r);
527 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
528 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
530 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
531 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
532 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
533 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
536 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
537 class _DiffType, _DiffType _BlockSize>
538 const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
539 _DiffType, _BlockSize>::__block_size =
540 __deque_block_size<_ValueType, _DiffType>::value;
544 template <class _RAIter,
545 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
546 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
549 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
550 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
552 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
553 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
554 const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
557 pointer __rb = __r.__ptr_;
558 pointer __re = *__r.__m_iter_ + __block_size;
559 difference_type __bs = __re - __rb;
560 difference_type __n = __l - __f;
567 _VSTD::copy(__f, __m, __rb);
574 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
575 class _OutputIterator>
577 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
578 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
581 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
582 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
583 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
584 difference_type __n = __l - __f;
587 pointer __fb = __f.__ptr_;
588 pointer __fe = *__f.__m_iter_ + __block_size;
589 difference_type __bs = __fe - __fb;
595 __r = _VSTD::copy(__fb, __fe, __r);
602 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
603 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
604 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
605 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
606 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
607 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
609 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
610 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
611 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
612 difference_type __n = __l - __f;
615 pointer __fb = __f.__ptr_;
616 pointer __fe = *__f.__m_iter_ + __block_size;
617 difference_type __bs = __fe - __fb;
623 __r = _VSTD::copy(__fb, __fe, __r);
632 template <class _RAIter,
633 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
634 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
635 copy_backward(_RAIter __f,
637 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
638 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
640 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
641 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
644 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
645 pointer __rb = *__rp.__m_iter_;
646 pointer __re = __rp.__ptr_ + 1;
647 difference_type __bs = __re - __rb;
648 difference_type __n = __l - __f;
655 _VSTD::copy_backward(__m, __l, __re);
662 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
663 class _OutputIterator>
665 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
666 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
669 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
670 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
671 difference_type __n = __l - __f;
675 pointer __lb = *__l.__m_iter_;
676 pointer __le = __l.__ptr_ + 1;
677 difference_type __bs = __le - __lb;
683 __r = _VSTD::copy_backward(__lb, __le, __r);
690 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
691 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
692 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
693 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
694 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
695 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
697 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
698 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
699 difference_type __n = __l - __f;
703 pointer __lb = *__l.__m_iter_;
704 pointer __le = __l.__ptr_ + 1;
705 difference_type __bs = __le - __lb;
711 __r = _VSTD::copy_backward(__lb, __le, __r);
720 template <class _RAIter,
721 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
722 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
725 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
726 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
728 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
729 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
730 const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
733 pointer __rb = __r.__ptr_;
734 pointer __re = *__r.__m_iter_ + __block_size;
735 difference_type __bs = __re - __rb;
736 difference_type __n = __l - __f;
743 _VSTD::move(__f, __m, __rb);
750 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
751 class _OutputIterator>
753 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
754 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
757 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
758 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
759 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
760 difference_type __n = __l - __f;
763 pointer __fb = __f.__ptr_;
764 pointer __fe = *__f.__m_iter_ + __block_size;
765 difference_type __bs = __fe - __fb;
771 __r = _VSTD::move(__fb, __fe, __r);
778 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
779 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
780 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
781 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
782 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
783 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
785 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
786 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
787 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
788 difference_type __n = __l - __f;
791 pointer __fb = __f.__ptr_;
792 pointer __fe = *__f.__m_iter_ + __block_size;
793 difference_type __bs = __fe - __fb;
799 __r = _VSTD::move(__fb, __fe, __r);
808 template <class _RAIter,
809 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
810 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
811 move_backward(_RAIter __f,
813 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
814 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
816 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
817 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
820 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
821 pointer __rb = *__rp.__m_iter_;
822 pointer __re = __rp.__ptr_ + 1;
823 difference_type __bs = __re - __rb;
824 difference_type __n = __l - __f;
831 _VSTD::move_backward(__m, __l, __re);
838 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
839 class _OutputIterator>
841 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
842 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
845 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
846 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
847 difference_type __n = __l - __f;
851 pointer __lb = *__l.__m_iter_;
852 pointer __le = __l.__ptr_ + 1;
853 difference_type __bs = __le - __lb;
859 __r = _VSTD::move_backward(__lb, __le, __r);
866 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
867 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
868 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
869 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
870 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
871 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
873 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
874 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
875 difference_type __n = __l - __f;
879 pointer __lb = *__l.__m_iter_;
880 pointer __le = __l.__ptr_ + 1;
881 difference_type __bs = __le - __lb;
887 __r = _VSTD::move_backward(__lb, __le, __r);
895 class __deque_base_common
898 void __throw_length_error() const;
899 void __throw_out_of_range() const;
904 __deque_base_common<__b>::__throw_length_error() const
906 #ifndef _LIBCPP_NO_EXCEPTIONS
907 throw length_error("deque");
913 __deque_base_common<__b>::__throw_out_of_range() const
915 #ifndef _LIBCPP_NO_EXCEPTIONS
916 throw out_of_range("deque");
920 template <class _Tp, class _Allocator>
922 : protected __deque_base_common<true>
924 __deque_base(const __deque_base& __c);
925 __deque_base& operator=(const __deque_base& __c);
927 typedef _Tp value_type;
928 typedef _Allocator allocator_type;
929 typedef allocator_traits<allocator_type> __alloc_traits;
930 typedef value_type& reference;
931 typedef const value_type& const_reference;
932 typedef typename __alloc_traits::size_type size_type;
933 typedef typename __alloc_traits::difference_type difference_type;
934 typedef typename __alloc_traits::pointer pointer;
935 typedef typename __alloc_traits::const_pointer const_pointer;
937 static const difference_type __block_size;
939 typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator;
940 typedef allocator_traits<__pointer_allocator> __map_traits;
941 typedef typename __map_traits::pointer __map_pointer;
942 typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator;
943 typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;
944 typedef __split_buffer<pointer, __pointer_allocator> __map;
946 typedef __deque_iterator<value_type, pointer, reference, __map_pointer,
947 difference_type> iterator;
948 typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
949 difference_type> const_iterator;
953 __compressed_pair<size_type, allocator_type> __size_;
955 iterator begin() _NOEXCEPT;
956 const_iterator begin() const _NOEXCEPT;
957 iterator end() _NOEXCEPT;
958 const_iterator end() const _NOEXCEPT;
960 _LIBCPP_INLINE_VISIBILITY size_type& size() {return __size_.first();}
961 _LIBCPP_INLINE_VISIBILITY
962 const size_type& size() const _NOEXCEPT {return __size_.first();}
963 _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __size_.second();}
964 _LIBCPP_INLINE_VISIBILITY
965 const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();}
967 _LIBCPP_INLINE_VISIBILITY
969 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
970 _LIBCPP_INLINE_VISIBILITY
971 explicit __deque_base(const allocator_type& __a);
975 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
977 __deque_base(__deque_base&& __c)
978 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
979 __deque_base(__deque_base&& __c, const allocator_type& __a);
981 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
982 void swap(__deque_base& __c)
983 #if _LIBCPP_STD_VER >= 14
986 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
987 __is_nothrow_swappable<allocator_type>::value);
990 void clear() _NOEXCEPT;
992 bool __invariants() const;
994 _LIBCPP_INLINE_VISIBILITY
995 void __move_assign(__deque_base& __c)
996 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
997 is_nothrow_move_assignable<allocator_type>::value)
999 __map_ = _VSTD::move(__c.__map_);
1000 __start_ = __c.__start_;
1001 size() = __c.size();
1002 __move_assign_alloc(__c);
1003 __c.__start_ = __c.size() = 0;
1006 _LIBCPP_INLINE_VISIBILITY
1007 void __move_assign_alloc(__deque_base& __c)
1008 _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
1009 is_nothrow_move_assignable<allocator_type>::value)
1010 {__move_assign_alloc(__c, integral_constant<bool,
1011 __alloc_traits::propagate_on_container_move_assignment::value>());}
1014 _LIBCPP_INLINE_VISIBILITY
1015 void __move_assign_alloc(__deque_base& __c, true_type)
1016 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1018 __alloc() = _VSTD::move(__c.__alloc());
1021 _LIBCPP_INLINE_VISIBILITY
1022 void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT
1026 template <class _Tp, class _Allocator>
1027 const typename __deque_base<_Tp, _Allocator>::difference_type
1028 __deque_base<_Tp, _Allocator>::__block_size =
1029 __deque_block_size<value_type, difference_type>::value;
1031 template <class _Tp, class _Allocator>
1033 __deque_base<_Tp, _Allocator>::__invariants() const
1035 if (!__map_.__invariants())
1037 if (__map_.size() >= size_type(-1) / __block_size)
1039 for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();
1041 if (*__i == nullptr)
1043 if (__map_.size() != 0)
1045 if (size() >= __map_.size() * __block_size)
1047 if (__start_ >= __map_.size() * __block_size - size())
1060 template <class _Tp, class _Allocator>
1061 typename __deque_base<_Tp, _Allocator>::iterator
1062 __deque_base<_Tp, _Allocator>::begin() _NOEXCEPT
1064 __map_pointer __mp = __map_.begin() + __start_ / __block_size;
1065 return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1068 template <class _Tp, class _Allocator>
1069 typename __deque_base<_Tp, _Allocator>::const_iterator
1070 __deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT
1072 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);
1073 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1076 template <class _Tp, class _Allocator>
1077 typename __deque_base<_Tp, _Allocator>::iterator
1078 __deque_base<_Tp, _Allocator>::end() _NOEXCEPT
1080 size_type __p = size() + __start_;
1081 __map_pointer __mp = __map_.begin() + __p / __block_size;
1082 return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1085 template <class _Tp, class _Allocator>
1086 typename __deque_base<_Tp, _Allocator>::const_iterator
1087 __deque_base<_Tp, _Allocator>::end() const _NOEXCEPT
1089 size_type __p = size() + __start_;
1090 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);
1091 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1094 template <class _Tp, class _Allocator>
1096 __deque_base<_Tp, _Allocator>::__deque_base()
1097 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1098 : __start_(0), __size_(0) {}
1100 template <class _Tp, class _Allocator>
1102 __deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a)
1103 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}
1105 template <class _Tp, class _Allocator>
1106 __deque_base<_Tp, _Allocator>::~__deque_base()
1109 typename __map::iterator __i = __map_.begin();
1110 typename __map::iterator __e = __map_.end();
1111 for (; __i != __e; ++__i)
1112 __alloc_traits::deallocate(__alloc(), *__i, __block_size);
1115 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1117 template <class _Tp, class _Allocator>
1118 __deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c)
1119 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1120 : __map_(_VSTD::move(__c.__map_)),
1121 __start_(_VSTD::move(__c.__start_)),
1122 __size_(_VSTD::move(__c.__size_))
1128 template <class _Tp, class _Allocator>
1129 __deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a)
1130 : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)),
1131 __start_(_VSTD::move(__c.__start_)),
1132 __size_(_VSTD::move(__c.size()), __a)
1134 if (__a == __c.__alloc())
1147 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1149 template <class _Tp, class _Allocator>
1151 __deque_base<_Tp, _Allocator>::swap(__deque_base& __c)
1152 #if _LIBCPP_STD_VER >= 14
1155 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1156 __is_nothrow_swappable<allocator_type>::value)
1159 __map_.swap(__c.__map_);
1160 _VSTD::swap(__start_, __c.__start_);
1161 _VSTD::swap(size(), __c.size());
1162 __swap_allocator(__alloc(), __c.__alloc());
1165 template <class _Tp, class _Allocator>
1167 __deque_base<_Tp, _Allocator>::clear() _NOEXCEPT
1169 allocator_type& __a = __alloc();
1170 for (iterator __i = begin(), __e = end(); __i != __e; ++__i)
1171 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
1173 while (__map_.size() > 2)
1175 __alloc_traits::deallocate(__a, __map_.front(), __block_size);
1178 switch (__map_.size())
1181 __start_ = __block_size / 2;
1184 __start_ = __block_size;
1189 template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
1190 class _LIBCPP_TYPE_VIS_ONLY deque
1191 : private __deque_base<_Tp, _Allocator>
1196 typedef _Tp value_type;
1197 typedef _Allocator allocator_type;
1199 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1200 "Allocator::value_type must be same type as value_type");
1202 typedef __deque_base<value_type, allocator_type> __base;
1204 typedef typename __base::__alloc_traits __alloc_traits;
1205 typedef typename __base::reference reference;
1206 typedef typename __base::const_reference const_reference;
1207 typedef typename __base::iterator iterator;
1208 typedef typename __base::const_iterator const_iterator;
1209 typedef typename __base::size_type size_type;
1210 typedef typename __base::difference_type difference_type;
1212 typedef typename __base::pointer pointer;
1213 typedef typename __base::const_pointer const_pointer;
1214 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1215 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1217 // construct/copy/destroy:
1218 _LIBCPP_INLINE_VISIBILITY
1220 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1222 _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {}
1223 explicit deque(size_type __n);
1224 #if _LIBCPP_STD_VER > 11
1225 explicit deque(size_type __n, const _Allocator& __a);
1227 deque(size_type __n, const value_type& __v);
1228 deque(size_type __n, const value_type& __v, const allocator_type& __a);
1229 template <class _InputIter>
1230 deque(_InputIter __f, _InputIter __l,
1231 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1232 template <class _InputIter>
1233 deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1234 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1235 deque(const deque& __c);
1236 deque(const deque& __c, const allocator_type& __a);
1237 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1238 deque(initializer_list<value_type> __il);
1239 deque(initializer_list<value_type> __il, const allocator_type& __a);
1240 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1242 deque& operator=(const deque& __c);
1243 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1244 _LIBCPP_INLINE_VISIBILITY
1245 deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
1246 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1248 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1249 _LIBCPP_INLINE_VISIBILITY
1250 deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
1251 _LIBCPP_INLINE_VISIBILITY
1252 deque(deque&& __c, const allocator_type& __a);
1253 _LIBCPP_INLINE_VISIBILITY
1254 deque& operator=(deque&& __c)
1255 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1256 is_nothrow_move_assignable<allocator_type>::value);
1257 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1259 template <class _InputIter>
1260 void assign(_InputIter __f, _InputIter __l,
1261 typename enable_if<__is_input_iterator<_InputIter>::value &&
1262 !__is_random_access_iterator<_InputIter>::value>::type* = 0);
1263 template <class _RAIter>
1264 void assign(_RAIter __f, _RAIter __l,
1265 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
1266 void assign(size_type __n, const value_type& __v);
1267 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1268 _LIBCPP_INLINE_VISIBILITY
1269 void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
1270 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1272 _LIBCPP_INLINE_VISIBILITY
1273 allocator_type get_allocator() const _NOEXCEPT;
1277 _LIBCPP_INLINE_VISIBILITY
1278 iterator begin() _NOEXCEPT {return __base::begin();}
1279 _LIBCPP_INLINE_VISIBILITY
1280 const_iterator begin() const _NOEXCEPT {return __base::begin();}
1281 _LIBCPP_INLINE_VISIBILITY
1282 iterator end() _NOEXCEPT {return __base::end();}
1283 _LIBCPP_INLINE_VISIBILITY
1284 const_iterator end() const _NOEXCEPT {return __base::end();}
1286 _LIBCPP_INLINE_VISIBILITY
1287 reverse_iterator rbegin() _NOEXCEPT
1288 {return reverse_iterator(__base::end());}
1289 _LIBCPP_INLINE_VISIBILITY
1290 const_reverse_iterator rbegin() const _NOEXCEPT
1291 {return const_reverse_iterator(__base::end());}
1292 _LIBCPP_INLINE_VISIBILITY
1293 reverse_iterator rend() _NOEXCEPT
1294 {return reverse_iterator(__base::begin());}
1295 _LIBCPP_INLINE_VISIBILITY
1296 const_reverse_iterator rend() const _NOEXCEPT
1297 {return const_reverse_iterator(__base::begin());}
1299 _LIBCPP_INLINE_VISIBILITY
1300 const_iterator cbegin() const _NOEXCEPT
1301 {return __base::begin();}
1302 _LIBCPP_INLINE_VISIBILITY
1303 const_iterator cend() const _NOEXCEPT
1304 {return __base::end();}
1305 _LIBCPP_INLINE_VISIBILITY
1306 const_reverse_iterator crbegin() const _NOEXCEPT
1307 {return const_reverse_iterator(__base::end());}
1308 _LIBCPP_INLINE_VISIBILITY
1309 const_reverse_iterator crend() const _NOEXCEPT
1310 {return const_reverse_iterator(__base::begin());}
1313 _LIBCPP_INLINE_VISIBILITY
1314 size_type size() const _NOEXCEPT {return __base::size();}
1315 _LIBCPP_INLINE_VISIBILITY
1316 size_type max_size() const _NOEXCEPT
1317 {return __alloc_traits::max_size(__base::__alloc());}
1318 void resize(size_type __n);
1319 void resize(size_type __n, const value_type& __v);
1320 void shrink_to_fit() _NOEXCEPT;
1321 _LIBCPP_INLINE_VISIBILITY
1322 bool empty() const _NOEXCEPT {return __base::size() == 0;}
1325 _LIBCPP_INLINE_VISIBILITY
1326 reference operator[](size_type __i);
1327 _LIBCPP_INLINE_VISIBILITY
1328 const_reference operator[](size_type __i) const;
1329 _LIBCPP_INLINE_VISIBILITY
1330 reference at(size_type __i);
1331 _LIBCPP_INLINE_VISIBILITY
1332 const_reference at(size_type __i) const;
1333 _LIBCPP_INLINE_VISIBILITY
1335 _LIBCPP_INLINE_VISIBILITY
1336 const_reference front() const;
1337 _LIBCPP_INLINE_VISIBILITY
1339 _LIBCPP_INLINE_VISIBILITY
1340 const_reference back() const;
1342 // 23.2.2.3 modifiers:
1343 void push_front(const value_type& __v);
1344 void push_back(const value_type& __v);
1345 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1346 #ifndef _LIBCPP_HAS_NO_VARIADICS
1347 template <class... _Args> void emplace_front(_Args&&... __args);
1348 template <class... _Args> void emplace_back(_Args&&... __args);
1349 template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args);
1350 #endif // _LIBCPP_HAS_NO_VARIADICS
1351 void push_front(value_type&& __v);
1352 void push_back(value_type&& __v);
1353 iterator insert(const_iterator __p, value_type&& __v);
1354 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1355 iterator insert(const_iterator __p, const value_type& __v);
1356 iterator insert(const_iterator __p, size_type __n, const value_type& __v);
1357 template <class _InputIter>
1358 iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
1359 typename enable_if<__is_input_iterator<_InputIter>::value
1360 &&!__is_forward_iterator<_InputIter>::value>::type* = 0);
1361 template <class _ForwardIterator>
1362 iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
1363 typename enable_if<__is_forward_iterator<_ForwardIterator>::value
1364 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type* = 0);
1365 template <class _BiIter>
1366 iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
1367 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type* = 0);
1368 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1369 _LIBCPP_INLINE_VISIBILITY
1370 iterator insert(const_iterator __p, initializer_list<value_type> __il)
1371 {return insert(__p, __il.begin(), __il.end());}
1372 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1375 iterator erase(const_iterator __p);
1376 iterator erase(const_iterator __f, const_iterator __l);
1378 _LIBCPP_INLINE_VISIBILITY
1379 void swap(deque& __c)
1380 #if _LIBCPP_STD_VER >= 14
1383 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1384 __is_nothrow_swappable<allocator_type>::value);
1386 _LIBCPP_INLINE_VISIBILITY
1387 void clear() _NOEXCEPT;
1389 _LIBCPP_INLINE_VISIBILITY
1390 bool __invariants() const {return __base::__invariants();}
1392 typedef typename __base::__map_const_pointer __map_const_pointer;
1394 _LIBCPP_INLINE_VISIBILITY
1395 static size_type __recommend_blocks(size_type __n)
1397 return __n / __base::__block_size + (__n % __base::__block_size != 0);
1399 _LIBCPP_INLINE_VISIBILITY
1400 size_type __capacity() const
1402 return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
1404 _LIBCPP_INLINE_VISIBILITY
1405 size_type __front_spare() const
1407 return __base::__start_;
1409 _LIBCPP_INLINE_VISIBILITY
1410 size_type __back_spare() const
1412 return __capacity() - (__base::__start_ + __base::size());
1415 template <class _InpIter>
1416 void __append(_InpIter __f, _InpIter __l,
1417 typename enable_if<__is_input_iterator<_InpIter>::value &&
1418 !__is_forward_iterator<_InpIter>::value>::type* = 0);
1419 template <class _ForIter>
1420 void __append(_ForIter __f, _ForIter __l,
1421 typename enable_if<__is_forward_iterator<_ForIter>::value>::type* = 0);
1422 void __append(size_type __n);
1423 void __append(size_type __n, const value_type& __v);
1424 void __erase_to_end(const_iterator __f);
1425 void __add_front_capacity();
1426 void __add_front_capacity(size_type __n);
1427 void __add_back_capacity();
1428 void __add_back_capacity(size_type __n);
1429 iterator __move_and_check(iterator __f, iterator __l, iterator __r,
1430 const_pointer& __vt);
1431 iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r,
1432 const_pointer& __vt);
1433 void __move_construct_and_check(iterator __f, iterator __l,
1434 iterator __r, const_pointer& __vt);
1435 void __move_construct_backward_and_check(iterator __f, iterator __l,
1436 iterator __r, const_pointer& __vt);
1438 _LIBCPP_INLINE_VISIBILITY
1439 void __copy_assign_alloc(const deque& __c)
1440 {__copy_assign_alloc(__c, integral_constant<bool,
1441 __alloc_traits::propagate_on_container_copy_assignment::value>());}
1443 _LIBCPP_INLINE_VISIBILITY
1444 void __copy_assign_alloc(const deque& __c, true_type)
1446 if (__base::__alloc() != __c.__alloc())
1451 __base::__alloc() = __c.__alloc();
1452 __base::__map_.__alloc() = __c.__map_.__alloc();
1455 _LIBCPP_INLINE_VISIBILITY
1456 void __copy_assign_alloc(const deque&, false_type)
1459 void __move_assign(deque& __c, true_type)
1460 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
1461 void __move_assign(deque& __c, false_type);
1464 template <class _Tp, class _Allocator>
1465 deque<_Tp, _Allocator>::deque(size_type __n)
1471 #if _LIBCPP_STD_VER > 11
1472 template <class _Tp, class _Allocator>
1473 deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a)
1481 template <class _Tp, class _Allocator>
1482 deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)
1488 template <class _Tp, class _Allocator>
1489 deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a)
1496 template <class _Tp, class _Allocator>
1497 template <class _InputIter>
1498 deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l,
1499 typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1504 template <class _Tp, class _Allocator>
1505 template <class _InputIter>
1506 deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1507 typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1513 template <class _Tp, class _Allocator>
1514 deque<_Tp, _Allocator>::deque(const deque& __c)
1515 : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))
1517 __append(__c.begin(), __c.end());
1520 template <class _Tp, class _Allocator>
1521 deque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a)
1524 __append(__c.begin(), __c.end());
1527 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1529 template <class _Tp, class _Allocator>
1530 deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)
1532 __append(__il.begin(), __il.end());
1535 template <class _Tp, class _Allocator>
1536 deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a)
1539 __append(__il.begin(), __il.end());
1542 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1544 template <class _Tp, class _Allocator>
1545 deque<_Tp, _Allocator>&
1546 deque<_Tp, _Allocator>::operator=(const deque& __c)
1550 __copy_assign_alloc(__c);
1551 assign(__c.begin(), __c.end());
1556 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1558 template <class _Tp, class _Allocator>
1560 deque<_Tp, _Allocator>::deque(deque&& __c)
1561 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1562 : __base(_VSTD::move(__c))
1566 template <class _Tp, class _Allocator>
1568 deque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a)
1569 : __base(_VSTD::move(__c), __a)
1571 if (__a != __c.__alloc())
1573 typedef move_iterator<iterator> _Ip;
1574 assign(_Ip(__c.begin()), _Ip(__c.end()));
1578 template <class _Tp, class _Allocator>
1580 deque<_Tp, _Allocator>&
1581 deque<_Tp, _Allocator>::operator=(deque&& __c)
1582 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1583 is_nothrow_move_assignable<allocator_type>::value)
1585 __move_assign(__c, integral_constant<bool,
1586 __alloc_traits::propagate_on_container_move_assignment::value>());
1590 template <class _Tp, class _Allocator>
1592 deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type)
1594 if (__base::__alloc() != __c.__alloc())
1596 typedef move_iterator<iterator> _Ip;
1597 assign(_Ip(__c.begin()), _Ip(__c.end()));
1600 __move_assign(__c, true_type());
1603 template <class _Tp, class _Allocator>
1605 deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type)
1606 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1610 __base::__move_assign(__c);
1613 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1615 template <class _Tp, class _Allocator>
1616 template <class _InputIter>
1618 deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
1619 typename enable_if<__is_input_iterator<_InputIter>::value &&
1620 !__is_random_access_iterator<_InputIter>::value>::type*)
1622 iterator __i = __base::begin();
1623 iterator __e = __base::end();
1624 for (; __f != __l && __i != __e; ++__f, (void) ++__i)
1629 __erase_to_end(__i);
1632 template <class _Tp, class _Allocator>
1633 template <class _RAIter>
1635 deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
1636 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
1638 if (static_cast<size_type>(__l - __f) > __base::size())
1640 _RAIter __m = __f + __base::size();
1641 _VSTD::copy(__f, __m, __base::begin());
1645 __erase_to_end(_VSTD::copy(__f, __l, __base::begin()));
1648 template <class _Tp, class _Allocator>
1650 deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
1652 if (__n > __base::size())
1654 _VSTD::fill_n(__base::begin(), __base::size(), __v);
1655 __n -= __base::size();
1659 __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v));
1662 template <class _Tp, class _Allocator>
1665 deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
1667 return __base::__alloc();
1670 template <class _Tp, class _Allocator>
1672 deque<_Tp, _Allocator>::resize(size_type __n)
1674 if (__n > __base::size())
1675 __append(__n - __base::size());
1676 else if (__n < __base::size())
1677 __erase_to_end(__base::begin() + __n);
1680 template <class _Tp, class _Allocator>
1682 deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v)
1684 if (__n > __base::size())
1685 __append(__n - __base::size(), __v);
1686 else if (__n < __base::size())
1687 __erase_to_end(__base::begin() + __n);
1690 template <class _Tp, class _Allocator>
1692 deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1694 allocator_type& __a = __base::__alloc();
1697 while (__base::__map_.size() > 0)
1699 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1700 __base::__map_.pop_back();
1702 __base::__start_ = 0;
1706 if (__front_spare() >= __base::__block_size)
1708 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
1709 __base::__map_.pop_front();
1710 __base::__start_ -= __base::__block_size;
1712 if (__back_spare() >= __base::__block_size)
1714 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1715 __base::__map_.pop_back();
1718 __base::__map_.shrink_to_fit();
1721 template <class _Tp, class _Allocator>
1723 typename deque<_Tp, _Allocator>::reference
1724 deque<_Tp, _Allocator>::operator[](size_type __i)
1726 size_type __p = __base::__start_ + __i;
1727 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1730 template <class _Tp, class _Allocator>
1732 typename deque<_Tp, _Allocator>::const_reference
1733 deque<_Tp, _Allocator>::operator[](size_type __i) const
1735 size_type __p = __base::__start_ + __i;
1736 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1739 template <class _Tp, class _Allocator>
1741 typename deque<_Tp, _Allocator>::reference
1742 deque<_Tp, _Allocator>::at(size_type __i)
1744 if (__i >= __base::size())
1745 __base::__throw_out_of_range();
1746 size_type __p = __base::__start_ + __i;
1747 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1750 template <class _Tp, class _Allocator>
1752 typename deque<_Tp, _Allocator>::const_reference
1753 deque<_Tp, _Allocator>::at(size_type __i) const
1755 if (__i >= __base::size())
1756 __base::__throw_out_of_range();
1757 size_type __p = __base::__start_ + __i;
1758 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1761 template <class _Tp, class _Allocator>
1763 typename deque<_Tp, _Allocator>::reference
1764 deque<_Tp, _Allocator>::front()
1766 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1767 + __base::__start_ % __base::__block_size);
1770 template <class _Tp, class _Allocator>
1772 typename deque<_Tp, _Allocator>::const_reference
1773 deque<_Tp, _Allocator>::front() const
1775 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1776 + __base::__start_ % __base::__block_size);
1779 template <class _Tp, class _Allocator>
1781 typename deque<_Tp, _Allocator>::reference
1782 deque<_Tp, _Allocator>::back()
1784 size_type __p = __base::size() + __base::__start_ - 1;
1785 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1788 template <class _Tp, class _Allocator>
1790 typename deque<_Tp, _Allocator>::const_reference
1791 deque<_Tp, _Allocator>::back() const
1793 size_type __p = __base::size() + __base::__start_ - 1;
1794 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1797 template <class _Tp, class _Allocator>
1799 deque<_Tp, _Allocator>::push_back(const value_type& __v)
1801 allocator_type& __a = __base::__alloc();
1802 if (__back_spare() == 0)
1803 __add_back_capacity();
1804 // __back_spare() >= 1
1805 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
1809 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1811 template <class _Tp, class _Allocator>
1813 deque<_Tp, _Allocator>::push_back(value_type&& __v)
1815 allocator_type& __a = __base::__alloc();
1816 if (__back_spare() == 0)
1817 __add_back_capacity();
1818 // __back_spare() >= 1
1819 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
1823 #ifndef _LIBCPP_HAS_NO_VARIADICS
1825 template <class _Tp, class _Allocator>
1826 template <class... _Args>
1828 deque<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1830 allocator_type& __a = __base::__alloc();
1831 if (__back_spare() == 0)
1832 __add_back_capacity();
1833 // __back_spare() >= 1
1834 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
1838 #endif // _LIBCPP_HAS_NO_VARIADICS
1839 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1841 template <class _Tp, class _Allocator>
1843 deque<_Tp, _Allocator>::push_front(const value_type& __v)
1845 allocator_type& __a = __base::__alloc();
1846 if (__front_spare() == 0)
1847 __add_front_capacity();
1848 // __front_spare() >= 1
1849 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
1854 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1856 template <class _Tp, class _Allocator>
1858 deque<_Tp, _Allocator>::push_front(value_type&& __v)
1860 allocator_type& __a = __base::__alloc();
1861 if (__front_spare() == 0)
1862 __add_front_capacity();
1863 // __front_spare() >= 1
1864 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
1869 #ifndef _LIBCPP_HAS_NO_VARIADICS
1871 template <class _Tp, class _Allocator>
1872 template <class... _Args>
1874 deque<_Tp, _Allocator>::emplace_front(_Args&&... __args)
1876 allocator_type& __a = __base::__alloc();
1877 if (__front_spare() == 0)
1878 __add_front_capacity();
1879 // __front_spare() >= 1
1880 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
1885 #endif // _LIBCPP_HAS_NO_VARIADICS
1886 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1888 template <class _Tp, class _Allocator>
1889 typename deque<_Tp, _Allocator>::iterator
1890 deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v)
1892 size_type __pos = __p - __base::begin();
1893 size_type __to_end = __base::size() - __pos;
1894 allocator_type& __a = __base::__alloc();
1895 if (__pos < __to_end)
1896 { // insert by shifting things backward
1897 if (__front_spare() == 0)
1898 __add_front_capacity();
1899 // __front_spare() >= 1
1902 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
1908 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1909 iterator __b = __base::begin();
1910 iterator __bm1 = _VSTD::prev(__b);
1911 if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))
1912 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);
1913 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1917 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt);
1922 { // insert by shifting things forward
1923 if (__back_spare() == 0)
1924 __add_back_capacity();
1925 // __back_capacity >= 1
1926 size_type __de = __base::size() - __pos;
1929 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
1934 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1935 iterator __e = __base::end();
1936 iterator __em1 = _VSTD::prev(__e);
1937 if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))
1938 __vt = pointer_traits<const_pointer>::pointer_to(*__e);
1939 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
1942 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);
1946 return __base::begin() + __pos;
1949 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1951 template <class _Tp, class _Allocator>
1952 typename deque<_Tp, _Allocator>::iterator
1953 deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v)
1955 size_type __pos = __p - __base::begin();
1956 size_type __to_end = __base::size() - __pos;
1957 allocator_type& __a = __base::__alloc();
1958 if (__pos < __to_end)
1959 { // insert by shifting things backward
1960 if (__front_spare() == 0)
1961 __add_front_capacity();
1962 // __front_spare() >= 1
1965 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
1971 iterator __b = __base::begin();
1972 iterator __bm1 = _VSTD::prev(__b);
1973 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
1977 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1978 *__b = _VSTD::move(__v);
1982 { // insert by shifting things forward
1983 if (__back_spare() == 0)
1984 __add_back_capacity();
1985 // __back_capacity >= 1
1986 size_type __de = __base::size() - __pos;
1989 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
1994 iterator __e = __base::end();
1995 iterator __em1 = _VSTD::prev(__e);
1996 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
1999 __e = _VSTD::move_backward(__e - __de, __em1, __e);
2000 *--__e = _VSTD::move(__v);
2003 return __base::begin() + __pos;
2006 #ifndef _LIBCPP_HAS_NO_VARIADICS
2008 template <class _Tp, class _Allocator>
2009 template <class... _Args>
2010 typename deque<_Tp, _Allocator>::iterator
2011 deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args)
2013 size_type __pos = __p - __base::begin();
2014 size_type __to_end = __base::size() - __pos;
2015 allocator_type& __a = __base::__alloc();
2016 if (__pos < __to_end)
2017 { // insert by shifting things backward
2018 if (__front_spare() == 0)
2019 __add_front_capacity();
2020 // __front_spare() >= 1
2023 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
2029 value_type __tmp(_VSTD::forward<_Args>(__args)...);
2030 iterator __b = __base::begin();
2031 iterator __bm1 = _VSTD::prev(__b);
2032 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
2036 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
2037 *__b = _VSTD::move(__tmp);
2041 { // insert by shifting things forward
2042 if (__back_spare() == 0)
2043 __add_back_capacity();
2044 // __back_capacity >= 1
2045 size_type __de = __base::size() - __pos;
2048 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
2053 value_type __tmp(_VSTD::forward<_Args>(__args)...);
2054 iterator __e = __base::end();
2055 iterator __em1 = _VSTD::prev(__e);
2056 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
2059 __e = _VSTD::move_backward(__e - __de, __em1, __e);
2060 *--__e = _VSTD::move(__tmp);
2063 return __base::begin() + __pos;
2066 #endif // _LIBCPP_HAS_NO_VARIADICS
2067 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2069 template <class _Tp, class _Allocator>
2070 typename deque<_Tp, _Allocator>::iterator
2071 deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v)
2073 size_type __pos = __p - __base::begin();
2074 size_type __to_end = __base::size() - __pos;
2075 allocator_type& __a = __base::__alloc();
2076 if (__pos < __to_end)
2077 { // insert by shifting things backward
2078 if (__n > __front_spare())
2079 __add_front_capacity(__n - __front_spare());
2080 // __n <= __front_spare()
2081 iterator __old_begin = __base::begin();
2082 iterator __i = __old_begin;
2085 for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size())
2086 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v);
2091 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2092 iterator __obn = __old_begin + __n;
2093 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);
2095 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);
2096 _VSTD::fill_n(__old_begin, __n, *__vt);
2100 { // insert by shifting things forward
2101 size_type __back_capacity = __back_spare();
2102 if (__n > __back_capacity)
2103 __add_back_capacity(__n - __back_capacity);
2104 // __n <= __back_capacity
2105 iterator __old_end = __base::end();
2106 iterator __i = __old_end;
2107 size_type __de = __base::size() - __pos;
2110 for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size())
2111 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
2116 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2117 iterator __oen = __old_end - __n;
2118 __move_construct_and_check(__oen, __old_end, __i, __vt);
2120 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);
2121 _VSTD::fill_n(__old_end - __n, __n, *__vt);
2124 return __base::begin() + __pos;
2127 template <class _Tp, class _Allocator>
2128 template <class _InputIter>
2129 typename deque<_Tp, _Allocator>::iterator
2130 deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
2131 typename enable_if<__is_input_iterator<_InputIter>::value
2132 &&!__is_forward_iterator<_InputIter>::value>::type*)
2134 __split_buffer<value_type, allocator_type&> __buf(__base::__alloc());
2135 __buf.__construct_at_end(__f, __l);
2136 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
2137 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
2140 template <class _Tp, class _Allocator>
2141 template <class _ForwardIterator>
2142 typename deque<_Tp, _Allocator>::iterator
2143 deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
2144 typename enable_if<__is_forward_iterator<_ForwardIterator>::value
2145 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type*)
2147 size_type __n = _VSTD::distance(__f, __l);
2148 __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc());
2149 __buf.__construct_at_end(__f, __l);
2150 typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
2151 return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
2154 template <class _Tp, class _Allocator>
2155 template <class _BiIter>
2156 typename deque<_Tp, _Allocator>::iterator
2157 deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
2158 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*)
2160 size_type __n = _VSTD::distance(__f, __l);
2161 size_type __pos = __p - __base::begin();
2162 size_type __to_end = __base::size() - __pos;
2163 allocator_type& __a = __base::__alloc();
2164 if (__pos < __to_end)
2165 { // insert by shifting things backward
2166 if (__n > __front_spare())
2167 __add_front_capacity(__n - __front_spare());
2168 // __n <= __front_spare()
2169 iterator __old_begin = __base::begin();
2170 iterator __i = __old_begin;
2174 __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
2175 for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size())
2176 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
2181 iterator __obn = __old_begin + __n;
2182 for (iterator __j = __obn; __j != __old_begin;)
2184 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
2189 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
2190 _VSTD::copy(__m, __l, __old_begin);
2194 { // insert by shifting things forward
2195 size_type __back_capacity = __back_spare();
2196 if (__n > __back_capacity)
2197 __add_back_capacity(__n - __back_capacity);
2198 // __n <= __back_capacity
2199 iterator __old_end = __base::end();
2200 iterator __i = __old_end;
2202 size_type __de = __base::size() - __pos;
2205 __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
2206 for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
2207 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
2212 iterator __oen = __old_end - __n;
2213 for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size())
2214 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
2216 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
2217 _VSTD::copy_backward(__f, __m, __old_end);
2220 return __base::begin() + __pos;
2223 template <class _Tp, class _Allocator>
2224 template <class _InpIter>
2226 deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
2227 typename enable_if<__is_input_iterator<_InpIter>::value &&
2228 !__is_forward_iterator<_InpIter>::value>::type*)
2230 for (; __f != __l; ++__f)
2234 template <class _Tp, class _Allocator>
2235 template <class _ForIter>
2237 deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
2238 typename enable_if<__is_forward_iterator<_ForIter>::value>::type*)
2240 size_type __n = _VSTD::distance(__f, __l);
2241 allocator_type& __a = __base::__alloc();
2242 size_type __back_capacity = __back_spare();
2243 if (__n > __back_capacity)
2244 __add_back_capacity(__n - __back_capacity);
2245 // __n <= __back_capacity
2246 for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size())
2247 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f);
2250 template <class _Tp, class _Allocator>
2252 deque<_Tp, _Allocator>::__append(size_type __n)
2254 allocator_type& __a = __base::__alloc();
2255 size_type __back_capacity = __back_spare();
2256 if (__n > __back_capacity)
2257 __add_back_capacity(__n - __back_capacity);
2258 // __n <= __back_capacity
2259 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
2260 __alloc_traits::construct(__a, _VSTD::addressof(*__i));
2263 template <class _Tp, class _Allocator>
2265 deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
2267 allocator_type& __a = __base::__alloc();
2268 size_type __back_capacity = __back_spare();
2269 if (__n > __back_capacity)
2270 __add_back_capacity(__n - __back_capacity);
2271 // __n <= __back_capacity
2272 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
2273 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
2276 // Create front capacity for one block of elements.
2277 // Strong guarantee. Either do it or don't touch anything.
2278 template <class _Tp, class _Allocator>
2280 deque<_Tp, _Allocator>::__add_front_capacity()
2282 allocator_type& __a = __base::__alloc();
2283 if (__back_spare() >= __base::__block_size)
2285 __base::__start_ += __base::__block_size;
2286 pointer __pt = __base::__map_.back();
2287 __base::__map_.pop_back();
2288 __base::__map_.push_front(__pt);
2290 // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer
2291 else if (__base::__map_.size() < __base::__map_.capacity())
2292 { // we can put the new buffer into the map, but don't shift things around
2293 // until all buffers are allocated. If we throw, we don't need to fix
2294 // anything up (any added buffers are undetectible)
2295 if (__base::__map_.__front_spare() > 0)
2296 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2299 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2300 // Done allocating, reorder capacity
2301 pointer __pt = __base::__map_.back();
2302 __base::__map_.pop_back();
2303 __base::__map_.push_front(__pt);
2305 __base::__start_ = __base::__map_.size() == 1 ?
2306 __base::__block_size / 2 :
2307 __base::__start_ + __base::__block_size;
2309 // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2312 __split_buffer<pointer, typename __base::__pointer_allocator&>
2313 __buf(max<size_type>(2 * __base::__map_.capacity(), 1),
2314 0, __base::__map_.__alloc());
2316 typedef __allocator_destructor<_Allocator> _Dp;
2317 unique_ptr<pointer, _Dp> __hold(
2318 __alloc_traits::allocate(__a, __base::__block_size),
2319 _Dp(__a, __base::__block_size));
2320 __buf.push_back(__hold.get());
2323 for (typename __base::__map_pointer __i = __base::__map_.begin();
2324 __i != __base::__map_.end(); ++__i)
2325 __buf.push_back(*__i);
2326 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2327 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2328 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2329 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2330 __base::__start_ = __base::__map_.size() == 1 ?
2331 __base::__block_size / 2 :
2332 __base::__start_ + __base::__block_size;
2336 // Create front capacity for __n elements.
2337 // Strong guarantee. Either do it or don't touch anything.
2338 template <class _Tp, class _Allocator>
2340 deque<_Tp, _Allocator>::__add_front_capacity(size_type __n)
2342 allocator_type& __a = __base::__alloc();
2343 size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2344 // Number of unused blocks at back:
2345 size_type __back_capacity = __back_spare() / __base::__block_size;
2346 __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need
2347 __nb -= __back_capacity; // number of blocks need to allocate
2348 // If __nb == 0, then we have sufficient capacity.
2351 __base::__start_ += __base::__block_size * __back_capacity;
2352 for (; __back_capacity > 0; --__back_capacity)
2354 pointer __pt = __base::__map_.back();
2355 __base::__map_.pop_back();
2356 __base::__map_.push_front(__pt);
2359 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2360 else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2361 { // we can put the new buffers into the map, but don't shift things around
2362 // until all buffers are allocated. If we throw, we don't need to fix
2363 // anything up (any added buffers are undetectible)
2364 for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1))
2366 if (__base::__map_.__front_spare() == 0)
2368 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2370 for (; __nb > 0; --__nb, ++__back_capacity)
2371 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2372 // Done allocating, reorder capacity
2373 __base::__start_ += __back_capacity * __base::__block_size;
2374 for (; __back_capacity > 0; --__back_capacity)
2376 pointer __pt = __base::__map_.back();
2377 __base::__map_.pop_back();
2378 __base::__map_.push_front(__pt);
2381 // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2384 size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty();
2385 __split_buffer<pointer, typename __base::__pointer_allocator&>
2386 __buf(max<size_type>(2* __base::__map_.capacity(),
2387 __nb + __base::__map_.size()),
2388 0, __base::__map_.__alloc());
2389 #ifndef _LIBCPP_NO_EXCEPTIONS
2392 #endif // _LIBCPP_NO_EXCEPTIONS
2393 for (; __nb > 0; --__nb)
2394 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2395 #ifndef _LIBCPP_NO_EXCEPTIONS
2399 for (typename __base::__map_pointer __i = __buf.begin();
2400 __i != __buf.end(); ++__i)
2401 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2404 #endif // _LIBCPP_NO_EXCEPTIONS
2405 for (; __back_capacity > 0; --__back_capacity)
2407 __buf.push_back(__base::__map_.back());
2408 __base::__map_.pop_back();
2410 for (typename __base::__map_pointer __i = __base::__map_.begin();
2411 __i != __base::__map_.end(); ++__i)
2412 __buf.push_back(*__i);
2413 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2414 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2415 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2416 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2417 __base::__start_ += __ds;
2421 // Create back capacity for one block of elements.
2422 // Strong guarantee. Either do it or don't touch anything.
2423 template <class _Tp, class _Allocator>
2425 deque<_Tp, _Allocator>::__add_back_capacity()
2427 allocator_type& __a = __base::__alloc();
2428 if (__front_spare() >= __base::__block_size)
2430 __base::__start_ -= __base::__block_size;
2431 pointer __pt = __base::__map_.front();
2432 __base::__map_.pop_front();
2433 __base::__map_.push_back(__pt);
2435 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2436 else if (__base::__map_.size() < __base::__map_.capacity())
2437 { // we can put the new buffer into the map, but don't shift things around
2438 // until it is allocated. If we throw, we don't need to fix
2439 // anything up (any added buffers are undetectible)
2440 if (__base::__map_.__back_spare() != 0)
2441 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2444 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2445 // Done allocating, reorder capacity
2446 pointer __pt = __base::__map_.front();
2447 __base::__map_.pop_front();
2448 __base::__map_.push_back(__pt);
2451 // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2454 __split_buffer<pointer, typename __base::__pointer_allocator&>
2455 __buf(max<size_type>(2* __base::__map_.capacity(), 1),
2456 __base::__map_.size(),
2457 __base::__map_.__alloc());
2459 typedef __allocator_destructor<_Allocator> _Dp;
2460 unique_ptr<pointer, _Dp> __hold(
2461 __alloc_traits::allocate(__a, __base::__block_size),
2462 _Dp(__a, __base::__block_size));
2463 __buf.push_back(__hold.get());
2466 for (typename __base::__map_pointer __i = __base::__map_.end();
2467 __i != __base::__map_.begin();)
2468 __buf.push_front(*--__i);
2469 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2470 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2471 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2472 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2476 // Create back capacity for __n elements.
2477 // Strong guarantee. Either do it or don't touch anything.
2478 template <class _Tp, class _Allocator>
2480 deque<_Tp, _Allocator>::__add_back_capacity(size_type __n)
2482 allocator_type& __a = __base::__alloc();
2483 size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2484 // Number of unused blocks at front:
2485 size_type __front_capacity = __front_spare() / __base::__block_size;
2486 __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need
2487 __nb -= __front_capacity; // number of blocks need to allocate
2488 // If __nb == 0, then we have sufficient capacity.
2491 __base::__start_ -= __base::__block_size * __front_capacity;
2492 for (; __front_capacity > 0; --__front_capacity)
2494 pointer __pt = __base::__map_.front();
2495 __base::__map_.pop_front();
2496 __base::__map_.push_back(__pt);
2499 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2500 else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2501 { // we can put the new buffers into the map, but don't shift things around
2502 // until all buffers are allocated. If we throw, we don't need to fix
2503 // anything up (any added buffers are undetectible)
2504 for (; __nb > 0; --__nb)
2506 if (__base::__map_.__back_spare() == 0)
2508 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2510 for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ +=
2511 __base::__block_size - (__base::__map_.size() == 1))
2512 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2513 // Done allocating, reorder capacity
2514 __base::__start_ -= __base::__block_size * __front_capacity;
2515 for (; __front_capacity > 0; --__front_capacity)
2517 pointer __pt = __base::__map_.front();
2518 __base::__map_.pop_front();
2519 __base::__map_.push_back(__pt);
2522 // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2525 size_type __ds = __front_capacity * __base::__block_size;
2526 __split_buffer<pointer, typename __base::__pointer_allocator&>
2527 __buf(max<size_type>(2* __base::__map_.capacity(),
2528 __nb + __base::__map_.size()),
2529 __base::__map_.size() - __front_capacity,
2530 __base::__map_.__alloc());
2531 #ifndef _LIBCPP_NO_EXCEPTIONS
2534 #endif // _LIBCPP_NO_EXCEPTIONS
2535 for (; __nb > 0; --__nb)
2536 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2537 #ifndef _LIBCPP_NO_EXCEPTIONS
2541 for (typename __base::__map_pointer __i = __buf.begin();
2542 __i != __buf.end(); ++__i)
2543 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2546 #endif // _LIBCPP_NO_EXCEPTIONS
2547 for (; __front_capacity > 0; --__front_capacity)
2549 __buf.push_back(__base::__map_.front());
2550 __base::__map_.pop_front();
2552 for (typename __base::__map_pointer __i = __base::__map_.end();
2553 __i != __base::__map_.begin();)
2554 __buf.push_front(*--__i);
2555 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2556 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2557 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2558 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2559 __base::__start_ -= __ds;
2563 template <class _Tp, class _Allocator>
2565 deque<_Tp, _Allocator>::pop_front()
2567 allocator_type& __a = __base::__alloc();
2568 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2569 __base::__start_ / __base::__block_size) +
2570 __base::__start_ % __base::__block_size));
2572 if (++__base::__start_ >= 2 * __base::__block_size)
2574 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2575 __base::__map_.pop_front();
2576 __base::__start_ -= __base::__block_size;
2580 template <class _Tp, class _Allocator>
2582 deque<_Tp, _Allocator>::pop_back()
2584 allocator_type& __a = __base::__alloc();
2585 size_type __p = __base::size() + __base::__start_ - 1;
2586 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2587 __p / __base::__block_size) +
2588 __p % __base::__block_size));
2590 if (__back_spare() >= 2 * __base::__block_size)
2592 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2593 __base::__map_.pop_back();
2597 // move assign [__f, __l) to [__r, __r + (__l-__f)).
2598 // If __vt points into [__f, __l), then subtract (__f - __r) from __vt.
2599 template <class _Tp, class _Allocator>
2600 typename deque<_Tp, _Allocator>::iterator
2601 deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r,
2602 const_pointer& __vt)
2605 // for (; __f != __l; ++__f, ++__r)
2606 // *__r = _VSTD::move(*__f);
2607 difference_type __n = __l - __f;
2610 pointer __fb = __f.__ptr_;
2611 pointer __fe = *__f.__m_iter_ + __base::__block_size;
2612 difference_type __bs = __fe - __fb;
2618 if (__fb <= __vt && __vt < __fe)
2619 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;
2620 __r = _VSTD::move(__fb, __fe, __r);
2627 // move assign [__f, __l) to [__r - (__l-__f), __r) backwards.
2628 // If __vt points into [__f, __l), then add (__r - __l) to __vt.
2629 template <class _Tp, class _Allocator>
2630 typename deque<_Tp, _Allocator>::iterator
2631 deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r,
2632 const_pointer& __vt)
2635 // while (__f != __l)
2636 // *--__r = _VSTD::move(*--__l);
2637 difference_type __n = __l - __f;
2641 pointer __lb = *__l.__m_iter_;
2642 pointer __le = __l.__ptr_ + 1;
2643 difference_type __bs = __le - __lb;
2649 if (__lb <= __vt && __vt < __le)
2650 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_;
2651 __r = _VSTD::move_backward(__lb, __le, __r);
2658 // move construct [__f, __l) to [__r, __r + (__l-__f)).
2659 // If __vt points into [__f, __l), then add (__r - __f) to __vt.
2660 template <class _Tp, class _Allocator>
2662 deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l,
2663 iterator __r, const_pointer& __vt)
2665 allocator_type& __a = __base::__alloc();
2667 // for (; __f != __l; ++__r, ++__f, ++__base::size())
2668 // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f));
2669 difference_type __n = __l - __f;
2672 pointer __fb = __f.__ptr_;
2673 pointer __fe = *__f.__m_iter_ + __base::__block_size;
2674 difference_type __bs = __fe - __fb;
2680 if (__fb <= __vt && __vt < __fe)
2681 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;
2682 for (; __fb != __fe; ++__fb, ++__r, ++__base::size())
2683 __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb));
2689 // move construct [__f, __l) to [__r - (__l-__f), __r) backwards.
2690 // If __vt points into [__f, __l), then subtract (__l - __r) from __vt.
2691 template <class _Tp, class _Allocator>
2693 deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l,
2694 iterator __r, const_pointer& __vt)
2696 allocator_type& __a = __base::__alloc();
2698 // for (iterator __j = __l; __j != __f;)
2700 // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j));
2701 // --__base::__start_;
2702 // ++__base::size();
2704 difference_type __n = __l - __f;
2708 pointer __lb = *__l.__m_iter_;
2709 pointer __le = __l.__ptr_ + 1;
2710 difference_type __bs = __le - __lb;
2716 if (__lb <= __vt && __vt < __le)
2717 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;
2718 while (__le != __lb)
2720 __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le));
2729 template <class _Tp, class _Allocator>
2730 typename deque<_Tp, _Allocator>::iterator
2731 deque<_Tp, _Allocator>::erase(const_iterator __f)
2733 iterator __b = __base::begin();
2734 difference_type __pos = __f - __b;
2735 iterator __p = __b + __pos;
2736 allocator_type& __a = __base::__alloc();
2737 if (__pos <= (__base::size() - 1) / 2)
2738 { // erase from front
2739 _VSTD::move_backward(__b, __p, _VSTD::next(__p));
2740 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2743 if (__front_spare() >= 2 * __base::__block_size)
2745 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2746 __base::__map_.pop_front();
2747 __base::__start_ -= __base::__block_size;
2751 { // erase from back
2752 iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
2753 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2755 if (__back_spare() >= 2 * __base::__block_size)
2757 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2758 __base::__map_.pop_back();
2761 return __base::begin() + __pos;
2764 template <class _Tp, class _Allocator>
2765 typename deque<_Tp, _Allocator>::iterator
2766 deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
2768 difference_type __n = __l - __f;
2769 iterator __b = __base::begin();
2770 difference_type __pos = __f - __b;
2771 iterator __p = __b + __pos;
2774 allocator_type& __a = __base::__alloc();
2775 if (__pos <= (__base::size() - __n) / 2)
2776 { // erase from front
2777 iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
2778 for (; __b != __i; ++__b)
2779 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2780 __base::size() -= __n;
2781 __base::__start_ += __n;
2782 while (__front_spare() >= 2 * __base::__block_size)
2784 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2785 __base::__map_.pop_front();
2786 __base::__start_ -= __base::__block_size;
2790 { // erase from back
2791 iterator __i = _VSTD::move(__p + __n, __base::end(), __p);
2792 for (iterator __e = __base::end(); __i != __e; ++__i)
2793 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2794 __base::size() -= __n;
2795 while (__back_spare() >= 2 * __base::__block_size)
2797 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2798 __base::__map_.pop_back();
2802 return __base::begin() + __pos;
2805 template <class _Tp, class _Allocator>
2807 deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
2809 iterator __e = __base::end();
2810 difference_type __n = __e - __f;
2813 allocator_type& __a = __base::__alloc();
2814 iterator __b = __base::begin();
2815 difference_type __pos = __f - __b;
2816 for (iterator __p = __b + __pos; __p != __e; ++__p)
2817 __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
2818 __base::size() -= __n;
2819 while (__back_spare() >= 2 * __base::__block_size)
2821 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2822 __base::__map_.pop_back();
2827 template <class _Tp, class _Allocator>
2830 deque<_Tp, _Allocator>::swap(deque& __c)
2831 #if _LIBCPP_STD_VER >= 14
2834 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2835 __is_nothrow_swappable<allocator_type>::value)
2841 template <class _Tp, class _Allocator>
2844 deque<_Tp, _Allocator>::clear() _NOEXCEPT
2849 template <class _Tp, class _Allocator>
2850 inline _LIBCPP_INLINE_VISIBILITY
2852 operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2854 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();
2855 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2858 template <class _Tp, class _Allocator>
2859 inline _LIBCPP_INLINE_VISIBILITY
2861 operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2863 return !(__x == __y);
2866 template <class _Tp, class _Allocator>
2867 inline _LIBCPP_INLINE_VISIBILITY
2869 operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2871 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2874 template <class _Tp, class _Allocator>
2875 inline _LIBCPP_INLINE_VISIBILITY
2877 operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2882 template <class _Tp, class _Allocator>
2883 inline _LIBCPP_INLINE_VISIBILITY
2885 operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2887 return !(__x < __y);
2890 template <class _Tp, class _Allocator>
2891 inline _LIBCPP_INLINE_VISIBILITY
2893 operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2895 return !(__y < __x);
2898 template <class _Tp, class _Allocator>
2899 inline _LIBCPP_INLINE_VISIBILITY
2901 swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y)
2902 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2907 _LIBCPP_END_NAMESPACE_STD
2909 #endif // _LIBCPP_DEQUE