62#if __cplusplus >= 201103L
69namespace std _GLIBCXX_VISIBILITY(default)
71_GLIBCXX_BEGIN_NAMESPACE_VERSION
72_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
88#ifndef _GLIBCXX_DEQUE_BUF_SIZE
89#define _GLIBCXX_DEQUE_BUF_SIZE 512
92 _GLIBCXX_CONSTEXPR
inline size_t
93 __deque_buf_size(
size_t __size)
109 template<
typename _Tp,
typename _Ref,
typename _Ptr>
112#if __cplusplus < 201103L
115 typedef _Tp* _Elt_pointer;
116 typedef _Tp** _Map_pointer;
119 template<
typename _CvTp>
128 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
129 {
return __deque_buf_size(
sizeof(_Tp)); }
132 typedef _Tp value_type;
133 typedef _Ptr pointer;
134 typedef _Ref reference;
135 typedef size_t size_type;
136 typedef ptrdiff_t difference_type;
140 _Elt_pointer _M_first;
141 _Elt_pointer _M_last;
142 _Map_pointer _M_node;
145 : _M_cur(__x), _M_first(*__y),
146 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
149 : _M_cur(), _M_first(), _M_last(), _M_node() { }
151#if __cplusplus < 201103L
154 : _M_cur(__x._M_cur), _M_first(__x._M_first),
155 _M_last(__x._M_last), _M_node(__x._M_node) { }
158 template<
typename _Iter,
159 typename = _Require<is_same<_Self, const_iterator>,
162 : _M_cur(__x._M_cur), _M_first(__x._M_first),
163 _M_last(__x._M_last), _M_node(__x._M_node) { }
166 : _M_cur(__x._M_cur), _M_first(__x._M_first),
167 _M_last(__x._M_last), _M_node(__x._M_node) { }
173 _M_const_cast()
const _GLIBCXX_NOEXCEPT
174 {
return iterator(_M_cur, _M_node); }
177 operator*()
const _GLIBCXX_NOEXCEPT
181 operator->()
const _GLIBCXX_NOEXCEPT
185 operator++() _GLIBCXX_NOEXCEPT
188 if (_M_cur == _M_last)
197 operator++(
int) _GLIBCXX_NOEXCEPT
205 operator--() _GLIBCXX_NOEXCEPT
207 if (_M_cur == _M_first)
217 operator--(
int) _GLIBCXX_NOEXCEPT
225 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
227 const difference_type __offset = __n + (_M_cur - _M_first);
228 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
232 const difference_type __node_offset =
233 __offset > 0 ? __offset / difference_type(_S_buffer_size())
234 : -difference_type((-__offset - 1)
235 / _S_buffer_size()) - 1;
237 _M_cur = _M_first + (__offset - __node_offset
238 * difference_type(_S_buffer_size()));
244 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
245 {
return *
this += -__n; }
248 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
249 {
return *(*
this + __n); }
259 _M_node = __new_node;
260 _M_first = *__new_node;
261 _M_last = _M_first + difference_type(_S_buffer_size());
265 operator==(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
266 {
return __x._M_cur == __y._M_cur; }
271 template<
typename _RefR,
typename _PtrR>
273 operator==(
const _Self& __x,
274 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
275 {
return __x._M_cur == __y._M_cur; }
278 operator!=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
279 {
return !(__x == __y); }
281 template<
typename _RefR,
typename _PtrR>
283 operator!=(
const _Self& __x,
284 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
285 {
return !(__x == __y); }
288 operator<(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
290 return (__x._M_node == __y._M_node)
291 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
294 template<
typename _RefR,
typename _PtrR>
296 operator<(
const _Self& __x,
297 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
299 return (__x._M_node == __y._M_node)
300 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
304 operator>(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
305 {
return __y < __x; }
307 template<
typename _RefR,
typename _PtrR>
309 operator>(
const _Self& __x,
310 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
311 {
return __y < __x; }
314 operator<=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
315 {
return !(__y < __x); }
317 template<
typename _RefR,
typename _PtrR>
319 operator<=(
const _Self& __x,
320 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
321 {
return !(__y < __x); }
324 operator>=(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
325 {
return !(__x < __y); }
327 template<
typename _RefR,
typename _PtrR>
329 operator>=(
const _Self& __x,
330 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
331 {
return !(__x < __y); }
333 friend difference_type
334 operator-(
const _Self& __x,
const _Self& __y) _GLIBCXX_NOEXCEPT
336 return difference_type(_S_buffer_size())
337 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
338 + (__y._M_last - __y._M_cur);
345 template<
typename _RefR,
typename _PtrR>
346 friend difference_type
347 operator-(
const _Self& __x,
348 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
350 return difference_type(_S_buffer_size())
351 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
352 + (__y._M_last - __y._M_cur);
356 operator+(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
364 operator-(
const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
372 operator+(difference_type __n,
const _Self& __x) _GLIBCXX_NOEXCEPT
373 {
return __x + __n; }
386 template<
typename _Tp,
typename _Alloc>
391 rebind<_Tp>::other _Tp_alloc_type;
394#if __cplusplus < 201103L
396 typedef const _Tp* _Ptr_const;
398 typedef typename _Alloc_traits::pointer _Ptr;
399 typedef typename _Alloc_traits::const_pointer _Ptr_const;
402 typedef typename _Alloc_traits::template rebind<_Ptr>::other
406 typedef _Alloc allocator_type;
409 get_allocator()
const _GLIBCXX_NOEXCEPT
410 {
return allocator_type(_M_get_Tp_allocator()); }
423 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
431#if __cplusplus >= 201103L
433 : _M_impl(
std::move(__x._M_get_Tp_allocator()))
436 if (__x._M_impl._M_map)
437 this->_M_impl._M_swap_data(__x._M_impl);
441 : _M_impl(
std::move(__x._M_impl), _Tp_alloc_type(__a))
442 { __x._M_initialize_map(0); }
447 if (__x.get_allocator() == __a)
449 if (__x._M_impl._M_map)
452 this->_M_impl._M_swap_data(__x._M_impl);
464 typedef typename iterator::_Map_pointer _Map_pointer;
466 struct _Deque_impl_data
473 _Deque_impl_data() _GLIBCXX_NOEXCEPT
474 : _M_map(), _M_map_size(), _M_start(), _M_finish()
477#if __cplusplus >= 201103L
478 _Deque_impl_data(
const _Deque_impl_data&) =
default;
480 operator=(
const _Deque_impl_data&) =
default;
482 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
483 : _Deque_impl_data(__x)
484 { __x = _Deque_impl_data(); }
488 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
492 std::swap(*
this, __x);
500 :
public _Tp_alloc_type,
public _Deque_impl_data
502 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
507 _Deque_impl(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
508 : _Tp_alloc_type(__a)
511#if __cplusplus >= 201103L
512 _Deque_impl(_Deque_impl&&) =
default;
514 _Deque_impl(_Tp_alloc_type&& __a) noexcept
518 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
525 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
526 {
return this->_M_impl; }
528 const _Tp_alloc_type&
529 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
530 {
return this->_M_impl; }
533 _M_get_map_allocator()
const _GLIBCXX_NOEXCEPT
534 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
540 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
544 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
547 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
551 _M_allocate_map(
size_t __n)
553 _Map_alloc_type __map_alloc = _M_get_map_allocator();
558 _M_deallocate_map(_Map_pointer __p,
size_t __n) _GLIBCXX_NOEXCEPT
560 _Map_alloc_type __map_alloc = _M_get_map_allocator();
565 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
566 void _M_destroy_nodes(_Map_pointer __nstart,
567 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
568 enum { _S_initial_map_size = 8 };
573 template<
typename _Tp,
typename _Alloc>
574 _Deque_base<_Tp, _Alloc>::
575 ~_Deque_base() _GLIBCXX_NOEXCEPT
577 if (this->_M_impl._M_map)
579 _M_destroy_nodes(this->_M_impl._M_start._M_node,
580 this->_M_impl._M_finish._M_node + 1);
581 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
593 template<
typename _Tp,
typename _Alloc>
598 const size_t __num_nodes = (__num_elements / __deque_buf_size(
sizeof(_Tp))
601 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
602 size_t(__num_nodes + 2));
603 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
610 _Map_pointer __nstart = (this->_M_impl._M_map
611 + (this->_M_impl._M_map_size - __num_nodes) / 2);
612 _Map_pointer __nfinish = __nstart + __num_nodes;
615 { _M_create_nodes(__nstart, __nfinish); }
618 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
619 this->_M_impl._M_map = _Map_pointer();
620 this->_M_impl._M_map_size = 0;
621 __throw_exception_again;
624 this->_M_impl._M_start._M_set_node(__nstart);
625 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
626 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
627 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
629 % __deque_buf_size(
sizeof(_Tp)));
632 template<
typename _Tp,
typename _Alloc>
640 for (__cur = __nstart; __cur < __nfinish; ++__cur)
641 *__cur = this->_M_allocate_node();
645 _M_destroy_nodes(__nstart, __cur);
646 __throw_exception_again;
650 template<
typename _Tp,
typename _Alloc>
652 _Deque_base<_Tp, _Alloc>::
653 _M_destroy_nodes(_Map_pointer __nstart,
654 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
656 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
657 _M_deallocate_node(*__n);
744 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
747#ifdef _GLIBCXX_CONCEPT_CHECKS
749 typedef typename _Alloc::value_type _Alloc_value_type;
750# if __cplusplus < 201103L
751 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
753 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
756#if __cplusplus >= 201103L
758 "std::deque must have a non-const, non-volatile value_type");
759# if __cplusplus > 201703L || defined __STRICT_ANSI__
761 "std::deque must have the same value_type as its allocator");
766 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
768 typedef typename _Base::_Map_pointer _Map_pointer;
771 typedef _Tp value_type;
772 typedef typename _Alloc_traits::pointer pointer;
773 typedef typename _Alloc_traits::const_pointer const_pointer;
774 typedef typename _Alloc_traits::reference reference;
775 typedef typename _Alloc_traits::const_reference const_reference;
780 typedef size_t size_type;
781 typedef ptrdiff_t difference_type;
782 typedef _Alloc allocator_type;
785 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
786 {
return __deque_buf_size(
sizeof(_Tp)); }
790 using _Base::_M_create_nodes;
791 using _Base::_M_destroy_nodes;
792 using _Base::_M_allocate_node;
793 using _Base::_M_deallocate_node;
794 using _Base::_M_allocate_map;
795 using _Base::_M_deallocate_map;
796 using _Base::_M_get_Tp_allocator;
802 using _Base::_M_impl;
811#if __cplusplus >= 201103L
825#if __cplusplus >= 201103L
835 deque(size_type __n,
const allocator_type& __a = allocator_type())
836 :
_Base(__a, _S_check_init_len(__n, __a))
837 { _M_default_initialize(); }
847 deque(size_type __n,
const value_type& __value,
848 const allocator_type& __a = allocator_type())
849 :
_Base(__a, _S_check_init_len(__n, __a))
861 deque(size_type __n,
const value_type& __value = value_type(),
862 const allocator_type& __a = allocator_type())
863 : _Base(__a, _S_check_init_len(__n, __a))
877 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
878 this->_M_impl._M_start,
879 _M_get_Tp_allocator()); }
881#if __cplusplus >= 201103L
895 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
896 this->_M_impl._M_start,
897 _M_get_Tp_allocator()); }
912 if (__x.get_allocator() != __a && !__x.empty())
914 std::__uninitialized_move_a(__x.begin(), __x.end(),
915 this->_M_impl._M_start,
916 _M_get_Tp_allocator());
934 const allocator_type& __a = allocator_type())
957#if __cplusplus >= 201103L
958 template<
typename _InputIterator,
959 typename = std::_RequireInputIter<_InputIterator>>
960 deque(_InputIterator __first, _InputIterator __last,
961 const allocator_type& __a = allocator_type())
968 template<
typename _InputIterator>
969 deque(_InputIterator __first, _InputIterator __last,
970 const allocator_type& __a = allocator_type())
974 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
975 _M_initialize_dispatch(__first, __last, _Integral());
985 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
999#if __cplusplus >= 201103L
1012 _M_move_assign1(
std::move(__x), __always_equal{});
1030 _M_assign_aux(__l.begin(), __l.end(),
1047 assign(size_type __n,
const value_type& __val)
1048 { _M_fill_assign(__n, __val); }
1062#if __cplusplus >= 201103L
1063 template<
typename _InputIterator,
1064 typename = std::_RequireInputIter<_InputIterator>>
1066 assign(_InputIterator __first, _InputIterator __last)
1069 template<
typename _InputIterator>
1071 assign(_InputIterator __first, _InputIterator __last)
1073 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1074 _M_assign_dispatch(__first, __last, _Integral());
1078#if __cplusplus >= 201103L
1098 {
return _Base::get_allocator(); }
1107 {
return this->_M_impl._M_start; }
1115 {
return this->_M_impl._M_start; }
1124 {
return this->_M_impl._M_finish; }
1133 {
return this->_M_impl._M_finish; }
1149 const_reverse_iterator
1167 const_reverse_iterator
1171#if __cplusplus >= 201103L
1178 {
return this->_M_impl._M_start; }
1187 {
return this->_M_impl._M_finish; }
1194 const_reverse_iterator
1203 const_reverse_iterator
1212 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
1217 {
return _S_max_size(_M_get_Tp_allocator()); }
1219#if __cplusplus >= 201103L
1232 const size_type __len =
size();
1233 if (__new_size > __len)
1234 _M_default_append(__new_size - __len);
1235 else if (__new_size < __len)
1236 _M_erase_at_end(this->_M_impl._M_start
1237 + difference_type(__new_size));
1252 resize(size_type __new_size,
const value_type& __x)
1266 resize(size_type __new_size, value_type __x = value_type())
1269 const size_type __len =
size();
1270 if (__new_size > __len)
1271 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1272 else if (__new_size < __len)
1273 _M_erase_at_end(this->_M_impl._M_start
1274 + difference_type(__new_size));
1277#if __cplusplus >= 201103L
1281 { _M_shrink_to_fit(); }
1288 _GLIBCXX_NODISCARD
bool
1290 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1307 __glibcxx_requires_subscript(__n);
1308 return this->_M_impl._M_start[difference_type(__n)];
1325 __glibcxx_requires_subscript(__n);
1326 return this->_M_impl._M_start[difference_type(__n)];
1334 if (__n >= this->
size())
1335 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n "
1336 "(which is %zu)>= this->size() "
1357 return (*
this)[__n];
1375 return (*
this)[__n];
1385 __glibcxx_requires_nonempty();
1396 __glibcxx_requires_nonempty();
1407 __glibcxx_requires_nonempty();
1420 __glibcxx_requires_nonempty();
1439 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1441 _Alloc_traits::construct(this->_M_impl,
1442 this->_M_impl._M_start._M_cur - 1,
1444 --this->_M_impl._M_start._M_cur;
1447 _M_push_front_aux(__x);
1450#if __cplusplus >= 201103L
1455 template<
typename... _Args>
1456#if __cplusplus > 201402L
1461 emplace_front(_Args&&... __args);
1476 if (this->_M_impl._M_finish._M_cur
1477 != this->_M_impl._M_finish._M_last - 1)
1479 _Alloc_traits::construct(this->_M_impl,
1480 this->_M_impl._M_finish._M_cur, __x);
1481 ++this->_M_impl._M_finish._M_cur;
1487#if __cplusplus >= 201103L
1492 template<
typename... _Args>
1493#if __cplusplus > 201402L
1498 emplace_back(_Args&&... __args);
1512 __glibcxx_requires_nonempty();
1513 if (this->_M_impl._M_start._M_cur
1514 != this->_M_impl._M_start._M_last - 1)
1516 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1517 this->_M_impl._M_start._M_cur);
1518 ++this->_M_impl._M_start._M_cur;
1535 __glibcxx_requires_nonempty();
1536 if (this->_M_impl._M_finish._M_cur
1537 != this->_M_impl._M_finish._M_first)
1539 --this->_M_impl._M_finish._M_cur;
1540 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1541 this->_M_impl._M_finish._M_cur);
1547#if __cplusplus >= 201103L
1557 template<
typename... _Args>
1559 emplace(const_iterator __position, _Args&&... __args);
1571 insert(const_iterator __position,
const value_type& __x);
1586#if __cplusplus >= 201103L
1613 auto __offset = __p -
cbegin();
1614 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1616 return begin() + __offset;
1632 difference_type __offset = __position -
cbegin();
1633 _M_fill_insert(__position._M_const_cast(), __n, __x);
1634 return begin() + __offset;
1647 insert(
iterator __position, size_type __n,
const value_type& __x)
1648 { _M_fill_insert(__position, __n, __x); }
1651#if __cplusplus >= 201103L
1663 template<
typename _InputIterator,
1664 typename = std::_RequireInputIter<_InputIterator>>
1667 _InputIterator __last)
1669 difference_type __offset = __position -
cbegin();
1670 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1672 return begin() + __offset;
1685 template<
typename _InputIterator>
1688 _InputIterator __last)
1691 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1692 _M_insert_dispatch(__position, __first, __last, _Integral());
1710#if __cplusplus >= 201103L
1715 {
return _M_erase(__position._M_const_cast()); }
1734#if __cplusplus >= 201103L
1739 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1755#if __cplusplus >= 201103L
1756 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1757 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1759 _M_impl._M_swap_data(__x._M_impl);
1760 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1761 __x._M_get_Tp_allocator());
1772 { _M_erase_at_end(
begin()); }
1777#if __cplusplus < 201103L
1782 template<
typename _Integer>
1784 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1786 _M_initialize_map(_S_check_init_len(
static_cast<size_type
>(__n),
1787 _M_get_Tp_allocator()));
1792 template<
typename _InputIterator>
1794 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1803 _S_check_init_len(
size_t __n,
const allocator_type& __a)
1805 if (__n > _S_max_size(__a))
1806 __throw_length_error(
1807 __N(
"cannot create std::deque larger than max_size()"));
1812 _S_max_size(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1814 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1816 return (
std::min)(__diffmax, __allocmax);
1831 template<
typename _InputIterator>
1837 template<
typename _ForwardIterator>
1856#if __cplusplus >= 201103L
1859 _M_default_initialize();
1865#if __cplusplus < 201103L
1870 template<
typename _Integer>
1872 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1873 { _M_fill_assign(__n, __val); }
1876 template<
typename _InputIterator>
1878 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1884 template<
typename _InputIterator>
1886 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1890 template<
typename _ForwardIterator>
1892 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1898 _ForwardIterator __mid = __first;
1900 std::copy(__first, __mid,
begin());
1901 _M_range_insert_aux(
end(), __mid, __last,
1905 _M_erase_at_end(std::copy(__first, __last,
begin()));
1911 _M_fill_assign(size_type __n,
const value_type& __val)
1916 _M_fill_insert(
end(), __n -
size(), __val);
1920 _M_erase_at_end(
begin() + difference_type(__n));
1927#if __cplusplus < 201103L
1930 void _M_push_front_aux(
const value_type&);
1932 template<
typename... _Args>
1935 template<
typename... _Args>
1936 void _M_push_front_aux(_Args&&... __args);
1939 void _M_pop_back_aux();
1941 void _M_pop_front_aux();
1947#if __cplusplus < 201103L
1952 template<
typename _Integer>
1954 _M_insert_dispatch(iterator __pos,
1955 _Integer __n, _Integer __x, __true_type)
1956 { _M_fill_insert(__pos, __n, __x); }
1959 template<
typename _InputIterator>
1961 _M_insert_dispatch(iterator __pos,
1962 _InputIterator __first, _InputIterator __last,
1965 _M_range_insert_aux(__pos, __first, __last,
1971 template<
typename _InputIterator>
1973 _M_range_insert_aux(iterator __pos, _InputIterator __first,
1977 template<
typename _ForwardIterator>
1979 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1986 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
1989#if __cplusplus < 201103L
1991 _M_insert_aux(iterator __pos,
const value_type& __x);
1993 template<
typename... _Args>
1995 _M_insert_aux(iterator __pos, _Args&&... __args);
2000 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2003 template<
typename _ForwardIterator>
2005 _M_insert_aux(iterator __pos,
2006 _ForwardIterator __first, _ForwardIterator __last,
2013 _M_destroy_data_aux(iterator __first, iterator __last);
2017 template<
typename _Alloc1>
2019 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2020 { _M_destroy_data_aux(__first, __last); }
2023 _M_destroy_data(iterator __first, iterator __last,
2026 if (!__has_trivial_destructor(value_type))
2027 _M_destroy_data_aux(__first, __last);
2032 _M_erase_at_begin(iterator __pos)
2034 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2035 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2036 this->_M_impl._M_start = __pos;
2042 _M_erase_at_end(iterator __pos)
2044 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2045 _M_destroy_nodes(__pos._M_node + 1,
2046 this->_M_impl._M_finish._M_node + 1);
2047 this->_M_impl._M_finish = __pos;
2051 _M_erase(iterator __pos);
2054 _M_erase(iterator __first, iterator __last);
2056#if __cplusplus >= 201103L
2059 _M_default_append(size_type __n);
2070 const size_type __vacancies = this->_M_impl._M_start._M_cur
2071 - this->_M_impl._M_start._M_first;
2072 if (__n > __vacancies)
2073 _M_new_elements_at_front(__n - __vacancies);
2074 return this->_M_impl._M_start - difference_type(__n);
2078 _M_reserve_elements_at_back(size_type __n)
2080 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2081 - this->_M_impl._M_finish._M_cur) - 1;
2082 if (__n > __vacancies)
2083 _M_new_elements_at_back(__n - __vacancies);
2084 return this->_M_impl._M_finish + difference_type(__n);
2088 _M_new_elements_at_front(size_type __new_elements);
2091 _M_new_elements_at_back(size_type __new_elements);
2106 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2107 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2108 _M_reallocate_map(__nodes_to_add,
false);
2112 _M_reserve_map_at_front(size_type __nodes_to_add = 1)
2114 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2115 - this->_M_impl._M_map))
2116 _M_reallocate_map(__nodes_to_add,
true);
2120 _M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front);
2123#if __cplusplus >= 201103L
2129 this->_M_impl._M_swap_data(__x._M_impl);
2131 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2140 constexpr bool __move_storage =
2141 _Alloc_traits::_S_propagate_on_move_assign();
2142 _M_move_assign2(
std::move(__x), __bool_constant<__move_storage>());
2147 template<
typename... _Args>
2149 _M_replace_map(_Args&&... __args)
2152 deque __newobj(std::forward<_Args>(__args)...);
2155 _M_deallocate_node(*
begin()._M_node);
2156 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2157 this->_M_impl._M_map =
nullptr;
2158 this->_M_impl._M_map_size = 0;
2160 this->_M_impl._M_swap_data(__newobj._M_impl);
2168 auto __alloc = __x._M_get_Tp_allocator();
2173 _M_get_Tp_allocator() =
std::move(__alloc);
2181 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2185 _M_replace_map(
std::move(__x), __x.get_allocator());
2191 _M_assign_aux(std::make_move_iterator(__x.begin()),
2192 std::make_move_iterator(__x.end()),
2200#if __cpp_deduction_guides >= 201606
2201 template<
typename _InputIterator,
typename _ValT
2202 =
typename iterator_traits<_InputIterator>::value_type,
2203 typename _Allocator = allocator<_ValT>,
2204 typename = _RequireInputIter<_InputIterator>,
2205 typename = _RequireAllocator<_Allocator>>
2206 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2207 -> deque<_ValT, _Allocator>;
2220 template<
typename _Tp,
typename _Alloc>
2237 template<
typename _Tp,
typename _Alloc>
2240 {
return std::lexicographical_compare(__x.
begin(), __x.
end(),
2244 template<
typename _Tp,
typename _Alloc>
2247 {
return !(__x == __y); }
2250 template<
typename _Tp,
typename _Alloc>
2253 {
return __y < __x; }
2256 template<
typename _Tp,
typename _Alloc>
2259 {
return !(__y < __x); }
2262 template<
typename _Tp,
typename _Alloc>
2265 {
return !(__x < __y); }
2268 template<
typename _Tp,
typename _Alloc>
2271 _GLIBCXX_NOEXCEPT_IF(
noexcept(__x.swap(__y)))
2274#undef _GLIBCXX_DEQUE_BUF_SIZE
2276_GLIBCXX_END_NAMESPACE_CONTAINER
2278#if __cplusplus >= 201103L
2282 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2286_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.
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 &)
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
is_nothrow_default_constructible
__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.
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
void _M_fill_initialize(const value_type &__value)
Fills the deque with copies of value.
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into deque before specified iterator.
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
deque(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a deque with copies of an exemplar element.
const_reverse_iterator crbegin() const noexcept
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
reference back() noexcept
deque()=default
Creates a deque with no elements.
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
void push_back(const value_type &__x)
Add data to the end of the deque.
deque(const allocator_type &__a)
Creates a deque with no elements.
void _M_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.