libstdc++
list.tcc
Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2016 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           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               size_t __dist = 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             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                 size_t __dist = 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 
00478         do
00479           {
00480             __carry.splice(__carry.begin(), *this, begin());
00481 
00482             for(__counter = __tmp;
00483                 __counter != __fill && !__counter->empty();
00484                 ++__counter)
00485               {
00486                 __counter->merge(__carry);
00487                 __carry.swap(*__counter);
00488               }
00489             __carry.swap(*__counter);
00490             if (__counter == __fill)
00491               ++__fill;
00492           }
00493         while ( !empty() );
00494 
00495         for (__counter = __tmp + 1; __counter != __fill; ++__counter)
00496           __counter->merge(*(__counter - 1));
00497         swap( *(__fill - 1) );
00498       }
00499     }
00500 
00501   template<typename _Tp, typename _Alloc>
00502     template <typename _Predicate>
00503       void
00504       list<_Tp, _Alloc>::
00505       remove_if(_Predicate __pred)
00506       {
00507         iterator __first = begin();
00508         iterator __last = end();
00509         while (__first != __last)
00510           {
00511             iterator __next = __first;
00512             ++__next;
00513             if (__pred(*__first))
00514               _M_erase(__first);
00515             __first = __next;
00516           }
00517       }
00518 
00519   template<typename _Tp, typename _Alloc>
00520     template <typename _BinaryPredicate>
00521       void
00522       list<_Tp, _Alloc>::
00523       unique(_BinaryPredicate __binary_pred)
00524       {
00525         iterator __first = begin();
00526         iterator __last = end();
00527         if (__first == __last)
00528           return;
00529         iterator __next = __first;
00530         while (++__next != __last)
00531           {
00532             if (__binary_pred(*__first, *__next))
00533               _M_erase(__next);
00534             else
00535               __first = __next;
00536             __next = __first;
00537           }
00538       }
00539 
00540   template<typename _Tp, typename _Alloc>
00541     template <typename _StrictWeakOrdering>
00542       void
00543       list<_Tp, _Alloc>::
00544       sort(_StrictWeakOrdering __comp)
00545       {
00546         // Do nothing if the list has length 0 or 1.
00547         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00548             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00549           {
00550             list __carry;
00551             list __tmp[64];
00552             list * __fill = __tmp;
00553             list * __counter;
00554 
00555             do
00556               {
00557                 __carry.splice(__carry.begin(), *this, begin());
00558 
00559                 for(__counter = __tmp;
00560                     __counter != __fill && !__counter->empty();
00561                     ++__counter)
00562                   {
00563                     __counter->merge(__carry, __comp);
00564                     __carry.swap(*__counter);
00565                   }
00566                 __carry.swap(*__counter);
00567                 if (__counter == __fill)
00568                   ++__fill;
00569               }
00570             while ( !empty() );
00571 
00572             for (__counter = __tmp + 1; __counter != __fill; ++__counter)
00573               __counter->merge(*(__counter - 1), __comp);
00574             swap(*(__fill - 1));
00575           }
00576       }
00577 
00578 _GLIBCXX_END_NAMESPACE_CONTAINER
00579 } // namespace std
00580 
00581 #endif /* _LIST_TCC */
00582