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