libstdc++/stl/slist.h

   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 #ifndef __SGI_STL_SLIST_H
  16 #define __SGI_STL_SLIST_H
  17
  18 #include <algobase.h>
  19 #include <alloc.h>
  20
  21 struct __slist_node_base
  22 {
  23   __slist_node_base* next;
  24 };
  25
  26 inline __slist_node_base* __slist_make_link(__slist_node_base* prev_node,
  27                                             __slist_node_base* new_node)
  28 {
  29   new_node->next = prev_node->next;
  30   prev_node->next = new_node;
  31   return new_node;
  32 }
  33
  34 inline __slist_node_base* __slist_previous(__slist_node_base* head,
  35                                            const __slist_node_base* node)
  36 {
  37   while (head && head->next != node)
  38     head = head->next;
  39   return head;
  40 }
  41
  42 inline const __slist_node_base* __slist_previous(const __slist_node_base* head,
  43                                                  const __slist_node_base* node)
  44 {
  45   while (head && head->next != node)
  46     head = head->next;
  47   return head;
  48 }
  49
  50 inline void __slist_splice_after(__slist_node_base* pos,
  51                                  __slist_node_base* before_first,
  52                                  __slist_node_base* before_last)
  53 {
  54   if (pos != before_first && pos != before_last) {
  55     __slist_node_base* first = before_first->next;
  56     __slist_node_base* after = pos->next;
  57     before_first->next = before_last->next;
  58     pos->next = first;
  59     before_last->next = after;
  60   }
  61 }
  62
  63 inline __slist_node_base* __slist_reverse(__slist_node_base* node)
  64 {
  65   __slist_node_base* result = node;
  66   node = node->next;
  67   result->next = 0;
  68   while(node) {
  69     __slist_node_base* next = node->next;
  70     node->next = result;
  71     result = node;
  72     node = next;
  73   }
  74   return result;
  75 }
  76
  77 template <class T>
  78 struct __slist_node : public __slist_node_base
  79 {
  80   T data;
  81 };
  82
  83 struct __slist_iterator_base
  84 {
  85   typedef size_t size_type;
  86   typedef ptrdiff_t difference_type;
  87   typedef forward_iterator_tag iterator_category;
  88
  89   __slist_node_base* node;
  90
  91   __slist_iterator_base(__slist_node_base* x) : node(x) {}
  92   void incr() { node = node->next; }
  93
  94   bool operator==(const __slist_iterator_base& x) const {
  95     return node == x.node;
  96   }
  97   bool operator!=(const __slist_iterator_base& x) const {
  98     return node != x.node;
  99   }
 100 };
 101
 102 template <class T, class Ref, class Ptr>
 103 struct __slist_iterator : public __slist_iterator_base
 104 {
 105   typedef __slist_iterator<T, T&, T*>             iterator;
 106   typedef __slist_iterator<T, const T&, const T*> const_iterator;
 107   typedef __slist_iterator<T, Ref, Ptr>           self;
 108
 109   typedef T value_type;
 110   typedef Ptr pointer;
 111   typedef Ref reference;
 112   typedef __slist_node<T> list_node;
 113
 114   __slist_iterator(list_node* x) : __slist_iterator_base(x) {}
 115   __slist_iterator() : __slist_iterator_base(0) {}
 116   __slist_iterator(const iterator& x) : __slist_iterator_base(x.node) {}
 117
 118   reference operator*() const { return ((list_node*) node)->data; }
 119 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 120   pointer operator->() const { return &(operator*()); }
 121 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 122
 123   self& operator++()
 124   {
 125     incr();
 126     return *this;
 127   }
 128   self operator++(int)
 129   {
 130     self tmp = *this;
 131     incr();
 132     return tmp;
 133   }
 134 };
 135
 136 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 137
 138 inline ptrdiff_t*
 139 distance_type(const __slist_iterator_base&)
 140 {
 141   return 0;
 142 }
 143
 144 inline forward_iterator_tag
 145 iterator_category(const __slist_iterator_base&)
 146 {
 147   return forward_iterator_tag();
 148 }
 149
 150 template <class T, class Ref, class Ptr>
 151 inline T*
 152 value_type(const __slist_iterator<T, Ref, Ptr>&) {
 153   return 0;
 154 }
 155
 156 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 157
 158 inline size_t __slist_size(__slist_node_base* node)
 159 {
 160   size_t result = 0;
 161   for ( ; node != 0; node = node->next)
 162     ++result;
 163   return result;
 164 }
 165
 166 template <class T, class Alloc = alloc>
 167 class slist
 168 {
 169 public:
 170   typedef T value_type;
 171   typedef value_type* pointer;
 172   typedef value_type& reference;
 173   typedef const value_type& const_reference;
 174   typedef size_t size_type;
 175   typedef ptrdiff_t difference_type;
 176
 177   typedef __slist_iterator<T, T&, T*>             iterator;
 178   typedef __slist_iterator<T, const T&, const T*> const_iterator;
 179
 180 private:
 181   typedef __slist_node<T> list_node;
 182   typedef __slist_node_base list_node_base;
 183   typedef __slist_iterator_base iterator_base;
 184   typedef simple_alloc<list_node, Alloc> list_node_allocator;
 185
 186   static list_node* create_node(const value_type& x) {
 187     list_node* node = list_node_allocator::allocate();
 188 #       ifdef __STL_USE_EXCEPTIONS
 189     try {
 190 #       endif /* __STL_USE_EXCEPTIONS */
 191       construct(&node->data, x);
 192       node->next = 0;
 193       return node;
 194 #       ifdef __STL_USE_EXCEPTIONS
 195     }
 196     catch(...) {
 197       list_node_allocator::deallocate(node);
 198       throw;
 199     }
 200 #       endif /* __STL_USE_EXCEPTIONS */
 201   }
 202
 203   static void destroy_node(list_node* node) {
 204     destroy(&node->data);
 205     list_node_allocator::deallocate(node);
 206   }
 207
 208   void fill_initialize(size_type n, const value_type& x) {
 209     head.next = 0;
 210 #       ifdef __STL_USE_EXCEPTIONS
 211     try {
 212 #       endif /* __STL_USE_EXCEPTIONS */
 213       _insert_after_fill(&head, n, x);
 214 #       ifdef __STL_USE_EXCEPTIONS
 215     }
 216     catch(...) {
 217       clear();
 218       throw;
 219     }
 220 #       endif /* __STL_USE_EXCEPTIONS */
 221   }
 222
 223 #ifdef __STL_MEMBER_TEMPLATES
 224   template <class InputIterator>
 225   void range_initialize(InputIterator first, InputIterator last) {
 226     head.next = 0;
 227 #       ifdef __STL_USE_EXCEPTIONS
 228     try {
 229 #       endif /* __STL_USE_EXCEPTIONS */
 230       _insert_after_range(&head, first, last);
 231 #       ifdef __STL_USE_EXCEPTIONS
 232     }
 233     catch(...) {
 234       clear();
 235       throw;
 236     }
 237 #       endif /* __STL_USE_EXCEPTIONS */
 238   }
 239 #else /* __STL_MEMBER_TEMPLATES */
 240   void range_initialize(const value_type* first, const value_type* last) {
 241     head.next = 0;
 242 #       ifdef __STL_USE_EXCEPTIONS
 243     try {
 244 #       endif /* __STL_USE_EXCEPTIONS */
 245       _insert_after_range(&head, first, last);
 246 #       ifdef __STL_USE_EXCEPTIONS
 247     }
 248     catch(...) {
 249       clear();
 250       throw;
 251     }
 252 #       endif /* __STL_USE_EXCEPTIONS */
 253   }
 254   void range_initialize(const_iterator first, const_iterator last) {
 255     head.next = 0;
 256 #       ifdef __STL_USE_EXCEPTIONS
 257     try {
 258 #       endif /* __STL_USE_EXCEPTIONS */
 259       _insert_after_range(&head, first, last);
 260 #       ifdef __STL_USE_EXCEPTIONS
 261     }
 262     catch(...) {
 263       clear();
 264       throw;
 265     }
 266 #       endif /* __STL_USE_EXCEPTIONS */
 267   }
 268 #endif /* __STL_MEMBER_TEMPLATES */
 269
 270 private:
 271   list_node_base head;
 272
 273 public:
 274   slist() { head.next = 0; }
 275
 276   slist(size_type n, const value_type& x) { fill_initialize(n, x); }
 277   slist(int n, const value_type& x) { fill_initialize(n, x); }
 278   slist(long n, const value_type& x) { fill_initialize(n, x); }
 279   explicit slist(size_type n) { fill_initialize(n, value_type()); }
 280
 281 #ifdef __STL_MEMBER_TEMPLATES
 282   template <class InputIterator>
 283   slist(InputIterator first, InputIterator last) {
 284     range_initialize(first, last);
 285   }
 286
 287 #else /* __STL_MEMBER_TEMPLATES */
 288   slist(const_iterator first, const_iterator last) {
 289     range_initialize(first, last);
 290   }
 291   slist(const value_type* first, const value_type* last) {
 292     range_initialize(first, last);
 293   }
 294 #endif /* __STL_MEMBER_TEMPLATES */
 295
 296   slist(const slist& L) { range_initialize(L.begin(), L.end()); }
 297
 298   slist& operator= (const slist& L);
 299
 300   ~slist() { clear(); }
 301
 302 public:
 303
 304   iterator begin() { return iterator((list_node*)head.next); }
 305   const_iterator begin() const { return const_iterator((list_node*)head.next);}
 306
 307   iterator end() { return iterator(0); }
 308   const_iterator end() const { return const_iterator(0); }
 309
 310   size_type size() const { return __slist_size(head.next); }
 311
 312   size_type max_size() const { return size_type(-1); }
 313
 314   bool empty() const { return head.next == 0; }
 315
 316   void swap(slist& L)
 317   {
 318     list_node_base* tmp = head.next;
 319     head.next = L.head.next;
 320     L.head.next = tmp;
 321   }
 322
 323 public:
 324   friend bool operator==(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2);
 325
 326 public:
 327
 328   reference front() { return ((list_node*) head.next)->data; }
 329   const_reference front() const { return ((list_node*) head.next)->data; }
 330   void push_front(const value_type& x)   {
 331     __slist_make_link(&head, create_node(x));
 332   }
 333   void pop_front() {
 334     list_node* node = (list_node*) head.next;
 335     head.next = node->next;
 336     destroy_node(node);
 337   }
 338
 339   iterator previous(const_iterator pos) {
 340     return iterator((list_node*) __slist_previous(&head, pos.node));
 341   }
 342   const_iterator previous(const_iterator pos) const {
 343     return const_iterator((list_node*) __slist_previous(&head, pos.node));
 344   }
 345
 346 private:
 347   list_node* _insert_after(list_node_base* pos, const value_type& x) {
 348     return (list_node*) (__slist_make_link(pos, create_node(x)));
 349   }
 350
 351   void _insert_after_fill(list_node_base* pos,
 352                           size_type n, const value_type& x) {
 353     for (size_type i = 0; i < n; ++i)
 354       pos = __slist_make_link(pos, create_node(x));
 355   }
 356
 357 #ifdef __STL_MEMBER_TEMPLATES
 358   template <class InIter>
 359   void _insert_after_range(list_node_base* pos, InIter first, InIter last) {
 360     while (first != last) {
 361       pos = __slist_make_link(pos, create_node(*first));
 362       ++first;
 363     }
 364   }
 365 #else /* __STL_MEMBER_TEMPLATES */
 366   void _insert_after_range(list_node_base* pos,
 367                            const_iterator first, const_iterator last) {
 368     while (first != last) {
 369       pos = __slist_make_link(pos, create_node(*first));
 370       ++first;
 371     }
 372   }
 373   void _insert_after_range(list_node_base* pos,
 374                            const value_type* first, const value_type* last) {
 375     while (first != last) {
 376       pos = __slist_make_link(pos, create_node(*first));
 377       ++first;
 378     }
 379   }
 380 #endif /* __STL_MEMBER_TEMPLATES */
 381
 382   void erase_after(list_node_base* pos) {
 383     list_node* next = (list_node*) (pos->next);
 384     pos->next = next->next;
 385     destroy_node(next);
 386   }
 387
 388   void erase_after(list_node_base* before_first, list_node_base* last_node) {
 389     list_node* cur = (list_node*) (before_first->next);
 390     while (cur != last_node) {
 391       list_node* tmp = cur;
 392       cur = (list_node*) cur->next;
 393       destroy_node(tmp);
 394     }
 395     before_first->next = last_node;
 396   }
 397
 398
 399 public:
 400
 401   iterator insert_after(iterator pos, const value_type& x) {
 402     return iterator(_insert_after(pos.node, x));
 403   }
 404
 405   iterator insert_after(iterator pos) {
 406     return insert_after(pos, value_type());
 407   }
 408
 409   void insert_after(iterator pos, size_type n, const value_type& x) {
 410     _insert_after_fill(pos.node, n, x);
 411   }
 412   void insert_after(iterator pos, int n, const value_type& x) {
 413     _insert_after_fill(pos.node, (size_type) n, x);
 414   }
 415   void insert_after(iterator pos, long n, const value_type& x) {
 416     _insert_after_fill(pos.node, (size_type) n, x);
 417   }
 418
 419 #ifdef __STL_MEMBER_TEMPLATES
 420   template <class InIter>
 421   void insert_after(iterator pos, InIter first, InIter last) {
 422     _insert_after_range(pos.node, first, last);
 423   }
 424 #else /* __STL_MEMBER_TEMPLATES */
 425   void insert_after(iterator pos, const_iterator first, const_iterator last) {
 426     _insert_after_range(pos.node, first, last);
 427   }
 428   void insert_after(iterator pos,
 429                     const value_type* first, const value_type* last) {
 430     _insert_after_range(pos.node, first, last);
 431   }
 432 #endif /* __STL_MEMBER_TEMPLATES */
 433
 434   iterator insert(iterator pos, const value_type& x) {
 435     return iterator(_insert_after(__slist_previous(&head, pos.node), x));
 436   }
 437
 438   iterator insert(iterator pos) {
 439     return iterator(_insert_after(__slist_previous(&head, pos.node),
 440                                   value_type()));
 441   }
 442
 443   void insert(iterator pos, size_type n, const value_type& x) {
 444     _insert_after_fill(__slist_previous(&head, pos.node), n, x);
 445   }
 446   void insert(iterator pos, int n, const value_type& x) {
 447     _insert_after_fill(__slist_previous(&head, pos.node), (size_type) n, x);
 448   }
 449   void insert(iterator pos, long n, const value_type& x) {
 450     _insert_after_fill(__slist_previous(&head, pos.node), (size_type) n, x);
 451   }
 452
 453 #ifdef __STL_MEMBER_TEMPLATES
 454   template <class InIter>
 455   void insert(iterator pos, InIter first, InIter last) {
 456     _insert_after_range(__slist_previous(&head, pos.node), first, last);
 457   }
 458 #else /* __STL_MEMBER_TEMPLATES */
 459   void insert(iterator pos, const_iterator first, const_iterator last) {
 460     _insert_after_range(__slist_previous(&head, pos.node), first, last);
 461   }
 462   void insert(iterator pos, const value_type* first, const value_type* last) {
 463     _insert_after_range(__slist_previous(&head, pos.node), first, last);
 464   }
 465 #endif /* __STL_MEMBER_TEMPLATES */
 466
 467
 468 public:
 469   void erase_after(iterator pos) { erase_after(pos.node); }
 470   void erase_after(iterator before_first, iterator last) {
 471     erase_after(before_first.node, last.node);
 472   }
 473
 474   void erase(iterator pos) { erase_after(__slist_previous(&head, pos.node)); }
 475   void erase(iterator first, iterator last) {
 476     erase_after(__slist_previous(&head, first.node), last.node);
 477   }
 478
 479   void resize(size_type new_size, const T& x);
 480   void resize(size_type new_size) { resize(new_size, T()); }
 481   void clear() { erase_after(&head, 0); }
 482
 483 public:
 484   // Moves the range [before_first + 1, before_last + 1) to *this,
 485   //  inserting it immediately after pos.  This is constant time.
 486   void splice_after(iterator pos,
 487                     iterator before_first, iterator before_last)
 488   {
 489     if (before_first != before_last)
 490       __slist_splice_after(pos.node, before_first.node, before_last.node);
 491   }
 492
 493   // Moves the element that follows prev to *this, inserting it immediately
 494   //  after pos.  This is constant time.
 495   void splice_after(iterator pos, iterator prev)
 496   {
 497     __slist_splice_after(pos.node, prev.node, prev.node->next);
 498   }
 499
 500
 501   // Linear in distance(begin(), pos), and linear in L.size().
 502   void splice(iterator pos, slist& L) {
 503     if (L.head.next)
 504       __slist_splice_after(__slist_previous(&head, pos.node),
 505                            &L.head,
 506                            __slist_previous(&L.head, 0));
 507   }
 508
 509   // Linear in distance(begin(), pos), and in distance(L.begin(), i).
 510   void splice(iterator pos, slist& L, iterator i) {
 511     __slist_splice_after(__slist_previous(&head, pos.node),
 512                          __slist_previous(&L.head, i.node),
 513                          i.node);
 514   }
 515
 516   // Linear in distance(begin(), pos), in distance(L.begin(), first),
 517   // and in distance(first, last).
 518   void splice(iterator pos, slist& L, iterator first, iterator last)
 519   {
 520     if (first != last)
 521       __slist_splice_after(__slist_previous(&head, pos.node),
 522                            __slist_previous(&L.head, first.node),
 523                            __slist_previous(first.node, last.node));
 524   }
 525
 526 public:
 527   void reverse() { if (head.next) head.next = __slist_reverse(head.next); }
 528
 529   void remove(const T& val);
 530   void unique();
 531   void merge(slist& L);
 532   void sort();
 533
 534 #ifdef __STL_MEMBER_TEMPLATES
 535   template <class Predicate> void remove_if(Predicate pred);
 536   template <class BinaryPredicate> void unique(BinaryPredicate pred);
 537   template <class StrictWeakOrdering> void merge(slist&, StrictWeakOrdering);
 538   template <class StrictWeakOrdering> void sort(StrictWeakOrdering comp);
 539 #endif /* __STL_MEMBER_TEMPLATES */
 540 };
 541
 542 template <class T, class Alloc>
 543 slist<T, Alloc>& slist<T,Alloc>::operator=(const slist<T, Alloc>& L)
 544 {
 545   if (&L != this) {
 546     list_node_base* p1 = &head;
 547     list_node* n1 = (list_node*) head.next;
 548     const list_node* n2 = (const list_node*) L.head.next;
 549     while (n1 && n2) {
 550       n1->data = n2->data;
 551       p1 = n1;
 552       n1 = (list_node*) n1->next;
 553       n2 = (const list_node*) n2->next;
 554     }
 555     if (n2 == 0)
 556       erase_after(p1, 0);
 557     else
 558       _insert_after_range(p1,
 559                           const_iterator((list_node*)n2), const_iterator(0));
 560   }
 561   return *this;
 562 }
 563
 564 template <class T, class Alloc>
 565 bool operator==(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2)
 566 {
 567   typedef typename slist<T,Alloc>::list_node list_node;
 568   list_node* n1 = (list_node*) L1.head.next;
 569   list_node* n2 = (list_node*) L2.head.next;
 570   while (n1 && n2 && n1->data == n2->data) {
 571     n1 = (list_node*) n1->next;
 572     n2 = (list_node*) n2->next;
 573   }
 574   return n1 == 0 && n2 == 0;
 575 }
 576
 577 template <class T, class Alloc>
 578 inline bool operator<(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2)
 579 {
 580   return lexicographical_compare(L1.begin(), L1.end(), L2.begin(), L2.end());
 581 }
 582
 583 template <class T, class Alloc>
 584 void slist<T, Alloc>::resize(size_type len, const T& x)
 585 {
 586   list_node_base* cur = &head;
 587   while (cur->next != 0 && len > 0) {
 588     --len;
 589     cur = cur->next;
 590   }
 591   if (cur->next)
 592     erase_after(cur, 0);
 593   else
 594     _insert_after_fill(cur, len, x);
 595 }
 596
 597 template <class T, class Alloc>
 598 void slist<T,Alloc>::remove(const T& val)
 599 {
 600   list_node_base* cur = &head;
 601   while (cur && cur->next) {
 602     if (((list_node*) cur->next)->data == val)
 603       erase_after(cur);
 604     else
 605       cur = cur->next;
 606   }
 607 }
 608
 609 template <class T, class Alloc>
 610 void slist<T,Alloc>::unique()
 611 {
 612   list_node_base* cur = head.next;
 613   if (cur) {
 614     while (cur->next) {
 615       if (((list_node*)cur)->data == ((list_node*)(cur->next))->data)
 616         erase_after(cur);
 617       else
 618         cur = cur->next;
 619     }
 620   }
 621 }
 622
 623 template <class T, class Alloc>
 624 void slist<T,Alloc>::merge(slist<T,Alloc>& L)
 625 {
 626   list_node_base* n1 = &head;
 627   while (n1->next && L.head.next) {
 628     if (((list_node*) L.head.next)->data < ((list_node*) n1->next)->data)
 629       __slist_splice_after(n1, &L.head, L.head.next);
 630     n1 = n1->next;
 631   }
 632   if (L.head.next) {
 633     n1->next = L.head.next;
 634     L.head.next = 0;
 635   }
 636 }
 637
 638 template <class T, class Alloc>
 639 void slist<T,Alloc>::sort()
 640 {
 641   if (head.next && head.next->next) {
 642     slist carry;
 643     slist counter[64];
 644     int fill = 0;
 645     while (!empty()) {
 646       __slist_splice_after(&carry.head, &head, head.next);
 647       int i = 0;
 648       while (i < fill && !counter[i].empty()) {
 649         counter[i].merge(carry);
 650         carry.swap(counter[i]);
 651         ++i;
 652       }
 653       carry.swap(counter[i]);
 654       if (i == fill)
 655         ++fill;
 656     }
 657
 658     for (int i = 1; i < fill; ++i)
 659       counter[i].merge(counter[i-1]);
 660     this->swap(counter[fill-1]);
 661   }
 662 }
 663
 664 #ifdef __STL_MEMBER_TEMPLATES
 665
 666 template <class T, class Alloc>
 667 template <class Predicate> void slist<T,Alloc>::remove_if(Predicate pred)
 668 {
 669   list_node_base* cur = &head;
 670   while (cur->next) {
 671     if (pred(((list_node*) cur->next)->data))
 672       erase_after(cur);
 673     else
 674       cur = cur->next;
 675   }
 676 }
 677
 678 template <class T, class Alloc> template <class BinaryPredicate>
 679 void slist<T,Alloc>::unique(BinaryPredicate pred)
 680 {
 681   list_node* cur = (list_node*) head.next;
 682   if (cur) {
 683     while (cur->next) {
 684       if (pred(((list_node*)cur)->data, ((list_node*)(cur->next))->data))
 685         erase_after(cur);
 686       else
 687         cur = (list_node*) cur->next;
 688     }
 689   }
 690 }
 691
 692 template <class T, class Alloc> template <class StrictWeakOrdering>
 693 void slist<T,Alloc>::merge(slist<T,Alloc>& L, StrictWeakOrdering comp)
 694 {
 695   list_node_base* n1 = &head;
 696   while (n1->next && L.head.next) {
 697     if (comp(((list_node*) L.head.next)->data,
 698              ((list_node*) n1->next)->data))
 699       __slist_splice_after(n1, &L.head, L.head.next);
 700     n1 = n1->next;
 701   }
 702   if (L.head.next) {
 703     n1->next = L.head.next;
 704     L.head.next = 0;
 705   }
 706 }
 707
 708 template <class T, class Alloc> template <class StrictWeakOrdering>
 709 void slist<T,Alloc>::sort(StrictWeakOrdering comp)
 710 {
 711   if (head.next && head.next->next) {
 712     slist carry;
 713     slist counter[64];
 714     int fill = 0;
 715     while (!empty()) {
 716       __slist_splice_after(&carry.head, &head, head.next);
 717       int i = 0;
 718       while (i < fill && !counter[i].empty()) {
 719         counter[i].merge(carry, comp);
 720         carry.swap(counter[i]);
 721         ++i;
 722       }
 723       carry.swap(counter[i]);
 724       if (i == fill)
 725         ++fill;
 726     }
 727
 728     for (int i = 1; i < fill; ++i)
 729       counter[i].merge(counter[i-1], comp);
 730     this->swap(counter[fill-1]);
 731   }
 732 }
 733
 734 #endif /* __STL_MEMBER_TEMPLATES */
 735
 736 #endif /* __SGI_STL_SLIST_H */