57 #define _STL_DEQUE_H 1 62 #if __cplusplus >= 201103L 68 namespace std _GLIBCXX_VISIBILITY(default)
70 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
86 #ifndef _GLIBCXX_DEQUE_BUF_SIZE 87 #define _GLIBCXX_DEQUE_BUF_SIZE 512 90 _GLIBCXX_CONSTEXPR
inline size_t 91 __deque_buf_size(
size_t __size)
107 template<
typename _Tp,
typename _Ref,
typename _Ptr>
110 #if __cplusplus < 201103L 113 typedef _Tp* _Elt_pointer;
114 typedef _Tp** _Map_pointer;
117 template<
typename _Up>
119 template<
typename _CvTp>
124 typedef __ptr_to<_Tp> _Elt_pointer;
125 typedef __ptr_to<_Elt_pointer> _Map_pointer;
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() { }
152 : _M_cur(__x._M_cur), _M_first(__x._M_first),
153 _M_last(__x._M_last), _M_node(__x._M_node) { }
156 _M_const_cast()
const _GLIBCXX_NOEXCEPT
157 {
return iterator(_M_cur, _M_node); }
160 operator*()
const _GLIBCXX_NOEXCEPT
164 operator->()
const _GLIBCXX_NOEXCEPT
168 operator++() _GLIBCXX_NOEXCEPT
171 if (_M_cur == _M_last)
180 operator++(
int) _GLIBCXX_NOEXCEPT
188 operator--() _GLIBCXX_NOEXCEPT
190 if (_M_cur == _M_first)
200 operator--(
int) _GLIBCXX_NOEXCEPT
208 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
210 const difference_type __offset = __n + (_M_cur - _M_first);
211 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
215 const difference_type __node_offset =
216 __offset > 0 ? __offset / difference_type(_S_buffer_size())
217 : -difference_type((-__offset - 1)
218 / _S_buffer_size()) - 1;
220 _M_cur = _M_first + (__offset - __node_offset
221 * difference_type(_S_buffer_size()));
227 operator+(difference_type __n)
const _GLIBCXX_NOEXCEPT
234 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
235 {
return *
this += -__n; }
238 operator-(difference_type __n)
const _GLIBCXX_NOEXCEPT
245 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
246 {
return *(*
this + __n); }
256 _M_node = __new_node;
257 _M_first = *__new_node;
258 _M_last = _M_first + difference_type(_S_buffer_size());
265 template<
typename _Tp,
typename _Ref,
typename _Ptr>
269 {
return __x._M_cur == __y._M_cur; }
271 template<
typename _Tp,
typename _RefL,
typename _PtrL,
272 typename _RefR,
typename _PtrR>
276 {
return __x._M_cur == __y._M_cur; }
278 template<
typename _Tp,
typename _Ref,
typename _Ptr>
282 {
return !(__x == __y); }
284 template<
typename _Tp,
typename _RefL,
typename _PtrL,
285 typename _RefR,
typename _PtrR>
289 {
return !(__x == __y); }
291 template<
typename _Tp,
typename _Ref,
typename _Ptr>
293 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
295 {
return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
296 : (__x._M_node < __y._M_node); }
298 template<
typename _Tp,
typename _RefL,
typename _PtrL,
299 typename _RefR,
typename _PtrR>
301 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
303 {
return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
304 : (__x._M_node < __y._M_node); }
306 template<
typename _Tp,
typename _Ref,
typename _Ptr>
310 {
return __y < __x; }
312 template<
typename _Tp,
typename _RefL,
typename _PtrL,
313 typename _RefR,
typename _PtrR>
317 {
return __y < __x; }
319 template<
typename _Tp,
typename _Ref,
typename _Ptr>
321 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
323 {
return !(__y < __x); }
325 template<
typename _Tp,
typename _RefL,
typename _PtrL,
326 typename _RefR,
typename _PtrR>
328 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
330 {
return !(__y < __x); }
332 template<
typename _Tp,
typename _Ref,
typename _Ptr>
336 {
return !(__x < __y); }
338 template<
typename _Tp,
typename _RefL,
typename _PtrL,
339 typename _RefR,
typename _PtrR>
343 {
return !(__x < __y); }
349 template<
typename _Tp,
typename _Ref,
typename _Ptr>
350 inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
354 return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
356 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
357 + (__y._M_last - __y._M_cur);
360 template<
typename _Tp,
typename _RefL,
typename _PtrL,
361 typename _RefR,
typename _PtrR>
362 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
366 return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
368 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
369 + (__y._M_last - __y._M_cur);
372 template<
typename _Tp,
typename _Ref,
typename _Ptr>
376 {
return __x + __n; }
378 template<
typename _Tp>
383 template<
typename _Tp>
389 template<
typename _Tp>
398 template<
typename _Tp>
404 template<
typename _Tp>
410 const _Tp&,
const _Tp*>(__first),
412 const _Tp&,
const _Tp*>(__last),
415 #if __cplusplus >= 201103L 416 template<
typename _Tp>
422 template<
typename _Tp>
431 template<
typename _Tp>
437 template<
typename _Tp>
443 const _Tp&,
const _Tp*>(__first),
445 const _Tp&,
const _Tp*>(__last),
459 template<
typename _Tp,
typename _Alloc>
464 rebind<_Tp>::other _Tp_alloc_type;
467 #if __cplusplus < 201103L 469 typedef const _Tp* _Ptr_const;
471 typedef typename _Alloc_traits::pointer _Ptr;
472 typedef typename _Alloc_traits::const_pointer _Ptr_const;
475 typedef typename _Alloc_traits::template rebind<_Ptr>::other
480 typedef _Alloc allocator_type;
481 typedef typename _Alloc_traits::size_type size_type;
484 get_allocator()
const _GLIBCXX_NOEXCEPT
485 {
return allocator_type(_M_get_Tp_allocator()); }
492 { _M_initialize_map(0); }
496 { _M_initialize_map(__num_elements); }
498 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
500 { _M_initialize_map(__num_elements); }
506 #if __cplusplus >= 201103L 508 : _M_impl(__x._M_move_impl())
512 : _M_impl(std::move(__x._M_get_Tp_allocator()))
514 _M_initialize_map(0);
515 if (__x._M_impl._M_map)
516 this->_M_impl._M_swap_data(__x._M_impl);
526 if (__x.get_allocator() == __a)
528 if (__x._M_impl._M_map)
530 _M_initialize_map(0);
531 this->_M_impl._M_swap_data(__x._M_impl);
536 _M_initialize_map(__n);
544 typedef typename iterator::_Map_pointer _Map_pointer;
550 :
public _Tp_alloc_type
558 : _Tp_alloc_type(), _M_map(), _M_map_size(0),
559 _M_start(), _M_finish()
562 _Deque_impl(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
563 : _Tp_alloc_type(__a), _M_map(), _M_map_size(0),
564 _M_start(), _M_finish()
567 #if __cplusplus >= 201103L 568 _Deque_impl(_Deque_impl&&) =
default;
570 _Deque_impl(_Tp_alloc_type&& __a) noexcept
571 : _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0),
572 _M_start(), _M_finish()
576 void _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT
579 swap(this->_M_start, __x._M_start);
580 swap(this->_M_finish, __x._M_finish);
581 swap(this->_M_map, __x._M_map);
582 swap(this->_M_map_size, __x._M_map_size);
587 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
588 {
return *
static_cast<_Tp_alloc_type*
>(&this->_M_impl); }
590 const _Tp_alloc_type&
591 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
592 {
return *
static_cast<const _Tp_alloc_type*
>(&this->_M_impl); }
595 _M_get_map_allocator()
const _GLIBCXX_NOEXCEPT
596 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
602 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
606 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
609 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
613 _M_allocate_map(
size_t __n)
615 _Map_alloc_type __map_alloc = _M_get_map_allocator();
616 return _Map_alloc_traits::allocate(__map_alloc, __n);
620 _M_deallocate_map(_Map_pointer __p,
size_t __n) _GLIBCXX_NOEXCEPT
622 _Map_alloc_type __map_alloc = _M_get_map_allocator();
623 _Map_alloc_traits::deallocate(__map_alloc, __p, __n);
627 void _M_initialize_map(
size_t);
628 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
629 void _M_destroy_nodes(_Map_pointer __nstart,
630 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
631 enum { _S_initial_map_size = 8 };
635 #if __cplusplus >= 201103L 641 return std::move(_M_impl);
644 _Tp_alloc_type __alloc{_M_get_Tp_allocator()};
646 _Tp_alloc_type __sink __attribute((__unused__)) {std::move(__alloc)};
651 _Deque_impl __ret{std::move(_M_get_Tp_allocator())};
652 _M_impl._M_swap_data(__ret);
653 _M_impl._M_swap_data(__empty._M_impl);
659 template<
typename _Tp,
typename _Alloc>
663 if (this->_M_impl._M_map)
665 _M_destroy_nodes(this->_M_impl._M_start._M_node,
666 this->_M_impl._M_finish._M_node + 1);
667 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
679 template<
typename _Tp,
typename _Alloc>
684 const size_t __num_nodes = (__num_elements/ __deque_buf_size(
sizeof(_Tp))
687 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
688 size_t(__num_nodes + 2));
689 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
696 _Map_pointer __nstart = (this->_M_impl._M_map
697 + (this->_M_impl._M_map_size - __num_nodes) / 2);
698 _Map_pointer __nfinish = __nstart + __num_nodes;
701 { _M_create_nodes(__nstart, __nfinish); }
704 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
705 this->_M_impl._M_map = _Map_pointer();
706 this->_M_impl._M_map_size = 0;
707 __throw_exception_again;
710 this->_M_impl._M_start._M_set_node(__nstart);
711 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
712 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
713 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
715 % __deque_buf_size(
sizeof(_Tp)));
718 template<
typename _Tp,
typename _Alloc>
726 for (__cur = __nstart; __cur < __nfinish; ++__cur)
727 *__cur = this->_M_allocate_node();
731 _M_destroy_nodes(__nstart, __cur);
732 __throw_exception_again;
736 template<
typename _Tp,
typename _Alloc>
740 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
742 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
743 _M_deallocate_node(*__n);
830 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
833 #ifdef _GLIBCXX_CONCEPT_CHECKS 835 typedef typename _Alloc::value_type _Alloc_value_type;
836 # if __cplusplus < 201103L 837 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
839 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
843 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
845 typedef typename _Base::_Map_pointer _Map_pointer;
848 typedef _Tp value_type;
849 typedef typename _Alloc_traits::pointer pointer;
850 typedef typename _Alloc_traits::const_pointer const_pointer;
851 typedef typename _Alloc_traits::reference reference;
852 typedef typename _Alloc_traits::const_reference const_reference;
857 typedef size_t size_type;
858 typedef ptrdiff_t difference_type;
859 typedef _Alloc allocator_type;
862 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
863 {
return __deque_buf_size(
sizeof(_Tp)); }
866 using _Base::_M_initialize_map;
867 using _Base::_M_create_nodes;
868 using _Base::_M_destroy_nodes;
869 using _Base::_M_allocate_node;
870 using _Base::_M_deallocate_node;
871 using _Base::_M_allocate_map;
872 using _Base::_M_deallocate_map;
873 using _Base::_M_get_Tp_allocator;
879 using _Base::_M_impl;
898 #if __cplusplus >= 201103L 908 deque(size_type __n,
const allocator_type& __a = allocator_type())
910 { _M_default_initialize(); }
920 deque(size_type __n,
const value_type& __value,
921 const allocator_type& __a = allocator_type())
923 { _M_fill_initialize(__value); }
934 deque(size_type __n,
const value_type& __value = value_type(),
935 const allocator_type& __a = allocator_type())
937 { _M_fill_initialize(__value); }
948 : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),
950 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
951 this->_M_impl._M_start,
952 _M_get_Tp_allocator()); }
954 #if __cplusplus >= 201103L 963 : _Base(
std::move(__x)) { }
967 : _Base(__a, __x.size())
968 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
969 this->_M_impl._M_start,
970 _M_get_Tp_allocator()); }
974 : _Base(
std::move(__x), __a, __x.size())
976 if (__x.get_allocator() != __a)
978 std::__uninitialized_move_a(__x.begin(), __x.end(),
979 this->_M_impl._M_start,
980 _M_get_Tp_allocator());
997 const allocator_type& __a = allocator_type())
1000 _M_range_initialize(__l.begin(), __l.end(),
1020 #if __cplusplus >= 201103L 1021 template<
typename _InputIterator,
1022 typename = std::_RequireInputIter<_InputIterator>>
1023 deque(_InputIterator __first, _InputIterator __last,
1024 const allocator_type& __a = allocator_type())
1026 { _M_initialize_dispatch(__first, __last, __false_type()); }
1028 template<
typename _InputIterator>
1029 deque(_InputIterator __first, _InputIterator __last,
1030 const allocator_type& __a = allocator_type())
1034 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1035 _M_initialize_dispatch(__first, __last, _Integral());
1045 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
1057 operator=(
const deque& __x);
1059 #if __cplusplus >= 201103L 1072 _M_move_assign1(std::move(__x), __always_equal{});
1090 _M_assign_aux(__l.begin(), __l.end(),
1107 assign(size_type __n,
const value_type& __val)
1108 { _M_fill_assign(__n, __val); }
1122 #if __cplusplus >= 201103L 1123 template<
typename _InputIterator,
1124 typename = std::_RequireInputIter<_InputIterator>>
1126 assign(_InputIterator __first, _InputIterator __last)
1127 { _M_assign_dispatch(__first, __last, __false_type()); }
1129 template<
typename _InputIterator>
1131 assign(_InputIterator __first, _InputIterator __last)
1133 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1134 _M_assign_dispatch(__first, __last, _Integral());
1138 #if __cplusplus >= 201103L 1158 {
return _Base::get_allocator(); }
1167 {
return this->_M_impl._M_start; }
1175 {
return this->_M_impl._M_start; }
1184 {
return this->_M_impl._M_finish; }
1193 {
return this->_M_impl._M_finish; }
1202 {
return reverse_iterator(this->_M_impl._M_finish); }
1209 const_reverse_iterator
1211 {
return const_reverse_iterator(this->_M_impl._M_finish); }
1220 {
return reverse_iterator(this->_M_impl._M_start); }
1227 const_reverse_iterator
1229 {
return const_reverse_iterator(this->_M_impl._M_start); }
1231 #if __cplusplus >= 201103L 1238 {
return this->_M_impl._M_start; }
1247 {
return this->_M_impl._M_finish; }
1254 const_reverse_iterator
1256 {
return const_reverse_iterator(this->_M_impl._M_finish); }
1263 const_reverse_iterator
1265 {
return const_reverse_iterator(this->_M_impl._M_start); }
1272 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
1277 {
return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
1279 #if __cplusplus >= 201103L 1292 const size_type __len = size();
1293 if (__new_size > __len)
1294 _M_default_append(__new_size - __len);
1295 else if (__new_size < __len)
1296 _M_erase_at_end(this->_M_impl._M_start
1297 + difference_type(__new_size));
1312 resize(size_type __new_size,
const value_type& __x)
1314 const size_type __len = size();
1315 if (__new_size > __len)
1316 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1317 else if (__new_size < __len)
1318 _M_erase_at_end(this->_M_impl._M_start
1319 + difference_type(__new_size));
1334 resize(size_type __new_size, value_type __x = value_type())
1336 const size_type __len = size();
1337 if (__new_size > __len)
1338 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1339 else if (__new_size < __len)
1340 _M_erase_at_end(this->_M_impl._M_start
1341 + difference_type(__new_size));
1345 #if __cplusplus >= 201103L 1349 { _M_shrink_to_fit(); }
1358 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1375 __glibcxx_requires_subscript(__n);
1376 return this->_M_impl._M_start[difference_type(__n)];
1393 __glibcxx_requires_subscript(__n);
1394 return this->_M_impl._M_start[difference_type(__n)];
1402 if (__n >= this->size())
1403 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n " 1404 "(which is %zu)>= this->size() " 1424 _M_range_check(__n);
1425 return (*
this)[__n];
1442 _M_range_check(__n);
1443 return (*
this)[__n];
1453 __glibcxx_requires_nonempty();
1464 __glibcxx_requires_nonempty();
1475 __glibcxx_requires_nonempty();
1476 iterator __tmp =
end();
1488 __glibcxx_requires_nonempty();
1489 const_iterator __tmp =
end();
1507 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1509 _Alloc_traits::construct(this->_M_impl,
1510 this->_M_impl._M_start._M_cur - 1,
1512 --this->_M_impl._M_start._M_cur;
1515 _M_push_front_aux(__x);
1518 #if __cplusplus >= 201103L 1520 push_front(value_type&& __x)
1521 { emplace_front(std::move(__x)); }
1523 template<
typename... _Args>
1524 #if __cplusplus > 201402L 1529 emplace_front(_Args&&... __args);
1544 if (this->_M_impl._M_finish._M_cur
1545 != this->_M_impl._M_finish._M_last - 1)
1547 _Alloc_traits::construct(this->_M_impl,
1548 this->_M_impl._M_finish._M_cur, __x);
1549 ++this->_M_impl._M_finish._M_cur;
1552 _M_push_back_aux(__x);
1555 #if __cplusplus >= 201103L 1557 push_back(value_type&& __x)
1558 { emplace_back(std::move(__x)); }
1560 template<
typename... _Args>
1561 #if __cplusplus > 201402L 1566 emplace_back(_Args&&... __args);
1580 __glibcxx_requires_nonempty();
1581 if (this->_M_impl._M_start._M_cur
1582 != this->_M_impl._M_start._M_last - 1)
1584 _Alloc_traits::destroy(this->_M_impl,
1585 this->_M_impl._M_start._M_cur);
1586 ++this->_M_impl._M_start._M_cur;
1603 __glibcxx_requires_nonempty();
1604 if (this->_M_impl._M_finish._M_cur
1605 != this->_M_impl._M_finish._M_first)
1607 --this->_M_impl._M_finish._M_cur;
1608 _Alloc_traits::destroy(this->_M_impl,
1609 this->_M_impl._M_finish._M_cur);
1615 #if __cplusplus >= 201103L 1625 template<
typename... _Args>
1627 emplace(const_iterator __position, _Args&&... __args);
1639 insert(const_iterator __position,
const value_type& __x);
1651 insert(iterator __position,
const value_type& __x);
1654 #if __cplusplus >= 201103L 1665 insert(const_iterator __position, value_type&& __x)
1666 {
return emplace(__position, std::move(__x)); }
1680 auto __offset = __p -
cbegin();
1681 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1683 return begin() + __offset;
1687 #if __cplusplus >= 201103L 1699 insert(const_iterator __position, size_type __n,
const value_type& __x)
1701 difference_type __offset = __position -
cbegin();
1702 _M_fill_insert(__position._M_const_cast(), __n, __x);
1703 return begin() + __offset;
1716 insert(iterator __position, size_type __n,
const value_type& __x)
1717 { _M_fill_insert(__position, __n, __x); }
1720 #if __cplusplus >= 201103L 1732 template<
typename _InputIterator,
1733 typename = std::_RequireInputIter<_InputIterator>>
1735 insert(const_iterator __position, _InputIterator __first,
1736 _InputIterator __last)
1738 difference_type __offset = __position -
cbegin();
1739 _M_insert_dispatch(__position._M_const_cast(),
1740 __first, __last, __false_type());
1741 return begin() + __offset;
1754 template<
typename _InputIterator>
1756 insert(iterator __position, _InputIterator __first,
1757 _InputIterator __last)
1760 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1761 _M_insert_dispatch(__position, __first, __last, _Integral());
1779 #if __cplusplus >= 201103L 1782 erase(iterator __position)
1784 {
return _M_erase(__position._M_const_cast()); }
1803 #if __cplusplus >= 201103L 1804 erase(const_iterator __first, const_iterator __last)
1806 erase(iterator __first, iterator __last)
1808 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1824 #if __cplusplus >= 201103L 1825 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1826 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1828 _M_impl._M_swap_data(__x._M_impl);
1829 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1830 __x._M_get_Tp_allocator());
1841 { _M_erase_at_end(
begin()); }
1850 template<
typename _Integer>
1852 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1854 _M_initialize_map(static_cast<size_type>(__n));
1855 _M_fill_initialize(__x);
1859 template<
typename _InputIterator>
1861 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1864 _M_range_initialize(__first, __last,
1880 template<
typename _InputIterator>
1882 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1886 template<
typename _ForwardIterator>
1888 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1903 _M_fill_initialize(
const value_type& __value);
1905 #if __cplusplus >= 201103L 1908 _M_default_initialize();
1918 template<
typename _Integer>
1920 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1921 { _M_fill_assign(__n, __val); }
1924 template<
typename _InputIterator>
1926 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1931 template<
typename _InputIterator>
1933 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1937 template<
typename _ForwardIterator>
1939 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1945 _ForwardIterator __mid = __first;
1947 std::copy(__first, __mid,
begin());
1948 _M_range_insert_aux(
end(), __mid, __last,
1952 _M_erase_at_end(std::copy(__first, __last,
begin()));
1958 _M_fill_assign(size_type __n,
const value_type& __val)
1963 _M_fill_insert(
end(), __n - size(), __val);
1967 _M_erase_at_end(
begin() + difference_type(__n));
1974 #if __cplusplus < 201103L 1975 void _M_push_back_aux(
const value_type&);
1977 void _M_push_front_aux(
const value_type&);
1979 template<
typename... _Args>
1980 void _M_push_back_aux(_Args&&... __args);
1982 template<
typename... _Args>
1983 void _M_push_front_aux(_Args&&... __args);
1986 void _M_pop_back_aux();
1988 void _M_pop_front_aux();
1998 template<
typename _Integer>
2000 _M_insert_dispatch(iterator __pos,
2001 _Integer __n, _Integer __x, __true_type)
2002 { _M_fill_insert(__pos, __n, __x); }
2005 template<
typename _InputIterator>
2007 _M_insert_dispatch(iterator __pos,
2008 _InputIterator __first, _InputIterator __last,
2011 _M_range_insert_aux(__pos, __first, __last,
2016 template<
typename _InputIterator>
2018 _M_range_insert_aux(iterator __pos, _InputIterator __first,
2022 template<
typename _ForwardIterator>
2024 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2031 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
2034 #if __cplusplus < 201103L 2036 _M_insert_aux(iterator __pos,
const value_type& __x);
2038 template<
typename... _Args>
2040 _M_insert_aux(iterator __pos, _Args&&... __args);
2045 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2048 template<
typename _ForwardIterator>
2050 _M_insert_aux(iterator __pos,
2051 _ForwardIterator __first, _ForwardIterator __last,
2058 _M_destroy_data_aux(iterator __first, iterator __last);
2062 template<
typename _Alloc1>
2064 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2065 { _M_destroy_data_aux(__first, __last); }
2068 _M_destroy_data(iterator __first, iterator __last,
2071 if (!__has_trivial_destructor(value_type))
2072 _M_destroy_data_aux(__first, __last);
2077 _M_erase_at_begin(iterator __pos)
2079 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2080 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2081 this->_M_impl._M_start = __pos;
2087 _M_erase_at_end(iterator __pos)
2089 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2090 _M_destroy_nodes(__pos._M_node + 1,
2091 this->_M_impl._M_finish._M_node + 1);
2092 this->_M_impl._M_finish = __pos;
2096 _M_erase(iterator __pos);
2099 _M_erase(iterator __first, iterator __last);
2101 #if __cplusplus >= 201103L 2104 _M_default_append(size_type __n);
2115 const size_type __vacancies = this->_M_impl._M_start._M_cur
2116 - this->_M_impl._M_start._M_first;
2117 if (__n > __vacancies)
2118 _M_new_elements_at_front(__n - __vacancies);
2119 return this->_M_impl._M_start - difference_type(__n);
2125 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2126 - this->_M_impl._M_finish._M_cur) - 1;
2127 if (__n > __vacancies)
2128 _M_new_elements_at_back(__n - __vacancies);
2129 return this->_M_impl._M_finish + difference_type(__n);
2133 _M_new_elements_at_front(size_type __new_elements);
2136 _M_new_elements_at_back(size_type __new_elements);
2151 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2152 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2153 _M_reallocate_map(__nodes_to_add,
false);
2159 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2160 - this->_M_impl._M_map))
2161 _M_reallocate_map(__nodes_to_add,
true);
2165 _M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front);
2168 #if __cplusplus >= 201103L 2174 this->_M_impl._M_swap_data(__x._M_impl);
2176 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2185 constexpr
bool __move_storage =
2186 _Alloc_traits::_S_propagate_on_move_assign();
2192 template<
typename... _Args>
2194 _M_replace_map(_Args&&... __args)
2197 deque __newobj(std::forward<_Args>(__args)...);
2200 _M_deallocate_node(*
begin()._M_node);
2201 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2202 this->_M_impl._M_map =
nullptr;
2203 this->_M_impl._M_map_size = 0;
2205 this->_M_impl._M_swap_data(__newobj._M_impl);
2213 auto __alloc = __x._M_get_Tp_allocator();
2216 _M_replace_map(std::move(__x));
2218 _M_get_Tp_allocator() = std::move(__alloc);
2226 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2230 _M_replace_map(std::move(__x), __x.get_allocator());
2236 _M_assign_aux(std::__make_move_if_noexcept_iterator(__x.begin()),
2237 std::__make_move_if_noexcept_iterator(__x.end()),
2256 template<
typename _Tp,
typename _Alloc>
2274 template<
typename _Tp,
typename _Alloc>
2276 operator<(const deque<_Tp, _Alloc>& __x,
2279 __y.begin(), __y.end()); }
2282 template<
typename _Tp,
typename _Alloc>
2286 {
return !(__x == __y); }
2289 template<
typename _Tp,
typename _Alloc>
2293 {
return __y < __x; }
2296 template<
typename _Tp,
typename _Alloc>
2298 operator<=(const deque<_Tp, _Alloc>& __x,
2300 {
return !(__y < __x); }
2303 template<
typename _Tp,
typename _Alloc>
2307 {
return !(__x < __y); }
2310 template<
typename _Tp,
typename _Alloc>
2313 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2316 #undef _GLIBCXX_DEQUE_BUF_SIZE 2318 _GLIBCXX_END_NAMESPACE_CONTAINER
void pop_back() noexcept
Removes last element.
deque(const deque &__x, const allocator_type &__a)
Copy constructor with alternative allocator.
reverse_iterator rend() noexcept
const_reference at(size_type __n) const
Provides access to the data contained in the deque.
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
The standard allocator, as per [20.4].
void _M_range_check(size_type __n) const
Safety check used only from at().
void _M_initialize_map(size_t)
Layout storage.
const_reverse_iterator rbegin() const noexcept
Uniform interface to C++98 and C++11 allocators.
Uniform interface to all pointer-like types.
reference front() noexcept
void swap(deque &__x) noexcept
Swaps data with another deque.
deque(const deque &__x)
Deque copy constructor.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
const_reverse_iterator rend() const noexcept
const_iterator cend() const noexcept
void resize(size_type __new_size)
Resizes the deque to the specified number of elements.
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
deque(deque &&__x)
Deque move constructor.
deque(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a deque with copies of an exemplar element.
void push_front(const value_type &__x)
Add data to the front of the deque.
iterator begin() noexcept
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
const_reference back() const noexcept
void resize(size_type __new_size, const value_type &__x)
Resizes the deque to the specified number of elements.
const_reference front() const noexcept
ISO C++ entities toplevel namespace is std.
reverse_iterator rbegin() noexcept
const_iterator begin() const noexcept
void assign(size_type __n, const value_type &__val)
Assigns a given value to a deque.
void push_back(const value_type &__x)
Add data to the end of the deque.
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
__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.
bool equal(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
Tests a range for element-wise equality.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
bool empty() const noexcept
reference back() noexcept
iterator _M_reserve_elements_at_front(size_type __n)
Memory-handling helpers for the previous internal insert functions.
void pop_front() noexcept
Removes first element.
void _M_set_node(_Map_pointer __new_node) noexcept
const_reverse_iterator crend() const noexcept
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
deque(deque &&__x, const allocator_type &__a)
Move constructor with alternative allocator.
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the deque.
deque()
Creates a deque with no elements.
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
iterator erase(const_iterator __position)
Remove element at given position.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
size_type max_size() const noexcept
reference at(size_type __n)
Provides access to the data contained in the deque.
iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the deque.
void shrink_to_fit() noexcept
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
Forward iterators support a superset of input iterator operations.
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
const_iterator end() const noexcept
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
const_reverse_iterator crbegin() const noexcept
deque(const allocator_type &__a)
Creates a deque with no elements.
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
Random-access iterators support a superset of bidirectional iterator operations.
deque(size_type __n, const allocator_type &__a=allocator_type())
Creates a deque with default constructed elements.
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the deque.
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
const_iterator cbegin() const noexcept
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
size_type size() const noexcept