libstdc++
forward_list.tcc
Go to the documentation of this file.
00001 // <forward_list.tcc> -*- C++ -*-
00002 
00003 // Copyright (C) 2008-2018 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/forward_list.tcc
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{forward_list}
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_VERSION
00036 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00037 
00038   template<typename _Tp, typename _Alloc>
00039     _Fwd_list_base<_Tp, _Alloc>::
00040     _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a)
00041     : _M_impl(std::move(__a))
00042     {
00043       if (__lst._M_get_Node_allocator() == _M_get_Node_allocator())
00044         this->_M_impl._M_head = std::move(__lst._M_impl._M_head);
00045     }
00046 
00047   template<typename _Tp, typename _Alloc>
00048     template<typename... _Args>
00049       _Fwd_list_node_base*
00050       _Fwd_list_base<_Tp, _Alloc>::
00051       _M_insert_after(const_iterator __pos, _Args&&... __args)
00052       {
00053         _Fwd_list_node_base* __to
00054           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
00055         _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
00056         __thing->_M_next = __to->_M_next;
00057         __to->_M_next = __thing;
00058         return __to->_M_next;
00059       }
00060 
00061   template<typename _Tp, typename _Alloc>
00062     _Fwd_list_node_base*
00063     _Fwd_list_base<_Tp, _Alloc>::
00064     _M_erase_after(_Fwd_list_node_base* __pos)
00065     {
00066       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
00067       __pos->_M_next = __curr->_M_next;
00068       _Node_alloc_traits::destroy(_M_get_Node_allocator(),
00069                                   __curr->_M_valptr());
00070       __curr->~_Node();
00071       _M_put_node(__curr);
00072       return __pos->_M_next;
00073     }
00074 
00075   template<typename _Tp, typename _Alloc>
00076     _Fwd_list_node_base*
00077     _Fwd_list_base<_Tp, _Alloc>::
00078     _M_erase_after(_Fwd_list_node_base* __pos,
00079                    _Fwd_list_node_base* __last)
00080     {
00081       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
00082       while (__curr != __last)
00083         {
00084           _Node* __temp = __curr;
00085           __curr = static_cast<_Node*>(__curr->_M_next);
00086           _Node_alloc_traits::destroy(_M_get_Node_allocator(),
00087                                       __temp->_M_valptr());
00088           __temp->~_Node();
00089           _M_put_node(__temp);
00090         }
00091       __pos->_M_next = __last;
00092       return __last;
00093     }
00094 
00095   // Called by the range constructor to implement [23.3.4.2]/9
00096   template<typename _Tp, typename _Alloc>
00097     template<typename _InputIterator>
00098       void
00099       forward_list<_Tp, _Alloc>::
00100       _M_range_initialize(_InputIterator __first, _InputIterator __last)
00101       {
00102         _Node_base* __to = &this->_M_impl._M_head;
00103         for (; __first != __last; ++__first)
00104           {
00105             __to->_M_next = this->_M_create_node(*__first);
00106             __to = __to->_M_next;
00107           }
00108       }
00109 
00110   // Called by forward_list(n,v,a).
00111   template<typename _Tp, typename _Alloc>
00112     void
00113     forward_list<_Tp, _Alloc>::
00114     _M_fill_initialize(size_type __n, const value_type& __value)
00115     {
00116       _Node_base* __to = &this->_M_impl._M_head;
00117       for (; __n; --__n)
00118         {
00119           __to->_M_next = this->_M_create_node(__value);
00120           __to = __to->_M_next;
00121         }
00122     }
00123 
00124   template<typename _Tp, typename _Alloc>
00125     void
00126     forward_list<_Tp, _Alloc>::
00127     _M_default_initialize(size_type __n)
00128     {
00129       _Node_base* __to = &this->_M_impl._M_head;
00130       for (; __n; --__n)
00131         {
00132           __to->_M_next = this->_M_create_node();
00133           __to = __to->_M_next;
00134         }
00135     }
00136 
00137   template<typename _Tp, typename _Alloc>
00138     forward_list<_Tp, _Alloc>&
00139     forward_list<_Tp, _Alloc>::
00140     operator=(const forward_list& __list)
00141     {
00142       if (std::__addressof(__list) != this)
00143         {
00144           if (_Node_alloc_traits::_S_propagate_on_copy_assign())
00145             {
00146               auto& __this_alloc = this->_M_get_Node_allocator();
00147               auto& __that_alloc = __list._M_get_Node_allocator();
00148               if (!_Node_alloc_traits::_S_always_equal()
00149                   && __this_alloc != __that_alloc)
00150                 {
00151                   // replacement allocator cannot free existing storage
00152                   clear();
00153                 }
00154               std::__alloc_on_copy(__this_alloc, __that_alloc);
00155             }
00156           assign(__list.cbegin(), __list.cend());
00157         }
00158       return *this;
00159     }
00160 
00161   template<typename _Tp, typename _Alloc>
00162     void
00163     forward_list<_Tp, _Alloc>::
00164     _M_default_insert_after(const_iterator __pos, size_type __n)
00165     {
00166       const_iterator __saved_pos = __pos;
00167       __try
00168         {
00169           for (; __n; --__n)
00170             __pos = emplace_after(__pos);
00171         }
00172       __catch(...)
00173         {
00174           erase_after(__saved_pos, ++__pos);
00175           __throw_exception_again;
00176         }
00177     }
00178 
00179   template<typename _Tp, typename _Alloc>
00180     void
00181     forward_list<_Tp, _Alloc>::
00182     resize(size_type __sz)
00183     {
00184       iterator __k = before_begin();
00185 
00186       size_type __len = 0;
00187       while (__k._M_next() != end() && __len < __sz)
00188         {
00189           ++__k;
00190           ++__len;
00191         }
00192       if (__len == __sz)
00193         erase_after(__k, end());
00194       else
00195         _M_default_insert_after(__k, __sz - __len);
00196     }
00197 
00198   template<typename _Tp, typename _Alloc>
00199     void
00200     forward_list<_Tp, _Alloc>::
00201     resize(size_type __sz, const value_type& __val)
00202     {
00203       iterator __k = before_begin();
00204 
00205       size_type __len = 0;
00206       while (__k._M_next() != end() && __len < __sz)
00207         {
00208           ++__k;
00209           ++__len;
00210         }
00211       if (__len == __sz)
00212         erase_after(__k, end());
00213       else
00214         insert_after(__k, __sz - __len, __val);
00215     }
00216 
00217   template<typename _Tp, typename _Alloc>
00218     typename forward_list<_Tp, _Alloc>::iterator
00219     forward_list<_Tp, _Alloc>::
00220     _M_splice_after(const_iterator __pos,
00221                     const_iterator __before, const_iterator __last)
00222     {
00223       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
00224       _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
00225       _Node_base* __end = __b;
00226 
00227       while (__end && __end->_M_next != __last._M_node)
00228         __end = __end->_M_next;
00229 
00230       if (__b != __end)
00231         return iterator(__tmp->_M_transfer_after(__b, __end));
00232       else
00233         return iterator(__tmp);
00234     }
00235 
00236   template<typename _Tp, typename _Alloc>
00237     void
00238     forward_list<_Tp, _Alloc>::
00239     splice_after(const_iterator __pos, forward_list&&,
00240                  const_iterator __i) noexcept
00241     {
00242       const_iterator __j = __i;
00243       ++__j;
00244 
00245       if (__pos == __i || __pos == __j)
00246         return;
00247 
00248       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
00249       __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
00250                                const_cast<_Node_base*>(__j._M_node));
00251     }
00252 
00253   template<typename _Tp, typename _Alloc>
00254     typename forward_list<_Tp, _Alloc>::iterator
00255     forward_list<_Tp, _Alloc>::
00256     insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
00257     {
00258       if (__n)
00259         {
00260           forward_list __tmp(__n, __val, get_allocator());
00261           return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
00262         }
00263       else
00264         return iterator(const_cast<_Node_base*>(__pos._M_node));
00265     }
00266 
00267   template<typename _Tp, typename _Alloc>
00268     template<typename _InputIterator, typename>
00269       typename forward_list<_Tp, _Alloc>::iterator
00270       forward_list<_Tp, _Alloc>::
00271       insert_after(const_iterator __pos,
00272                    _InputIterator __first, _InputIterator __last)
00273       {
00274         forward_list __tmp(__first, __last, get_allocator());
00275         if (!__tmp.empty())
00276           return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
00277         else
00278           return iterator(const_cast<_Node_base*>(__pos._M_node));
00279       }
00280 
00281   template<typename _Tp, typename _Alloc>
00282     void
00283     forward_list<_Tp, _Alloc>::
00284     remove(const _Tp& __val)
00285     {
00286       _Node_base* __curr = &this->_M_impl._M_head;
00287       _Node_base* __extra = nullptr;
00288 
00289       while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
00290         {
00291           if (*__tmp->_M_valptr() == __val)
00292             {
00293               if (__tmp->_M_valptr() != std::__addressof(__val))
00294                 {
00295                   this->_M_erase_after(__curr);
00296                   continue;
00297                 }
00298               else
00299                 __extra = __curr;
00300             }
00301           __curr = __curr->_M_next;
00302         }
00303 
00304       if (__extra)
00305         this->_M_erase_after(__extra);
00306     }
00307 
00308   template<typename _Tp, typename _Alloc>
00309     template<typename _Pred>
00310       void
00311       forward_list<_Tp, _Alloc>::
00312       remove_if(_Pred __pred)
00313       {
00314         _Node_base* __curr = &this->_M_impl._M_head;
00315         while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
00316           {
00317             if (__pred(*__tmp->_M_valptr()))
00318               this->_M_erase_after(__curr);
00319             else
00320               __curr = __curr->_M_next;
00321           }
00322       }
00323 
00324   template<typename _Tp, typename _Alloc>
00325     template<typename _BinPred>
00326       void
00327       forward_list<_Tp, _Alloc>::
00328       unique(_BinPred __binary_pred)
00329       {
00330         iterator __first = begin();
00331         iterator __last = end();
00332         if (__first == __last)
00333           return;
00334         iterator __next = __first;
00335         while (++__next != __last)
00336         {
00337           if (__binary_pred(*__first, *__next))
00338             erase_after(__first);
00339           else
00340             __first = __next;
00341           __next = __first;
00342         }
00343       }
00344 
00345   template<typename _Tp, typename _Alloc>
00346     template<typename _Comp>
00347       void
00348       forward_list<_Tp, _Alloc>::
00349       merge(forward_list&& __list, _Comp __comp)
00350       {
00351         _Node_base* __node = &this->_M_impl._M_head;
00352         while (__node->_M_next && __list._M_impl._M_head._M_next)
00353           {
00354             if (__comp(*static_cast<_Node*>
00355                        (__list._M_impl._M_head._M_next)->_M_valptr(),
00356                        *static_cast<_Node*>
00357                        (__node->_M_next)->_M_valptr()))
00358               __node->_M_transfer_after(&__list._M_impl._M_head,
00359                                         __list._M_impl._M_head._M_next);
00360             __node = __node->_M_next;
00361           }
00362 
00363         if (__list._M_impl._M_head._M_next)
00364           *__node = std::move(__list._M_impl._M_head);
00365       }
00366 
00367   template<typename _Tp, typename _Alloc>
00368     bool
00369     operator==(const forward_list<_Tp, _Alloc>& __lx,
00370                const forward_list<_Tp, _Alloc>& __ly)
00371     {
00372       //  We don't have size() so we need to walk through both lists
00373       //  making sure both iterators are valid.
00374       auto __ix = __lx.cbegin();
00375       auto __iy = __ly.cbegin();
00376       while (__ix != __lx.cend() && __iy != __ly.cend())
00377         {
00378           if (*__ix != *__iy)
00379             return false;
00380           ++__ix;
00381           ++__iy;
00382         }
00383       if (__ix == __lx.cend() && __iy == __ly.cend())
00384         return true;
00385       else
00386         return false;
00387     }
00388 
00389   template<typename _Tp, class _Alloc>
00390     template<typename _Comp>
00391       void
00392       forward_list<_Tp, _Alloc>::
00393       sort(_Comp __comp)
00394       {
00395         // If `next' is nullptr, return immediately.
00396         _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
00397         if (!__list)
00398           return;
00399 
00400         unsigned long __insize = 1;
00401 
00402         while (1)
00403           {
00404             _Node* __p = __list;
00405             __list = nullptr;
00406             _Node* __tail = nullptr;
00407 
00408             // Count number of merges we do in this pass.
00409             unsigned long __nmerges = 0;
00410 
00411             while (__p)
00412               {
00413                 ++__nmerges;
00414                 // There exists a merge to be done.
00415                 // Step `insize' places along from p.
00416                 _Node* __q = __p;
00417                 unsigned long __psize = 0;
00418                 for (unsigned long __i = 0; __i < __insize; ++__i)
00419                   {
00420                     ++__psize;
00421                     __q = static_cast<_Node*>(__q->_M_next);
00422                     if (!__q)
00423                       break;
00424                   }
00425 
00426                 // If q hasn't fallen off end, we have two lists to merge.
00427                 unsigned long __qsize = __insize;
00428 
00429                 // Now we have two lists; merge them.
00430                 while (__psize > 0 || (__qsize > 0 && __q))
00431                   {
00432                     // Decide whether next node of merge comes from p or q.
00433                     _Node* __e;
00434                     if (__psize == 0)
00435                       {
00436                         // p is empty; e must come from q.
00437                         __e = __q;
00438                         __q = static_cast<_Node*>(__q->_M_next);
00439                         --__qsize;
00440                       }
00441                     else if (__qsize == 0 || !__q)
00442                       {
00443                         // q is empty; e must come from p.
00444                         __e = __p;
00445                         __p = static_cast<_Node*>(__p->_M_next);
00446                         --__psize;
00447                       }
00448                     else if (__comp(*__p->_M_valptr(), *__q->_M_valptr()))
00449                       {
00450                         // First node of p is lower; e must come from p.
00451                         __e = __p;
00452                         __p = static_cast<_Node*>(__p->_M_next);
00453                         --__psize;
00454                       }
00455                     else
00456                       {
00457                         // First node of q is lower; e must come from q.
00458                         __e = __q;
00459                         __q = static_cast<_Node*>(__q->_M_next);
00460                         --__qsize;
00461                       }
00462 
00463                     // Add the next node to the merged list.
00464                     if (__tail)
00465                       __tail->_M_next = __e;
00466                     else
00467                       __list = __e;
00468                     __tail = __e;
00469                   }
00470 
00471                 // Now p has stepped `insize' places along, and q has too.
00472                 __p = __q;
00473               }
00474             __tail->_M_next = nullptr;
00475 
00476             // If we have done only one merge, we're finished.
00477             // Allow for nmerges == 0, the empty list case.
00478             if (__nmerges <= 1)
00479               {
00480                 this->_M_impl._M_head._M_next = __list;
00481                 return;
00482               }
00483 
00484             // Otherwise repeat, merging lists twice the size.
00485             __insize *= 2;
00486           }
00487       }
00488 
00489 _GLIBCXX_END_NAMESPACE_CONTAINER
00490 _GLIBCXX_END_NAMESPACE_VERSION
00491 } // namespace std
00492 
00493 #endif /* _FORWARD_LIST_TCC */