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 #ifndef _FORWARD_LIST_TCC
00031 #define _FORWARD_LIST_TCC 1
00032
00033 namespace std _GLIBCXX_VISIBILITY(default)
00034 {
00035 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00036
00037 template<typename _Tp, typename _Alloc>
00038 _Fwd_list_base<_Tp, _Alloc>::
00039 _Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a)
00040 : _M_impl(__a)
00041 {
00042 this->_M_impl._M_head._M_next = 0;
00043 _Fwd_list_node_base* __to = &this->_M_impl._M_head;
00044 _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
00045
00046 while (__curr)
00047 {
00048 __to->_M_next = _M_create_node(__curr->_M_value);
00049 __to = __to->_M_next;
00050 __curr = static_cast<_Node*>(__curr->_M_next);
00051 }
00052 }
00053
00054 template<typename _Tp, typename _Alloc>
00055 template<typename... _Args>
00056 _Fwd_list_node_base*
00057 _Fwd_list_base<_Tp, _Alloc>::
00058 _M_insert_after(const_iterator __pos, _Args&&... __args)
00059 {
00060 _Fwd_list_node_base* __to
00061 = const_cast<_Fwd_list_node_base*>(__pos._M_node);
00062 _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
00063 __thing->_M_next = __to->_M_next;
00064 __to->_M_next = __thing;
00065 return __to->_M_next;
00066 }
00067
00068 template<typename _Tp, typename _Alloc>
00069 _Fwd_list_node_base*
00070 _Fwd_list_base<_Tp, _Alloc>::
00071 _M_erase_after(_Fwd_list_node_base* __pos)
00072 {
00073 _Node* __curr = static_cast<_Node*>(__pos->_M_next);
00074 __pos->_M_next = __curr->_M_next;
00075 _M_get_Node_allocator().destroy(__curr);
00076 _M_put_node(__curr);
00077 return __pos->_M_next;
00078 }
00079
00080 template<typename _Tp, typename _Alloc>
00081 _Fwd_list_node_base*
00082 _Fwd_list_base<_Tp, _Alloc>::
00083 _M_erase_after(_Fwd_list_node_base* __pos,
00084 _Fwd_list_node_base* __last)
00085 {
00086 _Node* __curr = static_cast<_Node*>(__pos->_M_next);
00087 while (__curr != __last)
00088 {
00089 _Node* __temp = __curr;
00090 __curr = static_cast<_Node*>(__curr->_M_next);
00091 _M_get_Node_allocator().destroy(__temp);
00092 _M_put_node(__temp);
00093 }
00094 __pos->_M_next = __last;
00095 return __last;
00096 }
00097
00098
00099 template<typename _Tp, typename _Alloc>
00100 template<typename _InputIterator>
00101 void
00102 forward_list<_Tp, _Alloc>::
00103 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00104 __false_type)
00105 {
00106 _Node_base* __to = &this->_M_impl._M_head;
00107 for (; __first != __last; ++__first)
00108 {
00109 __to->_M_next = this->_M_create_node(*__first);
00110 __to = __to->_M_next;
00111 }
00112 }
00113
00114
00115
00116 template<typename _Tp, typename _Alloc>
00117 void
00118 forward_list<_Tp, _Alloc>::
00119 _M_fill_initialize(size_type __n, const value_type& __value)
00120 {
00121 _Node_base* __to = &this->_M_impl._M_head;
00122 for (; __n; --__n)
00123 {
00124 __to->_M_next = this->_M_create_node(__value);
00125 __to = __to->_M_next;
00126 }
00127 }
00128
00129 template<typename _Tp, typename _Alloc>
00130 void
00131 forward_list<_Tp, _Alloc>::
00132 _M_default_initialize(size_type __n)
00133 {
00134 _Node_base* __to = &this->_M_impl._M_head;
00135 for (; __n; --__n)
00136 {
00137 __to->_M_next = this->_M_create_node();
00138 __to = __to->_M_next;
00139 }
00140 }
00141
00142 template<typename _Tp, typename _Alloc>
00143 forward_list<_Tp, _Alloc>&
00144 forward_list<_Tp, _Alloc>::
00145 operator=(const forward_list& __list)
00146 {
00147 if (&__list != this)
00148 {
00149 iterator __prev1 = before_begin();
00150 iterator __curr1 = begin();
00151 iterator __last1 = end();
00152 const_iterator __first2 = __list.cbegin();
00153 const_iterator __last2 = __list.cend();
00154 while (__curr1 != __last1 && __first2 != __last2)
00155 {
00156 *__curr1 = *__first2;
00157 ++__prev1;
00158 ++__curr1;
00159 ++__first2;
00160 }
00161 if (__first2 == __last2)
00162 erase_after(__prev1, __last1);
00163 else
00164 insert_after(__prev1, __first2, __last2);
00165 }
00166 return *this;
00167 }
00168
00169 template<typename _Tp, typename _Alloc>
00170 void
00171 forward_list<_Tp, _Alloc>::
00172 _M_default_insert_after(const_iterator __pos, size_type __n)
00173 {
00174 const_iterator __saved_pos = __pos;
00175 __try
00176 {
00177 for (; __n; --__n)
00178 __pos = emplace_after(__pos);
00179 }
00180 __catch(...)
00181 {
00182 erase_after(__saved_pos, ++__pos);
00183 __throw_exception_again;
00184 }
00185 }
00186
00187 template<typename _Tp, typename _Alloc>
00188 void
00189 forward_list<_Tp, _Alloc>::
00190 resize(size_type __sz)
00191 {
00192 iterator __k = before_begin();
00193
00194 size_type __len = 0;
00195 while (__k._M_next() != end() && __len < __sz)
00196 {
00197 ++__k;
00198 ++__len;
00199 }
00200 if (__len == __sz)
00201 erase_after(__k, end());
00202 else
00203 _M_default_insert_after(__k, __sz - __len);
00204 }
00205
00206 template<typename _Tp, typename _Alloc>
00207 void
00208 forward_list<_Tp, _Alloc>::
00209 resize(size_type __sz, const value_type& __val)
00210 {
00211 iterator __k = before_begin();
00212
00213 size_type __len = 0;
00214 while (__k._M_next() != end() && __len < __sz)
00215 {
00216 ++__k;
00217 ++__len;
00218 }
00219 if (__len == __sz)
00220 erase_after(__k, end());
00221 else
00222 insert_after(__k, __sz - __len, __val);
00223 }
00224
00225 template<typename _Tp, typename _Alloc>
00226 typename forward_list<_Tp, _Alloc>::iterator
00227 forward_list<_Tp, _Alloc>::
00228 _M_splice_after(const_iterator __pos, forward_list&& __list)
00229 {
00230 _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
00231 iterator __before = __list.before_begin();
00232 return iterator(__tmp->_M_transfer_after(__before._M_node));
00233 }
00234
00235 template<typename _Tp, typename _Alloc>
00236 void
00237 forward_list<_Tp, _Alloc>::
00238 splice_after(const_iterator __pos, forward_list&&,
00239 const_iterator __before, const_iterator __last)
00240 {
00241 _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
00242 __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),
00243 const_cast<_Node_base*>(__last._M_node));
00244 }
00245
00246 template<typename _Tp, typename _Alloc>
00247 typename forward_list<_Tp, _Alloc>::iterator
00248 forward_list<_Tp, _Alloc>::
00249 insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
00250 {
00251 if (__n)
00252 {
00253 forward_list __tmp(__n, __val, this->_M_get_Node_allocator());
00254 return _M_splice_after(__pos, std::move(__tmp));
00255 }
00256 else
00257 return iterator(const_cast<_Node_base*>(__pos._M_node));
00258 }
00259
00260 template<typename _Tp, typename _Alloc>
00261 template<typename _InputIterator>
00262 typename forward_list<_Tp, _Alloc>::iterator
00263 forward_list<_Tp, _Alloc>::
00264 insert_after(const_iterator __pos,
00265 _InputIterator __first, _InputIterator __last)
00266 {
00267 forward_list __tmp(__first, __last, this->_M_get_Node_allocator());
00268 if (!__tmp.empty())
00269 return _M_splice_after(__pos, std::move(__tmp));
00270 else
00271 return iterator(const_cast<_Node_base*>(__pos._M_node));
00272 }
00273
00274 template<typename _Tp, typename _Alloc>
00275 typename forward_list<_Tp, _Alloc>::iterator
00276 forward_list<_Tp, _Alloc>::
00277 insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
00278 {
00279 if (__il.size())
00280 {
00281 forward_list __tmp(__il, this->_M_get_Node_allocator());
00282 return _M_splice_after(__pos, std::move(__tmp));
00283 }
00284 else
00285 return iterator(const_cast<_Node_base*>(__pos._M_node));
00286 }
00287
00288 template<typename _Tp, typename _Alloc>
00289 void
00290 forward_list<_Tp, _Alloc>::
00291 remove(const _Tp& __val)
00292 {
00293 _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
00294 _Node* __extra = 0;
00295
00296 while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
00297 {
00298 if (__tmp->_M_value == __val)
00299 {
00300 if (std::__addressof(__tmp->_M_value)
00301 != std::__addressof(__val))
00302 {
00303 this->_M_erase_after(__curr);
00304 continue;
00305 }
00306 else
00307 __extra = __curr;
00308 }
00309 __curr = static_cast<_Node*>(__curr->_M_next);
00310 }
00311
00312 if (__extra)
00313 this->_M_erase_after(__extra);
00314 }
00315
00316 template<typename _Tp, typename _Alloc>
00317 template<typename _Pred>
00318 void
00319 forward_list<_Tp, _Alloc>::
00320 remove_if(_Pred __pred)
00321 {
00322 _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
00323 while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
00324 {
00325 if (__pred(__tmp->_M_value))
00326 this->_M_erase_after(__curr);
00327 else
00328 __curr = static_cast<_Node*>(__curr->_M_next);
00329 }
00330 }
00331
00332 template<typename _Tp, typename _Alloc>
00333 template<typename _BinPred>
00334 void
00335 forward_list<_Tp, _Alloc>::
00336 unique(_BinPred __binary_pred)
00337 {
00338 iterator __first = begin();
00339 iterator __last = end();
00340 if (__first == __last)
00341 return;
00342 iterator __next = __first;
00343 while (++__next != __last)
00344 {
00345 if (__binary_pred(*__first, *__next))
00346 erase_after(__first);
00347 else
00348 __first = __next;
00349 __next = __first;
00350 }
00351 }
00352
00353 template<typename _Tp, typename _Alloc>
00354 template<typename _Comp>
00355 void
00356 forward_list<_Tp, _Alloc>::
00357 merge(forward_list&& __list, _Comp __comp)
00358 {
00359 _Node_base* __node = &this->_M_impl._M_head;
00360 while (__node->_M_next && __list._M_impl._M_head._M_next)
00361 {
00362 if (__comp(static_cast<_Node*>
00363 (__list._M_impl._M_head._M_next)->_M_value,
00364 static_cast<_Node*>
00365 (__node->_M_next)->_M_value))
00366 __node->_M_transfer_after(&__list._M_impl._M_head,
00367 __list._M_impl._M_head._M_next);
00368 __node = __node->_M_next;
00369 }
00370 if (__list._M_impl._M_head._M_next)
00371 {
00372 __node->_M_next = __list._M_impl._M_head._M_next;
00373 __list._M_impl._M_head._M_next = 0;
00374 }
00375 }
00376
00377 template<typename _Tp, typename _Alloc>
00378 bool
00379 operator==(const forward_list<_Tp, _Alloc>& __lx,
00380 const forward_list<_Tp, _Alloc>& __ly)
00381 {
00382
00383
00384 auto __ix = __lx.cbegin();
00385 auto __iy = __ly.cbegin();
00386 while (__ix != __lx.cend() && __iy != __ly.cend())
00387 {
00388 if (*__ix != *__iy)
00389 return false;
00390 ++__ix;
00391 ++__iy;
00392 }
00393 if (__ix == __lx.cend() && __iy == __ly.cend())
00394 return true;
00395 else
00396 return false;
00397 }
00398
00399 template<typename _Tp, class _Alloc>
00400 template<typename _Comp>
00401 void
00402 forward_list<_Tp, _Alloc>::
00403 sort(_Comp __comp)
00404 {
00405
00406 _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
00407 if (!__list)
00408 return;
00409
00410 unsigned long __insize = 1;
00411
00412 while (1)
00413 {
00414 _Node* __p = __list;
00415 __list = 0;
00416 _Node* __tail = 0;
00417
00418
00419 unsigned long __nmerges = 0;
00420
00421 while (__p)
00422 {
00423 ++__nmerges;
00424
00425
00426 _Node* __q = __p;
00427 unsigned long __psize = 0;
00428 for (unsigned long __i = 0; __i < __insize; ++__i)
00429 {
00430 ++__psize;
00431 __q = static_cast<_Node*>(__q->_M_next);
00432 if (!__q)
00433 break;
00434 }
00435
00436
00437 unsigned long __qsize = __insize;
00438
00439
00440 while (__psize > 0 || (__qsize > 0 && __q))
00441 {
00442
00443 _Node* __e;
00444 if (__psize == 0)
00445 {
00446
00447 __e = __q;
00448 __q = static_cast<_Node*>(__q->_M_next);
00449 --__qsize;
00450 }
00451 else if (__qsize == 0 || !__q)
00452 {
00453
00454 __e = __p;
00455 __p = static_cast<_Node*>(__p->_M_next);
00456 --__psize;
00457 }
00458 else if (__comp(__p->_M_value, __q->_M_value))
00459 {
00460
00461 __e = __p;
00462 __p = static_cast<_Node*>(__p->_M_next);
00463 --__psize;
00464 }
00465 else
00466 {
00467
00468 __e = __q;
00469 __q = static_cast<_Node*>(__q->_M_next);
00470 --__qsize;
00471 }
00472
00473
00474 if (__tail)
00475 __tail->_M_next = __e;
00476 else
00477 __list = __e;
00478 __tail = __e;
00479 }
00480
00481
00482 __p = __q;
00483 }
00484 __tail->_M_next = 0;
00485
00486
00487
00488 if (__nmerges <= 1)
00489 {
00490 this->_M_impl._M_head._M_next = __list;
00491 return;
00492 }
00493
00494
00495 __insize *= 2;
00496 }
00497 }
00498
00499 _GLIBCXX_END_NAMESPACE_CONTAINER
00500 }
00501
00502 #endif
00503