libstdc++
|
00001 // Deque implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1997 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file deque.tcc 00053 * This is an internal header file, included by other library headers. 00054 * You should not attempt to use it directly. 00055 */ 00056 00057 #ifndef _DEQUE_TCC 00058 #define _DEQUE_TCC 1 00059 00060 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 00061 00062 template <typename _Tp, typename _Alloc> 00063 deque<_Tp, _Alloc>& 00064 deque<_Tp, _Alloc>:: 00065 operator=(const deque& __x) 00066 { 00067 const size_type __len = size(); 00068 if (&__x != this) 00069 { 00070 if (__len >= __x.size()) 00071 _M_erase_at_end(std::copy(__x.begin(), __x.end(), 00072 this->_M_impl._M_start)); 00073 else 00074 { 00075 const_iterator __mid = __x.begin() + difference_type(__len); 00076 std::copy(__x.begin(), __mid, this->_M_impl._M_start); 00077 insert(this->_M_impl._M_finish, __mid, __x.end()); 00078 } 00079 } 00080 return *this; 00081 } 00082 00083 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00084 template<typename _Tp, typename _Alloc> 00085 template<typename... _Args> 00086 void 00087 deque<_Tp, _Alloc>:: 00088 emplace_front(_Args&&... __args) 00089 { 00090 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) 00091 { 00092 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, 00093 std::forward<_Args>(__args)...); 00094 --this->_M_impl._M_start._M_cur; 00095 } 00096 else 00097 _M_push_front_aux(std::forward<_Args>(__args)...); 00098 } 00099 00100 template<typename _Tp, typename _Alloc> 00101 template<typename... _Args> 00102 void 00103 deque<_Tp, _Alloc>:: 00104 emplace_back(_Args&&... __args) 00105 { 00106 if (this->_M_impl._M_finish._M_cur 00107 != this->_M_impl._M_finish._M_last - 1) 00108 { 00109 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, 00110 std::forward<_Args>(__args)...); 00111 ++this->_M_impl._M_finish._M_cur; 00112 } 00113 else 00114 _M_push_back_aux(std::forward<_Args>(__args)...); 00115 } 00116 #endif 00117 00118 template <typename _Tp, typename _Alloc> 00119 typename deque<_Tp, _Alloc>::iterator 00120 deque<_Tp, _Alloc>:: 00121 insert(iterator __position, const value_type& __x) 00122 { 00123 if (__position._M_cur == this->_M_impl._M_start._M_cur) 00124 { 00125 push_front(__x); 00126 return this->_M_impl._M_start; 00127 } 00128 else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 00129 { 00130 push_back(__x); 00131 iterator __tmp = this->_M_impl._M_finish; 00132 --__tmp; 00133 return __tmp; 00134 } 00135 else 00136 return _M_insert_aux(__position, __x); 00137 } 00138 00139 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00140 template<typename _Tp, typename _Alloc> 00141 template<typename... _Args> 00142 typename deque<_Tp, _Alloc>::iterator 00143 deque<_Tp, _Alloc>:: 00144 emplace(iterator __position, _Args&&... __args) 00145 { 00146 if (__position._M_cur == this->_M_impl._M_start._M_cur) 00147 { 00148 push_front(std::forward<_Args>(__args)...); 00149 return this->_M_impl._M_start; 00150 } 00151 else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 00152 { 00153 push_back(std::forward<_Args>(__args)...); 00154 iterator __tmp = this->_M_impl._M_finish; 00155 --__tmp; 00156 return __tmp; 00157 } 00158 else 00159 return _M_insert_aux(__position, std::forward<_Args>(__args)...); 00160 } 00161 #endif 00162 00163 template <typename _Tp, typename _Alloc> 00164 typename deque<_Tp, _Alloc>::iterator 00165 deque<_Tp, _Alloc>:: 00166 erase(iterator __position) 00167 { 00168 iterator __next = __position; 00169 ++__next; 00170 const difference_type __index = __position - begin(); 00171 if (static_cast<size_type>(__index) < (size() >> 1)) 00172 { 00173 if (__position != begin()) 00174 _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next); 00175 pop_front(); 00176 } 00177 else 00178 { 00179 if (__next != end()) 00180 _GLIBCXX_MOVE3(__next, end(), __position); 00181 pop_back(); 00182 } 00183 return begin() + __index; 00184 } 00185 00186 template <typename _Tp, typename _Alloc> 00187 typename deque<_Tp, _Alloc>::iterator 00188 deque<_Tp, _Alloc>:: 00189 erase(iterator __first, iterator __last) 00190 { 00191 if (__first == begin() && __last == end()) 00192 { 00193 clear(); 00194 return end(); 00195 } 00196 else 00197 { 00198 const difference_type __n = __last - __first; 00199 const difference_type __elems_before = __first - begin(); 00200 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) 00201 { 00202 if (__first != begin()) 00203 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); 00204 _M_erase_at_begin(begin() + __n); 00205 } 00206 else 00207 { 00208 if (__last != end()) 00209 _GLIBCXX_MOVE3(__last, end(), __first); 00210 _M_erase_at_end(end() - __n); 00211 } 00212 return begin() + __elems_before; 00213 } 00214 } 00215 00216 template <typename _Tp, class _Alloc> 00217 template <typename _InputIterator> 00218 void 00219 deque<_Tp, _Alloc>:: 00220 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00221 std::input_iterator_tag) 00222 { 00223 iterator __cur = begin(); 00224 for (; __first != __last && __cur != end(); ++__cur, ++__first) 00225 *__cur = *__first; 00226 if (__first == __last) 00227 _M_erase_at_end(__cur); 00228 else 00229 insert(end(), __first, __last); 00230 } 00231 00232 template <typename _Tp, typename _Alloc> 00233 void 00234 deque<_Tp, _Alloc>:: 00235 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 00236 { 00237 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00238 { 00239 iterator __new_start = _M_reserve_elements_at_front(__n); 00240 __try 00241 { 00242 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, 00243 __x, _M_get_Tp_allocator()); 00244 this->_M_impl._M_start = __new_start; 00245 } 00246 __catch(...) 00247 { 00248 _M_destroy_nodes(__new_start._M_node, 00249 this->_M_impl._M_start._M_node); 00250 __throw_exception_again; 00251 } 00252 } 00253 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00254 { 00255 iterator __new_finish = _M_reserve_elements_at_back(__n); 00256 __try 00257 { 00258 std::__uninitialized_fill_a(this->_M_impl._M_finish, 00259 __new_finish, __x, 00260 _M_get_Tp_allocator()); 00261 this->_M_impl._M_finish = __new_finish; 00262 } 00263 __catch(...) 00264 { 00265 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00266 __new_finish._M_node + 1); 00267 __throw_exception_again; 00268 } 00269 } 00270 else 00271 _M_insert_aux(__pos, __n, __x); 00272 } 00273 00274 template <typename _Tp, typename _Alloc> 00275 void 00276 deque<_Tp, _Alloc>:: 00277 _M_fill_initialize(const value_type& __value) 00278 { 00279 _Map_pointer __cur; 00280 __try 00281 { 00282 for (__cur = this->_M_impl._M_start._M_node; 00283 __cur < this->_M_impl._M_finish._M_node; 00284 ++__cur) 00285 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), 00286 __value, _M_get_Tp_allocator()); 00287 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 00288 this->_M_impl._M_finish._M_cur, 00289 __value, _M_get_Tp_allocator()); 00290 } 00291 __catch(...) 00292 { 00293 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 00294 _M_get_Tp_allocator()); 00295 __throw_exception_again; 00296 } 00297 } 00298 00299 template <typename _Tp, typename _Alloc> 00300 template <typename _InputIterator> 00301 void 00302 deque<_Tp, _Alloc>:: 00303 _M_range_initialize(_InputIterator __first, _InputIterator __last, 00304 std::input_iterator_tag) 00305 { 00306 this->_M_initialize_map(0); 00307 __try 00308 { 00309 for (; __first != __last; ++__first) 00310 push_back(*__first); 00311 } 00312 __catch(...) 00313 { 00314 clear(); 00315 __throw_exception_again; 00316 } 00317 } 00318 00319 template <typename _Tp, typename _Alloc> 00320 template <typename _ForwardIterator> 00321 void 00322 deque<_Tp, _Alloc>:: 00323 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 00324 std::forward_iterator_tag) 00325 { 00326 const size_type __n = std::distance(__first, __last); 00327 this->_M_initialize_map(__n); 00328 00329 _Map_pointer __cur_node; 00330 __try 00331 { 00332 for (__cur_node = this->_M_impl._M_start._M_node; 00333 __cur_node < this->_M_impl._M_finish._M_node; 00334 ++__cur_node) 00335 { 00336 _ForwardIterator __mid = __first; 00337 std::advance(__mid, _S_buffer_size()); 00338 std::__uninitialized_copy_a(__first, __mid, *__cur_node, 00339 _M_get_Tp_allocator()); 00340 __first = __mid; 00341 } 00342 std::__uninitialized_copy_a(__first, __last, 00343 this->_M_impl._M_finish._M_first, 00344 _M_get_Tp_allocator()); 00345 } 00346 __catch(...) 00347 { 00348 std::_Destroy(this->_M_impl._M_start, 00349 iterator(*__cur_node, __cur_node), 00350 _M_get_Tp_allocator()); 00351 __throw_exception_again; 00352 } 00353 } 00354 00355 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 00356 template<typename _Tp, typename _Alloc> 00357 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00358 template<typename... _Args> 00359 void 00360 deque<_Tp, _Alloc>:: 00361 _M_push_back_aux(_Args&&... __args) 00362 #else 00363 void 00364 deque<_Tp, _Alloc>:: 00365 _M_push_back_aux(const value_type& __t) 00366 #endif 00367 { 00368 _M_reserve_map_at_back(); 00369 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 00370 __try 00371 { 00372 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00373 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, 00374 std::forward<_Args>(__args)...); 00375 #else 00376 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); 00377 #endif 00378 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 00379 + 1); 00380 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 00381 } 00382 __catch(...) 00383 { 00384 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 00385 __throw_exception_again; 00386 } 00387 } 00388 00389 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 00390 template<typename _Tp, typename _Alloc> 00391 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00392 template<typename... _Args> 00393 void 00394 deque<_Tp, _Alloc>:: 00395 _M_push_front_aux(_Args&&... __args) 00396 #else 00397 void 00398 deque<_Tp, _Alloc>:: 00399 _M_push_front_aux(const value_type& __t) 00400 #endif 00401 { 00402 _M_reserve_map_at_front(); 00403 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 00404 __try 00405 { 00406 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 00407 - 1); 00408 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 00409 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00410 this->_M_impl.construct(this->_M_impl._M_start._M_cur, 00411 std::forward<_Args>(__args)...); 00412 #else 00413 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); 00414 #endif 00415 } 00416 __catch(...) 00417 { 00418 ++this->_M_impl._M_start; 00419 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 00420 __throw_exception_again; 00421 } 00422 } 00423 00424 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 00425 template <typename _Tp, typename _Alloc> 00426 void deque<_Tp, _Alloc>:: 00427 _M_pop_back_aux() 00428 { 00429 _M_deallocate_node(this->_M_impl._M_finish._M_first); 00430 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 00431 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 00432 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); 00433 } 00434 00435 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 00436 // Note that if the deque has at least one element (a precondition for this 00437 // member function), and if 00438 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 00439 // then the deque must have at least two nodes. 00440 template <typename _Tp, typename _Alloc> 00441 void deque<_Tp, _Alloc>:: 00442 _M_pop_front_aux() 00443 { 00444 this->_M_impl.destroy(this->_M_impl._M_start._M_cur); 00445 _M_deallocate_node(this->_M_impl._M_start._M_first); 00446 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 00447 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 00448 } 00449 00450 template <typename _Tp, typename _Alloc> 00451 template <typename _InputIterator> 00452 void 00453 deque<_Tp, _Alloc>:: 00454 _M_range_insert_aux(iterator __pos, 00455 _InputIterator __first, _InputIterator __last, 00456 std::input_iterator_tag) 00457 { std::copy(__first, __last, std::inserter(*this, __pos)); } 00458 00459 template <typename _Tp, typename _Alloc> 00460 template <typename _ForwardIterator> 00461 void 00462 deque<_Tp, _Alloc>:: 00463 _M_range_insert_aux(iterator __pos, 00464 _ForwardIterator __first, _ForwardIterator __last, 00465 std::forward_iterator_tag) 00466 { 00467 const size_type __n = std::distance(__first, __last); 00468 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00469 { 00470 iterator __new_start = _M_reserve_elements_at_front(__n); 00471 __try 00472 { 00473 std::__uninitialized_copy_a(__first, __last, __new_start, 00474 _M_get_Tp_allocator()); 00475 this->_M_impl._M_start = __new_start; 00476 } 00477 __catch(...) 00478 { 00479 _M_destroy_nodes(__new_start._M_node, 00480 this->_M_impl._M_start._M_node); 00481 __throw_exception_again; 00482 } 00483 } 00484 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00485 { 00486 iterator __new_finish = _M_reserve_elements_at_back(__n); 00487 __try 00488 { 00489 std::__uninitialized_copy_a(__first, __last, 00490 this->_M_impl._M_finish, 00491 _M_get_Tp_allocator()); 00492 this->_M_impl._M_finish = __new_finish; 00493 } 00494 __catch(...) 00495 { 00496 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00497 __new_finish._M_node + 1); 00498 __throw_exception_again; 00499 } 00500 } 00501 else 00502 _M_insert_aux(__pos, __first, __last, __n); 00503 } 00504 00505 template<typename _Tp, typename _Alloc> 00506 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00507 template<typename... _Args> 00508 typename deque<_Tp, _Alloc>::iterator 00509 deque<_Tp, _Alloc>:: 00510 _M_insert_aux(iterator __pos, _Args&&... __args) 00511 { 00512 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy 00513 #else 00514 typename deque<_Tp, _Alloc>::iterator 00515 deque<_Tp, _Alloc>:: 00516 _M_insert_aux(iterator __pos, const value_type& __x) 00517 { 00518 value_type __x_copy = __x; // XXX copy 00519 #endif 00520 difference_type __index = __pos - this->_M_impl._M_start; 00521 if (static_cast<size_type>(__index) < size() / 2) 00522 { 00523 push_front(_GLIBCXX_MOVE(front())); 00524 iterator __front1 = this->_M_impl._M_start; 00525 ++__front1; 00526 iterator __front2 = __front1; 00527 ++__front2; 00528 __pos = this->_M_impl._M_start + __index; 00529 iterator __pos1 = __pos; 00530 ++__pos1; 00531 _GLIBCXX_MOVE3(__front2, __pos1, __front1); 00532 } 00533 else 00534 { 00535 push_back(_GLIBCXX_MOVE(back())); 00536 iterator __back1 = this->_M_impl._M_finish; 00537 --__back1; 00538 iterator __back2 = __back1; 00539 --__back2; 00540 __pos = this->_M_impl._M_start + __index; 00541 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); 00542 } 00543 *__pos = _GLIBCXX_MOVE(__x_copy); 00544 return __pos; 00545 } 00546 00547 template <typename _Tp, typename _Alloc> 00548 void 00549 deque<_Tp, _Alloc>:: 00550 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 00551 { 00552 const difference_type __elems_before = __pos - this->_M_impl._M_start; 00553 const size_type __length = this->size(); 00554 value_type __x_copy = __x; 00555 if (__elems_before < difference_type(__length / 2)) 00556 { 00557 iterator __new_start = _M_reserve_elements_at_front(__n); 00558 iterator __old_start = this->_M_impl._M_start; 00559 __pos = this->_M_impl._M_start + __elems_before; 00560 __try 00561 { 00562 if (__elems_before >= difference_type(__n)) 00563 { 00564 iterator __start_n = (this->_M_impl._M_start 00565 + difference_type(__n)); 00566 std::__uninitialized_move_a(this->_M_impl._M_start, 00567 __start_n, __new_start, 00568 _M_get_Tp_allocator()); 00569 this->_M_impl._M_start = __new_start; 00570 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 00571 std::fill(__pos - difference_type(__n), __pos, __x_copy); 00572 } 00573 else 00574 { 00575 std::__uninitialized_move_fill(this->_M_impl._M_start, 00576 __pos, __new_start, 00577 this->_M_impl._M_start, 00578 __x_copy, 00579 _M_get_Tp_allocator()); 00580 this->_M_impl._M_start = __new_start; 00581 std::fill(__old_start, __pos, __x_copy); 00582 } 00583 } 00584 __catch(...) 00585 { 00586 _M_destroy_nodes(__new_start._M_node, 00587 this->_M_impl._M_start._M_node); 00588 __throw_exception_again; 00589 } 00590 } 00591 else 00592 { 00593 iterator __new_finish = _M_reserve_elements_at_back(__n); 00594 iterator __old_finish = this->_M_impl._M_finish; 00595 const difference_type __elems_after = 00596 difference_type(__length) - __elems_before; 00597 __pos = this->_M_impl._M_finish - __elems_after; 00598 __try 00599 { 00600 if (__elems_after > difference_type(__n)) 00601 { 00602 iterator __finish_n = (this->_M_impl._M_finish 00603 - difference_type(__n)); 00604 std::__uninitialized_move_a(__finish_n, 00605 this->_M_impl._M_finish, 00606 this->_M_impl._M_finish, 00607 _M_get_Tp_allocator()); 00608 this->_M_impl._M_finish = __new_finish; 00609 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 00610 std::fill(__pos, __pos + difference_type(__n), __x_copy); 00611 } 00612 else 00613 { 00614 std::__uninitialized_fill_move(this->_M_impl._M_finish, 00615 __pos + difference_type(__n), 00616 __x_copy, __pos, 00617 this->_M_impl._M_finish, 00618 _M_get_Tp_allocator()); 00619 this->_M_impl._M_finish = __new_finish; 00620 std::fill(__pos, __old_finish, __x_copy); 00621 } 00622 } 00623 __catch(...) 00624 { 00625 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00626 __new_finish._M_node + 1); 00627 __throw_exception_again; 00628 } 00629 } 00630 } 00631 00632 template <typename _Tp, typename _Alloc> 00633 template <typename _ForwardIterator> 00634 void 00635 deque<_Tp, _Alloc>:: 00636 _M_insert_aux(iterator __pos, 00637 _ForwardIterator __first, _ForwardIterator __last, 00638 size_type __n) 00639 { 00640 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 00641 const size_type __length = size(); 00642 if (static_cast<size_type>(__elemsbefore) < __length / 2) 00643 { 00644 iterator __new_start = _M_reserve_elements_at_front(__n); 00645 iterator __old_start = this->_M_impl._M_start; 00646 __pos = this->_M_impl._M_start + __elemsbefore; 00647 __try 00648 { 00649 if (__elemsbefore >= difference_type(__n)) 00650 { 00651 iterator __start_n = (this->_M_impl._M_start 00652 + difference_type(__n)); 00653 std::__uninitialized_move_a(this->_M_impl._M_start, 00654 __start_n, __new_start, 00655 _M_get_Tp_allocator()); 00656 this->_M_impl._M_start = __new_start; 00657 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 00658 std::copy(__first, __last, __pos - difference_type(__n)); 00659 } 00660 else 00661 { 00662 _ForwardIterator __mid = __first; 00663 std::advance(__mid, difference_type(__n) - __elemsbefore); 00664 std::__uninitialized_move_copy(this->_M_impl._M_start, 00665 __pos, __first, __mid, 00666 __new_start, 00667 _M_get_Tp_allocator()); 00668 this->_M_impl._M_start = __new_start; 00669 std::copy(__mid, __last, __old_start); 00670 } 00671 } 00672 __catch(...) 00673 { 00674 _M_destroy_nodes(__new_start._M_node, 00675 this->_M_impl._M_start._M_node); 00676 __throw_exception_again; 00677 } 00678 } 00679 else 00680 { 00681 iterator __new_finish = _M_reserve_elements_at_back(__n); 00682 iterator __old_finish = this->_M_impl._M_finish; 00683 const difference_type __elemsafter = 00684 difference_type(__length) - __elemsbefore; 00685 __pos = this->_M_impl._M_finish - __elemsafter; 00686 __try 00687 { 00688 if (__elemsafter > difference_type(__n)) 00689 { 00690 iterator __finish_n = (this->_M_impl._M_finish 00691 - difference_type(__n)); 00692 std::__uninitialized_move_a(__finish_n, 00693 this->_M_impl._M_finish, 00694 this->_M_impl._M_finish, 00695 _M_get_Tp_allocator()); 00696 this->_M_impl._M_finish = __new_finish; 00697 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 00698 std::copy(__first, __last, __pos); 00699 } 00700 else 00701 { 00702 _ForwardIterator __mid = __first; 00703 std::advance(__mid, __elemsafter); 00704 std::__uninitialized_copy_move(__mid, __last, __pos, 00705 this->_M_impl._M_finish, 00706 this->_M_impl._M_finish, 00707 _M_get_Tp_allocator()); 00708 this->_M_impl._M_finish = __new_finish; 00709 std::copy(__first, __mid, __pos); 00710 } 00711 } 00712 __catch(...) 00713 { 00714 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00715 __new_finish._M_node + 1); 00716 __throw_exception_again; 00717 } 00718 } 00719 } 00720 00721 template<typename _Tp, typename _Alloc> 00722 void 00723 deque<_Tp, _Alloc>:: 00724 _M_destroy_data_aux(iterator __first, iterator __last) 00725 { 00726 for (_Map_pointer __node = __first._M_node + 1; 00727 __node < __last._M_node; ++__node) 00728 std::_Destroy(*__node, *__node + _S_buffer_size(), 00729 _M_get_Tp_allocator()); 00730 00731 if (__first._M_node != __last._M_node) 00732 { 00733 std::_Destroy(__first._M_cur, __first._M_last, 00734 _M_get_Tp_allocator()); 00735 std::_Destroy(__last._M_first, __last._M_cur, 00736 _M_get_Tp_allocator()); 00737 } 00738 else 00739 std::_Destroy(__first._M_cur, __last._M_cur, 00740 _M_get_Tp_allocator()); 00741 } 00742 00743 template <typename _Tp, typename _Alloc> 00744 void 00745 deque<_Tp, _Alloc>:: 00746 _M_new_elements_at_front(size_type __new_elems) 00747 { 00748 if (this->max_size() - this->size() < __new_elems) 00749 __throw_length_error(__N("deque::_M_new_elements_at_front")); 00750 00751 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 00752 / _S_buffer_size()); 00753 _M_reserve_map_at_front(__new_nodes); 00754 size_type __i; 00755 __try 00756 { 00757 for (__i = 1; __i <= __new_nodes; ++__i) 00758 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 00759 } 00760 __catch(...) 00761 { 00762 for (size_type __j = 1; __j < __i; ++__j) 00763 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 00764 __throw_exception_again; 00765 } 00766 } 00767 00768 template <typename _Tp, typename _Alloc> 00769 void 00770 deque<_Tp, _Alloc>:: 00771 _M_new_elements_at_back(size_type __new_elems) 00772 { 00773 if (this->max_size() - this->size() < __new_elems) 00774 __throw_length_error(__N("deque::_M_new_elements_at_back")); 00775 00776 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 00777 / _S_buffer_size()); 00778 _M_reserve_map_at_back(__new_nodes); 00779 size_type __i; 00780 __try 00781 { 00782 for (__i = 1; __i <= __new_nodes; ++__i) 00783 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 00784 } 00785 __catch(...) 00786 { 00787 for (size_type __j = 1; __j < __i; ++__j) 00788 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 00789 __throw_exception_again; 00790 } 00791 } 00792 00793 template <typename _Tp, typename _Alloc> 00794 void 00795 deque<_Tp, _Alloc>:: 00796 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 00797 { 00798 const size_type __old_num_nodes 00799 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 00800 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 00801 00802 _Map_pointer __new_nstart; 00803 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 00804 { 00805 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 00806 - __new_num_nodes) / 2 00807 + (__add_at_front ? __nodes_to_add : 0); 00808 if (__new_nstart < this->_M_impl._M_start._M_node) 00809 std::copy(this->_M_impl._M_start._M_node, 00810 this->_M_impl._M_finish._M_node + 1, 00811 __new_nstart); 00812 else 00813 std::copy_backward(this->_M_impl._M_start._M_node, 00814 this->_M_impl._M_finish._M_node + 1, 00815 __new_nstart + __old_num_nodes); 00816 } 00817 else 00818 { 00819 size_type __new_map_size = this->_M_impl._M_map_size 00820 + std::max(this->_M_impl._M_map_size, 00821 __nodes_to_add) + 2; 00822 00823 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 00824 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 00825 + (__add_at_front ? __nodes_to_add : 0); 00826 std::copy(this->_M_impl._M_start._M_node, 00827 this->_M_impl._M_finish._M_node + 1, 00828 __new_nstart); 00829 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 00830 00831 this->_M_impl._M_map = __new_map; 00832 this->_M_impl._M_map_size = __new_map_size; 00833 } 00834 00835 this->_M_impl._M_start._M_set_node(__new_nstart); 00836 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 00837 } 00838 00839 // Overload for deque::iterators, exploiting the "segmented-iterator 00840 // optimization". NB: leave const_iterators alone! 00841 template<typename _Tp> 00842 void 00843 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 00844 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) 00845 { 00846 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 00847 00848 for (typename _Self::_Map_pointer __node = __first._M_node + 1; 00849 __node < __last._M_node; ++__node) 00850 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); 00851 00852 if (__first._M_node != __last._M_node) 00853 { 00854 std::fill(__first._M_cur, __first._M_last, __value); 00855 std::fill(__last._M_first, __last._M_cur, __value); 00856 } 00857 else 00858 std::fill(__first._M_cur, __last._M_cur, __value); 00859 } 00860 00861 _GLIBCXX_END_NESTED_NAMESPACE 00862 00863 #endif