list.tcc

Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996,1997 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00056 /** @file list.tcc 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 00061 #ifndef _LIST_TCC 00062 #define _LIST_TCC 1 00063 00064 namespace _GLIBCXX_STD 00065 { 00066 template<typename _Tp, typename _Alloc> 00067 void 00068 _List_base<_Tp,_Alloc>:: 00069 _M_clear() 00070 { 00071 typedef _List_node<_Tp> _Node; 00072 _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next); 00073 while (__cur != &this->_M_impl._M_node) 00074 { 00075 _Node* __tmp = __cur; 00076 __cur = static_cast<_Node*>(__cur->_M_next); 00077 std::_Destroy(&__tmp->_M_data); 00078 _M_put_node(__tmp); 00079 } 00080 } 00081 00082 template<typename _Tp, typename _Alloc> 00083 typename list<_Tp,_Alloc>::iterator 00084 list<_Tp,_Alloc>:: 00085 insert(iterator __position, const value_type& __x) 00086 { 00087 _Node* __tmp = _M_create_node(__x); 00088 __tmp->hook(__position._M_node); 00089 return __tmp; 00090 } 00091 00092 template<typename _Tp, typename _Alloc> 00093 typename list<_Tp,_Alloc>::iterator 00094 list<_Tp,_Alloc>:: 00095 erase(iterator __position) 00096 { 00097 iterator __ret = __position._M_node->_M_next; 00098 _M_erase(__position); 00099 return __ret; 00100 } 00101 00102 template<typename _Tp, typename _Alloc> 00103 void 00104 list<_Tp,_Alloc>:: 00105 resize(size_type __new_size, const value_type& __x) 00106 { 00107 iterator __i = begin(); 00108 size_type __len = 0; 00109 for ( ; __i != end() && __len < __new_size; ++__i, ++__len) 00110 ; 00111 if (__len == __new_size) 00112 erase(__i, end()); 00113 else // __i == end() 00114 insert(end(), __new_size - __len, __x); 00115 } 00116 00117 template<typename _Tp, typename _Alloc> 00118 list<_Tp,_Alloc>& 00119 list<_Tp,_Alloc>:: 00120 operator=(const list& __x) 00121 { 00122 if (this != &__x) 00123 { 00124 iterator __first1 = begin(); 00125 iterator __last1 = end(); 00126 const_iterator __first2 = __x.begin(); 00127 const_iterator __last2 = __x.end(); 00128 while (__first1 != __last1 && __first2 != __last2) 00129 *__first1++ = *__first2++; 00130 if (__first2 == __last2) 00131 erase(__first1, __last1); 00132 else 00133 insert(__last1, __first2, __last2); 00134 } 00135 return *this; 00136 } 00137 00138 template<typename _Tp, typename _Alloc> 00139 void 00140 list<_Tp,_Alloc>:: 00141 _M_fill_assign(size_type __n, const value_type& __val) 00142 { 00143 iterator __i = begin(); 00144 for ( ; __i != end() && __n > 0; ++__i, --__n) 00145 *__i = __val; 00146 if (__n > 0) 00147 insert(end(), __n, __val); 00148 else 00149 erase(__i, end()); 00150 } 00151 00152 template<typename _Tp, typename _Alloc> 00153 template <typename _InputIterator> 00154 void 00155 list<_Tp,_Alloc>:: 00156 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 00157 __false_type) 00158 { 00159 iterator __first1 = begin(); 00160 iterator __last1 = end(); 00161 for (; __first1 != __last1 && __first2 != __last2; 00162 ++__first1, ++__first2) 00163 *__first1 = *__first2; 00164 if (__first2 == __last2) 00165 erase(__first1, __last1); 00166 else 00167 insert(__last1, __first2, __last2); 00168 } 00169 00170 template<typename _Tp, typename _Alloc> 00171 void 00172 list<_Tp,_Alloc>:: 00173 remove(const value_type& __value) 00174 { 00175 iterator __first = begin(); 00176 iterator __last = end(); 00177 while (__first != __last) 00178 { 00179 iterator __next = __first; 00180 ++__next; 00181 if (*__first == __value) 00182 _M_erase(__first); 00183 __first = __next; 00184 } 00185 } 00186 00187 template<typename _Tp, typename _Alloc> 00188 void 00189 list<_Tp,_Alloc>:: 00190 unique() 00191 { 00192 iterator __first = begin(); 00193 iterator __last = end(); 00194 if (__first == __last) 00195 return; 00196 iterator __next = __first; 00197 while (++__next != __last) 00198 { 00199 if (*__first == *__next) 00200 _M_erase(__next); 00201 else 00202 __first = __next; 00203 __next = __first; 00204 } 00205 } 00206 00207 template<typename _Tp, typename _Alloc> 00208 void 00209 list<_Tp,_Alloc>:: 00210 merge(list& __x) 00211 { 00212 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00213 // 300. list::merge() specification incomplete 00214 if (this != &__x) 00215 { 00216 iterator __first1 = begin(); 00217 iterator __last1 = end(); 00218 iterator __first2 = __x.begin(); 00219 iterator __last2 = __x.end(); 00220 while (__first1 != __last1 && __first2 != __last2) 00221 if (*__first2 < *__first1) 00222 { 00223 iterator __next = __first2; 00224 _M_transfer(__first1, __first2, ++__next); 00225 __first2 = __next; 00226 } 00227 else 00228 ++__first1; 00229 if (__first2 != __last2) 00230 _M_transfer(__last1, __first2, __last2); 00231 } 00232 } 00233 00234 template<typename _Tp, typename _Alloc> 00235 void 00236 list<_Tp,_Alloc>:: 00237 sort() 00238 { 00239 // Do nothing if the list has length 0 or 1. 00240 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00241 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00242 { 00243 list __carry; 00244 list __tmp[64]; 00245 list * __fill = &__tmp[0]; 00246 list * __counter; 00247 00248 do 00249 { 00250 __carry.splice(__carry.begin(), *this, begin()); 00251 00252 for(__counter = &__tmp[0]; 00253 (__counter != __fill) && !__counter->empty(); 00254 ++__counter) 00255 { 00256 __counter->merge(__carry); 00257 __carry.swap(*__counter); 00258 } 00259 __carry.swap(*__counter); 00260 if (__counter == __fill) 00261 ++__fill; 00262 } 00263 while ( !empty() ); 00264 00265 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00266 __counter->merge( *(__counter-1) ); 00267 swap( *(__fill-1) ); 00268 } 00269 } 00270 00271 template<typename _Tp, typename _Alloc> 00272 template <typename _Predicate> 00273 void 00274 list<_Tp,_Alloc>:: 00275 remove_if(_Predicate __pred) 00276 { 00277 iterator __first = begin(); 00278 iterator __last = end(); 00279 while (__first != __last) 00280 { 00281 iterator __next = __first; 00282 ++__next; 00283 if (__pred(*__first)) 00284 _M_erase(__first); 00285 __first = __next; 00286 } 00287 } 00288 00289 template<typename _Tp, typename _Alloc> 00290 template <typename _BinaryPredicate> 00291 void 00292 list<_Tp,_Alloc>:: 00293 unique(_BinaryPredicate __binary_pred) 00294 { 00295 iterator __first = begin(); 00296 iterator __last = end(); 00297 if (__first == __last) return; 00298 iterator __next = __first; 00299 while (++__next != __last) 00300 { 00301 if (__binary_pred(*__first, *__next)) 00302 _M_erase(__next); 00303 else 00304 __first = __next; 00305 __next = __first; 00306 } 00307 } 00308 00309 template<typename _Tp, typename _Alloc> 00310 template <typename _StrictWeakOrdering> 00311 void 00312 list<_Tp,_Alloc>:: 00313 merge(list& __x, _StrictWeakOrdering __comp) 00314 { 00315 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00316 // 300. list::merge() specification incomplete 00317 if (this != &__x) 00318 { 00319 iterator __first1 = begin(); 00320 iterator __last1 = end(); 00321 iterator __first2 = __x.begin(); 00322 iterator __last2 = __x.end(); 00323 while (__first1 != __last1 && __first2 != __last2) 00324 if (__comp(*__first2, *__first1)) 00325 { 00326 iterator __next = __first2; 00327 _M_transfer(__first1, __first2, ++__next); 00328 __first2 = __next; 00329 } 00330 else 00331 ++__first1; 00332 if (__first2 != __last2) 00333 _M_transfer(__last1, __first2, __last2); 00334 } 00335 } 00336 00337 template<typename _Tp, typename _Alloc> 00338 template <typename _StrictWeakOrdering> 00339 void 00340 list<_Tp,_Alloc>:: 00341 sort(_StrictWeakOrdering __comp) 00342 { 00343 // Do nothing if the list has length 0 or 1. 00344 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00345 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00346 { 00347 list __carry; 00348 list __tmp[64]; 00349 list * __fill = &__tmp[0]; 00350 list * __counter; 00351 00352 do 00353 { 00354 __carry.splice(__carry.begin(), *this, begin()); 00355 00356 for(__counter = &__tmp[0]; 00357 (__counter != __fill) && !__counter->empty(); 00358 ++__counter) 00359 { 00360 __counter->merge(__carry, __comp); 00361 __carry.swap(*__counter); 00362 } 00363 __carry.swap(*__counter); 00364 if (__counter == __fill) 00365 ++__fill; 00366 } 00367 while ( !empty() ); 00368 00369 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00370 __counter->merge( *(__counter-1), __comp ); 00371 swap( *(__fill-1) ); 00372 } 00373 } 00374 } // namespace std 00375 00376 #endif /* _LIST_TCC */ 00377

Generated on Tue Sep 7 10:05:08 2004 for libstdc++-v3 Source by doxygen 1.3.8