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