libstdc++
|
00001 // List 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) 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, ++__first2) 00316 *__first1 = *__first2; 00317 if (__first2 == __last2) 00318 erase(__first1, __last1); 00319 else 00320 insert(__last1, __first2, __last2); 00321 } 00322 00323 template<typename _Tp, typename _Alloc> 00324 void 00325 list<_Tp, _Alloc>:: 00326 remove(const value_type& __value) 00327 { 00328 iterator __first = begin(); 00329 iterator __last = end(); 00330 iterator __extra = __last; 00331 while (__first != __last) 00332 { 00333 iterator __next = __first; 00334 ++__next; 00335 if (*__first == __value) 00336 { 00337 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00338 // 526. Is it undefined if a function in the standard changes 00339 // in parameters? 00340 if (std::__addressof(*__first) != std::__addressof(__value)) 00341 _M_erase(__first); 00342 else 00343 __extra = __first; 00344 } 00345 __first = __next; 00346 } 00347 if (__extra != __last) 00348 _M_erase(__extra); 00349 } 00350 00351 template<typename _Tp, typename _Alloc> 00352 void 00353 list<_Tp, _Alloc>:: 00354 unique() 00355 { 00356 iterator __first = begin(); 00357 iterator __last = end(); 00358 if (__first == __last) 00359 return; 00360 iterator __next = __first; 00361 while (++__next != __last) 00362 { 00363 if (*__first == *__next) 00364 _M_erase(__next); 00365 else 00366 __first = __next; 00367 __next = __first; 00368 } 00369 } 00370 00371 template<typename _Tp, typename _Alloc> 00372 void 00373 list<_Tp, _Alloc>:: 00374 #if __cplusplus >= 201103L 00375 merge(list&& __x) 00376 #else 00377 merge(list& __x) 00378 #endif 00379 { 00380 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00381 // 300. list::merge() specification incomplete 00382 if (this != std::__addressof(__x)) 00383 { 00384 _M_check_equal_allocators(__x); 00385 00386 iterator __first1 = begin(); 00387 iterator __last1 = end(); 00388 iterator __first2 = __x.begin(); 00389 iterator __last2 = __x.end(); 00390 const size_t __orig_size = __x.size(); 00391 __try { 00392 while (__first1 != __last1 && __first2 != __last2) 00393 if (*__first2 < *__first1) 00394 { 00395 iterator __next = __first2; 00396 _M_transfer(__first1, __first2, ++__next); 00397 __first2 = __next; 00398 } 00399 else 00400 ++__first1; 00401 if (__first2 != __last2) 00402 _M_transfer(__last1, __first2, __last2); 00403 00404 this->_M_inc_size(__x._M_get_size()); 00405 __x._M_set_size(0); 00406 } 00407 __catch(...) 00408 { 00409 const size_t __dist = std::distance(__first2, __last2); 00410 this->_M_inc_size(__orig_size - __dist); 00411 __x._M_set_size(__dist); 00412 __throw_exception_again; 00413 } 00414 } 00415 } 00416 00417 template<typename _Tp, typename _Alloc> 00418 template <typename _StrictWeakOrdering> 00419 void 00420 list<_Tp, _Alloc>:: 00421 #if __cplusplus >= 201103L 00422 merge(list&& __x, _StrictWeakOrdering __comp) 00423 #else 00424 merge(list& __x, _StrictWeakOrdering __comp) 00425 #endif 00426 { 00427 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00428 // 300. list::merge() specification incomplete 00429 if (this != std::__addressof(__x)) 00430 { 00431 _M_check_equal_allocators(__x); 00432 00433 iterator __first1 = begin(); 00434 iterator __last1 = end(); 00435 iterator __first2 = __x.begin(); 00436 iterator __last2 = __x.end(); 00437 const size_t __orig_size = __x.size(); 00438 __try 00439 { 00440 while (__first1 != __last1 && __first2 != __last2) 00441 if (__comp(*__first2, *__first1)) 00442 { 00443 iterator __next = __first2; 00444 _M_transfer(__first1, __first2, ++__next); 00445 __first2 = __next; 00446 } 00447 else 00448 ++__first1; 00449 if (__first2 != __last2) 00450 _M_transfer(__last1, __first2, __last2); 00451 00452 this->_M_inc_size(__x._M_get_size()); 00453 __x._M_set_size(0); 00454 } 00455 __catch(...) 00456 { 00457 const size_t __dist = std::distance(__first2, __last2); 00458 this->_M_inc_size(__orig_size - __dist); 00459 __x._M_set_size(__dist); 00460 __throw_exception_again; 00461 } 00462 } 00463 } 00464 00465 template<typename _Tp, typename _Alloc> 00466 void 00467 list<_Tp, _Alloc>:: 00468 sort() 00469 { 00470 // Do nothing if the list has length 0 or 1. 00471 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00472 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00473 { 00474 list __carry; 00475 list __tmp[64]; 00476 list * __fill = __tmp; 00477 list * __counter; 00478 __try 00479 { 00480 do 00481 { 00482 __carry.splice(__carry.begin(), *this, begin()); 00483 00484 for(__counter = __tmp; 00485 __counter != __fill && !__counter->empty(); 00486 ++__counter) 00487 { 00488 __counter->merge(__carry); 00489 __carry.swap(*__counter); 00490 } 00491 __carry.swap(*__counter); 00492 if (__counter == __fill) 00493 ++__fill; 00494 } 00495 while ( !empty() ); 00496 00497 for (__counter = __tmp + 1; __counter != __fill; ++__counter) 00498 __counter->merge(*(__counter - 1)); 00499 swap( *(__fill - 1) ); 00500 } 00501 __catch(...) 00502 { 00503 this->splice(this->end(), __carry); 00504 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) 00505 this->splice(this->end(), __tmp[__i]); 00506 __throw_exception_again; 00507 } 00508 } 00509 } 00510 00511 template<typename _Tp, typename _Alloc> 00512 template <typename _Predicate> 00513 void 00514 list<_Tp, _Alloc>:: 00515 remove_if(_Predicate __pred) 00516 { 00517 iterator __first = begin(); 00518 iterator __last = end(); 00519 while (__first != __last) 00520 { 00521 iterator __next = __first; 00522 ++__next; 00523 if (__pred(*__first)) 00524 _M_erase(__first); 00525 __first = __next; 00526 } 00527 } 00528 00529 template<typename _Tp, typename _Alloc> 00530 template <typename _BinaryPredicate> 00531 void 00532 list<_Tp, _Alloc>:: 00533 unique(_BinaryPredicate __binary_pred) 00534 { 00535 iterator __first = begin(); 00536 iterator __last = end(); 00537 if (__first == __last) 00538 return; 00539 iterator __next = __first; 00540 while (++__next != __last) 00541 { 00542 if (__binary_pred(*__first, *__next)) 00543 _M_erase(__next); 00544 else 00545 __first = __next; 00546 __next = __first; 00547 } 00548 } 00549 00550 template<typename _Tp, typename _Alloc> 00551 template <typename _StrictWeakOrdering> 00552 void 00553 list<_Tp, _Alloc>:: 00554 sort(_StrictWeakOrdering __comp) 00555 { 00556 // Do nothing if the list has length 0 or 1. 00557 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00558 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00559 { 00560 list __carry; 00561 list __tmp[64]; 00562 list * __fill = __tmp; 00563 list * __counter; 00564 __try 00565 { 00566 do 00567 { 00568 __carry.splice(__carry.begin(), *this, begin()); 00569 00570 for(__counter = __tmp; 00571 __counter != __fill && !__counter->empty(); 00572 ++__counter) 00573 { 00574 __counter->merge(__carry, __comp); 00575 __carry.swap(*__counter); 00576 } 00577 __carry.swap(*__counter); 00578 if (__counter == __fill) 00579 ++__fill; 00580 } 00581 while ( !empty() ); 00582 00583 for (__counter = __tmp + 1; __counter != __fill; ++__counter) 00584 __counter->merge(*(__counter - 1), __comp); 00585 swap(*(__fill - 1)); 00586 } 00587 __catch(...) 00588 { 00589 this->splice(this->end(), __carry); 00590 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) 00591 this->splice(this->end(), __tmp[__i]); 00592 __throw_exception_again; 00593 } 00594 } 00595 } 00596 00597 _GLIBCXX_END_NAMESPACE_CONTAINER 00598 _GLIBCXX_END_NAMESPACE_VERSION 00599 } // namespace std 00600 00601 #endif /* _LIST_TCC */ 00602