libstdc++
list.tcc
Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2019 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 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996,1997
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/list.tcc
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{list}
00054  */
00055 
00056 #ifndef _LIST_TCC
00057 #define _LIST_TCC 1
00058 
00059 namespace std _GLIBCXX_VISIBILITY(default)
00060 {
00061 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00062 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00063 
00064   template<typename _Tp, typename _Alloc>
00065     void
00066     _List_base<_Tp, _Alloc>::
00067     _M_clear() _GLIBCXX_NOEXCEPT
00068     {
00069       typedef _List_node<_Tp>  _Node;
00070       __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
00071       while (__cur != &_M_impl._M_node)
00072         {
00073           _Node* __tmp = static_cast<_Node*>(__cur);
00074           __cur = __tmp->_M_next;
00075           _Tp* __val = __tmp->_M_valptr();
00076 #if __cplusplus >= 201103L
00077           _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
00078 #else
00079           _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
00080 #endif
00081           _M_put_node(__tmp);
00082         }
00083     }
00084 
00085 #if __cplusplus >= 201103L
00086   template<typename _Tp, typename _Alloc>
00087     template<typename... _Args>
00088       typename list<_Tp, _Alloc>::iterator
00089       list<_Tp, _Alloc>::
00090       emplace(const_iterator __position, _Args&&... __args)
00091       {
00092         _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
00093         __tmp->_M_hook(__position._M_const_cast()._M_node);
00094         this->_M_inc_size(1);
00095         return iterator(__tmp);
00096       }
00097 #endif
00098 
00099   template<typename _Tp, typename _Alloc>
00100     typename list<_Tp, _Alloc>::iterator
00101     list<_Tp, _Alloc>::
00102 #if __cplusplus >= 201103L
00103     insert(const_iterator __position, const value_type& __x)
00104 #else
00105     insert(iterator __position, const value_type& __x)
00106 #endif
00107     {
00108       _Node* __tmp = _M_create_node(__x);
00109       __tmp->_M_hook(__position._M_const_cast()._M_node);
00110       this->_M_inc_size(1);
00111       return iterator(__tmp);
00112     }
00113 
00114 #if __cplusplus >= 201103L
00115   template<typename _Tp, typename _Alloc>
00116     typename list<_Tp, _Alloc>::iterator
00117     list<_Tp, _Alloc>::
00118     insert(const_iterator __position, size_type __n, const value_type& __x)
00119     {
00120       if (__n)
00121         {
00122           list __tmp(__n, __x, get_allocator());
00123           iterator __it = __tmp.begin();
00124           splice(__position, __tmp);
00125           return __it;
00126         }
00127       return __position._M_const_cast();
00128     }
00129 
00130   template<typename _Tp, typename _Alloc>
00131     template<typename _InputIterator, typename>
00132       typename list<_Tp, _Alloc>::iterator
00133       list<_Tp, _Alloc>::
00134       insert(const_iterator __position, _InputIterator __first,
00135              _InputIterator __last)
00136       {
00137         list __tmp(__first, __last, get_allocator());
00138         if (!__tmp.empty())
00139           {
00140             iterator __it = __tmp.begin();
00141             splice(__position, __tmp);
00142             return __it;
00143           }
00144         return __position._M_const_cast();
00145       }
00146 #endif
00147 
00148   template<typename _Tp, typename _Alloc>
00149     typename list<_Tp, _Alloc>::iterator
00150     list<_Tp, _Alloc>::
00151 #if __cplusplus >= 201103L
00152     erase(const_iterator __position) noexcept
00153 #else
00154     erase(iterator __position)
00155 #endif
00156     {
00157       iterator __ret = iterator(__position._M_node->_M_next);
00158       _M_erase(__position._M_const_cast());
00159       return __ret;
00160     }
00161 
00162   // Return a const_iterator indicating the position to start inserting or
00163   // erasing elements (depending whether the list is growing or shrinking),
00164   // and set __new_size to the number of new elements that must be appended.
00165   // Equivalent to the following, but performed optimally:
00166   // if (__new_size < size()) {
00167   //   __new_size = 0;
00168   //   return std::next(begin(), __new_size);
00169   // } else {
00170   //   __newsize -= size();
00171   //   return end();
00172   // }
00173   template<typename _Tp, typename _Alloc>
00174     typename list<_Tp, _Alloc>::const_iterator
00175     list<_Tp, _Alloc>::
00176     _M_resize_pos(size_type& __new_size) const
00177     {
00178       const_iterator __i;
00179 #if _GLIBCXX_USE_CXX11_ABI
00180       const size_type __len = size();
00181       if (__new_size < __len)
00182         {
00183           if (__new_size <= __len / 2)
00184             {
00185               __i = begin();
00186               std::advance(__i, __new_size);
00187             }
00188           else
00189             {
00190               __i = end();
00191               ptrdiff_t __num_erase = __len - __new_size;
00192               std::advance(__i, -__num_erase);
00193             }
00194           __new_size = 0;
00195           return __i;
00196         }
00197       else
00198         __i = end();
00199 #else
00200       size_type __len = 0;
00201       for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
00202         ;
00203 #endif
00204       __new_size -= __len;
00205       return __i;
00206     }
00207 
00208 #if __cplusplus >= 201103L
00209   template<typename _Tp, typename _Alloc>
00210     void
00211     list<_Tp, _Alloc>::
00212     _M_default_append(size_type __n)
00213     {
00214       size_type __i = 0;
00215       __try
00216         {
00217           for (; __i < __n; ++__i)
00218             emplace_back();
00219         }
00220       __catch(...)
00221         {
00222           for (; __i; --__i)
00223             pop_back();
00224           __throw_exception_again;
00225         }
00226     }
00227 
00228   template<typename _Tp, typename _Alloc>
00229     void
00230     list<_Tp, _Alloc>::
00231     resize(size_type __new_size)
00232     {
00233       const_iterator __i = _M_resize_pos(__new_size);
00234       if (__new_size)
00235         _M_default_append(__new_size);
00236       else
00237         erase(__i, end());
00238     }
00239 
00240   template<typename _Tp, typename _Alloc>
00241     void
00242     list<_Tp, _Alloc>::
00243     resize(size_type __new_size, const value_type& __x)
00244     {
00245       const_iterator __i = _M_resize_pos(__new_size);
00246       if (__new_size)
00247         insert(end(), __new_size, __x);
00248       else
00249         erase(__i, end());
00250     }
00251 #else
00252   template<typename _Tp, typename _Alloc>
00253     void
00254     list<_Tp, _Alloc>::
00255     resize(size_type __new_size, value_type __x)
00256     {
00257       const_iterator __i = _M_resize_pos(__new_size);
00258       if (__new_size)
00259         insert(end(), __new_size, __x);
00260       else
00261         erase(__i._M_const_cast(), end());
00262     }
00263 #endif
00264 
00265   template<typename _Tp, typename _Alloc>
00266     list<_Tp, _Alloc>&
00267     list<_Tp, _Alloc>::
00268     operator=(const list& __x)
00269     {
00270       if (this != std::__addressof(__x))
00271         {
00272 #if __cplusplus >= 201103L
00273           if (_Node_alloc_traits::_S_propagate_on_copy_assign())
00274             {
00275               auto& __this_alloc = this->_M_get_Node_allocator();
00276               auto& __that_alloc = __x._M_get_Node_allocator();
00277               if (!_Node_alloc_traits::_S_always_equal()
00278                   && __this_alloc != __that_alloc)
00279                 {
00280                   // replacement allocator cannot free existing storage
00281                   clear();
00282                 }
00283               std::__alloc_on_copy(__this_alloc, __that_alloc);
00284             }
00285 #endif
00286           _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
00287         }
00288       return *this;
00289     }
00290 
00291   template<typename _Tp, typename _Alloc>
00292     void
00293     list<_Tp, _Alloc>::
00294     _M_fill_assign(size_type __n, const value_type& __val)
00295     {
00296       iterator __i = begin();
00297       for (; __i != end() && __n > 0; ++__i, --__n)
00298         *__i = __val;
00299       if (__n > 0)
00300         insert(end(), __n, __val);
00301       else
00302         erase(__i, end());
00303     }
00304 
00305   template<typename _Tp, typename _Alloc>
00306     template <typename _InputIterator>
00307       void
00308       list<_Tp, _Alloc>::
00309       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
00310                          __false_type)
00311       {
00312         iterator __first1 = begin();
00313         iterator __last1 = end();
00314         for (; __first1 != __last1 && __first2 != __last2;
00315              ++__first1, (void)++__first2)
00316           *__first1 = *__first2;
00317         if (__first2 == __last2)
00318           erase(__first1, __last1);
00319         else
00320           insert(__last1, __first2, __last2);
00321       }
00322 
00323 #if __cplusplus > 201703L
00324 # define _GLIBCXX20_ONLY(__expr) __expr
00325 #else
00326 # define _GLIBCXX20_ONLY(__expr)
00327 #endif
00328 
00329   template<typename _Tp, typename _Alloc>
00330     typename list<_Tp, _Alloc>::__remove_return_type
00331     list<_Tp, _Alloc>::
00332     remove(const value_type& __value)
00333     {
00334       size_type __removed __attribute__((__unused__)) = 0;
00335       iterator __first = begin();
00336       iterator __last = end();
00337       iterator __extra = __last;
00338       while (__first != __last)
00339         {
00340           iterator __next = __first;
00341           ++__next;
00342           if (*__first == __value)
00343             {
00344               // _GLIBCXX_RESOLVE_LIB_DEFECTS
00345               // 526. Is it undefined if a function in the standard changes
00346               // in parameters?
00347               if (std::__addressof(*__first) != std::__addressof(__value))
00348                 {
00349                   _M_erase(__first);
00350                   _GLIBCXX20_ONLY( __removed++ );
00351                 }
00352               else
00353                 __extra = __first;
00354             }
00355           __first = __next;
00356         }
00357       if (__extra != __last)
00358         {
00359           _M_erase(__extra);
00360           _GLIBCXX20_ONLY( __removed++ );
00361         }
00362       return _GLIBCXX20_ONLY( __removed );
00363     }
00364 
00365   template<typename _Tp, typename _Alloc>
00366     typename list<_Tp, _Alloc>::__remove_return_type
00367     list<_Tp, _Alloc>::
00368     unique()
00369     {
00370       iterator __first = begin();
00371       iterator __last = end();
00372       if (__first == __last)
00373         return _GLIBCXX20_ONLY( 0 );
00374       size_type __removed __attribute__((__unused__)) = 0;
00375       iterator __next = __first;
00376       while (++__next != __last)
00377         {
00378           if (*__first == *__next)
00379             {
00380               _M_erase(__next);
00381               _GLIBCXX20_ONLY( __removed++ );
00382             }
00383           else
00384             __first = __next;
00385           __next = __first;
00386         }
00387       return _GLIBCXX20_ONLY( __removed );
00388     }
00389 
00390   template<typename _Tp, typename _Alloc>
00391     void
00392     list<_Tp, _Alloc>::
00393 #if __cplusplus >= 201103L
00394     merge(list&& __x)
00395 #else
00396     merge(list& __x)
00397 #endif
00398     {
00399       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00400       // 300. list::merge() specification incomplete
00401       if (this != std::__addressof(__x))
00402         {
00403           _M_check_equal_allocators(__x);
00404 
00405           iterator __first1 = begin();
00406           iterator __last1 = end();
00407           iterator __first2 = __x.begin();
00408           iterator __last2 = __x.end();
00409           const size_t __orig_size = __x.size();
00410           __try {
00411             while (__first1 != __last1 && __first2 != __last2)
00412               if (*__first2 < *__first1)
00413                 {
00414                   iterator __next = __first2;
00415                   _M_transfer(__first1, __first2, ++__next);
00416                   __first2 = __next;
00417                 }
00418               else
00419                 ++__first1;
00420             if (__first2 != __last2)
00421               _M_transfer(__last1, __first2, __last2);
00422 
00423             this->_M_inc_size(__x._M_get_size());
00424             __x._M_set_size(0);
00425           }
00426           __catch(...)
00427             {
00428               const size_t __dist = std::distance(__first2, __last2);
00429               this->_M_inc_size(__orig_size - __dist);
00430               __x._M_set_size(__dist);
00431               __throw_exception_again;
00432             }
00433         }
00434     }
00435 
00436   template<typename _Tp, typename _Alloc>
00437     template <typename _StrictWeakOrdering>
00438       void
00439       list<_Tp, _Alloc>::
00440 #if __cplusplus >= 201103L
00441       merge(list&& __x, _StrictWeakOrdering __comp)
00442 #else
00443       merge(list& __x, _StrictWeakOrdering __comp)
00444 #endif
00445       {
00446         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00447         // 300. list::merge() specification incomplete
00448         if (this != std::__addressof(__x))
00449           {
00450             _M_check_equal_allocators(__x);
00451 
00452             iterator __first1 = begin();
00453             iterator __last1 = end();
00454             iterator __first2 = __x.begin();
00455             iterator __last2 = __x.end();
00456             const size_t __orig_size = __x.size();
00457             __try
00458               {
00459                 while (__first1 != __last1 && __first2 != __last2)
00460                   if (__comp(*__first2, *__first1))
00461                     {
00462                       iterator __next = __first2;
00463                       _M_transfer(__first1, __first2, ++__next);
00464                       __first2 = __next;
00465                     }
00466                   else
00467                     ++__first1;
00468                 if (__first2 != __last2)
00469                   _M_transfer(__last1, __first2, __last2);
00470 
00471                 this->_M_inc_size(__x._M_get_size());
00472                 __x._M_set_size(0);
00473               }
00474             __catch(...)
00475               {
00476                 const size_t __dist = std::distance(__first2, __last2);
00477                 this->_M_inc_size(__orig_size - __dist);
00478                 __x._M_set_size(__dist);
00479                 __throw_exception_again;
00480               }
00481           }
00482       }
00483 
00484   template<typename _Tp, typename _Alloc>
00485     void
00486     list<_Tp, _Alloc>::
00487     sort()
00488     {
00489       // Do nothing if the list has length 0 or 1.
00490       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00491           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00492       {
00493         list __carry;
00494         list __tmp[64];
00495         list * __fill = __tmp;
00496         list * __counter;
00497         __try
00498           {
00499             do
00500               {
00501                 __carry.splice(__carry.begin(), *this, begin());
00502 
00503                 for(__counter = __tmp;
00504                     __counter != __fill && !__counter->empty();
00505                     ++__counter)
00506                   {
00507                     __counter->merge(__carry);
00508                     __carry.swap(*__counter);
00509                   }
00510                 __carry.swap(*__counter);
00511                 if (__counter == __fill)
00512                   ++__fill;
00513               }
00514             while ( !empty() );
00515 
00516             for (__counter = __tmp + 1; __counter != __fill; ++__counter)
00517               __counter->merge(*(__counter - 1));
00518             swap( *(__fill - 1) );
00519           }
00520         __catch(...)
00521           {
00522             this->splice(this->end(), __carry);
00523             for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
00524               this->splice(this->end(), __tmp[__i]);
00525             __throw_exception_again;
00526           }
00527       }
00528     }
00529 
00530   template<typename _Tp, typename _Alloc>
00531     template <typename _Predicate>
00532       typename list<_Tp, _Alloc>::__remove_return_type
00533       list<_Tp, _Alloc>::
00534       remove_if(_Predicate __pred)
00535       {
00536         size_type __removed __attribute__((__unused__)) = 0;
00537         iterator __first = begin();
00538         iterator __last = end();
00539         while (__first != __last)
00540           {
00541             iterator __next = __first;
00542             ++__next;
00543             if (__pred(*__first))
00544               {
00545                 _M_erase(__first);
00546                 _GLIBCXX20_ONLY( __removed++ );
00547               }
00548             __first = __next;
00549           }
00550         return _GLIBCXX20_ONLY( __removed );
00551       }
00552 
00553   template<typename _Tp, typename _Alloc>
00554     template <typename _BinaryPredicate>
00555       typename list<_Tp, _Alloc>::__remove_return_type
00556       list<_Tp, _Alloc>::
00557       unique(_BinaryPredicate __binary_pred)
00558       {
00559         iterator __first = begin();
00560         iterator __last = end();
00561         if (__first == __last)
00562           return _GLIBCXX20_ONLY(0);
00563         size_type __removed __attribute__((__unused__)) = 0;
00564         iterator __next = __first;
00565         while (++__next != __last)
00566           {
00567             if (__binary_pred(*__first, *__next))
00568               {
00569                 _M_erase(__next);
00570                 _GLIBCXX20_ONLY( __removed++ );
00571               }
00572             else
00573               __first = __next;
00574             __next = __first;
00575           }
00576         return _GLIBCXX20_ONLY( __removed );
00577       }
00578 
00579 #undef _GLIBCXX20_ONLY
00580 
00581   template<typename _Tp, typename _Alloc>
00582     template <typename _StrictWeakOrdering>
00583       void
00584       list<_Tp, _Alloc>::
00585       sort(_StrictWeakOrdering __comp)
00586       {
00587         // Do nothing if the list has length 0 or 1.
00588         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00589             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00590           {
00591             list __carry;
00592             list __tmp[64];
00593             list * __fill = __tmp;
00594             list * __counter;
00595             __try
00596               {
00597                 do
00598                   {
00599                     __carry.splice(__carry.begin(), *this, begin());
00600 
00601                     for(__counter = __tmp;
00602                         __counter != __fill && !__counter->empty();
00603                         ++__counter)
00604                       {
00605                         __counter->merge(__carry, __comp);
00606                         __carry.swap(*__counter);
00607                       }
00608                     __carry.swap(*__counter);
00609                     if (__counter == __fill)
00610                       ++__fill;
00611                   }
00612                 while ( !empty() );
00613 
00614                 for (__counter = __tmp + 1; __counter != __fill; ++__counter)
00615                   __counter->merge(*(__counter - 1), __comp);
00616                 swap(*(__fill - 1));
00617               }
00618             __catch(...)
00619               {
00620                 this->splice(this->end(), __carry);
00621                 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
00622                   this->splice(this->end(), __tmp[__i]);
00623                 __throw_exception_again;
00624               }
00625           }
00626       }
00627 
00628 _GLIBCXX_END_NAMESPACE_CONTAINER
00629 _GLIBCXX_END_NAMESPACE_VERSION
00630 } // namespace std
00631 
00632 #endif /* _LIST_TCC */
00633