list.tcc

Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 2, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /*
00032  *
00033  * Copyright (c) 1994
00034  * Hewlett-Packard Company
00035  *
00036  * Permission to use, copy, modify, distribute and sell this software
00037  * and its documentation for any purpose is hereby granted without fee,
00038  * provided that the above copyright notice appear in all copies and
00039  * that both that copyright notice and this permission notice appear
00040  * in supporting documentation.  Hewlett-Packard Company makes no
00041  * representations about the suitability of this software for any
00042  * purpose.  It is provided "as is" without express or implied warranty.
00043  *
00044  *
00045  * Copyright (c) 1996,1997
00046  * Silicon Graphics Computer Systems, Inc.
00047  *
00048  * Permission to use, copy, modify, distribute and sell this software
00049  * and its documentation for any purpose is hereby granted without fee,
00050  * provided that the above copyright notice appear in all copies and
00051  * that both that copyright notice and this permission notice appear
00052  * in supporting documentation.  Silicon Graphics makes no
00053  * representations about the suitability of this software for any
00054  * purpose.  It is provided "as is" without express or implied warranty.
00055  */
00056 
00057 /** @file list.tcc
00058  *  This is an internal header file, included by other library headers.
00059  *  You should not attempt to use it directly.
00060  */
00061 
00062 #ifndef _LIST_TCC
00063 #define _LIST_TCC 1
00064 
00065 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00066 
00067   template<typename _Tp, typename _Alloc>
00068     void
00069     _List_base<_Tp, _Alloc>::
00070     _M_clear()
00071     {
00072       typedef _List_node<_Tp>  _Node;
00073       _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
00074       while (__cur != &this->_M_impl._M_node)
00075     {
00076       _Node* __tmp = __cur;
00077       __cur = static_cast<_Node*>(__cur->_M_next);
00078       _M_get_Tp_allocator().destroy(&__tmp->_M_data);
00079       _M_put_node(__tmp);
00080     }
00081     }
00082 
00083 #ifdef __GXX_EXPERIMENTAL_CXX0X__
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->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->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   template<typename _Tp, typename _Alloc>
00117     void
00118     list<_Tp, _Alloc>::
00119     resize(size_type __new_size, value_type __x)
00120     {
00121       iterator __i = begin();
00122       size_type __len = 0;
00123       for (; __i != end() && __len < __new_size; ++__i, ++__len)
00124         ;
00125       if (__len == __new_size)
00126         erase(__i, end());
00127       else                          // __i == end()
00128         insert(end(), __new_size - __len, __x);
00129     }
00130 
00131   template<typename _Tp, typename _Alloc>
00132     list<_Tp, _Alloc>&
00133     list<_Tp, _Alloc>::
00134     operator=(const list& __x)
00135     {
00136       if (this != &__x)
00137     {
00138       iterator __first1 = begin();
00139       iterator __last1 = end();
00140       const_iterator __first2 = __x.begin();
00141       const_iterator __last2 = __x.end();
00142       for (; __first1 != __last1 && __first2 != __last2;
00143            ++__first1, ++__first2)
00144         *__first1 = *__first2;
00145       if (__first2 == __last2)
00146         erase(__first1, __last1);
00147       else
00148         insert(__last1, __first2, __last2);
00149     }
00150       return *this;
00151     }
00152 
00153   template<typename _Tp, typename _Alloc>
00154     void
00155     list<_Tp, _Alloc>::
00156     _M_fill_assign(size_type __n, const value_type& __val)
00157     {
00158       iterator __i = begin();
00159       for (; __i != end() && __n > 0; ++__i, --__n)
00160         *__i = __val;
00161       if (__n > 0)
00162         insert(end(), __n, __val);
00163       else
00164         erase(__i, end());
00165     }
00166 
00167   template<typename _Tp, typename _Alloc>
00168     template <typename _InputIterator>
00169       void
00170       list<_Tp, _Alloc>::
00171       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
00172              __false_type)
00173       {
00174         iterator __first1 = begin();
00175         iterator __last1 = end();
00176         for (; __first1 != __last1 && __first2 != __last2;
00177          ++__first1, ++__first2)
00178           *__first1 = *__first2;
00179         if (__first2 == __last2)
00180           erase(__first1, __last1);
00181         else
00182           insert(__last1, __first2, __last2);
00183       }
00184 
00185   template<typename _Tp, typename _Alloc>
00186     void
00187     list<_Tp, _Alloc>::
00188     remove(const value_type& __value)
00189     {
00190       iterator __first = begin();
00191       iterator __last = end();
00192       iterator __extra = __last;
00193       while (__first != __last)
00194     {
00195       iterator __next = __first;
00196       ++__next;
00197       if (*__first == __value)
00198         {
00199           // _GLIBCXX_RESOLVE_LIB_DEFECTS
00200           // 526. Is it undefined if a function in the standard changes
00201           // in parameters?
00202           if (&*__first != &__value)
00203         _M_erase(__first);
00204           else
00205         __extra = __first;
00206         }
00207       __first = __next;
00208     }
00209       if (__extra != __last)
00210     _M_erase(__extra);
00211     }
00212 
00213   template<typename _Tp, typename _Alloc>
00214     void
00215     list<_Tp, _Alloc>::
00216     unique()
00217     {
00218       iterator __first = begin();
00219       iterator __last = end();
00220       if (__first == __last)
00221     return;
00222       iterator __next = __first;
00223       while (++__next != __last)
00224     {
00225       if (*__first == *__next)
00226         _M_erase(__next);
00227       else
00228         __first = __next;
00229       __next = __first;
00230     }
00231     }
00232 
00233   template<typename _Tp, typename _Alloc>
00234     void
00235     list<_Tp, _Alloc>::
00236 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00237     merge(list&& __x)
00238 #else
00239     merge(list& __x)
00240 #endif
00241     {
00242       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00243       // 300. list::merge() specification incomplete
00244       if (this != &__x)
00245     {
00246       _M_check_equal_allocators(__x); 
00247 
00248       iterator __first1 = begin();
00249       iterator __last1 = end();
00250       iterator __first2 = __x.begin();
00251       iterator __last2 = __x.end();
00252       while (__first1 != __last1 && __first2 != __last2)
00253         if (*__first2 < *__first1)
00254           {
00255         iterator __next = __first2;
00256         _M_transfer(__first1, __first2, ++__next);
00257         __first2 = __next;
00258           }
00259         else
00260           ++__first1;
00261       if (__first2 != __last2)
00262         _M_transfer(__last1, __first2, __last2);
00263     }
00264     }
00265 
00266   template<typename _Tp, typename _Alloc>
00267     template <typename _StrictWeakOrdering>
00268       void
00269       list<_Tp, _Alloc>::
00270 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00271       merge(list&& __x, _StrictWeakOrdering __comp)
00272 #else
00273       merge(list& __x, _StrictWeakOrdering __comp)
00274 #endif
00275       {
00276     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00277     // 300. list::merge() specification incomplete
00278     if (this != &__x)
00279       {
00280         _M_check_equal_allocators(__x);
00281 
00282         iterator __first1 = begin();
00283         iterator __last1 = end();
00284         iterator __first2 = __x.begin();
00285         iterator __last2 = __x.end();
00286         while (__first1 != __last1 && __first2 != __last2)
00287           if (__comp(*__first2, *__first1))
00288         {
00289           iterator __next = __first2;
00290           _M_transfer(__first1, __first2, ++__next);
00291           __first2 = __next;
00292         }
00293           else
00294         ++__first1;
00295         if (__first2 != __last2)
00296           _M_transfer(__last1, __first2, __last2);
00297       }
00298       }
00299 
00300   template<typename _Tp, typename _Alloc>
00301     void
00302     list<_Tp, _Alloc>::
00303     sort()
00304     {
00305       // Do nothing if the list has length 0 or 1.
00306       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00307       && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00308       {
00309         list __carry;
00310         list __tmp[64];
00311         list * __fill = &__tmp[0];
00312         list * __counter;
00313 
00314         do
00315       {
00316         __carry.splice(__carry.begin(), *this, begin());
00317 
00318         for(__counter = &__tmp[0];
00319         __counter != __fill && !__counter->empty();
00320         ++__counter)
00321           {
00322         __counter->merge(__carry);
00323         __carry.swap(*__counter);
00324           }
00325         __carry.swap(*__counter);
00326         if (__counter == __fill)
00327           ++__fill;
00328       }
00329     while ( !empty() );
00330 
00331         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00332           __counter->merge(*(__counter - 1));
00333         swap( *(__fill - 1) );
00334       }
00335     }
00336 
00337   template<typename _Tp, typename _Alloc>
00338     template <typename _Predicate>
00339       void
00340       list<_Tp, _Alloc>::
00341       remove_if(_Predicate __pred)
00342       {
00343         iterator __first = begin();
00344         iterator __last = end();
00345         while (__first != __last)
00346       {
00347         iterator __next = __first;
00348         ++__next;
00349         if (__pred(*__first))
00350           _M_erase(__first);
00351         __first = __next;
00352       }
00353       }
00354 
00355   template<typename _Tp, typename _Alloc>
00356     template <typename _BinaryPredicate>
00357       void
00358       list<_Tp, _Alloc>::
00359       unique(_BinaryPredicate __binary_pred)
00360       {
00361         iterator __first = begin();
00362         iterator __last = end();
00363         if (__first == __last)
00364       return;
00365         iterator __next = __first;
00366         while (++__next != __last)
00367       {
00368         if (__binary_pred(*__first, *__next))
00369           _M_erase(__next);
00370         else
00371           __first = __next;
00372         __next = __first;
00373       }
00374       }
00375 
00376   template<typename _Tp, typename _Alloc>
00377     template <typename _StrictWeakOrdering>
00378       void
00379       list<_Tp, _Alloc>::
00380       sort(_StrictWeakOrdering __comp)
00381       {
00382     // Do nothing if the list has length 0 or 1.
00383     if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00384         && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00385       {
00386         list __carry;
00387         list __tmp[64];
00388         list * __fill = &__tmp[0];
00389         list * __counter;
00390 
00391         do
00392           {
00393         __carry.splice(__carry.begin(), *this, begin());
00394 
00395         for(__counter = &__tmp[0];
00396             __counter != __fill && !__counter->empty();
00397             ++__counter)
00398           {
00399             __counter->merge(__carry, __comp);
00400             __carry.swap(*__counter);
00401           }
00402         __carry.swap(*__counter);
00403         if (__counter == __fill)
00404           ++__fill;
00405           }
00406         while ( !empty() );
00407 
00408         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00409           __counter->merge(*(__counter - 1), __comp);
00410         swap(*(__fill - 1));
00411       }
00412       }
00413 
00414 _GLIBCXX_END_NESTED_NAMESPACE
00415 
00416 #endif /* _LIST_TCC */
00417 

Generated on Wed Dec 31 12:48:56 2008 for libstdc++ by  doxygen 1.5.6