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