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 == begin() && __last == end()) 00222 { 00223 clear(); 00224 return end(); 00225 } 00226 else 00227 { 00228 const difference_type __n = __last - __first; 00229 const difference_type __elems_before = __first - begin(); 00230 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) 00231 { 00232 if (__first != begin()) 00233 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); 00234 _M_erase_at_begin(begin() + __n); 00235 } 00236 else 00237 { 00238 if (__last != end()) 00239 _GLIBCXX_MOVE3(__last, end(), __first); 00240 _M_erase_at_end(end() - __n); 00241 } 00242 return begin() + __elems_before; 00243 } 00244 } 00245 00246 template <typename _Tp, class _Alloc> 00247 template <typename _InputIterator> 00248 void 00249 deque<_Tp, _Alloc>:: 00250 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00251 std::input_iterator_tag) 00252 { 00253 iterator __cur = begin(); 00254 for (; __first != __last && __cur != end(); ++__cur, ++__first) 00255 *__cur = *__first; 00256 if (__first == __last) 00257 _M_erase_at_end(__cur); 00258 else 00259 insert(end(), __first, __last); 00260 } 00261 00262 template <typename _Tp, typename _Alloc> 00263 void 00264 deque<_Tp, _Alloc>:: 00265 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 00266 { 00267 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00268 { 00269 iterator __new_start = _M_reserve_elements_at_front(__n); 00270 __try 00271 { 00272 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, 00273 __x, _M_get_Tp_allocator()); 00274 this->_M_impl._M_start = __new_start; 00275 } 00276 __catch(...) 00277 { 00278 _M_destroy_nodes(__new_start._M_node, 00279 this->_M_impl._M_start._M_node); 00280 __throw_exception_again; 00281 } 00282 } 00283 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00284 { 00285 iterator __new_finish = _M_reserve_elements_at_back(__n); 00286 __try 00287 { 00288 std::__uninitialized_fill_a(this->_M_impl._M_finish, 00289 __new_finish, __x, 00290 _M_get_Tp_allocator()); 00291 this->_M_impl._M_finish = __new_finish; 00292 } 00293 __catch(...) 00294 { 00295 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00296 __new_finish._M_node + 1); 00297 __throw_exception_again; 00298 } 00299 } 00300 else 00301 _M_insert_aux(__pos, __n, __x); 00302 } 00303 00304 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00305 template <typename _Tp, typename _Alloc> 00306 void 00307 deque<_Tp, _Alloc>:: 00308 _M_default_append(size_type __n) 00309 { 00310 if (__n) 00311 { 00312 iterator __new_finish = _M_reserve_elements_at_back(__n); 00313 __try 00314 { 00315 std::__uninitialized_default_a(this->_M_impl._M_finish, 00316 __new_finish, 00317 _M_get_Tp_allocator()); 00318 this->_M_impl._M_finish = __new_finish; 00319 } 00320 __catch(...) 00321 { 00322 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00323 __new_finish._M_node + 1); 00324 __throw_exception_again; 00325 } 00326 } 00327 } 00328 #endif 00329 00330 template <typename _Tp, typename _Alloc> 00331 void 00332 deque<_Tp, _Alloc>:: 00333 _M_fill_initialize(const value_type& __value) 00334 { 00335 _Map_pointer __cur; 00336 __try 00337 { 00338 for (__cur = this->_M_impl._M_start._M_node; 00339 __cur < this->_M_impl._M_finish._M_node; 00340 ++__cur) 00341 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), 00342 __value, _M_get_Tp_allocator()); 00343 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 00344 this->_M_impl._M_finish._M_cur, 00345 __value, _M_get_Tp_allocator()); 00346 } 00347 __catch(...) 00348 { 00349 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 00350 _M_get_Tp_allocator()); 00351 __throw_exception_again; 00352 } 00353 } 00354 00355 template <typename _Tp, typename _Alloc> 00356 template <typename _InputIterator> 00357 void 00358 deque<_Tp, _Alloc>:: 00359 _M_range_initialize(_InputIterator __first, _InputIterator __last, 00360 std::input_iterator_tag) 00361 { 00362 this->_M_initialize_map(0); 00363 __try 00364 { 00365 for (; __first != __last; ++__first) 00366 push_back(*__first); 00367 } 00368 __catch(...) 00369 { 00370 clear(); 00371 __throw_exception_again; 00372 } 00373 } 00374 00375 template <typename _Tp, typename _Alloc> 00376 template <typename _ForwardIterator> 00377 void 00378 deque<_Tp, _Alloc>:: 00379 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 00380 std::forward_iterator_tag) 00381 { 00382 const size_type __n = std::distance(__first, __last); 00383 this->_M_initialize_map(__n); 00384 00385 _Map_pointer __cur_node; 00386 __try 00387 { 00388 for (__cur_node = this->_M_impl._M_start._M_node; 00389 __cur_node < this->_M_impl._M_finish._M_node; 00390 ++__cur_node) 00391 { 00392 _ForwardIterator __mid = __first; 00393 std::advance(__mid, _S_buffer_size()); 00394 std::__uninitialized_copy_a(__first, __mid, *__cur_node, 00395 _M_get_Tp_allocator()); 00396 __first = __mid; 00397 } 00398 std::__uninitialized_copy_a(__first, __last, 00399 this->_M_impl._M_finish._M_first, 00400 _M_get_Tp_allocator()); 00401 } 00402 __catch(...) 00403 { 00404 std::_Destroy(this->_M_impl._M_start, 00405 iterator(*__cur_node, __cur_node), 00406 _M_get_Tp_allocator()); 00407 __throw_exception_again; 00408 } 00409 } 00410 00411 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 00412 template<typename _Tp, typename _Alloc> 00413 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00414 template<typename... _Args> 00415 void 00416 deque<_Tp, _Alloc>:: 00417 _M_push_back_aux(_Args&&... __args) 00418 #else 00419 void 00420 deque<_Tp, _Alloc>:: 00421 _M_push_back_aux(const value_type& __t) 00422 #endif 00423 { 00424 _M_reserve_map_at_back(); 00425 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 00426 __try 00427 { 00428 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00429 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, 00430 std::forward<_Args>(__args)...); 00431 #else 00432 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); 00433 #endif 00434 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 00435 + 1); 00436 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 00437 } 00438 __catch(...) 00439 { 00440 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 00441 __throw_exception_again; 00442 } 00443 } 00444 00445 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 00446 template<typename _Tp, typename _Alloc> 00447 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00448 template<typename... _Args> 00449 void 00450 deque<_Tp, _Alloc>:: 00451 _M_push_front_aux(_Args&&... __args) 00452 #else 00453 void 00454 deque<_Tp, _Alloc>:: 00455 _M_push_front_aux(const value_type& __t) 00456 #endif 00457 { 00458 _M_reserve_map_at_front(); 00459 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 00460 __try 00461 { 00462 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 00463 - 1); 00464 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 00465 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00466 this->_M_impl.construct(this->_M_impl._M_start._M_cur, 00467 std::forward<_Args>(__args)...); 00468 #else 00469 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); 00470 #endif 00471 } 00472 __catch(...) 00473 { 00474 ++this->_M_impl._M_start; 00475 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 00476 __throw_exception_again; 00477 } 00478 } 00479 00480 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 00481 template <typename _Tp, typename _Alloc> 00482 void deque<_Tp, _Alloc>:: 00483 _M_pop_back_aux() 00484 { 00485 _M_deallocate_node(this->_M_impl._M_finish._M_first); 00486 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 00487 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 00488 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); 00489 } 00490 00491 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 00492 // Note that if the deque has at least one element (a precondition for this 00493 // member function), and if 00494 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 00495 // then the deque must have at least two nodes. 00496 template <typename _Tp, typename _Alloc> 00497 void deque<_Tp, _Alloc>:: 00498 _M_pop_front_aux() 00499 { 00500 this->_M_impl.destroy(this->_M_impl._M_start._M_cur); 00501 _M_deallocate_node(this->_M_impl._M_start._M_first); 00502 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 00503 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 00504 } 00505 00506 template <typename _Tp, typename _Alloc> 00507 template <typename _InputIterator> 00508 void 00509 deque<_Tp, _Alloc>:: 00510 _M_range_insert_aux(iterator __pos, 00511 _InputIterator __first, _InputIterator __last, 00512 std::input_iterator_tag) 00513 { std::copy(__first, __last, std::inserter(*this, __pos)); } 00514 00515 template <typename _Tp, typename _Alloc> 00516 template <typename _ForwardIterator> 00517 void 00518 deque<_Tp, _Alloc>:: 00519 _M_range_insert_aux(iterator __pos, 00520 _ForwardIterator __first, _ForwardIterator __last, 00521 std::forward_iterator_tag) 00522 { 00523 const size_type __n = std::distance(__first, __last); 00524 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00525 { 00526 iterator __new_start = _M_reserve_elements_at_front(__n); 00527 __try 00528 { 00529 std::__uninitialized_copy_a(__first, __last, __new_start, 00530 _M_get_Tp_allocator()); 00531 this->_M_impl._M_start = __new_start; 00532 } 00533 __catch(...) 00534 { 00535 _M_destroy_nodes(__new_start._M_node, 00536 this->_M_impl._M_start._M_node); 00537 __throw_exception_again; 00538 } 00539 } 00540 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00541 { 00542 iterator __new_finish = _M_reserve_elements_at_back(__n); 00543 __try 00544 { 00545 std::__uninitialized_copy_a(__first, __last, 00546 this->_M_impl._M_finish, 00547 _M_get_Tp_allocator()); 00548 this->_M_impl._M_finish = __new_finish; 00549 } 00550 __catch(...) 00551 { 00552 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00553 __new_finish._M_node + 1); 00554 __throw_exception_again; 00555 } 00556 } 00557 else 00558 _M_insert_aux(__pos, __first, __last, __n); 00559 } 00560 00561 template<typename _Tp, typename _Alloc> 00562 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00563 template<typename... _Args> 00564 typename deque<_Tp, _Alloc>::iterator 00565 deque<_Tp, _Alloc>:: 00566 _M_insert_aux(iterator __pos, _Args&&... __args) 00567 { 00568 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy 00569 #else 00570 typename deque<_Tp, _Alloc>::iterator 00571 deque<_Tp, _Alloc>:: 00572 _M_insert_aux(iterator __pos, const value_type& __x) 00573 { 00574 value_type __x_copy = __x; // XXX copy 00575 #endif 00576 difference_type __index = __pos - this->_M_impl._M_start; 00577 if (static_cast<size_type>(__index) < size() / 2) 00578 { 00579 push_front(_GLIBCXX_MOVE(front())); 00580 iterator __front1 = this->_M_impl._M_start; 00581 ++__front1; 00582 iterator __front2 = __front1; 00583 ++__front2; 00584 __pos = this->_M_impl._M_start + __index; 00585 iterator __pos1 = __pos; 00586 ++__pos1; 00587 _GLIBCXX_MOVE3(__front2, __pos1, __front1); 00588 } 00589 else 00590 { 00591 push_back(_GLIBCXX_MOVE(back())); 00592 iterator __back1 = this->_M_impl._M_finish; 00593 --__back1; 00594 iterator __back2 = __back1; 00595 --__back2; 00596 __pos = this->_M_impl._M_start + __index; 00597 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); 00598 } 00599 *__pos = _GLIBCXX_MOVE(__x_copy); 00600 return __pos; 00601 } 00602 00603 template <typename _Tp, typename _Alloc> 00604 void 00605 deque<_Tp, _Alloc>:: 00606 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 00607 { 00608 const difference_type __elems_before = __pos - this->_M_impl._M_start; 00609 const size_type __length = this->size(); 00610 value_type __x_copy = __x; 00611 if (__elems_before < difference_type(__length / 2)) 00612 { 00613 iterator __new_start = _M_reserve_elements_at_front(__n); 00614 iterator __old_start = this->_M_impl._M_start; 00615 __pos = this->_M_impl._M_start + __elems_before; 00616 __try 00617 { 00618 if (__elems_before >= difference_type(__n)) 00619 { 00620 iterator __start_n = (this->_M_impl._M_start 00621 + difference_type(__n)); 00622 std::__uninitialized_move_a(this->_M_impl._M_start, 00623 __start_n, __new_start, 00624 _M_get_Tp_allocator()); 00625 this->_M_impl._M_start = __new_start; 00626 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 00627 std::fill(__pos - difference_type(__n), __pos, __x_copy); 00628 } 00629 else 00630 { 00631 std::__uninitialized_move_fill(this->_M_impl._M_start, 00632 __pos, __new_start, 00633 this->_M_impl._M_start, 00634 __x_copy, 00635 _M_get_Tp_allocator()); 00636 this->_M_impl._M_start = __new_start; 00637 std::fill(__old_start, __pos, __x_copy); 00638 } 00639 } 00640 __catch(...) 00641 { 00642 _M_destroy_nodes(__new_start._M_node, 00643 this->_M_impl._M_start._M_node); 00644 __throw_exception_again; 00645 } 00646 } 00647 else 00648 { 00649 iterator __new_finish = _M_reserve_elements_at_back(__n); 00650 iterator __old_finish = this->_M_impl._M_finish; 00651 const difference_type __elems_after = 00652 difference_type(__length) - __elems_before; 00653 __pos = this->_M_impl._M_finish - __elems_after; 00654 __try 00655 { 00656 if (__elems_after > difference_type(__n)) 00657 { 00658 iterator __finish_n = (this->_M_impl._M_finish 00659 - difference_type(__n)); 00660 std::__uninitialized_move_a(__finish_n, 00661 this->_M_impl._M_finish, 00662 this->_M_impl._M_finish, 00663 _M_get_Tp_allocator()); 00664 this->_M_impl._M_finish = __new_finish; 00665 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 00666 std::fill(__pos, __pos + difference_type(__n), __x_copy); 00667 } 00668 else 00669 { 00670 std::__uninitialized_fill_move(this->_M_impl._M_finish, 00671 __pos + difference_type(__n), 00672 __x_copy, __pos, 00673 this->_M_impl._M_finish, 00674 _M_get_Tp_allocator()); 00675 this->_M_impl._M_finish = __new_finish; 00676 std::fill(__pos, __old_finish, __x_copy); 00677 } 00678 } 00679 __catch(...) 00680 { 00681 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00682 __new_finish._M_node + 1); 00683 __throw_exception_again; 00684 } 00685 } 00686 } 00687 00688 template <typename _Tp, typename _Alloc> 00689 template <typename _ForwardIterator> 00690 void 00691 deque<_Tp, _Alloc>:: 00692 _M_insert_aux(iterator __pos, 00693 _ForwardIterator __first, _ForwardIterator __last, 00694 size_type __n) 00695 { 00696 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 00697 const size_type __length = size(); 00698 if (static_cast<size_type>(__elemsbefore) < __length / 2) 00699 { 00700 iterator __new_start = _M_reserve_elements_at_front(__n); 00701 iterator __old_start = this->_M_impl._M_start; 00702 __pos = this->_M_impl._M_start + __elemsbefore; 00703 __try 00704 { 00705 if (__elemsbefore >= difference_type(__n)) 00706 { 00707 iterator __start_n = (this->_M_impl._M_start 00708 + difference_type(__n)); 00709 std::__uninitialized_move_a(this->_M_impl._M_start, 00710 __start_n, __new_start, 00711 _M_get_Tp_allocator()); 00712 this->_M_impl._M_start = __new_start; 00713 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 00714 std::copy(__first, __last, __pos - difference_type(__n)); 00715 } 00716 else 00717 { 00718 _ForwardIterator __mid = __first; 00719 std::advance(__mid, difference_type(__n) - __elemsbefore); 00720 std::__uninitialized_move_copy(this->_M_impl._M_start, 00721 __pos, __first, __mid, 00722 __new_start, 00723 _M_get_Tp_allocator()); 00724 this->_M_impl._M_start = __new_start; 00725 std::copy(__mid, __last, __old_start); 00726 } 00727 } 00728 __catch(...) 00729 { 00730 _M_destroy_nodes(__new_start._M_node, 00731 this->_M_impl._M_start._M_node); 00732 __throw_exception_again; 00733 } 00734 } 00735 else 00736 { 00737 iterator __new_finish = _M_reserve_elements_at_back(__n); 00738 iterator __old_finish = this->_M_impl._M_finish; 00739 const difference_type __elemsafter = 00740 difference_type(__length) - __elemsbefore; 00741 __pos = this->_M_impl._M_finish - __elemsafter; 00742 __try 00743 { 00744 if (__elemsafter > difference_type(__n)) 00745 { 00746 iterator __finish_n = (this->_M_impl._M_finish 00747 - difference_type(__n)); 00748 std::__uninitialized_move_a(__finish_n, 00749 this->_M_impl._M_finish, 00750 this->_M_impl._M_finish, 00751 _M_get_Tp_allocator()); 00752 this->_M_impl._M_finish = __new_finish; 00753 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 00754 std::copy(__first, __last, __pos); 00755 } 00756 else 00757 { 00758 _ForwardIterator __mid = __first; 00759 std::advance(__mid, __elemsafter); 00760 std::__uninitialized_copy_move(__mid, __last, __pos, 00761 this->_M_impl._M_finish, 00762 this->_M_impl._M_finish, 00763 _M_get_Tp_allocator()); 00764 this->_M_impl._M_finish = __new_finish; 00765 std::copy(__first, __mid, __pos); 00766 } 00767 } 00768 __catch(...) 00769 { 00770 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00771 __new_finish._M_node + 1); 00772 __throw_exception_again; 00773 } 00774 } 00775 } 00776 00777 template<typename _Tp, typename _Alloc> 00778 void 00779 deque<_Tp, _Alloc>:: 00780 _M_destroy_data_aux(iterator __first, iterator __last) 00781 { 00782 for (_Map_pointer __node = __first._M_node + 1; 00783 __node < __last._M_node; ++__node) 00784 std::_Destroy(*__node, *__node + _S_buffer_size(), 00785 _M_get_Tp_allocator()); 00786 00787 if (__first._M_node != __last._M_node) 00788 { 00789 std::_Destroy(__first._M_cur, __first._M_last, 00790 _M_get_Tp_allocator()); 00791 std::_Destroy(__last._M_first, __last._M_cur, 00792 _M_get_Tp_allocator()); 00793 } 00794 else 00795 std::_Destroy(__first._M_cur, __last._M_cur, 00796 _M_get_Tp_allocator()); 00797 } 00798 00799 template <typename _Tp, typename _Alloc> 00800 void 00801 deque<_Tp, _Alloc>:: 00802 _M_new_elements_at_front(size_type __new_elems) 00803 { 00804 if (this->max_size() - this->size() < __new_elems) 00805 __throw_length_error(__N("deque::_M_new_elements_at_front")); 00806 00807 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 00808 / _S_buffer_size()); 00809 _M_reserve_map_at_front(__new_nodes); 00810 size_type __i; 00811 __try 00812 { 00813 for (__i = 1; __i <= __new_nodes; ++__i) 00814 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 00815 } 00816 __catch(...) 00817 { 00818 for (size_type __j = 1; __j < __i; ++__j) 00819 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 00820 __throw_exception_again; 00821 } 00822 } 00823 00824 template <typename _Tp, typename _Alloc> 00825 void 00826 deque<_Tp, _Alloc>:: 00827 _M_new_elements_at_back(size_type __new_elems) 00828 { 00829 if (this->max_size() - this->size() < __new_elems) 00830 __throw_length_error(__N("deque::_M_new_elements_at_back")); 00831 00832 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 00833 / _S_buffer_size()); 00834 _M_reserve_map_at_back(__new_nodes); 00835 size_type __i; 00836 __try 00837 { 00838 for (__i = 1; __i <= __new_nodes; ++__i) 00839 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 00840 } 00841 __catch(...) 00842 { 00843 for (size_type __j = 1; __j < __i; ++__j) 00844 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 00845 __throw_exception_again; 00846 } 00847 } 00848 00849 template <typename _Tp, typename _Alloc> 00850 void 00851 deque<_Tp, _Alloc>:: 00852 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 00853 { 00854 const size_type __old_num_nodes 00855 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 00856 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 00857 00858 _Map_pointer __new_nstart; 00859 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 00860 { 00861 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 00862 - __new_num_nodes) / 2 00863 + (__add_at_front ? __nodes_to_add : 0); 00864 if (__new_nstart < this->_M_impl._M_start._M_node) 00865 std::copy(this->_M_impl._M_start._M_node, 00866 this->_M_impl._M_finish._M_node + 1, 00867 __new_nstart); 00868 else 00869 std::copy_backward(this->_M_impl._M_start._M_node, 00870 this->_M_impl._M_finish._M_node + 1, 00871 __new_nstart + __old_num_nodes); 00872 } 00873 else 00874 { 00875 size_type __new_map_size = this->_M_impl._M_map_size 00876 + std::max(this->_M_impl._M_map_size, 00877 __nodes_to_add) + 2; 00878 00879 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 00880 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 00881 + (__add_at_front ? __nodes_to_add : 0); 00882 std::copy(this->_M_impl._M_start._M_node, 00883 this->_M_impl._M_finish._M_node + 1, 00884 __new_nstart); 00885 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 00886 00887 this->_M_impl._M_map = __new_map; 00888 this->_M_impl._M_map_size = __new_map_size; 00889 } 00890 00891 this->_M_impl._M_start._M_set_node(__new_nstart); 00892 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 00893 } 00894 00895 // Overload for deque::iterators, exploiting the "segmented-iterator 00896 // optimization". 00897 template<typename _Tp> 00898 void 00899 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 00900 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) 00901 { 00902 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 00903 00904 for (typename _Self::_Map_pointer __node = __first._M_node + 1; 00905 __node < __last._M_node; ++__node) 00906 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); 00907 00908 if (__first._M_node != __last._M_node) 00909 { 00910 std::fill(__first._M_cur, __first._M_last, __value); 00911 std::fill(__last._M_first, __last._M_cur, __value); 00912 } 00913 else 00914 std::fill(__first._M_cur, __last._M_cur, __value); 00915 } 00916 00917 template<typename _Tp> 00918 _Deque_iterator<_Tp, _Tp&, _Tp*> 00919 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 00920 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 00921 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 00922 { 00923 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 00924 typedef typename _Self::difference_type difference_type; 00925 00926 difference_type __len = __last - __first; 00927 while (__len > 0) 00928 { 00929 const difference_type __clen 00930 = std::min(__len, std::min(__first._M_last - __first._M_cur, 00931 __result._M_last - __result._M_cur)); 00932 std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 00933 __first += __clen; 00934 __result += __clen; 00935 __len -= __clen; 00936 } 00937 return __result; 00938 } 00939 00940 template<typename _Tp> 00941 _Deque_iterator<_Tp, _Tp&, _Tp*> 00942 copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 00943 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 00944 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 00945 { 00946 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 00947 typedef typename _Self::difference_type difference_type; 00948 00949 difference_type __len = __last - __first; 00950 while (__len > 0) 00951 { 00952 difference_type __llen = __last._M_cur - __last._M_first; 00953 _Tp* __lend = __last._M_cur; 00954 00955 difference_type __rlen = __result._M_cur - __result._M_first; 00956 _Tp* __rend = __result._M_cur; 00957 00958 if (!__llen) 00959 { 00960 __llen = _Self::_S_buffer_size(); 00961 __lend = *(__last._M_node - 1) + __llen; 00962 } 00963 if (!__rlen) 00964 { 00965 __rlen = _Self::_S_buffer_size(); 00966 __rend = *(__result._M_node - 1) + __rlen; 00967 } 00968 00969 const difference_type __clen = std::min(__len, 00970 std::min(__llen, __rlen)); 00971 std::copy_backward(__lend - __clen, __lend, __rend); 00972 __last -= __clen; 00973 __result -= __clen; 00974 __len -= __clen; 00975 } 00976 return __result; 00977 } 00978 00979 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00980 template<typename _Tp> 00981 _Deque_iterator<_Tp, _Tp&, _Tp*> 00982 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 00983 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 00984 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 00985 { 00986 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 00987 typedef typename _Self::difference_type difference_type; 00988 00989 difference_type __len = __last - __first; 00990 while (__len > 0) 00991 { 00992 const difference_type __clen 00993 = std::min(__len, std::min(__first._M_last - __first._M_cur, 00994 __result._M_last - __result._M_cur)); 00995 std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 00996 __first += __clen; 00997 __result += __clen; 00998 __len -= __clen; 00999 } 01000 return __result; 01001 } 01002 01003 template<typename _Tp> 01004 _Deque_iterator<_Tp, _Tp&, _Tp*> 01005 move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 01006 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 01007 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 01008 { 01009 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 01010 typedef typename _Self::difference_type difference_type; 01011 01012 difference_type __len = __last - __first; 01013 while (__len > 0) 01014 { 01015 difference_type __llen = __last._M_cur - __last._M_first; 01016 _Tp* __lend = __last._M_cur; 01017 01018 difference_type __rlen = __result._M_cur - __result._M_first; 01019 _Tp* __rend = __result._M_cur; 01020 01021 if (!__llen) 01022 { 01023 __llen = _Self::_S_buffer_size(); 01024 __lend = *(__last._M_node - 1) + __llen; 01025 } 01026 if (!__rlen) 01027 { 01028 __rlen = _Self::_S_buffer_size(); 01029 __rend = *(__result._M_node - 1) + __rlen; 01030 } 01031 01032 const difference_type __clen = std::min(__len, 01033 std::min(__llen, __rlen)); 01034 std::move_backward(__lend - __clen, __lend, __rend); 01035 __last -= __clen; 01036 __result -= __clen; 01037 __len -= __clen; 01038 } 01039 return __result; 01040 } 01041 #endif 01042 01043 _GLIBCXX_END_NAMESPACE_CONTAINER 01044 } // namespace std 01045 01046 #endif