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