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
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 _M_get_Tp_allocator().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 iterator(__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 = iterator(__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, 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
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 for (; __first1 != __last1 && __first2 != __last2;
00129 ++__first1, ++__first2)
00130 *__first1 = *__first2;
00131 if (__first2 == __last2)
00132 erase(__first1, __last1);
00133 else
00134 insert(__last1, __first2, __last2);
00135 }
00136 return *this;
00137 }
00138
00139 template<typename _Tp, typename _Alloc>
00140 void
00141 list<_Tp, _Alloc>::
00142 _M_fill_assign(size_type __n, const value_type& __val)
00143 {
00144 iterator __i = begin();
00145 for (; __i != end() && __n > 0; ++__i, --__n)
00146 *__i = __val;
00147 if (__n > 0)
00148 insert(end(), __n, __val);
00149 else
00150 erase(__i, end());
00151 }
00152
00153 template<typename _Tp, typename _Alloc>
00154 template <typename _InputIterator>
00155 void
00156 list<_Tp, _Alloc>::
00157 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
00158 __false_type)
00159 {
00160 iterator __first1 = begin();
00161 iterator __last1 = end();
00162 for (; __first1 != __last1 && __first2 != __last2;
00163 ++__first1, ++__first2)
00164 *__first1 = *__first2;
00165 if (__first2 == __last2)
00166 erase(__first1, __last1);
00167 else
00168 insert(__last1, __first2, __last2);
00169 }
00170
00171 template<typename _Tp, typename _Alloc>
00172 void
00173 list<_Tp, _Alloc>::
00174 remove(const value_type& __value)
00175 {
00176 iterator __first = begin();
00177 iterator __last = end();
00178 while (__first != __last)
00179 {
00180 iterator __next = __first;
00181 ++__next;
00182 if (*__first == __value)
00183 _M_erase(__first);
00184 __first = __next;
00185 }
00186 }
00187
00188 template<typename _Tp, typename _Alloc>
00189 void
00190 list<_Tp, _Alloc>::
00191 unique()
00192 {
00193 iterator __first = begin();
00194 iterator __last = end();
00195 if (__first == __last)
00196 return;
00197 iterator __next = __first;
00198 while (++__next != __last)
00199 {
00200 if (*__first == *__next)
00201 _M_erase(__next);
00202 else
00203 __first = __next;
00204 __next = __first;
00205 }
00206 }
00207
00208 template<typename _Tp, typename _Alloc>
00209 void
00210 list<_Tp, _Alloc>::
00211 merge(list& __x)
00212 {
00213
00214
00215 if (this != &__x)
00216 {
00217 iterator __first1 = begin();
00218 iterator __last1 = end();
00219 iterator __first2 = __x.begin();
00220 iterator __last2 = __x.end();
00221 while (__first1 != __last1 && __first2 != __last2)
00222 if (*__first2 < *__first1)
00223 {
00224 iterator __next = __first2;
00225 _M_transfer(__first1, __first2, ++__next);
00226 __first2 = __next;
00227 }
00228 else
00229 ++__first1;
00230 if (__first2 != __last2)
00231 _M_transfer(__last1, __first2, __last2);
00232 }
00233 }
00234
00235 template<typename _Tp, typename _Alloc>
00236 void
00237 list<_Tp, _Alloc>::
00238 sort()
00239 {
00240
00241 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00242 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00243 {
00244 list __carry;
00245 list __tmp[64];
00246 list * __fill = &__tmp[0];
00247 list * __counter;
00248
00249 do
00250 {
00251 __carry.splice(__carry.begin(), *this, begin());
00252
00253 for(__counter = &__tmp[0];
00254 __counter != __fill && !__counter->empty();
00255 ++__counter)
00256 {
00257 __counter->merge(__carry);
00258 __carry.swap(*__counter);
00259 }
00260 __carry.swap(*__counter);
00261 if (__counter == __fill)
00262 ++__fill;
00263 }
00264 while ( !empty() );
00265
00266 for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00267 __counter->merge(*(__counter - 1));
00268 swap( *(__fill - 1) );
00269 }
00270 }
00271
00272 template<typename _Tp, typename _Alloc>
00273 template <typename _Predicate>
00274 void
00275 list<_Tp, _Alloc>::
00276 remove_if(_Predicate __pred)
00277 {
00278 iterator __first = begin();
00279 iterator __last = end();
00280 while (__first != __last)
00281 {
00282 iterator __next = __first;
00283 ++__next;
00284 if (__pred(*__first))
00285 _M_erase(__first);
00286 __first = __next;
00287 }
00288 }
00289
00290 template<typename _Tp, typename _Alloc>
00291 template <typename _BinaryPredicate>
00292 void
00293 list<_Tp, _Alloc>::
00294 unique(_BinaryPredicate __binary_pred)
00295 {
00296 iterator __first = begin();
00297 iterator __last = end();
00298 if (__first == __last)
00299 return;
00300 iterator __next = __first;
00301 while (++__next != __last)
00302 {
00303 if (__binary_pred(*__first, *__next))
00304 _M_erase(__next);
00305 else
00306 __first = __next;
00307 __next = __first;
00308 }
00309 }
00310
00311 template<typename _Tp, typename _Alloc>
00312 template <typename _StrictWeakOrdering>
00313 void
00314 list<_Tp, _Alloc>::
00315 merge(list& __x, _StrictWeakOrdering __comp)
00316 {
00317
00318
00319 if (this != &__x)
00320 {
00321 iterator __first1 = begin();
00322 iterator __last1 = end();
00323 iterator __first2 = __x.begin();
00324 iterator __last2 = __x.end();
00325 while (__first1 != __last1 && __first2 != __last2)
00326 if (__comp(*__first2, *__first1))
00327 {
00328 iterator __next = __first2;
00329 _M_transfer(__first1, __first2, ++__next);
00330 __first2 = __next;
00331 }
00332 else
00333 ++__first1;
00334 if (__first2 != __last2)
00335 _M_transfer(__last1, __first2, __last2);
00336 }
00337 }
00338
00339 template<typename _Tp, typename _Alloc>
00340 template <typename _StrictWeakOrdering>
00341 void
00342 list<_Tp, _Alloc>::
00343 sort(_StrictWeakOrdering __comp)
00344 {
00345
00346 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00347 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00348 {
00349 list __carry;
00350 list __tmp[64];
00351 list * __fill = &__tmp[0];
00352 list * __counter;
00353
00354 do
00355 {
00356 __carry.splice(__carry.begin(), *this, begin());
00357
00358 for(__counter = &__tmp[0];
00359 __counter != __fill && !__counter->empty();
00360 ++__counter)
00361 {
00362 __counter->merge(__carry, __comp);
00363 __carry.swap(*__counter);
00364 }
00365 __carry.swap(*__counter);
00366 if (__counter == __fill)
00367 ++__fill;
00368 }
00369 while ( !empty() );
00370
00371 for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00372 __counter->merge(*(__counter - 1), __comp);
00373 swap(*(__fill - 1));
00374 }
00375 }
00376 }
00377
00378 #endif
00379