57 #define _STL_DEQUE_H 1 62 #if __cplusplus >= 201103L 66 #if __cplusplus > 201703L 72 namespace 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;
127 typedef __ptr_rebind<_Ptr, _Tp> _Elt_pointer;
128 typedef __ptr_rebind<_Ptr, _Elt_pointer> _Map_pointer;
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>,
163 is_same<_Iter, 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); }
180 operator*() const _GLIBCXX_NOEXCEPT
184 operator->() const _GLIBCXX_NOEXCEPT
188 operator++() _GLIBCXX_NOEXCEPT
191 if (_M_cur == _M_last)
200 operator++(
int) _GLIBCXX_NOEXCEPT
208 operator--() _GLIBCXX_NOEXCEPT
210 if (_M_cur == _M_first)
220 operator--(
int) _GLIBCXX_NOEXCEPT
228 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
230 const difference_type __offset = __n + (_M_cur - _M_first);
231 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
235 const difference_type __node_offset =
236 __offset > 0 ? __offset / difference_type(_S_buffer_size())
237 : -difference_type((-__offset - 1)
238 / _S_buffer_size()) - 1;
240 _M_cur = _M_first + (__offset - __node_offset
241 * difference_type(_S_buffer_size()));
247 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
248 {
return *
this += -__n; }
251 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
252 {
return *(*
this + __n); }
262 _M_node = __new_node;
263 _M_first = *__new_node;
264 _M_last = _M_first + difference_type(_S_buffer_size());
268 operator==(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
269 {
return __x._M_cur == __y._M_cur; }
274 template<
typename _RefR,
typename _PtrR>
276 operator==(
const _Self& __x,
277 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
279 {
return __x._M_cur == __y._M_cur; }
281 #if __cpp_lib_three_way_comparison 282 friend strong_ordering
283 operator<=>(
const _Self& __x,
const _Self& __y) noexcept
285 if (
const auto __cmp = __x._M_node <=> __y._M_node; __cmp != 0)
287 return __x._M_cur <=> __y._M_cur;
291 operator!=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
292 {
return !(__x == __y); }
294 template<
typename _RefR,
typename _PtrR>
296 operator!=(
const _Self& __x,
297 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
299 {
return !(__x == __y); }
302 operator<(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
304 return (__x._M_node == __y._M_node)
305 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
308 template<
typename _RefR,
typename _PtrR>
310 operator<(
const _Self& __x,
311 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
314 return (__x._M_node == __y._M_node)
315 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
319 operator>(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
320 {
return __y < __x; }
322 template<
typename _RefR,
typename _PtrR>
324 operator>(
const _Self& __x,
325 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
327 {
return __y < __x; }
330 operator<=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
331 {
return !(__y < __x); }
333 template<
typename _RefR,
typename _PtrR>
335 operator<=(
const _Self& __x,
336 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
338 {
return !(__y < __x); }
341 operator>=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
342 {
return !(__x < __y); }
344 template<
typename _RefR,
typename _PtrR>
346 operator>=(
const _Self& __x,
347 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
349 {
return !(__x < __y); }
350 #endif // three-way comparison 352 friend difference_type
353 operator-(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
355 return difference_type(_S_buffer_size())
356 * (__x._M_node - __y._M_node - int(__x._M_node != 0))
357 + (__x._M_cur - __x._M_first)
358 + (__y._M_last - __y._M_cur);
365 template<
typename _RefR,
typename _PtrR>
366 friend difference_type
367 operator-(
const _Self& __x,
368 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
370 return difference_type(_S_buffer_size())
371 * (__x._M_node - __y._M_node - int(__x._M_node != 0))
372 + (__x._M_cur - __x._M_first)
373 + (__y._M_last - __y._M_cur);
377 operator+(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
385 operator-(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
393 operator+(difference_type __n,
const _Self& __x) _GLIBCXX_NOEXCEPT
394 {
return __x + __n; }
407 template<
typename _Tp,
typename _Alloc>
412 rebind<_Tp>::other _Tp_alloc_type;
415 #if __cplusplus < 201103L 417 typedef const _Tp* _Ptr_const;
419 typedef typename _Alloc_traits::pointer _Ptr;
420 typedef typename _Alloc_traits::const_pointer _Ptr_const;
423 typedef typename _Alloc_traits::template rebind<_Ptr>::other
427 typedef _Alloc allocator_type;
430 get_allocator()
const _GLIBCXX_NOEXCEPT
431 {
return allocator_type(_M_get_Tp_allocator()); }
444 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
452 #if __cplusplus >= 201103L 454 : _M_impl(
std::move(__x._M_get_Tp_allocator()))
457 if (__x._M_impl._M_map)
458 this->_M_impl._M_swap_data(__x._M_impl);
462 : _M_impl(
std::move(__x._M_impl), _Tp_alloc_type(__a))
463 { __x._M_initialize_map(0); }
468 if (__x.get_allocator() == __a)
470 if (__x._M_impl._M_map)
473 this->_M_impl._M_swap_data(__x._M_impl);
485 typedef typename iterator::_Map_pointer _Map_pointer;
487 struct _Deque_impl_data
494 _Deque_impl_data() _GLIBCXX_NOEXCEPT
495 : _M_map(), _M_map_size(), _M_start(), _M_finish()
498 #if __cplusplus >= 201103L 499 _Deque_impl_data(
const _Deque_impl_data&) =
default;
501 operator=(
const _Deque_impl_data&) =
default;
503 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
504 : _Deque_impl_data(__x)
505 { __x = _Deque_impl_data(); }
509 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
513 std::swap(*
this, __x);
521 :
public _Tp_alloc_type,
public _Deque_impl_data
523 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
528 _Deque_impl(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
529 : _Tp_alloc_type(__a)
532 #if __cplusplus >= 201103L 533 _Deque_impl(_Deque_impl&&) =
default;
535 _Deque_impl(_Tp_alloc_type&& __a) noexcept
539 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
546 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
547 {
return this->_M_impl; }
549 const _Tp_alloc_type&
550 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
551 {
return this->_M_impl; }
554 _M_get_map_allocator()
const _GLIBCXX_NOEXCEPT
555 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
561 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
565 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
568 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
572 _M_allocate_map(
size_t __n)
574 _Map_alloc_type __map_alloc = _M_get_map_allocator();
579 _M_deallocate_map(_Map_pointer __p,
size_t __n) _GLIBCXX_NOEXCEPT
581 _Map_alloc_type __map_alloc = _M_get_map_allocator();
586 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
587 void _M_destroy_nodes(_Map_pointer __nstart,
588 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
589 enum { _S_initial_map_size = 8 };
594 template<
typename _Tp,
typename _Alloc>
598 if (this->_M_impl._M_map)
600 _M_destroy_nodes(this->_M_impl._M_start._M_node,
601 this->_M_impl._M_finish._M_node + 1);
602 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
614 template<
typename _Tp,
typename _Alloc>
619 const size_t __num_nodes = (__num_elements / __deque_buf_size(
sizeof(_Tp))
622 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
623 size_t(__num_nodes + 2));
624 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
631 _Map_pointer __nstart = (this->_M_impl._M_map
632 + (this->_M_impl._M_map_size - __num_nodes) / 2);
633 _Map_pointer __nfinish = __nstart + __num_nodes;
636 { _M_create_nodes(__nstart, __nfinish); }
639 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
640 this->_M_impl._M_map = _Map_pointer();
641 this->_M_impl._M_map_size = 0;
642 __throw_exception_again;
645 this->_M_impl._M_start._M_set_node(__nstart);
646 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
647 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
648 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
650 % __deque_buf_size(
sizeof(_Tp)));
653 template<
typename _Tp,
typename _Alloc>
661 for (__cur = __nstart; __cur < __nfinish; ++__cur)
662 *__cur = this->_M_allocate_node();
666 _M_destroy_nodes(__nstart, __cur);
667 __throw_exception_again;
671 template<
typename _Tp,
typename _Alloc>
673 _Deque_base<_Tp, _Alloc>::
674 _M_destroy_nodes(_Map_pointer __nstart,
675 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
677 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
678 _M_deallocate_node(*__n);
765 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
768 #ifdef _GLIBCXX_CONCEPT_CHECKS 770 typedef typename _Alloc::value_type _Alloc_value_type;
771 # if __cplusplus < 201103L 772 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
774 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
777 #if __cplusplus >= 201103L 778 static_assert(
is_same<
typename remove_cv<_Tp>::type, _Tp>::value,
779 "std::deque must have a non-const, non-volatile value_type");
780 # if __cplusplus > 201703L || defined __STRICT_ANSI__ 782 "std::deque must have the same value_type as its allocator");
787 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
789 typedef typename _Base::_Map_pointer _Map_pointer;
792 typedef _Tp value_type;
793 typedef typename _Alloc_traits::pointer pointer;
794 typedef typename _Alloc_traits::const_pointer const_pointer;
795 typedef typename _Alloc_traits::reference reference;
796 typedef typename _Alloc_traits::const_reference const_reference;
801 typedef size_t size_type;
802 typedef ptrdiff_t difference_type;
803 typedef _Alloc allocator_type;
806 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
807 {
return __deque_buf_size(
sizeof(_Tp)); }
811 using _Base::_M_create_nodes;
812 using _Base::_M_destroy_nodes;
813 using _Base::_M_allocate_node;
814 using _Base::_M_deallocate_node;
815 using _Base::_M_allocate_map;
816 using _Base::_M_deallocate_map;
817 using _Base::_M_get_Tp_allocator;
823 using _Base::_M_impl;
832 #if __cplusplus >= 201103L 846 #if __cplusplus >= 201103L 857 :
_Base(__a, _S_check_init_len(__n, __a))
858 { _M_default_initialize(); }
868 deque(size_type __n,
const value_type& __value,
870 :
_Base(__a, _S_check_init_len(__n, __a))
882 deque(size_type __n,
const value_type& __value = value_type(),
883 const allocator_type& __a = allocator_type())
884 : _Base(__a, _S_check_init_len(__n, __a))
898 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
899 this->_M_impl._M_start,
900 _M_get_Tp_allocator()); }
902 #if __cplusplus >= 201103L 916 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
917 this->_M_impl._M_start,
918 _M_get_Tp_allocator()); }
933 if (__x.get_allocator() != __a && !__x.empty())
935 std::__uninitialized_move_a(__x.begin(), __x.end(),
936 this->_M_impl._M_start,
937 _M_get_Tp_allocator());
978 #if __cplusplus >= 201103L 979 template<
typename _InputIterator,
980 typename = std::_RequireInputIter<_InputIterator>>
981 deque(_InputIterator __first, _InputIterator __last,
989 template<
typename _InputIterator>
990 deque(_InputIterator __first, _InputIterator __last,
991 const allocator_type& __a = allocator_type())
995 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
996 _M_initialize_dispatch(__first, __last, _Integral());
1006 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
1020 #if __cplusplus >= 201103L 1033 _M_move_assign1(
std::move(__x), __always_equal{});
1051 _M_assign_aux(__l.begin(), __l.end(),
1068 assign(size_type __n,
const value_type& __val)
1069 { _M_fill_assign(__n, __val); }
1083 #if __cplusplus >= 201103L 1084 template<
typename _InputIterator,
1085 typename = std::_RequireInputIter<_InputIterator>>
1087 assign(_InputIterator __first, _InputIterator __last)
1090 template<
typename _InputIterator>
1092 assign(_InputIterator __first, _InputIterator __last)
1094 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1095 _M_assign_dispatch(__first, __last, _Integral());
1099 #if __cplusplus >= 201103L 1119 {
return _Base::get_allocator(); }
1128 {
return this->_M_impl._M_start; }
1136 {
return this->_M_impl._M_start; }
1145 {
return this->_M_impl._M_finish; }
1154 {
return this->_M_impl._M_finish; }
1170 const_reverse_iterator
1188 const_reverse_iterator
1192 #if __cplusplus >= 201103L 1199 {
return this->_M_impl._M_start; }
1208 {
return this->_M_impl._M_finish; }
1215 const_reverse_iterator
1224 const_reverse_iterator
1233 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
1238 {
return _S_max_size(_M_get_Tp_allocator()); }
1240 #if __cplusplus >= 201103L 1253 const size_type __len =
size();
1254 if (__new_size > __len)
1255 _M_default_append(__new_size - __len);
1256 else if (__new_size < __len)
1257 _M_erase_at_end(this->_M_impl._M_start
1258 + difference_type(__new_size));
1273 resize(size_type __new_size,
const value_type& __x)
1287 resize(size_type __new_size, value_type __x = value_type())
1290 const size_type __len =
size();
1291 if (__new_size > __len)
1292 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1293 else if (__new_size < __len)
1294 _M_erase_at_end(this->_M_impl._M_start
1295 + difference_type(__new_size));
1298 #if __cplusplus >= 201103L 1302 { _M_shrink_to_fit(); }
1309 _GLIBCXX_NODISCARD
bool 1311 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1328 __glibcxx_requires_subscript(__n);
1329 return this->_M_impl._M_start[difference_type(__n)];
1346 __glibcxx_requires_subscript(__n);
1347 return this->_M_impl._M_start[difference_type(__n)];
1355 if (__n >= this->
size())
1356 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n " 1357 "(which is %zu)>= this->size() " 1378 return (*
this)[__n];
1396 return (*
this)[__n];
1406 __glibcxx_requires_nonempty();
1417 __glibcxx_requires_nonempty();
1428 __glibcxx_requires_nonempty();
1441 __glibcxx_requires_nonempty();
1460 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1462 _Alloc_traits::construct(this->_M_impl,
1463 this->_M_impl._M_start._M_cur - 1,
1465 --this->_M_impl._M_start._M_cur;
1471 #if __cplusplus >= 201103L 1476 template<
typename... _Args>
1477 #if __cplusplus > 201402L 1482 emplace_front(_Args&&... __args);
1497 if (this->_M_impl._M_finish._M_cur
1498 != this->_M_impl._M_finish._M_last - 1)
1500 _Alloc_traits::construct(this->_M_impl,
1501 this->_M_impl._M_finish._M_cur, __x);
1502 ++this->_M_impl._M_finish._M_cur;
1508 #if __cplusplus >= 201103L 1513 template<
typename... _Args>
1514 #if __cplusplus > 201402L 1519 emplace_back(_Args&&... __args);
1533 __glibcxx_requires_nonempty();
1534 if (this->_M_impl._M_start._M_cur
1535 != this->_M_impl._M_start._M_last - 1)
1537 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1538 this->_M_impl._M_start._M_cur);
1539 ++this->_M_impl._M_start._M_cur;
1556 __glibcxx_requires_nonempty();
1557 if (this->_M_impl._M_finish._M_cur
1558 != this->_M_impl._M_finish._M_first)
1560 --this->_M_impl._M_finish._M_cur;
1561 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1562 this->_M_impl._M_finish._M_cur);
1568 #if __cplusplus >= 201103L 1578 template<
typename... _Args>
1580 emplace(const_iterator __position, _Args&&... __args);
1592 insert(const_iterator __position,
const value_type& __x);
1607 #if __cplusplus >= 201103L 1634 auto __offset = __p -
cbegin();
1635 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1637 return begin() + __offset;
1653 difference_type __offset = __position -
cbegin();
1654 _M_fill_insert(__position._M_const_cast(), __n, __x);
1655 return begin() + __offset;
1668 insert(
iterator __position, size_type __n,
const value_type& __x)
1669 { _M_fill_insert(__position, __n, __x); }
1672 #if __cplusplus >= 201103L 1684 template<
typename _InputIterator,
1685 typename = std::_RequireInputIter<_InputIterator>>
1688 _InputIterator __last)
1690 difference_type __offset = __position -
cbegin();
1691 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1693 return begin() + __offset;
1706 template<
typename _InputIterator>
1709 _InputIterator __last)
1712 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1713 _M_insert_dispatch(__position, __first, __last, _Integral());
1731 #if __cplusplus >= 201103L 1736 {
return _M_erase(__position._M_const_cast()); }
1755 #if __cplusplus >= 201103L 1760 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1776 #if __cplusplus >= 201103L 1777 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1778 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1780 _M_impl._M_swap_data(__x._M_impl);
1781 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1782 __x._M_get_Tp_allocator());
1793 { _M_erase_at_end(
begin()); }
1798 #if __cplusplus < 201103L 1803 template<
typename _Integer>
1805 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1808 _M_get_Tp_allocator()));
1813 template<
typename _InputIterator>
1815 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1824 _S_check_init_len(
size_t __n,
const allocator_type& __a)
1826 if (__n > _S_max_size(__a))
1827 __throw_length_error(
1828 __N(
"cannot create std::deque larger than max_size()"));
1833 _S_max_size(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1835 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1837 return (
std::min)(__diffmax, __allocmax);
1852 template<
typename _InputIterator>
1858 template<
typename _ForwardIterator>
1877 #if __cplusplus >= 201103L 1880 _M_default_initialize();
1886 #if __cplusplus < 201103L 1891 template<
typename _Integer>
1893 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1894 { _M_fill_assign(__n, __val); }
1897 template<
typename _InputIterator>
1899 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1905 template<
typename _InputIterator>
1907 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1911 template<
typename _ForwardIterator>
1913 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1919 _ForwardIterator __mid = __first;
1920 std::advance(__mid,
size());
1921 std::copy(__first, __mid,
begin());
1922 _M_range_insert_aux(
end(), __mid, __last,
1926 _M_erase_at_end(std::copy(__first, __last,
begin()));
1932 _M_fill_assign(size_type __n,
const value_type& __val)
1937 _M_fill_insert(
end(), __n -
size(), __val);
1941 _M_erase_at_end(
begin() + difference_type(__n));
1948 #if __cplusplus < 201103L 1953 template<
typename... _Args>
1956 template<
typename... _Args>
1968 #if __cplusplus < 201103L 1973 template<
typename _Integer>
1975 _M_insert_dispatch(iterator __pos,
1976 _Integer __n, _Integer __x, __true_type)
1977 { _M_fill_insert(__pos, __n, __x); }
1980 template<
typename _InputIterator>
1982 _M_insert_dispatch(iterator __pos,
1983 _InputIterator __first, _InputIterator __last,
1986 _M_range_insert_aux(__pos, __first, __last,
1992 template<
typename _InputIterator>
1994 _M_range_insert_aux(iterator __pos, _InputIterator __first,
1998 template<
typename _ForwardIterator>
2000 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2007 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
2010 #if __cplusplus < 201103L 2012 _M_insert_aux(iterator __pos,
const value_type& __x);
2014 template<
typename... _Args>
2016 _M_insert_aux(iterator __pos, _Args&&... __args);
2021 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2024 template<
typename _ForwardIterator>
2026 _M_insert_aux(iterator __pos,
2027 _ForwardIterator __first, _ForwardIterator __last,
2034 _M_destroy_data_aux(iterator __first, iterator __last);
2038 template<
typename _Alloc1>
2040 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2041 { _M_destroy_data_aux(__first, __last); }
2044 _M_destroy_data(iterator __first, iterator __last,
2047 if (!__has_trivial_destructor(value_type))
2048 _M_destroy_data_aux(__first, __last);
2053 _M_erase_at_begin(iterator __pos)
2055 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2056 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2057 this->_M_impl._M_start = __pos;
2063 _M_erase_at_end(iterator __pos)
2065 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2066 _M_destroy_nodes(__pos._M_node + 1,
2067 this->_M_impl._M_finish._M_node + 1);
2068 this->_M_impl._M_finish = __pos;
2072 _M_erase(iterator __pos);
2075 _M_erase(iterator __first, iterator __last);
2077 #if __cplusplus >= 201103L 2080 _M_default_append(size_type __n);
2091 const size_type __vacancies = this->_M_impl._M_start._M_cur
2092 - this->_M_impl._M_start._M_first;
2093 if (__n > __vacancies)
2095 return this->_M_impl._M_start - difference_type(__n);
2101 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2102 - this->_M_impl._M_finish._M_cur) - 1;
2103 if (__n > __vacancies)
2105 return this->_M_impl._M_finish + difference_type(__n);
2127 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2128 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2135 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2136 - this->_M_impl._M_map))
2144 #if __cplusplus >= 201103L 2150 this->_M_impl._M_swap_data(__x._M_impl);
2152 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2161 if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
2164 constexpr
bool __move_storage =
2165 _Alloc_traits::_S_propagate_on_move_assign();
2166 _M_move_assign2(
std::move(__x), __bool_constant<__move_storage>());
2171 template<
typename... _Args>
2173 _M_replace_map(_Args&&... __args)
2176 deque __newobj(std::forward<_Args>(__args)...);
2179 _M_deallocate_node(*
begin()._M_node);
2180 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2181 this->_M_impl._M_map =
nullptr;
2182 this->_M_impl._M_map_size = 0;
2184 this->_M_impl._M_swap_data(__newobj._M_impl);
2192 auto __alloc = __x._M_get_Tp_allocator();
2197 _M_get_Tp_allocator() =
std::move(__alloc);
2205 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2209 _M_replace_map(
std::move(__x), __x.get_allocator());
2215 _M_assign_aux(std::make_move_iterator(__x.begin()),
2216 std::make_move_iterator(__x.end()),
2224 #if __cpp_deduction_guides >= 201606 2225 template<
typename _InputIterator,
typename _ValT
2226 =
typename iterator_traits<_InputIterator>::value_type,
2227 typename _Allocator = allocator<_ValT>,
2228 typename = _RequireInputIter<_InputIterator>,
2229 typename = _RequireAllocator<_Allocator>>
2230 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2231 -> deque<_ValT, _Allocator>;
2244 template<
typename _Tp,
typename _Alloc>
2250 #if __cpp_lib_three_way_comparison 2262 template<
typename _Tp,
typename _Alloc>
2263 inline __detail::__synth3way_t<_Tp>
2264 operator<=>(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2266 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2267 __y.begin(), __y.end(),
2268 __detail::__synth3way);
2282 template<
typename _Tp,
typename _Alloc>
2286 __y.begin(), __y.end()); }
2289 template<
typename _Tp,
typename _Alloc>
2292 {
return !(__x == __y); }
2295 template<
typename _Tp,
typename _Alloc>
2298 {
return __y < __x; }
2301 template<
typename _Tp,
typename _Alloc>
2304 {
return !(__y < __x); }
2307 template<
typename _Tp,
typename _Alloc>
2310 {
return !(__x < __y); }
2311 #endif // three-way comparison 2314 template<
typename _Tp,
typename _Alloc>
2317 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2320 #undef _GLIBCXX_DEQUE_BUF_SIZE 2322 _GLIBCXX_END_NAMESPACE_CONTAINER
2324 #if __cplusplus >= 201103L 2328 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2332 _GLIBCXX_END_NAMESPACE_VERSION
constexpr void fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__value)
Fills the range [first,last) with copies of value.
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
deque(size_type __n, const allocator_type &__a=allocator_type())
Creates a deque with default constructed elements.
const_reference front() const noexcept
void _M_initialize_map(size_t)
Layout storage.
reference back() noexcept
size_type size() const noexcept
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in deque before specified iterator.
const_reverse_iterator rbegin() const noexcept
const_iterator cend() const noexcept
const_reference at(size_type __n) const
Provides access to the data contained in 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.
reference front() noexcept
deque()=default
Creates a deque with no elements.
void _M_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
Fills the deque with whatever is in [first,last).
void resize(size_type __new_size, const value_type &__x)
Resizes the deque to the specified number of elements.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
The standard allocator, as per C++03 [20.4.1].
iterator erase(const_iterator __position)
Remove element at given position.
const_reverse_iterator rend() const noexcept
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
void pop_back() noexcept
Removes last element.
deque(const allocator_type &__a)
Creates a deque with no elements.
const_reference back() const noexcept
Forward iterators support a superset of input iterator operations.
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the deque.
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
is_nothrow_default_constructible
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into deque before specified iterator.
deque & operator=(const deque &__x)
Deque assignment operator.
const_reverse_iterator crbegin() const noexcept
void _M_fill_initialize(const value_type &__value)
Fills the deque with copies of value.
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
const_iterator end() const noexcept
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
__detected_or_t< typename is_empty< _Tp_alloc_type >::type, __equal, _Tp_alloc_type > is_always_equal
Whether all instances of the allocator type compare equal.
iterator _M_reserve_elements_at_front(size_type __n)
Memory-handling helpers for the previous internal insert functions.
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
deque(deque &&__x, const allocator_type &__a)
Move constructor with alternative allocator.
const_iterator cbegin() const noexcept
void _M_new_elements_at_back(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
const_reverse_iterator crend() const noexcept
deque(const deque &__x, const allocator_type &__a)
Copy constructor with alternative allocator.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
iterator begin() noexcept
static constexpr size_type max_size(const _Tp_alloc_type &__a) noexcept
The maximum supported allocation size.
void _M_range_check(size_type __n) const
Safety check used only from at().
void assign(size_type __n, const value_type &__val)
Assigns a given value to a deque.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void pop_front() noexcept
Removes first element.
reference at(size_type __n)
Provides access to the data contained in the deque.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
void push_back(const value_type &__x)
Add data to the end of the deque.
const_iterator begin() const noexcept
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the deque.
void _M_new_elements_at_front(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
Memory-handling helpers for the major map.
size_type max_size() const noexcept
reverse_iterator rend() noexcept
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
deque(const deque &__x)
Deque copy constructor.
ISO C++ entities toplevel namespace is std.
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.
void push_front(const value_type &__x)
Add data to the front of the deque.
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
void swap(deque &__x) noexcept
Swaps data with another deque.
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
void shrink_to_fit() noexcept
Uniform interface to C++98 and C++11 allocators.
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
void resize(size_type __new_size)
Resizes the deque to the specified number of elements.
constexpr bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
bool empty() const noexcept
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the deque.
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
void _M_set_node(_Map_pointer __new_node) noexcept
Random-access iterators support a superset of bidirectional iterator operations.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
reverse_iterator rbegin() noexcept
constexpr bool equal(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
Tests a range for element-wise equality.