libstdc++-v3/include/ext/slist

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