# 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