libstdc++-v3/include/ext/slist

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