deque.tcc

Go to the documentation of this file.
00001 // Deque implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1997 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00056 /** @file deque.tcc 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 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 this->get_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 this->get_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 this->get_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 this->get_allocator()); 00188 std::_Destroy(this->_M_impl._M_finish._M_first, 00189 this->_M_impl._M_finish._M_cur, 00190 this->get_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 this->get_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 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 this->get_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 this->get_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, this->get_allocator()); 00273 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 00274 this->_M_impl._M_finish._M_cur, 00275 __value, this->get_allocator()); 00276 } 00277 catch(...) 00278 { 00279 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 00280 this->get_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 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 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 this->get_allocator()); 00326 __first = __mid; 00327 } 00328 std::__uninitialized_copy_a(__first, __last, 00329 this->_M_impl._M_finish._M_first, 00330 this->get_allocator()); 00331 } 00332 catch(...) 00333 { 00334 std::_Destroy(this->_M_impl._M_start, 00335 iterator(*__cur_node, __cur_node), 00336 this->get_allocator()); 00337 __throw_exception_again; 00338 } 00339 } 00340 00341 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 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 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 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 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 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 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 00400 // Note that if the deque has at least one element (a precondition for this 00401 // member function), and if 00402 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 00403 // then the deque must have at least two nodes. 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 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 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 this->get_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 this->get_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; // XXX copy 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 this->get_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 this->get_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 this->get_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 this->get_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 this->get_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 this->get_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 this->get_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 this->get_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 } // namespace std 00766 00767 #endif

Generated on Sun Sep 12 15:49:57 2004 for libstdc++ source by doxygen 1.3.8