libstdc++
list.tcc
Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2013 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()
00067     {
00068       typedef _List_node<_Tp>  _Node;
00069       _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
00070       while (__cur != &_M_impl._M_node)
00071     {
00072       _Node* __tmp = __cur;
00073       __cur = static_cast<_Node*>(__cur->_M_next);
00074 #if __cplusplus >= 201103L
00075       _M_get_Node_allocator().destroy(__tmp);
00076 #else
00077       _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
00078 #endif
00079       _M_put_node(__tmp);
00080     }
00081     }
00082 
00083 #if __cplusplus >= 201103L
00084   template<typename _Tp, typename _Alloc>
00085     template<typename... _Args>
00086       typename list<_Tp, _Alloc>::iterator
00087       list<_Tp, _Alloc>::
00088       emplace(iterator __position, _Args&&... __args)
00089       {
00090     _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
00091     __tmp->_M_hook(__position._M_node);
00092     return iterator(__tmp);
00093       }
00094 #endif
00095 
00096   template<typename _Tp, typename _Alloc>
00097     typename list<_Tp, _Alloc>::iterator
00098     list<_Tp, _Alloc>::
00099     insert(iterator __position, const value_type& __x)
00100     {
00101       _Node* __tmp = _M_create_node(__x);
00102       __tmp->_M_hook(__position._M_node);
00103       return iterator(__tmp);
00104     }
00105 
00106   template<typename _Tp, typename _Alloc>
00107     typename list<_Tp, _Alloc>::iterator
00108     list<_Tp, _Alloc>::
00109     erase(iterator __position)
00110     {
00111       iterator __ret = iterator(__position._M_node->_M_next);
00112       _M_erase(__position);
00113       return __ret;
00114     }
00115 
00116 #if __cplusplus >= 201103L
00117   template<typename _Tp, typename _Alloc>
00118     void
00119     list<_Tp, _Alloc>::
00120     _M_default_append(size_type __n)
00121     {
00122       size_type __i = 0;
00123       __try
00124     {
00125       for (; __i < __n; ++__i)
00126         emplace_back();
00127     }
00128       __catch(...)
00129     {
00130       for (; __i; --__i)
00131         pop_back();
00132       __throw_exception_again;
00133     }
00134     }
00135 
00136   template<typename _Tp, typename _Alloc>
00137     void
00138     list<_Tp, _Alloc>::
00139     resize(size_type __new_size)
00140     {
00141       iterator __i = begin();
00142       size_type __len = 0;
00143       for (; __i != end() && __len < __new_size; ++__i, ++__len)
00144         ;
00145       if (__len == __new_size)
00146         erase(__i, end());
00147       else                          // __i == end()
00148     _M_default_append(__new_size - __len);
00149     }
00150 
00151   template<typename _Tp, typename _Alloc>
00152     void
00153     list<_Tp, _Alloc>::
00154     resize(size_type __new_size, const value_type& __x)
00155     {
00156       iterator __i = begin();
00157       size_type __len = 0;
00158       for (; __i != end() && __len < __new_size; ++__i, ++__len)
00159         ;
00160       if (__len == __new_size)
00161         erase(__i, end());
00162       else                          // __i == end()
00163         insert(end(), __new_size - __len, __x);
00164     }
00165 #else
00166   template<typename _Tp, typename _Alloc>
00167     void
00168     list<_Tp, _Alloc>::
00169     resize(size_type __new_size, value_type __x)
00170     {
00171       iterator __i = begin();
00172       size_type __len = 0;
00173       for (; __i != end() && __len < __new_size; ++__i, ++__len)
00174         ;
00175       if (__len == __new_size)
00176         erase(__i, end());
00177       else                          // __i == end()
00178         insert(end(), __new_size - __len, __x);
00179     }
00180 #endif
00181 
00182   template<typename _Tp, typename _Alloc>
00183     list<_Tp, _Alloc>&
00184     list<_Tp, _Alloc>::
00185     operator=(const list& __x)
00186     {
00187       if (this != &__x)
00188     {
00189       iterator __first1 = begin();
00190       iterator __last1 = end();
00191       const_iterator __first2 = __x.begin();
00192       const_iterator __last2 = __x.end();
00193       for (; __first1 != __last1 && __first2 != __last2;
00194            ++__first1, ++__first2)
00195         *__first1 = *__first2;
00196       if (__first2 == __last2)
00197         erase(__first1, __last1);
00198       else
00199         insert(__last1, __first2, __last2);
00200     }
00201       return *this;
00202     }
00203 
00204   template<typename _Tp, typename _Alloc>
00205     void
00206     list<_Tp, _Alloc>::
00207     _M_fill_assign(size_type __n, const value_type& __val)
00208     {
00209       iterator __i = begin();
00210       for (; __i != end() && __n > 0; ++__i, --__n)
00211         *__i = __val;
00212       if (__n > 0)
00213         insert(end(), __n, __val);
00214       else
00215         erase(__i, end());
00216     }
00217 
00218   template<typename _Tp, typename _Alloc>
00219     template <typename _InputIterator>
00220       void
00221       list<_Tp, _Alloc>::
00222       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
00223              __false_type)
00224       {
00225         iterator __first1 = begin();
00226         iterator __last1 = end();
00227         for (; __first1 != __last1 && __first2 != __last2;
00228          ++__first1, ++__first2)
00229           *__first1 = *__first2;
00230         if (__first2 == __last2)
00231           erase(__first1, __last1);
00232         else
00233           insert(__last1, __first2, __last2);
00234       }
00235 
00236   template<typename _Tp, typename _Alloc>
00237     void
00238     list<_Tp, _Alloc>::
00239     remove(const value_type& __value)
00240     {
00241       iterator __first = begin();
00242       iterator __last = end();
00243       iterator __extra = __last;
00244       while (__first != __last)
00245     {
00246       iterator __next = __first;
00247       ++__next;
00248       if (*__first == __value)
00249         {
00250           // _GLIBCXX_RESOLVE_LIB_DEFECTS
00251           // 526. Is it undefined if a function in the standard changes
00252           // in parameters?
00253           if (std::__addressof(*__first) != std::__addressof(__value))
00254         _M_erase(__first);
00255           else
00256         __extra = __first;
00257         }
00258       __first = __next;
00259     }
00260       if (__extra != __last)
00261     _M_erase(__extra);
00262     }
00263 
00264   template<typename _Tp, typename _Alloc>
00265     void
00266     list<_Tp, _Alloc>::
00267     unique()
00268     {
00269       iterator __first = begin();
00270       iterator __last = end();
00271       if (__first == __last)
00272     return;
00273       iterator __next = __first;
00274       while (++__next != __last)
00275     {
00276       if (*__first == *__next)
00277         _M_erase(__next);
00278       else
00279         __first = __next;
00280       __next = __first;
00281     }
00282     }
00283 
00284   template<typename _Tp, typename _Alloc>
00285     void
00286     list<_Tp, _Alloc>::
00287 #if __cplusplus >= 201103L
00288     merge(list&& __x)
00289 #else
00290     merge(list& __x)
00291 #endif
00292     {
00293       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00294       // 300. list::merge() specification incomplete
00295       if (this != &__x)
00296     {
00297       _M_check_equal_allocators(__x); 
00298 
00299       iterator __first1 = begin();
00300       iterator __last1 = end();
00301       iterator __first2 = __x.begin();
00302       iterator __last2 = __x.end();
00303       while (__first1 != __last1 && __first2 != __last2)
00304         if (*__first2 < *__first1)
00305           {
00306         iterator __next = __first2;
00307         _M_transfer(__first1, __first2, ++__next);
00308         __first2 = __next;
00309           }
00310         else
00311           ++__first1;
00312       if (__first2 != __last2)
00313         _M_transfer(__last1, __first2, __last2);
00314     }
00315     }
00316 
00317   template<typename _Tp, typename _Alloc>
00318     template <typename _StrictWeakOrdering>
00319       void
00320       list<_Tp, _Alloc>::
00321 #if __cplusplus >= 201103L
00322       merge(list&& __x, _StrictWeakOrdering __comp)
00323 #else
00324       merge(list& __x, _StrictWeakOrdering __comp)
00325 #endif
00326       {
00327     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00328     // 300. list::merge() specification incomplete
00329     if (this != &__x)
00330       {
00331         _M_check_equal_allocators(__x);
00332 
00333         iterator __first1 = begin();
00334         iterator __last1 = end();
00335         iterator __first2 = __x.begin();
00336         iterator __last2 = __x.end();
00337         while (__first1 != __last1 && __first2 != __last2)
00338           if (__comp(*__first2, *__first1))
00339         {
00340           iterator __next = __first2;
00341           _M_transfer(__first1, __first2, ++__next);
00342           __first2 = __next;
00343         }
00344           else
00345         ++__first1;
00346         if (__first2 != __last2)
00347           _M_transfer(__last1, __first2, __last2);
00348       }
00349       }
00350 
00351   template<typename _Tp, typename _Alloc>
00352     void
00353     list<_Tp, _Alloc>::
00354     sort()
00355     {
00356       // Do nothing if the list has length 0 or 1.
00357       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00358       && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00359       {
00360         list __carry;
00361         list __tmp[64];
00362         list * __fill = &__tmp[0];
00363         list * __counter;
00364 
00365         do
00366       {
00367         __carry.splice(__carry.begin(), *this, begin());
00368 
00369         for(__counter = &__tmp[0];
00370         __counter != __fill && !__counter->empty();
00371         ++__counter)
00372           {
00373         __counter->merge(__carry);
00374         __carry.swap(*__counter);
00375           }
00376         __carry.swap(*__counter);
00377         if (__counter == __fill)
00378           ++__fill;
00379       }
00380     while ( !empty() );
00381 
00382         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00383           __counter->merge(*(__counter - 1));
00384         swap( *(__fill - 1) );
00385       }
00386     }
00387 
00388   template<typename _Tp, typename _Alloc>
00389     template <typename _Predicate>
00390       void
00391       list<_Tp, _Alloc>::
00392       remove_if(_Predicate __pred)
00393       {
00394         iterator __first = begin();
00395         iterator __last = end();
00396         while (__first != __last)
00397       {
00398         iterator __next = __first;
00399         ++__next;
00400         if (__pred(*__first))
00401           _M_erase(__first);
00402         __first = __next;
00403       }
00404       }
00405 
00406   template<typename _Tp, typename _Alloc>
00407     template <typename _BinaryPredicate>
00408       void
00409       list<_Tp, _Alloc>::
00410       unique(_BinaryPredicate __binary_pred)
00411       {
00412         iterator __first = begin();
00413         iterator __last = end();
00414         if (__first == __last)
00415       return;
00416         iterator __next = __first;
00417         while (++__next != __last)
00418       {
00419         if (__binary_pred(*__first, *__next))
00420           _M_erase(__next);
00421         else
00422           __first = __next;
00423         __next = __first;
00424       }
00425       }
00426 
00427   template<typename _Tp, typename _Alloc>
00428     template <typename _StrictWeakOrdering>
00429       void
00430       list<_Tp, _Alloc>::
00431       sort(_StrictWeakOrdering __comp)
00432       {
00433     // Do nothing if the list has length 0 or 1.
00434     if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00435         && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00436       {
00437         list __carry;
00438         list __tmp[64];
00439         list * __fill = &__tmp[0];
00440         list * __counter;
00441 
00442         do
00443           {
00444         __carry.splice(__carry.begin(), *this, begin());
00445 
00446         for(__counter = &__tmp[0];
00447             __counter != __fill && !__counter->empty();
00448             ++__counter)
00449           {
00450             __counter->merge(__carry, __comp);
00451             __carry.swap(*__counter);
00452           }
00453         __carry.swap(*__counter);
00454         if (__counter == __fill)
00455           ++__fill;
00456           }
00457         while ( !empty() );
00458 
00459         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00460           __counter->merge(*(__counter - 1), __comp);
00461         swap(*(__fill - 1));
00462       }
00463       }
00464 
00465 _GLIBCXX_END_NAMESPACE_CONTAINER
00466 } // namespace std
00467 
00468 #endif /* _LIST_TCC */
00469