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