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