libstdc++-v3/include/ext/slist

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