1 // Deque implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
4 // 2009, 2010, 2011, 2012
5 // Free Software Foundation, Inc.
7 // This file is part of the GNU ISO C++ Library. This library is free
8 // software; you can redistribute it and/or modify it under the
9 // terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 3, or (at your option)
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 // GNU General Public License for more details.
18 // Under Section 7 of GPL version 3, you are granted additional
19 // permissions described in the GCC Runtime Library Exception, version
20 // 3.1, as published by the Free Software Foundation.
22 // You should have received a copy of the GNU General Public License and
23 // a copy of the GCC Runtime Library Exception along with this program;
24 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 // <http://www.gnu.org/licenses/>.
30 * Hewlett-Packard Company
32 * Permission to use, copy, modify, distribute and sell this software
33 * and its documentation for any purpose is hereby granted without fee,
34 * provided that the above copyright notice appear in all copies and
35 * that both that copyright notice and this permission notice appear
36 * in supporting documentation. Hewlett-Packard Company makes no
37 * representations about the suitability of this software for any
38 * purpose. It is provided "as is" without express or implied warranty.
42 * Silicon Graphics Computer Systems, Inc.
44 * Permission to use, copy, modify, distribute and sell this software
45 * and its documentation for any purpose is hereby granted without fee,
46 * provided that the above copyright notice appear in all copies and
47 * that both that copyright notice and this permission notice appear
48 * in supporting documentation. Silicon Graphics makes no
49 * representations about the suitability of this software for any
50 * purpose. It is provided "as is" without express or implied warranty.
53 /** @file bits/deque.tcc
54 * This is an internal header file, included by other library headers.
55 * Do not attempt to use it directly. @headername{deque}
61 namespace std _GLIBCXX_VISIBILITY(default)
63 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
65 #ifdef __GXX_EXPERIMENTAL_CXX0X__
66 template <typename _Tp, typename _Alloc>
69 _M_default_initialize()
74 for (__cur = this->_M_impl._M_start._M_node;
75 __cur < this->_M_impl._M_finish._M_node;
77 std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
78 _M_get_Tp_allocator());
79 std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
80 this->_M_impl._M_finish._M_cur,
81 _M_get_Tp_allocator());
85 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
86 _M_get_Tp_allocator());
87 __throw_exception_again;
92 template <typename _Tp, typename _Alloc>
95 operator=(const deque& __x)
97 const size_type __len = size();
100 if (__len >= __x.size())
101 _M_erase_at_end(std::copy(__x.begin(), __x.end(),
102 this->_M_impl._M_start));
105 const_iterator __mid = __x.begin() + difference_type(__len);
106 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
107 insert(this->_M_impl._M_finish, __mid, __x.end());
113 #ifdef __GXX_EXPERIMENTAL_CXX0X__
114 template<typename _Tp, typename _Alloc>
115 template<typename... _Args>
118 emplace_front(_Args&&... __args)
120 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
122 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
123 std::forward<_Args>(__args)...);
124 --this->_M_impl._M_start._M_cur;
127 _M_push_front_aux(std::forward<_Args>(__args)...);
130 template<typename _Tp, typename _Alloc>
131 template<typename... _Args>
134 emplace_back(_Args&&... __args)
136 if (this->_M_impl._M_finish._M_cur
137 != this->_M_impl._M_finish._M_last - 1)
139 this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
140 std::forward<_Args>(__args)...);
141 ++this->_M_impl._M_finish._M_cur;
144 _M_push_back_aux(std::forward<_Args>(__args)...);
148 template <typename _Tp, typename _Alloc>
149 typename deque<_Tp, _Alloc>::iterator
151 insert(iterator __position, const value_type& __x)
153 if (__position._M_cur == this->_M_impl._M_start._M_cur)
156 return this->_M_impl._M_start;
158 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
161 iterator __tmp = this->_M_impl._M_finish;
166 return _M_insert_aux(__position, __x);
169 #ifdef __GXX_EXPERIMENTAL_CXX0X__
170 template<typename _Tp, typename _Alloc>
171 template<typename... _Args>
172 typename deque<_Tp, _Alloc>::iterator
174 emplace(iterator __position, _Args&&... __args)
176 if (__position._M_cur == this->_M_impl._M_start._M_cur)
178 emplace_front(std::forward<_Args>(__args)...);
179 return this->_M_impl._M_start;
181 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
183 emplace_back(std::forward<_Args>(__args)...);
184 iterator __tmp = this->_M_impl._M_finish;
189 return _M_insert_aux(__position, std::forward<_Args>(__args)...);
193 template <typename _Tp, typename _Alloc>
194 typename deque<_Tp, _Alloc>::iterator
196 erase(iterator __position)
198 iterator __next = __position;
200 const difference_type __index = __position - begin();
201 if (static_cast<size_type>(__index) < (size() >> 1))
203 if (__position != begin())
204 _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
210 _GLIBCXX_MOVE3(__next, end(), __position);
213 return begin() + __index;
216 template <typename _Tp, typename _Alloc>
217 typename deque<_Tp, _Alloc>::iterator
219 erase(iterator __first, iterator __last)
221 if (__first == __last)
223 else if (__first == begin() && __last == end())
230 const difference_type __n = __last - __first;
231 const difference_type __elems_before = __first - begin();
232 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
234 if (__first != begin())
235 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
236 _M_erase_at_begin(begin() + __n);
241 _GLIBCXX_MOVE3(__last, end(), __first);
242 _M_erase_at_end(end() - __n);
244 return begin() + __elems_before;
248 template <typename _Tp, class _Alloc>
249 template <typename _InputIterator>
252 _M_assign_aux(_InputIterator __first, _InputIterator __last,
253 std::input_iterator_tag)
255 iterator __cur = begin();
256 for (; __first != __last && __cur != end(); ++__cur, ++__first)
258 if (__first == __last)
259 _M_erase_at_end(__cur);
261 insert(end(), __first, __last);
264 template <typename _Tp, typename _Alloc>
267 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
269 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
271 iterator __new_start = _M_reserve_elements_at_front(__n);
274 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
275 __x, _M_get_Tp_allocator());
276 this->_M_impl._M_start = __new_start;
280 _M_destroy_nodes(__new_start._M_node,
281 this->_M_impl._M_start._M_node);
282 __throw_exception_again;
285 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
287 iterator __new_finish = _M_reserve_elements_at_back(__n);
290 std::__uninitialized_fill_a(this->_M_impl._M_finish,
292 _M_get_Tp_allocator());
293 this->_M_impl._M_finish = __new_finish;
297 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
298 __new_finish._M_node + 1);
299 __throw_exception_again;
303 _M_insert_aux(__pos, __n, __x);
306 #ifdef __GXX_EXPERIMENTAL_CXX0X__
307 template <typename _Tp, typename _Alloc>
310 _M_default_append(size_type __n)
314 iterator __new_finish = _M_reserve_elements_at_back(__n);
317 std::__uninitialized_default_a(this->_M_impl._M_finish,
319 _M_get_Tp_allocator());
320 this->_M_impl._M_finish = __new_finish;
324 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
325 __new_finish._M_node + 1);
326 __throw_exception_again;
331 template <typename _Tp, typename _Alloc>
336 const difference_type __front_capacity
337 = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
338 if (__front_capacity == 0)
341 const difference_type __back_capacity
342 = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
343 if (__front_capacity + __back_capacity < _S_buffer_size())
346 return std::__shrink_to_fit_aux<deque>::_S_do_it(*this);
350 template <typename _Tp, typename _Alloc>
353 _M_fill_initialize(const value_type& __value)
358 for (__cur = this->_M_impl._M_start._M_node;
359 __cur < this->_M_impl._M_finish._M_node;
361 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
362 __value, _M_get_Tp_allocator());
363 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
364 this->_M_impl._M_finish._M_cur,
365 __value, _M_get_Tp_allocator());
369 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
370 _M_get_Tp_allocator());
371 __throw_exception_again;
375 template <typename _Tp, typename _Alloc>
376 template <typename _InputIterator>
379 _M_range_initialize(_InputIterator __first, _InputIterator __last,
380 std::input_iterator_tag)
382 this->_M_initialize_map(0);
385 for (; __first != __last; ++__first)
391 __throw_exception_again;
395 template <typename _Tp, typename _Alloc>
396 template <typename _ForwardIterator>
399 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
400 std::forward_iterator_tag)
402 const size_type __n = std::distance(__first, __last);
403 this->_M_initialize_map(__n);
405 _Map_pointer __cur_node;
408 for (__cur_node = this->_M_impl._M_start._M_node;
409 __cur_node < this->_M_impl._M_finish._M_node;
412 _ForwardIterator __mid = __first;
413 std::advance(__mid, _S_buffer_size());
414 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
415 _M_get_Tp_allocator());
418 std::__uninitialized_copy_a(__first, __last,
419 this->_M_impl._M_finish._M_first,
420 _M_get_Tp_allocator());
424 std::_Destroy(this->_M_impl._M_start,
425 iterator(*__cur_node, __cur_node),
426 _M_get_Tp_allocator());
427 __throw_exception_again;
431 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
432 template<typename _Tp, typename _Alloc>
433 #ifdef __GXX_EXPERIMENTAL_CXX0X__
434 template<typename... _Args>
437 _M_push_back_aux(_Args&&... __args)
441 _M_push_back_aux(const value_type& __t)
444 _M_reserve_map_at_back();
445 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
448 #ifdef __GXX_EXPERIMENTAL_CXX0X__
449 this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
450 std::forward<_Args>(__args)...);
452 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
454 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
456 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
460 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
461 __throw_exception_again;
465 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
466 template<typename _Tp, typename _Alloc>
467 #ifdef __GXX_EXPERIMENTAL_CXX0X__
468 template<typename... _Args>
471 _M_push_front_aux(_Args&&... __args)
475 _M_push_front_aux(const value_type& __t)
478 _M_reserve_map_at_front();
479 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
482 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
484 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
485 #ifdef __GXX_EXPERIMENTAL_CXX0X__
486 this->_M_impl.construct(this->_M_impl._M_start._M_cur,
487 std::forward<_Args>(__args)...);
489 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
494 ++this->_M_impl._M_start;
495 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
496 __throw_exception_again;
500 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
501 template <typename _Tp, typename _Alloc>
502 void deque<_Tp, _Alloc>::
505 _M_deallocate_node(this->_M_impl._M_finish._M_first);
506 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
507 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
508 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
511 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
512 // Note that if the deque has at least one element (a precondition for this
513 // member function), and if
514 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
515 // then the deque must have at least two nodes.
516 template <typename _Tp, typename _Alloc>
517 void deque<_Tp, _Alloc>::
520 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
521 _M_deallocate_node(this->_M_impl._M_start._M_first);
522 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
523 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
526 template <typename _Tp, typename _Alloc>
527 template <typename _InputIterator>
530 _M_range_insert_aux(iterator __pos,
531 _InputIterator __first, _InputIterator __last,
532 std::input_iterator_tag)
533 { std::copy(__first, __last, std::inserter(*this, __pos)); }
535 template <typename _Tp, typename _Alloc>
536 template <typename _ForwardIterator>
539 _M_range_insert_aux(iterator __pos,
540 _ForwardIterator __first, _ForwardIterator __last,
541 std::forward_iterator_tag)
543 const size_type __n = std::distance(__first, __last);
544 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
546 iterator __new_start = _M_reserve_elements_at_front(__n);
549 std::__uninitialized_copy_a(__first, __last, __new_start,
550 _M_get_Tp_allocator());
551 this->_M_impl._M_start = __new_start;
555 _M_destroy_nodes(__new_start._M_node,
556 this->_M_impl._M_start._M_node);
557 __throw_exception_again;
560 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
562 iterator __new_finish = _M_reserve_elements_at_back(__n);
565 std::__uninitialized_copy_a(__first, __last,
566 this->_M_impl._M_finish,
567 _M_get_Tp_allocator());
568 this->_M_impl._M_finish = __new_finish;
572 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
573 __new_finish._M_node + 1);
574 __throw_exception_again;
578 _M_insert_aux(__pos, __first, __last, __n);
581 template<typename _Tp, typename _Alloc>
582 #ifdef __GXX_EXPERIMENTAL_CXX0X__
583 template<typename... _Args>
584 typename deque<_Tp, _Alloc>::iterator
586 _M_insert_aux(iterator __pos, _Args&&... __args)
588 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
590 typename deque<_Tp, _Alloc>::iterator
592 _M_insert_aux(iterator __pos, const value_type& __x)
594 value_type __x_copy = __x; // XXX copy
596 difference_type __index = __pos - this->_M_impl._M_start;
597 if (static_cast<size_type>(__index) < size() / 2)
599 push_front(_GLIBCXX_MOVE(front()));
600 iterator __front1 = this->_M_impl._M_start;
602 iterator __front2 = __front1;
604 __pos = this->_M_impl._M_start + __index;
605 iterator __pos1 = __pos;
607 _GLIBCXX_MOVE3(__front2, __pos1, __front1);
611 push_back(_GLIBCXX_MOVE(back()));
612 iterator __back1 = this->_M_impl._M_finish;
614 iterator __back2 = __back1;
616 __pos = this->_M_impl._M_start + __index;
617 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
619 *__pos = _GLIBCXX_MOVE(__x_copy);
623 template <typename _Tp, typename _Alloc>
626 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
628 const difference_type __elems_before = __pos - this->_M_impl._M_start;
629 const size_type __length = this->size();
630 value_type __x_copy = __x;
631 if (__elems_before < difference_type(__length / 2))
633 iterator __new_start = _M_reserve_elements_at_front(__n);
634 iterator __old_start = this->_M_impl._M_start;
635 __pos = this->_M_impl._M_start + __elems_before;
638 if (__elems_before >= difference_type(__n))
640 iterator __start_n = (this->_M_impl._M_start
641 + difference_type(__n));
642 std::__uninitialized_move_a(this->_M_impl._M_start,
643 __start_n, __new_start,
644 _M_get_Tp_allocator());
645 this->_M_impl._M_start = __new_start;
646 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
647 std::fill(__pos - difference_type(__n), __pos, __x_copy);
651 std::__uninitialized_move_fill(this->_M_impl._M_start,
653 this->_M_impl._M_start,
655 _M_get_Tp_allocator());
656 this->_M_impl._M_start = __new_start;
657 std::fill(__old_start, __pos, __x_copy);
662 _M_destroy_nodes(__new_start._M_node,
663 this->_M_impl._M_start._M_node);
664 __throw_exception_again;
669 iterator __new_finish = _M_reserve_elements_at_back(__n);
670 iterator __old_finish = this->_M_impl._M_finish;
671 const difference_type __elems_after =
672 difference_type(__length) - __elems_before;
673 __pos = this->_M_impl._M_finish - __elems_after;
676 if (__elems_after > difference_type(__n))
678 iterator __finish_n = (this->_M_impl._M_finish
679 - difference_type(__n));
680 std::__uninitialized_move_a(__finish_n,
681 this->_M_impl._M_finish,
682 this->_M_impl._M_finish,
683 _M_get_Tp_allocator());
684 this->_M_impl._M_finish = __new_finish;
685 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
686 std::fill(__pos, __pos + difference_type(__n), __x_copy);
690 std::__uninitialized_fill_move(this->_M_impl._M_finish,
691 __pos + difference_type(__n),
693 this->_M_impl._M_finish,
694 _M_get_Tp_allocator());
695 this->_M_impl._M_finish = __new_finish;
696 std::fill(__pos, __old_finish, __x_copy);
701 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
702 __new_finish._M_node + 1);
703 __throw_exception_again;
708 template <typename _Tp, typename _Alloc>
709 template <typename _ForwardIterator>
712 _M_insert_aux(iterator __pos,
713 _ForwardIterator __first, _ForwardIterator __last,
716 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
717 const size_type __length = size();
718 if (static_cast<size_type>(__elemsbefore) < __length / 2)
720 iterator __new_start = _M_reserve_elements_at_front(__n);
721 iterator __old_start = this->_M_impl._M_start;
722 __pos = this->_M_impl._M_start + __elemsbefore;
725 if (__elemsbefore >= difference_type(__n))
727 iterator __start_n = (this->_M_impl._M_start
728 + difference_type(__n));
729 std::__uninitialized_move_a(this->_M_impl._M_start,
730 __start_n, __new_start,
731 _M_get_Tp_allocator());
732 this->_M_impl._M_start = __new_start;
733 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
734 std::copy(__first, __last, __pos - difference_type(__n));
738 _ForwardIterator __mid = __first;
739 std::advance(__mid, difference_type(__n) - __elemsbefore);
740 std::__uninitialized_move_copy(this->_M_impl._M_start,
741 __pos, __first, __mid,
743 _M_get_Tp_allocator());
744 this->_M_impl._M_start = __new_start;
745 std::copy(__mid, __last, __old_start);
750 _M_destroy_nodes(__new_start._M_node,
751 this->_M_impl._M_start._M_node);
752 __throw_exception_again;
757 iterator __new_finish = _M_reserve_elements_at_back(__n);
758 iterator __old_finish = this->_M_impl._M_finish;
759 const difference_type __elemsafter =
760 difference_type(__length) - __elemsbefore;
761 __pos = this->_M_impl._M_finish - __elemsafter;
764 if (__elemsafter > difference_type(__n))
766 iterator __finish_n = (this->_M_impl._M_finish
767 - difference_type(__n));
768 std::__uninitialized_move_a(__finish_n,
769 this->_M_impl._M_finish,
770 this->_M_impl._M_finish,
771 _M_get_Tp_allocator());
772 this->_M_impl._M_finish = __new_finish;
773 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
774 std::copy(__first, __last, __pos);
778 _ForwardIterator __mid = __first;
779 std::advance(__mid, __elemsafter);
780 std::__uninitialized_copy_move(__mid, __last, __pos,
781 this->_M_impl._M_finish,
782 this->_M_impl._M_finish,
783 _M_get_Tp_allocator());
784 this->_M_impl._M_finish = __new_finish;
785 std::copy(__first, __mid, __pos);
790 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
791 __new_finish._M_node + 1);
792 __throw_exception_again;
797 template<typename _Tp, typename _Alloc>
800 _M_destroy_data_aux(iterator __first, iterator __last)
802 for (_Map_pointer __node = __first._M_node + 1;
803 __node < __last._M_node; ++__node)
804 std::_Destroy(*__node, *__node + _S_buffer_size(),
805 _M_get_Tp_allocator());
807 if (__first._M_node != __last._M_node)
809 std::_Destroy(__first._M_cur, __first._M_last,
810 _M_get_Tp_allocator());
811 std::_Destroy(__last._M_first, __last._M_cur,
812 _M_get_Tp_allocator());
815 std::_Destroy(__first._M_cur, __last._M_cur,
816 _M_get_Tp_allocator());
819 template <typename _Tp, typename _Alloc>
822 _M_new_elements_at_front(size_type __new_elems)
824 if (this->max_size() - this->size() < __new_elems)
825 __throw_length_error(__N("deque::_M_new_elements_at_front"));
827 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
829 _M_reserve_map_at_front(__new_nodes);
833 for (__i = 1; __i <= __new_nodes; ++__i)
834 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
838 for (size_type __j = 1; __j < __i; ++__j)
839 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
840 __throw_exception_again;
844 template <typename _Tp, typename _Alloc>
847 _M_new_elements_at_back(size_type __new_elems)
849 if (this->max_size() - this->size() < __new_elems)
850 __throw_length_error(__N("deque::_M_new_elements_at_back"));
852 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
854 _M_reserve_map_at_back(__new_nodes);
858 for (__i = 1; __i <= __new_nodes; ++__i)
859 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
863 for (size_type __j = 1; __j < __i; ++__j)
864 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
865 __throw_exception_again;
869 template <typename _Tp, typename _Alloc>
872 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
874 const size_type __old_num_nodes
875 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
876 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
878 _Map_pointer __new_nstart;
879 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
881 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
882 - __new_num_nodes) / 2
883 + (__add_at_front ? __nodes_to_add : 0);
884 if (__new_nstart < this->_M_impl._M_start._M_node)
885 std::copy(this->_M_impl._M_start._M_node,
886 this->_M_impl._M_finish._M_node + 1,
889 std::copy_backward(this->_M_impl._M_start._M_node,
890 this->_M_impl._M_finish._M_node + 1,
891 __new_nstart + __old_num_nodes);
895 size_type __new_map_size = this->_M_impl._M_map_size
896 + std::max(this->_M_impl._M_map_size,
899 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
900 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
901 + (__add_at_front ? __nodes_to_add : 0);
902 std::copy(this->_M_impl._M_start._M_node,
903 this->_M_impl._M_finish._M_node + 1,
905 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
907 this->_M_impl._M_map = __new_map;
908 this->_M_impl._M_map_size = __new_map_size;
911 this->_M_impl._M_start._M_set_node(__new_nstart);
912 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
915 // Overload for deque::iterators, exploiting the "segmented-iterator
917 template<typename _Tp>
919 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
920 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
922 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
924 for (typename _Self::_Map_pointer __node = __first._M_node + 1;
925 __node < __last._M_node; ++__node)
926 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
928 if (__first._M_node != __last._M_node)
930 std::fill(__first._M_cur, __first._M_last, __value);
931 std::fill(__last._M_first, __last._M_cur, __value);
934 std::fill(__first._M_cur, __last._M_cur, __value);
937 template<typename _Tp>
938 _Deque_iterator<_Tp, _Tp&, _Tp*>
939 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
940 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
941 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
943 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
944 typedef typename _Self::difference_type difference_type;
946 difference_type __len = __last - __first;
949 const difference_type __clen
950 = std::min(__len, std::min(__first._M_last - __first._M_cur,
951 __result._M_last - __result._M_cur));
952 std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
960 template<typename _Tp>
961 _Deque_iterator<_Tp, _Tp&, _Tp*>
962 copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
963 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
964 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
966 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
967 typedef typename _Self::difference_type difference_type;
969 difference_type __len = __last - __first;
972 difference_type __llen = __last._M_cur - __last._M_first;
973 _Tp* __lend = __last._M_cur;
975 difference_type __rlen = __result._M_cur - __result._M_first;
976 _Tp* __rend = __result._M_cur;
980 __llen = _Self::_S_buffer_size();
981 __lend = *(__last._M_node - 1) + __llen;
985 __rlen = _Self::_S_buffer_size();
986 __rend = *(__result._M_node - 1) + __rlen;
989 const difference_type __clen = std::min(__len,
990 std::min(__llen, __rlen));
991 std::copy_backward(__lend - __clen, __lend, __rend);
999 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1000 template<typename _Tp>
1001 _Deque_iterator<_Tp, _Tp&, _Tp*>
1002 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1003 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1004 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1006 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1007 typedef typename _Self::difference_type difference_type;
1009 difference_type __len = __last - __first;
1012 const difference_type __clen
1013 = std::min(__len, std::min(__first._M_last - __first._M_cur,
1014 __result._M_last - __result._M_cur));
1015 std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1023 template<typename _Tp>
1024 _Deque_iterator<_Tp, _Tp&, _Tp*>
1025 move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1026 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1027 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1029 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1030 typedef typename _Self::difference_type difference_type;
1032 difference_type __len = __last - __first;
1035 difference_type __llen = __last._M_cur - __last._M_first;
1036 _Tp* __lend = __last._M_cur;
1038 difference_type __rlen = __result._M_cur - __result._M_first;
1039 _Tp* __rend = __result._M_cur;
1043 __llen = _Self::_S_buffer_size();
1044 __lend = *(__last._M_node - 1) + __llen;
1048 __rlen = _Self::_S_buffer_size();
1049 __rend = *(__result._M_node - 1) + __rlen;
1052 const difference_type __clen = std::min(__len,
1053 std::min(__llen, __rlen));
1054 std::move_backward(__lend - __clen, __lend, __rend);
1063 _GLIBCXX_END_NAMESPACE_CONTAINER