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