home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _slist.h < prev    next >
C/C++ Source or Header  |  2002-02-02  |  25KB  |  778 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1996,1997
  4.  * Silicon Graphics Computer Systems, Inc.
  5.  *
  6.  * Copyright (c) 1997
  7.  * Moscow Center for SPARC Technology
  8.  *
  9.  * Copyright (c) 1999 
  10.  * Boris Fomitchev
  11.  *
  12.  * This material is provided "as is", with absolutely no warranty expressed
  13.  * or implied. Any use is at your own risk.
  14.  *
  15.  * Permission to use or copy this software for any purpose is hereby granted 
  16.  * without fee, provided the above notices are retained on all copies.
  17.  * Permission to modify the code and to distribute modified code is granted,
  18.  * provided the above notices are retained, and a notice that the code was
  19.  * modified is included with the above copyright notice.
  20.  *
  21.  */
  22.  
  23. /* NOTE: This is an internal header file, included by other STL headers.
  24.  *   You should not attempt to use it directly.
  25.  */
  26.  
  27. #ifndef _STLP_INTERNAL_SLIST_H
  28. #define _STLP_INTERNAL_SLIST_H
  29.  
  30.  
  31. # ifndef _STLP_INTERNAL_ALGOBASE_H
  32. #  include <stl/_algobase.h>
  33. # endif
  34.  
  35. # ifndef _STLP_INTERNAL_ALLOC_H
  36. #  include <stl/_alloc.h>
  37. # endif
  38.  
  39. # ifndef _STLP_INTERNAL_ITERATOR_H
  40. #  include <stl/_iterator.h>
  41. # endif
  42.  
  43. # ifndef _STLP_INTERNAL_CONSTRUCT_H
  44. #  include <stl/_construct.h>
  45. # endif
  46.  
  47. # ifndef _STLP_INTERNAL_SLIST_BASE_H
  48. #  include <stl/_slist_base.h>
  49. # endif
  50.  
  51. # undef slist
  52. # define  slist  __WORKAROUND_DBG_RENAME(slist)
  53.  
  54. _STLP_BEGIN_NAMESPACE 
  55.  
  56. template <class _Tp>
  57. struct _Slist_node : public _Slist_node_base
  58. {
  59.   _Tp _M_data;
  60.   __TRIVIAL_STUFF(_Slist_node)
  61. };
  62.  
  63. struct _Slist_iterator_base {
  64.  
  65.   typedef size_t               size_type;
  66.   typedef ptrdiff_t            difference_type;
  67.   typedef forward_iterator_tag iterator_category;
  68.  
  69.   _Slist_node_base* _M_node;
  70.  
  71.   _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
  72.  
  73.   void _M_incr() { 
  74. //    _STLP_VERBOSE_ASSERT(_M_node != 0, _StlMsg_INVALID_ADVANCE)
  75.     _M_node = _M_node->_M_next; 
  76.   }
  77.   bool operator==(const _Slist_iterator_base& __y ) const { 
  78.     return _M_node == __y._M_node; 
  79.   }
  80.   bool operator!=(const _Slist_iterator_base& __y ) const { 
  81.     return _M_node != __y._M_node; 
  82.   }
  83. };
  84.  
  85. # ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
  86. inline ptrdiff_t* _STLP_CALL distance_type(const _Slist_iterator_base&) { return 0; }
  87. inline forward_iterator_tag _STLP_CALL iterator_category(const _Slist_iterator_base&) { return forward_iterator_tag(); }
  88. #endif
  89.  
  90. template <class _Tp, class _Traits>
  91. struct _Slist_iterator : public _Slist_iterator_base
  92. {
  93.   typedef _Tp value_type;
  94.   typedef typename _Traits::pointer    pointer;
  95.   typedef typename _Traits::reference  reference;
  96.   typedef forward_iterator_tag iterator_category;
  97.   typedef size_t size_type;
  98.   typedef ptrdiff_t difference_type;
  99.   
  100.   typedef _Slist_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
  101.   typedef _Slist_iterator<_Tp, _Const_traits<_Tp> >    const_iterator;
  102.   typedef _Slist_iterator<_Tp, _Traits>                       _Self;
  103.  
  104.   typedef _Slist_node<value_type> _Node;
  105.  
  106.   _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
  107.   _Slist_iterator() : _Slist_iterator_base(0) {}
  108.   _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
  109.  
  110.   reference operator*() const { return ((_Node*) _M_node)->_M_data; }
  111.  
  112.   _STLP_DEFINE_ARROW_OPERATOR
  113.  
  114.   _Self& operator++()
  115.   {
  116.     _M_incr();
  117.     return *this;
  118.   }
  119.   _Self operator++(int)
  120.   {
  121.     _Self __tmp = *this;
  122.     _M_incr();
  123.     return __tmp;
  124.   }
  125. };
  126.  
  127. #ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
  128. template <class _Tp, class _Traits>
  129. inline _Tp* _STLP_CALL value_type(const _Slist_iterator<_Tp, _Traits>&) { return (_Tp*)0; }
  130. #endif /* OLD_QUERIES */
  131.  
  132. // Base class that encapsulates details of allocators and simplifies EH
  133.  
  134. template <class _Tp, class _Alloc> 
  135. struct _Slist_base {
  136.   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
  137.   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
  138.   typedef _Slist_node<_Tp> _Node;
  139.  
  140.   _Slist_base(const allocator_type& __a) : 
  141.     _M_head(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Slist_node_base() ) { 
  142.     _M_head._M_data._M_next = 0; 
  143.   }
  144.   ~_Slist_base() { _M_erase_after(&_M_head._M_data, 0); }
  145.  
  146. protected:
  147.   typedef typename _Alloc_traits<_Node,_Alloc>::allocator_type _M_node_allocator_type;
  148.  
  149.   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
  150.   {
  151.     _Node* __next = (_Node*) (__pos->_M_next);
  152.     _Slist_node_base* __next_next = __next->_M_next;
  153.     __pos->_M_next = __next_next;
  154.     _Destroy(&__next->_M_data);
  155.     _M_head.deallocate(__next,1);
  156.     return __next_next;
  157.   }
  158.   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
  159.  
  160. public:
  161.   allocator_type get_allocator() const { 
  162.     return _STLP_CONVERT_ALLOCATOR((const _M_node_allocator_type&)_M_head, _Tp); 
  163.   }
  164.   _STLP_alloc_proxy<_Slist_node_base, _Node, _M_node_allocator_type> _M_head;
  165. };  
  166.  
  167. template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
  168. class slist : protected _Slist_base<_Tp,_Alloc>
  169. {
  170. private:
  171.   typedef _Slist_base<_Tp,_Alloc> _Base;
  172.   typedef slist<_Tp,_Alloc> _Self;
  173. public:
  174.   typedef _Tp                value_type;
  175.   typedef value_type*       pointer;
  176.   typedef const value_type* const_pointer;
  177.   typedef value_type&       reference;
  178.   typedef const value_type& const_reference;
  179.   typedef size_t            size_type;
  180.   typedef ptrdiff_t         difference_type;
  181.   typedef forward_iterator_tag _Iterator_category;
  182.  
  183.   typedef _Slist_iterator<_Tp, _Nonconst_traits<_Tp> >  iterator;
  184.   typedef _Slist_iterator<_Tp, _Const_traits<_Tp> >     const_iterator;
  185.  
  186.   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
  187.   typedef typename _Base::allocator_type allocator_type;
  188.  
  189.  
  190. private:
  191.   typedef _Slist_node<_Tp>      _Node;
  192.   typedef _Slist_node_base      _Node_base;
  193.   typedef _Slist_iterator_base  _Iterator_base;
  194.  
  195.   _Node* _M_create_node(const value_type& __x) {
  196.     _Node* __node = this->_M_head.allocate(1);
  197.     _STLP_TRY {
  198.       _Construct(&__node->_M_data, __x);
  199.       __node->_M_next = 0;
  200.     }
  201.     _STLP_UNWIND(this->_M_head.deallocate(__node, 1));
  202.     return __node;
  203.   }
  204.   
  205.   _Node* _M_create_node() {
  206.     _Node* __node = this->_M_head.allocate(1);
  207.     _STLP_TRY {
  208.       _Construct(&__node->_M_data);
  209.       __node->_M_next = 0;
  210.     }
  211.     _STLP_UNWIND(this->_M_head.deallocate(__node, 1));
  212.     return __node;
  213.   }
  214.  
  215. public:
  216.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  217.  
  218.   explicit slist(const allocator_type& __a = allocator_type()) : _Slist_base<_Tp,_Alloc>(__a) {}
  219.  
  220.   slist(size_type __n, const value_type& __x,
  221.         const allocator_type& __a =  allocator_type()) : _Slist_base<_Tp,_Alloc>(__a)
  222.     { _M_insert_after_fill(&this->_M_head._M_data, __n, __x); }
  223.  
  224.   explicit slist(size_type __n) : _Slist_base<_Tp,_Alloc>(allocator_type())
  225.     { _M_insert_after_fill(&this->_M_head._M_data, __n, value_type()); }
  226.  
  227. #ifdef _STLP_MEMBER_TEMPLATES
  228.   // We don't need any dispatching tricks here, because _M_insert_after_range
  229.   // already does them.
  230.   template <class _InputIterator>
  231.   slist(_InputIterator __first, _InputIterator __last,
  232.         const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) : 
  233.     _Slist_base<_Tp,_Alloc>(__a)
  234.   { _M_insert_after_range(&this->_M_head._M_data, __first, __last); }
  235. # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
  236.   // VC++ needs this crazyness
  237.   template <class _InputIterator>
  238.   slist(_InputIterator __first, _InputIterator __last) :
  239.     _Slist_base<_Tp,_Alloc>(allocator_type())
  240.   { _M_insert_after_range(&this->_M_head._M_data, __first, __last); }
  241. # endif  
  242. #else /* _STLP_MEMBER_TEMPLATES */
  243.   slist(const_iterator __first, const_iterator __last,
  244.         const allocator_type& __a =  allocator_type() ) :
  245.     _Slist_base<_Tp,_Alloc>(__a)
  246.     { _M_insert_after_range(&this->_M_head._M_data, __first, __last); }
  247.   slist(const value_type* __first, const value_type* __last,
  248.         const allocator_type& __a =  allocator_type()) : 
  249.     _Slist_base<_Tp,_Alloc>(__a)
  250.     { _M_insert_after_range(&this->_M_head._M_data, __first, __last); }
  251. #endif /* _STLP_MEMBER_TEMPLATES */
  252.  
  253.   slist(const _Self& __x) : _Slist_base<_Tp,_Alloc>(__x.get_allocator())
  254.     { _M_insert_after_range(&this->_M_head._M_data, __x.begin(), __x.end()); }
  255.  
  256.   _Self& operator= (const _Self& __x);
  257.  
  258.   ~slist() {}
  259.  
  260. public:
  261.   // assign(), a generalized assignment member function.  Two
  262.   // versions: one that takes a count, and one that takes a range.
  263.   // The range version is a member template, so we dispatch on whether
  264.   // or not the type is an integer.
  265.  
  266.   void assign(size_type __n, const _Tp& __val)
  267.     { _M_fill_assign(__n, __val); }
  268.  
  269.   void _M_fill_assign(size_type __n, const _Tp& __val);
  270.  
  271. #ifdef _STLP_MEMBER_TEMPLATES
  272.  
  273.   template <class _InputIterator>
  274.   void assign(_InputIterator __first, _InputIterator __last) {
  275.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  276.     _M_assign_dispatch(__first, __last, _Integral());
  277.   }
  278.  
  279.   template <class _Integer>
  280.   void _M_assign_dispatch(_Integer __n, _Integer __val, const __true_type&)
  281.     { _M_fill_assign((size_type) __n, (_Tp) __val); }
  282.  
  283.   template <class _InputIter>
  284.   void
  285.   _M_assign_dispatch(_InputIter __first, _InputIter __last,
  286.              const __false_type&) {
  287.     _Node_base* __prev = &this->_M_head._M_data;
  288.     _Node* __node = (_Node*) this->_M_head._M_data._M_next;
  289.     while (__node != 0 && __first != __last) {
  290.       __node->_M_data = *__first;
  291.       __prev = __node;
  292.       __node = (_Node*) __node->_M_next;
  293.       ++__first;
  294.     }
  295.     if (__first != __last)
  296.       _M_insert_after_range(__prev, __first, __last);
  297.     else
  298.       this->_M_erase_after(__prev, 0);
  299.   }
  300. #endif /* _STLP_MEMBER_TEMPLATES */
  301.  
  302. public:
  303.  
  304.   // Experimental new feature: before_begin() returns a
  305.   // non-dereferenceable iterator that, when incremented, yields
  306.   // begin().  This iterator may be used as the argument to
  307.   // insert_after, erase_after, etc.  Note that even for an empty 
  308.   // slist, before_begin() is not the same iterator as end().  It 
  309.   // is always necessary to increment before_begin() at least once to
  310.   // obtain end().
  311.   iterator before_begin() { return iterator((_Node*) &this->_M_head._M_data); }
  312.   const_iterator before_begin() const
  313.     { return const_iterator((_Node*) &this->_M_head._M_data); }
  314.  
  315.   iterator begin() { return iterator((_Node*)this->_M_head._M_data._M_next); }
  316.   const_iterator begin() const 
  317.     { return const_iterator((_Node*)this->_M_head._M_data._M_next);}
  318.  
  319.   iterator end() { return iterator(0); }
  320.   const_iterator end() const { return const_iterator(0); }
  321.  
  322.   size_type size() const { return _Sl_global_inst::size(this->_M_head._M_data._M_next); }
  323.   
  324.   size_type max_size() const { return size_type(-1); }
  325.  
  326.   bool empty() const { return this->_M_head._M_data._M_next == 0; }
  327.  
  328.   void swap(_Self& __x) { 
  329.     _STLP_STD::swap(this->_M_head, __x._M_head); 
  330.   }
  331.  
  332. public:
  333.   reference front() { return ((_Node*) this->_M_head._M_data._M_next)->_M_data; }
  334.   const_reference front() const 
  335.     { return ((_Node*) this->_M_head._M_data._M_next)->_M_data; }
  336.   void push_front(const value_type& __x)   {
  337.     __slist_make_link(&this->_M_head._M_data, _M_create_node(__x));
  338.   }
  339.  
  340. # ifndef _STLP_NO_ANACHRONISMS
  341.   void push_front() { __slist_make_link(&this->_M_head._M_data, _M_create_node());}
  342. # endif
  343.  
  344.   void pop_front() {
  345.     _Node* __node = (_Node*) this->_M_head._M_data._M_next;
  346.     this->_M_head._M_data._M_next = __node->_M_next;
  347.     _Destroy(&__node->_M_data);
  348.     this->_M_head.deallocate(__node, 1);
  349.   }
  350.  
  351.   iterator previous(const_iterator __pos) {
  352.     return iterator((_Node*) _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node));
  353.   }
  354.   const_iterator previous(const_iterator __pos) const {
  355.     return const_iterator((_Node*) _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node));
  356.   }
  357.  
  358. private:
  359.   _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
  360.     return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
  361.   }
  362.  
  363.   _Node* _M_insert_after(_Node_base* __pos) {
  364.     return (_Node*) (__slist_make_link(__pos, _M_create_node()));
  365.   }
  366.  
  367.   void _M_insert_after_fill(_Node_base* __pos,
  368.                             size_type __n, const value_type& __x) {
  369.     for (size_type __i = 0; __i < __n; ++__i)
  370.       __pos = __slist_make_link(__pos, _M_create_node(__x));
  371.   }
  372.  
  373. #ifdef _STLP_MEMBER_TEMPLATES
  374.  
  375.   // Check whether it's an integral type.  If so, it's not an iterator.
  376.   template <class _InIter>
  377.   void _M_insert_after_range(_Node_base* __pos, 
  378.                              _InIter __first, _InIter __last) {
  379.     typedef typename _Is_integer<_InIter>::_Integral _Integral;
  380.     _M_insert_after_range(__pos, __first, __last, _Integral());
  381.   }
  382.  
  383.   template <class _Integer>
  384.   void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
  385.                              const __true_type&) {
  386.     _M_insert_after_fill(__pos, __n, __x);
  387.   }
  388.  
  389.   template <class _InIter>
  390.   void _M_insert_after_range(_Node_base* __pos,
  391.                              _InIter __first, _InIter __last,
  392.                              const __false_type&) {
  393.     while (__first != __last) {
  394.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  395.       ++__first;
  396.     }
  397.   }
  398.  
  399. #else /* _STLP_MEMBER_TEMPLATES */
  400.  
  401.   void _M_insert_after_range(_Node_base* __pos,
  402.                              const_iterator __first, const_iterator __last) {
  403.     while (__first != __last) {
  404.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  405.       ++__first;
  406.     }
  407.   }
  408.   void _M_insert_after_range(_Node_base* __pos,
  409.                              const value_type* __first,
  410.                              const value_type* __last) {
  411.     while (__first != __last) {
  412.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  413.       ++__first;
  414.     }
  415.   }
  416.  
  417. #endif /* _STLP_MEMBER_TEMPLATES */
  418.  
  419. public:
  420.  
  421.   iterator insert_after(iterator __pos, const value_type& __x) {
  422.     return iterator(_M_insert_after(__pos._M_node, __x));
  423.   }
  424.  
  425.   iterator insert_after(iterator __pos) {
  426.     return insert_after(__pos, value_type());
  427.   }
  428.  
  429.   void insert_after(iterator __pos, size_type __n, const value_type& __x) {
  430.     _M_insert_after_fill(__pos._M_node, __n, __x);
  431.   }
  432.  
  433. #ifdef _STLP_MEMBER_TEMPLATES
  434.  
  435.   // We don't need any dispatching tricks here, because _M_insert_after_range
  436.   // already does them.
  437.   template <class _InIter>
  438.   void insert_after(iterator __pos, _InIter __first, _InIter __last) {
  439.     _M_insert_after_range(__pos._M_node, __first, __last);
  440.   }
  441.  
  442. #else /* _STLP_MEMBER_TEMPLATES */
  443.  
  444.   void insert_after(iterator __pos,
  445.                     const_iterator __first, const_iterator __last) {
  446.     _M_insert_after_range(__pos._M_node, __first, __last);
  447.   }
  448.   void insert_after(iterator __pos,
  449.                     const value_type* __first, const value_type* __last) {
  450.     _M_insert_after_range(__pos._M_node, __first, __last);
  451.   }
  452.  
  453. #endif /* _STLP_MEMBER_TEMPLATES */
  454.  
  455.   iterator insert(iterator __pos, const value_type& __x) {
  456.     return iterator(_M_insert_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
  457.                     __x));
  458.   }
  459.  
  460.   iterator insert(iterator __pos) {
  461.     return iterator(_M_insert_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
  462.                                     value_type()));
  463.   }
  464.  
  465.   void insert(iterator __pos, size_type __n, const value_type& __x) {
  466.     _M_insert_after_fill(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), __n, __x);
  467.   } 
  468.     
  469. #ifdef _STLP_MEMBER_TEMPLATES
  470.  
  471.   // We don't need any dispatching tricks here, because _M_insert_after_range
  472.   // already does them.
  473.   template <class _InIter>
  474.   void insert(iterator __pos, _InIter __first, _InIter __last) {
  475.     _M_insert_after_range(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 
  476.                           __first, __last);
  477.   }
  478.  
  479. #else /* _STLP_MEMBER_TEMPLATES */
  480.  
  481.   void insert(iterator __pos, const_iterator __first, const_iterator __last) {
  482.     _M_insert_after_range(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 
  483.                           __first, __last);
  484.   }
  485.   void insert(iterator __pos, const value_type* __first, 
  486.                               const value_type* __last) {
  487.     _M_insert_after_range(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 
  488.                           __first, __last);
  489.   }
  490.  
  491. #endif /* _STLP_MEMBER_TEMPLATES */
  492.  
  493.  
  494. public:
  495.   iterator erase_after(iterator __pos) {
  496.     return iterator((_Node*) this->_M_erase_after(__pos._M_node));
  497.   }
  498.   iterator erase_after(iterator __before_first, iterator __last) {
  499.     return iterator((_Node*) this->_M_erase_after(__before_first._M_node, 
  500.                                             __last._M_node));
  501.   } 
  502.  
  503.   iterator erase(iterator __pos) {
  504.     return iterator((_Node*) this->_M_erase_after(_Sl_global_inst::__previous(&this->_M_head._M_data, 
  505.                                                     __pos._M_node)));
  506.   }
  507.   iterator erase(iterator __first, iterator __last) {
  508.     return iterator((_Node*) this->_M_erase_after(
  509.       _Sl_global_inst::__previous(&this->_M_head._M_data, __first._M_node), __last._M_node));
  510.   }
  511.  
  512.   void resize(size_type new_size, const _Tp& __x);
  513.   void resize(size_type new_size) { resize(new_size, _Tp()); }
  514.   void clear() {
  515.     this->_M_erase_after(&this->_M_head._M_data, 0); 
  516.   }
  517.  
  518. public:
  519.   // Moves the range [__before_first + 1, __before_last + 1) to *this,
  520.   //  inserting it immediately after __pos.  This is constant time.
  521.   void splice_after(iterator __pos, 
  522.                     iterator __before_first, iterator __before_last)
  523.   {
  524.     if (__before_first != __before_last) {
  525.       _Sl_global_inst::__splice_after(__pos._M_node, __before_first._M_node, 
  526.                            __before_last._M_node);
  527.     }
  528.   }
  529.  
  530.   // Moves the element that follows __prev to *this, inserting it immediately
  531.   //  after __pos.  This is constant time.
  532.   void splice_after(iterator __pos, iterator __prev)
  533.   {
  534.     _Sl_global_inst::__splice_after(__pos._M_node,
  535.                          __prev._M_node, __prev._M_node->_M_next);
  536.   }
  537.  
  538.   // Removes all of the elements from the list __x to *this, inserting
  539.   // them immediately after __pos.  __x must not be *this.  Complexity:
  540.   // linear in __x.size().
  541.   void splice_after(iterator __pos, _Self& __x)
  542.   {
  543.     _Sl_global_inst::__splice_after(__pos._M_node, &__x._M_head._M_data);
  544.   }
  545.  
  546.   // Linear in distance(begin(), __pos), and linear in __x.size().
  547.   void splice(iterator __pos, _Self& __x) {
  548.     if (__x._M_head._M_data._M_next)
  549.       _Sl_global_inst::__splice_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
  550.                            &__x._M_head._M_data, _Sl_global_inst::__previous(&__x._M_head._M_data, 0));
  551.   }
  552.  
  553.   // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
  554.   void splice(iterator __pos, _Self& __x, iterator __i) {
  555.     _Sl_global_inst::__splice_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
  556.                          _Sl_global_inst::__previous(&__x._M_head._M_data, __i._M_node),
  557.                          __i._M_node);
  558.   }
  559.  
  560.   // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
  561.   // and in distance(__first, __last).
  562.   void splice(iterator __pos, _Self& __x, iterator __first, iterator __last)
  563.   {
  564.     if (__first != __last)
  565.       _Sl_global_inst::__splice_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
  566.                            _Sl_global_inst::__previous(&__x._M_head._M_data, __first._M_node),
  567.                            _Sl_global_inst::__previous(__first._M_node, __last._M_node));
  568.   }
  569.  
  570. public:
  571.   void reverse() { 
  572.     if (this->_M_head._M_data._M_next)
  573.       this->_M_head._M_data._M_next = _Sl_global_inst::__reverse(this->_M_head._M_data._M_next);
  574.   }
  575.  
  576.   void remove(const _Tp& __val); 
  577.   void unique(); 
  578.   void merge(_Self& __x);
  579.   void sort();     
  580.  
  581. #ifdef _STLP_MEMBER_TEMPLATES
  582.   template <class _Predicate>
  583.   void remove_if(_Predicate __pred) {
  584.     _Node_base* __cur = &this->_M_head._M_data;
  585.     while (__cur->_M_next) {
  586.       if (__pred(((_Node*) __cur->_M_next)->_M_data))
  587.     this->_M_erase_after(__cur);
  588.       else
  589.     __cur = __cur->_M_next;
  590.     }
  591.   }
  592.  
  593.   template <class _BinaryPredicate> 
  594.   void unique(_BinaryPredicate __pred) {
  595.     _Node* __cur = (_Node*) this->_M_head._M_data._M_next;
  596.     if (__cur) {
  597.       while (__cur->_M_next) {
  598.     if (__pred(((_Node*)__cur)->_M_data, 
  599.            ((_Node*)(__cur->_M_next))->_M_data))
  600.       this->_M_erase_after(__cur);
  601.     else
  602.       __cur = (_Node*) __cur->_M_next;
  603.       }
  604.     }
  605.   }
  606.  
  607.   template <class _StrictWeakOrdering>
  608.   void merge(slist<_Tp,_Alloc>& __x,
  609.          _StrictWeakOrdering __comp) {
  610.     _Node_base* __n1 = &this->_M_head._M_data;
  611.     while (__n1->_M_next && __x._M_head._M_data._M_next) {
  612.       if (__comp(((_Node*) __x._M_head._M_data._M_next)->_M_data,
  613.          ((_Node*)       __n1->_M_next)->_M_data))
  614.     _Sl_global_inst::__splice_after(__n1, &__x._M_head._M_data, __x._M_head._M_data._M_next);
  615.       __n1 = __n1->_M_next;
  616.     }
  617.     if (__x._M_head._M_data._M_next) {
  618.       __n1->_M_next = __x._M_head._M_data._M_next;
  619.       __x._M_head._M_data._M_next = 0;
  620.     }
  621.   }
  622.  
  623.   template <class _StrictWeakOrdering> 
  624.   void sort(_StrictWeakOrdering __comp) {
  625.     if (this->_M_head._M_data._M_next && this->_M_head._M_data._M_next->_M_next) {
  626.       slist __carry;
  627.       slist __counter[64];
  628.       int __fill = 0;
  629.       while (!empty()) {
  630.     _Sl_global_inst::__splice_after(&__carry._M_head._M_data, &this->_M_head._M_data, this->_M_head._M_data._M_next);
  631.     int __i = 0;
  632.     while (__i < __fill && !__counter[__i].empty()) {
  633.       __counter[__i].merge(__carry, __comp);
  634.       __carry.swap(__counter[__i]);
  635.       ++__i;
  636.     }
  637.     __carry.swap(__counter[__i]);
  638.     if (__i == __fill)
  639.       ++__fill;
  640.       }
  641.       
  642.       for (int __i = 1; __i < __fill; ++__i)
  643.     __counter[__i].merge(__counter[__i-1], __comp);
  644.       this->swap(__counter[__fill-1]);
  645.     }
  646.   }
  647. #endif /* _STLP_MEMBER_TEMPLATES */
  648.  
  649. };
  650.  
  651. template <class _Tp, class _Alloc>
  652. inline bool  _STLP_CALL
  653. operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
  654. {
  655.   typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
  656.   const_iterator __end1 = _SL1.end();
  657.   const_iterator __end2 = _SL2.end();
  658.  
  659.   const_iterator __i1 = _SL1.begin();
  660.   const_iterator __i2 = _SL2.begin();
  661.   while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
  662.     ++__i1;
  663.     ++__i2;
  664.    }
  665.   return __i1 == __end1 && __i2 == __end2;
  666. }
  667.  
  668. template <class _Tp, class _Alloc>
  669. inline bool _STLP_CALL operator<(const slist<_Tp,_Alloc>& _SL1,
  670.                                  const slist<_Tp,_Alloc>& _SL2)
  671. {
  672.   return lexicographical_compare(_SL1.begin(), _SL1.end(), 
  673.                                  _SL2.begin(), _SL2.end());
  674. }
  675.  
  676. #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
  677.  
  678. template <class _Tp, class _Alloc>
  679. inline bool _STLP_CALL 
  680. operator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  681.   return !(_SL1 == _SL2);
  682. }
  683.  
  684. template <class _Tp, class _Alloc>
  685. inline bool _STLP_CALL 
  686. operator>(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  687.   return _SL2 < _SL1;
  688. }
  689.  
  690. template <class _Tp, class _Alloc>
  691. inline bool _STLP_CALL 
  692. operator<=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  693.   return !(_SL2 < _SL1);
  694. }
  695.  
  696. template <class _Tp, class _Alloc>
  697. inline bool _STLP_CALL 
  698. operator>=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  699.   return !(_SL1 < _SL2);
  700. }
  701. #endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
  702.  
  703. #ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
  704.  
  705. template <class _Tp, class _Alloc>
  706. inline void _STLP_CALL swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) {
  707.   __x.swap(__y);
  708. }
  709.  
  710. #endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */
  711.  
  712. _STLP_END_NAMESPACE
  713.  
  714. # if !defined (_STLP_LINK_TIME_INSTANTIATION)
  715. #  include <stl/_slist.c>
  716. # endif
  717.  
  718. #  undef  slist
  719. #  define __slist__ __FULL_NAME(slist)
  720.  
  721. #if defined (_STLP_DEBUG) && !defined (_STLP_INTERNAL_DBG_SLIST_H)
  722. # include <stl/debug/_slist.h>
  723. #endif
  724.  
  725. _STLP_BEGIN_NAMESPACE
  726. // Specialization of insert_iterator so that insertions will be constant
  727. // time rather than linear time.
  728.  
  729. #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
  730.  
  731. template <class _Tp, class _Alloc>
  732. class insert_iterator<slist<_Tp, _Alloc> > {
  733. protected:
  734.   typedef slist<_Tp, _Alloc> _Container;
  735.   _Container* container;
  736.   typename _Container::iterator iter;
  737. public:
  738.   typedef _Container          container_type;
  739.   typedef output_iterator_tag iterator_category;
  740.   typedef void                value_type;
  741.   typedef void                difference_type;
  742.   typedef void                pointer;
  743.   typedef void                reference;
  744.  
  745.   insert_iterator(_Container& __x, typename _Container::iterator __i) 
  746.     : container(&__x) {
  747.     if (__i == __x.begin())
  748.       iter = __x.before_begin();
  749.     else
  750.       iter = __x.previous(__i);
  751.   }
  752.  
  753.   insert_iterator<_Container>&
  754.   operator=(const typename _Container::value_type& __val) { 
  755.     iter = container->insert_after(iter, __val);
  756.     return *this;
  757.   }
  758.   insert_iterator<_Container>& operator*() { return *this; }
  759.   insert_iterator<_Container>& operator++() { return *this; }
  760.   insert_iterator<_Container>& operator++(int) { return *this; }
  761. };
  762.  
  763. #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
  764.  
  765. _STLP_END_NAMESPACE
  766.  
  767.  
  768. # if defined ( _STLP_USE_WRAPPER_FOR_ALLOC_PARAM )
  769. # include <stl/wrappers/_slist.h>
  770. # endif
  771.  
  772. #endif /* _STLP_INTERNAL_SLIST_H */
  773.  
  774. // Local Variables:
  775. // mode:C++
  776. // End:
  777.  
  778.