libstdc++-v3/include/ext/slist

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