libstdc++-v3/include/ext/slist

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