1 // Deque implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001-2018 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
28 * Hewlett-Packard Company
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
40 * Silicon Graphics Computer Systems, Inc.
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
51 /** @file bits/deque.tcc
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{deque}
59 namespace std _GLIBCXX_VISIBILITY(default)
61 _GLIBCXX_BEGIN_NAMESPACE_VERSION
62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
64 #if __cplusplus >= 201103L
65 template <typename _Tp, typename _Alloc>
68 _M_default_initialize()
73 for (__cur = this->_M_impl._M_start._M_node;
74 __cur < this->_M_impl._M_finish._M_node;
76 std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
77 _M_get_Tp_allocator());
78 std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
79 this->_M_impl._M_finish._M_cur,
80 _M_get_Tp_allocator());
84 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
85 _M_get_Tp_allocator());
86 __throw_exception_again;
91 template <typename _Tp, typename _Alloc>
94 operator=(const deque& __x)
98 #if __cplusplus >= 201103L
99 if (_Alloc_traits::_S_propagate_on_copy_assign())
101 if (!_Alloc_traits::_S_always_equal()
102 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
104 // Replacement allocator cannot free existing storage,
105 // so deallocate everything and take copy of __x's data.
106 _M_replace_map(__x, __x.get_allocator());
107 std::__alloc_on_copy(_M_get_Tp_allocator(),
108 __x._M_get_Tp_allocator());
111 std::__alloc_on_copy(_M_get_Tp_allocator(),
112 __x._M_get_Tp_allocator());
115 const size_type __len = size();
116 if (__len >= __x.size())
117 _M_erase_at_end(std::copy(__x.begin(), __x.end(),
118 this->_M_impl._M_start));
121 const_iterator __mid = __x.begin() + difference_type(__len);
122 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
123 _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(),
124 std::random_access_iterator_tag());
130 #if __cplusplus >= 201103L
131 template<typename _Tp, typename _Alloc>
132 template<typename... _Args>
133 #if __cplusplus > 201402L
134 typename deque<_Tp, _Alloc>::reference
139 emplace_front(_Args&&... __args)
141 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
143 _Alloc_traits::construct(this->_M_impl,
144 this->_M_impl._M_start._M_cur - 1,
145 std::forward<_Args>(__args)...);
146 --this->_M_impl._M_start._M_cur;
149 _M_push_front_aux(std::forward<_Args>(__args)...);
150 #if __cplusplus > 201402L
155 template<typename _Tp, typename _Alloc>
156 template<typename... _Args>
157 #if __cplusplus > 201402L
158 typename deque<_Tp, _Alloc>::reference
163 emplace_back(_Args&&... __args)
165 if (this->_M_impl._M_finish._M_cur
166 != this->_M_impl._M_finish._M_last - 1)
168 _Alloc_traits::construct(this->_M_impl,
169 this->_M_impl._M_finish._M_cur,
170 std::forward<_Args>(__args)...);
171 ++this->_M_impl._M_finish._M_cur;
174 _M_push_back_aux(std::forward<_Args>(__args)...);
175 #if __cplusplus > 201402L
181 #if __cplusplus >= 201103L
182 template<typename _Tp, typename _Alloc>
183 template<typename... _Args>
184 typename deque<_Tp, _Alloc>::iterator
186 emplace(const_iterator __position, _Args&&... __args)
188 if (__position._M_cur == this->_M_impl._M_start._M_cur)
190 emplace_front(std::forward<_Args>(__args)...);
191 return this->_M_impl._M_start;
193 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
195 emplace_back(std::forward<_Args>(__args)...);
196 iterator __tmp = this->_M_impl._M_finish;
201 return _M_insert_aux(__position._M_const_cast(),
202 std::forward<_Args>(__args)...);
206 template <typename _Tp, typename _Alloc>
207 typename deque<_Tp, _Alloc>::iterator
209 #if __cplusplus >= 201103L
210 insert(const_iterator __position, const value_type& __x)
212 insert(iterator __position, const value_type& __x)
215 if (__position._M_cur == this->_M_impl._M_start._M_cur)
218 return this->_M_impl._M_start;
220 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
223 iterator __tmp = this->_M_impl._M_finish;
228 return _M_insert_aux(__position._M_const_cast(), __x);
231 template <typename _Tp, typename _Alloc>
232 typename deque<_Tp, _Alloc>::iterator
234 _M_erase(iterator __position)
236 iterator __next = __position;
238 const difference_type __index = __position - begin();
239 if (static_cast<size_type>(__index) < (size() >> 1))
241 if (__position != begin())
242 _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
248 _GLIBCXX_MOVE3(__next, end(), __position);
251 return begin() + __index;
254 template <typename _Tp, typename _Alloc>
255 typename deque<_Tp, _Alloc>::iterator
257 _M_erase(iterator __first, iterator __last)
259 if (__first == __last)
261 else if (__first == begin() && __last == end())
268 const difference_type __n = __last - __first;
269 const difference_type __elems_before = __first - begin();
270 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
272 if (__first != begin())
273 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
274 _M_erase_at_begin(begin() + __n);
279 _GLIBCXX_MOVE3(__last, end(), __first);
280 _M_erase_at_end(end() - __n);
282 return begin() + __elems_before;
286 template <typename _Tp, class _Alloc>
287 template <typename _InputIterator>
290 _M_assign_aux(_InputIterator __first, _InputIterator __last,
291 std::input_iterator_tag)
293 iterator __cur = begin();
294 for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
296 if (__first == __last)
297 _M_erase_at_end(__cur);
299 _M_range_insert_aux(end(), __first, __last,
300 std::__iterator_category(__first));
303 template <typename _Tp, typename _Alloc>
306 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
308 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
310 iterator __new_start = _M_reserve_elements_at_front(__n);
313 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
314 __x, _M_get_Tp_allocator());
315 this->_M_impl._M_start = __new_start;
319 _M_destroy_nodes(__new_start._M_node,
320 this->_M_impl._M_start._M_node);
321 __throw_exception_again;
324 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
326 iterator __new_finish = _M_reserve_elements_at_back(__n);
329 std::__uninitialized_fill_a(this->_M_impl._M_finish,
331 _M_get_Tp_allocator());
332 this->_M_impl._M_finish = __new_finish;
336 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
337 __new_finish._M_node + 1);
338 __throw_exception_again;
342 _M_insert_aux(__pos, __n, __x);
345 #if __cplusplus >= 201103L
346 template <typename _Tp, typename _Alloc>
349 _M_default_append(size_type __n)
353 iterator __new_finish = _M_reserve_elements_at_back(__n);
356 std::__uninitialized_default_a(this->_M_impl._M_finish,
358 _M_get_Tp_allocator());
359 this->_M_impl._M_finish = __new_finish;
363 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
364 __new_finish._M_node + 1);
365 __throw_exception_again;
370 template <typename _Tp, typename _Alloc>
375 const difference_type __front_capacity
376 = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
377 if (__front_capacity == 0)
380 const difference_type __back_capacity
381 = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
382 if (__front_capacity + __back_capacity < _S_buffer_size())
385 return std::__shrink_to_fit_aux<deque>::_S_do_it(*this);
389 template <typename _Tp, typename _Alloc>
392 _M_fill_initialize(const value_type& __value)
397 for (__cur = this->_M_impl._M_start._M_node;
398 __cur < this->_M_impl._M_finish._M_node;
400 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
401 __value, _M_get_Tp_allocator());
402 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
403 this->_M_impl._M_finish._M_cur,
404 __value, _M_get_Tp_allocator());
408 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
409 _M_get_Tp_allocator());
410 __throw_exception_again;
414 template <typename _Tp, typename _Alloc>
415 template <typename _InputIterator>
418 _M_range_initialize(_InputIterator __first, _InputIterator __last,
419 std::input_iterator_tag)
421 this->_M_initialize_map(0);
424 for (; __first != __last; ++__first)
425 #if __cplusplus >= 201103L
426 emplace_back(*__first);
434 __throw_exception_again;
438 template <typename _Tp, typename _Alloc>
439 template <typename _ForwardIterator>
442 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
443 std::forward_iterator_tag)
445 const size_type __n = std::distance(__first, __last);
446 this->_M_initialize_map(_S_check_init_len(__n, _M_get_Tp_allocator()));
448 _Map_pointer __cur_node;
451 for (__cur_node = this->_M_impl._M_start._M_node;
452 __cur_node < this->_M_impl._M_finish._M_node;
455 _ForwardIterator __mid = __first;
456 std::advance(__mid, _S_buffer_size());
457 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
458 _M_get_Tp_allocator());
461 std::__uninitialized_copy_a(__first, __last,
462 this->_M_impl._M_finish._M_first,
463 _M_get_Tp_allocator());
467 std::_Destroy(this->_M_impl._M_start,
468 iterator(*__cur_node, __cur_node),
469 _M_get_Tp_allocator());
470 __throw_exception_again;
474 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
475 template<typename _Tp, typename _Alloc>
476 #if __cplusplus >= 201103L
477 template<typename... _Args>
480 _M_push_back_aux(_Args&&... __args)
484 _M_push_back_aux(const value_type& __t)
487 if (size() == max_size())
488 __throw_length_error(
489 __N("cannot create std::deque larger than max_size()"));
491 _M_reserve_map_at_back();
492 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
495 #if __cplusplus >= 201103L
496 _Alloc_traits::construct(this->_M_impl,
497 this->_M_impl._M_finish._M_cur,
498 std::forward<_Args>(__args)...);
500 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
502 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
504 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
508 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
509 __throw_exception_again;
513 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
514 template<typename _Tp, typename _Alloc>
515 #if __cplusplus >= 201103L
516 template<typename... _Args>
519 _M_push_front_aux(_Args&&... __args)
523 _M_push_front_aux(const value_type& __t)
526 if (size() == max_size())
527 __throw_length_error(
528 __N("cannot create std::deque larger than max_size()"));
530 _M_reserve_map_at_front();
531 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
534 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
536 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
537 #if __cplusplus >= 201103L
538 _Alloc_traits::construct(this->_M_impl,
539 this->_M_impl._M_start._M_cur,
540 std::forward<_Args>(__args)...);
542 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
547 ++this->_M_impl._M_start;
548 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
549 __throw_exception_again;
553 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
554 template <typename _Tp, typename _Alloc>
555 void deque<_Tp, _Alloc>::
558 _M_deallocate_node(this->_M_impl._M_finish._M_first);
559 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
560 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
561 _Alloc_traits::destroy(_M_get_Tp_allocator(),
562 this->_M_impl._M_finish._M_cur);
565 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
566 // Note that if the deque has at least one element (a precondition for this
567 // member function), and if
568 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
569 // then the deque must have at least two nodes.
570 template <typename _Tp, typename _Alloc>
571 void deque<_Tp, _Alloc>::
574 _Alloc_traits::destroy(_M_get_Tp_allocator(),
575 this->_M_impl._M_start._M_cur);
576 _M_deallocate_node(this->_M_impl._M_start._M_first);
577 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
578 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
581 template <typename _Tp, typename _Alloc>
582 template <typename _InputIterator>
585 _M_range_insert_aux(iterator __pos,
586 _InputIterator __first, _InputIterator __last,
587 std::input_iterator_tag)
588 { std::copy(__first, __last, std::inserter(*this, __pos)); }
590 template <typename _Tp, typename _Alloc>
591 template <typename _ForwardIterator>
594 _M_range_insert_aux(iterator __pos,
595 _ForwardIterator __first, _ForwardIterator __last,
596 std::forward_iterator_tag)
598 const size_type __n = std::distance(__first, __last);
599 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
601 iterator __new_start = _M_reserve_elements_at_front(__n);
604 std::__uninitialized_copy_a(__first, __last, __new_start,
605 _M_get_Tp_allocator());
606 this->_M_impl._M_start = __new_start;
610 _M_destroy_nodes(__new_start._M_node,
611 this->_M_impl._M_start._M_node);
612 __throw_exception_again;
615 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
617 iterator __new_finish = _M_reserve_elements_at_back(__n);
620 std::__uninitialized_copy_a(__first, __last,
621 this->_M_impl._M_finish,
622 _M_get_Tp_allocator());
623 this->_M_impl._M_finish = __new_finish;
627 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
628 __new_finish._M_node + 1);
629 __throw_exception_again;
633 _M_insert_aux(__pos, __first, __last, __n);
636 template<typename _Tp, typename _Alloc>
637 #if __cplusplus >= 201103L
638 template<typename... _Args>
639 typename deque<_Tp, _Alloc>::iterator
641 _M_insert_aux(iterator __pos, _Args&&... __args)
643 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
645 typename deque<_Tp, _Alloc>::iterator
647 _M_insert_aux(iterator __pos, const value_type& __x)
649 value_type __x_copy = __x; // XXX copy
651 difference_type __index = __pos - this->_M_impl._M_start;
652 if (static_cast<size_type>(__index) < size() / 2)
654 push_front(_GLIBCXX_MOVE(front()));
655 iterator __front1 = this->_M_impl._M_start;
657 iterator __front2 = __front1;
659 __pos = this->_M_impl._M_start + __index;
660 iterator __pos1 = __pos;
662 _GLIBCXX_MOVE3(__front2, __pos1, __front1);
666 push_back(_GLIBCXX_MOVE(back()));
667 iterator __back1 = this->_M_impl._M_finish;
669 iterator __back2 = __back1;
671 __pos = this->_M_impl._M_start + __index;
672 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
674 *__pos = _GLIBCXX_MOVE(__x_copy);
678 template <typename _Tp, typename _Alloc>
681 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
683 const difference_type __elems_before = __pos - this->_M_impl._M_start;
684 const size_type __length = this->size();
685 value_type __x_copy = __x;
686 if (__elems_before < difference_type(__length / 2))
688 iterator __new_start = _M_reserve_elements_at_front(__n);
689 iterator __old_start = this->_M_impl._M_start;
690 __pos = this->_M_impl._M_start + __elems_before;
693 if (__elems_before >= difference_type(__n))
695 iterator __start_n = (this->_M_impl._M_start
696 + difference_type(__n));
697 std::__uninitialized_move_a(this->_M_impl._M_start,
698 __start_n, __new_start,
699 _M_get_Tp_allocator());
700 this->_M_impl._M_start = __new_start;
701 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
702 std::fill(__pos - difference_type(__n), __pos, __x_copy);
706 std::__uninitialized_move_fill(this->_M_impl._M_start,
708 this->_M_impl._M_start,
710 _M_get_Tp_allocator());
711 this->_M_impl._M_start = __new_start;
712 std::fill(__old_start, __pos, __x_copy);
717 _M_destroy_nodes(__new_start._M_node,
718 this->_M_impl._M_start._M_node);
719 __throw_exception_again;
724 iterator __new_finish = _M_reserve_elements_at_back(__n);
725 iterator __old_finish = this->_M_impl._M_finish;
726 const difference_type __elems_after =
727 difference_type(__length) - __elems_before;
728 __pos = this->_M_impl._M_finish - __elems_after;
731 if (__elems_after > difference_type(__n))
733 iterator __finish_n = (this->_M_impl._M_finish
734 - difference_type(__n));
735 std::__uninitialized_move_a(__finish_n,
736 this->_M_impl._M_finish,
737 this->_M_impl._M_finish,
738 _M_get_Tp_allocator());
739 this->_M_impl._M_finish = __new_finish;
740 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
741 std::fill(__pos, __pos + difference_type(__n), __x_copy);
745 std::__uninitialized_fill_move(this->_M_impl._M_finish,
746 __pos + difference_type(__n),
748 this->_M_impl._M_finish,
749 _M_get_Tp_allocator());
750 this->_M_impl._M_finish = __new_finish;
751 std::fill(__pos, __old_finish, __x_copy);
756 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
757 __new_finish._M_node + 1);
758 __throw_exception_again;
763 template <typename _Tp, typename _Alloc>
764 template <typename _ForwardIterator>
767 _M_insert_aux(iterator __pos,
768 _ForwardIterator __first, _ForwardIterator __last,
771 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
772 const size_type __length = size();
773 if (static_cast<size_type>(__elemsbefore) < __length / 2)
775 iterator __new_start = _M_reserve_elements_at_front(__n);
776 iterator __old_start = this->_M_impl._M_start;
777 __pos = this->_M_impl._M_start + __elemsbefore;
780 if (__elemsbefore >= difference_type(__n))
782 iterator __start_n = (this->_M_impl._M_start
783 + difference_type(__n));
784 std::__uninitialized_move_a(this->_M_impl._M_start,
785 __start_n, __new_start,
786 _M_get_Tp_allocator());
787 this->_M_impl._M_start = __new_start;
788 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
789 std::copy(__first, __last, __pos - difference_type(__n));
793 _ForwardIterator __mid = __first;
794 std::advance(__mid, difference_type(__n) - __elemsbefore);
795 std::__uninitialized_move_copy(this->_M_impl._M_start,
796 __pos, __first, __mid,
798 _M_get_Tp_allocator());
799 this->_M_impl._M_start = __new_start;
800 std::copy(__mid, __last, __old_start);
805 _M_destroy_nodes(__new_start._M_node,
806 this->_M_impl._M_start._M_node);
807 __throw_exception_again;
812 iterator __new_finish = _M_reserve_elements_at_back(__n);
813 iterator __old_finish = this->_M_impl._M_finish;
814 const difference_type __elemsafter =
815 difference_type(__length) - __elemsbefore;
816 __pos = this->_M_impl._M_finish - __elemsafter;
819 if (__elemsafter > difference_type(__n))
821 iterator __finish_n = (this->_M_impl._M_finish
822 - difference_type(__n));
823 std::__uninitialized_move_a(__finish_n,
824 this->_M_impl._M_finish,
825 this->_M_impl._M_finish,
826 _M_get_Tp_allocator());
827 this->_M_impl._M_finish = __new_finish;
828 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
829 std::copy(__first, __last, __pos);
833 _ForwardIterator __mid = __first;
834 std::advance(__mid, __elemsafter);
835 std::__uninitialized_copy_move(__mid, __last, __pos,
836 this->_M_impl._M_finish,
837 this->_M_impl._M_finish,
838 _M_get_Tp_allocator());
839 this->_M_impl._M_finish = __new_finish;
840 std::copy(__first, __mid, __pos);
845 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
846 __new_finish._M_node + 1);
847 __throw_exception_again;
852 template<typename _Tp, typename _Alloc>
855 _M_destroy_data_aux(iterator __first, iterator __last)
857 for (_Map_pointer __node = __first._M_node + 1;
858 __node < __last._M_node; ++__node)
859 std::_Destroy(*__node, *__node + _S_buffer_size(),
860 _M_get_Tp_allocator());
862 if (__first._M_node != __last._M_node)
864 std::_Destroy(__first._M_cur, __first._M_last,
865 _M_get_Tp_allocator());
866 std::_Destroy(__last._M_first, __last._M_cur,
867 _M_get_Tp_allocator());
870 std::_Destroy(__first._M_cur, __last._M_cur,
871 _M_get_Tp_allocator());
874 template <typename _Tp, typename _Alloc>
877 _M_new_elements_at_front(size_type __new_elems)
879 if (this->max_size() - this->size() < __new_elems)
880 __throw_length_error(__N("deque::_M_new_elements_at_front"));
882 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
884 _M_reserve_map_at_front(__new_nodes);
888 for (__i = 1; __i <= __new_nodes; ++__i)
889 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
893 for (size_type __j = 1; __j < __i; ++__j)
894 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
895 __throw_exception_again;
899 template <typename _Tp, typename _Alloc>
902 _M_new_elements_at_back(size_type __new_elems)
904 if (this->max_size() - this->size() < __new_elems)
905 __throw_length_error(__N("deque::_M_new_elements_at_back"));
907 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
909 _M_reserve_map_at_back(__new_nodes);
913 for (__i = 1; __i <= __new_nodes; ++__i)
914 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
918 for (size_type __j = 1; __j < __i; ++__j)
919 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
920 __throw_exception_again;
924 template <typename _Tp, typename _Alloc>
927 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
929 const size_type __old_num_nodes
930 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
931 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
933 _Map_pointer __new_nstart;
934 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
936 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
937 - __new_num_nodes) / 2
938 + (__add_at_front ? __nodes_to_add : 0);
939 if (__new_nstart < this->_M_impl._M_start._M_node)
940 std::copy(this->_M_impl._M_start._M_node,
941 this->_M_impl._M_finish._M_node + 1,
944 std::copy_backward(this->_M_impl._M_start._M_node,
945 this->_M_impl._M_finish._M_node + 1,
946 __new_nstart + __old_num_nodes);
950 size_type __new_map_size = this->_M_impl._M_map_size
951 + std::max(this->_M_impl._M_map_size,
954 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
955 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
956 + (__add_at_front ? __nodes_to_add : 0);
957 std::copy(this->_M_impl._M_start._M_node,
958 this->_M_impl._M_finish._M_node + 1,
960 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
962 this->_M_impl._M_map = __new_map;
963 this->_M_impl._M_map_size = __new_map_size;
966 this->_M_impl._M_start._M_set_node(__new_nstart);
967 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
970 // Overload for deque::iterators, exploiting the "segmented-iterator
972 template<typename _Tp>
974 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
975 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
977 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
979 for (typename _Self::_Map_pointer __node = __first._M_node + 1;
980 __node < __last._M_node; ++__node)
981 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
983 if (__first._M_node != __last._M_node)
985 std::fill(__first._M_cur, __first._M_last, __value);
986 std::fill(__last._M_first, __last._M_cur, __value);
989 std::fill(__first._M_cur, __last._M_cur, __value);
992 template<typename _Tp>
993 _Deque_iterator<_Tp, _Tp&, _Tp*>
994 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
995 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
996 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
998 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
999 typedef typename _Self::difference_type difference_type;
1001 difference_type __len = __last - __first;
1004 const difference_type __clen
1005 = std::min(__len, std::min(__first._M_last - __first._M_cur,
1006 __result._M_last - __result._M_cur));
1007 std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1015 template<typename _Tp>
1016 _Deque_iterator<_Tp, _Tp&, _Tp*>
1017 copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1018 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1019 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1021 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1022 typedef typename _Self::difference_type difference_type;
1024 difference_type __len = __last - __first;
1027 difference_type __llen = __last._M_cur - __last._M_first;
1028 _Tp* __lend = __last._M_cur;
1030 difference_type __rlen = __result._M_cur - __result._M_first;
1031 _Tp* __rend = __result._M_cur;
1035 __llen = _Self::_S_buffer_size();
1036 __lend = *(__last._M_node - 1) + __llen;
1040 __rlen = _Self::_S_buffer_size();
1041 __rend = *(__result._M_node - 1) + __rlen;
1044 const difference_type __clen = std::min(__len,
1045 std::min(__llen, __rlen));
1046 std::copy_backward(__lend - __clen, __lend, __rend);
1054 #if __cplusplus >= 201103L
1055 template<typename _Tp>
1056 _Deque_iterator<_Tp, _Tp&, _Tp*>
1057 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1058 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1059 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1061 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1062 typedef typename _Self::difference_type difference_type;
1064 difference_type __len = __last - __first;
1067 const difference_type __clen
1068 = std::min(__len, std::min(__first._M_last - __first._M_cur,
1069 __result._M_last - __result._M_cur));
1070 std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1078 template<typename _Tp>
1079 _Deque_iterator<_Tp, _Tp&, _Tp*>
1080 move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1081 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1082 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1084 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1085 typedef typename _Self::difference_type difference_type;
1087 difference_type __len = __last - __first;
1090 difference_type __llen = __last._M_cur - __last._M_first;
1091 _Tp* __lend = __last._M_cur;
1093 difference_type __rlen = __result._M_cur - __result._M_first;
1094 _Tp* __rend = __result._M_cur;
1098 __llen = _Self::_S_buffer_size();
1099 __lend = *(__last._M_node - 1) + __llen;
1103 __rlen = _Self::_S_buffer_size();
1104 __rend = *(__result._M_node - 1) + __rlen;
1107 const difference_type __clen = std::min(__len,
1108 std::min(__llen, __rlen));
1109 std::move_backward(__lend - __clen, __lend, __rend);
1118 _GLIBCXX_END_NAMESPACE_CONTAINER
1119 _GLIBCXX_END_NAMESPACE_VERSION