Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

slist

Go to the documentation of this file.
00001 // Singly-linked list implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  * Copyright (c) 1997
00032  * Silicon Graphics Computer Systems, Inc.
00033  *
00034  * Permission to use, copy, modify, distribute and sell this software
00035  * and its documentation for any purpose is hereby granted without fee,
00036  * provided that the above copyright notice appear in all copies and
00037  * that both that copyright notice and this permission notice appear
00038  * in supporting documentation.  Silicon Graphics makes no
00039  * representations about the suitability of this software for any
00040  * purpose.  It is provided "as is" without express or implied warranty.
00041  *
00042  */
00043 
00044 /* NOTE: This is an internal header file, included by other STL headers.
00045  *   You should not attempt to use it directly.
00046  */
00047 
00048 #ifndef __SGI_STL_INTERNAL_SLIST_H
00049 #define __SGI_STL_INTERNAL_SLIST_H
00050 
00051 #include <bits/stl_algobase.h>
00052 #include <bits/stl_alloc.h>
00053 #include <bits/stl_construct.h>
00054 #include <bits/stl_uninitialized.h>
00055 #include <bits/concept_check.h>
00056 
00057 namespace std
00058 { 
00059 
00060 struct _Slist_node_base
00061 {
00062   _Slist_node_base* _M_next;
00063 };
00064 
00065 inline _Slist_node_base*
00066 __slist_make_link(_Slist_node_base* __prev_node,
00067                   _Slist_node_base* __new_node)
00068 {
00069   __new_node->_M_next = __prev_node->_M_next;
00070   __prev_node->_M_next = __new_node;
00071   return __new_node;
00072 }
00073 
00074 inline _Slist_node_base* 
00075 __slist_previous(_Slist_node_base* __head,
00076                  const _Slist_node_base* __node)
00077 {
00078   while (__head && __head->_M_next != __node)
00079     __head = __head->_M_next;
00080   return __head;
00081 }
00082 
00083 inline const _Slist_node_base* 
00084 __slist_previous(const _Slist_node_base* __head,
00085                  const _Slist_node_base* __node)
00086 {
00087   while (__head && __head->_M_next != __node)
00088     __head = __head->_M_next;
00089   return __head;
00090 }
00091 
00092 inline void __slist_splice_after(_Slist_node_base* __pos,
00093                                  _Slist_node_base* __before_first,
00094                                  _Slist_node_base* __before_last)
00095 {
00096   if (__pos != __before_first && __pos != __before_last) {
00097     _Slist_node_base* __first = __before_first->_M_next;
00098     _Slist_node_base* __after = __pos->_M_next;
00099     __before_first->_M_next = __before_last->_M_next;
00100     __pos->_M_next = __first;
00101     __before_last->_M_next = __after;
00102   }
00103 }
00104 
00105 inline void
00106 __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
00107 {
00108   _Slist_node_base* __before_last = __slist_previous(__head, 0);
00109   if (__before_last != __head) {
00110     _Slist_node_base* __after = __pos->_M_next;
00111     __pos->_M_next = __head->_M_next;
00112     __head->_M_next = 0;
00113     __before_last->_M_next = __after;
00114   }
00115 }
00116 
00117 inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node)
00118 {
00119   _Slist_node_base* __result = __node;
00120   __node = __node->_M_next;
00121   __result->_M_next = 0;
00122   while(__node) {
00123     _Slist_node_base* __next = __node->_M_next;
00124     __node->_M_next = __result;
00125     __result = __node;
00126     __node = __next;
00127   }
00128   return __result;
00129 }
00130 
00131 inline size_t __slist_size(_Slist_node_base* __node)
00132 {
00133   size_t __result = 0;
00134   for ( ; __node != 0; __node = __node->_M_next)
00135     ++__result;
00136   return __result;
00137 }
00138 
00139 template <class _Tp>
00140 struct _Slist_node : public _Slist_node_base
00141 {
00142   _Tp _M_data;
00143 };
00144 
00145 struct _Slist_iterator_base
00146 {
00147   typedef size_t               size_type;
00148   typedef ptrdiff_t            difference_type;
00149   typedef forward_iterator_tag iterator_category;
00150 
00151   _Slist_node_base* _M_node;
00152 
00153   _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
00154   void _M_incr() { _M_node = _M_node->_M_next; }
00155 
00156   bool operator==(const _Slist_iterator_base& __x) const {
00157     return _M_node == __x._M_node;
00158   }
00159   bool operator!=(const _Slist_iterator_base& __x) const {
00160     return _M_node != __x._M_node;
00161   }
00162 };
00163 
00164 template <class _Tp, class _Ref, class _Ptr>
00165 struct _Slist_iterator : public _Slist_iterator_base
00166 {
00167   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
00168   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00169   typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
00170 
00171   typedef _Tp              value_type;
00172   typedef _Ptr             pointer;
00173   typedef _Ref             reference;
00174   typedef _Slist_node<_Tp> _Node;
00175 
00176   _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
00177   _Slist_iterator() : _Slist_iterator_base(0) {}
00178   _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
00179 
00180   reference operator*() const { return ((_Node*) _M_node)->_M_data; }
00181   pointer operator->() const { return &(operator*()); }
00182 
00183   _Self& operator++()
00184   {
00185     _M_incr();
00186     return *this;
00187   }
00188   _Self operator++(int)
00189   {
00190     _Self __tmp = *this;
00191     _M_incr();
00192     return __tmp;
00193   }
00194 };
00195 
00196 
00197 // Base class that encapsulates details of allocators.  Three cases:
00198 // an ordinary standard-conforming allocator, a standard-conforming
00199 // allocator with no non-static data, and an SGI-style allocator.
00200 // This complexity is necessary only because we're worrying about backward
00201 // compatibility and because we want to avoid wasting storage on an 
00202 // allocator instance if it isn't necessary.
00203 
00204 // Base for general standard-conforming allocators.
00205 template <class _Tp, class _Allocator, bool _IsStatic>
00206 class _Slist_alloc_base {
00207 public:
00208   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
00209           allocator_type;
00210   allocator_type get_allocator() const { return _M_node_allocator; }
00211 
00212   _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {}
00213 
00214 protected:
00215   _Slist_node<_Tp>* _M_get_node() 
00216     { return _M_node_allocator.allocate(1); }
00217   void _M_put_node(_Slist_node<_Tp>* __p) 
00218     { _M_node_allocator.deallocate(__p, 1); }
00219 
00220 protected:
00221   typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type
00222            _M_node_allocator;
00223   _Slist_node_base _M_head;
00224 };
00225 
00226 // Specialization for instanceless allocators.
00227 template <class _Tp, class _Allocator>
00228 class _Slist_alloc_base<_Tp,_Allocator, true> {
00229 public:
00230   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
00231           allocator_type;
00232   allocator_type get_allocator() const { return allocator_type(); }
00233 
00234   _Slist_alloc_base(const allocator_type&) {}
00235 
00236 protected:
00237   typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type
00238           _Alloc_type;
00239   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
00240   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
00241 
00242 protected:
00243   _Slist_node_base _M_head;
00244 };
00245 
00246 
00247 template <class _Tp, class _Alloc>
00248 struct _Slist_base
00249   : public _Slist_alloc_base<_Tp, _Alloc,
00250                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00251 {
00252   typedef _Slist_alloc_base<_Tp, _Alloc,
00253                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00254           _Base;
00255   typedef typename _Base::allocator_type allocator_type;
00256 
00257   _Slist_base(const allocator_type& __a)
00258     : _Base(__a) { this->_M_head._M_next = 0; }
00259   ~_Slist_base() { _M_erase_after(&this->_M_head, 0); }
00260 
00261 protected:
00262 
00263   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
00264   {
00265     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
00266     _Slist_node_base* __next_next = __next->_M_next;
00267     __pos->_M_next = __next_next;
00268     destroy(&__next->_M_data);
00269     _M_put_node(__next);
00270     return __next_next;
00271   }
00272   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
00273 };
00274 
00275 template <class _Tp, class _Alloc> 
00276 _Slist_node_base*
00277 _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
00278                                         _Slist_node_base* __last_node) {
00279   _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
00280   while (__cur != __last_node) {
00281     _Slist_node<_Tp>* __tmp = __cur;
00282     __cur = (_Slist_node<_Tp>*) __cur->_M_next;
00283     destroy(&__tmp->_M_data);
00284     _M_put_node(__tmp);
00285   }
00286   __before_first->_M_next = __last_node;
00287   return __last_node;
00288 }
00289 
00290 template <class _Tp, class _Alloc = allocator<_Tp> >
00291 class slist : private _Slist_base<_Tp,_Alloc>
00292 {
00293   // concept requirements
00294   __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
00295 
00296 private:
00297   typedef _Slist_base<_Tp,_Alloc> _Base;
00298 public:
00299   typedef _Tp                value_type;
00300   typedef value_type*       pointer;
00301   typedef const value_type* const_pointer;
00302   typedef value_type&       reference;
00303   typedef const value_type& const_reference;
00304   typedef size_t            size_type;
00305   typedef ptrdiff_t         difference_type;
00306 
00307   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
00308   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00309 
00310   typedef typename _Base::allocator_type allocator_type;
00311   allocator_type get_allocator() const { return _Base::get_allocator(); }
00312 
00313 private:
00314   typedef _Slist_node<_Tp>      _Node;
00315   typedef _Slist_node_base      _Node_base;
00316   typedef _Slist_iterator_base  _Iterator_base;
00317 
00318   _Node* _M_create_node(const value_type& __x) {
00319     _Node* __node = this->_M_get_node();
00320     __STL_TRY {
00321       construct(&__node->_M_data, __x);
00322       __node->_M_next = 0;
00323     }
00324     __STL_UNWIND(this->_M_put_node(__node));
00325     return __node;
00326   }
00327   
00328   _Node* _M_create_node() {
00329     _Node* __node = this->_M_get_node();
00330     __STL_TRY {
00331       construct(&__node->_M_data);
00332       __node->_M_next = 0;
00333     }
00334     __STL_UNWIND(this->_M_put_node(__node));
00335     return __node;
00336   }
00337 
00338 public:
00339   explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}
00340 
00341   slist(size_type __n, const value_type& __x,
00342         const allocator_type& __a =  allocator_type()) : _Base(__a)
00343     { _M_insert_after_fill(&this->_M_head, __n, __x); }
00344 
00345   explicit slist(size_type __n) : _Base(allocator_type())
00346     { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
00347 
00348   // We don't need any dispatching tricks here, because _M_insert_after_range
00349   // already does them.
00350   template <class _InputIterator>
00351   slist(_InputIterator __first, _InputIterator __last,
00352         const allocator_type& __a =  allocator_type()) : _Base(__a)
00353     { _M_insert_after_range(&this->_M_head, __first, __last); }
00354 
00355   slist(const slist& __x) : _Base(__x.get_allocator())
00356     { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
00357 
00358   slist& operator= (const slist& __x);
00359 
00360   ~slist() {}
00361 
00362 public:
00363   // assign(), a generalized assignment member function.  Two
00364   // versions: one that takes a count, and one that takes a range.
00365   // The range version is a member template, so we dispatch on whether
00366   // or not the type is an integer.
00367 
00368   void assign(size_type __n, const _Tp& __val)
00369     { _M_fill_assign(__n, __val); }
00370 
00371   void _M_fill_assign(size_type __n, const _Tp& __val);
00372 
00373   template <class _InputIterator>
00374   void assign(_InputIterator __first, _InputIterator __last) {
00375     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00376     _M_assign_dispatch(__first, __last, _Integral());
00377   }
00378 
00379   template <class _Integer>
00380   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00381     { _M_fill_assign((size_type) __n, (_Tp) __val); }
00382 
00383   template <class _InputIterator>
00384   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00385                           __false_type);
00386 
00387 public:
00388 
00389   iterator begin() { return iterator((_Node*)this->_M_head._M_next); }
00390   const_iterator begin() const 
00391     { return const_iterator((_Node*)this->_M_head._M_next);}
00392 
00393   iterator end() { return iterator(0); }
00394   const_iterator end() const { return const_iterator(0); }
00395 
00396   // Experimental new feature: before_begin() returns a
00397   // non-dereferenceable iterator that, when incremented, yields
00398   // begin().  This iterator may be used as the argument to
00399   // insert_after, erase_after, etc.  Note that even for an empty 
00400   // slist, before_begin() is not the same iterator as end().  It 
00401   // is always necessary to increment before_begin() at least once to
00402   // obtain end().
00403   iterator before_begin() { return iterator((_Node*) &this->_M_head); }
00404   const_iterator before_begin() const
00405     { return const_iterator((_Node*) &this->_M_head); }
00406 
00407   size_type size() const { return __slist_size(this->_M_head._M_next); }
00408   
00409   size_type max_size() const { return size_type(-1); }
00410 
00411   bool empty() const { return this->_M_head._M_next == 0; }
00412 
00413   void swap(slist& __x)
00414     { std::swap(this->_M_head._M_next, __x._M_head._M_next); }
00415 
00416 public:
00417 
00418   reference front() { return ((_Node*) this->_M_head._M_next)->_M_data; }
00419   const_reference front() const 
00420     { return ((_Node*) this->_M_head._M_next)->_M_data; }
00421   void push_front(const value_type& __x)   {
00422     __slist_make_link(&this->_M_head, _M_create_node(__x));
00423   }
00424   void push_front() { __slist_make_link(&this->_M_head, _M_create_node()); }
00425   void pop_front() {
00426     _Node* __node = (_Node*) this->_M_head._M_next;
00427     this->_M_head._M_next = __node->_M_next;
00428     destroy(&__node->_M_data);
00429     this->_M_put_node(__node);
00430   }
00431 
00432   iterator previous(const_iterator __pos) {
00433     return iterator((_Node*) __slist_previous(&this->_M_head, __pos._M_node));
00434   }
00435   const_iterator previous(const_iterator __pos) const {
00436     return const_iterator((_Node*) __slist_previous(&this->_M_head,
00437                                                     __pos._M_node));
00438   }
00439 
00440 private:
00441   _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
00442     return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
00443   }
00444 
00445   _Node* _M_insert_after(_Node_base* __pos) {
00446     return (_Node*) (__slist_make_link(__pos, _M_create_node()));
00447   }
00448 
00449   void _M_insert_after_fill(_Node_base* __pos,
00450                             size_type __n, const value_type& __x) {
00451     for (size_type __i = 0; __i < __n; ++__i)
00452       __pos = __slist_make_link(__pos, _M_create_node(__x));
00453   }
00454 
00455   // Check whether it's an integral type.  If so, it's not an iterator.
00456   template <class _InIter>
00457   void _M_insert_after_range(_Node_base* __pos, 
00458                              _InIter __first, _InIter __last) {
00459     typedef typename _Is_integer<_InIter>::_Integral _Integral;
00460     _M_insert_after_range(__pos, __first, __last, _Integral());
00461   }
00462 
00463   template <class _Integer>
00464   void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
00465                              __true_type) {
00466     _M_insert_after_fill(__pos, __n, __x);
00467   }
00468 
00469   template <class _InIter>
00470   void _M_insert_after_range(_Node_base* __pos,
00471                              _InIter __first, _InIter __last,
00472                              __false_type) {
00473     while (__first != __last) {
00474       __pos = __slist_make_link(__pos, _M_create_node(*__first));
00475       ++__first;
00476     }
00477   }
00478 
00479 public:
00480 
00481   iterator insert_after(iterator __pos, const value_type& __x) {
00482     return iterator(_M_insert_after(__pos._M_node, __x));
00483   }
00484 
00485   iterator insert_after(iterator __pos) {
00486     return insert_after(__pos, value_type());
00487   }
00488 
00489   void insert_after(iterator __pos, size_type __n, const value_type& __x) {
00490     _M_insert_after_fill(__pos._M_node, __n, __x);
00491   }
00492 
00493   // We don't need any dispatching tricks here, because _M_insert_after_range
00494   // already does them.
00495   template <class _InIter>
00496   void insert_after(iterator __pos, _InIter __first, _InIter __last) {
00497     _M_insert_after_range(__pos._M_node, __first, __last);
00498   }
00499 
00500   iterator insert(iterator __pos, const value_type& __x) {
00501     return iterator(_M_insert_after(__slist_previous(&this->_M_head,
00502                                                      __pos._M_node),
00503                     __x));
00504   }
00505 
00506   iterator insert(iterator __pos) {
00507     return iterator(_M_insert_after(__slist_previous(&this->_M_head,
00508                                                      __pos._M_node),
00509                                     value_type()));
00510   }
00511 
00512   void insert(iterator __pos, size_type __n, const value_type& __x) {
00513     _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
00514                          __n, __x);
00515   } 
00516     
00517   // We don't need any dispatching tricks here, because _M_insert_after_range
00518   // already does them.
00519   template <class _InIter>
00520   void insert(iterator __pos, _InIter __first, _InIter __last) {
00521     _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 
00522                           __first, __last);
00523   }
00524 
00525 public:
00526   iterator erase_after(iterator __pos) {
00527     return iterator((_Node*) this->_M_erase_after(__pos._M_node));
00528   }
00529   iterator erase_after(iterator __before_first, iterator __last) {
00530     return iterator((_Node*) this->_M_erase_after(__before_first._M_node, 
00531                                                   __last._M_node));
00532   } 
00533 
00534   iterator erase(iterator __pos) {
00535     return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head, 
00536                                                           __pos._M_node));
00537   }
00538   iterator erase(iterator __first, iterator __last) {
00539     return (_Node*) this->_M_erase_after(
00540       __slist_previous(&this->_M_head, __first._M_node), __last._M_node);
00541   }
00542 
00543   void resize(size_type new_size, const _Tp& __x);
00544   void resize(size_type new_size) { resize(new_size, _Tp()); }
00545   void clear() { this->_M_erase_after(&this->_M_head, 0); }
00546 
00547 public:
00548   // Moves the range [__before_first + 1, __before_last + 1) to *this,
00549   //  inserting it immediately after __pos.  This is constant time.
00550   void splice_after(iterator __pos, 
00551                     iterator __before_first, iterator __before_last)
00552   {
00553     if (__before_first != __before_last) 
00554       __slist_splice_after(__pos._M_node, __before_first._M_node, 
00555                            __before_last._M_node);
00556   }
00557 
00558   // Moves the element that follows __prev to *this, inserting it immediately
00559   //  after __pos.  This is constant time.
00560   void splice_after(iterator __pos, iterator __prev)
00561   {
00562     __slist_splice_after(__pos._M_node,
00563                          __prev._M_node, __prev._M_node->_M_next);
00564   }
00565 
00566 
00567   // Removes all of the elements from the list __x to *this, inserting
00568   // them immediately after __pos.  __x must not be *this.  Complexity:
00569   // linear in __x.size().
00570   void splice_after(iterator __pos, slist& __x)
00571   {
00572     __slist_splice_after(__pos._M_node, &__x._M_head);
00573   }
00574 
00575   // Linear in distance(begin(), __pos), and linear in __x.size().
00576   void splice(iterator __pos, slist& __x) {
00577     if (__x._M_head._M_next)
00578       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
00579                            &__x._M_head, __slist_previous(&__x._M_head, 0));
00580   }
00581 
00582   // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
00583   void splice(iterator __pos, slist& __x, iterator __i) {
00584     __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
00585                          __slist_previous(&__x._M_head, __i._M_node),
00586                          __i._M_node);
00587   }
00588 
00589   // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
00590   // and in distance(__first, __last).
00591   void splice(iterator __pos, slist& __x, iterator __first, iterator __last)
00592   {
00593     if (__first != __last)
00594       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
00595                            __slist_previous(&__x._M_head, __first._M_node),
00596                            __slist_previous(__first._M_node, __last._M_node));
00597   }
00598 
00599 public:
00600   void reverse() { 
00601     if (this->_M_head._M_next)
00602       this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
00603   }
00604 
00605   void remove(const _Tp& __val); 
00606   void unique(); 
00607   void merge(slist& __x);
00608   void sort();     
00609 
00610   template <class _Predicate> 
00611   void remove_if(_Predicate __pred);
00612 
00613   template <class _BinaryPredicate> 
00614   void unique(_BinaryPredicate __pred); 
00615 
00616   template <class _StrictWeakOrdering> 
00617   void merge(slist&, _StrictWeakOrdering);
00618 
00619   template <class _StrictWeakOrdering> 
00620   void sort(_StrictWeakOrdering __comp); 
00621 };
00622 
00623 template <class _Tp, class _Alloc>
00624 slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x)
00625 {
00626   if (&__x != this) {
00627     _Node_base* __p1 = &this->_M_head;
00628     _Node* __n1 = (_Node*) this->_M_head._M_next;
00629     const _Node* __n2 = (const _Node*) __x._M_head._M_next;
00630     while (__n1 && __n2) {
00631       __n1->_M_data = __n2->_M_data;
00632       __p1 = __n1;
00633       __n1 = (_Node*) __n1->_M_next;
00634       __n2 = (const _Node*) __n2->_M_next;
00635     }
00636     if (__n2 == 0)
00637       this->_M_erase_after(__p1, 0);
00638     else
00639       _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 
00640                                   const_iterator(0));
00641   }
00642   return *this;
00643 }
00644 
00645 template <class _Tp, class _Alloc>
00646 void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
00647   _Node_base* __prev = &this->_M_head;
00648   _Node* __node = (_Node*) this->_M_head._M_next;
00649   for ( ; __node != 0 && __n > 0 ; --__n) {
00650     __node->_M_data = __val;
00651     __prev = __node;
00652     __node = (_Node*) __node->_M_next;
00653   }
00654   if (__n > 0)
00655     _M_insert_after_fill(__prev, __n, __val);
00656   else
00657     this->_M_erase_after(__prev, 0);
00658 }
00659 
00660 template <class _Tp, class _Alloc> template <class _InputIter>
00661 void
00662 slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last,
00663                                        __false_type)
00664 {
00665   _Node_base* __prev = &this->_M_head;
00666   _Node* __node = (_Node*) this->_M_head._M_next;
00667   while (__node != 0 && __first != __last) {
00668     __node->_M_data = *__first;
00669     __prev = __node;
00670     __node = (_Node*) __node->_M_next;
00671     ++__first;
00672   }
00673   if (__first != __last)
00674     _M_insert_after_range(__prev, __first, __last);
00675   else
00676     this->_M_erase_after(__prev, 0);
00677 }
00678 
00679 template <class _Tp, class _Alloc>
00680 inline bool 
00681 operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
00682 {
00683   typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
00684   const_iterator __end1 = _SL1.end();
00685   const_iterator __end2 = _SL2.end();
00686 
00687   const_iterator __i1 = _SL1.begin();
00688   const_iterator __i2 = _SL2.begin();
00689   while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
00690     ++__i1;
00691     ++__i2;
00692   }
00693   return __i1 == __end1 && __i2 == __end2;
00694 }
00695 
00696 
00697 template <class _Tp, class _Alloc>
00698 inline bool
00699 operator<(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
00700 {
00701   return lexicographical_compare(_SL1.begin(), _SL1.end(), 
00702                                  _SL2.begin(), _SL2.end());
00703 }
00704 
00705 template <class _Tp, class _Alloc>
00706 inline bool 
00707 operator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
00708   return !(_SL1 == _SL2);
00709 }
00710 
00711 template <class _Tp, class _Alloc>
00712 inline bool 
00713 operator>(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
00714   return _SL2 < _SL1;
00715 }
00716 
00717 template <class _Tp, class _Alloc>
00718 inline bool 
00719 operator<=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
00720   return !(_SL2 < _SL1);
00721 }
00722 
00723 template <class _Tp, class _Alloc>
00724 inline bool 
00725 operator>=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
00726   return !(_SL1 < _SL2);
00727 }
00728 
00729 template <class _Tp, class _Alloc>
00730 inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) {
00731   __x.swap(__y);
00732 }
00733 
00734 
00735 template <class _Tp, class _Alloc>
00736 void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x)
00737 {
00738   _Node_base* __cur = &this->_M_head;
00739   while (__cur->_M_next != 0 && __len > 0) {
00740     --__len;
00741     __cur = __cur->_M_next;
00742   }
00743   if (__cur->_M_next) 
00744     this->_M_erase_after(__cur, 0);
00745   else
00746     _M_insert_after_fill(__cur, __len, __x);
00747 }
00748 
00749 template <class _Tp, class _Alloc>
00750 void slist<_Tp,_Alloc>::remove(const _Tp& __val)
00751 {
00752   _Node_base* __cur = &this->_M_head;
00753   while (__cur && __cur->_M_next) {
00754     if (((_Node*) __cur->_M_next)->_M_data == __val)
00755       this->_M_erase_after(__cur);
00756     else
00757       __cur = __cur->_M_next;
00758   }
00759 }
00760 
00761 template <class _Tp, class _Alloc> 
00762 void slist<_Tp,_Alloc>::unique()
00763 {
00764   _Node_base* __cur = this->_M_head._M_next;
00765   if (__cur) {
00766     while (__cur->_M_next) {
00767       if (((_Node*)__cur)->_M_data == 
00768           ((_Node*)(__cur->_M_next))->_M_data)
00769         this->_M_erase_after(__cur);
00770       else
00771         __cur = __cur->_M_next;
00772     }
00773   }
00774 }
00775 
00776 template <class _Tp, class _Alloc>
00777 void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x)
00778 {
00779   _Node_base* __n1 = &this->_M_head;
00780   while (__n1->_M_next && __x._M_head._M_next) {
00781     if (((_Node*) __x._M_head._M_next)->_M_data < 
00782         ((_Node*)       __n1->_M_next)->_M_data) 
00783       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
00784     __n1 = __n1->_M_next;
00785   }
00786   if (__x._M_head._M_next) {
00787     __n1->_M_next = __x._M_head._M_next;
00788     __x._M_head._M_next = 0;
00789   }
00790 }
00791 
00792 template <class _Tp, class _Alloc>
00793 void slist<_Tp,_Alloc>::sort()
00794 {
00795   if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
00796     slist __carry;
00797     slist __counter[64];
00798     int __fill = 0;
00799     while (!empty()) {
00800       __slist_splice_after(&__carry._M_head,
00801                            &this->_M_head, this->_M_head._M_next);
00802       int __i = 0;
00803       while (__i < __fill && !__counter[__i].empty()) {
00804         __counter[__i].merge(__carry);
00805         __carry.swap(__counter[__i]);
00806         ++__i;
00807       }
00808       __carry.swap(__counter[__i]);
00809       if (__i == __fill)
00810         ++__fill;
00811     }
00812 
00813     for (int __i = 1; __i < __fill; ++__i)
00814       __counter[__i].merge(__counter[__i-1]);
00815     this->swap(__counter[__fill-1]);
00816   }
00817 }
00818 
00819 template <class _Tp, class _Alloc> 
00820 template <class _Predicate>
00821 void slist<_Tp,_Alloc>::remove_if(_Predicate __pred)
00822 {
00823   _Node_base* __cur = &this->_M_head;
00824   while (__cur->_M_next) {
00825     if (__pred(((_Node*) __cur->_M_next)->_M_data))
00826       this->_M_erase_after(__cur);
00827     else
00828       __cur = __cur->_M_next;
00829   }
00830 }
00831 
00832 template <class _Tp, class _Alloc> template <class _BinaryPredicate> 
00833 void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred)
00834 {
00835   _Node* __cur = (_Node*) this->_M_head._M_next;
00836   if (__cur) {
00837     while (__cur->_M_next) {
00838       if (__pred(((_Node*)__cur)->_M_data, 
00839                  ((_Node*)(__cur->_M_next))->_M_data))
00840         this->_M_erase_after(__cur);
00841       else
00842         __cur = (_Node*) __cur->_M_next;
00843     }
00844   }
00845 }
00846 
00847 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
00848 void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x,
00849                               _StrictWeakOrdering __comp)
00850 {
00851   _Node_base* __n1 = &this->_M_head;
00852   while (__n1->_M_next && __x._M_head._M_next) {
00853     if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
00854                ((_Node*)       __n1->_M_next)->_M_data))
00855       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
00856     __n1 = __n1->_M_next;
00857   }
00858   if (__x._M_head._M_next) {
00859     __n1->_M_next = __x._M_head._M_next;
00860     __x._M_head._M_next = 0;
00861   }
00862 }
00863 
00864 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> 
00865 void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp)
00866 {
00867   if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
00868     slist __carry;
00869     slist __counter[64];
00870     int __fill = 0;
00871     while (!empty()) {
00872       __slist_splice_after(&__carry._M_head,
00873                            &this->_M_head, this->_M_head._M_next);
00874       int __i = 0;
00875       while (__i < __fill && !__counter[__i].empty()) {
00876         __counter[__i].merge(__carry, __comp);
00877         __carry.swap(__counter[__i]);
00878         ++__i;
00879       }
00880       __carry.swap(__counter[__i]);
00881       if (__i == __fill)
00882         ++__fill;
00883     }
00884 
00885     for (int __i = 1; __i < __fill; ++__i)
00886       __counter[__i].merge(__counter[__i-1], __comp);
00887     this->swap(__counter[__fill-1]);
00888   }
00889 }
00890 
00891 // Specialization of insert_iterator so that insertions will be constant
00892 // time rather than linear time.
00893 
00894 template <class _Tp, class _Alloc>
00895 class insert_iterator<slist<_Tp, _Alloc> > {
00896 protected:
00897   typedef slist<_Tp, _Alloc> _Container;
00898   _Container* container;
00899   typename _Container::iterator iter;
00900 public:
00901   typedef _Container          container_type;
00902   typedef output_iterator_tag iterator_category;
00903   typedef void                value_type;
00904   typedef void                difference_type;
00905   typedef void                pointer;
00906   typedef void                reference;
00907 
00908   insert_iterator(_Container& __x, typename _Container::iterator __i) 
00909     : container(&__x) {
00910     if (__i == __x.begin())
00911       iter = __x.before_begin();
00912     else
00913       iter = __x.previous(__i);
00914   }
00915 
00916   insert_iterator<_Container>&
00917   operator=(const typename _Container::value_type& __value) { 
00918     iter = container->insert_after(iter, __value);
00919     return *this;
00920   }
00921   insert_iterator<_Container>& operator*() { return *this; }
00922   insert_iterator<_Container>& operator++() { return *this; }
00923   insert_iterator<_Container>& operator++(int) { return *this; }
00924 };
00925 
00926 } // namespace std 
00927 
00928 #endif /* __SGI_STL_INTERNAL_SLIST_H */
00929 
00930 // Local Variables:
00931 // mode:C++
00932 // End:

Generated on Mon Apr 8 03:11:32 2002 for libstdc++-v3 Source by doxygen1.2.15