stl_slis.h
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:31k
源码类别:

STL

开发平台:

Visual C++

  1. /*
  2.  * Copyright (c) 1997
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  *
  13.  */
  14. /* NOTE: This is an internal header file, included by other STL headers.
  15.  *   You should not attempt to use it directly.
  16.  */
  17. #ifndef __SGI_STL_INTERNAL_SLIST_H
  18. #define __SGI_STL_INTERNAL_SLIST_H
  19. #include <concept_checks.h>
  20. __STL_BEGIN_NAMESPACE 
  21. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  22. #pragma set woff 1174
  23. #pragma set woff 1375
  24. #endif
  25. struct _Slist_node_base
  26. {
  27.   _Slist_node_base* _M_next;
  28. };
  29. inline _Slist_node_base*
  30. __slist_make_link(_Slist_node_base* __prev_node,
  31.                   _Slist_node_base* __new_node)
  32. {
  33.   __new_node->_M_next = __prev_node->_M_next;
  34.   __prev_node->_M_next = __new_node;
  35.   return __new_node;
  36. }
  37. inline _Slist_node_base* 
  38. __slist_previous(_Slist_node_base* __head,
  39.                  const _Slist_node_base* __node)
  40. {
  41.   while (__head && __head->_M_next != __node)
  42.     __head = __head->_M_next;
  43.   return __head;
  44. }
  45. inline const _Slist_node_base* 
  46. __slist_previous(const _Slist_node_base* __head,
  47.                  const _Slist_node_base* __node)
  48. {
  49.   while (__head && __head->_M_next != __node)
  50.     __head = __head->_M_next;
  51.   return __head;
  52. }
  53. inline void __slist_splice_after(_Slist_node_base* __pos,
  54.                                  _Slist_node_base* __before_first,
  55.                                  _Slist_node_base* __before_last)
  56. {
  57.   if (__pos != __before_first && __pos != __before_last) {
  58.     _Slist_node_base* __first = __before_first->_M_next;
  59.     _Slist_node_base* __after = __pos->_M_next;
  60.     __before_first->_M_next = __before_last->_M_next;
  61.     __pos->_M_next = __first;
  62.     __before_last->_M_next = __after;
  63.   }
  64. }
  65. inline void
  66. __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
  67. {
  68.   _Slist_node_base* __before_last = __slist_previous(__head, 0);
  69.   if (__before_last != __head) {
  70.     _Slist_node_base* __after = __pos->_M_next;
  71.     __pos->_M_next = __head->_M_next;
  72.     __head->_M_next = 0;
  73.     __before_last->_M_next = __after;
  74.   }
  75. }
  76. inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node)
  77. {
  78.   _Slist_node_base* __result = __node;
  79.   __node = __node->_M_next;
  80.   __result->_M_next = 0;
  81.   while(__node) {
  82.     _Slist_node_base* __next = __node->_M_next;
  83.     __node->_M_next = __result;
  84.     __result = __node;
  85.     __node = __next;
  86.   }
  87.   return __result;
  88. }
  89. inline size_t __slist_size(_Slist_node_base* __node)
  90. {
  91.   size_t __result = 0;
  92.   for ( ; __node != 0; __node = __node->_M_next)
  93.     ++__result;
  94.   return __result;
  95. }
  96. template <class _Tp>
  97. struct _Slist_node : public _Slist_node_base
  98. {
  99.   _Tp _M_data;
  100. };
  101. struct _Slist_iterator_base
  102. {
  103.   typedef size_t               size_type;
  104.   typedef ptrdiff_t            difference_type;
  105.   typedef forward_iterator_tag iterator_category;
  106.   _Slist_node_base* _M_node;
  107.   _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
  108.   void _M_incr() { _M_node = _M_node->_M_next; }
  109.   bool operator==(const _Slist_iterator_base& __x) const {
  110.     return _M_node == __x._M_node;
  111.   }
  112.   bool operator!=(const _Slist_iterator_base& __x) const {
  113.     return _M_node != __x._M_node;
  114.   }
  115. };
  116. template <class _Tp, class _Ref, class _Ptr>
  117. struct _Slist_iterator : public _Slist_iterator_base
  118. {
  119.   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
  120.   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  121.   typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
  122.   typedef _Tp              value_type;
  123.   typedef _Ptr             pointer;
  124.   typedef _Ref             reference;
  125.   typedef _Slist_node<_Tp> _Node;
  126.   _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
  127.   _Slist_iterator() : _Slist_iterator_base(0) {}
  128.   _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
  129.   reference operator*() const { return ((_Node*) _M_node)->_M_data; }
  130. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  131.   pointer operator->() const { return &(operator*()); }
  132. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  133.   _Self& operator++()
  134.   {
  135.     _M_incr();
  136.     return *this;
  137.   }
  138.   _Self operator++(int)
  139.   {
  140.     _Self __tmp = *this;
  141.     _M_incr();
  142.     return __tmp;
  143.   }
  144. };
  145. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  146. inline ptrdiff_t* distance_type(const _Slist_iterator_base&) {
  147.   return 0;
  148. }
  149. inline forward_iterator_tag iterator_category(const _Slist_iterator_base&) {
  150.   return forward_iterator_tag();
  151. }
  152. template <class _Tp, class _Ref, class _Ptr> 
  153. inline _Tp* value_type(const _Slist_iterator<_Tp, _Ref, _Ptr>&) {
  154.   return 0;
  155. }
  156. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  157. // Base class that encapsulates details of allocators.  Three cases:
  158. // an ordinary standard-conforming allocator, a standard-conforming
  159. // allocator with no non-static data, and an SGI-style allocator.
  160. // This complexity is necessary only because we're worrying about backward
  161. // compatibility and because we want to avoid wasting storage on an 
  162. // allocator instance if it isn't necessary.
  163. #ifdef __STL_USE_STD_ALLOCATORS
  164. // Base for general standard-conforming allocators.
  165. template <class _Tp, class _Allocator, bool _IsStatic>
  166. class _Slist_alloc_base {
  167. public:
  168.   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
  169.           allocator_type;
  170.   allocator_type get_allocator() const { return _M_node_allocator; }
  171.   _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {}
  172. protected:
  173.   _Slist_node<_Tp>* _M_get_node() 
  174.     { return _M_node_allocator.allocate(1); }
  175.   void _M_put_node(_Slist_node<_Tp>* __p) 
  176.     { _M_node_allocator.deallocate(__p, 1); }
  177. protected:
  178.   typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type
  179.            _M_node_allocator;
  180.   _Slist_node_base _M_head;
  181. };
  182. // Specialization for instanceless allocators.
  183. template <class _Tp, class _Allocator>
  184. class _Slist_alloc_base<_Tp,_Allocator, true> {
  185. public:
  186.   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
  187.           allocator_type;
  188.   allocator_type get_allocator() const { return allocator_type(); }
  189.   _Slist_alloc_base(const allocator_type&) {}
  190. protected:
  191.   typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type
  192.           _Alloc_type;
  193.   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
  194.   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
  195. protected:
  196.   _Slist_node_base _M_head;
  197. };
  198. template <class _Tp, class _Alloc>
  199. struct _Slist_base
  200.   : public _Slist_alloc_base<_Tp, _Alloc,
  201.                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  202. {
  203.   typedef _Slist_alloc_base<_Tp, _Alloc,
  204.                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  205.           _Base;
  206.   typedef typename _Base::allocator_type allocator_type;
  207.   _Slist_base(const allocator_type& __a)
  208.     : _Base(__a) { this->_M_head._M_next = 0; }
  209.   ~_Slist_base() { _M_erase_after(&this->_M_head, 0); }
  210. protected:
  211.   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
  212.   {
  213.     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
  214.     _Slist_node_base* __next_next = __next->_M_next;
  215.     __pos->_M_next = __next_next;
  216.     destroy(&__next->_M_data);
  217.     _M_put_node(__next);
  218.     return __next_next;
  219.   }
  220.   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
  221. };
  222. #else /* __STL_USE_STD_ALLOCATORS */
  223. template <class _Tp, class _Alloc> 
  224. struct _Slist_base {
  225.   typedef _Alloc allocator_type;
  226.   allocator_type get_allocator() const { return allocator_type(); }
  227.   _Slist_base(const allocator_type&) { _M_head._M_next = 0; }
  228.   ~_Slist_base() { _M_erase_after(&_M_head, 0); }
  229. protected:
  230.   typedef simple_alloc<_Slist_node<_Tp>, _Alloc> _Alloc_type;
  231.   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
  232.   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
  233.   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
  234.   {
  235.     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
  236.     _Slist_node_base* __next_next = __next->_M_next;
  237.     __pos->_M_next = __next_next;
  238.     destroy(&__next->_M_data);
  239.     _M_put_node(__next);
  240.     return __next_next;
  241.   }
  242.   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
  243. protected:
  244.   _Slist_node_base _M_head;
  245. };  
  246. #endif /* __STL_USE_STD_ALLOCATORS */
  247. template <class _Tp, class _Alloc> 
  248. _Slist_node_base*
  249. _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
  250.                                         _Slist_node_base* __last_node) {
  251.   _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
  252.   while (__cur != __last_node) {
  253.     _Slist_node<_Tp>* __tmp = __cur;
  254.     __cur = (_Slist_node<_Tp>*) __cur->_M_next;
  255.     destroy(&__tmp->_M_data);
  256.     _M_put_node(__tmp);
  257.   }
  258.   __before_first->_M_next = __last_node;
  259.   return __last_node;
  260. }
  261. template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
  262. class slist : private _Slist_base<_Tp,_Alloc>
  263. {
  264.   // requirements:
  265.   __STL_CLASS_REQUIRES(_Tp, _Assignable);
  266. private:
  267.   typedef _Slist_base<_Tp,_Alloc> _Base;
  268. public:
  269.   typedef _Tp                value_type;
  270.   typedef value_type*       pointer;
  271.   typedef const value_type* const_pointer;
  272.   typedef value_type&       reference;
  273.   typedef const value_type& const_reference;
  274.   typedef size_t            size_type;
  275.   typedef ptrdiff_t         difference_type;
  276.   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
  277.   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  278.   typedef typename _Base::allocator_type allocator_type;
  279.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  280. private:
  281.   typedef _Slist_node<_Tp>      _Node;
  282.   typedef _Slist_node_base      _Node_base;
  283.   typedef _Slist_iterator_base  _Iterator_base;
  284.   _Node* _M_create_node(const value_type& __x) {
  285.     _Node* __node = this->_M_get_node();
  286.     __STL_TRY {
  287.       construct(&__node->_M_data, __x);
  288.       __node->_M_next = 0;
  289.     }
  290.     __STL_UNWIND(this->_M_put_node(__node));
  291.     return __node;
  292.   }
  293.   
  294.   _Node* _M_create_node() {
  295.     _Node* __node = this->_M_get_node();
  296.     __STL_TRY {
  297.       construct(&__node->_M_data);
  298.       __node->_M_next = 0;
  299.     }
  300.     __STL_UNWIND(this->_M_put_node(__node));
  301.     return __node;
  302.   }
  303. public:
  304.   explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}
  305.   slist(size_type __n, const value_type& __x,
  306.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  307.     { _M_insert_after_fill(&this->_M_head, __n, __x); }
  308.   explicit slist(size_type __n) : _Base(allocator_type())
  309.     { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
  310. #ifdef __STL_MEMBER_TEMPLATES
  311.   // We don't need any dispatching tricks here, because _M_insert_after_range
  312.   // already does them.
  313.   template <class _InputIterator>
  314.   slist(_InputIterator __first, _InputIterator __last,
  315.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  316.     { _M_insert_after_range(&this->_M_head, __first, __last); }
  317. #else /* __STL_MEMBER_TEMPLATES */
  318.   slist(const_iterator __first, const_iterator __last,
  319.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  320.     { _M_insert_after_range(&this->_M_head, __first, __last); }
  321.   slist(const value_type* __first, const value_type* __last,
  322.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  323.     { _M_insert_after_range(&this->_M_head, __first, __last); }
  324. #endif /* __STL_MEMBER_TEMPLATES */
  325.   slist(const slist& __x) : _Base(__x.get_allocator())
  326.     { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
  327.   slist& operator= (const slist& __x);
  328.   ~slist() {}
  329. public:
  330.   // assign(), a generalized assignment member function.  Two
  331.   // versions: one that takes a count, and one that takes a range.
  332.   // The range version is a member template, so we dispatch on whether
  333.   // or not the type is an integer.
  334.   void assign(size_type __n, const _Tp& __val)
  335.     { _M_fill_assign(__n, __val); }
  336.   void _M_fill_assign(size_type __n, const _Tp& __val);
  337. #ifdef __STL_MEMBER_TEMPLATES
  338.   template <class _InputIterator>
  339.   void assign(_InputIterator __first, _InputIterator __last) {
  340.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  341.     _M_assign_dispatch(__first, __last, _Integral());
  342.   }
  343.   template <class _Integer>
  344.   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  345.     { _M_fill_assign((size_type) __n, (_Tp) __val); }
  346.   template <class _InputIterator>
  347.   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  348.                           __false_type);
  349. #endif /* __STL_MEMBER_TEMPLATES */
  350. public:
  351.   iterator begin() { return iterator((_Node*)this->_M_head._M_next); }
  352.   const_iterator begin() const 
  353.     { return const_iterator((_Node*)this->_M_head._M_next);}
  354.   iterator end() { return iterator(0); }
  355.   const_iterator end() const { return const_iterator(0); }
  356.   // Experimental new feature: before_begin() returns a
  357.   // non-dereferenceable iterator that, when incremented, yields
  358.   // begin().  This iterator may be used as the argument to
  359.   // insert_after, erase_after, etc.  Note that even for an empty 
  360.   // slist, before_begin() is not the same iterator as end().  It 
  361.   // is always necessary to increment before_begin() at least once to
  362.   // obtain end().
  363.   iterator before_begin() { return iterator((_Node*) &this->_M_head); }
  364.   const_iterator before_begin() const
  365.     { return const_iterator((_Node*) &this->_M_head); }
  366.   size_type size() const { return __slist_size(this->_M_head._M_next); }
  367.   
  368.   size_type max_size() const { return size_type(-1); }
  369.   bool empty() const { return this->_M_head._M_next == 0; }
  370.   void swap(slist& __x)
  371.     { __STD::swap(this->_M_head._M_next, __x._M_head._M_next); }
  372. public:
  373.   reference front() { return ((_Node*) this->_M_head._M_next)->_M_data; }
  374.   const_reference front() const 
  375.     { return ((_Node*) this->_M_head._M_next)->_M_data; }
  376.   void push_front(const value_type& __x)   {
  377.     __slist_make_link(&this->_M_head, _M_create_node(__x));
  378.   }
  379.   void push_front() { __slist_make_link(&this->_M_head, _M_create_node()); }
  380.   void pop_front() {
  381.     _Node* __node = (_Node*) this->_M_head._M_next;
  382.     this->_M_head._M_next = __node->_M_next;
  383.     destroy(&__node->_M_data);
  384.     this->_M_put_node(__node);
  385.   }
  386.   iterator previous(const_iterator __pos) {
  387.     return iterator((_Node*) __slist_previous(&this->_M_head, __pos._M_node));
  388.   }
  389.   const_iterator previous(const_iterator __pos) const {
  390.     return const_iterator((_Node*) __slist_previous(&this->_M_head,
  391.                                                     __pos._M_node));
  392.   }
  393. private:
  394.   _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
  395.     return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
  396.   }
  397.   _Node* _M_insert_after(_Node_base* __pos) {
  398.     return (_Node*) (__slist_make_link(__pos, _M_create_node()));
  399.   }
  400.   void _M_insert_after_fill(_Node_base* __pos,
  401.                             size_type __n, const value_type& __x) {
  402.     for (size_type __i = 0; __i < __n; ++__i)
  403.       __pos = __slist_make_link(__pos, _M_create_node(__x));
  404.   }
  405. #ifdef __STL_MEMBER_TEMPLATES
  406.   // Check whether it's an integral type.  If so, it's not an iterator.
  407.   template <class _InIter>
  408.   void _M_insert_after_range(_Node_base* __pos, 
  409.                              _InIter __first, _InIter __last) {
  410.     typedef typename _Is_integer<_InIter>::_Integral _Integral;
  411.     _M_insert_after_range(__pos, __first, __last, _Integral());
  412.   }
  413.   template <class _Integer>
  414.   void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
  415.                              __true_type) {
  416.     _M_insert_after_fill(__pos, __n, __x);
  417.   }
  418.   template <class _InIter>
  419.   void _M_insert_after_range(_Node_base* __pos,
  420.                              _InIter __first, _InIter __last,
  421.                              __false_type) {
  422.     while (__first != __last) {
  423.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  424.       ++__first;
  425.     }
  426.   }
  427. #else /* __STL_MEMBER_TEMPLATES */
  428.   void _M_insert_after_range(_Node_base* __pos,
  429.                              const_iterator __first, const_iterator __last) {
  430.     while (__first != __last) {
  431.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  432.       ++__first;
  433.     }
  434.   }
  435.   void _M_insert_after_range(_Node_base* __pos,
  436.                              const value_type* __first,
  437.                              const value_type* __last) {
  438.     while (__first != __last) {
  439.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  440.       ++__first;
  441.     }
  442.   }
  443. #endif /* __STL_MEMBER_TEMPLATES */
  444. public:
  445.   iterator insert_after(iterator __pos, const value_type& __x) {
  446.     return iterator(_M_insert_after(__pos._M_node, __x));
  447.   }
  448.   iterator insert_after(iterator __pos) {
  449.     return insert_after(__pos, value_type());
  450.   }
  451.   void insert_after(iterator __pos, size_type __n, const value_type& __x) {
  452.     _M_insert_after_fill(__pos._M_node, __n, __x);
  453.   }
  454. #ifdef __STL_MEMBER_TEMPLATES
  455.   // We don't need any dispatching tricks here, because _M_insert_after_range
  456.   // already does them.
  457.   template <class _InIter>
  458.   void insert_after(iterator __pos, _InIter __first, _InIter __last) {
  459.     _M_insert_after_range(__pos._M_node, __first, __last);
  460.   }
  461. #else /* __STL_MEMBER_TEMPLATES */
  462.   void insert_after(iterator __pos,
  463.                     const_iterator __first, const_iterator __last) {
  464.     _M_insert_after_range(__pos._M_node, __first, __last);
  465.   }
  466.   void insert_after(iterator __pos,
  467.                     const value_type* __first, const value_type* __last) {
  468.     _M_insert_after_range(__pos._M_node, __first, __last);
  469.   }
  470. #endif /* __STL_MEMBER_TEMPLATES */
  471.   iterator insert(iterator __pos, const value_type& __x) {
  472.     return iterator(_M_insert_after(__slist_previous(&this->_M_head,
  473.                                                      __pos._M_node),
  474.                     __x));
  475.   }
  476.   iterator insert(iterator __pos) {
  477.     return iterator(_M_insert_after(__slist_previous(&this->_M_head,
  478.                                                      __pos._M_node),
  479.                                     value_type()));
  480.   }
  481.   void insert(iterator __pos, size_type __n, const value_type& __x) {
  482.     _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
  483.                          __n, __x);
  484.   } 
  485.     
  486. #ifdef __STL_MEMBER_TEMPLATES
  487.   // We don't need any dispatching tricks here, because _M_insert_after_range
  488.   // already does them.
  489.   template <class _InIter>
  490.   void insert(iterator __pos, _InIter __first, _InIter __last) {
  491.     _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 
  492.                           __first, __last);
  493.   }
  494. #else /* __STL_MEMBER_TEMPLATES */
  495.   void insert(iterator __pos, const_iterator __first, const_iterator __last) {
  496.     _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 
  497.                           __first, __last);
  498.   }
  499.   void insert(iterator __pos, const value_type* __first, 
  500.                               const value_type* __last) {
  501.     _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 
  502.                           __first, __last);
  503.   }
  504. #endif /* __STL_MEMBER_TEMPLATES */
  505. public:
  506.   iterator erase_after(iterator __pos) {
  507.     return iterator((_Node*) this->_M_erase_after(__pos._M_node));
  508.   }
  509.   iterator erase_after(iterator __before_first, iterator __last) {
  510.     return iterator((_Node*) this->_M_erase_after(__before_first._M_node, 
  511.                                                   __last._M_node));
  512.   } 
  513.   iterator erase(iterator __pos) {
  514.     return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head, 
  515.                                                           __pos._M_node));
  516.   }
  517.   iterator erase(iterator __first, iterator __last) {
  518.     return (_Node*) this->_M_erase_after(
  519.       __slist_previous(&this->_M_head, __first._M_node), __last._M_node);
  520.   }
  521.   void resize(size_type new_size, const _Tp& __x);
  522.   void resize(size_type new_size) { resize(new_size, _Tp()); }
  523.   void clear() { this->_M_erase_after(&this->_M_head, 0); }
  524. public:
  525.   // Moves the range [__before_first + 1, __before_last + 1) to *this,
  526.   //  inserting it immediately after __pos.  This is constant time.
  527.   void splice_after(iterator __pos, 
  528.                     iterator __before_first, iterator __before_last)
  529.   {
  530.     if (__before_first != __before_last) 
  531.       __slist_splice_after(__pos._M_node, __before_first._M_node, 
  532.                            __before_last._M_node);
  533.   }
  534.   // Moves the element that follows __prev to *this, inserting it immediately
  535.   //  after __pos.  This is constant time.
  536.   void splice_after(iterator __pos, iterator __prev)
  537.   {
  538.     __slist_splice_after(__pos._M_node,
  539.                          __prev._M_node, __prev._M_node->_M_next);
  540.   }
  541.   // Removes all of the elements from the list __x to *this, inserting
  542.   // them immediately after __pos.  __x must not be *this.  Complexity:
  543.   // linear in __x.size().
  544.   void splice_after(iterator __pos, slist& __x)
  545.   {
  546.     __slist_splice_after(__pos._M_node, &__x._M_head);
  547.   }
  548.   // Linear in distance(begin(), __pos), and linear in __x.size().
  549.   void splice(iterator __pos, slist& __x) {
  550.     if (__x._M_head._M_next)
  551.       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  552.                            &__x._M_head, __slist_previous(&__x._M_head, 0));
  553.   }
  554.   // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
  555.   void splice(iterator __pos, slist& __x, iterator __i) {
  556.     __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  557.                          __slist_previous(&__x._M_head, __i._M_node),
  558.                          __i._M_node);
  559.   }
  560.   // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
  561.   // and in distance(__first, __last).
  562.   void splice(iterator __pos, slist& __x, iterator __first, iterator __last)
  563.   {
  564.     if (__first != __last)
  565.       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  566.                            __slist_previous(&__x._M_head, __first._M_node),
  567.                            __slist_previous(__first._M_node, __last._M_node));
  568.   }
  569. public:
  570.   void reverse() { 
  571.     if (this->_M_head._M_next)
  572.       this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
  573.   }
  574.   void remove(const _Tp& __val); 
  575.   void unique(); 
  576.   void merge(slist& __x);
  577.   void sort();     
  578. #ifdef __STL_MEMBER_TEMPLATES
  579.   template <class _Predicate> 
  580.   void remove_if(_Predicate __pred);
  581.   template <class _BinaryPredicate> 
  582.   void unique(_BinaryPredicate __pred); 
  583.   template <class _StrictWeakOrdering> 
  584.   void merge(slist&, _StrictWeakOrdering);
  585.   template <class _StrictWeakOrdering> 
  586.   void sort(_StrictWeakOrdering __comp); 
  587. #endif /* __STL_MEMBER_TEMPLATES */
  588. };
  589. template <class _Tp, class _Alloc>
  590. slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x)
  591. {
  592.   if (&__x != this) {
  593.     _Node_base* __p1 = &this->_M_head;
  594.     _Node* __n1 = (_Node*) this->_M_head._M_next;
  595.     const _Node* __n2 = (const _Node*) __x._M_head._M_next;
  596.     while (__n1 && __n2) {
  597.       __n1->_M_data = __n2->_M_data;
  598.       __p1 = __n1;
  599.       __n1 = (_Node*) __n1->_M_next;
  600.       __n2 = (const _Node*) __n2->_M_next;
  601.     }
  602.     if (__n2 == 0)
  603.       this->_M_erase_after(__p1, 0);
  604.     else
  605.       _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 
  606.                                   const_iterator(0));
  607.   }
  608.   return *this;
  609. }
  610. template <class _Tp, class _Alloc>
  611. void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
  612.   _Node_base* __prev = &this->_M_head;
  613.   _Node* __node = (_Node*) this->_M_head._M_next;
  614.   for ( ; __node != 0 && __n > 0 ; --__n) {
  615.     __node->_M_data = __val;
  616.     __prev = __node;
  617.     __node = (_Node*) __node->_M_next;
  618.   }
  619.   if (__n > 0)
  620.     _M_insert_after_fill(__prev, __n, __val);
  621.   else
  622.     this->_M_erase_after(__prev, 0);
  623. }
  624. #ifdef __STL_MEMBER_TEMPLATES
  625. template <class _Tp, class _Alloc> template <class _InputIter>
  626. void
  627. slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last,
  628.                                        __false_type)
  629. {
  630.   _Node_base* __prev = &this->_M_head;
  631.   _Node* __node = (_Node*) this->_M_head._M_next;
  632.   while (__node != 0 && __first != __last) {
  633.     __node->_M_data = *__first;
  634.     __prev = __node;
  635.     __node = (_Node*) __node->_M_next;
  636.     ++__first;
  637.   }
  638.   if (__first != __last)
  639.     _M_insert_after_range(__prev, __first, __last);
  640.   else
  641.     this->_M_erase_after(__prev, 0);
  642. }
  643. #endif /* __STL_MEMBER_TEMPLATES */
  644. template <class _Tp, class _Alloc>
  645. inline bool 
  646. operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
  647. {
  648.   typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
  649.   const_iterator __end1 = _SL1.end();
  650.   const_iterator __end2 = _SL2.end();
  651.   const_iterator __i1 = _SL1.begin();
  652.   const_iterator __i2 = _SL2.begin();
  653.   while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
  654.     ++__i1;
  655.     ++__i2;
  656.   }
  657.   return __i1 == __end1 && __i2 == __end2;
  658. }
  659. template <class _Tp, class _Alloc>
  660. inline bool
  661. operator<(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
  662. {
  663.   return lexicographical_compare(_SL1.begin(), _SL1.end(), 
  664.                                  _SL2.begin(), _SL2.end());
  665. }
  666. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  667. template <class _Tp, class _Alloc>
  668. inline bool 
  669. operator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  670.   return !(_SL1 == _SL2);
  671. }
  672. template <class _Tp, class _Alloc>
  673. inline bool 
  674. operator>(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  675.   return _SL2 < _SL1;
  676. }
  677. template <class _Tp, class _Alloc>
  678. inline bool 
  679. operator<=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  680.   return !(_SL2 < _SL1);
  681. }
  682. template <class _Tp, class _Alloc>
  683. inline bool 
  684. operator>=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  685.   return !(_SL1 < _SL2);
  686. }
  687. template <class _Tp, class _Alloc>
  688. inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) {
  689.   __x.swap(__y);
  690. }
  691. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  692. template <class _Tp, class _Alloc>
  693. void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x)
  694. {
  695.   _Node_base* __cur = &this->_M_head;
  696.   while (__cur->_M_next != 0 && __len > 0) {
  697.     --__len;
  698.     __cur = __cur->_M_next;
  699.   }
  700.   if (__cur->_M_next) 
  701.     this->_M_erase_after(__cur, 0);
  702.   else
  703.     _M_insert_after_fill(__cur, __len, __x);
  704. }
  705. template <class _Tp, class _Alloc>
  706. void slist<_Tp,_Alloc>::remove(const _Tp& __val)
  707. {
  708.   _Node_base* __cur = &this->_M_head;
  709.   while (__cur && __cur->_M_next) {
  710.     if (((_Node*) __cur->_M_next)->_M_data == __val)
  711.       this->_M_erase_after(__cur);
  712.     else
  713.       __cur = __cur->_M_next;
  714.   }
  715. }
  716. template <class _Tp, class _Alloc> 
  717. void slist<_Tp,_Alloc>::unique()
  718. {
  719.   _Node_base* __cur = this->_M_head._M_next;
  720.   if (__cur) {
  721.     while (__cur->_M_next) {
  722.       if (((_Node*)__cur)->_M_data == 
  723.           ((_Node*)(__cur->_M_next))->_M_data)
  724.         this->_M_erase_after(__cur);
  725.       else
  726.         __cur = __cur->_M_next;
  727.     }
  728.   }
  729. }
  730. template <class _Tp, class _Alloc>
  731. void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x)
  732. {
  733.   _Node_base* __n1 = &this->_M_head;
  734.   while (__n1->_M_next && __x._M_head._M_next) {
  735.     if (((_Node*) __x._M_head._M_next)->_M_data < 
  736.         ((_Node*)       __n1->_M_next)->_M_data) 
  737.       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
  738.     __n1 = __n1->_M_next;
  739.   }
  740.   if (__x._M_head._M_next) {
  741.     __n1->_M_next = __x._M_head._M_next;
  742.     __x._M_head._M_next = 0;
  743.   }
  744. }
  745. template <class _Tp, class _Alloc>
  746. void slist<_Tp,_Alloc>::sort()
  747. {
  748.   if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
  749.     slist __carry;
  750.     slist __counter[64];
  751.     int __fill = 0;
  752.     while (!empty()) {
  753.       __slist_splice_after(&__carry._M_head,
  754.                            &this->_M_head, this->_M_head._M_next);
  755.       int __i = 0;
  756.       while (__i < __fill && !__counter[__i].empty()) {
  757.         __counter[__i].merge(__carry);
  758.         __carry.swap(__counter[__i]);
  759.         ++__i;
  760.       }
  761.       __carry.swap(__counter[__i]);
  762.       if (__i == __fill)
  763.         ++__fill;
  764.     }
  765.     for (int __i = 1; __i < __fill; ++__i)
  766.       __counter[__i].merge(__counter[__i-1]);
  767.     this->swap(__counter[__fill-1]);
  768.   }
  769. }
  770. #ifdef __STL_MEMBER_TEMPLATES
  771. template <class _Tp, class _Alloc> 
  772. template <class _Predicate>
  773. void slist<_Tp,_Alloc>::remove_if(_Predicate __pred)
  774. {
  775.   _Node_base* __cur = &this->_M_head;
  776.   while (__cur->_M_next) {
  777.     if (__pred(((_Node*) __cur->_M_next)->_M_data))
  778.       this->_M_erase_after(__cur);
  779.     else
  780.       __cur = __cur->_M_next;
  781.   }
  782. }
  783. template <class _Tp, class _Alloc> template <class _BinaryPredicate> 
  784. void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred)
  785. {
  786.   _Node* __cur = (_Node*) this->_M_head._M_next;
  787.   if (__cur) {
  788.     while (__cur->_M_next) {
  789.       if (__pred(((_Node*)__cur)->_M_data, 
  790.                  ((_Node*)(__cur->_M_next))->_M_data))
  791.         this->_M_erase_after(__cur);
  792.       else
  793.         __cur = (_Node*) __cur->_M_next;
  794.     }
  795.   }
  796. }
  797. template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
  798. void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x,
  799.                               _StrictWeakOrdering __comp)
  800. {
  801.   _Node_base* __n1 = &this->_M_head;
  802.   while (__n1->_M_next && __x._M_head._M_next) {
  803.     if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
  804.                ((_Node*)       __n1->_M_next)->_M_data))
  805.       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
  806.     __n1 = __n1->_M_next;
  807.   }
  808.   if (__x._M_head._M_next) {
  809.     __n1->_M_next = __x._M_head._M_next;
  810.     __x._M_head._M_next = 0;
  811.   }
  812. }
  813. template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> 
  814. void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp)
  815. {
  816.   if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
  817.     slist __carry;
  818.     slist __counter[64];
  819.     int __fill = 0;
  820.     while (!empty()) {
  821.       __slist_splice_after(&__carry._M_head,
  822.                            &this->_M_head, this->_M_head._M_next);
  823.       int __i = 0;
  824.       while (__i < __fill && !__counter[__i].empty()) {
  825.         __counter[__i].merge(__carry, __comp);
  826.         __carry.swap(__counter[__i]);
  827.         ++__i;
  828.       }
  829.       __carry.swap(__counter[__i]);
  830.       if (__i == __fill)
  831.         ++__fill;
  832.     }
  833.     for (int __i = 1; __i < __fill; ++__i)
  834.       __counter[__i].merge(__counter[__i-1], __comp);
  835.     this->swap(__counter[__fill-1]);
  836.   }
  837. }
  838. #endif /* __STL_MEMBER_TEMPLATES */
  839. // Specialization of insert_iterator so that insertions will be constant
  840. // time rather than linear time.
  841. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  842. template <class _Tp, class _Alloc>
  843. class insert_iterator<slist<_Tp, _Alloc> > {
  844. protected:
  845.   typedef slist<_Tp, _Alloc> _Container;
  846.   _Container* container;
  847.   typename _Container::iterator iter;
  848. public:
  849.   typedef _Container          container_type;
  850.   typedef output_iterator_tag iterator_category;
  851.   typedef void                value_type;
  852.   typedef void                difference_type;
  853.   typedef void                pointer;
  854.   typedef void                reference;
  855.   insert_iterator(_Container& __x, typename _Container::iterator __i) 
  856.     : container(&__x) {
  857.     if (__i == __x.begin())
  858.       iter = __x.before_begin();
  859.     else
  860.       iter = __x.previous(__i);
  861.   }
  862.   insert_iterator<_Container>&
  863.   operator=(const typename _Container::value_type& __value) { 
  864.     iter = container->insert_after(iter, __value);
  865.     return *this;
  866.   }
  867.   insert_iterator<_Container>& operator*() { return *this; }
  868.   insert_iterator<_Container>& operator++() { return *this; }
  869.   insert_iterator<_Container>& operator++(int) { return *this; }
  870. };
  871. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  872. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  873. #pragma reset woff 1174
  874. #pragma reset woff 1375
  875. #endif
  876. __STL_END_NAMESPACE 
  877. #endif /* __SGI_STL_INTERNAL_SLIST_H */
  878. // Local Variables:
  879. // mode:C++
  880. // End: