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