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