libstdc++
|
00001 // Deque implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001-2018 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, ++__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(__n); 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 _M_reserve_map_at_back(); 00488 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 00489 __try 00490 { 00491 #if __cplusplus >= 201103L 00492 _Alloc_traits::construct(this->_M_impl, 00493 this->_M_impl._M_finish._M_cur, 00494 std::forward<_Args>(__args)...); 00495 #else 00496 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); 00497 #endif 00498 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 00499 + 1); 00500 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 00501 } 00502 __catch(...) 00503 { 00504 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 00505 __throw_exception_again; 00506 } 00507 } 00508 00509 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 00510 template<typename _Tp, typename _Alloc> 00511 #if __cplusplus >= 201103L 00512 template<typename... _Args> 00513 void 00514 deque<_Tp, _Alloc>:: 00515 _M_push_front_aux(_Args&&... __args) 00516 #else 00517 void 00518 deque<_Tp, _Alloc>:: 00519 _M_push_front_aux(const value_type& __t) 00520 #endif 00521 { 00522 _M_reserve_map_at_front(); 00523 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 00524 __try 00525 { 00526 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 00527 - 1); 00528 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 00529 #if __cplusplus >= 201103L 00530 _Alloc_traits::construct(this->_M_impl, 00531 this->_M_impl._M_start._M_cur, 00532 std::forward<_Args>(__args)...); 00533 #else 00534 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); 00535 #endif 00536 } 00537 __catch(...) 00538 { 00539 ++this->_M_impl._M_start; 00540 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 00541 __throw_exception_again; 00542 } 00543 } 00544 00545 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 00546 template <typename _Tp, typename _Alloc> 00547 void deque<_Tp, _Alloc>:: 00548 _M_pop_back_aux() 00549 { 00550 _M_deallocate_node(this->_M_impl._M_finish._M_first); 00551 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 00552 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 00553 _Alloc_traits::destroy(_M_get_Tp_allocator(), 00554 this->_M_impl._M_finish._M_cur); 00555 } 00556 00557 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 00558 // Note that if the deque has at least one element (a precondition for this 00559 // member function), and if 00560 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 00561 // then the deque must have at least two nodes. 00562 template <typename _Tp, typename _Alloc> 00563 void deque<_Tp, _Alloc>:: 00564 _M_pop_front_aux() 00565 { 00566 _Alloc_traits::destroy(_M_get_Tp_allocator(), 00567 this->_M_impl._M_start._M_cur); 00568 _M_deallocate_node(this->_M_impl._M_start._M_first); 00569 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 00570 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 00571 } 00572 00573 template <typename _Tp, typename _Alloc> 00574 template <typename _InputIterator> 00575 void 00576 deque<_Tp, _Alloc>:: 00577 _M_range_insert_aux(iterator __pos, 00578 _InputIterator __first, _InputIterator __last, 00579 std::input_iterator_tag) 00580 { std::copy(__first, __last, std::inserter(*this, __pos)); } 00581 00582 template <typename _Tp, typename _Alloc> 00583 template <typename _ForwardIterator> 00584 void 00585 deque<_Tp, _Alloc>:: 00586 _M_range_insert_aux(iterator __pos, 00587 _ForwardIterator __first, _ForwardIterator __last, 00588 std::forward_iterator_tag) 00589 { 00590 const size_type __n = std::distance(__first, __last); 00591 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00592 { 00593 iterator __new_start = _M_reserve_elements_at_front(__n); 00594 __try 00595 { 00596 std::__uninitialized_copy_a(__first, __last, __new_start, 00597 _M_get_Tp_allocator()); 00598 this->_M_impl._M_start = __new_start; 00599 } 00600 __catch(...) 00601 { 00602 _M_destroy_nodes(__new_start._M_node, 00603 this->_M_impl._M_start._M_node); 00604 __throw_exception_again; 00605 } 00606 } 00607 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00608 { 00609 iterator __new_finish = _M_reserve_elements_at_back(__n); 00610 __try 00611 { 00612 std::__uninitialized_copy_a(__first, __last, 00613 this->_M_impl._M_finish, 00614 _M_get_Tp_allocator()); 00615 this->_M_impl._M_finish = __new_finish; 00616 } 00617 __catch(...) 00618 { 00619 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00620 __new_finish._M_node + 1); 00621 __throw_exception_again; 00622 } 00623 } 00624 else 00625 _M_insert_aux(__pos, __first, __last, __n); 00626 } 00627 00628 template<typename _Tp, typename _Alloc> 00629 #if __cplusplus >= 201103L 00630 template<typename... _Args> 00631 typename deque<_Tp, _Alloc>::iterator 00632 deque<_Tp, _Alloc>:: 00633 _M_insert_aux(iterator __pos, _Args&&... __args) 00634 { 00635 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy 00636 #else 00637 typename deque<_Tp, _Alloc>::iterator 00638 deque<_Tp, _Alloc>:: 00639 _M_insert_aux(iterator __pos, const value_type& __x) 00640 { 00641 value_type __x_copy = __x; // XXX copy 00642 #endif 00643 difference_type __index = __pos - this->_M_impl._M_start; 00644 if (static_cast<size_type>(__index) < size() / 2) 00645 { 00646 push_front(_GLIBCXX_MOVE(front())); 00647 iterator __front1 = this->_M_impl._M_start; 00648 ++__front1; 00649 iterator __front2 = __front1; 00650 ++__front2; 00651 __pos = this->_M_impl._M_start + __index; 00652 iterator __pos1 = __pos; 00653 ++__pos1; 00654 _GLIBCXX_MOVE3(__front2, __pos1, __front1); 00655 } 00656 else 00657 { 00658 push_back(_GLIBCXX_MOVE(back())); 00659 iterator __back1 = this->_M_impl._M_finish; 00660 --__back1; 00661 iterator __back2 = __back1; 00662 --__back2; 00663 __pos = this->_M_impl._M_start + __index; 00664 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); 00665 } 00666 *__pos = _GLIBCXX_MOVE(__x_copy); 00667 return __pos; 00668 } 00669 00670 template <typename _Tp, typename _Alloc> 00671 void 00672 deque<_Tp, _Alloc>:: 00673 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 00674 { 00675 const difference_type __elems_before = __pos - this->_M_impl._M_start; 00676 const size_type __length = this->size(); 00677 value_type __x_copy = __x; 00678 if (__elems_before < difference_type(__length / 2)) 00679 { 00680 iterator __new_start = _M_reserve_elements_at_front(__n); 00681 iterator __old_start = this->_M_impl._M_start; 00682 __pos = this->_M_impl._M_start + __elems_before; 00683 __try 00684 { 00685 if (__elems_before >= difference_type(__n)) 00686 { 00687 iterator __start_n = (this->_M_impl._M_start 00688 + difference_type(__n)); 00689 std::__uninitialized_move_a(this->_M_impl._M_start, 00690 __start_n, __new_start, 00691 _M_get_Tp_allocator()); 00692 this->_M_impl._M_start = __new_start; 00693 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 00694 std::fill(__pos - difference_type(__n), __pos, __x_copy); 00695 } 00696 else 00697 { 00698 std::__uninitialized_move_fill(this->_M_impl._M_start, 00699 __pos, __new_start, 00700 this->_M_impl._M_start, 00701 __x_copy, 00702 _M_get_Tp_allocator()); 00703 this->_M_impl._M_start = __new_start; 00704 std::fill(__old_start, __pos, __x_copy); 00705 } 00706 } 00707 __catch(...) 00708 { 00709 _M_destroy_nodes(__new_start._M_node, 00710 this->_M_impl._M_start._M_node); 00711 __throw_exception_again; 00712 } 00713 } 00714 else 00715 { 00716 iterator __new_finish = _M_reserve_elements_at_back(__n); 00717 iterator __old_finish = this->_M_impl._M_finish; 00718 const difference_type __elems_after = 00719 difference_type(__length) - __elems_before; 00720 __pos = this->_M_impl._M_finish - __elems_after; 00721 __try 00722 { 00723 if (__elems_after > difference_type(__n)) 00724 { 00725 iterator __finish_n = (this->_M_impl._M_finish 00726 - difference_type(__n)); 00727 std::__uninitialized_move_a(__finish_n, 00728 this->_M_impl._M_finish, 00729 this->_M_impl._M_finish, 00730 _M_get_Tp_allocator()); 00731 this->_M_impl._M_finish = __new_finish; 00732 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 00733 std::fill(__pos, __pos + difference_type(__n), __x_copy); 00734 } 00735 else 00736 { 00737 std::__uninitialized_fill_move(this->_M_impl._M_finish, 00738 __pos + difference_type(__n), 00739 __x_copy, __pos, 00740 this->_M_impl._M_finish, 00741 _M_get_Tp_allocator()); 00742 this->_M_impl._M_finish = __new_finish; 00743 std::fill(__pos, __old_finish, __x_copy); 00744 } 00745 } 00746 __catch(...) 00747 { 00748 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00749 __new_finish._M_node + 1); 00750 __throw_exception_again; 00751 } 00752 } 00753 } 00754 00755 template <typename _Tp, typename _Alloc> 00756 template <typename _ForwardIterator> 00757 void 00758 deque<_Tp, _Alloc>:: 00759 _M_insert_aux(iterator __pos, 00760 _ForwardIterator __first, _ForwardIterator __last, 00761 size_type __n) 00762 { 00763 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 00764 const size_type __length = size(); 00765 if (static_cast<size_type>(__elemsbefore) < __length / 2) 00766 { 00767 iterator __new_start = _M_reserve_elements_at_front(__n); 00768 iterator __old_start = this->_M_impl._M_start; 00769 __pos = this->_M_impl._M_start + __elemsbefore; 00770 __try 00771 { 00772 if (__elemsbefore >= difference_type(__n)) 00773 { 00774 iterator __start_n = (this->_M_impl._M_start 00775 + difference_type(__n)); 00776 std::__uninitialized_move_a(this->_M_impl._M_start, 00777 __start_n, __new_start, 00778 _M_get_Tp_allocator()); 00779 this->_M_impl._M_start = __new_start; 00780 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 00781 std::copy(__first, __last, __pos - difference_type(__n)); 00782 } 00783 else 00784 { 00785 _ForwardIterator __mid = __first; 00786 std::advance(__mid, difference_type(__n) - __elemsbefore); 00787 std::__uninitialized_move_copy(this->_M_impl._M_start, 00788 __pos, __first, __mid, 00789 __new_start, 00790 _M_get_Tp_allocator()); 00791 this->_M_impl._M_start = __new_start; 00792 std::copy(__mid, __last, __old_start); 00793 } 00794 } 00795 __catch(...) 00796 { 00797 _M_destroy_nodes(__new_start._M_node, 00798 this->_M_impl._M_start._M_node); 00799 __throw_exception_again; 00800 } 00801 } 00802 else 00803 { 00804 iterator __new_finish = _M_reserve_elements_at_back(__n); 00805 iterator __old_finish = this->_M_impl._M_finish; 00806 const difference_type __elemsafter = 00807 difference_type(__length) - __elemsbefore; 00808 __pos = this->_M_impl._M_finish - __elemsafter; 00809 __try 00810 { 00811 if (__elemsafter > difference_type(__n)) 00812 { 00813 iterator __finish_n = (this->_M_impl._M_finish 00814 - difference_type(__n)); 00815 std::__uninitialized_move_a(__finish_n, 00816 this->_M_impl._M_finish, 00817 this->_M_impl._M_finish, 00818 _M_get_Tp_allocator()); 00819 this->_M_impl._M_finish = __new_finish; 00820 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 00821 std::copy(__first, __last, __pos); 00822 } 00823 else 00824 { 00825 _ForwardIterator __mid = __first; 00826 std::advance(__mid, __elemsafter); 00827 std::__uninitialized_copy_move(__mid, __last, __pos, 00828 this->_M_impl._M_finish, 00829 this->_M_impl._M_finish, 00830 _M_get_Tp_allocator()); 00831 this->_M_impl._M_finish = __new_finish; 00832 std::copy(__first, __mid, __pos); 00833 } 00834 } 00835 __catch(...) 00836 { 00837 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00838 __new_finish._M_node + 1); 00839 __throw_exception_again; 00840 } 00841 } 00842 } 00843 00844 template<typename _Tp, typename _Alloc> 00845 void 00846 deque<_Tp, _Alloc>:: 00847 _M_destroy_data_aux(iterator __first, iterator __last) 00848 { 00849 for (_Map_pointer __node = __first._M_node + 1; 00850 __node < __last._M_node; ++__node) 00851 std::_Destroy(*__node, *__node + _S_buffer_size(), 00852 _M_get_Tp_allocator()); 00853 00854 if (__first._M_node != __last._M_node) 00855 { 00856 std::_Destroy(__first._M_cur, __first._M_last, 00857 _M_get_Tp_allocator()); 00858 std::_Destroy(__last._M_first, __last._M_cur, 00859 _M_get_Tp_allocator()); 00860 } 00861 else 00862 std::_Destroy(__first._M_cur, __last._M_cur, 00863 _M_get_Tp_allocator()); 00864 } 00865 00866 template <typename _Tp, typename _Alloc> 00867 void 00868 deque<_Tp, _Alloc>:: 00869 _M_new_elements_at_front(size_type __new_elems) 00870 { 00871 if (this->max_size() - this->size() < __new_elems) 00872 __throw_length_error(__N("deque::_M_new_elements_at_front")); 00873 00874 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 00875 / _S_buffer_size()); 00876 _M_reserve_map_at_front(__new_nodes); 00877 size_type __i; 00878 __try 00879 { 00880 for (__i = 1; __i <= __new_nodes; ++__i) 00881 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 00882 } 00883 __catch(...) 00884 { 00885 for (size_type __j = 1; __j < __i; ++__j) 00886 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 00887 __throw_exception_again; 00888 } 00889 } 00890 00891 template <typename _Tp, typename _Alloc> 00892 void 00893 deque<_Tp, _Alloc>:: 00894 _M_new_elements_at_back(size_type __new_elems) 00895 { 00896 if (this->max_size() - this->size() < __new_elems) 00897 __throw_length_error(__N("deque::_M_new_elements_at_back")); 00898 00899 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 00900 / _S_buffer_size()); 00901 _M_reserve_map_at_back(__new_nodes); 00902 size_type __i; 00903 __try 00904 { 00905 for (__i = 1; __i <= __new_nodes; ++__i) 00906 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 00907 } 00908 __catch(...) 00909 { 00910 for (size_type __j = 1; __j < __i; ++__j) 00911 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 00912 __throw_exception_again; 00913 } 00914 } 00915 00916 template <typename _Tp, typename _Alloc> 00917 void 00918 deque<_Tp, _Alloc>:: 00919 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 00920 { 00921 const size_type __old_num_nodes 00922 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 00923 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 00924 00925 _Map_pointer __new_nstart; 00926 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 00927 { 00928 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 00929 - __new_num_nodes) / 2 00930 + (__add_at_front ? __nodes_to_add : 0); 00931 if (__new_nstart < this->_M_impl._M_start._M_node) 00932 std::copy(this->_M_impl._M_start._M_node, 00933 this->_M_impl._M_finish._M_node + 1, 00934 __new_nstart); 00935 else 00936 std::copy_backward(this->_M_impl._M_start._M_node, 00937 this->_M_impl._M_finish._M_node + 1, 00938 __new_nstart + __old_num_nodes); 00939 } 00940 else 00941 { 00942 size_type __new_map_size = this->_M_impl._M_map_size 00943 + std::max(this->_M_impl._M_map_size, 00944 __nodes_to_add) + 2; 00945 00946 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 00947 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 00948 + (__add_at_front ? __nodes_to_add : 0); 00949 std::copy(this->_M_impl._M_start._M_node, 00950 this->_M_impl._M_finish._M_node + 1, 00951 __new_nstart); 00952 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 00953 00954 this->_M_impl._M_map = __new_map; 00955 this->_M_impl._M_map_size = __new_map_size; 00956 } 00957 00958 this->_M_impl._M_start._M_set_node(__new_nstart); 00959 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 00960 } 00961 00962 // Overload for deque::iterators, exploiting the "segmented-iterator 00963 // optimization". 00964 template<typename _Tp> 00965 void 00966 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 00967 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) 00968 { 00969 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 00970 00971 for (typename _Self::_Map_pointer __node = __first._M_node + 1; 00972 __node < __last._M_node; ++__node) 00973 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); 00974 00975 if (__first._M_node != __last._M_node) 00976 { 00977 std::fill(__first._M_cur, __first._M_last, __value); 00978 std::fill(__last._M_first, __last._M_cur, __value); 00979 } 00980 else 00981 std::fill(__first._M_cur, __last._M_cur, __value); 00982 } 00983 00984 template<typename _Tp> 00985 _Deque_iterator<_Tp, _Tp&, _Tp*> 00986 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 00987 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 00988 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 00989 { 00990 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 00991 typedef typename _Self::difference_type difference_type; 00992 00993 difference_type __len = __last - __first; 00994 while (__len > 0) 00995 { 00996 const difference_type __clen 00997 = std::min(__len, std::min(__first._M_last - __first._M_cur, 00998 __result._M_last - __result._M_cur)); 00999 std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 01000 __first += __clen; 01001 __result += __clen; 01002 __len -= __clen; 01003 } 01004 return __result; 01005 } 01006 01007 template<typename _Tp> 01008 _Deque_iterator<_Tp, _Tp&, _Tp*> 01009 copy_backward(_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 difference_type __llen = __last._M_cur - __last._M_first; 01020 _Tp* __lend = __last._M_cur; 01021 01022 difference_type __rlen = __result._M_cur - __result._M_first; 01023 _Tp* __rend = __result._M_cur; 01024 01025 if (!__llen) 01026 { 01027 __llen = _Self::_S_buffer_size(); 01028 __lend = *(__last._M_node - 1) + __llen; 01029 } 01030 if (!__rlen) 01031 { 01032 __rlen = _Self::_S_buffer_size(); 01033 __rend = *(__result._M_node - 1) + __rlen; 01034 } 01035 01036 const difference_type __clen = std::min(__len, 01037 std::min(__llen, __rlen)); 01038 std::copy_backward(__lend - __clen, __lend, __rend); 01039 __last -= __clen; 01040 __result -= __clen; 01041 __len -= __clen; 01042 } 01043 return __result; 01044 } 01045 01046 #if __cplusplus >= 201103L 01047 template<typename _Tp> 01048 _Deque_iterator<_Tp, _Tp&, _Tp*> 01049 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 01050 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 01051 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 01052 { 01053 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 01054 typedef typename _Self::difference_type difference_type; 01055 01056 difference_type __len = __last - __first; 01057 while (__len > 0) 01058 { 01059 const difference_type __clen 01060 = std::min(__len, std::min(__first._M_last - __first._M_cur, 01061 __result._M_last - __result._M_cur)); 01062 std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 01063 __first += __clen; 01064 __result += __clen; 01065 __len -= __clen; 01066 } 01067 return __result; 01068 } 01069 01070 template<typename _Tp> 01071 _Deque_iterator<_Tp, _Tp&, _Tp*> 01072 move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 01073 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 01074 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 01075 { 01076 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 01077 typedef typename _Self::difference_type difference_type; 01078 01079 difference_type __len = __last - __first; 01080 while (__len > 0) 01081 { 01082 difference_type __llen = __last._M_cur - __last._M_first; 01083 _Tp* __lend = __last._M_cur; 01084 01085 difference_type __rlen = __result._M_cur - __result._M_first; 01086 _Tp* __rend = __result._M_cur; 01087 01088 if (!__llen) 01089 { 01090 __llen = _Self::_S_buffer_size(); 01091 __lend = *(__last._M_node - 1) + __llen; 01092 } 01093 if (!__rlen) 01094 { 01095 __rlen = _Self::_S_buffer_size(); 01096 __rend = *(__result._M_node - 1) + __rlen; 01097 } 01098 01099 const difference_type __clen = std::min(__len, 01100 std::min(__llen, __rlen)); 01101 std::move_backward(__lend - __clen, __lend, __rend); 01102 __last -= __clen; 01103 __result -= __clen; 01104 __len -= __clen; 01105 } 01106 return __result; 01107 } 01108 #endif 01109 01110 _GLIBCXX_END_NAMESPACE_CONTAINER 01111 _GLIBCXX_END_NAMESPACE_VERSION 01112 } // namespace std 01113 01114 #endif