old-autovect-branch/libstdc++-v3/include/ext/slist

   1 // Singly-linked list implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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 /** @file ext/slist
  45  *  This file is a GNU extension to the Standard C++ Library (possibly
  46  *  containing extensions from the HP/SGI STL subset).
  47  */
  48
  49 #ifndef _SLIST
  50 #define _SLIST 1
  51
  52 #include <bits/stl_algobase.h>
  53 #include <bits/allocator.h>
  54 #include <bits/stl_construct.h>
  55 #include <bits/stl_uninitialized.h>
  56 #include <bits/concept_check.h>
  57
  58 namespace __gnu_cxx
  59 {
  60   using std::size_t;
  61   using std::ptrdiff_t;
  62   using std::_Construct;
  63   using std::_Destroy;
  64   using std::allocator;
  65
  66   struct _Slist_node_base
  67   {
  68     _Slist_node_base* _M_next;
  69   };
  70
  71   inline _Slist_node_base*
  72   __slist_make_link(_Slist_node_base* __prev_node,
  73                     _Slist_node_base* __new_node)
  74   {
  75     __new_node->_M_next = __prev_node->_M_next;
  76     __prev_node->_M_next = __new_node;
  77     return __new_node;
  78   }
  79
  80   inline _Slist_node_base*
  81   __slist_previous(_Slist_node_base* __head,
  82                    const _Slist_node_base* __node)
  83   {
  84     while (__head && __head->_M_next != __node)
  85       __head = __head->_M_next;
  86     return __head;
  87   }
  88
  89   inline const _Slist_node_base*
  90   __slist_previous(const _Slist_node_base* __head,
  91                    const _Slist_node_base* __node)
  92   {
  93     while (__head && __head->_M_next != __node)
  94       __head = __head->_M_next;
  95     return __head;
  96   }
  97
  98   inline void
  99   __slist_splice_after(_Slist_node_base* __pos,
 100                        _Slist_node_base* __before_first,
 101                        _Slist_node_base* __before_last)
 102   {
 103     if (__pos != __before_first && __pos != __before_last)
 104       {
 105         _Slist_node_base* __first = __before_first->_M_next;
 106         _Slist_node_base* __after = __pos->_M_next;
 107         __before_first->_M_next = __before_last->_M_next;
 108         __pos->_M_next = __first;
 109         __before_last->_M_next = __after;
 110       }
 111   }
 112
 113   inline void
 114   __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
 115   {
 116     _Slist_node_base* __before_last = __slist_previous(__head, 0);
 117     if (__before_last != __head)
 118       {
 119         _Slist_node_base* __after = __pos->_M_next;
 120         __pos->_M_next = __head->_M_next;
 121         __head->_M_next = 0;
 122         __before_last->_M_next = __after;
 123       }
 124   }
 125
 126   inline _Slist_node_base*
 127   __slist_reverse(_Slist_node_base* __node)
 128   {
 129     _Slist_node_base* __result = __node;
 130     __node = __node->_M_next;
 131     __result->_M_next = 0;
 132     while(__node)
 133       {
 134         _Slist_node_base* __next = __node->_M_next;
 135         __node->_M_next = __result;
 136         __result = __node;
 137         __node = __next;
 138       }
 139     return __result;
 140   }
 141
 142   inline size_t
 143   __slist_size(_Slist_node_base* __node)
 144   {
 145     size_t __result = 0;
 146     for (; __node != 0; __node = __node->_M_next)
 147       ++__result;
 148     return __result;
 149   }
 150
 151   template <class _Tp>
 152     struct _Slist_node : public _Slist_node_base
 153     {
 154       _Tp _M_data;
 155     };
 156
 157   struct _Slist_iterator_base
 158   {
 159     typedef size_t                    size_type;
 160     typedef ptrdiff_t                 difference_type;
 161     typedef std::forward_iterator_tag iterator_category;
 162
 163     _Slist_node_base* _M_node;
 164
 165     _Slist_iterator_base(_Slist_node_base* __x)
 166     : _M_node(__x) {}
 167
 168     void
 169     _M_incr()
 170     { _M_node = _M_node->_M_next; }
 171
 172     bool
 173     operator==(const _Slist_iterator_base& __x) const
 174     { return _M_node == __x._M_node; }
 175
 176     bool
 177     operator!=(const _Slist_iterator_base& __x) const
 178     { return _M_node != __x._M_node; }
 179   };
 180
 181   template <class _Tp, class _Ref, class _Ptr>
 182     struct _Slist_iterator : public _Slist_iterator_base
 183     {
 184       typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
 185       typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
 186       typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
 187
 188       typedef _Tp              value_type;
 189       typedef _Ptr             pointer;
 190       typedef _Ref             reference;
 191       typedef _Slist_node<_Tp> _Node;
 192
 193       explicit
 194       _Slist_iterator(_Node* __x)
 195       : _Slist_iterator_base(__x) {}
 196
 197       _Slist_iterator()
 198       : _Slist_iterator_base(0) {}
 199
 200       _Slist_iterator(const iterator& __x)
 201       : _Slist_iterator_base(__x._M_node) {}
 202
 203       reference
 204       operator*() const
 205       { return ((_Node*) _M_node)->_M_data; }
 206
 207       pointer
 208       operator->() const
 209       { return &(operator*()); }
 210
 211       _Self&
 212       operator++()
 213       {
 214         _M_incr();
 215         return *this;
 216       }
 217
 218       _Self
 219       operator++(int)
 220       {
 221         _Self __tmp = *this;
 222         _M_incr();
 223         return __tmp;
 224       }
 225     };
 226
 227   template <class _Tp, class _Alloc>
 228     struct _Slist_base
 229     : public _Alloc::template rebind<_Slist_node<_Tp> >::other
 230     {
 231       typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other
 232         _Node_alloc;
 233       typedef _Alloc allocator_type;
 234
 235       allocator_type
 236       get_allocator() const
 237       { return *static_cast<const _Node_alloc*>(this); }
 238
 239       _Slist_base(const allocator_type& __a)
 240       : _Node_alloc(__a)
 241       { this->_M_head._M_next = 0; }
 242
 243       ~_Slist_base()
 244       { _M_erase_after(&this->_M_head, 0); }
 245
 246     protected:
 247       _Slist_node_base _M_head;
 248
 249       _Slist_node<_Tp>*
 250       _M_get_node()
 251       { return _Node_alloc::allocate(1); }
 252
 253       void
 254       _M_put_node(_Slist_node<_Tp>* __p)
 255       { _Node_alloc::deallocate(__p, 1); }
 256
 257     protected:
 258       _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
 259       {
 260         _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
 261         _Slist_node_base* __next_next = __next->_M_next;
 262         __pos->_M_next = __next_next;
 263         get_allocator().destroy(&__next->_M_data);
 264         _M_put_node(__next);
 265         return __next_next;
 266       }
 267       _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
 268     };
 269
 270   template <class _Tp, class _Alloc>
 271     _Slist_node_base*
 272     _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
 273                                             _Slist_node_base* __last_node)
 274     {
 275       _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
 276       while (__cur != __last_node)
 277         {
 278           _Slist_node<_Tp>* __tmp = __cur;
 279           __cur = (_Slist_node<_Tp>*) __cur->_M_next;
 280           get_allocator().destroy(&__tmp->_M_data);
 281           _M_put_node(__tmp);
 282         }
 283       __before_first->_M_next = __last_node;
 284       return __last_node;
 285     }
 286
 287   /**
 288    *  This is an SGI extension.
 289    *  @ingroup SGIextensions
 290    *  @doctodo
 291    */
 292   template <class _Tp, class _Alloc = allocator<_Tp> >
 293     class slist : private _Slist_base<_Tp,_Alloc>
 294     {
 295       // concept requirements
 296       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 297
 298     private:
 299       typedef _Slist_base<_Tp,_Alloc> _Base;
 300
 301     public:
 302       typedef _Tp               value_type;
 303       typedef value_type*       pointer;
 304       typedef const value_type* const_pointer;
 305       typedef value_type&       reference;
 306       typedef const value_type& const_reference;
 307       typedef size_t            size_type;
 308       typedef ptrdiff_t         difference_type;
 309
 310       typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
 311       typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
 312
 313       typedef typename _Base::allocator_type allocator_type;
 314
 315       allocator_type
 316       get_allocator() const
 317       { 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*
 325       _M_create_node(const value_type& __x)
 326       {
 327         _Node* __node = this->_M_get_node();
 328         try
 329           {
 330             get_allocator().construct(&__node->_M_data, __x);
 331             __node->_M_next = 0;
 332           }
 333         catch(...)
 334           {
 335             this->_M_put_node(__node);
 336             __throw_exception_again;
 337           }
 338         return __node;
 339       }
 340
 341       _Node*
 342       _M_create_node()
 343       {
 344         _Node* __node = this->_M_get_node();
 345         try
 346           {
 347             get_allocator().construct(&__node->_M_data, value_type());
 348             __node->_M_next = 0;
 349           }
 350         catch(...)
 351           {
 352             this->_M_put_node(__node);
 353             __throw_exception_again;
 354           }
 355         return __node;
 356       }
 357
 358     public:
 359       explicit
 360       slist(const allocator_type& __a = allocator_type())
 361       : _Base(__a) {}
 362
 363       slist(size_type __n, const value_type& __x,
 364             const allocator_type& __a =  allocator_type())
 365       : _Base(__a)
 366       { _M_insert_after_fill(&this->_M_head, __n, __x); }
 367
 368       explicit
 369       slist(size_type __n)
 370       : _Base(allocator_type())
 371       { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
 372
 373       // We don't need any dispatching tricks here, because
 374       // _M_insert_after_range already does them.
 375       template <class _InputIterator>
 376         slist(_InputIterator __first, _InputIterator __last,
 377               const allocator_type& __a =  allocator_type())
 378         : _Base(__a)
 379         { _M_insert_after_range(&this->_M_head, __first, __last); }
 380
 381       slist(const slist& __x)
 382       : _Base(__x.get_allocator())
 383       { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
 384
 385       slist&
 386       operator= (const slist& __x);
 387
 388       ~slist() {}
 389
 390     public:
 391       // assign(), a generalized assignment member function.  Two
 392       // versions: one that takes a count, and one that takes a range.
 393       // The range version is a member template, so we dispatch on whether
 394       // or not the type is an integer.
 395
 396       void
 397       assign(size_type __n, const _Tp& __val)
 398       { _M_fill_assign(__n, __val); }
 399
 400       void
 401       _M_fill_assign(size_type __n, const _Tp& __val);
 402
 403       template <class _InputIterator>
 404         void
 405         assign(_InputIterator __first, _InputIterator __last)
 406         {
 407           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 408           _M_assign_dispatch(__first, __last, _Integral());
 409         }
 410
 411       template <class _Integer>
 412       void
 413       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 414       { _M_fill_assign((size_type) __n, (_Tp) __val); }
 415
 416       template <class _InputIterator>
 417       void
 418       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 419                          __false_type);
 420
 421     public:
 422
 423       iterator
 424       begin()
 425       { return iterator((_Node*)this->_M_head._M_next); }
 426
 427       const_iterator
 428       begin() const
 429       { return const_iterator((_Node*)this->_M_head._M_next);}
 430
 431       iterator
 432       end()
 433       { return iterator(0); }
 434
 435       const_iterator
 436       end() const
 437       { return const_iterator(0); }
 438
 439       // Experimental new feature: before_begin() returns a
 440       // non-dereferenceable iterator that, when incremented, yields
 441       // begin().  This iterator may be used as the argument to
 442       // insert_after, erase_after, etc.  Note that even for an empty
 443       // slist, before_begin() is not the same iterator as end().  It
 444       // is always necessary to increment before_begin() at least once to
 445       // obtain end().
 446       iterator
 447       before_begin()
 448       { return iterator((_Node*) &this->_M_head); }
 449
 450       const_iterator
 451       before_begin() const
 452       { return const_iterator((_Node*) &this->_M_head); }
 453
 454       size_type
 455       size() const
 456       { return __slist_size(this->_M_head._M_next); }
 457
 458       size_type
 459       max_size() const
 460       { return size_type(-1); }
 461
 462       bool
 463       empty() const
 464       { return this->_M_head._M_next == 0; }
 465
 466       void
 467       swap(slist& __x)
 468       { std::swap(this->_M_head._M_next, __x._M_head._M_next); }
 469
 470     public:
 471
 472       reference
 473       front()
 474       { return ((_Node*) this->_M_head._M_next)->_M_data; }
 475
 476       const_reference
 477       front() const
 478       { return ((_Node*) this->_M_head._M_next)->_M_data; }
 479
 480       void
 481       push_front(const value_type& __x)
 482       { __slist_make_link(&this->_M_head, _M_create_node(__x)); }
 483
 484       void
 485       push_front()
 486       { __slist_make_link(&this->_M_head, _M_create_node()); }
 487
 488       void
 489       pop_front()
 490       {
 491         _Node* __node = (_Node*) this->_M_head._M_next;
 492         this->_M_head._M_next = __node->_M_next;
 493         get_allocator().destroy(&__node->_M_data);
 494         this->_M_put_node(__node);
 495       }
 496
 497       iterator
 498       previous(const_iterator __pos)
 499       { return iterator((_Node*) __slist_previous(&this->_M_head,
 500                                                   __pos._M_node)); }
 501
 502       const_iterator
 503       previous(const_iterator __pos) const
 504       { return const_iterator((_Node*) __slist_previous(&this->_M_head,
 505                                                         __pos._M_node)); }
 506
 507     private:
 508       _Node*
 509       _M_insert_after(_Node_base* __pos, const value_type& __x)
 510       { return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); }
 511
 512       _Node*
 513       _M_insert_after(_Node_base* __pos)
 514       { return (_Node*) (__slist_make_link(__pos, _M_create_node())); }
 515
 516       void
 517       _M_insert_after_fill(_Node_base* __pos,
 518                            size_type __n, const value_type& __x)
 519       {
 520         for (size_type __i = 0; __i < __n; ++__i)
 521           __pos = __slist_make_link(__pos, _M_create_node(__x));
 522       }
 523
 524       // Check whether it's an integral type.  If so, it's not an iterator.
 525       template <class _InIterator>
 526         void
 527         _M_insert_after_range(_Node_base* __pos,
 528                               _InIterator __first, _InIterator __last)
 529         {
 530           typedef typename std::__is_integer<_InIterator>::__type _Integral;
 531           _M_insert_after_range(__pos, __first, __last, _Integral());
 532         }
 533
 534       template <class _Integer>
 535         void
 536         _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
 537                               __true_type)
 538         { _M_insert_after_fill(__pos, __n, __x); }
 539
 540       template <class _InIterator>
 541         void
 542         _M_insert_after_range(_Node_base* __pos,
 543                               _InIterator __first, _InIterator __last,
 544                               __false_type)
 545         {
 546           while (__first != __last)
 547             {
 548               __pos = __slist_make_link(__pos, _M_create_node(*__first));
 549               ++__first;
 550             }
 551         }
 552
 553     public:
 554       iterator
 555       insert_after(iterator __pos, const value_type& __x)
 556       { return iterator(_M_insert_after(__pos._M_node, __x)); }
 557
 558       iterator
 559       insert_after(iterator __pos)
 560       { return insert_after(__pos, value_type()); }
 561
 562       void
 563       insert_after(iterator __pos, size_type __n, const value_type& __x)
 564       { _M_insert_after_fill(__pos._M_node, __n, __x); }
 565
 566       // We don't need any dispatching tricks here, because
 567       // _M_insert_after_range already does them.
 568       template <class _InIterator>
 569         void
 570         insert_after(iterator __pos, _InIterator __first, _InIterator __last)
 571         { _M_insert_after_range(__pos._M_node, __first, __last); }
 572
 573       iterator
 574       insert(iterator __pos, const value_type& __x)
 575       { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
 576                                                          __pos._M_node),
 577                                         __x)); }
 578
 579       iterator
 580       insert(iterator __pos)
 581       { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
 582                                                          __pos._M_node),
 583                                         value_type())); }
 584
 585       void
 586       insert(iterator __pos, size_type __n, const value_type& __x)
 587       { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
 588                              __n, __x); }
 589
 590       // We don't need any dispatching tricks here, because
 591       // _M_insert_after_range already does them.
 592       template <class _InIterator>
 593         void
 594         insert(iterator __pos, _InIterator __first, _InIterator __last)
 595         { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node),
 596                                 __first, __last); }
 597
 598     public:
 599       iterator
 600       erase_after(iterator __pos)
 601       { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); }
 602
 603       iterator
 604       erase_after(iterator __before_first, iterator __last)
 605       {
 606         return iterator((_Node*) this->_M_erase_after(__before_first._M_node,
 607                                                       __last._M_node));
 608       }
 609
 610       iterator
 611       erase(iterator __pos)
 612       {
 613         return iterator((_Node*) this->_M_erase_after
 614                         (__slist_previous(&this->_M_head, __pos._M_node)));
 615       }
 616
 617       iterator
 618       erase(iterator __first, iterator __last)
 619       {
 620         return iterator((_Node*) this->_M_erase_after
 621                         (__slist_previous(&this->_M_head, __first._M_node),
 622                          __last._M_node));
 623       }
 624
 625       void
 626       resize(size_type new_size, const _Tp& __x);
 627
 628       void
 629       resize(size_type new_size)
 630       { resize(new_size, _Tp()); }
 631
 632       void
 633       clear()
 634       { this->_M_erase_after(&this->_M_head, 0); }
 635
 636     public:
 637       // Moves the range [__before_first + 1, __before_last + 1) to *this,
 638       //  inserting it immediately after __pos.  This is constant time.
 639       void
 640       splice_after(iterator __pos,
 641                    iterator __before_first, iterator __before_last)
 642       {
 643         if (__before_first != __before_last)
 644           __slist_splice_after(__pos._M_node, __before_first._M_node,
 645                                __before_last._M_node);
 646       }
 647
 648       // Moves the element that follows __prev to *this, inserting it
 649       // immediately after __pos.  This is constant time.
 650       void
 651       splice_after(iterator __pos, iterator __prev)
 652       { __slist_splice_after(__pos._M_node,
 653                              __prev._M_node, __prev._M_node->_M_next); }
 654
 655       // Removes all of the elements from the list __x to *this, inserting
 656       // them immediately after __pos.  __x must not be *this.  Complexity:
 657       // linear in __x.size().
 658       void
 659       splice_after(iterator __pos, slist& __x)
 660       { __slist_splice_after(__pos._M_node, &__x._M_head); }
 661
 662       // Linear in distance(begin(), __pos), and linear in __x.size().
 663       void
 664       splice(iterator __pos, slist& __x)
 665       {
 666         if (__x._M_head._M_next)
 667           __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
 668                                &__x._M_head,
 669                                __slist_previous(&__x._M_head, 0)); }
 670
 671       // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
 672       void
 673       splice(iterator __pos, slist& __x, iterator __i)
 674       { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
 675                              __slist_previous(&__x._M_head, __i._M_node),
 676                              __i._M_node); }
 677
 678       // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
 679       // and in distance(__first, __last).
 680       void
 681       splice(iterator __pos, slist& __x, iterator __first, iterator __last)
 682       {
 683         if (__first != __last)
 684           __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
 685                                __slist_previous(&__x._M_head, __first._M_node),
 686                                __slist_previous(__first._M_node,
 687                                                 __last._M_node));
 688       }
 689
 690     public:
 691       void
 692       reverse()
 693       {
 694         if (this->_M_head._M_next)
 695           this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
 696       }
 697
 698       void
 699       remove(const _Tp& __val);
 700
 701       void
 702       unique();
 703
 704       void
 705       merge(slist& __x);
 706
 707       void
 708       sort();
 709
 710       template <class _Predicate>
 711         void
 712         remove_if(_Predicate __pred);
 713
 714       template <class _BinaryPredicate>
 715         void
 716         unique(_BinaryPredicate __pred);
 717
 718       template <class _StrictWeakOrdering>
 719         void
 720         merge(slist&, _StrictWeakOrdering);
 721
 722       template <class _StrictWeakOrdering>
 723         void
 724         sort(_StrictWeakOrdering __comp);
 725     };
 726
 727   template <class _Tp, class _Alloc>
 728     slist<_Tp, _Alloc>&
 729     slist<_Tp, _Alloc>::operator=(const slist<_Tp, _Alloc>& __x)
 730     {
 731       if (&__x != this)
 732         {
 733           _Node_base* __p1 = &this->_M_head;
 734           _Node* __n1 = (_Node*) this->_M_head._M_next;
 735           const _Node* __n2 = (const _Node*) __x._M_head._M_next;
 736           while (__n1 && __n2)
 737             {
 738               __n1->_M_data = __n2->_M_data;
 739               __p1 = __n1;
 740               __n1 = (_Node*) __n1->_M_next;
 741               __n2 = (const _Node*) __n2->_M_next;
 742             }
 743           if (__n2 == 0)
 744             this->_M_erase_after(__p1, 0);
 745           else
 746             _M_insert_after_range(__p1, const_iterator((_Node*)__n2),
 747                                   const_iterator(0));
 748         }
 749       return *this;
 750     }
 751
 752   template <class _Tp, class _Alloc>
 753     void
 754     slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val)
 755     {
 756       _Node_base* __prev = &this->_M_head;
 757       _Node* __node = (_Node*) this->_M_head._M_next;
 758       for (; __node != 0 && __n > 0; --__n)
 759         {
 760           __node->_M_data = __val;
 761           __prev = __node;
 762           __node = (_Node*) __node->_M_next;
 763         }
 764       if (__n > 0)
 765         _M_insert_after_fill(__prev, __n, __val);
 766       else
 767         this->_M_erase_after(__prev, 0);
 768     }
 769
 770   template <class _Tp, class _Alloc>
 771     template <class _InputIterator>
 772       void
 773       slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first,
 774                                              _InputIterator __last,
 775                                              __false_type)
 776       {
 777         _Node_base* __prev = &this->_M_head;
 778         _Node* __node = (_Node*) this->_M_head._M_next;
 779         while (__node != 0 && __first != __last)
 780           {
 781             __node->_M_data = *__first;
 782             __prev = __node;
 783             __node = (_Node*) __node->_M_next;
 784             ++__first;
 785           }
 786         if (__first != __last)
 787           _M_insert_after_range(__prev, __first, __last);
 788         else
 789           this->_M_erase_after(__prev, 0);
 790       }
 791
 792   template <class _Tp, class _Alloc>
 793     inline bool
 794     operator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
 795     {
 796       typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
 797       const_iterator __end1 = _SL1.end();
 798       const_iterator __end2 = _SL2.end();
 799
 800       const_iterator __i1 = _SL1.begin();
 801       const_iterator __i2 = _SL2.begin();
 802       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
 803         {
 804           ++__i1;
 805           ++__i2;
 806         }
 807       return __i1 == __end1 && __i2 == __end2;
 808     }
 809
 810
 811   template <class _Tp, class _Alloc>
 812     inline bool
 813     operator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
 814     { return std::lexicographical_compare(_SL1.begin(), _SL1.end(),
 815                                           _SL2.begin(), _SL2.end()); }
 816
 817   template <class _Tp, class _Alloc>
 818     inline bool
 819     operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
 820     { return !(_SL1 == _SL2); }
 821
 822   template <class _Tp, class _Alloc>
 823     inline bool
 824     operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
 825     { return _SL2 < _SL1; }
 826
 827   template <class _Tp, class _Alloc>
 828     inline bool
 829     operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
 830     { return !(_SL2 < _SL1); }
 831
 832   template <class _Tp, class _Alloc>
 833     inline bool
 834     operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
 835     { return !(_SL1 < _SL2); }
 836
 837   template <class _Tp, class _Alloc>
 838     inline void
 839     swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y)
 840     { __x.swap(__y); }
 841
 842   template <class _Tp, class _Alloc>
 843     void
 844     slist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x)
 845     {
 846       _Node_base* __cur = &this->_M_head;
 847       while (__cur->_M_next != 0 && __len > 0)
 848         {
 849           --__len;
 850           __cur = __cur->_M_next;
 851         }
 852       if (__cur->_M_next)
 853         this->_M_erase_after(__cur, 0);
 854       else
 855         _M_insert_after_fill(__cur, __len, __x);
 856     }
 857
 858   template <class _Tp, class _Alloc>
 859     void
 860     slist<_Tp, _Alloc>::remove(const _Tp& __val)
 861     {
 862       _Node_base* __cur = &this->_M_head;
 863       while (__cur && __cur->_M_next)
 864         {
 865           if (((_Node*) __cur->_M_next)->_M_data == __val)
 866             this->_M_erase_after(__cur);
 867           else
 868             __cur = __cur->_M_next;
 869         }
 870     }
 871
 872   template <class _Tp, class _Alloc>
 873     void
 874     slist<_Tp, _Alloc>::unique()
 875     {
 876       _Node_base* __cur = this->_M_head._M_next;
 877       if (__cur)
 878         {
 879           while (__cur->_M_next)
 880             {
 881               if (((_Node*)__cur)->_M_data
 882                   == ((_Node*)(__cur->_M_next))->_M_data)
 883                 this->_M_erase_after(__cur);
 884               else
 885                 __cur = __cur->_M_next;
 886             }
 887         }
 888     }
 889
 890   template <class _Tp, class _Alloc>
 891     void
 892     slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x)
 893     {
 894       _Node_base* __n1 = &this->_M_head;
 895       while (__n1->_M_next && __x._M_head._M_next)
 896         {
 897           if (((_Node*) __x._M_head._M_next)->_M_data
 898               < ((_Node*) __n1->_M_next)->_M_data)
 899             __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
 900           __n1 = __n1->_M_next;
 901         }
 902       if (__x._M_head._M_next)
 903         {
 904           __n1->_M_next = __x._M_head._M_next;
 905           __x._M_head._M_next = 0;
 906         }
 907     }
 908
 909   template <class _Tp, class _Alloc>
 910     void
 911     slist<_Tp, _Alloc>::sort()
 912     {
 913       if (this->_M_head._M_next && this->_M_head._M_next->_M_next)
 914         {
 915           slist __carry;
 916           slist __counter[64];
 917           int __fill = 0;
 918           while (!empty())
 919             {
 920               __slist_splice_after(&__carry._M_head,
 921                                    &this->_M_head, this->_M_head._M_next);
 922               int __i = 0;
 923               while (__i < __fill && !__counter[__i].empty())
 924                 {
 925                   __counter[__i].merge(__carry);
 926                   __carry.swap(__counter[__i]);
 927                   ++__i;
 928                 }
 929               __carry.swap(__counter[__i]);
 930               if (__i == __fill)
 931                 ++__fill;
 932             }
 933
 934           for (int __i = 1; __i < __fill; ++__i)
 935             __counter[__i].merge(__counter[__i-1]);
 936           this->swap(__counter[__fill-1]);
 937         }
 938     }
 939
 940   template <class _Tp, class _Alloc>
 941     template <class _Predicate>
 942       void slist<_Tp, _Alloc>::remove_if(_Predicate __pred)
 943       {
 944         _Node_base* __cur = &this->_M_head;
 945         while (__cur->_M_next)
 946           {
 947             if (__pred(((_Node*) __cur->_M_next)->_M_data))
 948               this->_M_erase_after(__cur);
 949             else
 950               __cur = __cur->_M_next;
 951           }
 952       }
 953
 954   template <class _Tp, class _Alloc>
 955     template <class _BinaryPredicate>
 956       void
 957       slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred)
 958       {
 959         _Node* __cur = (_Node*) this->_M_head._M_next;
 960         if (__cur)
 961           {
 962             while (__cur->_M_next)
 963               {
 964                 if (__pred(((_Node*)__cur)->_M_data,
 965                            ((_Node*)(__cur->_M_next))->_M_data))
 966                   this->_M_erase_after(__cur);
 967                 else
 968                   __cur = (_Node*) __cur->_M_next;
 969               }
 970           }
 971       }
 972
 973   template <class _Tp, class _Alloc>
 974     template <class _StrictWeakOrdering>
 975       void
 976       slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x,
 977                                _StrictWeakOrdering __comp)
 978       {
 979         _Node_base* __n1 = &this->_M_head;
 980         while (__n1->_M_next && __x._M_head._M_next)
 981           {
 982             if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
 983                        ((_Node*) __n1->_M_next)->_M_data))
 984               __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
 985             __n1 = __n1->_M_next;
 986           }
 987         if (__x._M_head._M_next)
 988           {
 989             __n1->_M_next = __x._M_head._M_next;
 990             __x._M_head._M_next = 0;
 991           }
 992       }
 993
 994   template <class _Tp, class _Alloc>
 995     template <class _StrictWeakOrdering>
 996       void
 997       slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
 998       {
 999         if (this->_M_head._M_next && this->_M_head._M_next->_M_next)
1000           {
1001             slist __carry;
1002             slist __counter[64];
1003             int __fill = 0;
1004             while (!empty())
1005               {
1006                 __slist_splice_after(&__carry._M_head,
1007                                      &this->_M_head, this->_M_head._M_next);
1008                 int __i = 0;
1009                 while (__i < __fill && !__counter[__i].empty())
1010                   {
1011                     __counter[__i].merge(__carry, __comp);
1012                     __carry.swap(__counter[__i]);
1013                     ++__i;
1014                   }
1015                 __carry.swap(__counter[__i]);
1016                 if (__i == __fill)
1017                   ++__fill;
1018               }
1019
1020             for (int __i = 1; __i < __fill; ++__i)
1021               __counter[__i].merge(__counter[__i-1], __comp);
1022             this->swap(__counter[__fill-1]);
1023           }
1024       }
1025
1026 } // namespace __gnu_cxx
1027
1028 namespace std
1029 {
1030   // Specialization of insert_iterator so that insertions will be constant
1031   // time rather than linear time.
1032
1033   template <class _Tp, class _Alloc>
1034     class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> >
1035     {
1036     protected:
1037       typedef __gnu_cxx::slist<_Tp, _Alloc> _Container;
1038       _Container* container;
1039       typename _Container::iterator iter;
1040
1041     public:
1042       typedef _Container          container_type;
1043       typedef output_iterator_tag iterator_category;
1044       typedef void                value_type;
1045       typedef void                difference_type;
1046       typedef void                pointer;
1047       typedef void                reference;
1048
1049       insert_iterator(_Container& __x, typename _Container::iterator __i)
1050       : container(&__x)
1051       {
1052         if (__i == __x.begin())
1053           iter = __x.before_begin();
1054         else
1055           iter = __x.previous(__i);
1056       }
1057
1058       insert_iterator<_Container>&
1059       operator=(const typename _Container::value_type& __value)
1060       {
1061         iter = container->insert_after(iter, __value);
1062         return *this;
1063       }
1064
1065       insert_iterator<_Container>&
1066       operator*()
1067       { return *this; }
1068
1069       insert_iterator<_Container>&
1070       operator++()
1071       { return *this; }
1072
1073       insert_iterator<_Container>&
1074       operator++(int)
1075       { return *this; }
1076 };
1077
1078 } // namespace std
1079 #endif