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