61namespace std _GLIBCXX_VISIBILITY(default)
63_GLIBCXX_BEGIN_NAMESPACE_VERSION
64_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
66#if __cplusplus >= 201103L
67 template <
typename _Tp,
typename _Alloc>
70 _M_default_initialize()
75 for (__cur = this->_M_impl._M_start._M_node;
76 __cur < this->_M_impl._M_finish._M_node;
79 _M_get_Tp_allocator());
81 this->_M_impl._M_finish._M_cur,
82 _M_get_Tp_allocator());
86 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
87 _M_get_Tp_allocator());
88 __throw_exception_again;
93 template <
typename _Tp,
typename _Alloc>
100#if __cplusplus >= 201103L
101 if (_Alloc_traits::_S_propagate_on_copy_assign())
103 if (!_Alloc_traits::_S_always_equal()
104 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
110 __x._M_get_Tp_allocator());
114 __x._M_get_Tp_allocator());
119 _M_erase_at_end(std::copy(__x.
begin(), __x.
end(),
120 this->_M_impl._M_start));
125 _M_range_insert_aux(this->_M_impl._M_finish,
__mid, __x.
end(),
132#if __cplusplus >= 201103L
133 template<
typename _Tp,
typename _Alloc>
134 template<
typename...
_Args>
135#if __cplusplus > 201402L
136 typename deque<_Tp, _Alloc>::reference
143 if (this->_M_impl._M_start._M_cur !=
this->_M_impl._M_start._M_first)
145 _Alloc_traits::construct(this->_M_impl,
146 this->_M_impl._M_start._M_cur - 1,
148 --this->_M_impl._M_start._M_cur;
152#if __cplusplus > 201402L
157 template<
typename _Tp,
typename _Alloc>
158 template<
typename... _Args>
159#if __cplusplus > 201402L
160 typename deque<_Tp, _Alloc>::reference
165 emplace_back(_Args&&... __args)
167 if (this->_M_impl._M_finish._M_cur
168 != this->_M_impl._M_finish._M_last - 1)
170 _Alloc_traits::construct(this->_M_impl,
171 this->_M_impl._M_finish._M_cur,
173 ++this->_M_impl._M_finish._M_cur;
177#if __cplusplus > 201402L
183#if __cplusplus >= 201103L
184 template<
typename _Tp,
typename _Alloc>
185 template<
typename... _Args>
186 typename deque<_Tp, _Alloc>::iterator
193 return this->_M_impl._M_start;
203 return _M_emplace_aux(
__position._M_const_cast(),
208 template <
typename _Tp,
typename _Alloc>
211#if __cplusplus >= 201103L
220 return this->_M_impl._M_start;
230 return _M_insert_aux(
__position._M_const_cast(), __x);
233 template <
typename _Tp,
typename _Alloc>
241 if (
static_cast<size_type
>(
__index) < (
size() >> 1))
250 _GLIBCXX_MOVE3(__next,
end(), __position);
253 return begin() + __index;
256 template <
typename _Tp,
typename _Alloc>
257 typename deque<_Tp, _Alloc>::iterator
259 _M_erase(iterator __first, iterator __last)
261 if (__first == __last)
263 else if (__first ==
begin() && __last ==
end())
270 const difference_type __n = __last - __first;
271 const difference_type __elems_before = __first -
begin();
272 if (
static_cast<size_type
>(__elems_before) <= (
size() - __n) / 2)
274 if (__first !=
begin())
275 _GLIBCXX_MOVE_BACKWARD3(
begin(), __first, __last);
276 _M_erase_at_begin(
begin() + __n);
281 _GLIBCXX_MOVE3(__last,
end(), __first);
282 _M_erase_at_end(
end() - __n);
284 return begin() + __elems_before;
288 template <
typename _Tp,
class _Alloc>
289 template <
typename _InputIterator>
292 _M_assign_aux(_InputIterator __first, _InputIterator __last,
295 iterator __cur =
begin();
296 for (; __first != __last && __cur !=
end(); ++__cur, (void)++__first)
298 if (__first == __last)
299 _M_erase_at_end(__cur);
301 _M_range_insert_aux(
end(), __first, __last,
305 template <
typename _Tp,
typename _Alloc>
308 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x)
310 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
312 iterator __new_start = _M_reserve_elements_at_front(__n);
316 __x, _M_get_Tp_allocator());
317 this->_M_impl._M_start = __new_start;
321 _M_destroy_nodes(__new_start._M_node,
322 this->_M_impl._M_start._M_node);
323 __throw_exception_again;
326 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
328 iterator __new_finish = _M_reserve_elements_at_back(__n);
333 _M_get_Tp_allocator());
334 this->_M_impl._M_finish = __new_finish;
338 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
339 __new_finish._M_node + 1);
340 __throw_exception_again;
344 _M_insert_aux(__pos, __n, __x);
347#if __cplusplus >= 201103L
348 template <
typename _Tp,
typename _Alloc>
351 _M_default_append(size_type __n)
355 iterator __new_finish = _M_reserve_elements_at_back(__n);
360 _M_get_Tp_allocator());
361 this->_M_impl._M_finish = __new_finish;
365 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
366 __new_finish._M_node + 1);
367 __throw_exception_again;
372 template <
typename _Tp,
typename _Alloc>
377 const difference_type __front_capacity
378 = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
379 if (__front_capacity == 0)
382 const difference_type __back_capacity
383 = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
384 if (__front_capacity + __back_capacity < _S_buffer_size())
391 template <
typename _Tp,
typename _Alloc>
399 for (
__cur = this->_M_impl._M_start._M_node;
400 __cur < this->_M_impl._M_finish._M_node;
403 __value, _M_get_Tp_allocator());
405 this->_M_impl._M_finish._M_cur,
406 __value, _M_get_Tp_allocator());
411 _M_get_Tp_allocator());
412 __throw_exception_again;
416 template <
typename _Tp,
typename _Alloc>
417 template <
typename _InputIterator>
423 this->_M_initialize_map(0);
426 for (; __first != __last; ++__first)
428 emplace_back(*__first);
436 __throw_exception_again;
440 template <
typename _Tp,
typename _Alloc>
441 template <
typename _ForwardIterator>
448 this->_M_initialize_map(_S_check_init_len(__n, _M_get_Tp_allocator()));
453 for (
__cur_node = this->_M_impl._M_start._M_node;
457 if (__n < _S_buffer_size())
463 _M_get_Tp_allocator());
467 this->_M_impl._M_finish._M_first,
468 _M_get_Tp_allocator());
474 _M_get_Tp_allocator());
475 __throw_exception_again;
480 template<
typename _Tp,
typename _Alloc>
481#if __cplusplus >= 201103L
482 template<
typename...
_Args>
492 if (
size() == max_size())
493 __throw_length_error(
494 __N(
"cannot create std::deque larger than max_size()"));
496 _M_reserve_map_at_back();
497 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
500#if __cplusplus >= 201103L
501 _Alloc_traits::construct(this->_M_impl,
502 this->_M_impl._M_finish._M_cur,
505 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
507 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
509 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
513 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
514 __throw_exception_again;
519 template<
typename _Tp,
typename _Alloc>
520#if __cplusplus >= 201103L
521 template<
typename...
_Args>
531 if (
size() == max_size())
532 __throw_length_error(
533 __N(
"cannot create std::deque larger than max_size()"));
535 _M_reserve_map_at_front();
536 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
539 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
541 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
542#if __cplusplus >= 201103L
543 _Alloc_traits::construct(this->_M_impl,
544 this->_M_impl._M_start._M_cur,
547 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
552 ++this->_M_impl._M_start;
553 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
554 __throw_exception_again;
559 template <
typename _Tp,
typename _Alloc>
563 _M_deallocate_node(this->_M_impl._M_finish._M_first);
564 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
565 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
566 _Alloc_traits::destroy(_M_get_Tp_allocator(),
567 this->_M_impl._M_finish._M_cur);
575 template <
typename _Tp,
typename _Alloc>
579 _Alloc_traits::destroy(_M_get_Tp_allocator(),
580 this->_M_impl._M_start._M_cur);
581 _M_deallocate_node(this->_M_impl._M_start._M_first);
582 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
583 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
586 template <
typename _Tp,
typename _Alloc>
587 template <
typename _InputIterator,
typename _Sentinel>
602 _M_destroy_nodes(__new_start._M_node,
603 this->_M_impl._M_start._M_node);
604 __throw_exception_again;
608 template <
typename _Tp,
typename _Alloc>
609 template <
typename _InputIterator,
typename _Sentinel>
612 _M_range_append(_InputIterator __first, _Sentinel __last,
615 iterator __new_finish = _M_reserve_elements_at_back(__n);
619 this->_M_impl._M_finish,
620 _M_get_Tp_allocator());
621 this->_M_impl._M_finish = __new_finish;
625 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
626 __new_finish._M_node + 1);
627 __throw_exception_again;
631 template <
typename _Tp,
typename _Alloc>
632 template <
typename _InputIterator>
635 _M_range_insert_aux(iterator __pos,
636 _InputIterator __first, _InputIterator __last,
640 template <
typename _Tp,
typename _Alloc>
641 template <
typename _ForwardIterator>
644 _M_range_insert_aux(iterator __pos,
645 _ForwardIterator __first, _ForwardIterator __last,
649 if (__builtin_expect(__n == 0, 0))
652 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
653 _M_range_prepend(__first, __last, __n);
654 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
655 _M_range_append(__first, __last, __n);
657 _M_insert_aux(__pos, __first, __last, __n);
660 template<
typename _Tp,
typename _Alloc>
661#if __cplusplus >= 201103L
662 template<
typename... _Args>
663 typename deque<_Tp, _Alloc>::iterator
665 _M_emplace_aux(iterator __pos, _Args&&... __args)
669 typename deque<_Tp, _Alloc>::iterator
671 _M_insert_aux(iterator __pos,
const value_type& __x)
673 value_type __x_copy = __x;
675 difference_type __index = __pos - this->_M_impl._M_start;
676 if (
static_cast<size_type
>(__index) <
size() / 2)
678 push_front(_GLIBCXX_MOVE(front()));
679 iterator __front1 = this->_M_impl._M_start;
681 iterator __front2 = __front1;
683 __pos = this->_M_impl._M_start + __index;
684 iterator __pos1 = __pos;
686 _GLIBCXX_MOVE3(__front2, __pos1, __front1);
690 push_back(_GLIBCXX_MOVE(back()));
691 iterator __back1 = this->_M_impl._M_finish;
693 iterator __back2 = __back1;
695 __pos = this->_M_impl._M_start + __index;
696 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
698 *__pos = _GLIBCXX_MOVE(__x_copy);
702 template <
typename _Tp,
typename _Alloc>
705 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x)
707 const difference_type __elems_before = __pos - this->_M_impl._M_start;
708 const size_type __length = this->
size();
709 value_type __x_copy = __x;
710 if (__elems_before < difference_type(__length / 2))
712 iterator __new_start = _M_reserve_elements_at_front(__n);
713 iterator __old_start = this->_M_impl._M_start;
714 __pos = this->_M_impl._M_start + __elems_before;
717 if (__elems_before >= difference_type(__n))
719 iterator __start_n = (this->_M_impl._M_start
720 + difference_type(__n));
722 __start_n, __new_start,
723 _M_get_Tp_allocator());
724 this->_M_impl._M_start = __new_start;
725 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
726 std::fill(__pos - difference_type(__n), __pos, __x_copy);
732 this->_M_impl._M_start,
734 _M_get_Tp_allocator());
735 this->_M_impl._M_start = __new_start;
736 std::fill(__old_start, __pos, __x_copy);
741 _M_destroy_nodes(__new_start._M_node,
742 this->_M_impl._M_start._M_node);
743 __throw_exception_again;
748 iterator __new_finish = _M_reserve_elements_at_back(__n);
749 iterator __old_finish = this->_M_impl._M_finish;
750 const difference_type __elems_after =
751 difference_type(__length) - __elems_before;
752 __pos = this->_M_impl._M_finish - __elems_after;
755 if (__elems_after > difference_type(__n))
757 iterator __finish_n = (this->_M_impl._M_finish
758 - difference_type(__n));
760 this->_M_impl._M_finish,
761 this->_M_impl._M_finish,
762 _M_get_Tp_allocator());
763 this->_M_impl._M_finish = __new_finish;
764 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
765 std::fill(__pos, __pos + difference_type(__n), __x_copy);
770 __pos + difference_type(__n),
772 this->_M_impl._M_finish,
773 _M_get_Tp_allocator());
774 this->_M_impl._M_finish = __new_finish;
775 std::fill(__pos, __old_finish, __x_copy);
780 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
781 __new_finish._M_node + 1);
782 __throw_exception_again;
787 template <
typename _Tp,
typename _Alloc>
788 template <
typename _ForwardIterator>
791 _M_insert_aux(iterator __pos,
792 _ForwardIterator __first, _ForwardIterator __last,
795 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
796 const size_type __length =
size();
797 if (
static_cast<size_type
>(__elemsbefore) < __length / 2)
799 iterator __new_start = _M_reserve_elements_at_front(__n);
800 iterator __old_start = this->_M_impl._M_start;
801 __pos = this->_M_impl._M_start + __elemsbefore;
804 if (__elemsbefore >= difference_type(__n))
806 iterator __start_n = (this->_M_impl._M_start
807 + difference_type(__n));
809 __start_n, __new_start,
810 _M_get_Tp_allocator());
811 this->_M_impl._M_start = __new_start;
812 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
813 std::copy(__first, __last, __pos - difference_type(__n));
817 _ForwardIterator __mid = __first;
818 std::advance(__mid, difference_type(__n) - __elemsbefore);
820 __pos, __first, __mid,
822 _M_get_Tp_allocator());
823 this->_M_impl._M_start = __new_start;
824 std::copy(__mid, __last, __old_start);
829 _M_destroy_nodes(__new_start._M_node,
830 this->_M_impl._M_start._M_node);
831 __throw_exception_again;
836 iterator __new_finish = _M_reserve_elements_at_back(__n);
837 iterator __old_finish = this->_M_impl._M_finish;
838 const difference_type __elemsafter =
839 difference_type(__length) - __elemsbefore;
840 __pos = this->_M_impl._M_finish - __elemsafter;
843 if (__elemsafter > difference_type(__n))
845 iterator __finish_n = (this->_M_impl._M_finish
846 - difference_type(__n));
848 this->_M_impl._M_finish,
849 this->_M_impl._M_finish,
850 _M_get_Tp_allocator());
851 this->_M_impl._M_finish = __new_finish;
852 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
853 std::copy(__first, __last, __pos);
857 _ForwardIterator __mid = __first;
860 this->_M_impl._M_finish,
861 this->_M_impl._M_finish,
862 _M_get_Tp_allocator());
863 this->_M_impl._M_finish = __new_finish;
864 std::copy(__first, __mid, __pos);
869 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
870 __new_finish._M_node + 1);
871 __throw_exception_again;
876#if __glibcxx_containers_ranges
877 template<ranges::forward_range _Rg>
878 auto __advance_dist(_Rg& __rg)
882 ranges::iterator_t<_Rg> __last;
883 ranges::range_difference_t<_Rg> __size;
885 if constexpr (ranges::common_range<_Rg>)
886 return _Res{ranges::end(__rg), ranges::distance(__rg)};
887 else if constexpr (ranges::sized_range<_Rg>)
889 auto const __n = ranges::distance(__rg);
890 auto __it = ranges::begin(__rg);
891 if constexpr (ranges::random_access_range<_Rg>)
894 ranges::advance(__it, ranges::end(__rg));
895 return _Res{__it, __n};
899 auto __it = ranges::begin(__rg);
900 auto const __last = ranges::end(__rg);
901 ranges::range_difference_t<_Rg> __n(0);
902 for (; __it != __last; ++__it)
904 return _Res{__it, __n};
908 template<
typename _Tp,
typename _Alloc>
909 template<__detail::__container_compatible_range<_Tp> _Rg>
912 insert_range(const_iterator __pos, _Rg&& __rg)
917 const auto __ins_idx =
size();
919 return begin() + __ins_idx;
928 const auto __ins_idx = __pos -
cbegin();
929 if constexpr (ranges::forward_range<_Rg>)
931 auto [__last, __n] = __advance_dist(__rg);
932 if (__n != 0) [[likely]]
933 _M_insert_aux(__pos._M_const_cast(),
934 ranges::begin(__rg), __last,
939 auto __first = ranges::begin(__rg);
940 const auto __last = ranges::end(__rg);
941 for (
auto __it = __pos._M_const_cast(); __first != __last;
942 (void)++__first, ++__it)
943 __it = _M_emplace_aux(__it, *__first);
945 return begin() + __ins_idx;
948 template<
typename _Tp,
typename _Alloc>
949 template<__detail::__container_compatible_range<_Tp> _Rg>
952 prepend_range(_Rg&& __rg)
956 else if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
958 const size_type __n(ranges::distance(__rg));
959 if (__n != 0) [[likely]]
960 _M_range_prepend(ranges::begin(__rg), ranges::end(__rg), __n);
964 struct _Guard_elts_front
972 __self._M_erase_at_begin(__self.begin() + __n);
976 _Guard_elts_front __guard{*
this};
977 auto __first = ranges::begin(__rg);
978 const auto __last = ranges::end(__rg);
979 for (; __first != __last; (void)++__first, ++__guard.__n)
980 emplace_front(*__first);
982 for (
auto __fins =
begin(), __lins =
begin() + __guard.__n;
983 __fins != __lins && __fins != --__lins; ++__fins)
984 std::iter_swap(__fins, __lins);
990 template<
typename _Tp,
typename _Alloc>
991 template<__detail::__container_compatible_range<_Tp> _Rg>
994 append_range(_Rg&& __rg)
996 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
998 const size_type __n(ranges::distance(__rg));
999 if (__n != 0) [[likely]]
1000 _M_range_append(ranges::begin(__rg), ranges::end(__rg), __n);
1004 struct _Guard_elts_back
1007 size_type __n = __self.size();
1011 if (__n < __self.size())
1012 __self._M_erase_at_end(__self.begin() + __n);
1016 _Guard_elts_back __guard{*
this};
1017 auto __first = ranges::begin(__rg);
1018 const auto __last = ranges::end(__rg);
1019 for (; __first != __last; (void)++__first)
1020 emplace_back(*__first);
1022 __guard.__n =
size();
1027 template<
typename _Tp,
typename _Alloc>
1029 deque<_Tp, _Alloc>::
1030 _M_destroy_data_aux(iterator __first, iterator __last)
1032 for (_Map_pointer __node = __first._M_node + 1;
1033 __node < __last._M_node; ++__node)
1035 _M_get_Tp_allocator());
1037 if (__first._M_node != __last._M_node)
1040 _M_get_Tp_allocator());
1042 _M_get_Tp_allocator());
1046 _M_get_Tp_allocator());
1049 template <
typename _Tp,
typename _Alloc>
1054 if (this->max_size() - this->
size() < __new_elems)
1055 __throw_length_error(__N(
"deque::_M_new_elements_at_front"));
1058 / _S_buffer_size());
1064 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
1068 for (size_type __j = 1; __j < __i; ++__j)
1069 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
1070 __throw_exception_again;
1074 template <
typename _Tp,
typename _Alloc>
1079 if (this->max_size() - this->
size() < __new_elems)
1080 __throw_length_error(__N(
"deque::_M_new_elements_at_back"));
1083 / _S_buffer_size());
1089 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
1093 for (size_type __j = 1; __j < __i; ++__j)
1094 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
1095 __throw_exception_again;
1099 template <
typename _Tp,
typename _Alloc>
1105 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
1111 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
1115 std::copy(this->_M_impl._M_start._M_node,
1116 this->_M_impl._M_finish._M_node + 1,
1119 std::copy_backward(this->_M_impl._M_start._M_node,
1120 this->_M_impl._M_finish._M_node + 1,
1126 +
std::max(this->_M_impl._M_map_size,
1129 const size_t __bufsz = __deque_buf_size(
sizeof(_Tp));
1136 std::copy(this->_M_impl._M_start._M_node,
1137 this->_M_impl._M_finish._M_node + 1,
1139 _M_deallocate_map(this->_M_impl._M_map,
this->_M_impl._M_map_size);
1149_GLIBCXX_END_NAMESPACE_CONTAINER
1153 template<
typename _Tp,
typename _VTp>
1155 __fill_a1(
const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
1156 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
1157 const _VTp& __value)
1159 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1160 if (__first._M_node != __last._M_node)
1162 std::__fill_a1(__first._M_cur, __first._M_last, __value);
1164 for (
typename _Iter::_Map_pointer
__node = __first._M_node + 1;
1166 std::__fill_a1(*
__node, *
__node + _Iter::_S_buffer_size(), __value);
1168 std::__fill_a1(__last._M_first, __last._M_cur, __value);
1171 std::__fill_a1(__first._M_cur, __last._M_cur, __value);
1174 template<
bool _IsMove,
1175 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
1177 __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1178 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1181 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1182 if (__first._M_node != __last._M_node)
1188 for (
typename _Iter::_Map_pointer __node = __first._M_node + 1;
1189 __node != __last._M_node; ++__node)
1192 *__node + _Iter::_S_buffer_size(),
1203 template<
bool _IsMove,
1204 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
1206 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1207 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1209 {
return __copy_move_dit<_IsMove>(__first, __last, __result); }
1211 template<
bool _IsMove,
1212 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
1213 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1214 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1215 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1216 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1217 {
return __copy_move_dit<_IsMove>(__first, __last, __result); }
1219 template<
bool _IsMove,
typename _II,
typename _Tp>
1220 typename __gnu_cxx::__enable_if<
1221 __is_random_access_iter<_II>::__value,
1222 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1223 __copy_move_a1(_II __first, _II __last,
1224 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1226 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1227 typedef typename _Iter::difference_type difference_type;
1229 difference_type __len = __last - __first;
1232 const difference_type __clen
1233 =
std::min(__len, __result._M_last - __result._M_cur);
1245 template<
bool _IsMove,
typename _CharT>
1246 typename __gnu_cxx::__enable_if<
1247 __is_char<_CharT>::__value,
1248 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
1250 istreambuf_iterator<_CharT, char_traits<_CharT> > __first,
1251 istreambuf_iterator<_CharT, char_traits<_CharT> > __last,
1252 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result)
1254 if (__first == __last)
1261 = std::__copy_n_a(__first, __len, __result._M_cur,
false)
1272 template<
typename _CharT,
typename _Size>
1273 typename __gnu_cxx::__enable_if<
1274 __is_char<_CharT>::__value,
1275 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
1277 istreambuf_iterator<_CharT, char_traits<_CharT> > __it, _Size __size,
1278 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result,
1288 std::__copy_n_a(__it, __len, __result._M_cur, __strict);
1292 while (__size != 0);
1296 template<
bool _IsMove,
1297 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
1299 __copy_move_backward_dit(
1300 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1301 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1304 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1305 if (__first._M_node != __last._M_node)
1308 __last._M_first, __last._M_cur, __result);
1310 for (
typename _Iter::_Map_pointer __node = __last._M_node - 1;
1311 __node != __first._M_node; --__node)
1313 *__node, *__node + _Iter::_S_buffer_size(), __result);
1316 __first._M_cur, __first._M_last, __result);
1320 __first._M_cur, __last._M_cur, __result);
1323 template<
bool _IsMove,
1324 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
1326 __copy_move_backward_a1(
1327 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1328 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1330 {
return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1332 template<
bool _IsMove,
1333 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
1334 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1335 __copy_move_backward_a1(
1336 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1337 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1338 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1339 {
return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1341 template<
bool _IsMove,
typename _II,
typename _Tp>
1342 typename __gnu_cxx::__enable_if<
1343 __is_random_access_iter<_II>::__value,
1344 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1345 __copy_move_backward_a1(_II __first, _II __last,
1346 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1348 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1349 typedef typename _Iter::difference_type difference_type;
1351 difference_type __len = __last - __first;
1354 difference_type __rlen = __result._M_cur - __result._M_first;
1355 _Tp* __rend = __result._M_cur;
1358 __rlen = _Iter::_S_buffer_size();
1359 __rend = *(__result._M_node - 1) + __rlen;
1362 const difference_type __clen =
std::min(__len, __rlen);
1373 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1376 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
1377 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
1380 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1381 if (__first1._M_node != __last1._M_node)
1383 if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2))
1386 __first2 += __first1._M_last - __first1._M_cur;
1387 for (
typename _Iter::_Map_pointer __node = __first1._M_node + 1;
1388 __node != __last1._M_node;
1389 __first2 += _Iter::_S_buffer_size(), ++__node)
1390 if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(),
1394 return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2);
1397 return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2);
1400 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1401 typename __gnu_cxx::__enable_if<
1402 __is_random_access_iter<_II>::__value,
bool>::__type
1403 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1,
1404 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1,
1406 {
return std::__equal_dit(__first1, __last1, __first2); }
1408 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1409 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1411 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1412 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1413 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2)
1414 {
return std::__equal_dit(__first1, __last1, __first2); }
1416 template<
typename _II,
typename _Tp,
typename _Ref,
typename _Ptr>
1417 typename __gnu_cxx::__enable_if<
1418 __is_random_access_iter<_II>::__value,
bool>::__type
1419 __equal_aux1(_II __first1, _II __last1,
1420 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2)
1422 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1423 typedef typename _Iter::difference_type difference_type;
1425 difference_type __len = __last1 - __first1;
1428 const difference_type __clen
1429 =
std::min(__len, __first2._M_last - __first2._M_cur);
1430 if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur))
1441 template<
typename _Tp1,
typename _Ref,
typename _Ptr,
typename _Tp2>
1444 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1,
1445 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1,
1446 const _Tp2* __first2,
const _Tp2* __last2)
1448#if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1449 const bool __simple =
1450 (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value
1451 && __is_pointer(_Ptr)
1452#if __cplusplus > 201703L && __cpp_lib_concepts
1456 && !is_volatile_v<_Tp1> && !is_volatile_v<_Tp2>
1464 while (__first1._M_node != __last1._M_node)
1466 const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur;
1467 const ptrdiff_t __len2 = __last2 - __first2;
1468 const ptrdiff_t __len =
std::min(__len1, __len2);
1470 if (
int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last,
1471 __first2, __first2 + __len))
1477 return _Lc::__3way(__first1._M_cur, __last1._M_cur,
1481 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1484 __lexicographical_compare_aux1(
1485 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1486 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1487 _Tp2* __first2, _Tp2* __last2)
1488 {
return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; }
1490 template<
typename _Tp1,
1491 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1493 __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1,
1494 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
1495 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
1496 {
return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; }
1498 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1499 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1501 __lexicographical_compare_aux1(
1502 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1503 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1504 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
1505 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
1507#if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1508 const bool __simple =
1509 (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value
1510 && __is_pointer(_Ptr1) && __is_pointer(_Ptr2)
1511#if __cplusplus > 201703L && __cpp_lib_concepts
1515 && !is_volatile_v<_Tp1> && !is_volatile_v<_Tp2>
1523 while (__first1 != __last1)
1525 const ptrdiff_t __len2 = __first2._M_node == __last2._M_node
1526 ? __last2._M_cur - __first2._M_cur
1527 : __first2._M_last - __first2._M_cur;
1530 const ptrdiff_t __len1 = __first1._M_node == __last1._M_node
1531 ? __last1._M_cur - __first1._M_cur
1532 : __first1._M_last - __first1._M_cur;
1533 const ptrdiff_t __len =
std::min(__len1, __len2);
1534 if (
int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len,
1535 __first2._M_cur, __first2._M_cur + __len))
1542 return __last2 != __first2;
1545_GLIBCXX_END_NAMESPACE_VERSION
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
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 &)
constexpr insert_iterator< _Container > inserter(_Container &__x, std::__detail::__range_iter_t< _Container > __i)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
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.
constexpr void _Destroy(_ForwardIterator __first, _ForwardIterator __last)
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
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.
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in deque before specified iterator.
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
void _M_fill_initialize(const value_type &__value)
Fills the deque with copies of value.
void _M_new_elements_at_back(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
void _M_new_elements_at_front(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
deque & operator=(const deque &__x)
Deque assignment operator.
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).
iterator begin() noexcept
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.