57 #define _STL_DEQUE_H 1
62 #if __cplusplus >= 201103L
69 namespace std _GLIBCXX_VISIBILITY(default)
71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
72 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
88 #ifndef _GLIBCXX_DEQUE_BUF_SIZE
89 #define _GLIBCXX_DEQUE_BUF_SIZE 512
92 _GLIBCXX_CONSTEXPR
inline size_t
93 __deque_buf_size(
size_t __size)
109 template<
typename _Tp,
typename _Ref,
typename _Ptr>
110 struct _Deque_iterator
112 #if __cplusplus < 201103L
113 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
114 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
115 typedef _Tp* _Elt_pointer;
116 typedef _Tp** _Map_pointer;
119 template<
typename _CvTp>
120 using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_rebind<_Ptr, _CvTp>>;
122 typedef __iter<_Tp> iterator;
123 typedef __iter<const _Tp> const_iterator;
124 typedef __ptr_rebind<_Ptr, _Tp> _Elt_pointer;
125 typedef __ptr_rebind<_Ptr, _Elt_pointer> _Map_pointer;
128 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
129 {
return __deque_buf_size(
sizeof(_Tp)); }
132 typedef _Tp value_type;
133 typedef _Ptr pointer;
134 typedef _Ref reference;
135 typedef size_t size_type;
136 typedef ptrdiff_t difference_type;
137 typedef _Deque_iterator _Self;
140 _Elt_pointer _M_first;
141 _Elt_pointer _M_last;
142 _Map_pointer _M_node;
144 _Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT
145 : _M_cur(__x), _M_first(*__y),
146 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
148 _Deque_iterator() _GLIBCXX_NOEXCEPT
149 : _M_cur(), _M_first(), _M_last(), _M_node() { }
151 #if __cplusplus < 201103L
153 _Deque_iterator(
const iterator& __x) _GLIBCXX_NOEXCEPT
154 : _M_cur(__x._M_cur), _M_first(__x._M_first),
155 _M_last(__x._M_last), _M_node(__x._M_node) { }
158 template<
typename _Iter,
159 typename = _Require<is_same<_Self, const_iterator>,
160 is_same<_Iter, iterator>>>
161 _Deque_iterator(
const _Iter& __x) noexcept
162 : _M_cur(__x._M_cur), _M_first(__x._M_first),
163 _M_last(__x._M_last), _M_node(__x._M_node) { }
165 _Deque_iterator(
const _Deque_iterator& __x) noexcept
166 : _M_cur(__x._M_cur), _M_first(__x._M_first),
167 _M_last(__x._M_last), _M_node(__x._M_node) { }
169 _Deque_iterator& operator=(
const _Deque_iterator&) =
default;
173 _M_const_cast() const _GLIBCXX_NOEXCEPT
174 {
return iterator(_M_cur, _M_node); }
177 operator*() const _GLIBCXX_NOEXCEPT
181 operator->() const _GLIBCXX_NOEXCEPT
185 operator++() _GLIBCXX_NOEXCEPT
188 if (_M_cur == _M_last)
197 operator++(
int) _GLIBCXX_NOEXCEPT
205 operator--() _GLIBCXX_NOEXCEPT
207 if (_M_cur == _M_first)
217 operator--(
int) _GLIBCXX_NOEXCEPT
225 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
227 const difference_type __offset = __n + (_M_cur - _M_first);
228 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
232 const difference_type __node_offset =
233 __offset > 0 ? __offset / difference_type(_S_buffer_size())
234 : -difference_type((-__offset - 1)
235 / _S_buffer_size()) - 1;
237 _M_cur = _M_first + (__offset - __node_offset
238 * difference_type(_S_buffer_size()));
244 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
245 {
return *
this += -__n; }
248 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
249 {
return *(*
this + __n); }
259 _M_node = __new_node;
260 _M_first = *__new_node;
261 _M_last = _M_first + difference_type(_S_buffer_size());
265 operator==(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
266 {
return __x._M_cur == __y._M_cur; }
271 template<
typename _RefR,
typename _PtrR>
273 operator==(
const _Self& __x,
274 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
275 {
return __x._M_cur == __y._M_cur; }
278 operator!=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
279 {
return !(__x == __y); }
281 template<
typename _RefR,
typename _PtrR>
283 operator!=(
const _Self& __x,
284 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
285 {
return !(__x == __y); }
288 operator<(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
290 return (__x._M_node == __y._M_node)
291 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
294 template<
typename _RefR,
typename _PtrR>
296 operator<(
const _Self& __x,
297 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
299 return (__x._M_node == __y._M_node)
300 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
304 operator>(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
305 {
return __y < __x; }
307 template<
typename _RefR,
typename _PtrR>
309 operator>(
const _Self& __x,
310 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
311 {
return __y < __x; }
314 operator<=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
315 {
return !(__y < __x); }
317 template<
typename _RefR,
typename _PtrR>
319 operator<=(
const _Self& __x,
320 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
321 {
return !(__y < __x); }
324 operator>=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
325 {
return !(__x < __y); }
327 template<
typename _RefR,
typename _PtrR>
329 operator>=(
const _Self& __x,
330 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
331 {
return !(__x < __y); }
333 friend difference_type
334 operator-(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
336 return difference_type(_S_buffer_size())
337 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
338 + (__y._M_last - __y._M_cur);
345 template<
typename _RefR,
typename _PtrR>
346 friend difference_type
347 operator-(
const _Self& __x,
348 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
350 return difference_type(_S_buffer_size())
351 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
352 + (__y._M_last - __y._M_cur);
356 operator+(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
364 operator-(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
372 operator+(difference_type __n,
const _Self& __x) _GLIBCXX_NOEXCEPT
373 {
return __x + __n; }
386 template<
typename _Tp,
typename _Alloc>
391 rebind<_Tp>::other _Tp_alloc_type;
394 #if __cplusplus < 201103L
396 typedef const _Tp* _Ptr_const;
398 typedef typename _Alloc_traits::pointer _Ptr;
399 typedef typename _Alloc_traits::const_pointer _Ptr_const;
402 typedef typename _Alloc_traits::template rebind<_Ptr>::other
406 typedef _Alloc allocator_type;
409 get_allocator()
const _GLIBCXX_NOEXCEPT
410 {
return allocator_type(_M_get_Tp_allocator()); }
423 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
431 #if __cplusplus >= 201103L
433 : _M_impl(
std::move(__x._M_get_Tp_allocator()))
436 if (__x._M_impl._M_map)
437 this->_M_impl._M_swap_data(__x._M_impl);
441 : _M_impl(
std::move(__x._M_impl), _Tp_alloc_type(__a))
442 { __x._M_initialize_map(0); }
447 if (__x.get_allocator() == __a)
449 if (__x._M_impl._M_map)
452 this->_M_impl._M_swap_data(__x._M_impl);
464 typedef typename iterator::_Map_pointer _Map_pointer;
466 struct _Deque_impl_data
473 _Deque_impl_data() _GLIBCXX_NOEXCEPT
474 : _M_map(), _M_map_size(), _M_start(), _M_finish()
477 #if __cplusplus >= 201103L
478 _Deque_impl_data(
const _Deque_impl_data&) =
default;
480 operator=(
const _Deque_impl_data&) =
default;
482 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
483 : _Deque_impl_data(__x)
484 { __x = _Deque_impl_data(); }
488 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
492 std::swap(*
this, __x);
500 :
public _Tp_alloc_type,
public _Deque_impl_data
502 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
507 _Deque_impl(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
508 : _Tp_alloc_type(__a)
511 #if __cplusplus >= 201103L
512 _Deque_impl(_Deque_impl&&) =
default;
514 _Deque_impl(_Tp_alloc_type&& __a) noexcept
518 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
525 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
526 {
return this->_M_impl; }
528 const _Tp_alloc_type&
529 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
530 {
return this->_M_impl; }
533 _M_get_map_allocator()
const _GLIBCXX_NOEXCEPT
534 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
540 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
544 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
547 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
551 _M_allocate_map(
size_t __n)
553 _Map_alloc_type __map_alloc = _M_get_map_allocator();
558 _M_deallocate_map(_Map_pointer __p,
size_t __n) _GLIBCXX_NOEXCEPT
560 _Map_alloc_type __map_alloc = _M_get_map_allocator();
565 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
566 void _M_destroy_nodes(_Map_pointer __nstart,
567 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
568 enum { _S_initial_map_size = 8 };
573 template<
typename _Tp,
typename _Alloc>
577 if (this->_M_impl._M_map)
579 _M_destroy_nodes(this->_M_impl._M_start._M_node,
580 this->_M_impl._M_finish._M_node + 1);
581 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
593 template<
typename _Tp,
typename _Alloc>
598 const size_t __num_nodes = (__num_elements / __deque_buf_size(
sizeof(_Tp))
601 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
602 size_t(__num_nodes + 2));
603 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
610 _Map_pointer __nstart = (this->_M_impl._M_map
611 + (this->_M_impl._M_map_size - __num_nodes) / 2);
612 _Map_pointer __nfinish = __nstart + __num_nodes;
615 { _M_create_nodes(__nstart, __nfinish); }
618 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
619 this->_M_impl._M_map = _Map_pointer();
620 this->_M_impl._M_map_size = 0;
621 __throw_exception_again;
624 this->_M_impl._M_start._M_set_node(__nstart);
625 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
626 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
627 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
629 % __deque_buf_size(
sizeof(_Tp)));
632 template<
typename _Tp,
typename _Alloc>
640 for (__cur = __nstart; __cur < __nfinish; ++__cur)
641 *__cur = this->_M_allocate_node();
645 _M_destroy_nodes(__nstart, __cur);
646 __throw_exception_again;
650 template<
typename _Tp,
typename _Alloc>
652 _Deque_base<_Tp, _Alloc>::
653 _M_destroy_nodes(_Map_pointer __nstart,
654 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
656 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
657 _M_deallocate_node(*__n);
744 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
747 #ifdef _GLIBCXX_CONCEPT_CHECKS
749 typedef typename _Alloc::value_type _Alloc_value_type;
750 # if __cplusplus < 201103L
751 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
753 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
756 #if __cplusplus >= 201103L
757 static_assert(
is_same<
typename remove_cv<_Tp>::type, _Tp>::value,
758 "std::deque must have a non-const, non-volatile value_type");
759 # if __cplusplus > 201703L || defined __STRICT_ANSI__
761 "std::deque must have the same value_type as its allocator");
766 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
768 typedef typename _Base::_Map_pointer _Map_pointer;
771 typedef _Tp value_type;
772 typedef typename _Alloc_traits::pointer pointer;
773 typedef typename _Alloc_traits::const_pointer const_pointer;
774 typedef typename _Alloc_traits::reference reference;
775 typedef typename _Alloc_traits::const_reference const_reference;
780 typedef size_t size_type;
781 typedef ptrdiff_t difference_type;
782 typedef _Alloc allocator_type;
785 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
786 {
return __deque_buf_size(
sizeof(_Tp)); }
790 using _Base::_M_create_nodes;
791 using _Base::_M_destroy_nodes;
792 using _Base::_M_allocate_node;
793 using _Base::_M_deallocate_node;
794 using _Base::_M_allocate_map;
795 using _Base::_M_deallocate_map;
796 using _Base::_M_get_Tp_allocator;
802 using _Base::_M_impl;
811 #if __cplusplus >= 201103L
825 #if __cplusplus >= 201103L
836 :
_Base(__a, _S_check_init_len(__n, __a))
837 { _M_default_initialize(); }
847 deque(size_type __n,
const value_type& __value,
849 :
_Base(__a, _S_check_init_len(__n, __a))
861 deque(size_type __n,
const value_type& __value = value_type(),
862 const allocator_type& __a = allocator_type())
863 : _Base(__a, _S_check_init_len(__n, __a))
877 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
878 this->_M_impl._M_start,
879 _M_get_Tp_allocator()); }
881 #if __cplusplus >= 201103L
895 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
896 this->_M_impl._M_start,
897 _M_get_Tp_allocator()); }
912 if (__x.get_allocator() != __a && !__x.empty())
914 std::__uninitialized_move_a(__x.begin(), __x.end(),
915 this->_M_impl._M_start,
916 _M_get_Tp_allocator());
957 #if __cplusplus >= 201103L
958 template<
typename _InputIterator,
959 typename = std::_RequireInputIter<_InputIterator>>
960 deque(_InputIterator __first, _InputIterator __last,
968 template<
typename _InputIterator>
969 deque(_InputIterator __first, _InputIterator __last,
970 const allocator_type& __a = allocator_type())
974 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
975 _M_initialize_dispatch(__first, __last, _Integral());
985 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
999 #if __cplusplus >= 201103L
1012 _M_move_assign1(
std::move(__x), __always_equal{});
1030 _M_assign_aux(__l.begin(), __l.end(),
1047 assign(size_type __n,
const value_type& __val)
1048 { _M_fill_assign(__n, __val); }
1062 #if __cplusplus >= 201103L
1063 template<
typename _InputIterator,
1064 typename = std::_RequireInputIter<_InputIterator>>
1066 assign(_InputIterator __first, _InputIterator __last)
1069 template<
typename _InputIterator>
1071 assign(_InputIterator __first, _InputIterator __last)
1073 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1074 _M_assign_dispatch(__first, __last, _Integral());
1078 #if __cplusplus >= 201103L
1098 {
return _Base::get_allocator(); }
1107 {
return this->_M_impl._M_start; }
1115 {
return this->_M_impl._M_start; }
1124 {
return this->_M_impl._M_finish; }
1133 {
return this->_M_impl._M_finish; }
1149 const_reverse_iterator
1167 const_reverse_iterator
1171 #if __cplusplus >= 201103L
1178 {
return this->_M_impl._M_start; }
1187 {
return this->_M_impl._M_finish; }
1194 const_reverse_iterator
1203 const_reverse_iterator
1212 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
1217 {
return _S_max_size(_M_get_Tp_allocator()); }
1219 #if __cplusplus >= 201103L
1232 const size_type __len =
size();
1233 if (__new_size > __len)
1234 _M_default_append(__new_size - __len);
1235 else if (__new_size < __len)
1236 _M_erase_at_end(this->_M_impl._M_start
1237 + difference_type(__new_size));
1252 resize(size_type __new_size,
const value_type& __x)
1266 resize(size_type __new_size, value_type __x = value_type())
1269 const size_type __len =
size();
1270 if (__new_size > __len)
1271 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1272 else if (__new_size < __len)
1273 _M_erase_at_end(this->_M_impl._M_start
1274 + difference_type(__new_size));
1277 #if __cplusplus >= 201103L
1281 { _M_shrink_to_fit(); }
1288 _GLIBCXX_NODISCARD
bool
1290 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1307 __glibcxx_requires_subscript(__n);
1308 return this->_M_impl._M_start[difference_type(__n)];
1325 __glibcxx_requires_subscript(__n);
1326 return this->_M_impl._M_start[difference_type(__n)];
1334 if (__n >= this->
size())
1335 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n "
1336 "(which is %zu)>= this->size() "
1357 return (*
this)[__n];
1375 return (*
this)[__n];
1385 __glibcxx_requires_nonempty();
1396 __glibcxx_requires_nonempty();
1407 __glibcxx_requires_nonempty();
1420 __glibcxx_requires_nonempty();
1439 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1441 _Alloc_traits::construct(this->_M_impl,
1442 this->_M_impl._M_start._M_cur - 1,
1444 --this->_M_impl._M_start._M_cur;
1447 _M_push_front_aux(__x);
1450 #if __cplusplus >= 201103L
1455 template<
typename... _Args>
1456 #if __cplusplus > 201402L
1461 emplace_front(_Args&&... __args);
1476 if (this->_M_impl._M_finish._M_cur
1477 != this->_M_impl._M_finish._M_last - 1)
1479 _Alloc_traits::construct(this->_M_impl,
1480 this->_M_impl._M_finish._M_cur, __x);
1481 ++this->_M_impl._M_finish._M_cur;
1487 #if __cplusplus >= 201103L
1492 template<
typename... _Args>
1493 #if __cplusplus > 201402L
1498 emplace_back(_Args&&... __args);
1512 __glibcxx_requires_nonempty();
1513 if (this->_M_impl._M_start._M_cur
1514 != this->_M_impl._M_start._M_last - 1)
1516 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1517 this->_M_impl._M_start._M_cur);
1518 ++this->_M_impl._M_start._M_cur;
1535 __glibcxx_requires_nonempty();
1536 if (this->_M_impl._M_finish._M_cur
1537 != this->_M_impl._M_finish._M_first)
1539 --this->_M_impl._M_finish._M_cur;
1540 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1541 this->_M_impl._M_finish._M_cur);
1547 #if __cplusplus >= 201103L
1557 template<
typename... _Args>
1559 emplace(const_iterator __position, _Args&&... __args);
1571 insert(const_iterator __position,
const value_type& __x);
1586 #if __cplusplus >= 201103L
1613 auto __offset = __p -
cbegin();
1614 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1616 return begin() + __offset;
1632 difference_type __offset = __position -
cbegin();
1633 _M_fill_insert(__position._M_const_cast(), __n, __x);
1634 return begin() + __offset;
1647 insert(
iterator __position, size_type __n,
const value_type& __x)
1648 { _M_fill_insert(__position, __n, __x); }
1651 #if __cplusplus >= 201103L
1663 template<
typename _InputIterator,
1664 typename = std::_RequireInputIter<_InputIterator>>
1667 _InputIterator __last)
1669 difference_type __offset = __position -
cbegin();
1670 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1672 return begin() + __offset;
1685 template<
typename _InputIterator>
1688 _InputIterator __last)
1691 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1692 _M_insert_dispatch(__position, __first, __last, _Integral());
1710 #if __cplusplus >= 201103L
1715 {
return _M_erase(__position._M_const_cast()); }
1734 #if __cplusplus >= 201103L
1739 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1755 #if __cplusplus >= 201103L
1756 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1757 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1759 _M_impl._M_swap_data(__x._M_impl);
1760 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1761 __x._M_get_Tp_allocator());
1772 { _M_erase_at_end(
begin()); }
1777 #if __cplusplus < 201103L
1782 template<
typename _Integer>
1784 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1787 _M_get_Tp_allocator()));
1792 template<
typename _InputIterator>
1794 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1803 _S_check_init_len(
size_t __n,
const allocator_type& __a)
1805 if (__n > _S_max_size(__a))
1806 __throw_length_error(
1807 __N(
"cannot create std::deque larger than max_size()"));
1812 _S_max_size(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1814 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1816 return (
std::min)(__diffmax, __allocmax);
1831 template<
typename _InputIterator>
1837 template<
typename _ForwardIterator>
1856 #if __cplusplus >= 201103L
1859 _M_default_initialize();
1865 #if __cplusplus < 201103L
1870 template<
typename _Integer>
1872 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1873 { _M_fill_assign(__n, __val); }
1876 template<
typename _InputIterator>
1878 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1884 template<
typename _InputIterator>
1886 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1890 template<
typename _ForwardIterator>
1892 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1898 _ForwardIterator __mid = __first;
1900 std::copy(__first, __mid,
begin());
1901 _M_range_insert_aux(
end(), __mid, __last,
1905 _M_erase_at_end(std::copy(__first, __last,
begin()));
1911 _M_fill_assign(size_type __n,
const value_type& __val)
1916 _M_fill_insert(
end(), __n -
size(), __val);
1920 _M_erase_at_end(
begin() + difference_type(__n));
1927 #if __cplusplus < 201103L
1930 void _M_push_front_aux(
const value_type&);
1932 template<
typename... _Args>
1935 template<
typename... _Args>
1936 void _M_push_front_aux(_Args&&... __args);
1939 void _M_pop_back_aux();
1941 void _M_pop_front_aux();
1947 #if __cplusplus < 201103L
1952 template<
typename _Integer>
1954 _M_insert_dispatch(iterator __pos,
1955 _Integer __n, _Integer __x, __true_type)
1956 { _M_fill_insert(__pos, __n, __x); }
1959 template<
typename _InputIterator>
1961 _M_insert_dispatch(iterator __pos,
1962 _InputIterator __first, _InputIterator __last,
1965 _M_range_insert_aux(__pos, __first, __last,
1971 template<
typename _InputIterator>
1973 _M_range_insert_aux(iterator __pos, _InputIterator __first,
1977 template<
typename _ForwardIterator>
1979 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1986 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
1989 #if __cplusplus < 201103L
1991 _M_insert_aux(iterator __pos,
const value_type& __x);
1993 template<
typename... _Args>
1995 _M_insert_aux(iterator __pos, _Args&&... __args);
2000 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2003 template<
typename _ForwardIterator>
2005 _M_insert_aux(iterator __pos,
2006 _ForwardIterator __first, _ForwardIterator __last,
2013 _M_destroy_data_aux(iterator __first, iterator __last);
2017 template<
typename _Alloc1>
2019 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2020 { _M_destroy_data_aux(__first, __last); }
2023 _M_destroy_data(iterator __first, iterator __last,
2026 if (!__has_trivial_destructor(value_type))
2027 _M_destroy_data_aux(__first, __last);
2032 _M_erase_at_begin(iterator __pos)
2034 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2035 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2036 this->_M_impl._M_start = __pos;
2042 _M_erase_at_end(iterator __pos)
2044 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2045 _M_destroy_nodes(__pos._M_node + 1,
2046 this->_M_impl._M_finish._M_node + 1);
2047 this->_M_impl._M_finish = __pos;
2051 _M_erase(iterator __pos);
2054 _M_erase(iterator __first, iterator __last);
2056 #if __cplusplus >= 201103L
2059 _M_default_append(size_type __n);
2070 const size_type __vacancies = this->_M_impl._M_start._M_cur
2071 - this->_M_impl._M_start._M_first;
2072 if (__n > __vacancies)
2073 _M_new_elements_at_front(__n - __vacancies);
2074 return this->_M_impl._M_start - difference_type(__n);
2078 _M_reserve_elements_at_back(size_type __n)
2080 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2081 - this->_M_impl._M_finish._M_cur) - 1;
2082 if (__n > __vacancies)
2083 _M_new_elements_at_back(__n - __vacancies);
2084 return this->_M_impl._M_finish + difference_type(__n);
2088 _M_new_elements_at_front(size_type __new_elements);
2091 _M_new_elements_at_back(size_type __new_elements);
2106 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2107 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2108 _M_reallocate_map(__nodes_to_add,
false);
2112 _M_reserve_map_at_front(size_type __nodes_to_add = 1)
2114 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2115 - this->_M_impl._M_map))
2116 _M_reallocate_map(__nodes_to_add,
true);
2120 _M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front);
2123 #if __cplusplus >= 201103L
2129 this->_M_impl._M_swap_data(__x._M_impl);
2131 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2140 constexpr
bool __move_storage =
2141 _Alloc_traits::_S_propagate_on_move_assign();
2142 _M_move_assign2(
std::move(__x), __bool_constant<__move_storage>());
2147 template<
typename... _Args>
2149 _M_replace_map(_Args&&... __args)
2152 deque __newobj(std::forward<_Args>(__args)...);
2155 _M_deallocate_node(*
begin()._M_node);
2156 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2157 this->_M_impl._M_map =
nullptr;
2158 this->_M_impl._M_map_size = 0;
2160 this->_M_impl._M_swap_data(__newobj._M_impl);
2168 auto __alloc = __x._M_get_Tp_allocator();
2173 _M_get_Tp_allocator() =
std::move(__alloc);
2181 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2185 _M_replace_map(
std::move(__x), __x.get_allocator());
2191 _M_assign_aux(std::make_move_iterator(__x.begin()),
2192 std::make_move_iterator(__x.end()),
2200 #if __cpp_deduction_guides >= 201606
2201 template<
typename _InputIterator,
typename _ValT
2202 =
typename iterator_traits<_InputIterator>::value_type,
2203 typename _Allocator = allocator<_ValT>,
2204 typename = _RequireInputIter<_InputIterator>,
2205 typename = _RequireAllocator<_Allocator>>
2206 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2207 -> deque<_ValT, _Allocator>;
2220 template<
typename _Tp,
typename _Alloc>
2237 template<
typename _Tp,
typename _Alloc>
2244 template<
typename _Tp,
typename _Alloc>
2247 {
return !(__x == __y); }
2250 template<
typename _Tp,
typename _Alloc>
2253 {
return __y < __x; }
2256 template<
typename _Tp,
typename _Alloc>
2259 {
return !(__y < __x); }
2262 template<
typename _Tp,
typename _Alloc>
2265 {
return !(__x < __y); }
2268 template<
typename _Tp,
typename _Alloc>
2271 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2274 #undef _GLIBCXX_DEQUE_BUF_SIZE
2276 _GLIBCXX_END_NAMESPACE_CONTAINER
2278 #if __cplusplus >= 201103L
2282 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2286 _GLIBCXX_END_NAMESPACE_VERSION