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