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