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