00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00061 #ifndef _DEQUE_TCC
00062 #define _DEQUE_TCC 1
00063
00064 namespace _GLIBCXX_STD
00065 {
00066 template <typename _Tp, typename _Alloc>
00067 deque<_Tp, _Alloc>&
00068 deque<_Tp, _Alloc>::
00069 operator=(const deque& __x)
00070 {
00071 const size_type __len = size();
00072 if (&__x != this)
00073 {
00074 if (__len >= __x.size())
00075 erase(std::copy(__x.begin(), __x.end(), this->_M_impl._M_start),
00076 this->_M_impl._M_finish);
00077 else
00078 {
00079 const_iterator __mid = __x.begin() + difference_type(__len);
00080 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
00081 insert(this->_M_impl._M_finish, __mid, __x.end());
00082 }
00083 }
00084 return *this;
00085 }
00086
00087 template <typename _Tp, typename _Alloc>
00088 typename deque<_Tp, _Alloc>::iterator
00089 deque<_Tp, _Alloc>::
00090 insert(iterator position, const value_type& __x)
00091 {
00092 if (position._M_cur == this->_M_impl._M_start._M_cur)
00093 {
00094 push_front(__x);
00095 return this->_M_impl._M_start;
00096 }
00097 else if (position._M_cur == this->_M_impl._M_finish._M_cur)
00098 {
00099 push_back(__x);
00100 iterator __tmp = this->_M_impl._M_finish;
00101 --__tmp;
00102 return __tmp;
00103 }
00104 else
00105 return _M_insert_aux(position, __x);
00106 }
00107
00108 template <typename _Tp, typename _Alloc>
00109 typename deque<_Tp, _Alloc>::iterator
00110 deque<_Tp, _Alloc>::
00111 erase(iterator __position)
00112 {
00113 iterator __next = __position;
00114 ++__next;
00115 const size_type __index = __position - this->_M_impl._M_start;
00116 if (__index < (size() >> 1))
00117 {
00118 std::copy_backward(this->_M_impl._M_start, __position, __next);
00119 pop_front();
00120 }
00121 else
00122 {
00123 std::copy(__next, this->_M_impl._M_finish, __position);
00124 pop_back();
00125 }
00126 return this->_M_impl._M_start + __index;
00127 }
00128
00129 template <typename _Tp, typename _Alloc>
00130 typename deque<_Tp, _Alloc>::iterator
00131 deque<_Tp, _Alloc>::
00132 erase(iterator __first, iterator __last)
00133 {
00134 if (__first == this->_M_impl._M_start
00135 && __last == this->_M_impl._M_finish)
00136 {
00137 clear();
00138 return this->_M_impl._M_finish;
00139 }
00140 else
00141 {
00142 const difference_type __n = __last - __first;
00143 const difference_type __elems_before = (__first
00144 - this->_M_impl._M_start);
00145 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
00146 {
00147 std::copy_backward(this->_M_impl._M_start, __first, __last);
00148 iterator __new_start = this->_M_impl._M_start + __n;
00149 std::_Destroy(this->_M_impl._M_start, __new_start,
00150 _M_get_Tp_allocator());
00151 _M_destroy_nodes(this->_M_impl._M_start._M_node,
00152 __new_start._M_node);
00153 this->_M_impl._M_start = __new_start;
00154 }
00155 else
00156 {
00157 std::copy(__last, this->_M_impl._M_finish, __first);
00158 iterator __new_finish = this->_M_impl._M_finish - __n;
00159 std::_Destroy(__new_finish, this->_M_impl._M_finish,
00160 _M_get_Tp_allocator());
00161 _M_destroy_nodes(__new_finish._M_node + 1,
00162 this->_M_impl._M_finish._M_node + 1);
00163 this->_M_impl._M_finish = __new_finish;
00164 }
00165 return this->_M_impl._M_start + __elems_before;
00166 }
00167 }
00168
00169 template <typename _Tp, typename _Alloc>
00170 void
00171 deque<_Tp, _Alloc>::
00172 clear()
00173 {
00174 for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1;
00175 __node < this->_M_impl._M_finish._M_node;
00176 ++__node)
00177 {
00178 std::_Destroy(*__node, *__node + _S_buffer_size(),
00179 _M_get_Tp_allocator());
00180 _M_deallocate_node(*__node);
00181 }
00182
00183 if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node)
00184 {
00185 std::_Destroy(this->_M_impl._M_start._M_cur,
00186 this->_M_impl._M_start._M_last,
00187 _M_get_Tp_allocator());
00188 std::_Destroy(this->_M_impl._M_finish._M_first,
00189 this->_M_impl._M_finish._M_cur,
00190 _M_get_Tp_allocator());
00191 _M_deallocate_node(this->_M_impl._M_finish._M_first);
00192 }
00193 else
00194 std::_Destroy(this->_M_impl._M_start._M_cur,
00195 this->_M_impl._M_finish._M_cur,
00196 _M_get_Tp_allocator());
00197
00198 this->_M_impl._M_finish = this->_M_impl._M_start;
00199 }
00200
00201 template <typename _Tp, class _Alloc>
00202 template <typename _InputIterator>
00203 void
00204 deque<_Tp, _Alloc>::
00205 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00206 std::input_iterator_tag)
00207 {
00208 iterator __cur = begin();
00209 for (; __first != __last && __cur != end(); ++__cur, ++__first)
00210 *__cur = *__first;
00211 if (__first == __last)
00212 erase(__cur, end());
00213 else
00214 insert(end(), __first, __last);
00215 }
00216
00217 template <typename _Tp, typename _Alloc>
00218 void
00219 deque<_Tp, _Alloc>::
00220 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
00221 {
00222 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00223 {
00224 iterator __new_start = _M_reserve_elements_at_front(__n);
00225 try
00226 {
00227 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
00228 __x,
00229 _M_get_Tp_allocator());
00230 this->_M_impl._M_start = __new_start;
00231 }
00232 catch(...)
00233 {
00234 _M_destroy_nodes(__new_start._M_node,
00235 this->_M_impl._M_start._M_node);
00236 __throw_exception_again;
00237 }
00238 }
00239 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00240 {
00241 iterator __new_finish = _M_reserve_elements_at_back(__n);
00242 try
00243 {
00244 std::__uninitialized_fill_a(this->_M_impl._M_finish,
00245 __new_finish, __x,
00246 _M_get_Tp_allocator());
00247 this->_M_impl._M_finish = __new_finish;
00248 }
00249 catch(...)
00250 {
00251 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00252 __new_finish._M_node + 1);
00253 __throw_exception_again;
00254 }
00255 }
00256 else
00257 _M_insert_aux(__pos, __n, __x);
00258 }
00259
00260 template <typename _Tp, typename _Alloc>
00261 void
00262 deque<_Tp, _Alloc>::
00263 _M_fill_initialize(const value_type& __value)
00264 {
00265 _Map_pointer __cur;
00266 try
00267 {
00268 for (__cur = this->_M_impl._M_start._M_node;
00269 __cur < this->_M_impl._M_finish._M_node;
00270 ++__cur)
00271 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
00272 __value, _M_get_Tp_allocator());
00273 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
00274 this->_M_impl._M_finish._M_cur,
00275 __value, _M_get_Tp_allocator());
00276 }
00277 catch(...)
00278 {
00279 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
00280 _M_get_Tp_allocator());
00281 __throw_exception_again;
00282 }
00283 }
00284
00285 template <typename _Tp, typename _Alloc>
00286 template <typename _InputIterator>
00287 void
00288 deque<_Tp, _Alloc>::
00289 _M_range_initialize(_InputIterator __first, _InputIterator __last,
00290 std::input_iterator_tag)
00291 {
00292 this->_M_initialize_map(0);
00293 try
00294 {
00295 for (; __first != __last; ++__first)
00296 push_back(*__first);
00297 }
00298 catch(...)
00299 {
00300 clear();
00301 __throw_exception_again;
00302 }
00303 }
00304
00305 template <typename _Tp, typename _Alloc>
00306 template <typename _ForwardIterator>
00307 void
00308 deque<_Tp, _Alloc>::
00309 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00310 std::forward_iterator_tag)
00311 {
00312 const size_type __n = std::distance(__first, __last);
00313 this->_M_initialize_map(__n);
00314
00315 _Map_pointer __cur_node;
00316 try
00317 {
00318 for (__cur_node = this->_M_impl._M_start._M_node;
00319 __cur_node < this->_M_impl._M_finish._M_node;
00320 ++__cur_node)
00321 {
00322 _ForwardIterator __mid = __first;
00323 std::advance(__mid, _S_buffer_size());
00324 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
00325 _M_get_Tp_allocator());
00326 __first = __mid;
00327 }
00328 std::__uninitialized_copy_a(__first, __last,
00329 this->_M_impl._M_finish._M_first,
00330 _M_get_Tp_allocator());
00331 }
00332 catch(...)
00333 {
00334 std::_Destroy(this->_M_impl._M_start,
00335 iterator(*__cur_node, __cur_node),
00336 _M_get_Tp_allocator());
00337 __throw_exception_again;
00338 }
00339 }
00340
00341
00342 template <typename _Tp, typename _Alloc>
00343 void
00344 deque<_Tp, _Alloc>::
00345 _M_push_back_aux(const value_type& __t)
00346 {
00347 value_type __t_copy = __t;
00348 _M_reserve_map_at_back();
00349 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
00350 try
00351 {
00352 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy);
00353 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
00354 + 1);
00355 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
00356 }
00357 catch(...)
00358 {
00359 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
00360 __throw_exception_again;
00361 }
00362 }
00363
00364
00365 template <typename _Tp, typename _Alloc>
00366 void
00367 deque<_Tp, _Alloc>::
00368 _M_push_front_aux(const value_type& __t)
00369 {
00370 value_type __t_copy = __t;
00371 _M_reserve_map_at_front();
00372 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
00373 try
00374 {
00375 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
00376 - 1);
00377 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
00378 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy);
00379 }
00380 catch(...)
00381 {
00382 ++this->_M_impl._M_start;
00383 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
00384 __throw_exception_again;
00385 }
00386 }
00387
00388
00389 template <typename _Tp, typename _Alloc>
00390 void deque<_Tp, _Alloc>::
00391 _M_pop_back_aux()
00392 {
00393 _M_deallocate_node(this->_M_impl._M_finish._M_first);
00394 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
00395 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
00396 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
00397 }
00398
00399
00400
00401
00402
00403
00404 template <typename _Tp, typename _Alloc>
00405 void deque<_Tp, _Alloc>::
00406 _M_pop_front_aux()
00407 {
00408 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
00409 _M_deallocate_node(this->_M_impl._M_start._M_first);
00410 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
00411 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
00412 }
00413
00414 template <typename _Tp, typename _Alloc>
00415 template <typename _InputIterator>
00416 void
00417 deque<_Tp, _Alloc>::
00418 _M_range_insert_aux(iterator __pos,
00419 _InputIterator __first, _InputIterator __last,
00420 std::input_iterator_tag)
00421 { std::copy(__first, __last, std::inserter(*this, __pos)); }
00422
00423 template <typename _Tp, typename _Alloc>
00424 template <typename _ForwardIterator>
00425 void
00426 deque<_Tp, _Alloc>::
00427 _M_range_insert_aux(iterator __pos,
00428 _ForwardIterator __first, _ForwardIterator __last,
00429 std::forward_iterator_tag)
00430 {
00431 const size_type __n = std::distance(__first, __last);
00432 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00433 {
00434 iterator __new_start = _M_reserve_elements_at_front(__n);
00435 try
00436 {
00437 std::__uninitialized_copy_a(__first, __last, __new_start,
00438 _M_get_Tp_allocator());
00439 this->_M_impl._M_start = __new_start;
00440 }
00441 catch(...)
00442 {
00443 _M_destroy_nodes(__new_start._M_node,
00444 this->_M_impl._M_start._M_node);
00445 __throw_exception_again;
00446 }
00447 }
00448 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00449 {
00450 iterator __new_finish = _M_reserve_elements_at_back(__n);
00451 try
00452 {
00453 std::__uninitialized_copy_a(__first, __last,
00454 this->_M_impl._M_finish,
00455 _M_get_Tp_allocator());
00456 this->_M_impl._M_finish = __new_finish;
00457 }
00458 catch(...)
00459 {
00460 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00461 __new_finish._M_node + 1);
00462 __throw_exception_again;
00463 }
00464 }
00465 else
00466 _M_insert_aux(__pos, __first, __last, __n);
00467 }
00468
00469 template <typename _Tp, typename _Alloc>
00470 typename deque<_Tp, _Alloc>::iterator
00471 deque<_Tp, _Alloc>::
00472 _M_insert_aux(iterator __pos, const value_type& __x)
00473 {
00474 difference_type __index = __pos - this->_M_impl._M_start;
00475 value_type __x_copy = __x;
00476 if (static_cast<size_type>(__index) < size() / 2)
00477 {
00478 push_front(front());
00479 iterator __front1 = this->_M_impl._M_start;
00480 ++__front1;
00481 iterator __front2 = __front1;
00482 ++__front2;
00483 __pos = this->_M_impl._M_start + __index;
00484 iterator __pos1 = __pos;
00485 ++__pos1;
00486 std::copy(__front2, __pos1, __front1);
00487 }
00488 else
00489 {
00490 push_back(back());
00491 iterator __back1 = this->_M_impl._M_finish;
00492 --__back1;
00493 iterator __back2 = __back1;
00494 --__back2;
00495 __pos = this->_M_impl._M_start + __index;
00496 std::copy_backward(__pos, __back2, __back1);
00497 }
00498 *__pos = __x_copy;
00499 return __pos;
00500 }
00501
00502 template <typename _Tp, typename _Alloc>
00503 void
00504 deque<_Tp, _Alloc>::
00505 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
00506 {
00507 const difference_type __elems_before = __pos - this->_M_impl._M_start;
00508 const size_type __length = this->size();
00509 value_type __x_copy = __x;
00510 if (__elems_before < difference_type(__length / 2))
00511 {
00512 iterator __new_start = _M_reserve_elements_at_front(__n);
00513 iterator __old_start = this->_M_impl._M_start;
00514 __pos = this->_M_impl._M_start + __elems_before;
00515 try
00516 {
00517 if (__elems_before >= difference_type(__n))
00518 {
00519 iterator __start_n = (this->_M_impl._M_start
00520 + difference_type(__n));
00521 std::__uninitialized_copy_a(this->_M_impl._M_start,
00522 __start_n, __new_start,
00523 _M_get_Tp_allocator());
00524 this->_M_impl._M_start = __new_start;
00525 std::copy(__start_n, __pos, __old_start);
00526 fill(__pos - difference_type(__n), __pos, __x_copy);
00527 }
00528 else
00529 {
00530 std::__uninitialized_copy_fill(this->_M_impl._M_start,
00531 __pos, __new_start,
00532 this->_M_impl._M_start,
00533 __x_copy,
00534 _M_get_Tp_allocator());
00535 this->_M_impl._M_start = __new_start;
00536 std::fill(__old_start, __pos, __x_copy);
00537 }
00538 }
00539 catch(...)
00540 {
00541 _M_destroy_nodes(__new_start._M_node,
00542 this->_M_impl._M_start._M_node);
00543 __throw_exception_again;
00544 }
00545 }
00546 else
00547 {
00548 iterator __new_finish = _M_reserve_elements_at_back(__n);
00549 iterator __old_finish = this->_M_impl._M_finish;
00550 const difference_type __elems_after =
00551 difference_type(__length) - __elems_before;
00552 __pos = this->_M_impl._M_finish - __elems_after;
00553 try
00554 {
00555 if (__elems_after > difference_type(__n))
00556 {
00557 iterator __finish_n = (this->_M_impl._M_finish
00558 - difference_type(__n));
00559 std::__uninitialized_copy_a(__finish_n,
00560 this->_M_impl._M_finish,
00561 this->_M_impl._M_finish,
00562 _M_get_Tp_allocator());
00563 this->_M_impl._M_finish = __new_finish;
00564 std::copy_backward(__pos, __finish_n, __old_finish);
00565 std::fill(__pos, __pos + difference_type(__n), __x_copy);
00566 }
00567 else
00568 {
00569 std::__uninitialized_fill_copy(this->_M_impl._M_finish,
00570 __pos + difference_type(__n),
00571 __x_copy, __pos,
00572 this->_M_impl._M_finish,
00573 _M_get_Tp_allocator());
00574 this->_M_impl._M_finish = __new_finish;
00575 std::fill(__pos, __old_finish, __x_copy);
00576 }
00577 }
00578 catch(...)
00579 {
00580 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00581 __new_finish._M_node + 1);
00582 __throw_exception_again;
00583 }
00584 }
00585 }
00586
00587 template <typename _Tp, typename _Alloc>
00588 template <typename _ForwardIterator>
00589 void
00590 deque<_Tp, _Alloc>::
00591 _M_insert_aux(iterator __pos,
00592 _ForwardIterator __first, _ForwardIterator __last,
00593 size_type __n)
00594 {
00595 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
00596 const size_type __length = size();
00597 if (static_cast<size_type>(__elemsbefore) < __length / 2)
00598 {
00599 iterator __new_start = _M_reserve_elements_at_front(__n);
00600 iterator __old_start = this->_M_impl._M_start;
00601 __pos = this->_M_impl._M_start + __elemsbefore;
00602 try
00603 {
00604 if (__elemsbefore >= difference_type(__n))
00605 {
00606 iterator __start_n = (this->_M_impl._M_start
00607 + difference_type(__n));
00608 std::__uninitialized_copy_a(this->_M_impl._M_start,
00609 __start_n, __new_start,
00610 _M_get_Tp_allocator());
00611 this->_M_impl._M_start = __new_start;
00612 std::copy(__start_n, __pos, __old_start);
00613 std::copy(__first, __last, __pos - difference_type(__n));
00614 }
00615 else
00616 {
00617 _ForwardIterator __mid = __first;
00618 std::advance(__mid, difference_type(__n) - __elemsbefore);
00619 std::__uninitialized_copy_copy(this->_M_impl._M_start,
00620 __pos, __first, __mid,
00621 __new_start,
00622 _M_get_Tp_allocator());
00623 this->_M_impl._M_start = __new_start;
00624 std::copy(__mid, __last, __old_start);
00625 }
00626 }
00627 catch(...)
00628 {
00629 _M_destroy_nodes(__new_start._M_node,
00630 this->_M_impl._M_start._M_node);
00631 __throw_exception_again;
00632 }
00633 }
00634 else
00635 {
00636 iterator __new_finish = _M_reserve_elements_at_back(__n);
00637 iterator __old_finish = this->_M_impl._M_finish;
00638 const difference_type __elemsafter =
00639 difference_type(__length) - __elemsbefore;
00640 __pos = this->_M_impl._M_finish - __elemsafter;
00641 try
00642 {
00643 if (__elemsafter > difference_type(__n))
00644 {
00645 iterator __finish_n = (this->_M_impl._M_finish
00646 - difference_type(__n));
00647 std::__uninitialized_copy_a(__finish_n,
00648 this->_M_impl._M_finish,
00649 this->_M_impl._M_finish,
00650 _M_get_Tp_allocator());
00651 this->_M_impl._M_finish = __new_finish;
00652 std::copy_backward(__pos, __finish_n, __old_finish);
00653 std::copy(__first, __last, __pos);
00654 }
00655 else
00656 {
00657 _ForwardIterator __mid = __first;
00658 std::advance(__mid, __elemsafter);
00659 std::__uninitialized_copy_copy(__mid, __last, __pos,
00660 this->_M_impl._M_finish,
00661 this->_M_impl._M_finish,
00662 _M_get_Tp_allocator());
00663 this->_M_impl._M_finish = __new_finish;
00664 std::copy(__first, __mid, __pos);
00665 }
00666 }
00667 catch(...)
00668 {
00669 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00670 __new_finish._M_node + 1);
00671 __throw_exception_again;
00672 }
00673 }
00674 }
00675
00676 template <typename _Tp, typename _Alloc>
00677 void
00678 deque<_Tp, _Alloc>::
00679 _M_new_elements_at_front(size_type __new_elems)
00680 {
00681 const size_type __new_nodes
00682 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
00683 _M_reserve_map_at_front(__new_nodes);
00684 size_type __i;
00685 try
00686 {
00687 for (__i = 1; __i <= __new_nodes; ++__i)
00688 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
00689 }
00690 catch(...)
00691 {
00692 for (size_type __j = 1; __j < __i; ++__j)
00693 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
00694 __throw_exception_again;
00695 }
00696 }
00697
00698 template <typename _Tp, typename _Alloc>
00699 void
00700 deque<_Tp, _Alloc>::
00701 _M_new_elements_at_back(size_type __new_elems)
00702 {
00703 const size_type __new_nodes
00704 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
00705 _M_reserve_map_at_back(__new_nodes);
00706 size_type __i;
00707 try
00708 {
00709 for (__i = 1; __i <= __new_nodes; ++__i)
00710 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
00711 }
00712 catch(...)
00713 {
00714 for (size_type __j = 1; __j < __i; ++__j)
00715 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
00716 __throw_exception_again;
00717 }
00718 }
00719
00720 template <typename _Tp, typename _Alloc>
00721 void
00722 deque<_Tp, _Alloc>::
00723 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
00724 {
00725 const size_type __old_num_nodes
00726 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
00727 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
00728
00729 _Map_pointer __new_nstart;
00730 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
00731 {
00732 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
00733 - __new_num_nodes) / 2
00734 + (__add_at_front ? __nodes_to_add : 0);
00735 if (__new_nstart < this->_M_impl._M_start._M_node)
00736 std::copy(this->_M_impl._M_start._M_node,
00737 this->_M_impl._M_finish._M_node + 1,
00738 __new_nstart);
00739 else
00740 std::copy_backward(this->_M_impl._M_start._M_node,
00741 this->_M_impl._M_finish._M_node + 1,
00742 __new_nstart + __old_num_nodes);
00743 }
00744 else
00745 {
00746 size_type __new_map_size = this->_M_impl._M_map_size
00747 + std::max(this->_M_impl._M_map_size,
00748 __nodes_to_add) + 2;
00749
00750 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
00751 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
00752 + (__add_at_front ? __nodes_to_add : 0);
00753 std::copy(this->_M_impl._M_start._M_node,
00754 this->_M_impl._M_finish._M_node + 1,
00755 __new_nstart);
00756 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00757
00758 this->_M_impl._M_map = __new_map;
00759 this->_M_impl._M_map_size = __new_map_size;
00760 }
00761
00762 this->_M_impl._M_start._M_set_node(__new_nstart);
00763 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
00764 }
00765 }
00766
00767 #endif