libstdc++
|
00001 // List implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 00004 // 2011 Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996,1997 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file bits/list.tcc 00053 * This is an internal header file, included by other library headers. 00054 * Do not attempt to use it directly. @headername{list} 00055 */ 00056 00057 #ifndef _LIST_TCC 00058 #define _LIST_TCC 1 00059 00060 namespace std _GLIBCXX_VISIBILITY(default) 00061 { 00062 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00063 00064 template<typename _Tp, typename _Alloc> 00065 void 00066 _List_base<_Tp, _Alloc>:: 00067 _M_clear() 00068 { 00069 typedef _List_node<_Tp> _Node; 00070 _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next); 00071 while (__cur != &this->_M_impl._M_node) 00072 { 00073 _Node* __tmp = __cur; 00074 __cur = static_cast<_Node*>(__cur->_M_next); 00075 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00076 _M_get_Node_allocator().destroy(__tmp); 00077 #else 00078 _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data)); 00079 #endif 00080 _M_put_node(__tmp); 00081 } 00082 } 00083 00084 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00085 template<typename _Tp, typename _Alloc> 00086 template<typename... _Args> 00087 typename list<_Tp, _Alloc>::iterator 00088 list<_Tp, _Alloc>:: 00089 emplace(iterator __position, _Args&&... __args) 00090 { 00091 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 00092 __tmp->_M_hook(__position._M_node); 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 insert(iterator __position, const value_type& __x) 00101 { 00102 _Node* __tmp = _M_create_node(__x); 00103 __tmp->_M_hook(__position._M_node); 00104 return iterator(__tmp); 00105 } 00106 00107 template<typename _Tp, typename _Alloc> 00108 typename list<_Tp, _Alloc>::iterator 00109 list<_Tp, _Alloc>:: 00110 erase(iterator __position) 00111 { 00112 iterator __ret = iterator(__position._M_node->_M_next); 00113 _M_erase(__position); 00114 return __ret; 00115 } 00116 00117 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00118 template<typename _Tp, typename _Alloc> 00119 void 00120 list<_Tp, _Alloc>:: 00121 _M_default_append(size_type __n) 00122 { 00123 size_type __i = 0; 00124 __try 00125 { 00126 for (; __i < __n; ++__i) 00127 emplace_back(); 00128 } 00129 __catch(...) 00130 { 00131 for (; __i; --__i) 00132 pop_back(); 00133 __throw_exception_again; 00134 } 00135 } 00136 00137 template<typename _Tp, typename _Alloc> 00138 void 00139 list<_Tp, _Alloc>:: 00140 resize(size_type __new_size) 00141 { 00142 iterator __i = begin(); 00143 size_type __len = 0; 00144 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00145 ; 00146 if (__len == __new_size) 00147 erase(__i, end()); 00148 else // __i == end() 00149 _M_default_append(__new_size - __len); 00150 } 00151 00152 template<typename _Tp, typename _Alloc> 00153 void 00154 list<_Tp, _Alloc>:: 00155 resize(size_type __new_size, const value_type& __x) 00156 { 00157 iterator __i = begin(); 00158 size_type __len = 0; 00159 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00160 ; 00161 if (__len == __new_size) 00162 erase(__i, end()); 00163 else // __i == end() 00164 insert(end(), __new_size - __len, __x); 00165 } 00166 #else 00167 template<typename _Tp, typename _Alloc> 00168 void 00169 list<_Tp, _Alloc>:: 00170 resize(size_type __new_size, value_type __x) 00171 { 00172 iterator __i = begin(); 00173 size_type __len = 0; 00174 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00175 ; 00176 if (__len == __new_size) 00177 erase(__i, end()); 00178 else // __i == end() 00179 insert(end(), __new_size - __len, __x); 00180 } 00181 #endif 00182 00183 template<typename _Tp, typename _Alloc> 00184 list<_Tp, _Alloc>& 00185 list<_Tp, _Alloc>:: 00186 operator=(const list& __x) 00187 { 00188 if (this != &__x) 00189 { 00190 iterator __first1 = begin(); 00191 iterator __last1 = end(); 00192 const_iterator __first2 = __x.begin(); 00193 const_iterator __last2 = __x.end(); 00194 for (; __first1 != __last1 && __first2 != __last2; 00195 ++__first1, ++__first2) 00196 *__first1 = *__first2; 00197 if (__first2 == __last2) 00198 erase(__first1, __last1); 00199 else 00200 insert(__last1, __first2, __last2); 00201 } 00202 return *this; 00203 } 00204 00205 template<typename _Tp, typename _Alloc> 00206 void 00207 list<_Tp, _Alloc>:: 00208 _M_fill_assign(size_type __n, const value_type& __val) 00209 { 00210 iterator __i = begin(); 00211 for (; __i != end() && __n > 0; ++__i, --__n) 00212 *__i = __val; 00213 if (__n > 0) 00214 insert(end(), __n, __val); 00215 else 00216 erase(__i, end()); 00217 } 00218 00219 template<typename _Tp, typename _Alloc> 00220 template <typename _InputIterator> 00221 void 00222 list<_Tp, _Alloc>:: 00223 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 00224 __false_type) 00225 { 00226 iterator __first1 = begin(); 00227 iterator __last1 = end(); 00228 for (; __first1 != __last1 && __first2 != __last2; 00229 ++__first1, ++__first2) 00230 *__first1 = *__first2; 00231 if (__first2 == __last2) 00232 erase(__first1, __last1); 00233 else 00234 insert(__last1, __first2, __last2); 00235 } 00236 00237 template<typename _Tp, typename _Alloc> 00238 void 00239 list<_Tp, _Alloc>:: 00240 remove(const value_type& __value) 00241 { 00242 iterator __first = begin(); 00243 iterator __last = end(); 00244 iterator __extra = __last; 00245 while (__first != __last) 00246 { 00247 iterator __next = __first; 00248 ++__next; 00249 if (*__first == __value) 00250 { 00251 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00252 // 526. Is it undefined if a function in the standard changes 00253 // in parameters? 00254 if (std::__addressof(*__first) != std::__addressof(__value)) 00255 _M_erase(__first); 00256 else 00257 __extra = __first; 00258 } 00259 __first = __next; 00260 } 00261 if (__extra != __last) 00262 _M_erase(__extra); 00263 } 00264 00265 template<typename _Tp, typename _Alloc> 00266 void 00267 list<_Tp, _Alloc>:: 00268 unique() 00269 { 00270 iterator __first = begin(); 00271 iterator __last = end(); 00272 if (__first == __last) 00273 return; 00274 iterator __next = __first; 00275 while (++__next != __last) 00276 { 00277 if (*__first == *__next) 00278 _M_erase(__next); 00279 else 00280 __first = __next; 00281 __next = __first; 00282 } 00283 } 00284 00285 template<typename _Tp, typename _Alloc> 00286 void 00287 list<_Tp, _Alloc>:: 00288 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00289 merge(list&& __x) 00290 #else 00291 merge(list& __x) 00292 #endif 00293 { 00294 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00295 // 300. list::merge() specification incomplete 00296 if (this != &__x) 00297 { 00298 _M_check_equal_allocators(__x); 00299 00300 iterator __first1 = begin(); 00301 iterator __last1 = end(); 00302 iterator __first2 = __x.begin(); 00303 iterator __last2 = __x.end(); 00304 while (__first1 != __last1 && __first2 != __last2) 00305 if (*__first2 < *__first1) 00306 { 00307 iterator __next = __first2; 00308 _M_transfer(__first1, __first2, ++__next); 00309 __first2 = __next; 00310 } 00311 else 00312 ++__first1; 00313 if (__first2 != __last2) 00314 _M_transfer(__last1, __first2, __last2); 00315 } 00316 } 00317 00318 template<typename _Tp, typename _Alloc> 00319 template <typename _StrictWeakOrdering> 00320 void 00321 list<_Tp, _Alloc>:: 00322 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00323 merge(list&& __x, _StrictWeakOrdering __comp) 00324 #else 00325 merge(list& __x, _StrictWeakOrdering __comp) 00326 #endif 00327 { 00328 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00329 // 300. list::merge() specification incomplete 00330 if (this != &__x) 00331 { 00332 _M_check_equal_allocators(__x); 00333 00334 iterator __first1 = begin(); 00335 iterator __last1 = end(); 00336 iterator __first2 = __x.begin(); 00337 iterator __last2 = __x.end(); 00338 while (__first1 != __last1 && __first2 != __last2) 00339 if (__comp(*__first2, *__first1)) 00340 { 00341 iterator __next = __first2; 00342 _M_transfer(__first1, __first2, ++__next); 00343 __first2 = __next; 00344 } 00345 else 00346 ++__first1; 00347 if (__first2 != __last2) 00348 _M_transfer(__last1, __first2, __last2); 00349 } 00350 } 00351 00352 template<typename _Tp, typename _Alloc> 00353 void 00354 list<_Tp, _Alloc>:: 00355 sort() 00356 { 00357 // Do nothing if the list has length 0 or 1. 00358 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00359 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00360 { 00361 list __carry; 00362 list __tmp[64]; 00363 list * __fill = &__tmp[0]; 00364 list * __counter; 00365 00366 do 00367 { 00368 __carry.splice(__carry.begin(), *this, begin()); 00369 00370 for(__counter = &__tmp[0]; 00371 __counter != __fill && !__counter->empty(); 00372 ++__counter) 00373 { 00374 __counter->merge(__carry); 00375 __carry.swap(*__counter); 00376 } 00377 __carry.swap(*__counter); 00378 if (__counter == __fill) 00379 ++__fill; 00380 } 00381 while ( !empty() ); 00382 00383 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00384 __counter->merge(*(__counter - 1)); 00385 swap( *(__fill - 1) ); 00386 } 00387 } 00388 00389 template<typename _Tp, typename _Alloc> 00390 template <typename _Predicate> 00391 void 00392 list<_Tp, _Alloc>:: 00393 remove_if(_Predicate __pred) 00394 { 00395 iterator __first = begin(); 00396 iterator __last = end(); 00397 while (__first != __last) 00398 { 00399 iterator __next = __first; 00400 ++__next; 00401 if (__pred(*__first)) 00402 _M_erase(__first); 00403 __first = __next; 00404 } 00405 } 00406 00407 template<typename _Tp, typename _Alloc> 00408 template <typename _BinaryPredicate> 00409 void 00410 list<_Tp, _Alloc>:: 00411 unique(_BinaryPredicate __binary_pred) 00412 { 00413 iterator __first = begin(); 00414 iterator __last = end(); 00415 if (__first == __last) 00416 return; 00417 iterator __next = __first; 00418 while (++__next != __last) 00419 { 00420 if (__binary_pred(*__first, *__next)) 00421 _M_erase(__next); 00422 else 00423 __first = __next; 00424 __next = __first; 00425 } 00426 } 00427 00428 template<typename _Tp, typename _Alloc> 00429 template <typename _StrictWeakOrdering> 00430 void 00431 list<_Tp, _Alloc>:: 00432 sort(_StrictWeakOrdering __comp) 00433 { 00434 // Do nothing if the list has length 0 or 1. 00435 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00436 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00437 { 00438 list __carry; 00439 list __tmp[64]; 00440 list * __fill = &__tmp[0]; 00441 list * __counter; 00442 00443 do 00444 { 00445 __carry.splice(__carry.begin(), *this, begin()); 00446 00447 for(__counter = &__tmp[0]; 00448 __counter != __fill && !__counter->empty(); 00449 ++__counter) 00450 { 00451 __counter->merge(__carry, __comp); 00452 __carry.swap(*__counter); 00453 } 00454 __carry.swap(*__counter); 00455 if (__counter == __fill) 00456 ++__fill; 00457 } 00458 while ( !empty() ); 00459 00460 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00461 __counter->merge(*(__counter - 1), __comp); 00462 swap(*(__fill - 1)); 00463 } 00464 } 00465 00466 _GLIBCXX_END_NAMESPACE_CONTAINER 00467 } // namespace std 00468 00469 #endif /* _LIST_TCC */ 00470