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>
115 #if __cplusplus < 201103L
118 typedef _Tp* _Elt_pointer;
119 typedef _Tp** _Map_pointer;
122 template<
typename _CvTp>
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;
143 _Elt_pointer _M_first;
144 _Elt_pointer _M_last;
145 _Map_pointer _M_node;
148 : _M_cur(__x), _M_first(*__y),
149 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
152 : _M_cur(), _M_first(), _M_last(), _M_node() { }
154 #if __cplusplus < 201103L
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>,
165 : _M_cur(__x._M_cur), _M_first(__x._M_first),
166 _M_last(__x._M_last), _M_node(__x._M_node) { }
169 : _M_cur(__x._M_cur), _M_first(__x._M_first),
170 _M_last(__x._M_last), _M_node(__x._M_node) { }
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); }
352 friend difference_type
353 operator-(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
355 if (__builtin_expect(__x._M_node || __y._M_node,
true))
356 return difference_type(_S_buffer_size())
357 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
358 + (__y._M_last - __y._M_cur);
367 template<
typename _RefR,
typename _PtrR>
368 friend difference_type
369 operator-(
const _Self& __x,
370 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
372 if (__builtin_expect(__x._M_node || __y._M_node,
true))
373 return difference_type(_S_buffer_size())
374 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
375 + (__y._M_last - __y._M_cur);
381 operator+(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
389 operator-(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
397 operator+(difference_type __n,
const _Self& __x) _GLIBCXX_NOEXCEPT
398 {
return __x + __n; }
411 template<
typename _Tp,
typename _Alloc>
416 rebind<_Tp>::other _Tp_alloc_type;
419 #if __cplusplus < 201103L
421 typedef const _Tp* _Ptr_const;
423 typedef typename _Alloc_traits::pointer _Ptr;
424 typedef typename _Alloc_traits::const_pointer _Ptr_const;
427 typedef typename _Alloc_traits::template rebind<_Ptr>::other
431 typedef _Alloc allocator_type;
434 get_allocator()
const _GLIBCXX_NOEXCEPT
435 {
return allocator_type(_M_get_Tp_allocator()); }
448 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
456 #if __cplusplus >= 201103L
458 : _M_impl(
std::move(__x._M_get_Tp_allocator()))
461 if (__x._M_impl._M_map)
462 this->_M_impl._M_swap_data(__x._M_impl);
466 : _M_impl(
std::move(__x._M_impl), _Tp_alloc_type(__a))
467 { __x._M_initialize_map(0); }
472 if (__x.get_allocator() == __a)
474 if (__x._M_impl._M_map)
477 this->_M_impl._M_swap_data(__x._M_impl);
489 typedef typename iterator::_Map_pointer _Map_pointer;
491 struct _Deque_impl_data
498 _Deque_impl_data() _GLIBCXX_NOEXCEPT
499 : _M_map(), _M_map_size(), _M_start(), _M_finish()
502 #if __cplusplus >= 201103L
503 _Deque_impl_data(
const _Deque_impl_data&) =
default;
505 operator=(
const _Deque_impl_data&) =
default;
507 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
508 : _Deque_impl_data(__x)
509 { __x = _Deque_impl_data(); }
513 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
525 :
public _Tp_alloc_type,
public _Deque_impl_data
527 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
532 _Deque_impl(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
533 : _Tp_alloc_type(__a)
536 #if __cplusplus >= 201103L
537 _Deque_impl(_Deque_impl&&) =
default;
539 _Deque_impl(_Tp_alloc_type&& __a) noexcept
543 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
550 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
551 {
return this->_M_impl; }
553 const _Tp_alloc_type&
554 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
555 {
return this->_M_impl; }
558 _M_get_map_allocator()
const _GLIBCXX_NOEXCEPT
559 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
565 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
569 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
572 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
576 _M_allocate_map(
size_t __n)
578 _Map_alloc_type __map_alloc = _M_get_map_allocator();
583 _M_deallocate_map(_Map_pointer __p,
size_t __n) _GLIBCXX_NOEXCEPT
585 _Map_alloc_type __map_alloc = _M_get_map_allocator();
590 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
591 void _M_destroy_nodes(_Map_pointer __nstart,
592 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
593 enum { _S_initial_map_size = 8 };
598 template<
typename _Tp,
typename _Alloc>
599 _Deque_base<_Tp, _Alloc>::
600 ~_Deque_base() _GLIBCXX_NOEXCEPT
602 if (this->_M_impl._M_map)
604 _M_destroy_nodes(this->_M_impl._M_start._M_node,
605 this->_M_impl._M_finish._M_node + 1);
606 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
618 template<
typename _Tp,
typename _Alloc>
623 const size_t __num_nodes = (__num_elements / __deque_buf_size(
sizeof(_Tp))
626 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
627 size_t(__num_nodes + 2));
628 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
635 _Map_pointer __nstart = (this->_M_impl._M_map
636 + (this->_M_impl._M_map_size - __num_nodes) / 2);
637 _Map_pointer __nfinish = __nstart + __num_nodes;
640 { _M_create_nodes(__nstart, __nfinish); }
643 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
644 this->_M_impl._M_map = _Map_pointer();
645 this->_M_impl._M_map_size = 0;
646 __throw_exception_again;
649 this->_M_impl._M_start._M_set_node(__nstart);
650 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
651 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
652 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
654 % __deque_buf_size(
sizeof(_Tp)));
657 template<
typename _Tp,
typename _Alloc>
665 for (__cur = __nstart; __cur < __nfinish; ++__cur)
666 *__cur = this->_M_allocate_node();
670 _M_destroy_nodes(__nstart, __cur);
671 __throw_exception_again;
675 template<
typename _Tp,
typename _Alloc>
677 _Deque_base<_Tp, _Alloc>::
678 _M_destroy_nodes(_Map_pointer __nstart,
679 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
681 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
682 _M_deallocate_node(*__n);
769 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
772 #ifdef _GLIBCXX_CONCEPT_CHECKS
774 typedef typename _Alloc::value_type _Alloc_value_type;
775 # if __cplusplus < 201103L
776 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
778 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
781 #if __cplusplus >= 201103L
782 static_assert(
is_same<
typename remove_cv<_Tp>::type, _Tp>::value,
783 "std::deque must have a non-const, non-volatile value_type");
784 # if __cplusplus > 201703L || defined __STRICT_ANSI__
786 "std::deque must have the same value_type as its allocator");
791 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
793 typedef typename _Base::_Map_pointer _Map_pointer;
796 typedef _Tp value_type;
797 typedef typename _Alloc_traits::pointer pointer;
798 typedef typename _Alloc_traits::const_pointer const_pointer;
799 typedef typename _Alloc_traits::reference reference;
800 typedef typename _Alloc_traits::const_reference const_reference;
805 typedef size_t size_type;
806 typedef ptrdiff_t difference_type;
807 typedef _Alloc allocator_type;
810 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
811 {
return __deque_buf_size(
sizeof(_Tp)); }
815 using _Base::_M_create_nodes;
816 using _Base::_M_destroy_nodes;
817 using _Base::_M_allocate_node;
818 using _Base::_M_deallocate_node;
819 using _Base::_M_allocate_map;
820 using _Base::_M_deallocate_map;
821 using _Base::_M_get_Tp_allocator;
827 using _Base::_M_impl;
836 #if __cplusplus >= 201103L
850 #if __cplusplus >= 201103L
860 deque(size_type __n,
const allocator_type& __a = allocator_type())
861 :
_Base(__a, _S_check_init_len(__n, __a))
862 { _M_default_initialize(); }
872 deque(size_type __n,
const value_type& __value,
873 const allocator_type& __a = allocator_type())
874 :
_Base(__a, _S_check_init_len(__n, __a))
886 deque(size_type __n,
const value_type& __value = value_type(),
887 const allocator_type& __a = allocator_type())
888 : _Base(__a, _S_check_init_len(__n, __a))
902 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
903 this->_M_impl._M_start,
904 _M_get_Tp_allocator()); }
906 #if __cplusplus >= 201103L
920 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
921 this->_M_impl._M_start,
922 _M_get_Tp_allocator()); }
937 if (__x.get_allocator() != __a && !__x.empty())
939 std::__uninitialized_move_a(__x.begin(), __x.end(),
940 this->_M_impl._M_start,
941 _M_get_Tp_allocator());
959 const allocator_type& __a = allocator_type())
982 #if __cplusplus >= 201103L
983 template<
typename _InputIterator,
984 typename = std::_RequireInputIter<_InputIterator>>
985 deque(_InputIterator __first, _InputIterator __last,
986 const allocator_type& __a = allocator_type())
993 template<
typename _InputIterator>
994 deque(_InputIterator __first, _InputIterator __last,
995 const allocator_type& __a = allocator_type())
999 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1000 _M_initialize_dispatch(__first, __last, _Integral());
1010 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
1024 #if __cplusplus >= 201103L
1037 _M_move_assign1(
std::move(__x), __always_equal{});
1055 _M_assign_aux(__l.begin(), __l.end(),
1072 assign(size_type __n,
const value_type& __val)
1073 { _M_fill_assign(__n, __val); }
1087 #if __cplusplus >= 201103L
1088 template<
typename _InputIterator,
1089 typename = std::_RequireInputIter<_InputIterator>>
1091 assign(_InputIterator __first, _InputIterator __last)
1094 template<
typename _InputIterator>
1096 assign(_InputIterator __first, _InputIterator __last)
1098 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1099 _M_assign_dispatch(__first, __last, _Integral());
1103 #if __cplusplus >= 201103L
1123 {
return _Base::get_allocator(); }
1132 {
return this->_M_impl._M_start; }
1140 {
return this->_M_impl._M_start; }
1149 {
return this->_M_impl._M_finish; }
1158 {
return this->_M_impl._M_finish; }
1174 const_reverse_iterator
1192 const_reverse_iterator
1196 #if __cplusplus >= 201103L
1203 {
return this->_M_impl._M_start; }
1212 {
return this->_M_impl._M_finish; }
1219 const_reverse_iterator
1228 const_reverse_iterator
1237 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
1242 {
return _S_max_size(_M_get_Tp_allocator()); }
1244 #if __cplusplus >= 201103L
1257 const size_type __len =
size();
1258 if (__new_size > __len)
1259 _M_default_append(__new_size - __len);
1260 else if (__new_size < __len)
1261 _M_erase_at_end(this->_M_impl._M_start
1262 + difference_type(__new_size));
1277 resize(size_type __new_size,
const value_type& __x)
1291 resize(size_type __new_size, value_type __x = value_type())
1294 const size_type __len =
size();
1295 if (__new_size > __len)
1296 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1297 else if (__new_size < __len)
1298 _M_erase_at_end(this->_M_impl._M_start
1299 + difference_type(__new_size));
1302 #if __cplusplus >= 201103L
1306 { _M_shrink_to_fit(); }
1313 _GLIBCXX_NODISCARD
bool
1315 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1332 __glibcxx_requires_subscript(__n);
1333 return this->_M_impl._M_start[difference_type(__n)];
1350 __glibcxx_requires_subscript(__n);
1351 return this->_M_impl._M_start[difference_type(__n)];
1359 if (__n >= this->
size())
1360 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n "
1361 "(which is %zu)>= this->size() "
1382 return (*
this)[__n];
1400 return (*
this)[__n];
1410 __glibcxx_requires_nonempty();
1421 __glibcxx_requires_nonempty();
1432 __glibcxx_requires_nonempty();
1445 __glibcxx_requires_nonempty();
1464 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1466 _Alloc_traits::construct(this->_M_impl,
1467 this->_M_impl._M_start._M_cur - 1,
1469 --this->_M_impl._M_start._M_cur;
1472 _M_push_front_aux(__x);
1475 #if __cplusplus >= 201103L
1480 template<
typename... _Args>
1481 #if __cplusplus > 201402L
1486 emplace_front(_Args&&... __args);
1501 if (this->_M_impl._M_finish._M_cur
1502 != this->_M_impl._M_finish._M_last - 1)
1504 _Alloc_traits::construct(this->_M_impl,
1505 this->_M_impl._M_finish._M_cur, __x);
1506 ++this->_M_impl._M_finish._M_cur;
1512 #if __cplusplus >= 201103L
1517 template<
typename... _Args>
1518 #if __cplusplus > 201402L
1523 emplace_back(_Args&&... __args);
1537 __glibcxx_requires_nonempty();
1538 if (this->_M_impl._M_start._M_cur
1539 != this->_M_impl._M_start._M_last - 1)
1541 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1542 this->_M_impl._M_start._M_cur);
1543 ++this->_M_impl._M_start._M_cur;
1560 __glibcxx_requires_nonempty();
1561 if (this->_M_impl._M_finish._M_cur
1562 != this->_M_impl._M_finish._M_first)
1564 --this->_M_impl._M_finish._M_cur;
1565 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1566 this->_M_impl._M_finish._M_cur);
1572 #if __cplusplus >= 201103L
1582 template<
typename... _Args>
1584 emplace(const_iterator __position, _Args&&... __args);
1596 insert(const_iterator __position,
const value_type& __x);
1611 #if __cplusplus >= 201103L
1638 auto __offset = __p -
cbegin();
1639 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1641 return begin() + __offset;
1657 difference_type __offset = __position -
cbegin();
1658 _M_fill_insert(__position._M_const_cast(), __n, __x);
1659 return begin() + __offset;
1672 insert(
iterator __position, size_type __n,
const value_type& __x)
1673 { _M_fill_insert(__position, __n, __x); }
1676 #if __cplusplus >= 201103L
1688 template<
typename _InputIterator,
1689 typename = std::_RequireInputIter<_InputIterator>>
1692 _InputIterator __last)
1694 difference_type __offset = __position -
cbegin();
1695 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1697 return begin() + __offset;
1710 template<
typename _InputIterator>
1713 _InputIterator __last)
1716 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1717 _M_insert_dispatch(__position, __first, __last, _Integral());
1735 #if __cplusplus >= 201103L
1740 {
return _M_erase(__position._M_const_cast()); }
1759 #if __cplusplus >= 201103L
1764 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1780 #if __cplusplus >= 201103L
1781 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1782 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1784 _M_impl._M_swap_data(__x._M_impl);
1785 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1786 __x._M_get_Tp_allocator());
1797 { _M_erase_at_end(
begin()); }
1802 #if __cplusplus < 201103L
1807 template<
typename _Integer>
1809 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1811 _M_initialize_map(_S_check_init_len(
static_cast<size_type
>(__n),
1812 _M_get_Tp_allocator()));
1817 template<
typename _InputIterator>
1819 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1828 _S_check_init_len(
size_t __n,
const allocator_type& __a)
1830 if (__n > _S_max_size(__a))
1831 __throw_length_error(
1832 __N(
"cannot create std::deque larger than max_size()"));
1837 _S_max_size(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1839 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1841 return (
std::min)(__diffmax, __allocmax);
1856 template<
typename _InputIterator>
1862 template<
typename _ForwardIterator>
1881 #if __cplusplus >= 201103L
1884 _M_default_initialize();
1890 #if __cplusplus < 201103L
1895 template<
typename _Integer>
1897 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1898 { _M_fill_assign(__n, __val); }
1901 template<
typename _InputIterator>
1903 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1909 template<
typename _InputIterator>
1911 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1915 template<
typename _ForwardIterator>
1917 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1920 const size_type __len = std::distance(__first, __last);
1923 _ForwardIterator __mid = __first;
1924 std::advance(__mid,
size());
1925 std::copy(__first, __mid,
begin());
1926 _M_range_insert_aux(
end(), __mid, __last,
1930 _M_erase_at_end(std::copy(__first, __last,
begin()));
1936 _M_fill_assign(size_type __n,
const value_type& __val)
1941 _M_fill_insert(
end(), __n -
size(), __val);
1945 _M_erase_at_end(
begin() + difference_type(__n));
1952 #if __cplusplus < 201103L
1955 void _M_push_front_aux(
const value_type&);
1957 template<
typename... _Args>
1960 template<
typename... _Args>
1961 void _M_push_front_aux(_Args&&... __args);
1964 void _M_pop_back_aux();
1966 void _M_pop_front_aux();
1972 #if __cplusplus < 201103L
1977 template<
typename _Integer>
1979 _M_insert_dispatch(iterator __pos,
1980 _Integer __n, _Integer __x, __true_type)
1981 { _M_fill_insert(__pos, __n, __x); }
1984 template<
typename _InputIterator>
1986 _M_insert_dispatch(iterator __pos,
1987 _InputIterator __first, _InputIterator __last,
1990 _M_range_insert_aux(__pos, __first, __last,
1996 template<
typename _InputIterator>
1998 _M_range_insert_aux(iterator __pos, _InputIterator __first,
2002 template<
typename _ForwardIterator>
2004 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2011 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
2014 #if __cplusplus < 201103L
2016 _M_insert_aux(iterator __pos,
const value_type& __x);
2018 template<
typename... _Args>
2020 _M_insert_aux(iterator __pos, _Args&&... __args);
2025 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2028 template<
typename _ForwardIterator>
2030 _M_insert_aux(iterator __pos,
2031 _ForwardIterator __first, _ForwardIterator __last,
2038 _M_destroy_data_aux(iterator __first, iterator __last);
2042 template<
typename _Alloc1>
2044 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2045 { _M_destroy_data_aux(__first, __last); }
2048 _M_destroy_data(iterator __first, iterator __last,
2051 if (!__has_trivial_destructor(value_type))
2052 _M_destroy_data_aux(__first, __last);
2057 _M_erase_at_begin(iterator __pos)
2059 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2060 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2061 this->_M_impl._M_start = __pos;
2067 _M_erase_at_end(iterator __pos)
2069 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2070 _M_destroy_nodes(__pos._M_node + 1,
2071 this->_M_impl._M_finish._M_node + 1);
2072 this->_M_impl._M_finish = __pos;
2076 _M_erase(iterator __pos);
2079 _M_erase(iterator __first, iterator __last);
2081 #if __cplusplus >= 201103L
2084 _M_default_append(size_type __n);
2095 const size_type __vacancies = this->_M_impl._M_start._M_cur
2096 - this->_M_impl._M_start._M_first;
2097 if (__n > __vacancies)
2098 _M_new_elements_at_front(__n - __vacancies);
2099 return this->_M_impl._M_start - difference_type(__n);
2103 _M_reserve_elements_at_back(size_type __n)
2105 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2106 - this->_M_impl._M_finish._M_cur) - 1;
2107 if (__n > __vacancies)
2108 _M_new_elements_at_back(__n - __vacancies);
2109 return this->_M_impl._M_finish + difference_type(__n);
2113 _M_new_elements_at_front(size_type __new_elements);
2116 _M_new_elements_at_back(size_type __new_elements);
2131 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2132 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2133 _M_reallocate_map(__nodes_to_add,
false);
2137 _M_reserve_map_at_front(size_type __nodes_to_add = 1)
2139 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2140 - this->_M_impl._M_map))
2141 _M_reallocate_map(__nodes_to_add,
true);
2145 _M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front);
2148 #if __cplusplus >= 201103L
2154 this->_M_impl._M_swap_data(__x._M_impl);
2156 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2165 if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
2168 constexpr
bool __move_storage =
2169 _Alloc_traits::_S_propagate_on_move_assign();
2170 _M_move_assign2(
std::move(__x), __bool_constant<__move_storage>());
2175 template<
typename... _Args>
2177 _M_replace_map(_Args&&... __args)
2180 deque __newobj(std::forward<_Args>(__args)...);
2183 _M_deallocate_node(*
begin()._M_node);
2184 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2185 this->_M_impl._M_map =
nullptr;
2186 this->_M_impl._M_map_size = 0;
2188 this->_M_impl._M_swap_data(__newobj._M_impl);
2196 auto __alloc = __x._M_get_Tp_allocator();
2201 _M_get_Tp_allocator() =
std::move(__alloc);
2209 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2213 _M_replace_map(
std::move(__x), __x.get_allocator());
2219 _M_assign_aux(std::make_move_iterator(__x.begin()),
2220 std::make_move_iterator(__x.end()),
2228 #if __cpp_deduction_guides >= 201606
2229 template<
typename _InputIterator,
typename _ValT
2230 =
typename iterator_traits<_InputIterator>::value_type,
2231 typename _Allocator = allocator<_ValT>,
2232 typename = _RequireInputIter<_InputIterator>,
2233 typename = _RequireAllocator<_Allocator>>
2234 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2235 -> deque<_ValT, _Allocator>;
2248 template<
typename _Tp,
typename _Alloc>
2254 #if __cpp_lib_three_way_comparison
2266 template<
typename _Tp,
typename _Alloc>
2267 inline __detail::__synth3way_t<_Tp>
2268 operator<=>(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2270 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2271 __y.begin(), __y.end(),
2272 __detail::__synth3way);
2286 template<
typename _Tp,
typename _Alloc>
2289 {
return std::lexicographical_compare(__x.
begin(), __x.
end(),
2293 template<
typename _Tp,
typename _Alloc>
2296 {
return !(__x == __y); }
2299 template<
typename _Tp,
typename _Alloc>
2302 {
return __y < __x; }
2305 template<
typename _Tp,
typename _Alloc>
2308 {
return !(__y < __x); }
2311 template<
typename _Tp,
typename _Alloc>
2314 {
return !(__x < __y); }
2318 template<
typename _Tp,
typename _Alloc>
2321 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2324 #undef _GLIBCXX_DEQUE_BUF_SIZE
2326 _GLIBCXX_END_NAMESPACE_CONTAINER
2328 #if __cplusplus >= 201103L
2332 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2336 _GLIBCXX_END_NAMESPACE_VERSION
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
integral_constant< bool, 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.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
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.
ISO C++ entities toplevel namespace is std.
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
is_nothrow_default_constructible
__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.
The standard allocator, as per [20.4].
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.
deque(const deque &__x, const allocator_type &__a)
Copy constructor with alternative allocator.
deque(deque &&__x, const allocator_type &__a)
Move constructor with alternative allocator.
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 pop_back() noexcept
Removes last element.
size_type size() const noexcept
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.
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 & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
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
deque()=default
Creates a deque with no elements.
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
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_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_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
Fills the deque with whatever is in [first,last).
reference front() noexcept
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
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.