libstdc++
list.tcc
Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001-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 /*
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, ++__first2)
00316           *__first1 = *__first2;
00317         if (__first2 == __last2)
00318           erase(__first1, __last1);
00319         else
00320           insert(__last1, __first2, __last2);
00321       }
00322 
00323   template<typename _Tp, typename _Alloc>
00324     void
00325     list<_Tp, _Alloc>::
00326     remove(const value_type& __value)
00327     {
00328       iterator __first = begin();
00329       iterator __last = end();
00330       iterator __extra = __last;
00331       while (__first != __last)
00332         {
00333           iterator __next = __first;
00334           ++__next;
00335           if (*__first == __value)
00336             {
00337               // _GLIBCXX_RESOLVE_LIB_DEFECTS
00338               // 526. Is it undefined if a function in the standard changes
00339               // in parameters?
00340               if (std::__addressof(*__first) != std::__addressof(__value))
00341                 _M_erase(__first);
00342               else
00343                 __extra = __first;
00344             }
00345           __first = __next;
00346         }
00347       if (__extra != __last)
00348         _M_erase(__extra);
00349     }
00350 
00351   template<typename _Tp, typename _Alloc>
00352     void
00353     list<_Tp, _Alloc>::
00354     unique()
00355     {
00356       iterator __first = begin();
00357       iterator __last = end();
00358       if (__first == __last)
00359         return;
00360       iterator __next = __first;
00361       while (++__next != __last)
00362         {
00363           if (*__first == *__next)
00364             _M_erase(__next);
00365           else
00366             __first = __next;
00367           __next = __first;
00368         }
00369     }
00370 
00371   template<typename _Tp, typename _Alloc>
00372     void
00373     list<_Tp, _Alloc>::
00374 #if __cplusplus >= 201103L
00375     merge(list&& __x)
00376 #else
00377     merge(list& __x)
00378 #endif
00379     {
00380       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00381       // 300. list::merge() specification incomplete
00382       if (this != std::__addressof(__x))
00383         {
00384           _M_check_equal_allocators(__x);
00385 
00386           iterator __first1 = begin();
00387           iterator __last1 = end();
00388           iterator __first2 = __x.begin();
00389           iterator __last2 = __x.end();
00390           const size_t __orig_size = __x.size();
00391           __try {
00392             while (__first1 != __last1 && __first2 != __last2)
00393               if (*__first2 < *__first1)
00394                 {
00395                   iterator __next = __first2;
00396                   _M_transfer(__first1, __first2, ++__next);
00397                   __first2 = __next;
00398                 }
00399               else
00400                 ++__first1;
00401             if (__first2 != __last2)
00402               _M_transfer(__last1, __first2, __last2);
00403 
00404             this->_M_inc_size(__x._M_get_size());
00405             __x._M_set_size(0);
00406           }
00407           __catch(...)
00408             {
00409               const size_t __dist = std::distance(__first2, __last2);
00410               this->_M_inc_size(__orig_size - __dist);
00411               __x._M_set_size(__dist);
00412               __throw_exception_again;
00413             }
00414         }
00415     }
00416 
00417   template<typename _Tp, typename _Alloc>
00418     template <typename _StrictWeakOrdering>
00419       void
00420       list<_Tp, _Alloc>::
00421 #if __cplusplus >= 201103L
00422       merge(list&& __x, _StrictWeakOrdering __comp)
00423 #else
00424       merge(list& __x, _StrictWeakOrdering __comp)
00425 #endif
00426       {
00427         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00428         // 300. list::merge() specification incomplete
00429         if (this != std::__addressof(__x))
00430           {
00431             _M_check_equal_allocators(__x);
00432 
00433             iterator __first1 = begin();
00434             iterator __last1 = end();
00435             iterator __first2 = __x.begin();
00436             iterator __last2 = __x.end();
00437             const size_t __orig_size = __x.size();
00438             __try
00439               {
00440                 while (__first1 != __last1 && __first2 != __last2)
00441                   if (__comp(*__first2, *__first1))
00442                     {
00443                       iterator __next = __first2;
00444                       _M_transfer(__first1, __first2, ++__next);
00445                       __first2 = __next;
00446                     }
00447                   else
00448                     ++__first1;
00449                 if (__first2 != __last2)
00450                   _M_transfer(__last1, __first2, __last2);
00451 
00452                 this->_M_inc_size(__x._M_get_size());
00453                 __x._M_set_size(0);
00454               }
00455             __catch(...)
00456               {
00457                 const size_t __dist = std::distance(__first2, __last2);
00458                 this->_M_inc_size(__orig_size - __dist);
00459                 __x._M_set_size(__dist);
00460                 __throw_exception_again;
00461               }
00462           }
00463       }
00464 
00465   template<typename _Tp, typename _Alloc>
00466     void
00467     list<_Tp, _Alloc>::
00468     sort()
00469     {
00470       // Do nothing if the list has length 0 or 1.
00471       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00472           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00473       {
00474         list __carry;
00475         list __tmp[64];
00476         list * __fill = __tmp;
00477         list * __counter;
00478         __try
00479           {
00480             do
00481               {
00482                 __carry.splice(__carry.begin(), *this, begin());
00483 
00484                 for(__counter = __tmp;
00485                     __counter != __fill && !__counter->empty();
00486                     ++__counter)
00487                   {
00488                     __counter->merge(__carry);
00489                     __carry.swap(*__counter);
00490                   }
00491                 __carry.swap(*__counter);
00492                 if (__counter == __fill)
00493                   ++__fill;
00494               }
00495             while ( !empty() );
00496 
00497             for (__counter = __tmp + 1; __counter != __fill; ++__counter)
00498               __counter->merge(*(__counter - 1));
00499             swap( *(__fill - 1) );
00500           }
00501         __catch(...)
00502           {
00503             this->splice(this->end(), __carry);
00504             for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
00505               this->splice(this->end(), __tmp[__i]);
00506             __throw_exception_again;
00507           }
00508       }
00509     }
00510 
00511   template<typename _Tp, typename _Alloc>
00512     template <typename _Predicate>
00513       void
00514       list<_Tp, _Alloc>::
00515       remove_if(_Predicate __pred)
00516       {
00517         iterator __first = begin();
00518         iterator __last = end();
00519         while (__first != __last)
00520           {
00521             iterator __next = __first;
00522             ++__next;
00523             if (__pred(*__first))
00524               _M_erase(__first);
00525             __first = __next;
00526           }
00527       }
00528 
00529   template<typename _Tp, typename _Alloc>
00530     template <typename _BinaryPredicate>
00531       void
00532       list<_Tp, _Alloc>::
00533       unique(_BinaryPredicate __binary_pred)
00534       {
00535         iterator __first = begin();
00536         iterator __last = end();
00537         if (__first == __last)
00538           return;
00539         iterator __next = __first;
00540         while (++__next != __last)
00541           {
00542             if (__binary_pred(*__first, *__next))
00543               _M_erase(__next);
00544             else
00545               __first = __next;
00546             __next = __first;
00547           }
00548       }
00549 
00550   template<typename _Tp, typename _Alloc>
00551     template <typename _StrictWeakOrdering>
00552       void
00553       list<_Tp, _Alloc>::
00554       sort(_StrictWeakOrdering __comp)
00555       {
00556         // Do nothing if the list has length 0 or 1.
00557         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00558             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00559           {
00560             list __carry;
00561             list __tmp[64];
00562             list * __fill = __tmp;
00563             list * __counter;
00564             __try
00565               {
00566                 do
00567                   {
00568                     __carry.splice(__carry.begin(), *this, begin());
00569 
00570                     for(__counter = __tmp;
00571                         __counter != __fill && !__counter->empty();
00572                         ++__counter)
00573                       {
00574                         __counter->merge(__carry, __comp);
00575                         __carry.swap(*__counter);
00576                       }
00577                     __carry.swap(*__counter);
00578                     if (__counter == __fill)
00579                       ++__fill;
00580                   }
00581                 while ( !empty() );
00582 
00583                 for (__counter = __tmp + 1; __counter != __fill; ++__counter)
00584                   __counter->merge(*(__counter - 1), __comp);
00585                 swap(*(__fill - 1));
00586               }
00587             __catch(...)
00588               {
00589                 this->splice(this->end(), __carry);
00590                 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
00591                   this->splice(this->end(), __tmp[__i]);
00592                 __throw_exception_again;
00593               }
00594           }
00595       }
00596 
00597 _GLIBCXX_END_NAMESPACE_CONTAINER
00598 _GLIBCXX_END_NAMESPACE_VERSION
00599 } // namespace std
00600 
00601 #endif /* _LIST_TCC */
00602