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*>(_M_impl._M_node._M_next); 00071 while (__cur != &_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 if (__new_size > size()) 00143 _M_default_append(__new_size - size()); 00144 else if (__new_size < size()) 00145 { 00146 iterator __i = begin(); 00147 std::advance(__i, __new_size); 00148 erase(__i, end()); 00149 } 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 if (__new_size > size()) 00158 insert(end(), __new_size - size(), __x); 00159 else if (__new_size < size()) 00160 { 00161 iterator __i = begin(); 00162 std::advance(__i, __new_size); 00163 erase(__i, end()); 00164 } 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 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00317 this->_M_impl._M_size += __x.size(); 00318 __x._M_impl._M_size = 0; 00319 #endif 00320 } 00321 } 00322 00323 template<typename _Tp, typename _Alloc> 00324 template <typename _StrictWeakOrdering> 00325 void 00326 list<_Tp, _Alloc>:: 00327 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00328 merge(list&& __x, _StrictWeakOrdering __comp) 00329 #else 00330 merge(list& __x, _StrictWeakOrdering __comp) 00331 #endif 00332 { 00333 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00334 // 300. list::merge() specification incomplete 00335 if (this != &__x) 00336 { 00337 _M_check_equal_allocators(__x); 00338 00339 iterator __first1 = begin(); 00340 iterator __last1 = end(); 00341 iterator __first2 = __x.begin(); 00342 iterator __last2 = __x.end(); 00343 while (__first1 != __last1 && __first2 != __last2) 00344 if (__comp(*__first2, *__first1)) 00345 { 00346 iterator __next = __first2; 00347 _M_transfer(__first1, __first2, ++__next); 00348 __first2 = __next; 00349 } 00350 else 00351 ++__first1; 00352 if (__first2 != __last2) 00353 _M_transfer(__last1, __first2, __last2); 00354 00355 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00356 this->_M_impl._M_size += __x.size(); 00357 __x._M_impl._M_size = 0; 00358 #endif 00359 } 00360 } 00361 00362 template<typename _Tp, typename _Alloc> 00363 void 00364 list<_Tp, _Alloc>:: 00365 sort() 00366 { 00367 // Do nothing if the list has length 0 or 1. 00368 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00369 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00370 { 00371 list __carry; 00372 list __tmp[64]; 00373 list * __fill = &__tmp[0]; 00374 list * __counter; 00375 00376 do 00377 { 00378 __carry.splice(__carry.begin(), *this, begin()); 00379 00380 for(__counter = &__tmp[0]; 00381 __counter != __fill && !__counter->empty(); 00382 ++__counter) 00383 { 00384 __counter->merge(__carry); 00385 __carry.swap(*__counter); 00386 } 00387 __carry.swap(*__counter); 00388 if (__counter == __fill) 00389 ++__fill; 00390 } 00391 while ( !empty() ); 00392 00393 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00394 __counter->merge(*(__counter - 1)); 00395 swap( *(__fill - 1) ); 00396 } 00397 } 00398 00399 template<typename _Tp, typename _Alloc> 00400 template <typename _Predicate> 00401 void 00402 list<_Tp, _Alloc>:: 00403 remove_if(_Predicate __pred) 00404 { 00405 iterator __first = begin(); 00406 iterator __last = end(); 00407 while (__first != __last) 00408 { 00409 iterator __next = __first; 00410 ++__next; 00411 if (__pred(*__first)) 00412 _M_erase(__first); 00413 __first = __next; 00414 } 00415 } 00416 00417 template<typename _Tp, typename _Alloc> 00418 template <typename _BinaryPredicate> 00419 void 00420 list<_Tp, _Alloc>:: 00421 unique(_BinaryPredicate __binary_pred) 00422 { 00423 iterator __first = begin(); 00424 iterator __last = end(); 00425 if (__first == __last) 00426 return; 00427 iterator __next = __first; 00428 while (++__next != __last) 00429 { 00430 if (__binary_pred(*__first, *__next)) 00431 _M_erase(__next); 00432 else 00433 __first = __next; 00434 __next = __first; 00435 } 00436 } 00437 00438 template<typename _Tp, typename _Alloc> 00439 template <typename _StrictWeakOrdering> 00440 void 00441 list<_Tp, _Alloc>:: 00442 sort(_StrictWeakOrdering __comp) 00443 { 00444 // Do nothing if the list has length 0 or 1. 00445 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00446 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00447 { 00448 list __carry; 00449 list __tmp[64]; 00450 list * __fill = &__tmp[0]; 00451 list * __counter; 00452 00453 do 00454 { 00455 __carry.splice(__carry.begin(), *this, begin()); 00456 00457 for(__counter = &__tmp[0]; 00458 __counter != __fill && !__counter->empty(); 00459 ++__counter) 00460 { 00461 __counter->merge(__carry, __comp); 00462 __carry.swap(*__counter); 00463 } 00464 __carry.swap(*__counter); 00465 if (__counter == __fill) 00466 ++__fill; 00467 } 00468 while ( !empty() ); 00469 00470 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00471 __counter->merge(*(__counter - 1), __comp); 00472 swap(*(__fill - 1)); 00473 } 00474 } 00475 00476 _GLIBCXX_END_NAMESPACE_CONTAINER 00477 } // namespace std 00478 00479 #endif /* _LIST_TCC */ 00480