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;
78 std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
79 _M_get_Tp_allocator());
80 std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
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())
109 std::__alloc_on_copy(_M_get_Tp_allocator(),
110 __x._M_get_Tp_allocator());
113 std::__alloc_on_copy(_M_get_Tp_allocator(),
114 __x._M_get_Tp_allocator());
117 const size_type __len =
size();
118 if (__len >= __x.
size())
119 _M_erase_at_end(std::copy(__x.
begin(), __x.
end(),
120 this->_M_impl._M_start));
124 std::copy(__x.
begin(), __mid, 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,
147 std::forward<_Args>(__args)...);
148 --this->_M_impl._M_start._M_cur;
151 _M_push_front_aux(std::forward<_Args>(__args)...);
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,
172 std::forward<_Args>(__args)...);
173 ++this->_M_impl._M_finish._M_cur;
176 _M_push_back_aux(std::forward<_Args>(__args)...);
177#if __cplusplus > 201402L
183#if __cplusplus >= 201103L
184 template<
typename _Tp,
typename _Alloc>
185 template<
typename... _Args>
186 typename deque<_Tp, _Alloc>::iterator
190 if (__position._M_cur == this->_M_impl._M_start._M_cur)
192 emplace_front(std::forward<_Args>(__args)...);
193 return this->_M_impl._M_start;
195 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
197 emplace_back(std::forward<_Args>(__args)...);
198 iterator __tmp = this->_M_impl._M_finish;
203 return _M_insert_aux(__position._M_const_cast(),
204 std::forward<_Args>(__args)...);
208 template <
typename _Tp,
typename _Alloc>
211#if __cplusplus >= 201103L
214 insert(
iterator __position,
const value_type& __x)
217 if (__position._M_cur == this->_M_impl._M_start._M_cur)
220 return this->_M_impl._M_start;
222 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
225 iterator __tmp = this->_M_impl._M_finish;
230 return _M_insert_aux(__position._M_const_cast(), __x);
233 template <
typename _Tp,
typename _Alloc>
240 const difference_type __index = __position -
begin();
241 if (
static_cast<size_type
>(__index) < (
size() >> 1))
243 if (__position !=
begin())
244 _GLIBCXX_MOVE_BACKWARD3(
begin(), __position, __next);
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);
315 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
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);
331 std::__uninitialized_fill_a(this->_M_impl._M_finish,
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);
358 std::__uninitialized_default_a(this->_M_impl._M_finish,
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())
387 return std::__shrink_to_fit_aux<deque>::_S_do_it(*
this);
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;
402 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
403 __value, _M_get_Tp_allocator());
404 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
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)
427#
if __cplusplus >= 201103L
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()));
450 _Map_pointer __cur_node;
453 for (__cur_node = this->_M_impl._M_start._M_node;
454 __cur_node < this->_M_impl._M_finish._M_node;
457 if (__n < _S_buffer_size())
458 __builtin_unreachable();
460 _ForwardIterator __mid = __first;
462 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
463 _M_get_Tp_allocator());
466 std::__uninitialized_copy_a(__first, __last,
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,
503 std::forward<_Args>(__args)...);
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,
545 std::forward<_Args>(__args)...);
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>
591 _InputIterator __first, _InputIterator __last,
595 template <
typename _Tp,
typename _Alloc>
596 template <
typename _ForwardIterator>
599 _M_range_insert_aux(iterator __pos,
600 _ForwardIterator __first, _ForwardIterator __last,
604 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
606 iterator __new_start = _M_reserve_elements_at_front(__n);
609 std::__uninitialized_copy_a(__first, __last, __new_start,
610 _M_get_Tp_allocator());
611 this->_M_impl._M_start = __new_start;
615 _M_destroy_nodes(__new_start._M_node,
616 this->_M_impl._M_start._M_node);
617 __throw_exception_again;
620 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
622 iterator __new_finish = _M_reserve_elements_at_back(__n);
625 std::__uninitialized_copy_a(__first, __last,
626 this->_M_impl._M_finish,
627 _M_get_Tp_allocator());
628 this->_M_impl._M_finish = __new_finish;
632 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
633 __new_finish._M_node + 1);
634 __throw_exception_again;
638 _M_insert_aux(__pos, __first, __last, __n);
641 template<
typename _Tp,
typename _Alloc>
642#if __cplusplus >= 201103L
643 template<
typename... _Args>
644 typename deque<_Tp, _Alloc>::iterator
646 _M_insert_aux(iterator __pos, _Args&&... __args)
648 value_type __x_copy(std::forward<_Args>(__args)...);
650 typename deque<_Tp, _Alloc>::iterator
652 _M_insert_aux(iterator __pos,
const value_type& __x)
654 value_type __x_copy = __x;
656 difference_type __index = __pos - this->_M_impl._M_start;
657 if (
static_cast<size_type
>(__index) <
size() / 2)
659 push_front(_GLIBCXX_MOVE(front()));
660 iterator __front1 = this->_M_impl._M_start;
662 iterator __front2 = __front1;
664 __pos = this->_M_impl._M_start + __index;
665 iterator __pos1 = __pos;
667 _GLIBCXX_MOVE3(__front2, __pos1, __front1);
671 push_back(_GLIBCXX_MOVE(back()));
672 iterator __back1 = this->_M_impl._M_finish;
674 iterator __back2 = __back1;
676 __pos = this->_M_impl._M_start + __index;
677 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
679 *__pos = _GLIBCXX_MOVE(__x_copy);
683 template <
typename _Tp,
typename _Alloc>
686 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x)
688 const difference_type __elems_before = __pos - this->_M_impl._M_start;
689 const size_type __length = this->
size();
690 value_type __x_copy = __x;
691 if (__elems_before < difference_type(__length / 2))
693 iterator __new_start = _M_reserve_elements_at_front(__n);
694 iterator __old_start = this->_M_impl._M_start;
695 __pos = this->_M_impl._M_start + __elems_before;
698 if (__elems_before >= difference_type(__n))
700 iterator __start_n = (this->_M_impl._M_start
701 + difference_type(__n));
702 std::__uninitialized_move_a(this->_M_impl._M_start,
703 __start_n, __new_start,
704 _M_get_Tp_allocator());
705 this->_M_impl._M_start = __new_start;
706 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
707 std::fill(__pos - difference_type(__n), __pos, __x_copy);
711 std::__uninitialized_move_fill(this->_M_impl._M_start,
713 this->_M_impl._M_start,
715 _M_get_Tp_allocator());
716 this->_M_impl._M_start = __new_start;
717 std::fill(__old_start, __pos, __x_copy);
722 _M_destroy_nodes(__new_start._M_node,
723 this->_M_impl._M_start._M_node);
724 __throw_exception_again;
729 iterator __new_finish = _M_reserve_elements_at_back(__n);
730 iterator __old_finish = this->_M_impl._M_finish;
731 const difference_type __elems_after =
732 difference_type(__length) - __elems_before;
733 __pos = this->_M_impl._M_finish - __elems_after;
736 if (__elems_after > difference_type(__n))
738 iterator __finish_n = (this->_M_impl._M_finish
739 - difference_type(__n));
740 std::__uninitialized_move_a(__finish_n,
741 this->_M_impl._M_finish,
742 this->_M_impl._M_finish,
743 _M_get_Tp_allocator());
744 this->_M_impl._M_finish = __new_finish;
745 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
746 std::fill(__pos, __pos + difference_type(__n), __x_copy);
750 std::__uninitialized_fill_move(this->_M_impl._M_finish,
751 __pos + difference_type(__n),
753 this->_M_impl._M_finish,
754 _M_get_Tp_allocator());
755 this->_M_impl._M_finish = __new_finish;
756 std::fill(__pos, __old_finish, __x_copy);
761 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
762 __new_finish._M_node + 1);
763 __throw_exception_again;
768 template <
typename _Tp,
typename _Alloc>
769 template <
typename _ForwardIterator>
772 _M_insert_aux(iterator __pos,
773 _ForwardIterator __first, _ForwardIterator __last,
776 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
777 const size_type __length =
size();
778 if (
static_cast<size_type
>(__elemsbefore) < __length / 2)
780 iterator __new_start = _M_reserve_elements_at_front(__n);
781 iterator __old_start = this->_M_impl._M_start;
782 __pos = this->_M_impl._M_start + __elemsbefore;
785 if (__elemsbefore >= difference_type(__n))
787 iterator __start_n = (this->_M_impl._M_start
788 + difference_type(__n));
789 std::__uninitialized_move_a(this->_M_impl._M_start,
790 __start_n, __new_start,
791 _M_get_Tp_allocator());
792 this->_M_impl._M_start = __new_start;
793 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
794 std::copy(__first, __last, __pos - difference_type(__n));
798 _ForwardIterator __mid = __first;
799 std::advance(__mid, difference_type(__n) - __elemsbefore);
800 std::__uninitialized_move_copy(this->_M_impl._M_start,
801 __pos, __first, __mid,
803 _M_get_Tp_allocator());
804 this->_M_impl._M_start = __new_start;
805 std::copy(__mid, __last, __old_start);
810 _M_destroy_nodes(__new_start._M_node,
811 this->_M_impl._M_start._M_node);
812 __throw_exception_again;
817 iterator __new_finish = _M_reserve_elements_at_back(__n);
818 iterator __old_finish = this->_M_impl._M_finish;
819 const difference_type __elemsafter =
820 difference_type(__length) - __elemsbefore;
821 __pos = this->_M_impl._M_finish - __elemsafter;
824 if (__elemsafter > difference_type(__n))
826 iterator __finish_n = (this->_M_impl._M_finish
827 - difference_type(__n));
828 std::__uninitialized_move_a(__finish_n,
829 this->_M_impl._M_finish,
830 this->_M_impl._M_finish,
831 _M_get_Tp_allocator());
832 this->_M_impl._M_finish = __new_finish;
833 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
834 std::copy(__first, __last, __pos);
838 _ForwardIterator __mid = __first;
840 std::__uninitialized_copy_move(__mid, __last, __pos,
841 this->_M_impl._M_finish,
842 this->_M_impl._M_finish,
843 _M_get_Tp_allocator());
844 this->_M_impl._M_finish = __new_finish;
845 std::copy(__first, __mid, __pos);
850 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
851 __new_finish._M_node + 1);
852 __throw_exception_again;
857 template<
typename _Tp,
typename _Alloc>
860 _M_destroy_data_aux(iterator __first, iterator __last)
862 for (_Map_pointer __node = __first._M_node + 1;
863 __node < __last._M_node; ++__node)
865 _M_get_Tp_allocator());
867 if (__first._M_node != __last._M_node)
870 _M_get_Tp_allocator());
872 _M_get_Tp_allocator());
876 _M_get_Tp_allocator());
879 template <
typename _Tp,
typename _Alloc>
884 if (this->max_size() - this->
size() < __new_elems)
885 __throw_length_error(__N(
"deque::_M_new_elements_at_front"));
887 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
889 _M_reserve_map_at_front(__new_nodes);
893 for (__i = 1; __i <= __new_nodes; ++__i)
894 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
898 for (size_type __j = 1; __j < __i; ++__j)
899 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
900 __throw_exception_again;
904 template <
typename _Tp,
typename _Alloc>
909 if (this->max_size() - this->
size() < __new_elems)
910 __throw_length_error(__N(
"deque::_M_new_elements_at_back"));
912 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
914 _M_reserve_map_at_back(__new_nodes);
918 for (__i = 1; __i <= __new_nodes; ++__i)
919 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
923 for (size_type __j = 1; __j < __i; ++__j)
924 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
925 __throw_exception_again;
929 template <
typename _Tp,
typename _Alloc>
934 const size_type __old_num_nodes
935 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
936 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
938 _Map_pointer __new_nstart;
939 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
941 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
942 - __new_num_nodes) / 2
943 + (__add_at_front ? __nodes_to_add : 0);
944 if (__new_nstart < this->_M_impl._M_start._M_node)
945 std::copy(this->_M_impl._M_start._M_node,
946 this->_M_impl._M_finish._M_node + 1,
949 std::copy_backward(this->_M_impl._M_start._M_node,
950 this->_M_impl._M_finish._M_node + 1,
951 __new_nstart + __old_num_nodes);
955 size_type __new_map_size = this->_M_impl._M_map_size
956 +
std::max(this->_M_impl._M_map_size,
959 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
960 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
961 + (__add_at_front ? __nodes_to_add : 0);
962 std::copy(this->_M_impl._M_start._M_node,
963 this->_M_impl._M_finish._M_node + 1,
965 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
967 this->_M_impl._M_map = __new_map;
968 this->_M_impl._M_map_size = __new_map_size;
971 this->_M_impl._M_start._M_set_node(__new_nstart);
972 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
975_GLIBCXX_END_NAMESPACE_CONTAINER
979 template<
typename _Tp,
typename _VTp>
981 __fill_a1(
const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
982 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
985 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
986 if (__first._M_node != __last._M_node)
988 std::__fill_a1(__first._M_cur, __first._M_last, __value);
990 for (
typename _Iter::_Map_pointer __node = __first._M_node + 1;
991 __node < __last._M_node; ++__node)
992 std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value);
994 std::__fill_a1(__last._M_first, __last._M_cur, __value);
997 std::__fill_a1(__first._M_cur, __last._M_cur, __value);
1000 template<
bool _IsMove,
1001 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
1003 __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1004 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1007 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1008 if (__first._M_node != __last._M_node)
1011 = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last,
1014 for (
typename _Iter::_Map_pointer __node = __first._M_node + 1;
1015 __node != __last._M_node; ++__node)
1017 = std::__copy_move_a1<_IsMove>(*__node,
1018 *__node + _Iter::_S_buffer_size(),
1021 return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur,
1025 return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur,
1029 template<
bool _IsMove,
1030 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
1032 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1033 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1035 {
return __copy_move_dit<_IsMove>(__first, __last, __result); }
1037 template<
bool _IsMove,
1038 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
1039 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1040 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1041 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1042 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1043 {
return __copy_move_dit<_IsMove>(__first, __last, __result); }
1045 template<
bool _IsMove,
typename _II,
typename _Tp>
1046 typename __gnu_cxx::__enable_if<
1047 __is_random_access_iter<_II>::__value,
1048 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1049 __copy_move_a1(_II __first, _II __last,
1050 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1052 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1053 typedef typename _Iter::difference_type difference_type;
1055 difference_type __len = __last - __first;
1058 const difference_type __clen
1059 =
std::min(__len, __result._M_last - __result._M_cur);
1060 std::__copy_move_a1<_IsMove>(__first, __first + __clen,
1071 template<
bool _IsMove,
typename _CharT>
1072 typename __gnu_cxx::__enable_if<
1073 __is_char<_CharT>::__value,
1074 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
1076 istreambuf_iterator<_CharT, char_traits<_CharT> > __first,
1077 istreambuf_iterator<_CharT, char_traits<_CharT> > __last,
1078 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result)
1080 if (__first == __last)
1085 const std::ptrdiff_t __len = __result._M_last - __result._M_cur;
1086 const std::ptrdiff_t __nb
1087 = std::__copy_n_a(__first, __len, __result._M_cur,
false)
1098 template<
typename _CharT,
typename _Size>
1099 typename __gnu_cxx::__enable_if<
1100 __is_char<_CharT>::__value,
1101 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
1103 istreambuf_iterator<_CharT, char_traits<_CharT> > __it, _Size __size,
1104 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result,
1113 = std::min<_Size>(__result._M_last - __result._M_cur, __size);
1114 std::__copy_n_a(__it, __len, __result._M_cur, __strict);
1118 while (__size != 0);
1122 template<
bool _IsMove,
1123 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
1125 __copy_move_backward_dit(
1126 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1127 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1130 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1131 if (__first._M_node != __last._M_node)
1133 __result = std::__copy_move_backward_a1<_IsMove>(
1134 __last._M_first, __last._M_cur, __result);
1136 for (
typename _Iter::_Map_pointer __node = __last._M_node - 1;
1137 __node != __first._M_node; --__node)
1138 __result = std::__copy_move_backward_a1<_IsMove>(
1139 *__node, *__node + _Iter::_S_buffer_size(), __result);
1141 return std::__copy_move_backward_a1<_IsMove>(
1142 __first._M_cur, __first._M_last, __result);
1145 return std::__copy_move_backward_a1<_IsMove>(
1146 __first._M_cur, __last._M_cur, __result);
1149 template<
bool _IsMove,
1150 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
1152 __copy_move_backward_a1(
1153 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1154 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1156 {
return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1158 template<
bool _IsMove,
1159 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
1160 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1161 __copy_move_backward_a1(
1162 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1163 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1164 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1165 {
return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1167 template<
bool _IsMove,
typename _II,
typename _Tp>
1168 typename __gnu_cxx::__enable_if<
1169 __is_random_access_iter<_II>::__value,
1170 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1171 __copy_move_backward_a1(_II __first, _II __last,
1172 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1174 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1175 typedef typename _Iter::difference_type difference_type;
1177 difference_type __len = __last - __first;
1180 difference_type __rlen = __result._M_cur - __result._M_first;
1181 _Tp* __rend = __result._M_cur;
1184 __rlen = _Iter::_S_buffer_size();
1185 __rend = *(__result._M_node - 1) + __rlen;
1188 const difference_type __clen =
std::min(__len, __rlen);
1189 std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend);
1199 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1202 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
1203 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
1206 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1207 if (__first1._M_node != __last1._M_node)
1209 if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2))
1212 __first2 += __first1._M_last - __first1._M_cur;
1213 for (
typename _Iter::_Map_pointer __node = __first1._M_node + 1;
1214 __node != __last1._M_node;
1215 __first2 += _Iter::_S_buffer_size(), ++__node)
1216 if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(),
1220 return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2);
1223 return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2);
1226 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1227 typename __gnu_cxx::__enable_if<
1228 __is_random_access_iter<_II>::__value,
bool>::__type
1229 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1,
1230 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1,
1232 {
return std::__equal_dit(__first1, __last1, __first2); }
1234 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1235 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1237 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1238 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1239 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2)
1240 {
return std::__equal_dit(__first1, __last1, __first2); }
1242 template<
typename _II,
typename _Tp,
typename _Ref,
typename _Ptr>
1243 typename __gnu_cxx::__enable_if<
1244 __is_random_access_iter<_II>::__value,
bool>::__type
1245 __equal_aux1(_II __first1, _II __last1,
1246 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2)
1248 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1249 typedef typename _Iter::difference_type difference_type;
1251 difference_type __len = __last1 - __first1;
1254 const difference_type __clen
1255 =
std::min(__len, __first2._M_last - __first2._M_cur);
1256 if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur))
1267 template<
typename _Tp1,
typename _Ref,
typename _Ptr,
typename _Tp2>
1270 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1,
1271 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1,
1272 const _Tp2* __first2,
const _Tp2* __last2)
1274#if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1275 const bool __simple =
1276 (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value
1277 && __is_pointer(_Ptr)
1278#if __cplusplus > 201703L && __cpp_lib_concepts
1282 && !is_volatile_v<_Tp1> && !is_volatile_v<_Tp2>
1285 typedef std::__lexicographical_compare<__simple> _Lc;
1287 typedef std::__lexicographical_compare<false> _Lc;
1290 while (__first1._M_node != __last1._M_node)
1292 const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur;
1293 const ptrdiff_t __len2 = __last2 - __first2;
1294 const ptrdiff_t __len =
std::min(__len1, __len2);
1296 if (
int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last,
1297 __first2, __first2 + __len))
1303 return _Lc::__3way(__first1._M_cur, __last1._M_cur,
1307 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1310 __lexicographical_compare_aux1(
1311 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1312 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1313 _Tp2* __first2, _Tp2* __last2)
1314 {
return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; }
1316 template<
typename _Tp1,
1317 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1319 __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1,
1320 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
1321 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
1322 {
return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; }
1324 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1325 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1327 __lexicographical_compare_aux1(
1328 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1329 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1330 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
1331 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
1333#if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1334 const bool __simple =
1335 (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value
1336 && __is_pointer(_Ptr1) && __is_pointer(_Ptr2)
1337#if __cplusplus > 201703L && __cpp_lib_concepts
1341 && !is_volatile_v<_Tp1> && !is_volatile_v<_Tp2>
1344 typedef std::__lexicographical_compare<__simple> _Lc;
1346 typedef std::__lexicographical_compare<false> _Lc;
1349 while (__first1 != __last1)
1351 const ptrdiff_t __len2 = __first2._M_node == __last2._M_node
1352 ? __last2._M_cur - __first2._M_cur
1353 : __first2._M_last - __first2._M_cur;
1356 const ptrdiff_t __len1 = __first1._M_node == __last1._M_node
1357 ? __last1._M_cur - __first1._M_cur
1358 : __first1._M_last - __first1._M_cur;
1359 const ptrdiff_t __len =
std::min(__len1, __len2);
1360 if (
int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len,
1361 __first2._M_cur, __first2._M_cur + __len))
1368 return __last2 != __first2;
1371_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 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 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.