slist

Go to the documentation of this file.
00001 // Singly-linked list implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2004, 2005, 2007, 2008, 2009
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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  * Copyright (c) 1997
00028  * Silicon Graphics Computer Systems, Inc.
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.  Silicon Graphics 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 
00040 /** @file ext/slist
00041  *  This file is a GNU extension to the Standard C++ Library (possibly
00042  *  containing extensions from the HP/SGI STL subset). 
00043  */
00044 
00045 #ifndef _SLIST
00046 #define _SLIST 1
00047 
00048 #include <algorithm>
00049 #include <bits/allocator.h>
00050 #include <bits/stl_construct.h>
00051 #include <bits/stl_uninitialized.h>
00052 #include <bits/concept_check.h>
00053 
00054 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00055 
00056   using std::size_t;
00057   using std::ptrdiff_t;
00058   using std::_Construct;
00059   using std::_Destroy;
00060   using std::allocator;
00061   using std::__true_type;
00062   using std::__false_type;
00063 
00064   struct _Slist_node_base
00065   {
00066     _Slist_node_base* _M_next;
00067   };
00068   
00069   inline _Slist_node_base*
00070   __slist_make_link(_Slist_node_base* __prev_node,
00071             _Slist_node_base* __new_node)
00072   {
00073     __new_node->_M_next = __prev_node->_M_next;
00074     __prev_node->_M_next = __new_node;
00075     return __new_node;
00076   }
00077 
00078   inline _Slist_node_base*
00079   __slist_previous(_Slist_node_base* __head,
00080            const _Slist_node_base* __node)
00081   {
00082     while (__head && __head->_M_next != __node)
00083       __head = __head->_M_next;
00084     return __head;
00085   }
00086 
00087   inline const _Slist_node_base*
00088   __slist_previous(const _Slist_node_base* __head,
00089            const _Slist_node_base* __node)
00090   {
00091     while (__head && __head->_M_next != __node)
00092       __head = __head->_M_next;
00093     return __head;
00094   }
00095 
00096   inline void
00097   __slist_splice_after(_Slist_node_base* __pos,
00098                _Slist_node_base* __before_first,
00099                _Slist_node_base* __before_last)
00100   {
00101     if (__pos != __before_first && __pos != __before_last)
00102       {
00103     _Slist_node_base* __first = __before_first->_M_next;
00104     _Slist_node_base* __after = __pos->_M_next;
00105     __before_first->_M_next = __before_last->_M_next;
00106     __pos->_M_next = __first;
00107     __before_last->_M_next = __after;
00108       }
00109   }
00110 
00111   inline void
00112   __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
00113   {
00114     _Slist_node_base* __before_last = __slist_previous(__head, 0);
00115     if (__before_last != __head)
00116       {
00117     _Slist_node_base* __after = __pos->_M_next;
00118     __pos->_M_next = __head->_M_next;
00119     __head->_M_next = 0;
00120     __before_last->_M_next = __after;
00121       }
00122   }
00123 
00124   inline _Slist_node_base*
00125   __slist_reverse(_Slist_node_base* __node)
00126   {
00127     _Slist_node_base* __result = __node;
00128     __node = __node->_M_next;
00129     __result->_M_next = 0;
00130     while(__node)
00131       {
00132     _Slist_node_base* __next = __node->_M_next;
00133     __node->_M_next = __result;
00134     __result = __node;
00135     __node = __next;
00136       }
00137     return __result;
00138   }
00139 
00140   inline size_t
00141   __slist_size(_Slist_node_base* __node)
00142   {
00143     size_t __result = 0;
00144     for (; __node != 0; __node = __node->_M_next)
00145       ++__result;
00146     return __result;
00147   }
00148 
00149   template <class _Tp>
00150     struct _Slist_node : public _Slist_node_base
00151     {
00152       _Tp _M_data;
00153     };
00154 
00155   struct _Slist_iterator_base
00156   {
00157     typedef size_t                    size_type;
00158     typedef ptrdiff_t                 difference_type;
00159     typedef std::forward_iterator_tag iterator_category;
00160 
00161     _Slist_node_base* _M_node;
00162     
00163     _Slist_iterator_base(_Slist_node_base* __x)
00164     : _M_node(__x) {}
00165 
00166     void
00167     _M_incr()
00168     { _M_node = _M_node->_M_next; }
00169 
00170     bool
00171     operator==(const _Slist_iterator_base& __x) const
00172     { return _M_node == __x._M_node; }
00173 
00174     bool
00175     operator!=(const _Slist_iterator_base& __x) const
00176     { return _M_node != __x._M_node; }
00177   };
00178 
00179   template <class _Tp, class _Ref, class _Ptr>
00180     struct _Slist_iterator : public _Slist_iterator_base
00181     {
00182       typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
00183       typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00184       typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
00185 
00186       typedef _Tp              value_type;
00187       typedef _Ptr             pointer;
00188       typedef _Ref             reference;
00189       typedef _Slist_node<_Tp> _Node;
00190 
00191       explicit
00192       _Slist_iterator(_Node* __x)
00193       : _Slist_iterator_base(__x) {}
00194 
00195       _Slist_iterator()
00196       : _Slist_iterator_base(0) {}
00197 
00198       _Slist_iterator(const iterator& __x)
00199       : _Slist_iterator_base(__x._M_node) {}
00200 
00201       reference
00202       operator*() const
00203       { return ((_Node*) _M_node)->_M_data; }
00204 
00205       pointer
00206       operator->() const
00207       { return &(operator*()); }
00208 
00209       _Self&
00210       operator++()
00211       {
00212     _M_incr();
00213     return *this;
00214       }
00215 
00216       _Self
00217       operator++(int)
00218       {
00219     _Self __tmp = *this;
00220     _M_incr();
00221     return __tmp;
00222       }
00223     };
00224 
00225   template <class _Tp, class _Alloc>
00226     struct _Slist_base
00227     : public _Alloc::template rebind<_Slist_node<_Tp> >::other
00228     {
00229       typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other
00230         _Node_alloc;
00231       typedef _Alloc allocator_type;
00232 
00233       allocator_type
00234       get_allocator() const
00235       { return *static_cast<const _Node_alloc*>(this); }
00236 
00237       _Slist_base(const allocator_type& __a)
00238       : _Node_alloc(__a)
00239       { this->_M_head._M_next = 0; }
00240 
00241       ~_Slist_base()
00242       { _M_erase_after(&this->_M_head, 0); }
00243 
00244     protected:
00245       _Slist_node_base _M_head;
00246 
00247       _Slist_node<_Tp>*
00248       _M_get_node()
00249       { return _Node_alloc::allocate(1); }
00250   
00251       void
00252       _M_put_node(_Slist_node<_Tp>* __p)
00253       { _Node_alloc::deallocate(__p, 1); }
00254 
00255     protected:
00256       _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
00257       {
00258     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
00259     _Slist_node_base* __next_next = __next->_M_next;
00260     __pos->_M_next = __next_next;
00261     get_allocator().destroy(&__next->_M_data);
00262     _M_put_node(__next);
00263     return __next_next;
00264       }
00265       _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
00266     };
00267 
00268   template <class _Tp, class _Alloc>
00269     _Slist_node_base*
00270     _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
00271                         _Slist_node_base* __last_node)
00272     {
00273       _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
00274       while (__cur != __last_node)
00275     {
00276       _Slist_node<_Tp>* __tmp = __cur;
00277       __cur = (_Slist_node<_Tp>*) __cur->_M_next;
00278       get_allocator().destroy(&__tmp->_M_data);
00279       _M_put_node(__tmp);
00280     }
00281       __before_first->_M_next = __last_node;
00282       return __last_node;
00283     }
00284 
00285   /**
00286    *  This is an SGI extension.
00287    *  @ingroup SGIextensions
00288    *  @doctodo
00289    */
00290   template <class _Tp, class _Alloc = allocator<_Tp> >
00291     class slist : private _Slist_base<_Tp,_Alloc>
00292     {
00293       // concept requirements
00294       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00295     
00296     private:
00297       typedef _Slist_base<_Tp,_Alloc> _Base;
00298 
00299     public:
00300       typedef _Tp               value_type;
00301       typedef value_type*       pointer;
00302       typedef const value_type* const_pointer;
00303       typedef value_type&       reference;
00304       typedef const value_type& const_reference;
00305       typedef size_t            size_type;
00306       typedef ptrdiff_t         difference_type;
00307       
00308       typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
00309       typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00310       
00311       typedef typename _Base::allocator_type allocator_type;
00312 
00313       allocator_type
00314       get_allocator() const
00315       { return _Base::get_allocator(); }
00316 
00317     private:
00318       typedef _Slist_node<_Tp>      _Node;
00319       typedef _Slist_node_base      _Node_base;
00320       typedef _Slist_iterator_base  _Iterator_base;
00321       
00322       _Node*
00323       _M_create_node(const value_type& __x)
00324       {
00325     _Node* __node = this->_M_get_node();
00326     __try
00327       {
00328         get_allocator().construct(&__node->_M_data, __x);
00329         __node->_M_next = 0;
00330       }
00331     __catch(...)
00332       {
00333         this->_M_put_node(__node);
00334         __throw_exception_again;
00335       }
00336     return __node;
00337       }
00338 
00339       _Node*
00340       _M_create_node()
00341       {
00342     _Node* __node = this->_M_get_node();
00343     __try
00344       {
00345         get_allocator().construct(&__node->_M_data, value_type());
00346         __node->_M_next = 0;
00347       }
00348     __catch(...)
00349       {
00350         this->_M_put_node(__node);
00351         __throw_exception_again;
00352       }
00353     return __node;
00354       }
00355 
00356     public:
00357       explicit
00358       slist(const allocator_type& __a = allocator_type())
00359       : _Base(__a) {}
00360 
00361       slist(size_type __n, const value_type& __x,
00362         const allocator_type& __a =  allocator_type())
00363       : _Base(__a)
00364       { _M_insert_after_fill(&this->_M_head, __n, __x); }
00365 
00366       explicit
00367       slist(size_type __n)
00368       : _Base(allocator_type())
00369       { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
00370 
00371       // We don't need any dispatching tricks here, because
00372       // _M_insert_after_range already does them.
00373       template <class _InputIterator>
00374         slist(_InputIterator __first, _InputIterator __last,
00375           const allocator_type& __a =  allocator_type())
00376     : _Base(__a)
00377         { _M_insert_after_range(&this->_M_head, __first, __last); }
00378 
00379       slist(const slist& __x)
00380       : _Base(__x.get_allocator())
00381       { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
00382 
00383       slist&
00384       operator= (const slist& __x);
00385 
00386       ~slist() {}
00387 
00388     public:
00389       // assign(), a generalized assignment member function.  Two
00390       // versions: one that takes a count, and one that takes a range.
00391       // The range version is a member template, so we dispatch on whether
00392       // or not the type is an integer.
00393       
00394       void
00395       assign(size_type __n, const _Tp& __val)
00396       { _M_fill_assign(__n, __val); }
00397 
00398       void
00399       _M_fill_assign(size_type __n, const _Tp& __val);
00400 
00401       template <class _InputIterator>
00402         void
00403         assign(_InputIterator __first, _InputIterator __last)
00404         {
00405       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00406       _M_assign_dispatch(__first, __last, _Integral());
00407     }
00408 
00409       template <class _Integer>
00410       void
00411       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00412       { _M_fill_assign((size_type) __n, (_Tp) __val); }
00413 
00414       template <class _InputIterator>
00415       void
00416       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00417              __false_type);
00418 
00419     public:
00420 
00421       iterator
00422       begin()
00423       { return iterator((_Node*)this->_M_head._M_next); }
00424 
00425       const_iterator
00426       begin() const
00427       { return const_iterator((_Node*)this->_M_head._M_next);}
00428 
00429       iterator
00430       end()
00431       { return iterator(0); }
00432 
00433       const_iterator
00434       end() const
00435       { return const_iterator(0); }
00436 
00437       // Experimental new feature: before_begin() returns a
00438       // non-dereferenceable iterator that, when incremented, yields
00439       // begin().  This iterator may be used as the argument to
00440       // insert_after, erase_after, etc.  Note that even for an empty
00441       // slist, before_begin() is not the same iterator as end().  It
00442       // is always necessary to increment before_begin() at least once to
00443       // obtain end().
00444       iterator
00445       before_begin()
00446       { return iterator((_Node*) &this->_M_head); }
00447 
00448       const_iterator
00449       before_begin() const
00450       { return const_iterator((_Node*) &this->_M_head); }
00451 
00452       size_type
00453       size() const
00454       { return __slist_size(this->_M_head._M_next); }
00455 
00456       size_type
00457       max_size() const
00458       { return size_type(-1); }
00459 
00460       bool
00461       empty() const
00462       { return this->_M_head._M_next == 0; }
00463 
00464       void
00465       swap(slist& __x)
00466       { std::swap(this->_M_head._M_next, __x._M_head._M_next); }
00467 
00468     public:
00469 
00470       reference
00471       front()
00472       { return ((_Node*) this->_M_head._M_next)->_M_data; }
00473 
00474       const_reference
00475       front() const
00476       { return ((_Node*) this->_M_head._M_next)->_M_data; }
00477 
00478       void
00479       push_front(const value_type& __x)
00480       { __slist_make_link(&this->_M_head, _M_create_node(__x)); }
00481 
00482       void
00483       push_front()
00484       { __slist_make_link(&this->_M_head, _M_create_node()); }
00485 
00486       void
00487       pop_front()
00488       {
00489     _Node* __node = (_Node*) this->_M_head._M_next;
00490     this->_M_head._M_next = __node->_M_next;
00491     get_allocator().destroy(&__node->_M_data);
00492     this->_M_put_node(__node);
00493       }
00494 
00495       iterator
00496       previous(const_iterator __pos)
00497       { return iterator((_Node*) __slist_previous(&this->_M_head,
00498                           __pos._M_node)); }
00499 
00500       const_iterator
00501       previous(const_iterator __pos) const
00502       { return const_iterator((_Node*) __slist_previous(&this->_M_head,
00503                             __pos._M_node)); }
00504 
00505     private:
00506       _Node*
00507       _M_insert_after(_Node_base* __pos, const value_type& __x)
00508       { return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); }
00509 
00510       _Node*
00511       _M_insert_after(_Node_base* __pos)
00512       { return (_Node*) (__slist_make_link(__pos, _M_create_node())); }
00513 
00514       void
00515       _M_insert_after_fill(_Node_base* __pos,
00516                size_type __n, const value_type& __x)
00517       {
00518     for (size_type __i = 0; __i < __n; ++__i)
00519       __pos = __slist_make_link(__pos, _M_create_node(__x));
00520       }
00521 
00522       // Check whether it's an integral type.  If so, it's not an iterator.
00523       template <class _InIterator>
00524         void
00525         _M_insert_after_range(_Node_base* __pos,
00526                   _InIterator __first, _InIterator __last)
00527         {
00528       typedef typename std::__is_integer<_InIterator>::__type _Integral;
00529       _M_insert_after_range(__pos, __first, __last, _Integral());
00530     }
00531 
00532       template <class _Integer>
00533         void
00534         _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
00535                   __true_type)
00536         { _M_insert_after_fill(__pos, __n, __x); }
00537 
00538       template <class _InIterator>
00539         void
00540         _M_insert_after_range(_Node_base* __pos,
00541                   _InIterator __first, _InIterator __last,
00542                   __false_type)
00543         {
00544       while (__first != __last)
00545         {
00546           __pos = __slist_make_link(__pos, _M_create_node(*__first));
00547           ++__first;
00548         }
00549     }
00550 
00551     public:
00552       iterator
00553       insert_after(iterator __pos, const value_type& __x)
00554       { return iterator(_M_insert_after(__pos._M_node, __x)); }
00555 
00556       iterator
00557       insert_after(iterator __pos)
00558       { return insert_after(__pos, value_type()); }
00559 
00560       void
00561       insert_after(iterator __pos, size_type __n, const value_type& __x)
00562       { _M_insert_after_fill(__pos._M_node, __n, __x); }
00563 
00564       // We don't need any dispatching tricks here, because
00565       // _M_insert_after_range already does them.
00566       template <class _InIterator>
00567         void
00568         insert_after(iterator __pos, _InIterator __first, _InIterator __last)
00569         { _M_insert_after_range(__pos._M_node, __first, __last); }
00570 
00571       iterator
00572       insert(iterator __pos, const value_type& __x)
00573       { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
00574                              __pos._M_node),
00575                     __x)); }
00576 
00577       iterator
00578       insert(iterator __pos)
00579       { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
00580                              __pos._M_node),
00581                     value_type())); }
00582 
00583       void
00584       insert(iterator __pos, size_type __n, const value_type& __x)
00585       { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
00586                  __n, __x); }
00587 
00588       // We don't need any dispatching tricks here, because
00589       // _M_insert_after_range already does them.
00590       template <class _InIterator>
00591         void
00592         insert(iterator __pos, _InIterator __first, _InIterator __last)
00593         { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node),
00594                 __first, __last); }
00595 
00596     public:
00597       iterator
00598       erase_after(iterator __pos)
00599       { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); }
00600 
00601       iterator
00602       erase_after(iterator __before_first, iterator __last)
00603       { 
00604     return iterator((_Node*) this->_M_erase_after(__before_first._M_node,
00605                               __last._M_node));
00606       }
00607 
00608       iterator
00609       erase(iterator __pos)
00610       { 
00611     return iterator((_Node*) this->_M_erase_after
00612             (__slist_previous(&this->_M_head, __pos._M_node)));
00613       }
00614 
00615       iterator
00616       erase(iterator __first, iterator __last)
00617       { 
00618     return iterator((_Node*) this->_M_erase_after
00619             (__slist_previous(&this->_M_head, __first._M_node),
00620              __last._M_node));
00621       }
00622       
00623       void
00624       resize(size_type new_size, const _Tp& __x);
00625 
00626       void
00627       resize(size_type new_size)
00628       { resize(new_size, _Tp()); }
00629 
00630       void
00631       clear()
00632       { this->_M_erase_after(&this->_M_head, 0); }
00633 
00634     public:
00635       // Moves the range [__before_first + 1, __before_last + 1) to *this,
00636       //  inserting it immediately after __pos.  This is constant time.
00637       void
00638       splice_after(iterator __pos,
00639            iterator __before_first, iterator __before_last)
00640       {
00641     if (__before_first != __before_last)
00642       __slist_splice_after(__pos._M_node, __before_first._M_node,
00643                    __before_last._M_node);
00644       }
00645 
00646       // Moves the element that follows __prev to *this, inserting it
00647       // immediately after __pos.  This is constant time.
00648       void
00649       splice_after(iterator __pos, iterator __prev)
00650       { __slist_splice_after(__pos._M_node,
00651                  __prev._M_node, __prev._M_node->_M_next); }
00652 
00653       // Removes all of the elements from the list __x to *this, inserting
00654       // them immediately after __pos.  __x must not be *this.  Complexity:
00655       // linear in __x.size().
00656       void
00657       splice_after(iterator __pos, slist& __x)
00658       { __slist_splice_after(__pos._M_node, &__x._M_head); }
00659 
00660       // Linear in distance(begin(), __pos), and linear in __x.size().
00661       void
00662       splice(iterator __pos, slist& __x)
00663       {
00664     if (__x._M_head._M_next)
00665       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
00666                    &__x._M_head,
00667                    __slist_previous(&__x._M_head, 0)); }
00668 
00669       // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
00670       void
00671       splice(iterator __pos, slist& __x, iterator __i)
00672       { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
00673                  __slist_previous(&__x._M_head, __i._M_node),
00674                  __i._M_node); }
00675 
00676       // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
00677       // and in distance(__first, __last).
00678       void
00679       splice(iterator __pos, slist& __x, iterator __first, iterator __last)
00680       {
00681     if (__first != __last)
00682       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
00683                    __slist_previous(&__x._M_head, __first._M_node),
00684                    __slist_previous(__first._M_node,
00685                         __last._M_node));
00686       }
00687 
00688     public:
00689       void
00690       reverse()
00691       {
00692     if (this->_M_head._M_next)
00693       this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
00694       }
00695 
00696       void
00697       remove(const _Tp& __val);
00698 
00699       void
00700       unique();
00701       
00702       void
00703       merge(slist& __x);
00704       
00705       void
00706       sort();
00707 
00708       template <class _Predicate>
00709         void
00710         remove_if(_Predicate __pred);
00711 
00712       template <class _BinaryPredicate>
00713         void
00714         unique(_BinaryPredicate __pred);
00715 
00716       template <class _StrictWeakOrdering>
00717         void
00718         merge(slist&, _StrictWeakOrdering);
00719 
00720       template <class _StrictWeakOrdering>
00721         void
00722         sort(_StrictWeakOrdering __comp);
00723     };
00724 
00725   template <class _Tp, class _Alloc>
00726     slist<_Tp, _Alloc>&
00727     slist<_Tp, _Alloc>::operator=(const slist<_Tp, _Alloc>& __x)
00728     {
00729       if (&__x != this)
00730     {
00731       _Node_base* __p1 = &this->_M_head;
00732       _Node* __n1 = (_Node*) this->_M_head._M_next;
00733       const _Node* __n2 = (const _Node*) __x._M_head._M_next;
00734       while (__n1 && __n2)
00735         {
00736           __n1->_M_data = __n2->_M_data;
00737           __p1 = __n1;
00738           __n1 = (_Node*) __n1->_M_next;
00739           __n2 = (const _Node*) __n2->_M_next;
00740         }
00741       if (__n2 == 0)
00742         this->_M_erase_after(__p1, 0);
00743       else
00744         _M_insert_after_range(__p1, const_iterator((_Node*)__n2),
00745                                   const_iterator(0));
00746     }
00747       return *this;
00748     }
00749 
00750   template <class _Tp, class _Alloc>
00751     void
00752     slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val)
00753     {
00754       _Node_base* __prev = &this->_M_head;
00755       _Node* __node = (_Node*) this->_M_head._M_next;
00756       for (; __node != 0 && __n > 0; --__n)
00757     {
00758       __node->_M_data = __val;
00759       __prev = __node;
00760       __node = (_Node*) __node->_M_next;
00761     }
00762       if (__n > 0)
00763     _M_insert_after_fill(__prev, __n, __val);
00764       else
00765     this->_M_erase_after(__prev, 0);
00766     }
00767   
00768   template <class _Tp, class _Alloc>
00769     template <class _InputIterator>
00770       void
00771       slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first,
00772                          _InputIterator __last,
00773                          __false_type)
00774       {
00775     _Node_base* __prev = &this->_M_head;
00776     _Node* __node = (_Node*) this->_M_head._M_next;
00777     while (__node != 0 && __first != __last)
00778       {
00779         __node->_M_data = *__first;
00780         __prev = __node;
00781         __node = (_Node*) __node->_M_next;
00782         ++__first;
00783       }
00784     if (__first != __last)
00785       _M_insert_after_range(__prev, __first, __last);
00786     else
00787       this->_M_erase_after(__prev, 0);
00788       }
00789   
00790   template <class _Tp, class _Alloc>
00791     inline bool
00792     operator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
00793     {
00794       typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
00795       const_iterator __end1 = _SL1.end();
00796       const_iterator __end2 = _SL2.end();
00797       
00798       const_iterator __i1 = _SL1.begin();
00799       const_iterator __i2 = _SL2.begin();
00800       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
00801     {
00802       ++__i1;
00803       ++__i2;
00804     }
00805       return __i1 == __end1 && __i2 == __end2;
00806     }
00807 
00808 
00809   template <class _Tp, class _Alloc>
00810     inline bool
00811     operator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
00812     { return std::lexicographical_compare(_SL1.begin(), _SL1.end(),
00813                       _SL2.begin(), _SL2.end()); }
00814 
00815   template <class _Tp, class _Alloc>
00816     inline bool
00817     operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
00818     { return !(_SL1 == _SL2); }
00819 
00820   template <class _Tp, class _Alloc>
00821     inline bool
00822     operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
00823     { return _SL2 < _SL1; }
00824 
00825   template <class _Tp, class _Alloc>
00826     inline bool
00827     operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
00828     { return !(_SL2 < _SL1); }
00829 
00830   template <class _Tp, class _Alloc>
00831     inline bool
00832     operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
00833     { return !(_SL1 < _SL2); }
00834 
00835   template <class _Tp, class _Alloc>
00836     inline void
00837     swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y)
00838     { __x.swap(__y); }
00839 
00840   template <class _Tp, class _Alloc>
00841     void
00842     slist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x)
00843     {
00844       _Node_base* __cur = &this->_M_head;
00845       while (__cur->_M_next != 0 && __len > 0)
00846     {
00847       --__len;
00848       __cur = __cur->_M_next;
00849     }
00850       if (__cur->_M_next)
00851     this->_M_erase_after(__cur, 0);
00852       else
00853     _M_insert_after_fill(__cur, __len, __x);
00854     }
00855 
00856   template <class _Tp, class _Alloc>
00857     void
00858     slist<_Tp, _Alloc>::remove(const _Tp& __val)
00859     { 
00860       _Node_base* __cur = &this->_M_head;
00861       while (__cur && __cur->_M_next)
00862     {
00863       if (((_Node*) __cur->_M_next)->_M_data == __val)
00864         this->_M_erase_after(__cur);
00865       else
00866         __cur = __cur->_M_next;
00867     }
00868     }
00869 
00870   template <class _Tp, class _Alloc>
00871     void
00872     slist<_Tp, _Alloc>::unique()
00873     {
00874       _Node_base* __cur = this->_M_head._M_next;
00875       if (__cur)
00876     {
00877       while (__cur->_M_next)
00878         {
00879           if (((_Node*)__cur)->_M_data
00880           == ((_Node*)(__cur->_M_next))->_M_data)
00881         this->_M_erase_after(__cur);
00882           else
00883         __cur = __cur->_M_next;
00884         }
00885     }
00886     }
00887 
00888   template <class _Tp, class _Alloc>
00889     void
00890     slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x)
00891     {
00892       _Node_base* __n1 = &this->_M_head;
00893       while (__n1->_M_next && __x._M_head._M_next)
00894     {
00895       if (((_Node*) __x._M_head._M_next)->_M_data
00896           < ((_Node*) __n1->_M_next)->_M_data)
00897         __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
00898       __n1 = __n1->_M_next;
00899     }
00900       if (__x._M_head._M_next)
00901     {
00902       __n1->_M_next = __x._M_head._M_next;
00903       __x._M_head._M_next = 0;
00904     }
00905     }
00906 
00907   template <class _Tp, class _Alloc>
00908     void
00909     slist<_Tp, _Alloc>::sort()
00910     {
00911       if (this->_M_head._M_next && this->_M_head._M_next->_M_next)
00912     {
00913       slist __carry;
00914       slist __counter[64];
00915       int __fill = 0;
00916       while (!empty())
00917         {
00918           __slist_splice_after(&__carry._M_head,
00919                    &this->_M_head, this->_M_head._M_next);
00920           int __i = 0;
00921           while (__i < __fill && !__counter[__i].empty())
00922         {
00923           __counter[__i].merge(__carry);
00924           __carry.swap(__counter[__i]);
00925           ++__i;
00926         }
00927           __carry.swap(__counter[__i]);
00928           if (__i == __fill)
00929         ++__fill;
00930         }
00931       
00932       for (int __i = 1; __i < __fill; ++__i)
00933         __counter[__i].merge(__counter[__i-1]);
00934       this->swap(__counter[__fill-1]);
00935     }
00936     }
00937 
00938   template <class _Tp, class _Alloc>
00939     template <class _Predicate>
00940       void slist<_Tp, _Alloc>::remove_if(_Predicate __pred)
00941       {
00942     _Node_base* __cur = &this->_M_head;
00943     while (__cur->_M_next)
00944       {
00945         if (__pred(((_Node*) __cur->_M_next)->_M_data))
00946           this->_M_erase_after(__cur);
00947         else
00948           __cur = __cur->_M_next;
00949       }
00950       }
00951 
00952   template <class _Tp, class _Alloc>
00953     template <class _BinaryPredicate>
00954       void
00955       slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred)
00956       {
00957     _Node* __cur = (_Node*) this->_M_head._M_next;
00958     if (__cur)
00959       {
00960         while (__cur->_M_next)
00961           {
00962         if (__pred(((_Node*)__cur)->_M_data,
00963                ((_Node*)(__cur->_M_next))->_M_data))
00964           this->_M_erase_after(__cur);
00965         else
00966           __cur = (_Node*) __cur->_M_next;
00967           }
00968       }
00969       }
00970 
00971   template <class _Tp, class _Alloc>
00972     template <class _StrictWeakOrdering>
00973       void
00974       slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x,
00975                    _StrictWeakOrdering __comp)
00976       {
00977     _Node_base* __n1 = &this->_M_head;
00978     while (__n1->_M_next && __x._M_head._M_next)
00979       {
00980         if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
00981                ((_Node*) __n1->_M_next)->_M_data))
00982           __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
00983         __n1 = __n1->_M_next;
00984       }
00985     if (__x._M_head._M_next)
00986       {
00987         __n1->_M_next = __x._M_head._M_next;
00988         __x._M_head._M_next = 0;
00989       }
00990       }
00991 
00992   template <class _Tp, class _Alloc>
00993     template <class _StrictWeakOrdering>
00994       void
00995       slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
00996       {
00997     if (this->_M_head._M_next && this->_M_head._M_next->_M_next)
00998       {
00999         slist __carry;
01000         slist __counter[64];
01001         int __fill = 0;
01002         while (!empty())
01003           {
01004         __slist_splice_after(&__carry._M_head,
01005                      &this->_M_head, this->_M_head._M_next);
01006         int __i = 0;
01007         while (__i < __fill && !__counter[__i].empty())
01008           {
01009             __counter[__i].merge(__carry, __comp);
01010             __carry.swap(__counter[__i]);
01011             ++__i;
01012           }
01013         __carry.swap(__counter[__i]);
01014         if (__i == __fill)
01015           ++__fill;
01016           }
01017 
01018         for (int __i = 1; __i < __fill; ++__i)
01019           __counter[__i].merge(__counter[__i-1], __comp);
01020         this->swap(__counter[__fill-1]);
01021       }
01022       }
01023 
01024 _GLIBCXX_END_NAMESPACE
01025 
01026 _GLIBCXX_BEGIN_NAMESPACE(std)
01027 
01028   // Specialization of insert_iterator so that insertions will be constant
01029   // time rather than linear time.
01030   template <class _Tp, class _Alloc>
01031     class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> >
01032     {
01033     protected:
01034       typedef __gnu_cxx::slist<_Tp, _Alloc> _Container;
01035       _Container* container;
01036       typename _Container::iterator iter;
01037 
01038     public:
01039       typedef _Container          container_type;
01040       typedef output_iterator_tag iterator_category;
01041       typedef void                value_type;
01042       typedef void                difference_type;
01043       typedef void                pointer;
01044       typedef void                reference;
01045 
01046       insert_iterator(_Container& __x, typename _Container::iterator __i)
01047       : container(&__x)
01048       {
01049     if (__i == __x.begin())
01050       iter = __x.before_begin();
01051     else
01052       iter = __x.previous(__i);
01053       }
01054 
01055       insert_iterator<_Container>&
01056       operator=(const typename _Container::value_type& __value)
01057       {
01058     iter = container->insert_after(iter, __value);
01059     return *this;
01060       }
01061 
01062       insert_iterator<_Container>&
01063       operator*()
01064       { return *this; }
01065 
01066       insert_iterator<_Container>&
01067       operator++()
01068       { return *this; }
01069 
01070       insert_iterator<_Container>&
01071       operator++(int)
01072       { return *this; }
01073     };
01074 
01075 _GLIBCXX_END_NAMESPACE
01076 
01077 #endif

Generated on Thu Jul 23 21:16:17 2009 for libstdc++ by  doxygen 1.5.8