libstdc++
|
00001 // List 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) 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 #if __cplusplus >= 201103L 00075 _M_get_Node_allocator().destroy(__tmp); 00076 #else 00077 _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data)); 00078 #endif 00079 _M_put_node(__tmp); 00080 } 00081 } 00082 00083 #if __cplusplus >= 201103L 00084 template<typename _Tp, typename _Alloc> 00085 template<typename... _Args> 00086 typename list<_Tp, _Alloc>::iterator 00087 list<_Tp, _Alloc>:: 00088 emplace(const_iterator __position, _Args&&... __args) 00089 { 00090 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 00091 __tmp->_M_hook(__position._M_const_cast()._M_node); 00092 this->_M_inc_size(1); 00093 return iterator(__tmp); 00094 } 00095 #endif 00096 00097 template<typename _Tp, typename _Alloc> 00098 typename list<_Tp, _Alloc>::iterator 00099 list<_Tp, _Alloc>:: 00100 #if __cplusplus >= 201103L 00101 insert(const_iterator __position, const value_type& __x) 00102 #else 00103 insert(iterator __position, const value_type& __x) 00104 #endif 00105 { 00106 _Node* __tmp = _M_create_node(__x); 00107 __tmp->_M_hook(__position._M_const_cast()._M_node); 00108 this->_M_inc_size(1); 00109 return iterator(__tmp); 00110 } 00111 00112 #if __cplusplus >= 201103L 00113 template<typename _Tp, typename _Alloc> 00114 typename list<_Tp, _Alloc>::iterator 00115 list<_Tp, _Alloc>:: 00116 insert(const_iterator __position, size_type __n, const value_type& __x) 00117 { 00118 if (__n) 00119 { 00120 list __tmp(__n, __x, get_allocator()); 00121 iterator __it = __tmp.begin(); 00122 splice(__position, __tmp); 00123 return __it; 00124 } 00125 return __position._M_const_cast(); 00126 } 00127 00128 template<typename _Tp, typename _Alloc> 00129 template<typename _InputIterator, typename> 00130 typename list<_Tp, _Alloc>::iterator 00131 list<_Tp, _Alloc>:: 00132 insert(const_iterator __position, _InputIterator __first, 00133 _InputIterator __last) 00134 { 00135 list __tmp(__first, __last, get_allocator()); 00136 if (!__tmp.empty()) 00137 { 00138 iterator __it = __tmp.begin(); 00139 splice(__position, __tmp); 00140 return __it; 00141 } 00142 return __position._M_const_cast(); 00143 } 00144 #endif 00145 00146 template<typename _Tp, typename _Alloc> 00147 typename list<_Tp, _Alloc>::iterator 00148 list<_Tp, _Alloc>:: 00149 #if __cplusplus >= 201103L 00150 erase(const_iterator __position) noexcept 00151 #else 00152 erase(iterator __position) 00153 #endif 00154 { 00155 iterator __ret = iterator(__position._M_node->_M_next); 00156 _M_erase(__position._M_const_cast()); 00157 return __ret; 00158 } 00159 00160 #if __cplusplus >= 201103L 00161 template<typename _Tp, typename _Alloc> 00162 void 00163 list<_Tp, _Alloc>:: 00164 _M_default_append(size_type __n) 00165 { 00166 size_type __i = 0; 00167 __try 00168 { 00169 for (; __i < __n; ++__i) 00170 emplace_back(); 00171 } 00172 __catch(...) 00173 { 00174 for (; __i; --__i) 00175 pop_back(); 00176 __throw_exception_again; 00177 } 00178 } 00179 00180 template<typename _Tp, typename _Alloc> 00181 void 00182 list<_Tp, _Alloc>:: 00183 resize(size_type __new_size) 00184 { 00185 iterator __i = begin(); 00186 size_type __len = 0; 00187 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00188 ; 00189 if (__len == __new_size) 00190 erase(__i, end()); 00191 else // __i == end() 00192 _M_default_append(__new_size - __len); 00193 } 00194 00195 template<typename _Tp, typename _Alloc> 00196 void 00197 list<_Tp, _Alloc>:: 00198 resize(size_type __new_size, const value_type& __x) 00199 { 00200 iterator __i = begin(); 00201 size_type __len = 0; 00202 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00203 ; 00204 if (__len == __new_size) 00205 erase(__i, end()); 00206 else // __i == end() 00207 insert(end(), __new_size - __len, __x); 00208 } 00209 #else 00210 template<typename _Tp, typename _Alloc> 00211 void 00212 list<_Tp, _Alloc>:: 00213 resize(size_type __new_size, value_type __x) 00214 { 00215 iterator __i = begin(); 00216 size_type __len = 0; 00217 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00218 ; 00219 if (__len == __new_size) 00220 erase(__i, end()); 00221 else // __i == end() 00222 insert(end(), __new_size - __len, __x); 00223 } 00224 #endif 00225 00226 template<typename _Tp, typename _Alloc> 00227 list<_Tp, _Alloc>& 00228 list<_Tp, _Alloc>:: 00229 operator=(const list& __x) 00230 { 00231 if (this != &__x) 00232 { 00233 iterator __first1 = begin(); 00234 iterator __last1 = end(); 00235 const_iterator __first2 = __x.begin(); 00236 const_iterator __last2 = __x.end(); 00237 for (; __first1 != __last1 && __first2 != __last2; 00238 ++__first1, ++__first2) 00239 *__first1 = *__first2; 00240 if (__first2 == __last2) 00241 erase(__first1, __last1); 00242 else 00243 insert(__last1, __first2, __last2); 00244 } 00245 return *this; 00246 } 00247 00248 template<typename _Tp, typename _Alloc> 00249 void 00250 list<_Tp, _Alloc>:: 00251 _M_fill_assign(size_type __n, const value_type& __val) 00252 { 00253 iterator __i = begin(); 00254 for (; __i != end() && __n > 0; ++__i, --__n) 00255 *__i = __val; 00256 if (__n > 0) 00257 insert(end(), __n, __val); 00258 else 00259 erase(__i, end()); 00260 } 00261 00262 template<typename _Tp, typename _Alloc> 00263 template <typename _InputIterator> 00264 void 00265 list<_Tp, _Alloc>:: 00266 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 00267 __false_type) 00268 { 00269 iterator __first1 = begin(); 00270 iterator __last1 = end(); 00271 for (; __first1 != __last1 && __first2 != __last2; 00272 ++__first1, ++__first2) 00273 *__first1 = *__first2; 00274 if (__first2 == __last2) 00275 erase(__first1, __last1); 00276 else 00277 insert(__last1, __first2, __last2); 00278 } 00279 00280 template<typename _Tp, typename _Alloc> 00281 void 00282 list<_Tp, _Alloc>:: 00283 remove(const value_type& __value) 00284 { 00285 iterator __first = begin(); 00286 iterator __last = end(); 00287 iterator __extra = __last; 00288 while (__first != __last) 00289 { 00290 iterator __next = __first; 00291 ++__next; 00292 if (*__first == __value) 00293 { 00294 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00295 // 526. Is it undefined if a function in the standard changes 00296 // in parameters? 00297 if (std::__addressof(*__first) != std::__addressof(__value)) 00298 _M_erase(__first); 00299 else 00300 __extra = __first; 00301 } 00302 __first = __next; 00303 } 00304 if (__extra != __last) 00305 _M_erase(__extra); 00306 } 00307 00308 template<typename _Tp, typename _Alloc> 00309 void 00310 list<_Tp, _Alloc>:: 00311 unique() 00312 { 00313 iterator __first = begin(); 00314 iterator __last = end(); 00315 if (__first == __last) 00316 return; 00317 iterator __next = __first; 00318 while (++__next != __last) 00319 { 00320 if (*__first == *__next) 00321 _M_erase(__next); 00322 else 00323 __first = __next; 00324 __next = __first; 00325 } 00326 } 00327 00328 template<typename _Tp, typename _Alloc> 00329 void 00330 list<_Tp, _Alloc>:: 00331 #if __cplusplus >= 201103L 00332 merge(list&& __x) 00333 #else 00334 merge(list& __x) 00335 #endif 00336 { 00337 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00338 // 300. list::merge() specification incomplete 00339 if (this != &__x) 00340 { 00341 _M_check_equal_allocators(__x); 00342 00343 iterator __first1 = begin(); 00344 iterator __last1 = end(); 00345 iterator __first2 = __x.begin(); 00346 iterator __last2 = __x.end(); 00347 while (__first1 != __last1 && __first2 != __last2) 00348 if (*__first2 < *__first1) 00349 { 00350 iterator __next = __first2; 00351 _M_transfer(__first1, __first2, ++__next); 00352 __first2 = __next; 00353 } 00354 else 00355 ++__first1; 00356 if (__first2 != __last2) 00357 _M_transfer(__last1, __first2, __last2); 00358 00359 this->_M_inc_size(__x._M_get_size()); 00360 __x._M_set_size(0); 00361 } 00362 } 00363 00364 template<typename _Tp, typename _Alloc> 00365 template <typename _StrictWeakOrdering> 00366 void 00367 list<_Tp, _Alloc>:: 00368 #if __cplusplus >= 201103L 00369 merge(list&& __x, _StrictWeakOrdering __comp) 00370 #else 00371 merge(list& __x, _StrictWeakOrdering __comp) 00372 #endif 00373 { 00374 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00375 // 300. list::merge() specification incomplete 00376 if (this != &__x) 00377 { 00378 _M_check_equal_allocators(__x); 00379 00380 iterator __first1 = begin(); 00381 iterator __last1 = end(); 00382 iterator __first2 = __x.begin(); 00383 iterator __last2 = __x.end(); 00384 while (__first1 != __last1 && __first2 != __last2) 00385 if (__comp(*__first2, *__first1)) 00386 { 00387 iterator __next = __first2; 00388 _M_transfer(__first1, __first2, ++__next); 00389 __first2 = __next; 00390 } 00391 else 00392 ++__first1; 00393 if (__first2 != __last2) 00394 _M_transfer(__last1, __first2, __last2); 00395 00396 this->_M_inc_size(__x._M_get_size()); 00397 __x._M_set_size(0); 00398 } 00399 } 00400 00401 template<typename _Tp, typename _Alloc> 00402 void 00403 list<_Tp, _Alloc>:: 00404 sort() 00405 { 00406 // Do nothing if the list has length 0 or 1. 00407 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00408 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00409 { 00410 list __carry; 00411 list __tmp[64]; 00412 list * __fill = &__tmp[0]; 00413 list * __counter; 00414 00415 do 00416 { 00417 __carry.splice(__carry.begin(), *this, begin()); 00418 00419 for(__counter = &__tmp[0]; 00420 __counter != __fill && !__counter->empty(); 00421 ++__counter) 00422 { 00423 __counter->merge(__carry); 00424 __carry.swap(*__counter); 00425 } 00426 __carry.swap(*__counter); 00427 if (__counter == __fill) 00428 ++__fill; 00429 } 00430 while ( !empty() ); 00431 00432 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00433 __counter->merge(*(__counter - 1)); 00434 swap( *(__fill - 1) ); 00435 } 00436 } 00437 00438 template<typename _Tp, typename _Alloc> 00439 template <typename _Predicate> 00440 void 00441 list<_Tp, _Alloc>:: 00442 remove_if(_Predicate __pred) 00443 { 00444 iterator __first = begin(); 00445 iterator __last = end(); 00446 while (__first != __last) 00447 { 00448 iterator __next = __first; 00449 ++__next; 00450 if (__pred(*__first)) 00451 _M_erase(__first); 00452 __first = __next; 00453 } 00454 } 00455 00456 template<typename _Tp, typename _Alloc> 00457 template <typename _BinaryPredicate> 00458 void 00459 list<_Tp, _Alloc>:: 00460 unique(_BinaryPredicate __binary_pred) 00461 { 00462 iterator __first = begin(); 00463 iterator __last = end(); 00464 if (__first == __last) 00465 return; 00466 iterator __next = __first; 00467 while (++__next != __last) 00468 { 00469 if (__binary_pred(*__first, *__next)) 00470 _M_erase(__next); 00471 else 00472 __first = __next; 00473 __next = __first; 00474 } 00475 } 00476 00477 template<typename _Tp, typename _Alloc> 00478 template <typename _StrictWeakOrdering> 00479 void 00480 list<_Tp, _Alloc>:: 00481 sort(_StrictWeakOrdering __comp) 00482 { 00483 // Do nothing if the list has length 0 or 1. 00484 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00485 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00486 { 00487 list __carry; 00488 list __tmp[64]; 00489 list * __fill = &__tmp[0]; 00490 list * __counter; 00491 00492 do 00493 { 00494 __carry.splice(__carry.begin(), *this, begin()); 00495 00496 for(__counter = &__tmp[0]; 00497 __counter != __fill && !__counter->empty(); 00498 ++__counter) 00499 { 00500 __counter->merge(__carry, __comp); 00501 __carry.swap(*__counter); 00502 } 00503 __carry.swap(*__counter); 00504 if (__counter == __fill) 00505 ++__fill; 00506 } 00507 while ( !empty() ); 00508 00509 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00510 __counter->merge(*(__counter - 1), __comp); 00511 swap(*(__fill - 1)); 00512 } 00513 } 00514 00515 _GLIBCXX_END_NAMESPACE_CONTAINER 00516 } // namespace std 00517 00518 #endif /* _LIST_TCC */ 00519