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