libstdc++
|
00001 // List 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) 1996,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/list.tcc 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{list} 00054 */ 00055 00056 #ifndef _LIST_TCC 00057 #define _LIST_TCC 1 00058 00059 namespace std _GLIBCXX_VISIBILITY(default) 00060 { 00061 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00062 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00063 00064 template<typename _Tp, typename _Alloc> 00065 void 00066 _List_base<_Tp, _Alloc>:: 00067 _M_clear() _GLIBCXX_NOEXCEPT 00068 { 00069 typedef _List_node<_Tp> _Node; 00070 __detail::_List_node_base* __cur = _M_impl._M_node._M_next; 00071 while (__cur != &_M_impl._M_node) 00072 { 00073 _Node* __tmp = static_cast<_Node*>(__cur); 00074 __cur = __tmp->_M_next; 00075 _Tp* __val = __tmp->_M_valptr(); 00076 #if __cplusplus >= 201103L 00077 _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val); 00078 #else 00079 _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val); 00080 #endif 00081 _M_put_node(__tmp); 00082 } 00083 } 00084 00085 #if __cplusplus >= 201103L 00086 template<typename _Tp, typename _Alloc> 00087 template<typename... _Args> 00088 typename list<_Tp, _Alloc>::iterator 00089 list<_Tp, _Alloc>:: 00090 emplace(const_iterator __position, _Args&&... __args) 00091 { 00092 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 00093 __tmp->_M_hook(__position._M_const_cast()._M_node); 00094 this->_M_inc_size(1); 00095 return iterator(__tmp); 00096 } 00097 #endif 00098 00099 template<typename _Tp, typename _Alloc> 00100 typename list<_Tp, _Alloc>::iterator 00101 list<_Tp, _Alloc>:: 00102 #if __cplusplus >= 201103L 00103 insert(const_iterator __position, const value_type& __x) 00104 #else 00105 insert(iterator __position, const value_type& __x) 00106 #endif 00107 { 00108 _Node* __tmp = _M_create_node(__x); 00109 __tmp->_M_hook(__position._M_const_cast()._M_node); 00110 this->_M_inc_size(1); 00111 return iterator(__tmp); 00112 } 00113 00114 #if __cplusplus >= 201103L 00115 template<typename _Tp, typename _Alloc> 00116 typename list<_Tp, _Alloc>::iterator 00117 list<_Tp, _Alloc>:: 00118 insert(const_iterator __position, size_type __n, const value_type& __x) 00119 { 00120 if (__n) 00121 { 00122 list __tmp(__n, __x, get_allocator()); 00123 iterator __it = __tmp.begin(); 00124 splice(__position, __tmp); 00125 return __it; 00126 } 00127 return __position._M_const_cast(); 00128 } 00129 00130 template<typename _Tp, typename _Alloc> 00131 template<typename _InputIterator, typename> 00132 typename list<_Tp, _Alloc>::iterator 00133 list<_Tp, _Alloc>:: 00134 insert(const_iterator __position, _InputIterator __first, 00135 _InputIterator __last) 00136 { 00137 list __tmp(__first, __last, get_allocator()); 00138 if (!__tmp.empty()) 00139 { 00140 iterator __it = __tmp.begin(); 00141 splice(__position, __tmp); 00142 return __it; 00143 } 00144 return __position._M_const_cast(); 00145 } 00146 #endif 00147 00148 template<typename _Tp, typename _Alloc> 00149 typename list<_Tp, _Alloc>::iterator 00150 list<_Tp, _Alloc>:: 00151 #if __cplusplus >= 201103L 00152 erase(const_iterator __position) noexcept 00153 #else 00154 erase(iterator __position) 00155 #endif 00156 { 00157 iterator __ret = iterator(__position._M_node->_M_next); 00158 _M_erase(__position._M_const_cast()); 00159 return __ret; 00160 } 00161 00162 // Return a const_iterator indicating the position to start inserting or 00163 // erasing elements (depending whether the list is growing or shrinking), 00164 // and set __new_size to the number of new elements that must be appended. 00165 // Equivalent to the following, but performed optimally: 00166 // if (__new_size < size()) { 00167 // __new_size = 0; 00168 // return std::next(begin(), __new_size); 00169 // } else { 00170 // __newsize -= size(); 00171 // return end(); 00172 // } 00173 template<typename _Tp, typename _Alloc> 00174 typename list<_Tp, _Alloc>::const_iterator 00175 list<_Tp, _Alloc>:: 00176 _M_resize_pos(size_type& __new_size) const 00177 { 00178 const_iterator __i; 00179 #if _GLIBCXX_USE_CXX11_ABI 00180 const size_type __len = size(); 00181 if (__new_size < __len) 00182 { 00183 if (__new_size <= __len / 2) 00184 { 00185 __i = begin(); 00186 std::advance(__i, __new_size); 00187 } 00188 else 00189 { 00190 __i = end(); 00191 ptrdiff_t __num_erase = __len - __new_size; 00192 std::advance(__i, -__num_erase); 00193 } 00194 __new_size = 0; 00195 return __i; 00196 } 00197 else 00198 __i = end(); 00199 #else 00200 size_type __len = 0; 00201 for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len) 00202 ; 00203 #endif 00204 __new_size -= __len; 00205 return __i; 00206 } 00207 00208 #if __cplusplus >= 201103L 00209 template<typename _Tp, typename _Alloc> 00210 void 00211 list<_Tp, _Alloc>:: 00212 _M_default_append(size_type __n) 00213 { 00214 size_type __i = 0; 00215 __try 00216 { 00217 for (; __i < __n; ++__i) 00218 emplace_back(); 00219 } 00220 __catch(...) 00221 { 00222 for (; __i; --__i) 00223 pop_back(); 00224 __throw_exception_again; 00225 } 00226 } 00227 00228 template<typename _Tp, typename _Alloc> 00229 void 00230 list<_Tp, _Alloc>:: 00231 resize(size_type __new_size) 00232 { 00233 const_iterator __i = _M_resize_pos(__new_size); 00234 if (__new_size) 00235 _M_default_append(__new_size); 00236 else 00237 erase(__i, end()); 00238 } 00239 00240 template<typename _Tp, typename _Alloc> 00241 void 00242 list<_Tp, _Alloc>:: 00243 resize(size_type __new_size, const value_type& __x) 00244 { 00245 const_iterator __i = _M_resize_pos(__new_size); 00246 if (__new_size) 00247 insert(end(), __new_size, __x); 00248 else 00249 erase(__i, end()); 00250 } 00251 #else 00252 template<typename _Tp, typename _Alloc> 00253 void 00254 list<_Tp, _Alloc>:: 00255 resize(size_type __new_size, value_type __x) 00256 { 00257 const_iterator __i = _M_resize_pos(__new_size); 00258 if (__new_size) 00259 insert(end(), __new_size, __x); 00260 else 00261 erase(__i._M_const_cast(), end()); 00262 } 00263 #endif 00264 00265 template<typename _Tp, typename _Alloc> 00266 list<_Tp, _Alloc>& 00267 list<_Tp, _Alloc>:: 00268 operator=(const list& __x) 00269 { 00270 if (this != std::__addressof(__x)) 00271 { 00272 #if __cplusplus >= 201103L 00273 if (_Node_alloc_traits::_S_propagate_on_copy_assign()) 00274 { 00275 auto& __this_alloc = this->_M_get_Node_allocator(); 00276 auto& __that_alloc = __x._M_get_Node_allocator(); 00277 if (!_Node_alloc_traits::_S_always_equal() 00278 && __this_alloc != __that_alloc) 00279 { 00280 // replacement allocator cannot free existing storage 00281 clear(); 00282 } 00283 std::__alloc_on_copy(__this_alloc, __that_alloc); 00284 } 00285 #endif 00286 _M_assign_dispatch(__x.begin(), __x.end(), __false_type()); 00287 } 00288 return *this; 00289 } 00290 00291 template<typename _Tp, typename _Alloc> 00292 void 00293 list<_Tp, _Alloc>:: 00294 _M_fill_assign(size_type __n, const value_type& __val) 00295 { 00296 iterator __i = begin(); 00297 for (; __i != end() && __n > 0; ++__i, --__n) 00298 *__i = __val; 00299 if (__n > 0) 00300 insert(end(), __n, __val); 00301 else 00302 erase(__i, end()); 00303 } 00304 00305 template<typename _Tp, typename _Alloc> 00306 template <typename _InputIterator> 00307 void 00308 list<_Tp, _Alloc>:: 00309 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 00310 __false_type) 00311 { 00312 iterator __first1 = begin(); 00313 iterator __last1 = end(); 00314 for (; __first1 != __last1 && __first2 != __last2; 00315 ++__first1, (void)++__first2) 00316 *__first1 = *__first2; 00317 if (__first2 == __last2) 00318 erase(__first1, __last1); 00319 else 00320 insert(__last1, __first2, __last2); 00321 } 00322 00323 #if __cplusplus > 201703L 00324 # define _GLIBCXX20_ONLY(__expr) __expr 00325 #else 00326 # define _GLIBCXX20_ONLY(__expr) 00327 #endif 00328 00329 template<typename _Tp, typename _Alloc> 00330 typename list<_Tp, _Alloc>::__remove_return_type 00331 list<_Tp, _Alloc>:: 00332 remove(const value_type& __value) 00333 { 00334 size_type __removed __attribute__((__unused__)) = 0; 00335 iterator __first = begin(); 00336 iterator __last = end(); 00337 iterator __extra = __last; 00338 while (__first != __last) 00339 { 00340 iterator __next = __first; 00341 ++__next; 00342 if (*__first == __value) 00343 { 00344 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00345 // 526. Is it undefined if a function in the standard changes 00346 // in parameters? 00347 if (std::__addressof(*__first) != std::__addressof(__value)) 00348 { 00349 _M_erase(__first); 00350 _GLIBCXX20_ONLY( __removed++ ); 00351 } 00352 else 00353 __extra = __first; 00354 } 00355 __first = __next; 00356 } 00357 if (__extra != __last) 00358 { 00359 _M_erase(__extra); 00360 _GLIBCXX20_ONLY( __removed++ ); 00361 } 00362 return _GLIBCXX20_ONLY( __removed ); 00363 } 00364 00365 template<typename _Tp, typename _Alloc> 00366 typename list<_Tp, _Alloc>::__remove_return_type 00367 list<_Tp, _Alloc>:: 00368 unique() 00369 { 00370 iterator __first = begin(); 00371 iterator __last = end(); 00372 if (__first == __last) 00373 return _GLIBCXX20_ONLY( 0 ); 00374 size_type __removed __attribute__((__unused__)) = 0; 00375 iterator __next = __first; 00376 while (++__next != __last) 00377 { 00378 if (*__first == *__next) 00379 { 00380 _M_erase(__next); 00381 _GLIBCXX20_ONLY( __removed++ ); 00382 } 00383 else 00384 __first = __next; 00385 __next = __first; 00386 } 00387 return _GLIBCXX20_ONLY( __removed ); 00388 } 00389 00390 template<typename _Tp, typename _Alloc> 00391 void 00392 list<_Tp, _Alloc>:: 00393 #if __cplusplus >= 201103L 00394 merge(list&& __x) 00395 #else 00396 merge(list& __x) 00397 #endif 00398 { 00399 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00400 // 300. list::merge() specification incomplete 00401 if (this != std::__addressof(__x)) 00402 { 00403 _M_check_equal_allocators(__x); 00404 00405 iterator __first1 = begin(); 00406 iterator __last1 = end(); 00407 iterator __first2 = __x.begin(); 00408 iterator __last2 = __x.end(); 00409 const size_t __orig_size = __x.size(); 00410 __try { 00411 while (__first1 != __last1 && __first2 != __last2) 00412 if (*__first2 < *__first1) 00413 { 00414 iterator __next = __first2; 00415 _M_transfer(__first1, __first2, ++__next); 00416 __first2 = __next; 00417 } 00418 else 00419 ++__first1; 00420 if (__first2 != __last2) 00421 _M_transfer(__last1, __first2, __last2); 00422 00423 this->_M_inc_size(__x._M_get_size()); 00424 __x._M_set_size(0); 00425 } 00426 __catch(...) 00427 { 00428 const size_t __dist = std::distance(__first2, __last2); 00429 this->_M_inc_size(__orig_size - __dist); 00430 __x._M_set_size(__dist); 00431 __throw_exception_again; 00432 } 00433 } 00434 } 00435 00436 template<typename _Tp, typename _Alloc> 00437 template <typename _StrictWeakOrdering> 00438 void 00439 list<_Tp, _Alloc>:: 00440 #if __cplusplus >= 201103L 00441 merge(list&& __x, _StrictWeakOrdering __comp) 00442 #else 00443 merge(list& __x, _StrictWeakOrdering __comp) 00444 #endif 00445 { 00446 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00447 // 300. list::merge() specification incomplete 00448 if (this != std::__addressof(__x)) 00449 { 00450 _M_check_equal_allocators(__x); 00451 00452 iterator __first1 = begin(); 00453 iterator __last1 = end(); 00454 iterator __first2 = __x.begin(); 00455 iterator __last2 = __x.end(); 00456 const size_t __orig_size = __x.size(); 00457 __try 00458 { 00459 while (__first1 != __last1 && __first2 != __last2) 00460 if (__comp(*__first2, *__first1)) 00461 { 00462 iterator __next = __first2; 00463 _M_transfer(__first1, __first2, ++__next); 00464 __first2 = __next; 00465 } 00466 else 00467 ++__first1; 00468 if (__first2 != __last2) 00469 _M_transfer(__last1, __first2, __last2); 00470 00471 this->_M_inc_size(__x._M_get_size()); 00472 __x._M_set_size(0); 00473 } 00474 __catch(...) 00475 { 00476 const size_t __dist = std::distance(__first2, __last2); 00477 this->_M_inc_size(__orig_size - __dist); 00478 __x._M_set_size(__dist); 00479 __throw_exception_again; 00480 } 00481 } 00482 } 00483 00484 template<typename _Tp, typename _Alloc> 00485 void 00486 list<_Tp, _Alloc>:: 00487 sort() 00488 { 00489 // Do nothing if the list has length 0 or 1. 00490 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00491 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00492 { 00493 list __carry; 00494 list __tmp[64]; 00495 list * __fill = __tmp; 00496 list * __counter; 00497 __try 00498 { 00499 do 00500 { 00501 __carry.splice(__carry.begin(), *this, begin()); 00502 00503 for(__counter = __tmp; 00504 __counter != __fill && !__counter->empty(); 00505 ++__counter) 00506 { 00507 __counter->merge(__carry); 00508 __carry.swap(*__counter); 00509 } 00510 __carry.swap(*__counter); 00511 if (__counter == __fill) 00512 ++__fill; 00513 } 00514 while ( !empty() ); 00515 00516 for (__counter = __tmp + 1; __counter != __fill; ++__counter) 00517 __counter->merge(*(__counter - 1)); 00518 swap( *(__fill - 1) ); 00519 } 00520 __catch(...) 00521 { 00522 this->splice(this->end(), __carry); 00523 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) 00524 this->splice(this->end(), __tmp[__i]); 00525 __throw_exception_again; 00526 } 00527 } 00528 } 00529 00530 template<typename _Tp, typename _Alloc> 00531 template <typename _Predicate> 00532 typename list<_Tp, _Alloc>::__remove_return_type 00533 list<_Tp, _Alloc>:: 00534 remove_if(_Predicate __pred) 00535 { 00536 size_type __removed __attribute__((__unused__)) = 0; 00537 iterator __first = begin(); 00538 iterator __last = end(); 00539 while (__first != __last) 00540 { 00541 iterator __next = __first; 00542 ++__next; 00543 if (__pred(*__first)) 00544 { 00545 _M_erase(__first); 00546 _GLIBCXX20_ONLY( __removed++ ); 00547 } 00548 __first = __next; 00549 } 00550 return _GLIBCXX20_ONLY( __removed ); 00551 } 00552 00553 template<typename _Tp, typename _Alloc> 00554 template <typename _BinaryPredicate> 00555 typename list<_Tp, _Alloc>::__remove_return_type 00556 list<_Tp, _Alloc>:: 00557 unique(_BinaryPredicate __binary_pred) 00558 { 00559 iterator __first = begin(); 00560 iterator __last = end(); 00561 if (__first == __last) 00562 return _GLIBCXX20_ONLY(0); 00563 size_type __removed __attribute__((__unused__)) = 0; 00564 iterator __next = __first; 00565 while (++__next != __last) 00566 { 00567 if (__binary_pred(*__first, *__next)) 00568 { 00569 _M_erase(__next); 00570 _GLIBCXX20_ONLY( __removed++ ); 00571 } 00572 else 00573 __first = __next; 00574 __next = __first; 00575 } 00576 return _GLIBCXX20_ONLY( __removed ); 00577 } 00578 00579 #undef _GLIBCXX20_ONLY 00580 00581 template<typename _Tp, typename _Alloc> 00582 template <typename _StrictWeakOrdering> 00583 void 00584 list<_Tp, _Alloc>:: 00585 sort(_StrictWeakOrdering __comp) 00586 { 00587 // Do nothing if the list has length 0 or 1. 00588 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00589 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00590 { 00591 list __carry; 00592 list __tmp[64]; 00593 list * __fill = __tmp; 00594 list * __counter; 00595 __try 00596 { 00597 do 00598 { 00599 __carry.splice(__carry.begin(), *this, begin()); 00600 00601 for(__counter = __tmp; 00602 __counter != __fill && !__counter->empty(); 00603 ++__counter) 00604 { 00605 __counter->merge(__carry, __comp); 00606 __carry.swap(*__counter); 00607 } 00608 __carry.swap(*__counter); 00609 if (__counter == __fill) 00610 ++__fill; 00611 } 00612 while ( !empty() ); 00613 00614 for (__counter = __tmp + 1; __counter != __fill; ++__counter) 00615 __counter->merge(*(__counter - 1), __comp); 00616 swap(*(__fill - 1)); 00617 } 00618 __catch(...) 00619 { 00620 this->splice(this->end(), __carry); 00621 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) 00622 this->splice(this->end(), __tmp[__i]); 00623 __throw_exception_again; 00624 } 00625 } 00626 } 00627 00628 _GLIBCXX_END_NAMESPACE_CONTAINER 00629 _GLIBCXX_END_NAMESPACE_VERSION 00630 } // namespace std 00631 00632 #endif /* _LIST_TCC */ 00633