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