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           while (__first1 != __last1 && __first2 != __last2)
00390             if (*__first2 < *__first1)
00391               {
00392                 iterator __next = __first2;
00393                 _M_transfer(__first1, __first2, ++__next);
00394                 __first2 = __next;
00395               }
00396             else
00397               ++__first1;
00398           if (__first2 != __last2)
00399             _M_transfer(__last1, __first2, __last2);
00400 
00401           this->_M_inc_size(__x._M_get_size());
00402           __x._M_set_size(0);
00403         }
00404     }
00405 
00406   template<typename _Tp, typename _Alloc>
00407     template <typename _StrictWeakOrdering>
00408       void
00409       list<_Tp, _Alloc>::
00410 #if __cplusplus >= 201103L
00411       merge(list&& __x, _StrictWeakOrdering __comp)
00412 #else
00413       merge(list& __x, _StrictWeakOrdering __comp)
00414 #endif
00415       {
00416         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00417         // 300. list::merge() specification incomplete
00418         if (this != std::__addressof(__x))
00419           {
00420             _M_check_equal_allocators(__x);
00421 
00422             iterator __first1 = begin();
00423             iterator __last1 = end();
00424             iterator __first2 = __x.begin();
00425             iterator __last2 = __x.end();
00426             while (__first1 != __last1 && __first2 != __last2)
00427               if (__comp(*__first2, *__first1))
00428                 {
00429                   iterator __next = __first2;
00430                   _M_transfer(__first1, __first2, ++__next);
00431                   __first2 = __next;
00432                 }
00433               else
00434                 ++__first1;
00435             if (__first2 != __last2)
00436               _M_transfer(__last1, __first2, __last2);
00437 
00438             this->_M_inc_size(__x._M_get_size());
00439             __x._M_set_size(0);
00440           }
00441       }
00442 
00443   template<typename _Tp, typename _Alloc>
00444     void
00445     list<_Tp, _Alloc>::
00446     sort()
00447     {
00448       // Do nothing if the list has length 0 or 1.
00449       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00450           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00451       {
00452         list __carry;
00453         list __tmp[64];
00454         list * __fill = __tmp;
00455         list * __counter;
00456 
00457         do
00458           {
00459             __carry.splice(__carry.begin(), *this, begin());
00460 
00461             for(__counter = __tmp;
00462                 __counter != __fill && !__counter->empty();
00463                 ++__counter)
00464               {
00465                 __counter->merge(__carry);
00466                 __carry.swap(*__counter);
00467               }
00468             __carry.swap(*__counter);
00469             if (__counter == __fill)
00470               ++__fill;
00471           }
00472         while ( !empty() );
00473 
00474         for (__counter = __tmp + 1; __counter != __fill; ++__counter)
00475           __counter->merge(*(__counter - 1));
00476         swap( *(__fill - 1) );
00477       }
00478     }
00479 
00480   template<typename _Tp, typename _Alloc>
00481     template <typename _Predicate>
00482       void
00483       list<_Tp, _Alloc>::
00484       remove_if(_Predicate __pred)
00485       {
00486         iterator __first = begin();
00487         iterator __last = end();
00488         while (__first != __last)
00489           {
00490             iterator __next = __first;
00491             ++__next;
00492             if (__pred(*__first))
00493               _M_erase(__first);
00494             __first = __next;
00495           }
00496       }
00497 
00498   template<typename _Tp, typename _Alloc>
00499     template <typename _BinaryPredicate>
00500       void
00501       list<_Tp, _Alloc>::
00502       unique(_BinaryPredicate __binary_pred)
00503       {
00504         iterator __first = begin();
00505         iterator __last = end();
00506         if (__first == __last)
00507           return;
00508         iterator __next = __first;
00509         while (++__next != __last)
00510           {
00511             if (__binary_pred(*__first, *__next))
00512               _M_erase(__next);
00513             else
00514               __first = __next;
00515             __next = __first;
00516           }
00517       }
00518 
00519   template<typename _Tp, typename _Alloc>
00520     template <typename _StrictWeakOrdering>
00521       void
00522       list<_Tp, _Alloc>::
00523       sort(_StrictWeakOrdering __comp)
00524       {
00525         // Do nothing if the list has length 0 or 1.
00526         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00527             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00528           {
00529             list __carry;
00530             list __tmp[64];
00531             list * __fill = __tmp;
00532             list * __counter;
00533 
00534             do
00535               {
00536                 __carry.splice(__carry.begin(), *this, begin());
00537 
00538                 for(__counter = __tmp;
00539                     __counter != __fill && !__counter->empty();
00540                     ++__counter)
00541                   {
00542                     __counter->merge(__carry, __comp);
00543                     __carry.swap(*__counter);
00544                   }
00545                 __carry.swap(*__counter);
00546                 if (__counter == __fill)
00547                   ++__fill;
00548               }
00549             while ( !empty() );
00550 
00551             for (__counter = __tmp + 1; __counter != __fill; ++__counter)
00552               __counter->merge(*(__counter - 1), __comp);
00553             swap(*(__fill - 1));
00554           }
00555       }
00556 
00557 _GLIBCXX_END_NAMESPACE_CONTAINER
00558 } // namespace std
00559 
00560 #endif /* _LIST_TCC */
00561