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