62#if __cplusplus >= 201103L
66#if __cplusplus > 201703L
69#if __cplusplus > 202002L
75namespace std _GLIBCXX_VISIBILITY(default)
77_GLIBCXX_BEGIN_NAMESPACE_VERSION
78_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
94#ifndef _GLIBCXX_DEQUE_BUF_SIZE
95#define _GLIBCXX_DEQUE_BUF_SIZE 512
98 _GLIBCXX_CONSTEXPR
inline size_t
99 __deque_buf_size(
size_t __size)
115 template<
typename _Tp,
typename _Ref,
typename _Ptr>
118#if __cplusplus < 201103L
121 typedef _Tp* _Elt_pointer;
122 typedef _Tp** _Map_pointer;
125 template<
typename _CvTp>
135 {
return __deque_buf_size(
sizeof(_Tp)); }
138 typedef _Tp value_type;
139 typedef _Ptr pointer;
141 typedef size_t size_type;
142 typedef ptrdiff_t difference_type;
146 _Elt_pointer _M_first;
147 _Elt_pointer _M_last;
148 _Map_pointer _M_node;
151 : _M_cur(__x), _M_first(*__y),
152 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
155 : _M_cur(), _M_first(), _M_last(), _M_node() { }
157#if __cplusplus < 201103L
160 : _M_cur(__x._M_cur), _M_first(__x._M_first),
161 _M_last(__x._M_last), _M_node(__x._M_node) { }
164 template<
typename _Iter,
168 : _M_cur(__x._M_cur), _M_first(__x._M_first),
169 _M_last(__x._M_last), _M_node(__x._M_node) { }
172 : _M_cur(__x._M_cur), _M_first(__x._M_first),
173 _M_last(__x._M_last), _M_node(__x._M_node) { }
180 {
return iterator(_M_cur, _M_node); }
196 if (_M_cur == _M_last)
215 if (_M_cur == _M_first)
235 const difference_type __offset = __n + (_M_cur - _M_first);
236 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
241 __offset > 0 ? __offset / difference_type(_S_buffer_size())
242 : -difference_type((-__offset - 1)
243 / _S_buffer_size()) - 1;
246 * difference_type(_S_buffer_size()));
253 {
return *
this += -__n; }
258 {
return *(*
this + __n); }
270 _M_last = _M_first + difference_type(_S_buffer_size());
276 {
return __x._M_cur == __y._M_cur; }
281 template<
typename _RefR,
typename _PtrR>
284 operator==(
const _Self& __x,
285 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
287 {
return __x._M_cur == __y._M_cur; }
289#if __cpp_lib_three_way_comparison
291 friend strong_ordering
292 operator<=>(
const _Self& __x,
const _Self& __y)
noexcept
294 if (
const auto __cmp = __x._M_node <=> __y._M_node; __cmp != 0)
296 return __x._M_cur <=> __y._M_cur;
301 operator!=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
302 {
return !(__x == __y); }
304 template<
typename _RefR,
typename _PtrR>
307 operator!=(
const _Self& __x,
308 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
310 {
return !(__x == __y); }
314 operator<(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
316 return (__x._M_node == __y._M_node)
317 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
320 template<
typename _RefR,
typename _PtrR>
324 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
327 return (__x._M_node == __y._M_node)
328 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
333 operator>(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
334 {
return __y < __x; }
336 template<
typename _RefR,
typename _PtrR>
340 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
342 {
return __y < __x; }
346 operator<=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
347 {
return !(__y < __x); }
349 template<
typename _RefR,
typename _PtrR>
353 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
355 {
return !(__y < __x); }
359 operator>=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
360 {
return !(__x < __y); }
362 template<
typename _RefR,
typename _PtrR>
366 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
368 {
return !(__x < __y); }
372 friend difference_type
373 operator-(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
375 return difference_type(_S_buffer_size())
376 * (__x._M_node - __y._M_node - bool(__x._M_node))
377 + (__x._M_cur - __x._M_first)
378 + (__y._M_last - __y._M_cur);
385 template<
typename _RefR,
typename _PtrR>
387 friend difference_type
388 operator-(
const _Self& __x,
389 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
392 return difference_type(_S_buffer_size())
393 * (__x._M_node - __y._M_node - bool(__x._M_node))
394 + (__x._M_cur - __x._M_first)
395 + (__y._M_last - __y._M_cur);
400 operator+(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
409 operator-(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
418 operator+(difference_type __n,
const _Self& __x) _GLIBCXX_NOEXCEPT
419 {
return __x + __n; }
432 template<
typename _Tp,
typename _Alloc>
437 rebind<_Tp>::other _Tp_alloc_type;
440#if __cplusplus < 201103L
442 typedef const _Tp* _Ptr_const;
444 typedef typename _Alloc_traits::pointer _Ptr;
445 typedef typename _Alloc_traits::const_pointer _Ptr_const;
448 typedef typename _Alloc_traits::template rebind<_Ptr>::other
452 typedef _Alloc allocator_type;
456 {
return allocator_type(_M_get_Tp_allocator()); }
477#if __cplusplus >= 201103L
479 : _M_impl(
std::move(__x._M_get_Tp_allocator()))
482 if (__x._M_impl._M_map)
483 this->_M_impl._M_swap_data(__x._M_impl);
487 : _M_impl(
std::move(__x._M_impl), _Tp_alloc_type(__a))
488 { __x._M_initialize_map(0); }
493 if (__x.get_allocator() == __a)
495 if (__x._M_impl._M_map)
498 this->_M_impl._M_swap_data(__x._M_impl);
510 typedef typename iterator::_Map_pointer _Map_pointer;
512 struct _Deque_impl_data
520 : _M_map(), _M_map_size(), _M_start(), _M_finish()
523#if __cplusplus >= 201103L
524 _Deque_impl_data(
const _Deque_impl_data&) =
default;
526 operator=(
const _Deque_impl_data&) =
default;
528 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
529 : _Deque_impl_data(__x)
530 { __x = _Deque_impl_data(); }
538 std::swap(*
this, __x);
546 :
public _Tp_alloc_type,
public _Deque_impl_data
554 : _Tp_alloc_type(__a)
557#if __cplusplus >= 201103L
558 _Deque_impl(_Deque_impl&&) =
default;
560 _Deque_impl(_Tp_alloc_type&& __a) noexcept
564 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
572 {
return this->_M_impl; }
574 const _Tp_alloc_type&
576 {
return this->_M_impl; }
580 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
586 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
593 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
597 _M_allocate_map(
size_t __n)
599 _Map_alloc_type
__map_alloc = _M_get_map_allocator();
606 _Map_alloc_type
__map_alloc = _M_get_map_allocator();
612 void _M_destroy_nodes(_Map_pointer
__nstart,
614 enum { _S_initial_map_size = 8 };
619 template<
typename _Tp,
typename _Alloc>
620 _Deque_base<_Tp, _Alloc>::
621 ~_Deque_base() _GLIBCXX_NOEXCEPT
623 if (this->_M_impl._M_map)
625 _M_destroy_nodes(this->_M_impl._M_start._M_node,
626 this->_M_impl._M_finish._M_node + 1);
627 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
639 template<
typename _Tp,
typename _Alloc>
647 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
649 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
656 _Map_pointer
__nstart = (this->_M_impl._M_map
664 _M_deallocate_map(this->_M_impl._M_map,
this->_M_impl._M_map_size);
665 this->_M_impl._M_map = _Map_pointer();
666 this->_M_impl._M_map_size = 0;
667 __throw_exception_again;
670 this->_M_impl._M_start._M_set_node(
__nstart);
671 this->_M_impl._M_finish._M_set_node(
__nfinish - 1);
672 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
673 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
675 % __deque_buf_size(
sizeof(_Tp)));
678 template<
typename _Tp,
typename _Alloc>
687 *
__cur = this->_M_allocate_node();
691 _M_destroy_nodes(__nstart, __cur);
692 __throw_exception_again;
696 template<
typename _Tp,
typename _Alloc>
698 _Deque_base<_Tp, _Alloc>::
699 _M_destroy_nodes(_Map_pointer __nstart,
700 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
702 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
703 _M_deallocate_node(*__n);
790 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
793#ifdef _GLIBCXX_CONCEPT_CHECKS
796# if __cplusplus < 201103L
797 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
802#if __cplusplus >= 201103L
804 "std::deque must have a non-const, non-volatile value_type");
805# if __cplusplus > 201703L || defined __STRICT_ANSI__
807 "std::deque must have the same value_type as its allocator");
812 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
814 typedef typename _Base::_Map_pointer _Map_pointer;
817 typedef _Tp value_type;
818 typedef typename _Alloc_traits::pointer
pointer;
819 typedef typename _Alloc_traits::const_pointer const_pointer;
820 typedef typename _Alloc_traits::reference reference;
821 typedef typename _Alloc_traits::const_reference const_reference;
826 typedef size_t size_type;
828 typedef _Alloc allocator_type;
832 {
return __deque_buf_size(
sizeof(_Tp)); }
836 using _Base::_M_create_nodes;
837 using _Base::_M_destroy_nodes;
838 using _Base::_M_allocate_node;
839 using _Base::_M_deallocate_node;
840 using _Base::_M_allocate_map;
841 using _Base::_M_deallocate_map;
842 using _Base::_M_get_Tp_allocator;
848 using _Base::_M_impl;
857#if __cplusplus >= 201103L
871#if __cplusplus >= 201103L
881 deque(size_type __n,
const allocator_type& __a = allocator_type())
882 :
_Base(__a, _S_check_init_len(__n, __a))
883 { _M_default_initialize(); }
893 deque(size_type __n,
const value_type& __value,
894 const allocator_type& __a = allocator_type())
895 :
_Base(__a, _S_check_init_len(__n, __a))
907 deque(size_type __n,
const value_type& __value = value_type(),
908 const allocator_type& __a = allocator_type())
909 : _Base(__a, _S_check_init_len(__n, __a))
924 this->_M_impl._M_start,
925 _M_get_Tp_allocator()); }
927#if __cplusplus >= 201103L
942 this->_M_impl._M_start,
943 _M_get_Tp_allocator()); }
958 if (__x.get_allocator() != __a && !__x.empty())
961 this->_M_impl._M_start,
962 _M_get_Tp_allocator());
980 const allocator_type& __a = allocator_type())
1003#if __cplusplus >= 201103L
1007 const allocator_type& __a = allocator_type())
1014 template<
typename _InputIterator>
1016 const allocator_type& __a = allocator_type())
1020 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
1021 _M_initialize_dispatch(__first, __last,
_Integral());
1025#if __glibcxx_containers_ranges
1031 template<__detail::__container_compatible_range<_Tp> _Rg>
1032 deque(from_range_t, _Rg&& __rg,
const allocator_type& __a = _Alloc())
1043 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
1057#if __cplusplus >= 201103L
1088 _M_assign_aux(
__l.begin(),
__l.end(),
1105 assign(size_type __n,
const value_type& __val)
1106 { _M_fill_assign(__n, __val); }
1120#if __cplusplus >= 201103L
1127 template<
typename _InputIterator>
1131 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
1132 _M_assign_dispatch(__first, __last,
_Integral());
1136#if __cplusplus >= 201103L
1153#if __glibcxx_containers_ranges
1160 template<__detail::__container_compatible_range<_Tp> _Rg>
1166 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1168 const size_type __n(ranges::distance(
__rg));
1172 return _M_erase_at_end(
__res.out);
1175 auto __rest = ranges::copy_n(ranges::begin(__rg),
size(),
1177 _M_range_append(
std::move(__rest), ranges::end(__rg),
1182 auto __first = ranges::begin(__rg);
1183 const auto __last = ranges::end(__rg);
1184 for (iterator __it =
begin(), __end =
end();
1185 __it != __end; (void)++__first, ++__it)
1187 if (__first == __last)
1188 return _M_erase_at_end(__it);
1193 for (; __first != __last; ++__first)
1194 emplace_back(*__first);
1204 {
return _Base::get_allocator(); }
1214 {
return this->_M_impl._M_start; }
1223 {
return this->_M_impl._M_start; }
1233 {
return this->_M_impl._M_finish; }
1243 {
return this->_M_impl._M_finish; }
1261 const_reverse_iterator
1281 const_reverse_iterator
1285#if __cplusplus >= 201103L
1293 {
return this->_M_impl._M_start; }
1303 {
return this->_M_impl._M_finish; }
1311 const_reverse_iterator
1321 const_reverse_iterator
1332 size_type
__sz = this->_M_impl._M_finish - this->_M_impl._M_start;
1342 {
return _S_max_size(_M_get_Tp_allocator()); }
1344#if __cplusplus >= 201103L
1361 _M_erase_at_end(this->_M_impl._M_start
1398 _M_erase_at_end(this->_M_impl._M_start
1402#if __cplusplus >= 201103L
1406 { _M_shrink_to_fit(); }
1413 _GLIBCXX_NODISCARD
bool
1415 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1433 __glibcxx_requires_subscript(__n);
1452 __glibcxx_requires_subscript(__n);
1461 if (__n >= this->
size())
1462 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n "
1463 "(which is %zu)>= this->size() "
1484 return (*
this)[__n];
1502 return (*
this)[__n];
1513 __glibcxx_requires_nonempty();
1525 __glibcxx_requires_nonempty();
1537 __glibcxx_requires_nonempty();
1551 __glibcxx_requires_nonempty();
1570 if (this->_M_impl._M_start._M_cur !=
this->_M_impl._M_start._M_first)
1572 _Alloc_traits::construct(this->_M_impl,
1573 this->_M_impl._M_start._M_cur - 1,
1575 --this->_M_impl._M_start._M_cur;
1581#if __cplusplus >= 201103L
1586 template<
typename... _Args>
1587#if __cplusplus > 201402L
1592 emplace_front(_Args&&... __args);
1607 if (this->_M_impl._M_finish._M_cur
1608 !=
this->_M_impl._M_finish._M_last - 1)
1610 _Alloc_traits::construct(this->_M_impl,
1611 this->_M_impl._M_finish._M_cur, __x);
1612 ++this->_M_impl._M_finish._M_cur;
1618#if __cplusplus >= 201103L
1623 template<
typename... _Args>
1624#if __cplusplus > 201402L
1629 emplace_back(_Args&&... __args);
1643 __glibcxx_requires_nonempty();
1644 if (this->_M_impl._M_start._M_cur
1645 !=
this->_M_impl._M_start._M_last - 1)
1647 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1648 this->_M_impl._M_start._M_cur);
1649 ++this->_M_impl._M_start._M_cur;
1666 __glibcxx_requires_nonempty();
1667 if (this->_M_impl._M_finish._M_cur
1668 !=
this->_M_impl._M_finish._M_first)
1670 --this->_M_impl._M_finish._M_cur;
1671 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1672 this->_M_impl._M_finish._M_cur);
1678#if __cplusplus >= 201103L
1688 template<
typename...
_Args>
1717#if __cplusplus >= 201103L
1744 auto __offset = __p -
cbegin();
1745 _M_range_insert_aux(__p._M_const_cast(),
__l.begin(),
__l.end(),
1747 return begin() + __offset;
1764 _M_fill_insert(
__position._M_const_cast(), __n, __x);
1765 return begin() + __offset;
1782#if __cplusplus >= 201103L
1794 template<
typename _InputIterator,
1801 _M_range_insert_aux(
__position._M_const_cast(), __first, __last,
1803 return begin() + __offset;
1816 template<
typename _InputIterator>
1822 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
1827#if __glibcxx_containers_ranges
1836 template<__detail::__container_compatible_range<_Tp> _Rg>
1838 insert_range(const_iterator __pos, _Rg&& __rg);
1845 template<__detail::__container_compatible_range<_Tp> _Rg>
1847 prepend_range(_Rg&& __rg);
1854 template<__detail::__container_compatible_range<_Tp> _Rg>
1856 append_range(_Rg&& __rg);
1873#if __cplusplus >= 201103L
1878 {
return _M_erase(
__position._M_const_cast()); }
1897#if __cplusplus >= 201103L
1902 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1918#if __cplusplus >= 201103L
1919 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1920 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1922 _M_impl._M_swap_data(__x._M_impl);
1923 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1924 __x._M_get_Tp_allocator());
1935 { _M_erase_at_end(
begin()); }
1940#if __cplusplus < 201103L
1945 template<
typename _Integer>
1949 _M_initialize_map(_S_check_init_len(
static_cast<size_type
>(__n),
1950 _M_get_Tp_allocator()));
1955 template<
typename _InputIterator>
1957 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1966 _S_check_init_len(
size_t __n,
const allocator_type& __a)
1968 if (__n > _S_max_size(__a))
1969 __throw_length_error(
1970 __N(
"cannot create std::deque larger than max_size()"));
1975 _S_max_size(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1977 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1979 return (
std::min)(__diffmax, __allocmax);
1994 template<
typename _InputIterator>
2000 template<
typename _ForwardIterator>
2019#if __cplusplus >= 201103L
2022 _M_default_initialize();
2028#if __cplusplus < 201103L
2033 template<
typename _Integer>
2035 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
2036 { _M_fill_assign(__n, __val); }
2039 template<
typename _InputIterator>
2041 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
2047 template<
typename _InputIterator>
2049 _M_assign_aux(_InputIterator __first, _InputIterator __last,
2053 template<
typename _ForwardIterator>
2055 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
2061 _ForwardIterator __mid = __first;
2063 std::copy(__first, __mid,
begin());
2064 _M_range_insert_aux(
end(), __mid, __last,
2068 _M_erase_at_end(std::copy(__first, __last,
begin()));
2074 _M_fill_assign(size_type __n,
const value_type& __val)
2079 _M_fill_insert(
end(), __n -
size(), __val);
2083 _M_erase_at_end(
begin() + difference_type(__n));
2090#if __cplusplus < 201103L
2095 template<
typename... _Args>
2098 template<
typename... _Args>
2110#if __cplusplus < 201103L
2115 template<
typename _Integer>
2117 _M_insert_dispatch(iterator __pos,
2118 _Integer __n, _Integer __x, __true_type)
2119 { _M_fill_insert(__pos, __n, __x); }
2122 template<
typename _InputIterator>
2124 _M_insert_dispatch(iterator __pos,
2125 _InputIterator __first, _InputIterator __last,
2128 _M_range_insert_aux(__pos, __first, __last,
2134 template<
typename _InputIterator,
typename _Sentinel>
2135 void _M_range_prepend(_InputIterator __first, _Sentinel __last,
2139 template<
typename _InputIterator,
typename _Sentinel>
2140 void _M_range_append(_InputIterator __first, _Sentinel __last,
2144 template<
typename _InputIterator>
2146 _M_range_insert_aux(iterator __pos, _InputIterator __first,
2150 template<
typename _ForwardIterator>
2152 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2159 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
2162#if __cplusplus < 201103L
2164 _M_insert_aux(iterator __pos,
const value_type& __x);
2167 _M_insert_aux(iterator __pos,
const value_type& __x)
2168 {
return _M_emplace_aux(__pos, __x); }
2170 template<
typename... _Args>
2172 _M_emplace_aux(iterator __pos, _Args&&... __args);
2177 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2180 template<
typename _ForwardIterator>
2182 _M_insert_aux(iterator __pos,
2183 _ForwardIterator __first, _ForwardIterator __last,
2190 _M_destroy_data_aux(iterator __first, iterator __last);
2194 template<
typename _Alloc1>
2196 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2197 { _M_destroy_data_aux(__first, __last); }
2200 _M_destroy_data(iterator __first, iterator __last,
2203 if (!__has_trivial_destructor(value_type))
2204 _M_destroy_data_aux(__first, __last);
2209 _M_erase_at_begin(iterator __pos)
2211 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2212 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2213 this->_M_impl._M_start = __pos;
2219 _M_erase_at_end(iterator __pos)
2221 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2222 _M_destroy_nodes(__pos._M_node + 1,
2223 this->_M_impl._M_finish._M_node + 1);
2224 this->_M_impl._M_finish = __pos;
2228 _M_erase(iterator __pos);
2231 _M_erase(iterator __first, iterator __last);
2233#if __cplusplus >= 201103L
2236 _M_default_append(size_type __n);
2247 const size_type
__vacancies = this->_M_impl._M_start._M_cur
2248 - this->_M_impl._M_start._M_first;
2257 const size_type
__vacancies = (this->_M_impl._M_finish._M_last
2258 - this->_M_impl._M_finish._M_cur) - 1;
2284 - (
this->_M_impl._M_finish._M_node -
this->_M_impl._M_map))
2292 -
this->_M_impl._M_map))
2300#if __cplusplus >= 201103L
2306 this->_M_impl._M_swap_data(__x._M_impl);
2317 if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
2320 constexpr bool __move_storage =
2321 _Alloc_traits::_S_propagate_on_move_assign();
2322 _M_move_assign2(
std::move(__x), __bool_constant<__move_storage>());
2327 template<
typename... _Args>
2329 _M_replace_map(_Args&&... __args)
2335 _M_deallocate_node(*
begin()._M_node);
2336 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2337 this->_M_impl._M_map =
nullptr;
2338 this->_M_impl._M_map_size = 0;
2340 this->_M_impl._M_swap_data(__newobj._M_impl);
2348 auto __alloc = __x._M_get_Tp_allocator();
2353 _M_get_Tp_allocator() =
std::move(__alloc);
2361 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2365 _M_replace_map(
std::move(__x), __x.get_allocator());
2371 _M_assign_aux(std::make_move_iterator(__x.begin()),
2372 std::make_move_iterator(__x.end()),
2380#if __cpp_deduction_guides >= 201606
2381 template<
typename _InputIterator,
typename _ValT
2382 =
typename iterator_traits<_InputIterator>::value_type,
2383 typename _Allocator = allocator<_ValT>,
2384 typename = _RequireInputIter<_InputIterator>,
2385 typename = _RequireAllocator<_Allocator>>
2386 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2387 -> deque<_ValT, _Allocator>;
2389#if __glibcxx_containers_ranges
2390 template<ranges::input_range _Rg,
2391 typename _Alloc = allocator<ranges::range_value_t<_Rg>>>
2392 deque(from_range_t, _Rg&&, _Alloc = _Alloc())
2393 -> deque<ranges::range_value_t<_Rg>, _Alloc>;
2407 template<
typename _Tp,
typename _Alloc>
2411 {
return __x.size() == __y.size()
2412 && std::equal(__x.begin(), __x.end(), __y.begin()); }
2414#if __cpp_lib_three_way_comparison
2426 template<
typename _Tp,
typename _Alloc>
2428 inline __detail::__synth3way_t<_Tp>
2429 operator<=>(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2432 __y.begin(), __y.end(),
2433 __detail::__synth3way);
2447 template<
typename _Tp,
typename _Alloc>
2450 operator<(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2451 {
return std::lexicographical_compare(__x.begin(), __x.end(),
2452 __y.begin(), __y.end()); }
2455 template<
typename _Tp,
typename _Alloc>
2458 operator!=(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2459 {
return !(__x == __y); }
2462 template<
typename _Tp,
typename _Alloc>
2465 operator>(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2466 {
return __y < __x; }
2469 template<
typename _Tp,
typename _Alloc>
2472 operator<=(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2473 {
return !(__y < __x); }
2476 template<
typename _Tp,
typename _Alloc>
2479 operator>=(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2480 {
return !(__x < __y); }
2484 template<
typename _Tp,
typename _Alloc>
2490#undef _GLIBCXX_DEQUE_BUF_SIZE
2492_GLIBCXX_END_NAMESPACE_CONTAINER
2494#if __cplusplus >= 201103L
2498 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2502_GLIBCXX_END_NAMESPACE_VERSION
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
is_nothrow_default_constructible
typename __detected_or_t< is_empty< _Alloc >, __equal, _Alloc >::type is_always_equal
Whether all instances of the allocator type compare equal.
void _M_set_node(_Map_pointer __new_node) noexcept
void _M_initialize_map(size_t)
Layout storage.
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
reverse_iterator rbegin() noexcept
deque(const deque &__x)
Deque copy constructor.
const_reference at(size_type __n) const
Provides access to the data contained in the deque.
reverse_iterator rend() noexcept
iterator erase(const_iterator __position)
Remove element at given position.
const_reference back() const noexcept
const_reverse_iterator crend() const noexcept
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
void pop_back() noexcept
Removes last element.
size_type size() const noexcept
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
Memory-handling helpers for the major map.
const_iterator cbegin() const noexcept
void resize(size_type __new_size)
Resizes the deque to the specified number of elements.
const_reverse_iterator rend() const noexcept
iterator _M_reserve_elements_at_front(size_type __n)
Memory-handling helpers for the previous internal insert functions.
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in deque before specified iterator.
void pop_front() noexcept
Removes first element.
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
void swap(deque &__x) noexcept
Swaps data with another deque.
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the deque.
reference at(size_type __n)
Provides access to the data contained in the deque.
deque(size_type __n, const allocator_type &__a=allocator_type())
Creates a deque with default constructed elements.
bool empty() const noexcept
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the deque.
size_type max_size() const noexcept
void push_front(const value_type &__x)
Add data to the front of the deque.
void resize(size_type __new_size, const value_type &__x)
Resizes the deque to the specified number of elements.
const_reference front() const noexcept
void assign(size_type __n, const value_type &__val)
Assigns a given value to a deque.
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
void _M_fill_initialize(const value_type &__value)
Fills the deque with copies of value.
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into deque before specified iterator.
deque(const deque &__x, const __type_identity_t< allocator_type > &__a)
Copy constructor with alternative allocator.
void _M_new_elements_at_back(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
deque(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a deque with copies of an exemplar element.
const_reverse_iterator crbegin() const noexcept
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
reference back() noexcept
void _M_new_elements_at_front(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
deque()=default
Creates a deque with no elements.
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
void push_back(const value_type &__x)
Add data to the end of the deque.
deque(const allocator_type &__a)
Creates a deque with no elements.
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
void _M_range_check(size_type __n) const
Safety check used only from at().
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
void shrink_to_fit() noexcept
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
const_iterator begin() const noexcept
deque & operator=(const deque &__x)
Deque assignment operator.
const_iterator end() const noexcept
iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the deque.
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
void _M_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
Fills the deque with whatever is in [first,last).
reference front() noexcept
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
const_iterator cend() const noexcept
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
const_reverse_iterator rbegin() const noexcept
deque(deque &&__x, const __type_identity_t< allocator_type > &__a)
Move constructor with alternative allocator.
iterator begin() noexcept
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
deque(deque &&)=default
Deque move constructor.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Tp_alloc_type &__a) noexcept
The maximum supported allocation size.