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 _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
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
00213
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
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
00316
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
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 }
00375
00376
#endif
00377