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); }
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>
320 operator<(
const _Self& __x,
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>
336 operator>(
const _Self& __x,
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>
349 operator<=(
const _Self& __x,
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>
362 operator>=(
const _Self& __x,
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 - int(__x._M_node != 0))
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) _GLIBCXX_NOEXCEPT
388 return difference_type(_S_buffer_size())
389 * (__x._M_node - __y._M_node - int(__x._M_node != 0))
390 + (__x._M_cur - __x._M_first)
391 + (__y._M_last - __y._M_cur);
396 operator+(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
405 operator-(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
414 operator+(difference_type __n,
const _Self& __x) _GLIBCXX_NOEXCEPT
415 {
return __x + __n; }
428 template<
typename _Tp,
typename _Alloc>
433 rebind<_Tp>::other _Tp_alloc_type;
436 #if __cplusplus < 201103L
438 typedef const _Tp* _Ptr_const;
440 typedef typename _Alloc_traits::pointer _Ptr;
441 typedef typename _Alloc_traits::const_pointer _Ptr_const;
444 typedef typename _Alloc_traits::template rebind<_Ptr>::other
448 typedef _Alloc allocator_type;
451 get_allocator()
const _GLIBCXX_NOEXCEPT
452 {
return allocator_type(_M_get_Tp_allocator()); }
465 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
473 #if __cplusplus >= 201103L
475 : _M_impl(
std::move(__x._M_get_Tp_allocator()))
478 if (__x._M_impl._M_map)
479 this->_M_impl._M_swap_data(__x._M_impl);
483 : _M_impl(
std::move(__x._M_impl), _Tp_alloc_type(__a))
484 { __x._M_initialize_map(0); }
489 if (__x.get_allocator() == __a)
491 if (__x._M_impl._M_map)
494 this->_M_impl._M_swap_data(__x._M_impl);
506 typedef typename iterator::_Map_pointer _Map_pointer;
508 struct _Deque_impl_data
515 _Deque_impl_data() _GLIBCXX_NOEXCEPT
516 : _M_map(), _M_map_size(), _M_start(), _M_finish()
519 #if __cplusplus >= 201103L
520 _Deque_impl_data(
const _Deque_impl_data&) =
default;
522 operator=(
const _Deque_impl_data&) =
default;
524 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
525 : _Deque_impl_data(__x)
526 { __x = _Deque_impl_data(); }
530 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
542 :
public _Tp_alloc_type,
public _Deque_impl_data
544 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
549 _Deque_impl(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
550 : _Tp_alloc_type(__a)
553 #if __cplusplus >= 201103L
554 _Deque_impl(_Deque_impl&&) =
default;
556 _Deque_impl(_Tp_alloc_type&& __a) noexcept
560 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
567 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
568 {
return this->_M_impl; }
570 const _Tp_alloc_type&
571 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
572 {
return this->_M_impl; }
575 _M_get_map_allocator()
const _GLIBCXX_NOEXCEPT
576 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
582 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
586 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
589 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
593 _M_allocate_map(
size_t __n)
595 _Map_alloc_type __map_alloc = _M_get_map_allocator();
600 _M_deallocate_map(_Map_pointer __p,
size_t __n) _GLIBCXX_NOEXCEPT
602 _Map_alloc_type __map_alloc = _M_get_map_allocator();
607 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
608 void _M_destroy_nodes(_Map_pointer __nstart,
609 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
610 enum { _S_initial_map_size = 8 };
615 template<
typename _Tp,
typename _Alloc>
616 _Deque_base<_Tp, _Alloc>::
617 ~_Deque_base() _GLIBCXX_NOEXCEPT
619 if (this->_M_impl._M_map)
621 _M_destroy_nodes(this->_M_impl._M_start._M_node,
622 this->_M_impl._M_finish._M_node + 1);
623 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
635 template<
typename _Tp,
typename _Alloc>
640 const size_t __num_nodes = (__num_elements / __deque_buf_size(
sizeof(_Tp))
643 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
644 size_t(__num_nodes + 2));
645 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
652 _Map_pointer __nstart = (this->_M_impl._M_map
653 + (this->_M_impl._M_map_size - __num_nodes) / 2);
654 _Map_pointer __nfinish = __nstart + __num_nodes;
657 { _M_create_nodes(__nstart, __nfinish); }
660 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
661 this->_M_impl._M_map = _Map_pointer();
662 this->_M_impl._M_map_size = 0;
663 __throw_exception_again;
666 this->_M_impl._M_start._M_set_node(__nstart);
667 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
668 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
669 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
671 % __deque_buf_size(
sizeof(_Tp)));
674 template<
typename _Tp,
typename _Alloc>
682 for (__cur = __nstart; __cur < __nfinish; ++__cur)
683 *__cur = this->_M_allocate_node();
687 _M_destroy_nodes(__nstart, __cur);
688 __throw_exception_again;
692 template<
typename _Tp,
typename _Alloc>
694 _Deque_base<_Tp, _Alloc>::
695 _M_destroy_nodes(_Map_pointer __nstart,
696 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
698 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
699 _M_deallocate_node(*__n);
786 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
789 #ifdef _GLIBCXX_CONCEPT_CHECKS
791 typedef typename _Alloc::value_type _Alloc_value_type;
792 # if __cplusplus < 201103L
793 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
795 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
798 #if __cplusplus >= 201103L
799 static_assert(
is_same<
typename remove_cv<_Tp>::type, _Tp>::value,
800 "std::deque must have a non-const, non-volatile value_type");
801 # if __cplusplus > 201703L || defined __STRICT_ANSI__
803 "std::deque must have the same value_type as its allocator");
808 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
810 typedef typename _Base::_Map_pointer _Map_pointer;
813 typedef _Tp value_type;
814 typedef typename _Alloc_traits::pointer pointer;
815 typedef typename _Alloc_traits::const_pointer const_pointer;
816 typedef typename _Alloc_traits::reference reference;
817 typedef typename _Alloc_traits::const_reference const_reference;
822 typedef size_t size_type;
823 typedef ptrdiff_t difference_type;
824 typedef _Alloc allocator_type;
827 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
828 {
return __deque_buf_size(
sizeof(_Tp)); }
832 using _Base::_M_create_nodes;
833 using _Base::_M_destroy_nodes;
834 using _Base::_M_allocate_node;
835 using _Base::_M_deallocate_node;
836 using _Base::_M_allocate_map;
837 using _Base::_M_deallocate_map;
838 using _Base::_M_get_Tp_allocator;
844 using _Base::_M_impl;
853 #if __cplusplus >= 201103L
867 #if __cplusplus >= 201103L
877 deque(size_type __n,
const allocator_type& __a = allocator_type())
878 :
_Base(__a, _S_check_init_len(__n, __a))
879 { _M_default_initialize(); }
889 deque(size_type __n,
const value_type& __value,
890 const allocator_type& __a = allocator_type())
891 :
_Base(__a, _S_check_init_len(__n, __a))
903 deque(size_type __n,
const value_type& __value = value_type(),
904 const allocator_type& __a = allocator_type())
905 : _Base(__a, _S_check_init_len(__n, __a))
919 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
920 this->_M_impl._M_start,
921 _M_get_Tp_allocator()); }
923 #if __cplusplus >= 201103L
935 deque(
const deque& __x,
const __type_identity_t<allocator_type>& __a)
937 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
938 this->_M_impl._M_start,
939 _M_get_Tp_allocator()); }
942 deque(
deque&& __x,
const __type_identity_t<allocator_type>& __a)
954 if (__x.get_allocator() != __a && !__x.empty())
956 std::__uninitialized_move_a(__x.begin(), __x.end(),
957 this->_M_impl._M_start,
958 _M_get_Tp_allocator());
976 const allocator_type& __a = allocator_type())
999 #if __cplusplus >= 201103L
1000 template<
typename _InputIterator,
1001 typename = std::_RequireInputIter<_InputIterator>>
1002 deque(_InputIterator __first, _InputIterator __last,
1003 const allocator_type& __a = allocator_type())
1010 template<
typename _InputIterator>
1011 deque(_InputIterator __first, _InputIterator __last,
1012 const allocator_type& __a = allocator_type())
1016 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1017 _M_initialize_dispatch(__first, __last, _Integral());
1027 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
1041 #if __cplusplus >= 201103L
1054 _M_move_assign1(
std::move(__x), __always_equal{});
1072 _M_assign_aux(__l.begin(), __l.end(),
1089 assign(size_type __n,
const value_type& __val)
1090 { _M_fill_assign(__n, __val); }
1104 #if __cplusplus >= 201103L
1105 template<
typename _InputIterator,
1106 typename = std::_RequireInputIter<_InputIterator>>
1108 assign(_InputIterator __first, _InputIterator __last)
1111 template<
typename _InputIterator>
1113 assign(_InputIterator __first, _InputIterator __last)
1115 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1116 _M_assign_dispatch(__first, __last, _Integral());
1120 #if __cplusplus >= 201103L
1141 {
return _Base::get_allocator(); }
1151 {
return this->_M_impl._M_start; }
1160 {
return this->_M_impl._M_start; }
1170 {
return this->_M_impl._M_finish; }
1180 {
return this->_M_impl._M_finish; }
1198 const_reverse_iterator
1218 const_reverse_iterator
1222 #if __cplusplus >= 201103L
1230 {
return this->_M_impl._M_start; }
1240 {
return this->_M_impl._M_finish; }
1248 const_reverse_iterator
1258 const_reverse_iterator
1268 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
1274 {
return _S_max_size(_M_get_Tp_allocator()); }
1276 #if __cplusplus >= 201103L
1289 const size_type __len =
size();
1290 if (__new_size > __len)
1291 _M_default_append(__new_size - __len);
1292 else if (__new_size < __len)
1293 _M_erase_at_end(this->_M_impl._M_start
1294 + difference_type(__new_size));
1309 resize(size_type __new_size,
const value_type& __x)
1323 resize(size_type __new_size, value_type __x = value_type())
1326 const size_type __len =
size();
1327 if (__new_size > __len)
1328 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1329 else if (__new_size < __len)
1330 _M_erase_at_end(this->_M_impl._M_start
1331 + difference_type(__new_size));
1334 #if __cplusplus >= 201103L
1338 { _M_shrink_to_fit(); }
1345 _GLIBCXX_NODISCARD
bool
1347 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1365 __glibcxx_requires_subscript(__n);
1366 return this->_M_impl._M_start[difference_type(__n)];
1384 __glibcxx_requires_subscript(__n);
1385 return this->_M_impl._M_start[difference_type(__n)];
1393 if (__n >= this->
size())
1394 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n "
1395 "(which is %zu)>= this->size() "
1416 return (*
this)[__n];
1434 return (*
this)[__n];
1445 __glibcxx_requires_nonempty();
1457 __glibcxx_requires_nonempty();
1469 __glibcxx_requires_nonempty();
1483 __glibcxx_requires_nonempty();
1502 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1504 _Alloc_traits::construct(this->_M_impl,
1505 this->_M_impl._M_start._M_cur - 1,
1507 --this->_M_impl._M_start._M_cur;
1513 #if __cplusplus >= 201103L
1518 template<
typename... _Args>
1519 #if __cplusplus > 201402L
1524 emplace_front(_Args&&... __args);
1539 if (this->_M_impl._M_finish._M_cur
1540 != this->_M_impl._M_finish._M_last - 1)
1542 _Alloc_traits::construct(this->_M_impl,
1543 this->_M_impl._M_finish._M_cur, __x);
1544 ++this->_M_impl._M_finish._M_cur;
1550 #if __cplusplus >= 201103L
1555 template<
typename... _Args>
1556 #if __cplusplus > 201402L
1561 emplace_back(_Args&&... __args);
1575 __glibcxx_requires_nonempty();
1576 if (this->_M_impl._M_start._M_cur
1577 != this->_M_impl._M_start._M_last - 1)
1579 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1580 this->_M_impl._M_start._M_cur);
1581 ++this->_M_impl._M_start._M_cur;
1598 __glibcxx_requires_nonempty();
1599 if (this->_M_impl._M_finish._M_cur
1600 != this->_M_impl._M_finish._M_first)
1602 --this->_M_impl._M_finish._M_cur;
1603 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1604 this->_M_impl._M_finish._M_cur);
1610 #if __cplusplus >= 201103L
1620 template<
typename... _Args>
1622 emplace(const_iterator __position, _Args&&... __args);
1634 insert(const_iterator __position,
const value_type& __x);
1649 #if __cplusplus >= 201103L
1676 auto __offset = __p -
cbegin();
1677 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1679 return begin() + __offset;
1695 difference_type __offset = __position -
cbegin();
1696 _M_fill_insert(__position._M_const_cast(), __n, __x);
1697 return begin() + __offset;
1710 insert(
iterator __position, size_type __n,
const value_type& __x)
1711 { _M_fill_insert(__position, __n, __x); }
1714 #if __cplusplus >= 201103L
1726 template<
typename _InputIterator,
1727 typename = std::_RequireInputIter<_InputIterator>>
1730 _InputIterator __last)
1732 difference_type __offset = __position -
cbegin();
1733 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1735 return begin() + __offset;
1748 template<
typename _InputIterator>
1751 _InputIterator __last)
1754 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1755 _M_insert_dispatch(__position, __first, __last, _Integral());
1773 #if __cplusplus >= 201103L
1778 {
return _M_erase(__position._M_const_cast()); }
1797 #if __cplusplus >= 201103L
1802 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1818 #if __cplusplus >= 201103L
1819 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1820 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1822 _M_impl._M_swap_data(__x._M_impl);
1823 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1824 __x._M_get_Tp_allocator());
1835 { _M_erase_at_end(
begin()); }
1840 #if __cplusplus < 201103L
1845 template<
typename _Integer>
1847 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1849 _M_initialize_map(_S_check_init_len(
static_cast<size_type
>(__n),
1850 _M_get_Tp_allocator()));
1855 template<
typename _InputIterator>
1857 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1866 _S_check_init_len(
size_t __n,
const allocator_type& __a)
1868 if (__n > _S_max_size(__a))
1869 __throw_length_error(
1870 __N(
"cannot create std::deque larger than max_size()"));
1875 _S_max_size(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1877 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1879 return (
std::min)(__diffmax, __allocmax);
1894 template<
typename _InputIterator>
1900 template<
typename _ForwardIterator>
1919 #if __cplusplus >= 201103L
1922 _M_default_initialize();
1928 #if __cplusplus < 201103L
1933 template<
typename _Integer>
1935 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1936 { _M_fill_assign(__n, __val); }
1939 template<
typename _InputIterator>
1941 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1947 template<
typename _InputIterator>
1949 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1953 template<
typename _ForwardIterator>
1955 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1961 _ForwardIterator __mid = __first;
1963 std::copy(__first, __mid,
begin());
1964 _M_range_insert_aux(
end(), __mid, __last,
1968 _M_erase_at_end(std::copy(__first, __last,
begin()));
1974 _M_fill_assign(size_type __n,
const value_type& __val)
1979 _M_fill_insert(
end(), __n -
size(), __val);
1983 _M_erase_at_end(
begin() + difference_type(__n));
1990 #if __cplusplus < 201103L
1995 template<
typename... _Args>
1998 template<
typename... _Args>
2010 #if __cplusplus < 201103L
2015 template<
typename _Integer>
2017 _M_insert_dispatch(iterator __pos,
2018 _Integer __n, _Integer __x, __true_type)
2019 { _M_fill_insert(__pos, __n, __x); }
2022 template<
typename _InputIterator>
2024 _M_insert_dispatch(iterator __pos,
2025 _InputIterator __first, _InputIterator __last,
2028 _M_range_insert_aux(__pos, __first, __last,
2034 template<
typename _InputIterator>
2036 _M_range_insert_aux(iterator __pos, _InputIterator __first,
2040 template<
typename _ForwardIterator>
2042 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2049 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
2052 #if __cplusplus < 201103L
2054 _M_insert_aux(iterator __pos,
const value_type& __x);
2056 template<
typename... _Args>
2058 _M_insert_aux(iterator __pos, _Args&&... __args);
2063 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2066 template<
typename _ForwardIterator>
2068 _M_insert_aux(iterator __pos,
2069 _ForwardIterator __first, _ForwardIterator __last,
2076 _M_destroy_data_aux(iterator __first, iterator __last);
2080 template<
typename _Alloc1>
2082 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2083 { _M_destroy_data_aux(__first, __last); }
2086 _M_destroy_data(iterator __first, iterator __last,
2089 if (!__has_trivial_destructor(value_type))
2090 _M_destroy_data_aux(__first, __last);
2095 _M_erase_at_begin(iterator __pos)
2097 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2098 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2099 this->_M_impl._M_start = __pos;
2105 _M_erase_at_end(iterator __pos)
2107 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2108 _M_destroy_nodes(__pos._M_node + 1,
2109 this->_M_impl._M_finish._M_node + 1);
2110 this->_M_impl._M_finish = __pos;
2114 _M_erase(iterator __pos);
2117 _M_erase(iterator __first, iterator __last);
2119 #if __cplusplus >= 201103L
2122 _M_default_append(size_type __n);
2133 const size_type __vacancies = this->_M_impl._M_start._M_cur
2134 - this->_M_impl._M_start._M_first;
2135 if (__n > __vacancies)
2137 return this->_M_impl._M_start - difference_type(__n);
2143 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2144 - this->_M_impl._M_finish._M_cur) - 1;
2145 if (__n > __vacancies)
2147 return this->_M_impl._M_finish + difference_type(__n);
2169 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2170 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2177 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2178 - this->_M_impl._M_map))
2186 #if __cplusplus >= 201103L
2192 this->_M_impl._M_swap_data(__x._M_impl);
2194 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2203 if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
2206 constexpr
bool __move_storage =
2207 _Alloc_traits::_S_propagate_on_move_assign();
2208 _M_move_assign2(
std::move(__x), __bool_constant<__move_storage>());
2213 template<
typename... _Args>
2215 _M_replace_map(_Args&&... __args)
2218 deque __newobj(std::forward<_Args>(__args)...);
2221 _M_deallocate_node(*
begin()._M_node);
2222 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2223 this->_M_impl._M_map =
nullptr;
2224 this->_M_impl._M_map_size = 0;
2226 this->_M_impl._M_swap_data(__newobj._M_impl);
2234 auto __alloc = __x._M_get_Tp_allocator();
2239 _M_get_Tp_allocator() =
std::move(__alloc);
2247 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2251 _M_replace_map(
std::move(__x), __x.get_allocator());
2257 _M_assign_aux(std::make_move_iterator(__x.begin()),
2258 std::make_move_iterator(__x.end()),
2266 #if __cpp_deduction_guides >= 201606
2267 template<
typename _InputIterator,
typename _ValT
2268 =
typename iterator_traits<_InputIterator>::value_type,
2269 typename _Allocator = allocator<_ValT>,
2270 typename = _RequireInputIter<_InputIterator>,
2271 typename = _RequireAllocator<_Allocator>>
2272 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2273 -> deque<_ValT, _Allocator>;
2286 template<
typename _Tp,
typename _Alloc>
2293 #if __cpp_lib_three_way_comparison
2305 template<
typename _Tp,
typename _Alloc>
2307 inline __detail::__synth3way_t<_Tp>
2308 operator<=>(
const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
2310 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2311 __y.begin(), __y.end(),
2312 __detail::__synth3way);
2326 template<
typename _Tp,
typename _Alloc>
2330 {
return std::lexicographical_compare(__x.
begin(), __x.
end(),
2334 template<
typename _Tp,
typename _Alloc>
2338 {
return !(__x == __y); }
2341 template<
typename _Tp,
typename _Alloc>
2345 {
return __y < __x; }
2348 template<
typename _Tp,
typename _Alloc>
2352 {
return !(__y < __x); }
2355 template<
typename _Tp,
typename _Alloc>
2359 {
return !(__x < __y); }
2363 template<
typename _Tp,
typename _Alloc>
2366 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2369 #undef _GLIBCXX_DEQUE_BUF_SIZE
2371 _GLIBCXX_END_NAMESPACE_CONTAINER
2373 #if __cplusplus >= 201103L
2377 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2381 _GLIBCXX_END_NAMESPACE_VERSION
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
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.
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
__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 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.
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.
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
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_*.
void push_back(const value_type &__x)
Add data to the end of the deque.
deque(const allocator_type &__a)
Creates a deque with no elements.
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
void _M_range_check(size_type __n) const
Safety check used only from at().
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
void shrink_to_fit() noexcept
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
const_iterator begin() const noexcept
deque & operator=(const deque &__x)
Deque assignment operator.
const_iterator end() const noexcept
iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the deque.
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
void _M_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
Fills the deque with whatever is in [first,last).
reference front() noexcept
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
const_iterator cend() const noexcept
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
const_reverse_iterator rbegin() const noexcept
deque(deque &&__x, const __type_identity_t< allocator_type > &__a)
Move constructor with alternative allocator.
iterator begin() noexcept
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
deque(deque &&)=default
Deque move constructor.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Tp_alloc_type &__a) noexcept
The maximum supported allocation size.