1 // Deque implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
29 * Hewlett-Packard Company
31 * Permission to use, copy, modify, distribute and sell this software
32 * and its documentation for any purpose is hereby granted without fee,
33 * provided that the above copyright notice appear in all copies and
34 * that both that copyright notice and this permission notice appear
35 * in supporting documentation. Hewlett-Packard Company makes no
36 * representations about the suitability of this software for any
37 * purpose. It is provided "as is" without express or implied warranty.
41 * Silicon Graphics Computer Systems, Inc.
43 * Permission to use, copy, modify, distribute and sell this software
44 * and its documentation for any purpose is hereby granted without fee,
45 * provided that the above copyright notice appear in all copies and
46 * that both that copyright notice and this permission notice appear
47 * in supporting documentation. Silicon Graphics makes no
48 * representations about the suitability of this software for any
49 * purpose. It is provided "as is" without express or implied warranty.
53 * This is an internal header file, included by other library headers.
54 * You should not attempt to use it directly.
60 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
62 template <typename _Tp, typename _Alloc>
65 operator=(const deque& __x)
67 const size_type __len = size();
70 if (__len >= __x.size())
71 _M_erase_at_end(std::copy(__x.begin(), __x.end(),
72 this->_M_impl._M_start));
75 const_iterator __mid = __x.begin() + difference_type(__len);
76 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
77 insert(this->_M_impl._M_finish, __mid, __x.end());
83 #ifdef __GXX_EXPERIMENTAL_CXX0X__
84 template<typename _Tp, typename _Alloc>
85 template<typename... _Args>
88 emplace_front(_Args&&... __args)
90 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
92 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
93 std::forward<_Args>(__args)...);
94 --this->_M_impl._M_start._M_cur;
97 _M_push_front_aux(std::forward<_Args>(__args)...);
100 template<typename _Tp, typename _Alloc>
101 template<typename... _Args>
104 emplace_back(_Args&&... __args)
106 if (this->_M_impl._M_finish._M_cur
107 != this->_M_impl._M_finish._M_last - 1)
109 this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
110 std::forward<_Args>(__args)...);
111 ++this->_M_impl._M_finish._M_cur;
114 _M_push_back_aux(std::forward<_Args>(__args)...);
118 template <typename _Tp, typename _Alloc>
119 typename deque<_Tp, _Alloc>::iterator
121 insert(iterator __position, const value_type& __x)
123 if (__position._M_cur == this->_M_impl._M_start._M_cur)
126 return this->_M_impl._M_start;
128 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
131 iterator __tmp = this->_M_impl._M_finish;
136 return _M_insert_aux(__position, __x);
139 #ifdef __GXX_EXPERIMENTAL_CXX0X__
140 template<typename _Tp, typename _Alloc>
141 template<typename... _Args>
142 typename deque<_Tp, _Alloc>::iterator
144 emplace(iterator __position, _Args&&... __args)
146 if (__position._M_cur == this->_M_impl._M_start._M_cur)
148 push_front(std::forward<_Args>(__args)...);
149 return this->_M_impl._M_start;
151 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
153 push_back(std::forward<_Args>(__args)...);
154 iterator __tmp = this->_M_impl._M_finish;
159 return _M_insert_aux(__position, std::forward<_Args>(__args)...);
163 template <typename _Tp, typename _Alloc>
164 typename deque<_Tp, _Alloc>::iterator
166 erase(iterator __position)
168 iterator __next = __position;
170 const difference_type __index = __position - begin();
171 if (static_cast<size_type>(__index) < (size() >> 1))
173 if (__position != begin())
174 _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
180 _GLIBCXX_MOVE3(__next, end(), __position);
183 return begin() + __index;
186 template <typename _Tp, typename _Alloc>
187 typename deque<_Tp, _Alloc>::iterator
189 erase(iterator __first, iterator __last)
191 if (__first == begin() && __last == end())
198 const difference_type __n = __last - __first;
199 const difference_type __elems_before = __first - begin();
200 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
202 if (__first != begin())
203 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
204 _M_erase_at_begin(begin() + __n);
209 _GLIBCXX_MOVE3(__last, end(), __first);
210 _M_erase_at_end(end() - __n);
212 return begin() + __elems_before;
216 template <typename _Tp, class _Alloc>
217 template <typename _InputIterator>
220 _M_assign_aux(_InputIterator __first, _InputIterator __last,
221 std::input_iterator_tag)
223 iterator __cur = begin();
224 for (; __first != __last && __cur != end(); ++__cur, ++__first)
226 if (__first == __last)
227 _M_erase_at_end(__cur);
229 insert(end(), __first, __last);
232 template <typename _Tp, typename _Alloc>
235 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
237 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
239 iterator __new_start = _M_reserve_elements_at_front(__n);
242 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
243 __x, _M_get_Tp_allocator());
244 this->_M_impl._M_start = __new_start;
248 _M_destroy_nodes(__new_start._M_node,
249 this->_M_impl._M_start._M_node);
250 __throw_exception_again;
253 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
255 iterator __new_finish = _M_reserve_elements_at_back(__n);
258 std::__uninitialized_fill_a(this->_M_impl._M_finish,
260 _M_get_Tp_allocator());
261 this->_M_impl._M_finish = __new_finish;
265 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
266 __new_finish._M_node + 1);
267 __throw_exception_again;
271 _M_insert_aux(__pos, __n, __x);
274 template <typename _Tp, typename _Alloc>
277 _M_fill_initialize(const value_type& __value)
282 for (__cur = this->_M_impl._M_start._M_node;
283 __cur < this->_M_impl._M_finish._M_node;
285 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
286 __value, _M_get_Tp_allocator());
287 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
288 this->_M_impl._M_finish._M_cur,
289 __value, _M_get_Tp_allocator());
293 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
294 _M_get_Tp_allocator());
295 __throw_exception_again;
299 template <typename _Tp, typename _Alloc>
300 template <typename _InputIterator>
303 _M_range_initialize(_InputIterator __first, _InputIterator __last,
304 std::input_iterator_tag)
306 this->_M_initialize_map(0);
309 for (; __first != __last; ++__first)
315 __throw_exception_again;
319 template <typename _Tp, typename _Alloc>
320 template <typename _ForwardIterator>
323 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
324 std::forward_iterator_tag)
326 const size_type __n = std::distance(__first, __last);
327 this->_M_initialize_map(__n);
329 _Map_pointer __cur_node;
332 for (__cur_node = this->_M_impl._M_start._M_node;
333 __cur_node < this->_M_impl._M_finish._M_node;
336 _ForwardIterator __mid = __first;
337 std::advance(__mid, _S_buffer_size());
338 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
339 _M_get_Tp_allocator());
342 std::__uninitialized_copy_a(__first, __last,
343 this->_M_impl._M_finish._M_first,
344 _M_get_Tp_allocator());
348 std::_Destroy(this->_M_impl._M_start,
349 iterator(*__cur_node, __cur_node),
350 _M_get_Tp_allocator());
351 __throw_exception_again;
355 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
356 template<typename _Tp, typename _Alloc>
357 #ifdef __GXX_EXPERIMENTAL_CXX0X__
358 template<typename... _Args>
361 _M_push_back_aux(_Args&&... __args)
365 _M_push_back_aux(const value_type& __t)
368 _M_reserve_map_at_back();
369 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
372 #ifdef __GXX_EXPERIMENTAL_CXX0X__
373 this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
374 std::forward<_Args>(__args)...);
376 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
378 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
380 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
384 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
385 __throw_exception_again;
389 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
390 template<typename _Tp, typename _Alloc>
391 #ifdef __GXX_EXPERIMENTAL_CXX0X__
392 template<typename... _Args>
395 _M_push_front_aux(_Args&&... __args)
399 _M_push_front_aux(const value_type& __t)
402 _M_reserve_map_at_front();
403 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
406 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
408 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
409 #ifdef __GXX_EXPERIMENTAL_CXX0X__
410 this->_M_impl.construct(this->_M_impl._M_start._M_cur,
411 std::forward<_Args>(__args)...);
413 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
418 ++this->_M_impl._M_start;
419 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
420 __throw_exception_again;
424 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
425 template <typename _Tp, typename _Alloc>
426 void deque<_Tp, _Alloc>::
429 _M_deallocate_node(this->_M_impl._M_finish._M_first);
430 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
431 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
432 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
435 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
436 // Note that if the deque has at least one element (a precondition for this
437 // member function), and if
438 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
439 // then the deque must have at least two nodes.
440 template <typename _Tp, typename _Alloc>
441 void deque<_Tp, _Alloc>::
444 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
445 _M_deallocate_node(this->_M_impl._M_start._M_first);
446 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
447 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
450 template <typename _Tp, typename _Alloc>
451 template <typename _InputIterator>
454 _M_range_insert_aux(iterator __pos,
455 _InputIterator __first, _InputIterator __last,
456 std::input_iterator_tag)
457 { std::copy(__first, __last, std::inserter(*this, __pos)); }
459 template <typename _Tp, typename _Alloc>
460 template <typename _ForwardIterator>
463 _M_range_insert_aux(iterator __pos,
464 _ForwardIterator __first, _ForwardIterator __last,
465 std::forward_iterator_tag)
467 const size_type __n = std::distance(__first, __last);
468 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
470 iterator __new_start = _M_reserve_elements_at_front(__n);
473 std::__uninitialized_copy_a(__first, __last, __new_start,
474 _M_get_Tp_allocator());
475 this->_M_impl._M_start = __new_start;
479 _M_destroy_nodes(__new_start._M_node,
480 this->_M_impl._M_start._M_node);
481 __throw_exception_again;
484 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
486 iterator __new_finish = _M_reserve_elements_at_back(__n);
489 std::__uninitialized_copy_a(__first, __last,
490 this->_M_impl._M_finish,
491 _M_get_Tp_allocator());
492 this->_M_impl._M_finish = __new_finish;
496 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
497 __new_finish._M_node + 1);
498 __throw_exception_again;
502 _M_insert_aux(__pos, __first, __last, __n);
505 template<typename _Tp, typename _Alloc>
506 #ifdef __GXX_EXPERIMENTAL_CXX0X__
507 template<typename... _Args>
508 typename deque<_Tp, _Alloc>::iterator
510 _M_insert_aux(iterator __pos, _Args&&... __args)
512 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
514 typename deque<_Tp, _Alloc>::iterator
516 _M_insert_aux(iterator __pos, const value_type& __x)
518 value_type __x_copy = __x; // XXX copy
520 difference_type __index = __pos - this->_M_impl._M_start;
521 if (static_cast<size_type>(__index) < size() / 2)
523 push_front(_GLIBCXX_MOVE(front()));
524 iterator __front1 = this->_M_impl._M_start;
526 iterator __front2 = __front1;
528 __pos = this->_M_impl._M_start + __index;
529 iterator __pos1 = __pos;
531 _GLIBCXX_MOVE3(__front2, __pos1, __front1);
535 push_back(_GLIBCXX_MOVE(back()));
536 iterator __back1 = this->_M_impl._M_finish;
538 iterator __back2 = __back1;
540 __pos = this->_M_impl._M_start + __index;
541 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
543 *__pos = _GLIBCXX_MOVE(__x_copy);
547 template <typename _Tp, typename _Alloc>
550 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
552 const difference_type __elems_before = __pos - this->_M_impl._M_start;
553 const size_type __length = this->size();
554 value_type __x_copy = __x;
555 if (__elems_before < difference_type(__length / 2))
557 iterator __new_start = _M_reserve_elements_at_front(__n);
558 iterator __old_start = this->_M_impl._M_start;
559 __pos = this->_M_impl._M_start + __elems_before;
562 if (__elems_before >= difference_type(__n))
564 iterator __start_n = (this->_M_impl._M_start
565 + difference_type(__n));
566 std::__uninitialized_move_a(this->_M_impl._M_start,
567 __start_n, __new_start,
568 _M_get_Tp_allocator());
569 this->_M_impl._M_start = __new_start;
570 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
571 std::fill(__pos - difference_type(__n), __pos, __x_copy);
575 std::__uninitialized_move_fill(this->_M_impl._M_start,
577 this->_M_impl._M_start,
579 _M_get_Tp_allocator());
580 this->_M_impl._M_start = __new_start;
581 std::fill(__old_start, __pos, __x_copy);
586 _M_destroy_nodes(__new_start._M_node,
587 this->_M_impl._M_start._M_node);
588 __throw_exception_again;
593 iterator __new_finish = _M_reserve_elements_at_back(__n);
594 iterator __old_finish = this->_M_impl._M_finish;
595 const difference_type __elems_after =
596 difference_type(__length) - __elems_before;
597 __pos = this->_M_impl._M_finish - __elems_after;
600 if (__elems_after > difference_type(__n))
602 iterator __finish_n = (this->_M_impl._M_finish
603 - difference_type(__n));
604 std::__uninitialized_move_a(__finish_n,
605 this->_M_impl._M_finish,
606 this->_M_impl._M_finish,
607 _M_get_Tp_allocator());
608 this->_M_impl._M_finish = __new_finish;
609 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
610 std::fill(__pos, __pos + difference_type(__n), __x_copy);
614 std::__uninitialized_fill_move(this->_M_impl._M_finish,
615 __pos + difference_type(__n),
617 this->_M_impl._M_finish,
618 _M_get_Tp_allocator());
619 this->_M_impl._M_finish = __new_finish;
620 std::fill(__pos, __old_finish, __x_copy);
625 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
626 __new_finish._M_node + 1);
627 __throw_exception_again;
632 template <typename _Tp, typename _Alloc>
633 template <typename _ForwardIterator>
636 _M_insert_aux(iterator __pos,
637 _ForwardIterator __first, _ForwardIterator __last,
640 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
641 const size_type __length = size();
642 if (static_cast<size_type>(__elemsbefore) < __length / 2)
644 iterator __new_start = _M_reserve_elements_at_front(__n);
645 iterator __old_start = this->_M_impl._M_start;
646 __pos = this->_M_impl._M_start + __elemsbefore;
649 if (__elemsbefore >= difference_type(__n))
651 iterator __start_n = (this->_M_impl._M_start
652 + difference_type(__n));
653 std::__uninitialized_move_a(this->_M_impl._M_start,
654 __start_n, __new_start,
655 _M_get_Tp_allocator());
656 this->_M_impl._M_start = __new_start;
657 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
658 std::copy(__first, __last, __pos - difference_type(__n));
662 _ForwardIterator __mid = __first;
663 std::advance(__mid, difference_type(__n) - __elemsbefore);
664 std::__uninitialized_move_copy(this->_M_impl._M_start,
665 __pos, __first, __mid,
667 _M_get_Tp_allocator());
668 this->_M_impl._M_start = __new_start;
669 std::copy(__mid, __last, __old_start);
674 _M_destroy_nodes(__new_start._M_node,
675 this->_M_impl._M_start._M_node);
676 __throw_exception_again;
681 iterator __new_finish = _M_reserve_elements_at_back(__n);
682 iterator __old_finish = this->_M_impl._M_finish;
683 const difference_type __elemsafter =
684 difference_type(__length) - __elemsbefore;
685 __pos = this->_M_impl._M_finish - __elemsafter;
688 if (__elemsafter > difference_type(__n))
690 iterator __finish_n = (this->_M_impl._M_finish
691 - difference_type(__n));
692 std::__uninitialized_move_a(__finish_n,
693 this->_M_impl._M_finish,
694 this->_M_impl._M_finish,
695 _M_get_Tp_allocator());
696 this->_M_impl._M_finish = __new_finish;
697 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
698 std::copy(__first, __last, __pos);
702 _ForwardIterator __mid = __first;
703 std::advance(__mid, __elemsafter);
704 std::__uninitialized_copy_move(__mid, __last, __pos,
705 this->_M_impl._M_finish,
706 this->_M_impl._M_finish,
707 _M_get_Tp_allocator());
708 this->_M_impl._M_finish = __new_finish;
709 std::copy(__first, __mid, __pos);
714 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
715 __new_finish._M_node + 1);
716 __throw_exception_again;
721 template<typename _Tp, typename _Alloc>
724 _M_destroy_data_aux(iterator __first, iterator __last)
726 for (_Map_pointer __node = __first._M_node + 1;
727 __node < __last._M_node; ++__node)
728 std::_Destroy(*__node, *__node + _S_buffer_size(),
729 _M_get_Tp_allocator());
731 if (__first._M_node != __last._M_node)
733 std::_Destroy(__first._M_cur, __first._M_last,
734 _M_get_Tp_allocator());
735 std::_Destroy(__last._M_first, __last._M_cur,
736 _M_get_Tp_allocator());
739 std::_Destroy(__first._M_cur, __last._M_cur,
740 _M_get_Tp_allocator());
743 template <typename _Tp, typename _Alloc>
746 _M_new_elements_at_front(size_type __new_elems)
748 if (this->max_size() - this->size() < __new_elems)
749 __throw_length_error(__N("deque::_M_new_elements_at_front"));
751 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
753 _M_reserve_map_at_front(__new_nodes);
757 for (__i = 1; __i <= __new_nodes; ++__i)
758 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
762 for (size_type __j = 1; __j < __i; ++__j)
763 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
764 __throw_exception_again;
768 template <typename _Tp, typename _Alloc>
771 _M_new_elements_at_back(size_type __new_elems)
773 if (this->max_size() - this->size() < __new_elems)
774 __throw_length_error(__N("deque::_M_new_elements_at_back"));
776 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
778 _M_reserve_map_at_back(__new_nodes);
782 for (__i = 1; __i <= __new_nodes; ++__i)
783 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
787 for (size_type __j = 1; __j < __i; ++__j)
788 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
789 __throw_exception_again;
793 template <typename _Tp, typename _Alloc>
796 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
798 const size_type __old_num_nodes
799 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
800 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
802 _Map_pointer __new_nstart;
803 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
805 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
806 - __new_num_nodes) / 2
807 + (__add_at_front ? __nodes_to_add : 0);
808 if (__new_nstart < this->_M_impl._M_start._M_node)
809 std::copy(this->_M_impl._M_start._M_node,
810 this->_M_impl._M_finish._M_node + 1,
813 std::copy_backward(this->_M_impl._M_start._M_node,
814 this->_M_impl._M_finish._M_node + 1,
815 __new_nstart + __old_num_nodes);
819 size_type __new_map_size = this->_M_impl._M_map_size
820 + std::max(this->_M_impl._M_map_size,
823 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
824 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
825 + (__add_at_front ? __nodes_to_add : 0);
826 std::copy(this->_M_impl._M_start._M_node,
827 this->_M_impl._M_finish._M_node + 1,
829 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
831 this->_M_impl._M_map = __new_map;
832 this->_M_impl._M_map_size = __new_map_size;
835 this->_M_impl._M_start._M_set_node(__new_nstart);
836 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
839 // Overload for deque::iterators, exploiting the "segmented-iterator
840 // optimization". NB: leave const_iterators alone!
841 template<typename _Tp>
843 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
844 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
846 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
848 for (typename _Self::_Map_pointer __node = __first._M_node + 1;
849 __node < __last._M_node; ++__node)
850 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
852 if (__first._M_node != __last._M_node)
854 std::fill(__first._M_cur, __first._M_last, __value);
855 std::fill(__last._M_first, __last._M_cur, __value);
858 std::fill(__first._M_cur, __last._M_cur, __value);
861 _GLIBCXX_END_NESTED_NAMESPACE