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