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