| blob | 294a0dd6a6c666d50c2f7db46a419d1a86cc5e55 |
1 // Deque implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 //
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 2, or (at your option)
9 // any later version.
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 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19 // USA.
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
30 /*
31 *
32 * Copyright (c) 1994
33 * Hewlett-Packard Company
34 *
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
42 *
43 *
44 * Copyright (c) 1997
45 * Silicon Graphics Computer Systems, Inc.
46 *
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
54 */
56 /** @file deque.tcc
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
59 */
61 #ifndef _DEQUE_TCC
62 #define _DEQUE_TCC 1
64 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
66 template <typename _Tp, typename _Alloc>
67 deque<_Tp, _Alloc>&
68 deque<_Tp, _Alloc>::
69 operator=(const deque& __x)
70 {
71 const size_type __len = size();
72 if (&__x != this)
73 {
74 if (__len >= __x.size())
75 _M_erase_at_end(std::copy(__x.begin(), __x.end(),
76 this->_M_impl._M_start));
77 else
78 {
79 const_iterator __mid = __x.begin() + difference_type(__len);
80 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
81 insert(this->_M_impl._M_finish, __mid, __x.end());
82 }
83 }
84 return *this;
85 }
87 template <typename _Tp, typename _Alloc>
88 typename deque<_Tp, _Alloc>::iterator
89 deque<_Tp, _Alloc>::
90 insert(iterator __position, const value_type& __x)
91 {
92 if (__position._M_cur == this->_M_impl._M_start._M_cur)
93 {
94 push_front(__x);
95 return this->_M_impl._M_start;
96 }
97 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
98 {
99 push_back(__x);
100 iterator __tmp = this->_M_impl._M_finish;
101 --__tmp;
102 return __tmp;
103 }
104 else
105 return _M_insert_aux(__position, __x);
106 }
108 template <typename _Tp, typename _Alloc>
109 typename deque<_Tp, _Alloc>::iterator
110 deque<_Tp, _Alloc>::
111 erase(iterator __position)
112 {
113 iterator __next = __position;
114 ++__next;
115 const difference_type __index = __position - begin();
116 if (static_cast<size_type>(__index) < (size() >> 1))
117 {
118 if (__position != begin())
119 std::copy_backward(begin(), __position, __next);
120 pop_front();
121 }
122 else
123 {
124 if (__next != end())
125 std::copy(__next, end(), __position);
126 pop_back();
127 }
128 return begin() + __index;
129 }
131 template <typename _Tp, typename _Alloc>
132 typename deque<_Tp, _Alloc>::iterator
133 deque<_Tp, _Alloc>::
134 erase(iterator __first, iterator __last)
135 {
136 if (__first == begin() && __last == end())
137 {
138 clear();
139 return end();
140 }
141 else
142 {
143 const difference_type __n = __last - __first;
144 const difference_type __elems_before = __first - begin();
145 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
146 {
147 if (__first != begin())
148 std::copy_backward(begin(), __first, __last);
149 _M_erase_at_begin(begin() + __n);
150 }
151 else
152 {
153 if (__last != end())
154 std::copy(__last, end(), __first);
155 _M_erase_at_end(end() - __n);
156 }
157 return begin() + __elems_before;
158 }
159 }
161 template <typename _Tp, class _Alloc>
162 template <typename _InputIterator>
163 void
164 deque<_Tp, _Alloc>::
165 _M_assign_aux(_InputIterator __first, _InputIterator __last,
166 std::input_iterator_tag)
167 {
168 iterator __cur = begin();
169 for (; __first != __last && __cur != end(); ++__cur, ++__first)
170 *__cur = *__first;
171 if (__first == __last)
172 _M_erase_at_end(__cur);
173 else
174 insert(end(), __first, __last);
175 }
177 template <typename _Tp, typename _Alloc>
178 void
179 deque<_Tp, _Alloc>::
180 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
181 {
182 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
183 {
184 iterator __new_start = _M_reserve_elements_at_front(__n);
185 try
186 {
187 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
188 __x, _M_get_Tp_allocator());
189 this->_M_impl._M_start = __new_start;
190 }
191 catch(...)
192 {
193 _M_destroy_nodes(__new_start._M_node,
194 this->_M_impl._M_start._M_node);
195 __throw_exception_again;
196 }
197 }
198 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
199 {
200 iterator __new_finish = _M_reserve_elements_at_back(__n);
201 try
202 {
203 std::__uninitialized_fill_a(this->_M_impl._M_finish,
204 __new_finish, __x,
205 _M_get_Tp_allocator());
206 this->_M_impl._M_finish = __new_finish;
207 }
208 catch(...)
209 {
210 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
211 __new_finish._M_node + 1);
212 __throw_exception_again;
213 }
214 }
215 else
216 _M_insert_aux(__pos, __n, __x);
217 }
219 template <typename _Tp, typename _Alloc>
220 void
221 deque<_Tp, _Alloc>::
222 _M_fill_initialize(const value_type& __value)
223 {
224 _Map_pointer __cur;
225 try
226 {
227 for (__cur = this->_M_impl._M_start._M_node;
228 __cur < this->_M_impl._M_finish._M_node;
229 ++__cur)
230 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
231 __value, _M_get_Tp_allocator());
232 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
233 this->_M_impl._M_finish._M_cur,
234 __value, _M_get_Tp_allocator());
235 }
236 catch(...)
237 {
238 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
239 _M_get_Tp_allocator());
240 __throw_exception_again;
241 }
242 }
244 template <typename _Tp, typename _Alloc>
245 template <typename _InputIterator>
246 void
247 deque<_Tp, _Alloc>::
248 _M_range_initialize(_InputIterator __first, _InputIterator __last,
249 std::input_iterator_tag)
250 {
251 this->_M_initialize_map(0);
252 try
253 {
254 for (; __first != __last; ++__first)
255 push_back(*__first);
256 }
257 catch(...)
258 {
259 clear();
260 __throw_exception_again;
261 }
262 }
264 template <typename _Tp, typename _Alloc>
265 template <typename _ForwardIterator>
266 void
267 deque<_Tp, _Alloc>::
268 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
269 std::forward_iterator_tag)
270 {
271 const size_type __n = std::distance(__first, __last);
272 this->_M_initialize_map(__n);
274 _Map_pointer __cur_node;
275 try
276 {
277 for (__cur_node = this->_M_impl._M_start._M_node;
278 __cur_node < this->_M_impl._M_finish._M_node;
279 ++__cur_node)
280 {
281 _ForwardIterator __mid = __first;
282 std::advance(__mid, _S_buffer_size());
283 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
284 _M_get_Tp_allocator());
285 __first = __mid;
286 }
287 std::__uninitialized_copy_a(__first, __last,
288 this->_M_impl._M_finish._M_first,
289 _M_get_Tp_allocator());
290 }
291 catch(...)
292 {
293 std::_Destroy(this->_M_impl._M_start,
294 iterator(*__cur_node, __cur_node),
295 _M_get_Tp_allocator());
296 __throw_exception_again;
297 }
298 }
300 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
301 template <typename _Tp, typename _Alloc>
302 void
303 deque<_Tp, _Alloc>::
304 _M_push_back_aux(const value_type& __t)
305 {
306 value_type __t_copy = __t;
307 _M_reserve_map_at_back();
308 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
309 try
310 {
311 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy);
312 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
313 + 1);
314 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
315 }
316 catch(...)
317 {
318 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
319 __throw_exception_again;
320 }
321 }
323 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
324 template <typename _Tp, typename _Alloc>
325 void
326 deque<_Tp, _Alloc>::
327 _M_push_front_aux(const value_type& __t)
328 {
329 value_type __t_copy = __t;
330 _M_reserve_map_at_front();
331 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
332 try
333 {
334 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
335 - 1);
336 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
337 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy);
338 }
339 catch(...)
340 {
341 ++this->_M_impl._M_start;
342 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
343 __throw_exception_again;
344 }
345 }
347 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
348 template <typename _Tp, typename _Alloc>
349 void deque<_Tp, _Alloc>::
350 _M_pop_back_aux()
351 {
352 _M_deallocate_node(this->_M_impl._M_finish._M_first);
353 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
354 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
355 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
356 }
358 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
359 // Note that if the deque has at least one element (a precondition for this
360 // member function), and if
361 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
362 // then the deque must have at least two nodes.
363 template <typename _Tp, typename _Alloc>
364 void deque<_Tp, _Alloc>::
365 _M_pop_front_aux()
366 {
367 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
368 _M_deallocate_node(this->_M_impl._M_start._M_first);
369 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
370 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
371 }
373 template <typename _Tp, typename _Alloc>
374 template <typename _InputIterator>
375 void
376 deque<_Tp, _Alloc>::
377 _M_range_insert_aux(iterator __pos,
378 _InputIterator __first, _InputIterator __last,
379 std::input_iterator_tag)
380 { std::copy(__first, __last, std::inserter(*this, __pos)); }
382 template <typename _Tp, typename _Alloc>
383 template <typename _ForwardIterator>
384 void
385 deque<_Tp, _Alloc>::
386 _M_range_insert_aux(iterator __pos,
387 _ForwardIterator __first, _ForwardIterator __last,
388 std::forward_iterator_tag)
389 {
390 const size_type __n = std::distance(__first, __last);
391 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
392 {
393 iterator __new_start = _M_reserve_elements_at_front(__n);
394 try
395 {
396 std::__uninitialized_copy_a(__first, __last, __new_start,
397 _M_get_Tp_allocator());
398 this->_M_impl._M_start = __new_start;
399 }
400 catch(...)
401 {
402 _M_destroy_nodes(__new_start._M_node,
403 this->_M_impl._M_start._M_node);
404 __throw_exception_again;
405 }
406 }
407 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
408 {
409 iterator __new_finish = _M_reserve_elements_at_back(__n);
410 try
411 {
412 std::__uninitialized_copy_a(__first, __last,
413 this->_M_impl._M_finish,
414 _M_get_Tp_allocator());
415 this->_M_impl._M_finish = __new_finish;
416 }
417 catch(...)
418 {
419 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
420 __new_finish._M_node + 1);
421 __throw_exception_again;
422 }
423 }
424 else
425 _M_insert_aux(__pos, __first, __last, __n);
426 }
428 template <typename _Tp, typename _Alloc>
429 typename deque<_Tp, _Alloc>::iterator
430 deque<_Tp, _Alloc>::
431 _M_insert_aux(iterator __pos, const value_type& __x)
432 {
433 difference_type __index = __pos - this->_M_impl._M_start;
434 value_type __x_copy = __x; // XXX copy
435 if (static_cast<size_type>(__index) < size() / 2)
436 {
437 push_front(front());
438 iterator __front1 = this->_M_impl._M_start;
439 ++__front1;
440 iterator __front2 = __front1;
441 ++__front2;
442 __pos = this->_M_impl._M_start + __index;
443 iterator __pos1 = __pos;
444 ++__pos1;
445 std::copy(__front2, __pos1, __front1);
446 }
447 else
448 {
449 push_back(back());
450 iterator __back1 = this->_M_impl._M_finish;
451 --__back1;
452 iterator __back2 = __back1;
453 --__back2;
454 __pos = this->_M_impl._M_start + __index;
455 std::copy_backward(__pos, __back2, __back1);
456 }
457 *__pos = __x_copy;
458 return __pos;
459 }
461 template <typename _Tp, typename _Alloc>
462 void
463 deque<_Tp, _Alloc>::
464 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
465 {
466 const difference_type __elems_before = __pos - this->_M_impl._M_start;
467 const size_type __length = this->size();
468 value_type __x_copy = __x;
469 if (__elems_before < difference_type(__length / 2))
470 {
471 iterator __new_start = _M_reserve_elements_at_front(__n);
472 iterator __old_start = this->_M_impl._M_start;
473 __pos = this->_M_impl._M_start + __elems_before;
474 try
475 {
476 if (__elems_before >= difference_type(__n))
477 {
478 iterator __start_n = (this->_M_impl._M_start
479 + difference_type(__n));
480 std::__uninitialized_copy_a(this->_M_impl._M_start,
481 __start_n, __new_start,
482 _M_get_Tp_allocator());
483 this->_M_impl._M_start = __new_start;
484 std::copy(__start_n, __pos, __old_start);
485 std::fill(__pos - difference_type(__n), __pos, __x_copy);
486 }
487 else
488 {
489 std::__uninitialized_copy_fill(this->_M_impl._M_start,
490 __pos, __new_start,
491 this->_M_impl._M_start,
492 __x_copy,
493 _M_get_Tp_allocator());
494 this->_M_impl._M_start = __new_start;
495 std::fill(__old_start, __pos, __x_copy);
496 }
497 }
498 catch(...)
499 {
500 _M_destroy_nodes(__new_start._M_node,
501 this->_M_impl._M_start._M_node);
502 __throw_exception_again;
503 }
504 }
505 else
506 {
507 iterator __new_finish = _M_reserve_elements_at_back(__n);
508 iterator __old_finish = this->_M_impl._M_finish;
509 const difference_type __elems_after =
510 difference_type(__length) - __elems_before;
511 __pos = this->_M_impl._M_finish - __elems_after;
512 try
513 {
514 if (__elems_after > difference_type(__n))
515 {
516 iterator __finish_n = (this->_M_impl._M_finish
517 - difference_type(__n));
518 std::__uninitialized_copy_a(__finish_n,
519 this->_M_impl._M_finish,
520 this->_M_impl._M_finish,
521 _M_get_Tp_allocator());
522 this->_M_impl._M_finish = __new_finish;
523 std::copy_backward(__pos, __finish_n, __old_finish);
524 std::fill(__pos, __pos + difference_type(__n), __x_copy);
525 }
526 else
527 {
528 std::__uninitialized_fill_copy(this->_M_impl._M_finish,
529 __pos + difference_type(__n),
530 __x_copy, __pos,
531 this->_M_impl._M_finish,
532 _M_get_Tp_allocator());
533 this->_M_impl._M_finish = __new_finish;
534 std::fill(__pos, __old_finish, __x_copy);
535 }
536 }
537 catch(...)
538 {
539 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
540 __new_finish._M_node + 1);
541 __throw_exception_again;
542 }
543 }
544 }
546 template <typename _Tp, typename _Alloc>
547 template <typename _ForwardIterator>
548 void
549 deque<_Tp, _Alloc>::
550 _M_insert_aux(iterator __pos,
551 _ForwardIterator __first, _ForwardIterator __last,
552 size_type __n)
553 {
554 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
555 const size_type __length = size();
556 if (static_cast<size_type>(__elemsbefore) < __length / 2)
557 {
558 iterator __new_start = _M_reserve_elements_at_front(__n);
559 iterator __old_start = this->_M_impl._M_start;
560 __pos = this->_M_impl._M_start + __elemsbefore;
561 try
562 {
563 if (__elemsbefore >= difference_type(__n))
564 {
565 iterator __start_n = (this->_M_impl._M_start
566 + difference_type(__n));
567 std::__uninitialized_copy_a(this->_M_impl._M_start,
568 __start_n, __new_start,
569 _M_get_Tp_allocator());
570 this->_M_impl._M_start = __new_start;
571 std::copy(__start_n, __pos, __old_start);
572 std::copy(__first, __last, __pos - difference_type(__n));
573 }
574 else
575 {
576 _ForwardIterator __mid = __first;
577 std::advance(__mid, difference_type(__n) - __elemsbefore);
578 std::__uninitialized_copy_copy(this->_M_impl._M_start,
579 __pos, __first, __mid,
580 __new_start,
581 _M_get_Tp_allocator());
582 this->_M_impl._M_start = __new_start;
583 std::copy(__mid, __last, __old_start);
584 }
585 }
586 catch(...)
587 {
588 _M_destroy_nodes(__new_start._M_node,
589 this->_M_impl._M_start._M_node);
590 __throw_exception_again;
591 }
592 }
593 else
594 {
595 iterator __new_finish = _M_reserve_elements_at_back(__n);
596 iterator __old_finish = this->_M_impl._M_finish;
597 const difference_type __elemsafter =
598 difference_type(__length) - __elemsbefore;
599 __pos = this->_M_impl._M_finish - __elemsafter;
600 try
601 {
602 if (__elemsafter > difference_type(__n))
603 {
604 iterator __finish_n = (this->_M_impl._M_finish
605 - difference_type(__n));
606 std::__uninitialized_copy_a(__finish_n,
607 this->_M_impl._M_finish,
608 this->_M_impl._M_finish,
609 _M_get_Tp_allocator());
610 this->_M_impl._M_finish = __new_finish;
611 std::copy_backward(__pos, __finish_n, __old_finish);
612 std::copy(__first, __last, __pos);
613 }
614 else
615 {
616 _ForwardIterator __mid = __first;
617 std::advance(__mid, __elemsafter);
618 std::__uninitialized_copy_copy(__mid, __last, __pos,
619 this->_M_impl._M_finish,
620 this->_M_impl._M_finish,
621 _M_get_Tp_allocator());
622 this->_M_impl._M_finish = __new_finish;
623 std::copy(__first, __mid, __pos);
624 }
625 }
626 catch(...)
627 {
628 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
629 __new_finish._M_node + 1);
630 __throw_exception_again;
631 }
632 }
633 }
635 template<typename _Tp, typename _Alloc>
636 void
637 deque<_Tp, _Alloc>::
638 _M_destroy_data_aux(iterator __first, iterator __last)
639 {
640 for (_Map_pointer __node = __first._M_node + 1;
641 __node < __last._M_node; ++__node)
642 std::_Destroy(*__node, *__node + _S_buffer_size(),
643 _M_get_Tp_allocator());
645 if (__first._M_node != __last._M_node)
646 {
647 std::_Destroy(__first._M_cur, __first._M_last,
648 _M_get_Tp_allocator());
649 std::_Destroy(__last._M_first, __last._M_cur,
650 _M_get_Tp_allocator());
651 }
652 else
653 std::_Destroy(__first._M_cur, __last._M_cur,
654 _M_get_Tp_allocator());
655 }
657 template <typename _Tp, typename _Alloc>
658 void
659 deque<_Tp, _Alloc>::
660 _M_new_elements_at_front(size_type __new_elems)
661 {
662 const size_type __new_nodes
663 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
664 _M_reserve_map_at_front(__new_nodes);
665 size_type __i;
666 try
667 {
668 for (__i = 1; __i <= __new_nodes; ++__i)
669 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
670 }
671 catch(...)
672 {
673 for (size_type __j = 1; __j < __i; ++__j)
674 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
675 __throw_exception_again;
676 }
677 }
679 template <typename _Tp, typename _Alloc>
680 void
681 deque<_Tp, _Alloc>::
682 _M_new_elements_at_back(size_type __new_elems)
683 {
684 const size_type __new_nodes
685 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
686 _M_reserve_map_at_back(__new_nodes);
687 size_type __i;
688 try
689 {
690 for (__i = 1; __i <= __new_nodes; ++__i)
691 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
692 }
693 catch(...)
694 {
695 for (size_type __j = 1; __j < __i; ++__j)
696 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
697 __throw_exception_again;
698 }
699 }
701 template <typename _Tp, typename _Alloc>
702 void
703 deque<_Tp, _Alloc>::
704 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
705 {
706 const size_type __old_num_nodes
707 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
708 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
710 _Map_pointer __new_nstart;
711 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
712 {
713 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
714 - __new_num_nodes) / 2
715 + (__add_at_front ? __nodes_to_add : 0);
716 if (__new_nstart < this->_M_impl._M_start._M_node)
717 std::copy(this->_M_impl._M_start._M_node,
718 this->_M_impl._M_finish._M_node + 1,
719 __new_nstart);
720 else
721 std::copy_backward(this->_M_impl._M_start._M_node,
722 this->_M_impl._M_finish._M_node + 1,
723 __new_nstart + __old_num_nodes);
724 }
725 else
726 {
727 size_type __new_map_size = this->_M_impl._M_map_size
728 + std::max(this->_M_impl._M_map_size,
729 __nodes_to_add) + 2;
731 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
732 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
733 + (__add_at_front ? __nodes_to_add : 0);
734 std::copy(this->_M_impl._M_start._M_node,
735 this->_M_impl._M_finish._M_node + 1,
736 __new_nstart);
737 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
739 this->_M_impl._M_map = __new_map;
740 this->_M_impl._M_map_size = __new_map_size;
741 }
743 this->_M_impl._M_start._M_set_node(__new_nstart);
744 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
745 }
747 _GLIBCXX_END_NESTED_NAMESPACE
749 #endif