62#if __cplusplus >= 201103L
66#if __cplusplus > 201703L
72namespace std _GLIBCXX_VISIBILITY(default)
74_GLIBCXX_BEGIN_NAMESPACE_VERSION
75_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
91#ifndef _GLIBCXX_DEQUE_BUF_SIZE
92#define _GLIBCXX_DEQUE_BUF_SIZE 512
95 _GLIBCXX_CONSTEXPR
inline size_t
96 __deque_buf_size(
size_t __size)
112 template<
typename _Tp,
typename _Ref,
typename _Ptr>
113 struct _Deque_iterator
115#if __cplusplus < 201103L
116 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
117 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
118 typedef _Tp* _Elt_pointer;
119 typedef _Tp** _Map_pointer;
122 template<
typename _CvTp>
123 using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_rebind<_Ptr, _CvTp>>;
125 typedef __iter<_Tp> iterator;
126 typedef __iter<const _Tp> const_iterator;
131 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
132 {
return __deque_buf_size(
sizeof(_Tp)); }
135 typedef _Tp value_type;
136 typedef _Ptr pointer;
137 typedef _Ref reference;
138 typedef size_t size_type;
139 typedef ptrdiff_t difference_type;
140 typedef _Deque_iterator _Self;
143 _Elt_pointer _M_first;
144 _Elt_pointer _M_last;
145 _Map_pointer _M_node;
147 _Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT
148 : _M_cur(__x), _M_first(*__y),
149 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
151 _Deque_iterator() _GLIBCXX_NOEXCEPT
152 : _M_cur(), _M_first(), _M_last(), _M_node() { }
154#if __cplusplus < 201103L
156 _Deque_iterator(
const iterator& __x) _GLIBCXX_NOEXCEPT
157 : _M_cur(__x._M_cur), _M_first(__x._M_first),
158 _M_last(__x._M_last), _M_node(__x._M_node) { }
161 template<
typename _Iter,
162 typename = _Require<is_same<_Self, const_iterator>,
164 _Deque_iterator(
const _Iter& __x) noexcept
165 : _M_cur(__x._M_cur), _M_first(__x._M_first),
166 _M_last(__x._M_last), _M_node(__x._M_node) { }
168 _Deque_iterator(
const _Deque_iterator& __x) noexcept
169 : _M_cur(__x._M_cur), _M_first(__x._M_first),
170 _M_last(__x._M_last), _M_node(__x._M_node) { }
172 _Deque_iterator& operator=(
const _Deque_iterator&) =
default;
176 _M_const_cast()
const _GLIBCXX_NOEXCEPT
177 {
return iterator(_M_cur, _M_node); }
181 operator*()
const _GLIBCXX_NOEXCEPT
186 operator->()
const _GLIBCXX_NOEXCEPT
190 operator++() _GLIBCXX_NOEXCEPT
193 if (_M_cur == _M_last)
202 operator++(
int) _GLIBCXX_NOEXCEPT
210 operator--() _GLIBCXX_NOEXCEPT
212 if (_M_cur == _M_first)
222 operator--(
int) _GLIBCXX_NOEXCEPT
230 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
232 const difference_type __offset = __n + (_M_cur - _M_first);
233 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
237 const difference_type __node_offset =
238 __offset > 0 ? __offset / difference_type(_S_buffer_size())
239 : -difference_type((-__offset - 1)
240 / _S_buffer_size()) - 1;
242 _M_cur = _M_first + (__offset - __node_offset
243 * difference_type(_S_buffer_size()));
249 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
250 {
return *
this += -__n; }
254 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
255 {
return *(*
this + __n); }
265 _M_node = __new_node;
266 _M_first = *__new_node;
267 _M_last = _M_first + difference_type(_S_buffer_size());
272 operator==(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
273 {
return __x._M_cur == __y._M_cur; }
278 template<
typename _RefR,
typename _PtrR>
281 operator==(
const _Self& __x,
282 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
284 {
return __x._M_cur == __y._M_cur; }
286#if __cpp_lib_three_way_comparison
288 friend strong_ordering
289 operator<=>(
const _Self& __x,
const _Self& __y)
noexcept
291 if (
const auto __cmp = __x._M_node <=> __y._M_node; __cmp != 0)
293 return __x._M_cur <=> __y._M_cur;
298 operator!=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
299 {
return !(__x == __y); }
301 template<
typename _RefR,
typename _PtrR>
304 operator!=(
const _Self& __x,
305 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
307 {
return !(__x == __y); }
311 operator<(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
313 return (__x._M_node == __y._M_node)
314 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
317 template<
typename _RefR,
typename _PtrR>
321 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
324 return (__x._M_node == __y._M_node)
325 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
330 operator>(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
331 {
return __y < __x; }
333 template<
typename _RefR,
typename _PtrR>
337 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
339 {
return __y < __x; }
343 operator<=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
344 {
return !(__y < __x); }
346 template<
typename _RefR,
typename _PtrR>
350 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
352 {
return !(__y < __x); }
356 operator>=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
357 {
return !(__x < __y); }
359 template<
typename _RefR,
typename _PtrR>
363 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
365 {
return !(__x < __y); }
369 friend difference_type
370 operator-(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
372 return difference_type(_S_buffer_size())
373 * (__x._M_node - __y._M_node - bool(__x._M_node))
374 + (__x._M_cur - __x._M_first)
375 + (__y._M_last - __y._M_cur);
382 template<
typename _RefR,
typename _PtrR>
384 friend difference_type
385 operator-(
const _Self& __x,
386 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
389 return difference_type(_S_buffer_size())
390 * (__x._M_node - __y._M_node - bool(__x._M_node))
391 + (__x._M_cur - __x._M_first)
392 + (__y._M_last - __y._M_cur);
397 operator+(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
406 operator-(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
415 operator+(difference_type __n,
const _Self& __x) _GLIBCXX_NOEXCEPT
416 {
return __x + __n; }
429 template<
typename _Tp,
typename _Alloc>
434 rebind<_Tp>::other _Tp_alloc_type;
437#if __cplusplus < 201103L
439 typedef const _Tp* _Ptr_const;
441 typedef typename _Alloc_traits::pointer _Ptr;
442 typedef typename _Alloc_traits::const_pointer _Ptr_const;
445 typedef typename _Alloc_traits::template rebind<_Ptr>::other
449 typedef _Alloc allocator_type;
452 get_allocator()
const _GLIBCXX_NOEXCEPT
453 {
return allocator_type(_M_get_Tp_allocator()); }
462 _Deque_base(
size_t __num_elements)
466 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
470 _Deque_base(
const allocator_type& __a)
474#if __cplusplus >= 201103L
475 _Deque_base(_Deque_base&& __x)
476 : _M_impl(
std::move(__x._M_get_Tp_allocator()))
479 if (__x._M_impl._M_map)
480 this->_M_impl._M_swap_data(__x._M_impl);
483 _Deque_base(_Deque_base&& __x,
const allocator_type& __a)
484 : _M_impl(
std::move(__x._M_impl), _Tp_alloc_type(__a))
485 { __x._M_initialize_map(0); }
487 _Deque_base(_Deque_base&& __x,
const allocator_type& __a,
size_t __n)
490 if (__x.get_allocator() == __a)
492 if (__x._M_impl._M_map)
495 this->_M_impl._M_swap_data(__x._M_impl);
505 ~_Deque_base() _GLIBCXX_NOEXCEPT;
507 typedef typename iterator::_Map_pointer _Map_pointer;
509 struct _Deque_impl_data
516 _Deque_impl_data() _GLIBCXX_NOEXCEPT
517 : _M_map(), _M_map_size(), _M_start(), _M_finish()
520#if __cplusplus >= 201103L
521 _Deque_impl_data(
const _Deque_impl_data&) =
default;
523 operator=(
const _Deque_impl_data&) =
default;
525 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
526 : _Deque_impl_data(__x)
527 { __x = _Deque_impl_data(); }
531 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
535 std::swap(*
this, __x);
543 :
public _Tp_alloc_type,
public _Deque_impl_data
545 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
550 _Deque_impl(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
551 : _Tp_alloc_type(__a)
554#if __cplusplus >= 201103L
555 _Deque_impl(_Deque_impl&&) =
default;
557 _Deque_impl(_Tp_alloc_type&& __a) noexcept
561 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
568 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
569 {
return this->_M_impl; }
571 const _Tp_alloc_type&
572 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
573 {
return this->_M_impl; }
576 _M_get_map_allocator()
const _GLIBCXX_NOEXCEPT
577 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
583 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
587 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
590 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
594 _M_allocate_map(
size_t __n)
596 _Map_alloc_type __map_alloc = _M_get_map_allocator();
601 _M_deallocate_map(_Map_pointer __p,
size_t __n) _GLIBCXX_NOEXCEPT
603 _Map_alloc_type __map_alloc = _M_get_map_allocator();
608 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
609 void _M_destroy_nodes(_Map_pointer __nstart,
610 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
611 enum { _S_initial_map_size = 8 };
616 template<
typename _Tp,
typename _Alloc>
617 _Deque_base<_Tp, _Alloc>::
618 ~_Deque_base() _GLIBCXX_NOEXCEPT
620 if (this->_M_impl._M_map)
622 _M_destroy_nodes(this->_M_impl._M_start._M_node,
623 this->_M_impl._M_finish._M_node + 1);
624 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
636 template<
typename _Tp,
typename _Alloc>
641 const size_t __num_nodes = (__num_elements / __deque_buf_size(
sizeof(_Tp))
644 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
645 size_t(__num_nodes + 2));
646 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
653 _Map_pointer __nstart = (this->_M_impl._M_map
654 + (this->_M_impl._M_map_size - __num_nodes) / 2);
655 _Map_pointer __nfinish = __nstart + __num_nodes;
658 { _M_create_nodes(__nstart, __nfinish); }
661 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
662 this->_M_impl._M_map = _Map_pointer();
663 this->_M_impl._M_map_size = 0;
664 __throw_exception_again;
667 this->_M_impl._M_start._M_set_node(__nstart);
668 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
669 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
670 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
672 % __deque_buf_size(
sizeof(_Tp)));
675 template<
typename _Tp,
typename _Alloc>
683 for (__cur = __nstart; __cur < __nfinish; ++__cur)
684 *__cur = this->_M_allocate_node();
688 _M_destroy_nodes(__nstart, __cur);
689 __throw_exception_again;
693 template<
typename _Tp,
typename _Alloc>
697 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
699 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
700 _M_deallocate_node(*__n);
787 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
788 class deque :
protected _Deque_base<_Tp, _Alloc>
790#ifdef _GLIBCXX_CONCEPT_CHECKS
792 typedef typename _Alloc::value_type _Alloc_value_type;
793# if __cplusplus < 201103L
794 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
796 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
799#if __cplusplus >= 201103L
801 "std::deque must have a non-const, non-volatile value_type");
802# if __cplusplus > 201703L || defined __STRICT_ANSI__
804 "std::deque must have the same value_type as its allocator");
808 typedef _Deque_base<_Tp, _Alloc> _Base;
809 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
810 typedef typename _Base::_Alloc_traits _Alloc_traits;
811 typedef typename _Base::_Map_pointer _Map_pointer;
814 typedef _Tp value_type;
815 typedef typename _Alloc_traits::pointer pointer;
816 typedef typename _Alloc_traits::const_pointer const_pointer;
817 typedef typename _Alloc_traits::reference reference;
818 typedef typename _Alloc_traits::const_reference const_reference;
819 typedef typename _Base::iterator iterator;
820 typedef typename _Base::const_iterator const_iterator;
823 typedef size_t size_type;
824 typedef ptrdiff_t difference_type;
825 typedef _Alloc allocator_type;
828 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
829 {
return __deque_buf_size(
sizeof(_Tp)); }
833 using _Base::_M_create_nodes;
834 using _Base::_M_destroy_nodes;
835 using _Base::_M_allocate_node;
836 using _Base::_M_deallocate_node;
837 using _Base::_M_allocate_map;
838 using _Base::_M_deallocate_map;
839 using _Base::_M_get_Tp_allocator;
845 using _Base::_M_impl;
854#if __cplusplus >= 201103L
868#if __cplusplus >= 201103L
878 deque(size_type __n,
const allocator_type& __a = allocator_type())
879 : _Base(__a, _S_check_init_len(__n, __a))
880 { _M_default_initialize(); }
890 deque(size_type __n,
const value_type& __value,
891 const allocator_type& __a = allocator_type())
892 : _Base(__a, _S_check_init_len(__n, __a))
905 const allocator_type& __a = allocator_type())
906 : _Base(__a, _S_check_init_len(__n, __a))
918 : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),
920 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
921 this->_M_impl._M_start,
922 _M_get_Tp_allocator()); }
924#if __cplusplus >= 201103L
936 deque(
const deque& __x,
const __type_identity_t<allocator_type>& __a)
937 : _Base(__a, __x.
size())
938 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
939 this->_M_impl._M_start,
940 _M_get_Tp_allocator()); }
943 deque(
deque&& __x,
const __type_identity_t<allocator_type>& __a)
944 :
deque(
std::
move(__x), __a, typename _Alloc_traits::is_always_equal{})
952 deque(deque&& __x,
const allocator_type& __a, false_type)
955 if (__x.get_allocator() != __a && !__x.empty())
957 std::__uninitialized_move_a(__x.begin(), __x.end(),
958 this->_M_impl._M_start,
959 _M_get_Tp_allocator());
977 const allocator_type& __a = allocator_type())
1000#if __cplusplus >= 201103L
1001 template<
typename _InputIterator,
1002 typename = std::_RequireInputIter<_InputIterator>>
1003 deque(_InputIterator __first, _InputIterator __last,
1004 const allocator_type& __a = allocator_type())
1011 template<
typename _InputIterator>
1012 deque(_InputIterator __first, _InputIterator __last,
1013 const allocator_type& __a = allocator_type())
1017 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1018 _M_initialize_dispatch(__first, __last, _Integral());
1028 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
1042#if __cplusplus >= 201103L
1055 _M_move_assign1(
std::move(__x), __always_equal{});
1073 _M_assign_aux(__l.begin(), __l.end(),
1090 assign(size_type __n,
const value_type& __val)
1091 { _M_fill_assign(__n, __val); }
1105#if __cplusplus >= 201103L
1106 template<
typename _InputIterator,
1107 typename = std::_RequireInputIter<_InputIterator>>
1109 assign(_InputIterator __first, _InputIterator __last)
1112 template<
typename _InputIterator>
1114 assign(_InputIterator __first, _InputIterator __last)
1116 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1117 _M_assign_dispatch(__first, __last, _Integral());
1121#if __cplusplus >= 201103L
1142 {
return _Base::get_allocator(); }
1152 {
return this->_M_impl._M_start; }
1161 {
return this->_M_impl._M_start; }
1171 {
return this->_M_impl._M_finish; }
1181 {
return this->_M_impl._M_finish; }
1191 {
return reverse_iterator(this->_M_impl._M_finish); }
1199 const_reverse_iterator
1201 {
return const_reverse_iterator(this->_M_impl._M_finish); }
1211 {
return reverse_iterator(this->_M_impl._M_start); }
1219 const_reverse_iterator
1221 {
return const_reverse_iterator(this->_M_impl._M_start); }
1223#if __cplusplus >= 201103L
1231 {
return this->_M_impl._M_start; }
1241 {
return this->_M_impl._M_finish; }
1249 const_reverse_iterator
1251 {
return const_reverse_iterator(this->_M_impl._M_finish); }
1259 const_reverse_iterator
1261 {
return const_reverse_iterator(this->_M_impl._M_start); }
1270 size_type __sz = this->_M_impl._M_finish - this->_M_impl._M_start;
1272 __builtin_unreachable ();
1280 {
return _S_max_size(_M_get_Tp_allocator()); }
1282#if __cplusplus >= 201103L
1295 const size_type __len =
size();
1296 if (__new_size > __len)
1297 _M_default_append(__new_size - __len);
1298 else if (__new_size < __len)
1299 _M_erase_at_end(this->_M_impl._M_start
1300 + difference_type(__new_size));
1315 resize(size_type __new_size,
const value_type& __x)
1329 resize(size_type __new_size, value_type __x = value_type())
1332 const size_type __len =
size();
1333 if (__new_size > __len)
1334 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1335 else if (__new_size < __len)
1336 _M_erase_at_end(this->_M_impl._M_start
1337 + difference_type(__new_size));
1340#if __cplusplus >= 201103L
1344 { _M_shrink_to_fit(); }
1351 _GLIBCXX_NODISCARD
bool
1353 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1371 __glibcxx_requires_subscript(__n);
1372 return this->_M_impl._M_start[difference_type(__n)];
1390 __glibcxx_requires_subscript(__n);
1391 return this->_M_impl._M_start[difference_type(__n)];
1399 if (__n >= this->
size())
1400 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n "
1401 "(which is %zu)>= this->size() "
1422 return (*
this)[__n];
1440 return (*
this)[__n];
1451 __glibcxx_requires_nonempty();
1463 __glibcxx_requires_nonempty();
1475 __glibcxx_requires_nonempty();
1476 iterator __tmp =
end();
1489 __glibcxx_requires_nonempty();
1490 const_iterator __tmp =
end();
1508 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1510 _Alloc_traits::construct(this->_M_impl,
1511 this->_M_impl._M_start._M_cur - 1,
1513 --this->_M_impl._M_start._M_cur;
1519#if __cplusplus >= 201103L
1524 template<
typename... _Args>
1525#if __cplusplus > 201402L
1530 emplace_front(_Args&&... __args);
1545 if (this->_M_impl._M_finish._M_cur
1546 != this->_M_impl._M_finish._M_last - 1)
1548 _Alloc_traits::construct(this->_M_impl,
1549 this->_M_impl._M_finish._M_cur, __x);
1550 ++this->_M_impl._M_finish._M_cur;
1556#if __cplusplus >= 201103L
1561 template<
typename... _Args>
1562#if __cplusplus > 201402L
1567 emplace_back(_Args&&... __args);
1581 __glibcxx_requires_nonempty();
1582 if (this->_M_impl._M_start._M_cur
1583 != this->_M_impl._M_start._M_last - 1)
1585 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1586 this->_M_impl._M_start._M_cur);
1587 ++this->_M_impl._M_start._M_cur;
1604 __glibcxx_requires_nonempty();
1605 if (this->_M_impl._M_finish._M_cur
1606 != this->_M_impl._M_finish._M_first)
1608 --this->_M_impl._M_finish._M_cur;
1609 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1610 this->_M_impl._M_finish._M_cur);
1616#if __cplusplus >= 201103L
1626 template<
typename... _Args>
1628 emplace(const_iterator __position, _Args&&... __args);
1640 insert(const_iterator __position,
const value_type& __x);
1652 insert(iterator __position,
const value_type& __x);
1655#if __cplusplus >= 201103L
1666 insert(const_iterator __position, value_type&& __x)
1682 auto __offset = __p -
cbegin();
1683 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1685 return begin() + __offset;
1699 insert(const_iterator __position, size_type __n,
const value_type& __x)
1701 difference_type __offset = __position -
cbegin();
1702 _M_fill_insert(__position._M_const_cast(), __n, __x);
1703 return begin() + __offset;
1717 { _M_fill_insert(__position, __n, __x); }
1720#if __cplusplus >= 201103L
1732 template<
typename _InputIterator,
1733 typename = std::_RequireInputIter<_InputIterator>>
1735 insert(const_iterator __position, _InputIterator __first,
1736 _InputIterator __last)
1738 difference_type __offset = __position -
cbegin();
1739 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1741 return begin() + __offset;
1754 template<
typename _InputIterator>
1757 _InputIterator __last)
1760 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1761 _M_insert_dispatch(__position, __first, __last, _Integral());
1779#if __cplusplus >= 201103L
1782 erase(iterator __position)
1784 {
return _M_erase(__position._M_const_cast()); }
1803#if __cplusplus >= 201103L
1804 erase(const_iterator __first, const_iterator __last)
1806 erase(iterator __first, iterator __last)
1808 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1824#if __cplusplus >= 201103L
1825 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1826 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1828 _M_impl._M_swap_data(__x._M_impl);
1829 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1830 __x._M_get_Tp_allocator());
1841 { _M_erase_at_end(
begin()); }
1846#if __cplusplus < 201103L
1851 template<
typename _Integer>
1853 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1855 _M_initialize_map(_S_check_init_len(
static_cast<size_type>(__n),
1856 _M_get_Tp_allocator()));
1861 template<
typename _InputIterator>
1863 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1872 _S_check_init_len(
size_t __n,
const allocator_type& __a)
1874 if (__n > _S_max_size(__a))
1875 __throw_length_error(
1876 __N(
"cannot create std::deque larger than max_size()"));
1881 _S_max_size(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1883 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1885 return (
std::min)(__diffmax, __allocmax);
1900 template<
typename _InputIterator>
1906 template<
typename _ForwardIterator>
1925#if __cplusplus >= 201103L
1928 _M_default_initialize();
1934#if __cplusplus < 201103L
1939 template<
typename _Integer>
1941 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1942 { _M_fill_assign(__n, __val); }
1945 template<
typename _InputIterator>
1947 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1953 template<
typename _InputIterator>
1955 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1959 template<
typename _ForwardIterator>
1961 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1967 _ForwardIterator __mid = __first;
1969 std::copy(__first, __mid,
begin());
1970 _M_range_insert_aux(
end(), __mid, __last,
1974 _M_erase_at_end(std::copy(__first, __last,
begin()));
1980 _M_fill_assign(size_type __n,
const value_type& __val)
1985 _M_fill_insert(
end(), __n -
size(), __val);
1989 _M_erase_at_end(
begin() + difference_type(__n));
1996#if __cplusplus < 201103L
2001 template<
typename... _Args>
2004 template<
typename... _Args>
2016#if __cplusplus < 201103L
2021 template<
typename _Integer>
2023 _M_insert_dispatch(iterator __pos,
2024 _Integer __n, _Integer __x, __true_type)
2025 { _M_fill_insert(__pos, __n, __x); }
2028 template<
typename _InputIterator>
2031 _InputIterator __first, _InputIterator __last,
2034 _M_range_insert_aux(__pos, __first, __last,
2040 template<
typename _InputIterator>
2042 _M_range_insert_aux(iterator __pos, _InputIterator __first,
2046 template<
typename _ForwardIterator>
2048 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2055 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
2058#if __cplusplus < 201103L
2060 _M_insert_aux(iterator __pos,
const value_type& __x);
2063 _M_insert_aux(iterator __pos,
const value_type& __x)
2064 {
return _M_emplace_aux(__pos, __x); }
2066 template<
typename... _Args>
2068 _M_emplace_aux(iterator __pos, _Args&&... __args);
2073 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2076 template<
typename _ForwardIterator>
2078 _M_insert_aux(iterator __pos,
2079 _ForwardIterator __first, _ForwardIterator __last,
2086 _M_destroy_data_aux(iterator __first, iterator __last);
2090 template<
typename _Alloc1>
2092 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2093 { _M_destroy_data_aux(__first, __last); }
2096 _M_destroy_data(iterator __first, iterator __last,
2097 const std::allocator<_Tp>&)
2099 if (!__has_trivial_destructor(value_type))
2100 _M_destroy_data_aux(__first, __last);
2105 _M_erase_at_begin(iterator __pos)
2107 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2108 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2109 this->_M_impl._M_start = __pos;
2115 _M_erase_at_end(iterator __pos)
2117 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2118 _M_destroy_nodes(__pos._M_node + 1,
2119 this->_M_impl._M_finish._M_node + 1);
2120 this->_M_impl._M_finish = __pos;
2124 _M_erase(iterator __pos);
2127 _M_erase(iterator __first, iterator __last);
2129#if __cplusplus >= 201103L
2132 _M_default_append(size_type __n);
2143 const size_type __vacancies = this->_M_impl._M_start._M_cur
2144 - this->_M_impl._M_start._M_first;
2145 if (__n > __vacancies)
2147 return this->_M_impl._M_start - difference_type(__n);
2153 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2154 - this->_M_impl._M_finish._M_cur) - 1;
2155 if (__n > __vacancies)
2157 return this->_M_impl._M_finish + difference_type(__n);
2179 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2180 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2187 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2188 - this->_M_impl._M_map))
2196#if __cplusplus >= 201103L
2202 this->_M_impl._M_swap_data(__x._M_impl);
2204 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2213 if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
2216 constexpr bool __move_storage =
2217 _Alloc_traits::_S_propagate_on_move_assign();
2218 _M_move_assign2(
std::move(__x), __bool_constant<__move_storage>());
2223 template<
typename... _Args>
2225 _M_replace_map(_Args&&... __args)
2231 _M_deallocate_node(*
begin()._M_node);
2232 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2233 this->_M_impl._M_map =
nullptr;
2234 this->_M_impl._M_map_size = 0;
2236 this->_M_impl._M_swap_data(__newobj._M_impl);
2244 auto __alloc = __x._M_get_Tp_allocator();
2249 _M_get_Tp_allocator() =
std::move(__alloc);
2257 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2261 _M_replace_map(
std::move(__x), __x.get_allocator());
2267 _M_assign_aux(std::make_move_iterator(__x.begin()),
2268 std::make_move_iterator(__x.end()),
2269 std::random_access_iterator_tag());
2276#if __cpp_deduction_guides >= 201606
2277 template<
typename _InputIterator,
typename _ValT
2280 typename = _RequireInputIter<_InputIterator>,
2281 typename = _RequireAllocator<_Allocator>>
2282 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2296 template<
typename _Tp,
typename _Alloc>
2303#if __cpp_lib_three_way_comparison
2315 template<
typename _Tp,
typename _Alloc>
2317 inline __detail::__synth3way_t<_Tp>
2318 operator<=>(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2321 __y.begin(), __y.end(),
2322 __detail::__synth3way);
2336 template<
typename _Tp,
typename _Alloc>
2340 {
return std::lexicographical_compare(__x.begin(), __x.end(),
2341 __y.begin(), __y.end()); }
2344 template<
typename _Tp,
typename _Alloc>
2348 {
return !(__x == __y); }
2351 template<
typename _Tp,
typename _Alloc>
2355 {
return __y < __x; }
2358 template<
typename _Tp,
typename _Alloc>
2362 {
return !(__y < __x); }
2365 template<
typename _Tp,
typename _Alloc>
2369 {
return !(__x < __y); }
2373 template<
typename _Tp,
typename _Alloc>
2376 _GLIBCXX_NOEXCEPT_IF(
noexcept(__x.swap(__y)))
2379#undef _GLIBCXX_DEQUE_BUF_SIZE
2381_GLIBCXX_END_NAMESPACE_CONTAINER
2383#if __cplusplus >= 201103L
2387 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2391_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 _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
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.
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
is_nothrow_default_constructible
typename __detected_or_t< is_empty< _Tp_alloc_type >, __equal, _Tp_alloc_type >::type is_always_equal
The standard allocator, as per C++03 [20.4.1].
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.
void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, std::forward_iterator_tag)
Fills the deque with whatever is in [first,last).
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(_Map_alloc_type &__a, size_type __n)
static constexpr void deallocate(_Map_alloc_type &__a, pointer __p, size_type __n)
static constexpr size_type max_size(const _Tp_alloc_type &__a) noexcept