list.tcc

Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 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 __GLIBCPP_INTERNAL_LIST_TCC 00062 #define __GLIBCPP_INTERNAL_LIST_TCC 00063 00064 namespace std 00065 { 00066 template<typename _Tp, typename _Alloc> 00067 void 00068 _List_base<_Tp,_Alloc>:: 00069 __clear() 00070 { 00071 typedef _List_node<_Tp> _Node; 00072 _Node* __cur = static_cast<_Node*>(_M_node->_M_next); 00073 while (__cur != _M_node) 00074 { 00075 _Node* __tmp = __cur; 00076 __cur = static_cast<_Node*>(__cur->_M_next); 00077 _Destroy(&__tmp->_M_data); 00078 _M_put_node(__tmp); 00079 } 00080 _M_node->_M_next = _M_node; 00081 _M_node->_M_prev = _M_node; 00082 } 00083 00084 template<typename _Tp, typename _Alloc> 00085 typename list<_Tp,_Alloc>::iterator 00086 list<_Tp,_Alloc>:: 00087 insert(iterator __position, const value_type& __x) 00088 { 00089 _Node* __tmp = _M_create_node(__x); 00090 __tmp->_M_next = __position._M_node; 00091 __tmp->_M_prev = __position._M_node->_M_prev; 00092 __position._M_node->_M_prev->_M_next = __tmp; 00093 __position._M_node->_M_prev = __tmp; 00094 return __tmp; 00095 } 00096 00097 template<typename _Tp, typename _Alloc> 00098 typename list<_Tp,_Alloc>::iterator 00099 list<_Tp,_Alloc>:: 00100 erase(iterator __position) 00101 { 00102 _List_node_base* __next_node = __position._M_node->_M_next; 00103 _List_node_base* __prev_node = __position._M_node->_M_prev; 00104 _Node* __n = static_cast<_Node*>(__position._M_node); 00105 __prev_node->_M_next = __next_node; 00106 __next_node->_M_prev = __prev_node; 00107 _Destroy(&__n->_M_data); 00108 _M_put_node(__n); 00109 return iterator(static_cast<_Node*>(__next_node)); 00110 } 00111 00112 template<typename _Tp, typename _Alloc> 00113 void 00114 list<_Tp,_Alloc>:: 00115 resize(size_type __new_size, const value_type& __x) 00116 { 00117 iterator __i = begin(); 00118 size_type __len = 0; 00119 for ( ; __i != end() && __len < __new_size; ++__i, ++__len) 00120 ; 00121 if (__len == __new_size) 00122 erase(__i, end()); 00123 else // __i == end() 00124 insert(end(), __new_size - __len, __x); 00125 } 00126 00127 template<typename _Tp, typename _Alloc> 00128 list<_Tp,_Alloc>& 00129 list<_Tp,_Alloc>:: 00130 operator=(const list& __x) 00131 { 00132 if (this != &__x) 00133 { 00134 iterator __first1 = begin(); 00135 iterator __last1 = end(); 00136 const_iterator __first2 = __x.begin(); 00137 const_iterator __last2 = __x.end(); 00138 while (__first1 != __last1 && __first2 != __last2) 00139 *__first1++ = *__first2++; 00140 if (__first2 == __last2) 00141 erase(__first1, __last1); 00142 else 00143 insert(__last1, __first2, __last2); 00144 } 00145 return *this; 00146 } 00147 00148 template<typename _Tp, typename _Alloc> 00149 void 00150 list<_Tp,_Alloc>:: 00151 _M_fill_assign(size_type __n, const value_type& __val) 00152 { 00153 iterator __i = begin(); 00154 for ( ; __i != end() && __n > 0; ++__i, --__n) 00155 *__i = __val; 00156 if (__n > 0) 00157 insert(end(), __n, __val); 00158 else 00159 erase(__i, end()); 00160 } 00161 00162 template<typename _Tp, typename _Alloc> 00163 template <typename _InputIter> 00164 void 00165 list<_Tp,_Alloc>:: 00166 _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) 00167 { 00168 iterator __first1 = begin(); 00169 iterator __last1 = end(); 00170 for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) 00171 *__first1 = *__first2; 00172 if (__first2 == __last2) 00173 erase(__first1, __last1); 00174 else 00175 insert(__last1, __first2, __last2); 00176 } 00177 00178 template<typename _Tp, typename _Alloc> 00179 void 00180 list<_Tp,_Alloc>:: 00181 remove(const value_type& __value) 00182 { 00183 iterator __first = begin(); 00184 iterator __last = end(); 00185 while (__first != __last) 00186 { 00187 iterator __next = __first; 00188 ++__next; 00189 if (*__first == __value) 00190 erase(__first); 00191 __first = __next; 00192 } 00193 } 00194 00195 template<typename _Tp, typename _Alloc> 00196 void 00197 list<_Tp,_Alloc>:: 00198 unique() 00199 { 00200 iterator __first = begin(); 00201 iterator __last = end(); 00202 if (__first == __last) return; 00203 iterator __next = __first; 00204 while (++__next != __last) 00205 { 00206 if (*__first == *__next) 00207 erase(__next); 00208 else 00209 __first = __next; 00210 __next = __first; 00211 } 00212 } 00213 00214 template<typename _Tp, typename _Alloc> 00215 void 00216 list<_Tp,_Alloc>:: 00217 merge(list& __x) 00218 { 00219 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00220 // 300. list::merge() specification incomplete 00221 if (this != &__x) 00222 { 00223 iterator __first1 = begin(); 00224 iterator __last1 = end(); 00225 iterator __first2 = __x.begin(); 00226 iterator __last2 = __x.end(); 00227 while (__first1 != __last1 && __first2 != __last2) 00228 if (*__first2 < *__first1) 00229 { 00230 iterator __next = __first2; 00231 _M_transfer(__first1, __first2, ++__next); 00232 __first2 = __next; 00233 } 00234 else 00235 ++__first1; 00236 if (__first2 != __last2) 00237 _M_transfer(__last1, __first2, __last2); 00238 } 00239 } 00240 00241 // FIXME put this somewhere else 00242 inline void 00243 __List_base_reverse(_List_node_base* __p) 00244 { 00245 _List_node_base* __tmp = __p; 00246 do { 00247 std::swap(__tmp->_M_next, __tmp->_M_prev); 00248 __tmp = __tmp->_M_prev; // Old next node is now prev. 00249 } while (__tmp != __p); 00250 } 00251 00252 template<typename _Tp, typename _Alloc> 00253 void 00254 list<_Tp,_Alloc>:: 00255 sort() 00256 { 00257 // Do nothing if the list has length 0 or 1. 00258 if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) 00259 { 00260 list __carry; 00261 list __counter[64]; 00262 int __fill = 0; 00263 while (!empty()) 00264 { 00265 __carry.splice(__carry.begin(), *this, begin()); 00266 int __i = 0; 00267 while(__i < __fill && !__counter[__i].empty()) 00268 { 00269 __counter[__i].merge(__carry); 00270 __carry.swap(__counter[__i++]); 00271 } 00272 __carry.swap(__counter[__i]); 00273 if (__i == __fill) ++__fill; 00274 } 00275 00276 for (int __i = 1; __i < __fill; ++__i) 00277 __counter[__i].merge(__counter[__i-1]); 00278 swap(__counter[__fill-1]); 00279 } 00280 } 00281 00282 template<typename _Tp, typename _Alloc> 00283 template <typename _Predicate> 00284 void 00285 list<_Tp,_Alloc>:: 00286 remove_if(_Predicate __pred) 00287 { 00288 iterator __first = begin(); 00289 iterator __last = end(); 00290 while (__first != __last) 00291 { 00292 iterator __next = __first; 00293 ++__next; 00294 if (__pred(*__first)) erase(__first); 00295 __first = __next; 00296 } 00297 } 00298 00299 template<typename _Tp, typename _Alloc> 00300 template <typename _BinaryPredicate> 00301 void 00302 list<_Tp,_Alloc>:: 00303 unique(_BinaryPredicate __binary_pred) 00304 { 00305 iterator __first = begin(); 00306 iterator __last = end(); 00307 if (__first == __last) return; 00308 iterator __next = __first; 00309 while (++__next != __last) 00310 { 00311 if (__binary_pred(*__first, *__next)) 00312 erase(__next); 00313 else 00314 __first = __next; 00315 __next = __first; 00316 } 00317 } 00318 00319 template<typename _Tp, typename _Alloc> 00320 template <typename _StrictWeakOrdering> 00321 void 00322 list<_Tp,_Alloc>:: 00323 merge(list& __x, _StrictWeakOrdering __comp) 00324 { 00325 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00326 // 300. list::merge() specification incomplete 00327 if (this != &__x) 00328 { 00329 iterator __first1 = begin(); 00330 iterator __last1 = end(); 00331 iterator __first2 = __x.begin(); 00332 iterator __last2 = __x.end(); 00333 while (__first1 != __last1 && __first2 != __last2) 00334 if (__comp(*__first2, *__first1)) 00335 { 00336 iterator __next = __first2; 00337 _M_transfer(__first1, __first2, ++__next); 00338 __first2 = __next; 00339 } 00340 else 00341 ++__first1; 00342 if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); 00343 } 00344 } 00345 00346 template<typename _Tp, typename _Alloc> 00347 template <typename _StrictWeakOrdering> 00348 void 00349 list<_Tp,_Alloc>:: 00350 sort(_StrictWeakOrdering __comp) 00351 { 00352 // Do nothing if the list has length 0 or 1. 00353 if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) 00354 { 00355 list __carry; 00356 list __counter[64]; 00357 int __fill = 0; 00358 while (!empty()) 00359 { 00360 __carry.splice(__carry.begin(), *this, begin()); 00361 int __i = 0; 00362 while(__i < __fill && !__counter[__i].empty()) 00363 { 00364 __counter[__i].merge(__carry, __comp); 00365 __carry.swap(__counter[__i++]); 00366 } 00367 __carry.swap(__counter[__i]); 00368 if (__i == __fill) ++__fill; 00369 } 00370 00371 for (int __i = 1; __i < __fill; ++__i) 00372 __counter[__i].merge(__counter[__i-1], __comp); 00373 swap(__counter[__fill-1]); 00374 } 00375 } 00376 } // namespace std 00377 00378 #endif /* __GLIBCPP_INTERNAL_LIST_TCC */

Generated on Wed Aug 4 21:43:13 2004 for libstdc++-v3 Source by doxygen 1.3.8