libstdc++
|
00001 // List implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // 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 list.tcc 00053 * This is an internal header file, included by other library headers. 00054 * You should not attempt to use it directly. 00055 */ 00056 00057 #ifndef _LIST_TCC 00058 #define _LIST_TCC 1 00059 00060 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 00061 00062 template<typename _Tp, typename _Alloc> 00063 void 00064 _List_base<_Tp, _Alloc>:: 00065 _M_clear() 00066 { 00067 typedef _List_node<_Tp> _Node; 00068 _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next); 00069 while (__cur != &this->_M_impl._M_node) 00070 { 00071 _Node* __tmp = __cur; 00072 __cur = static_cast<_Node*>(__cur->_M_next); 00073 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00074 _M_get_Node_allocator().destroy(__tmp); 00075 #else 00076 _M_get_Tp_allocator().destroy(&__tmp->_M_data); 00077 #endif 00078 _M_put_node(__tmp); 00079 } 00080 } 00081 00082 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00083 template<typename _Tp, typename _Alloc> 00084 template<typename... _Args> 00085 typename list<_Tp, _Alloc>::iterator 00086 list<_Tp, _Alloc>:: 00087 emplace(iterator __position, _Args&&... __args) 00088 { 00089 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 00090 __tmp->hook(__position._M_node); 00091 return iterator(__tmp); 00092 } 00093 #endif 00094 00095 template<typename _Tp, typename _Alloc> 00096 typename list<_Tp, _Alloc>::iterator 00097 list<_Tp, _Alloc>:: 00098 insert(iterator __position, const value_type& __x) 00099 { 00100 _Node* __tmp = _M_create_node(__x); 00101 __tmp->hook(__position._M_node); 00102 return iterator(__tmp); 00103 } 00104 00105 template<typename _Tp, typename _Alloc> 00106 typename list<_Tp, _Alloc>::iterator 00107 list<_Tp, _Alloc>:: 00108 erase(iterator __position) 00109 { 00110 iterator __ret = iterator(__position._M_node->_M_next); 00111 _M_erase(__position); 00112 return __ret; 00113 } 00114 00115 template<typename _Tp, typename _Alloc> 00116 void 00117 list<_Tp, _Alloc>:: 00118 resize(size_type __new_size, value_type __x) 00119 { 00120 iterator __i = begin(); 00121 size_type __len = 0; 00122 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00123 ; 00124 if (__len == __new_size) 00125 erase(__i, end()); 00126 else // __i == end() 00127 insert(end(), __new_size - __len, __x); 00128 } 00129 00130 template<typename _Tp, typename _Alloc> 00131 list<_Tp, _Alloc>& 00132 list<_Tp, _Alloc>:: 00133 operator=(const list& __x) 00134 { 00135 if (this != &__x) 00136 { 00137 iterator __first1 = begin(); 00138 iterator __last1 = end(); 00139 const_iterator __first2 = __x.begin(); 00140 const_iterator __last2 = __x.end(); 00141 for (; __first1 != __last1 && __first2 != __last2; 00142 ++__first1, ++__first2) 00143 *__first1 = *__first2; 00144 if (__first2 == __last2) 00145 erase(__first1, __last1); 00146 else 00147 insert(__last1, __first2, __last2); 00148 } 00149 return *this; 00150 } 00151 00152 template<typename _Tp, typename _Alloc> 00153 void 00154 list<_Tp, _Alloc>:: 00155 _M_fill_assign(size_type __n, const value_type& __val) 00156 { 00157 iterator __i = begin(); 00158 for (; __i != end() && __n > 0; ++__i, --__n) 00159 *__i = __val; 00160 if (__n > 0) 00161 insert(end(), __n, __val); 00162 else 00163 erase(__i, end()); 00164 } 00165 00166 template<typename _Tp, typename _Alloc> 00167 template <typename _InputIterator> 00168 void 00169 list<_Tp, _Alloc>:: 00170 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 00171 __false_type) 00172 { 00173 iterator __first1 = begin(); 00174 iterator __last1 = end(); 00175 for (; __first1 != __last1 && __first2 != __last2; 00176 ++__first1, ++__first2) 00177 *__first1 = *__first2; 00178 if (__first2 == __last2) 00179 erase(__first1, __last1); 00180 else 00181 insert(__last1, __first2, __last2); 00182 } 00183 00184 template<typename _Tp, typename _Alloc> 00185 void 00186 list<_Tp, _Alloc>:: 00187 remove(const value_type& __value) 00188 { 00189 iterator __first = begin(); 00190 iterator __last = end(); 00191 iterator __extra = __last; 00192 while (__first != __last) 00193 { 00194 iterator __next = __first; 00195 ++__next; 00196 if (*__first == __value) 00197 { 00198 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00199 // 526. Is it undefined if a function in the standard changes 00200 // in parameters? 00201 if (&*__first != &__value) 00202 _M_erase(__first); 00203 else 00204 __extra = __first; 00205 } 00206 __first = __next; 00207 } 00208 if (__extra != __last) 00209 _M_erase(__extra); 00210 } 00211 00212 template<typename _Tp, typename _Alloc> 00213 void 00214 list<_Tp, _Alloc>:: 00215 unique() 00216 { 00217 iterator __first = begin(); 00218 iterator __last = end(); 00219 if (__first == __last) 00220 return; 00221 iterator __next = __first; 00222 while (++__next != __last) 00223 { 00224 if (*__first == *__next) 00225 _M_erase(__next); 00226 else 00227 __first = __next; 00228 __next = __first; 00229 } 00230 } 00231 00232 template<typename _Tp, typename _Alloc> 00233 void 00234 list<_Tp, _Alloc>:: 00235 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00236 merge(list&& __x) 00237 #else 00238 merge(list& __x) 00239 #endif 00240 { 00241 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00242 // 300. list::merge() specification incomplete 00243 if (this != &__x) 00244 { 00245 _M_check_equal_allocators(__x); 00246 00247 iterator __first1 = begin(); 00248 iterator __last1 = end(); 00249 iterator __first2 = __x.begin(); 00250 iterator __last2 = __x.end(); 00251 while (__first1 != __last1 && __first2 != __last2) 00252 if (*__first2 < *__first1) 00253 { 00254 iterator __next = __first2; 00255 _M_transfer(__first1, __first2, ++__next); 00256 __first2 = __next; 00257 } 00258 else 00259 ++__first1; 00260 if (__first2 != __last2) 00261 _M_transfer(__last1, __first2, __last2); 00262 } 00263 } 00264 00265 template<typename _Tp, typename _Alloc> 00266 template <typename _StrictWeakOrdering> 00267 void 00268 list<_Tp, _Alloc>:: 00269 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00270 merge(list&& __x, _StrictWeakOrdering __comp) 00271 #else 00272 merge(list& __x, _StrictWeakOrdering __comp) 00273 #endif 00274 { 00275 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00276 // 300. list::merge() specification incomplete 00277 if (this != &__x) 00278 { 00279 _M_check_equal_allocators(__x); 00280 00281 iterator __first1 = begin(); 00282 iterator __last1 = end(); 00283 iterator __first2 = __x.begin(); 00284 iterator __last2 = __x.end(); 00285 while (__first1 != __last1 && __first2 != __last2) 00286 if (__comp(*__first2, *__first1)) 00287 { 00288 iterator __next = __first2; 00289 _M_transfer(__first1, __first2, ++__next); 00290 __first2 = __next; 00291 } 00292 else 00293 ++__first1; 00294 if (__first2 != __last2) 00295 _M_transfer(__last1, __first2, __last2); 00296 } 00297 } 00298 00299 template<typename _Tp, typename _Alloc> 00300 void 00301 list<_Tp, _Alloc>:: 00302 sort() 00303 { 00304 // Do nothing if the list has length 0 or 1. 00305 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00306 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00307 { 00308 list __carry; 00309 list __tmp[64]; 00310 list * __fill = &__tmp[0]; 00311 list * __counter; 00312 00313 do 00314 { 00315 __carry.splice(__carry.begin(), *this, begin()); 00316 00317 for(__counter = &__tmp[0]; 00318 __counter != __fill && !__counter->empty(); 00319 ++__counter) 00320 { 00321 __counter->merge(__carry); 00322 __carry.swap(*__counter); 00323 } 00324 __carry.swap(*__counter); 00325 if (__counter == __fill) 00326 ++__fill; 00327 } 00328 while ( !empty() ); 00329 00330 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00331 __counter->merge(*(__counter - 1)); 00332 swap( *(__fill - 1) ); 00333 } 00334 } 00335 00336 template<typename _Tp, typename _Alloc> 00337 template <typename _Predicate> 00338 void 00339 list<_Tp, _Alloc>:: 00340 remove_if(_Predicate __pred) 00341 { 00342 iterator __first = begin(); 00343 iterator __last = end(); 00344 while (__first != __last) 00345 { 00346 iterator __next = __first; 00347 ++__next; 00348 if (__pred(*__first)) 00349 _M_erase(__first); 00350 __first = __next; 00351 } 00352 } 00353 00354 template<typename _Tp, typename _Alloc> 00355 template <typename _BinaryPredicate> 00356 void 00357 list<_Tp, _Alloc>:: 00358 unique(_BinaryPredicate __binary_pred) 00359 { 00360 iterator __first = begin(); 00361 iterator __last = end(); 00362 if (__first == __last) 00363 return; 00364 iterator __next = __first; 00365 while (++__next != __last) 00366 { 00367 if (__binary_pred(*__first, *__next)) 00368 _M_erase(__next); 00369 else 00370 __first = __next; 00371 __next = __first; 00372 } 00373 } 00374 00375 template<typename _Tp, typename _Alloc> 00376 template <typename _StrictWeakOrdering> 00377 void 00378 list<_Tp, _Alloc>:: 00379 sort(_StrictWeakOrdering __comp) 00380 { 00381 // Do nothing if the list has length 0 or 1. 00382 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00383 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00384 { 00385 list __carry; 00386 list __tmp[64]; 00387 list * __fill = &__tmp[0]; 00388 list * __counter; 00389 00390 do 00391 { 00392 __carry.splice(__carry.begin(), *this, begin()); 00393 00394 for(__counter = &__tmp[0]; 00395 __counter != __fill && !__counter->empty(); 00396 ++__counter) 00397 { 00398 __counter->merge(__carry, __comp); 00399 __carry.swap(*__counter); 00400 } 00401 __carry.swap(*__counter); 00402 if (__counter == __fill) 00403 ++__fill; 00404 } 00405 while ( !empty() ); 00406 00407 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00408 __counter->merge(*(__counter - 1), __comp); 00409 swap(*(__fill - 1)); 00410 } 00411 } 00412 00413 _GLIBCXX_END_NESTED_NAMESPACE 00414 00415 #endif /* _LIST_TCC */ 00416