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
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)
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   template<typename _Tp, typename _Alloc>
00084     typename list<_Tp, _Alloc>::iterator
00085     list<_Tp, _Alloc>::
00086     insert(iterator __position, const value_type& __x)
00087     {
00088       _Node* __tmp = _M_create_node(__x);
00089       __tmp->hook(__position._M_node);
00090       return iterator(__tmp);
00091     }
00092 
00093   template<typename _Tp, typename _Alloc>
00094     typename list<_Tp, _Alloc>::iterator
00095     list<_Tp, _Alloc>::
00096     erase(iterator __position)
00097     {
00098       iterator __ret = iterator(__position._M_node->_M_next);
00099       _M_erase(__position);
00100       return __ret;
00101     }
00102 
00103   template<typename _Tp, typename _Alloc>
00104     void
00105     list<_Tp, _Alloc>::
00106     resize(size_type __new_size, value_type __x)
00107     {
00108       iterator __i = begin();
00109       size_type __len = 0;
00110       for (; __i != end() && __len < __new_size; ++__i, ++__len)
00111         ;
00112       if (__len == __new_size)
00113         erase(__i, end());
00114       else                          // __i == end()
00115         insert(end(), __new_size - __len, __x);
00116     }
00117 
00118   template<typename _Tp, typename _Alloc>
00119     list<_Tp, _Alloc>&
00120     list<_Tp, _Alloc>::
00121     operator=(const list& __x)
00122     {
00123       if (this != &__x)
00124     {
00125       iterator __first1 = begin();
00126       iterator __last1 = end();
00127       const_iterator __first2 = __x.begin();
00128       const_iterator __last2 = __x.end();
00129       for (; __first1 != __last1 && __first2 != __last2;
00130            ++__first1, ++__first2)
00131         *__first1 = *__first2;
00132       if (__first2 == __last2)
00133         erase(__first1, __last1);
00134       else
00135         insert(__last1, __first2, __last2);
00136     }
00137       return *this;
00138     }
00139 
00140   template<typename _Tp, typename _Alloc>
00141     void
00142     list<_Tp, _Alloc>::
00143     _M_fill_assign(size_type __n, const value_type& __val)
00144     {
00145       iterator __i = begin();
00146       for (; __i != end() && __n > 0; ++__i, --__n)
00147         *__i = __val;
00148       if (__n > 0)
00149         insert(end(), __n, __val);
00150       else
00151         erase(__i, end());
00152     }
00153 
00154   template<typename _Tp, typename _Alloc>
00155     template <typename _InputIterator>
00156       void
00157       list<_Tp, _Alloc>::
00158       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
00159              __false_type)
00160       {
00161         iterator __first1 = begin();
00162         iterator __last1 = end();
00163         for (; __first1 != __last1 && __first2 != __last2;
00164          ++__first1, ++__first2)
00165           *__first1 = *__first2;
00166         if (__first2 == __last2)
00167           erase(__first1, __last1);
00168         else
00169           insert(__last1, __first2, __last2);
00170       }
00171 
00172   template<typename _Tp, typename _Alloc>
00173     void
00174     list<_Tp, _Alloc>::
00175     remove(const value_type& __value)
00176     {
00177       iterator __first = begin();
00178       iterator __last = end();
00179       while (__first != __last)
00180     {
00181       iterator __next = __first;
00182       ++__next;
00183       if (*__first == __value)
00184         _M_erase(__first);
00185       __first = __next;
00186     }
00187     }
00188 
00189   template<typename _Tp, typename _Alloc>
00190     void
00191     list<_Tp, _Alloc>::
00192     unique()
00193     {
00194       iterator __first = begin();
00195       iterator __last = end();
00196       if (__first == __last)
00197     return;
00198       iterator __next = __first;
00199       while (++__next != __last)
00200     {
00201       if (*__first == *__next)
00202         _M_erase(__next);
00203       else
00204         __first = __next;
00205       __next = __first;
00206     }
00207     }
00208 
00209   template<typename _Tp, typename _Alloc>
00210     void
00211     list<_Tp, _Alloc>::
00212     merge(list& __x)
00213     {
00214       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00215       // 300. list::merge() specification incomplete
00216       if (this != &__x)
00217     {
00218       _M_check_equal_allocators(__x); 
00219 
00220       iterator __first1 = begin();
00221       iterator __last1 = end();
00222       iterator __first2 = __x.begin();
00223       iterator __last2 = __x.end();
00224       while (__first1 != __last1 && __first2 != __last2)
00225         if (*__first2 < *__first1)
00226           {
00227         iterator __next = __first2;
00228         _M_transfer(__first1, __first2, ++__next);
00229         __first2 = __next;
00230           }
00231         else
00232           ++__first1;
00233       if (__first2 != __last2)
00234         _M_transfer(__last1, __first2, __last2);
00235     }
00236     }
00237 
00238   template<typename _Tp, typename _Alloc>
00239     template <typename _StrictWeakOrdering>
00240       void
00241       list<_Tp, _Alloc>::
00242       merge(list& __x, _StrictWeakOrdering __comp)
00243       {
00244     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00245     // 300. list::merge() specification incomplete
00246     if (this != &__x)
00247       {
00248         _M_check_equal_allocators(__x);
00249 
00250         iterator __first1 = begin();
00251         iterator __last1 = end();
00252         iterator __first2 = __x.begin();
00253         iterator __last2 = __x.end();
00254         while (__first1 != __last1 && __first2 != __last2)
00255           if (__comp(*__first2, *__first1))
00256         {
00257           iterator __next = __first2;
00258           _M_transfer(__first1, __first2, ++__next);
00259           __first2 = __next;
00260         }
00261           else
00262         ++__first1;
00263         if (__first2 != __last2)
00264           _M_transfer(__last1, __first2, __last2);
00265       }
00266       }
00267 
00268   template<typename _Tp, typename _Alloc>
00269     void
00270     list<_Tp, _Alloc>::
00271     sort()
00272     {
00273       // Do nothing if the list has length 0 or 1.
00274       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00275       && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00276       {
00277         list __carry;
00278         list __tmp[64];
00279         list * __fill = &__tmp[0];
00280         list * __counter;
00281 
00282         do
00283       {
00284         __carry.splice(__carry.begin(), *this, begin());
00285 
00286         for(__counter = &__tmp[0];
00287         __counter != __fill && !__counter->empty();
00288         ++__counter)
00289           {
00290         __counter->merge(__carry);
00291         __carry.swap(*__counter);
00292           }
00293         __carry.swap(*__counter);
00294         if (__counter == __fill)
00295           ++__fill;
00296       }
00297     while ( !empty() );
00298 
00299         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00300           __counter->merge(*(__counter - 1));
00301         swap( *(__fill - 1) );
00302       }
00303     }
00304 
00305   template<typename _Tp, typename _Alloc>
00306     template <typename _Predicate>
00307       void
00308       list<_Tp, _Alloc>::
00309       remove_if(_Predicate __pred)
00310       {
00311         iterator __first = begin();
00312         iterator __last = end();
00313         while (__first != __last)
00314       {
00315         iterator __next = __first;
00316         ++__next;
00317         if (__pred(*__first))
00318           _M_erase(__first);
00319         __first = __next;
00320       }
00321       }
00322 
00323   template<typename _Tp, typename _Alloc>
00324     template <typename _BinaryPredicate>
00325       void
00326       list<_Tp, _Alloc>::
00327       unique(_BinaryPredicate __binary_pred)
00328       {
00329         iterator __first = begin();
00330         iterator __last = end();
00331         if (__first == __last)
00332       return;
00333         iterator __next = __first;
00334         while (++__next != __last)
00335       {
00336         if (__binary_pred(*__first, *__next))
00337           _M_erase(__next);
00338         else
00339           __first = __next;
00340         __next = __first;
00341       }
00342       }
00343 
00344   template<typename _Tp, typename _Alloc>
00345     template <typename _StrictWeakOrdering>
00346       void
00347       list<_Tp, _Alloc>::
00348       sort(_StrictWeakOrdering __comp)
00349       {
00350     // Do nothing if the list has length 0 or 1.
00351     if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00352         && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00353       {
00354         list __carry;
00355         list __tmp[64];
00356         list * __fill = &__tmp[0];
00357         list * __counter;
00358 
00359         do
00360           {
00361         __carry.splice(__carry.begin(), *this, begin());
00362 
00363         for(__counter = &__tmp[0];
00364             __counter != __fill && !__counter->empty();
00365             ++__counter)
00366           {
00367             __counter->merge(__carry, __comp);
00368             __carry.swap(*__counter);
00369           }
00370         __carry.swap(*__counter);
00371         if (__counter == __fill)
00372           ++__fill;
00373           }
00374         while ( !empty() );
00375 
00376         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00377           __counter->merge(*(__counter - 1), __comp);
00378         swap(*(__fill - 1));
00379       }
00380       }
00381 
00382 _GLIBCXX_END_NESTED_NAMESPACE
00383 
00384 #endif /* _LIST_TCC */
00385 

Generated on Thu Nov 1 13:12:03 2007 for libstdc++ by  doxygen 1.5.1