libstdc++/stl/stl_slist.h

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