00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
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
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
00220
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
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;
00249 } while (__tmp != __p);
00250 }
00251
00252 template<typename _Tp, typename _Alloc>
00253 void
00254 list<_Tp,_Alloc>::
00255 sort()
00256 {
00257
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
00326
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
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 }
00377
00378 #endif