libstdc++-v3/include/bits/stl_list.h

   1 // 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  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1996,1997
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /** @file stl_list.h
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  */
  60
  61 #ifndef __SGI_STL_INTERNAL_LIST_H
  62 #define __SGI_STL_INTERNAL_LIST_H
  63
  64 #include <bits/concept_check.h>
  65
  66 namespace std
  67 {
  68
  69 struct _List_node_base {
  70   _List_node_base* _M_next;
  71   _List_node_base* _M_prev;
  72 };
  73
  74 template <class _Tp>
  75 struct _List_node : public _List_node_base {
  76   _Tp _M_data;
  77 };
  78
  79 struct _List_iterator_base {
  80   typedef size_t                     size_type;
  81   typedef ptrdiff_t                  difference_type;
  82   typedef bidirectional_iterator_tag iterator_category;
  83
  84   _List_node_base* _M_node;
  85
  86   _List_iterator_base(_List_node_base* __x) : _M_node(__x) {}
  87   _List_iterator_base() {}
  88
  89   void _M_incr() { _M_node = _M_node->_M_next; }
  90   void _M_decr() { _M_node = _M_node->_M_prev; }
  91
  92   bool operator==(const _List_iterator_base& __x) const {
  93     return _M_node == __x._M_node;
  94   }
  95   bool operator!=(const _List_iterator_base& __x) const {
  96     return _M_node != __x._M_node;
  97   }
  98 };
  99
 100 template<class _Tp, class _Ref, class _Ptr>
 101 struct _List_iterator : public _List_iterator_base {
 102   typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
 103   typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
 104   typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;
 105
 106   typedef _Tp value_type;
 107   typedef _Ptr pointer;
 108   typedef _Ref reference;
 109   typedef _List_node<_Tp> _Node;
 110
 111   _List_iterator(_Node* __x) : _List_iterator_base(__x) {}
 112   _List_iterator() {}
 113   _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}
 114
 115   reference operator*() const { return ((_Node*) _M_node)->_M_data; }
 116   pointer operator->() const { return &(operator*()); }
 117
 118   _Self& operator++() {
 119     this->_M_incr();
 120     return *this;
 121   }
 122   _Self operator++(int) {
 123     _Self __tmp = *this;
 124     this->_M_incr();
 125     return __tmp;
 126   }
 127   _Self& operator--() {
 128     this->_M_decr();
 129     return *this;
 130   }
 131   _Self operator--(int) {
 132     _Self __tmp = *this;
 133     this->_M_decr();
 134     return __tmp;
 135   }
 136 };
 137
 138
 139 // Base class that encapsulates details of allocators.  Three cases:
 140 // an ordinary standard-conforming allocator, a standard-conforming
 141 // allocator with no non-static data, and an SGI-style allocator.
 142 // This complexity is necessary only because we're worrying about backward
 143 // compatibility and because we want to avoid wasting storage on an
 144 // allocator instance if it isn't necessary.
 145
 146
 147 // Base for general standard-conforming allocators.
 148 template <class _Tp, class _Allocator, bool _IsStatic>
 149 class _List_alloc_base {
 150 public:
 151   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
 152           allocator_type;
 153   allocator_type get_allocator() const { return _Node_allocator; }
 154
 155   _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
 156
 157 protected:
 158   _List_node<_Tp>* _M_get_node()
 159    { return _Node_allocator.allocate(1); }
 160   void _M_put_node(_List_node<_Tp>* __p)
 161     { _Node_allocator.deallocate(__p, 1); }
 162
 163 protected:
 164   typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
 165            _Node_allocator;
 166   _List_node<_Tp>* _M_node;
 167 };
 168
 169 // Specialization for instanceless allocators.
 170
 171 template <class _Tp, class _Allocator>
 172 class _List_alloc_base<_Tp, _Allocator, true> {
 173 public:
 174   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
 175           allocator_type;
 176   allocator_type get_allocator() const { return allocator_type(); }
 177
 178   _List_alloc_base(const allocator_type&) {}
 179
 180 protected:
 181   typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
 182           _Alloc_type;
 183   _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
 184   void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
 185
 186 protected:
 187   _List_node<_Tp>* _M_node;
 188 };
 189
 190 template <class _Tp, class _Alloc>
 191 class _List_base
 192   : public _List_alloc_base<_Tp, _Alloc,
 193                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 194 {
 195 public:
 196   typedef _List_alloc_base<_Tp, _Alloc,
 197                            _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 198           _Base;
 199   typedef typename _Base::allocator_type allocator_type;
 200
 201   _List_base(const allocator_type& __a) : _Base(__a) {
 202     _M_node = _M_get_node();
 203     _M_node->_M_next = _M_node;
 204     _M_node->_M_prev = _M_node;
 205   }
 206   ~_List_base() {
 207     clear();
 208     _M_put_node(_M_node);
 209   }
 210
 211   void clear();
 212 };
 213
 214
 215 template <class _Tp, class _Alloc>
 216 void
 217 _List_base<_Tp,_Alloc>::clear()
 218 {
 219   _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;
 220   while (__cur != _M_node) {
 221     _List_node<_Tp>* __tmp = __cur;
 222     __cur = (_List_node<_Tp>*) __cur->_M_next;
 223     _Destroy(&__tmp->_M_data);
 224     _M_put_node(__tmp);
 225   }
 226   _M_node->_M_next = _M_node;
 227   _M_node->_M_prev = _M_node;
 228 }
 229
 230 template <class _Tp, class _Alloc = allocator<_Tp> >
 231 class list : protected _List_base<_Tp, _Alloc>
 232 {
 233   // concept requirements
 234   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
 235
 236   typedef _List_base<_Tp, _Alloc> _Base;
 237 protected:
 238   typedef void* _Void_pointer;
 239
 240 public:
 241   typedef _Tp value_type;
 242   typedef value_type* pointer;
 243   typedef const value_type* const_pointer;
 244   typedef value_type& reference;
 245   typedef const value_type& const_reference;
 246   typedef _List_node<_Tp> _Node;
 247   typedef size_t size_type;
 248   typedef ptrdiff_t difference_type;
 249
 250   typedef typename _Base::allocator_type allocator_type;
 251   allocator_type get_allocator() const { return _Base::get_allocator(); }
 252
 253 public:
 254   typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
 255   typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
 256
 257   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 258   typedef reverse_iterator<iterator>       reverse_iterator;
 259
 260 protected:
 261   using _Base::_M_node;
 262   using _Base::_M_put_node;
 263   using _Base::_M_get_node;
 264
 265 protected:
 266   _Node* _M_create_node(const _Tp& __x)
 267   {
 268     _Node* __p = _M_get_node();
 269     try {
 270       _Construct(&__p->_M_data, __x);
 271     }
 272     catch(...)
 273       {
 274         _M_put_node(__p);
 275         __throw_exception_again;
 276       }
 277     return __p;
 278   }
 279
 280   _Node* _M_create_node()
 281   {
 282     _Node* __p = _M_get_node();
 283     try {
 284       _Construct(&__p->_M_data);
 285     }
 286     catch(...)
 287       {
 288         _M_put_node(__p);
 289         __throw_exception_again;
 290       }
 291     return __p;
 292   }
 293
 294 public:
 295   explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
 296
 297   iterator begin()             { return (_Node*)(_M_node->_M_next); }
 298   const_iterator begin() const { return (_Node*)(_M_node->_M_next); }
 299
 300   iterator end()             { return _M_node; }
 301   const_iterator end() const { return _M_node; }
 302
 303   reverse_iterator rbegin()
 304     { return reverse_iterator(end()); }
 305   const_reverse_iterator rbegin() const
 306     { return const_reverse_iterator(end()); }
 307
 308   reverse_iterator rend()
 309     { return reverse_iterator(begin()); }
 310   const_reverse_iterator rend() const
 311     { return const_reverse_iterator(begin()); }
 312
 313   bool empty() const { return _M_node->_M_next == _M_node; }
 314   size_type size() const {
 315     size_type __result = 0;
 316     distance(begin(), end(), __result);
 317     return __result;
 318   }
 319   size_type max_size() const { return size_type(-1); }
 320
 321   reference front() { return *begin(); }
 322   const_reference front() const { return *begin(); }
 323   reference back() { return *(--end()); }
 324   const_reference back() const { return *(--end()); }
 325
 326   void swap(list<_Tp, _Alloc>& __x) { std::swap(_M_node, __x._M_node); }
 327
 328   iterator insert(iterator __position, const _Tp& __x) {
 329     _Node* __tmp = _M_create_node(__x);
 330     __tmp->_M_next = __position._M_node;
 331     __tmp->_M_prev = __position._M_node->_M_prev;
 332     __position._M_node->_M_prev->_M_next = __tmp;
 333     __position._M_node->_M_prev = __tmp;
 334     return __tmp;
 335   }
 336   iterator insert(iterator __position) { return insert(__position, _Tp()); }
 337
 338   // Check whether it's an integral type.  If so, it's not an iterator.
 339   template<class _Integer>
 340   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
 341                           __true_type) {
 342     _M_fill_insert(__pos, (size_type) __n, (_Tp) __x);
 343   }
 344
 345   template <class _InputIterator>
 346   void _M_insert_dispatch(iterator __pos,
 347                           _InputIterator __first, _InputIterator __last,
 348                           __false_type);
 349
 350   template <class _InputIterator>
 351   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
 352     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 353     _M_insert_dispatch(__pos, __first, __last, _Integral());
 354   }
 355
 356   void insert(iterator __pos, size_type __n, const _Tp& __x)
 357     { _M_fill_insert(__pos, __n, __x); }
 358   void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x);
 359
 360   void push_front(const _Tp& __x) { insert(begin(), __x); }
 361   void push_front() {insert(begin());}
 362   void push_back(const _Tp& __x) { insert(end(), __x); }
 363   void push_back() {insert(end());}
 364
 365   iterator erase(iterator __position) {
 366     _List_node_base* __next_node = __position._M_node->_M_next;
 367     _List_node_base* __prev_node = __position._M_node->_M_prev;
 368     _Node* __n = (_Node*) __position._M_node;
 369     __prev_node->_M_next = __next_node;
 370     __next_node->_M_prev = __prev_node;
 371     _Destroy(&__n->_M_data);
 372     _M_put_node(__n);
 373     return iterator((_Node*) __next_node);
 374   }
 375   iterator erase(iterator __first, iterator __last);
 376   void clear() { _Base::clear(); }
 377
 378   void resize(size_type __new_size, const _Tp& __x);
 379   void resize(size_type __new_size) { this->resize(__new_size, _Tp()); }
 380
 381   void pop_front() { erase(begin()); }
 382   void pop_back() {
 383     iterator __tmp = end();
 384     erase(--__tmp);
 385   }
 386   list(size_type __n, const _Tp& __value,
 387        const allocator_type& __a = allocator_type())
 388     : _Base(__a)
 389     { insert(begin(), __n, __value); }
 390   explicit list(size_type __n)
 391     : _Base(allocator_type())
 392     { insert(begin(), __n, _Tp()); }
 393
 394   // We don't need any dispatching tricks here, because insert does all of
 395   // that anyway.
 396   template <class _InputIterator>
 397   list(_InputIterator __first, _InputIterator __last,
 398        const allocator_type& __a = allocator_type())
 399     : _Base(__a)
 400     { insert(begin(), __first, __last); }
 401
 402   list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
 403     { insert(begin(), __x.begin(), __x.end()); }
 404
 405   ~list() { }
 406
 407   list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x);
 408
 409 public:
 410   // assign(), a generalized assignment member function.  Two
 411   // versions: one that takes a count, and one that takes a range.
 412   // The range version is a member template, so we dispatch on whether
 413   // or not the type is an integer.
 414
 415   void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
 416
 417   void _M_fill_assign(size_type __n, const _Tp& __val);
 418
 419   template <class _InputIterator>
 420   void assign(_InputIterator __first, _InputIterator __last) {
 421     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 422     _M_assign_dispatch(__first, __last, _Integral());
 423   }
 424
 425   template <class _Integer>
 426   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 427     { _M_fill_assign((size_type) __n, (_Tp) __val); }
 428
 429   template <class _InputIterator>
 430   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 431                           __false_type);
 432
 433 protected:
 434   void transfer(iterator __position, iterator __first, iterator __last) {
 435     if (__position != __last) {
 436       // Remove [first, last) from its old position.
 437       __last._M_node->_M_prev->_M_next     = __position._M_node;
 438       __first._M_node->_M_prev->_M_next    = __last._M_node;
 439       __position._M_node->_M_prev->_M_next = __first._M_node;
 440
 441       // Splice [first, last) into its new position.
 442       _List_node_base* __tmp      = __position._M_node->_M_prev;
 443       __position._M_node->_M_prev = __last._M_node->_M_prev;
 444       __last._M_node->_M_prev     = __first._M_node->_M_prev;
 445       __first._M_node->_M_prev    = __tmp;
 446     }
 447   }
 448
 449 public:
 450   void splice(iterator __position, list& __x) {
 451     if (!__x.empty())
 452       this->transfer(__position, __x.begin(), __x.end());
 453   }
 454   void splice(iterator __position, list&, iterator __i) {
 455     iterator __j = __i;
 456     ++__j;
 457     if (__position == __i || __position == __j) return;
 458     this->transfer(__position, __i, __j);
 459   }
 460   void splice(iterator __position, list&, iterator __first, iterator __last) {
 461     if (__first != __last)
 462       this->transfer(__position, __first, __last);
 463   }
 464   void remove(const _Tp& __value);
 465   void unique();
 466   void merge(list& __x);
 467   void reverse();
 468   void sort();
 469
 470   template <class _Predicate> void remove_if(_Predicate);
 471   template <class _BinaryPredicate> void unique(_BinaryPredicate);
 472   template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering);
 473   template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering);
 474 };
 475
 476 template <class _Tp, class _Alloc>
 477 inline bool
 478 operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
 479 {
 480   typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
 481   const_iterator __end1 = __x.end();
 482   const_iterator __end2 = __y.end();
 483
 484   const_iterator __i1 = __x.begin();
 485   const_iterator __i2 = __y.begin();
 486   while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
 487     ++__i1;
 488     ++__i2;
 489   }
 490   return __i1 == __end1 && __i2 == __end2;
 491 }
 492
 493 template <class _Tp, class _Alloc>
 494 inline bool operator<(const list<_Tp,_Alloc>& __x,
 495                       const list<_Tp,_Alloc>& __y)
 496 {
 497   return lexicographical_compare(__x.begin(), __x.end(),
 498                                  __y.begin(), __y.end());
 499 }
 500
 501 template <class _Tp, class _Alloc>
 502 inline bool operator!=(const list<_Tp,_Alloc>& __x,
 503                        const list<_Tp,_Alloc>& __y) {
 504   return !(__x == __y);
 505 }
 506
 507 template <class _Tp, class _Alloc>
 508 inline bool operator>(const list<_Tp,_Alloc>& __x,
 509                       const list<_Tp,_Alloc>& __y) {
 510   return __y < __x;
 511 }
 512
 513 template <class _Tp, class _Alloc>
 514 inline bool operator<=(const list<_Tp,_Alloc>& __x,
 515                        const list<_Tp,_Alloc>& __y) {
 516   return !(__y < __x);
 517 }
 518
 519 template <class _Tp, class _Alloc>
 520 inline bool operator>=(const list<_Tp,_Alloc>& __x,
 521                        const list<_Tp,_Alloc>& __y) {
 522   return !(__x < __y);
 523 }
 524
 525 template <class _Tp, class _Alloc>
 526 inline void
 527 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
 528 {
 529   __x.swap(__y);
 530 }
 531
 532 template <class _Tp, class _Alloc> template <class _InputIter>
 533 void
 534 list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position,
 535                                       _InputIter __first, _InputIter __last,
 536                                       __false_type)
 537 {
 538   for ( ; __first != __last; ++__first)
 539     insert(__position, *__first);
 540 }
 541
 542 template <class _Tp, class _Alloc>
 543 void
 544 list<_Tp, _Alloc>::_M_fill_insert(iterator __position,
 545                                   size_type __n, const _Tp& __x)
 546 {
 547   for ( ; __n > 0; --__n)
 548     insert(__position, __x);
 549 }
 550
 551 template <class _Tp, class _Alloc>
 552 typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
 553                                                              iterator __last)
 554 {
 555   while (__first != __last)
 556     erase(__first++);
 557   return __last;
 558 }
 559
 560 template <class _Tp, class _Alloc>
 561 void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
 562 {
 563   iterator __i = begin();
 564   size_type __len = 0;
 565   for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
 566     ;
 567   if (__len == __new_size)
 568     erase(__i, end());
 569   else                          // __i == end()
 570     insert(end(), __new_size - __len, __x);
 571 }
 572
 573 template <class _Tp, class _Alloc>
 574 list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
 575 {
 576   if (this != &__x) {
 577     iterator __first1 = begin();
 578     iterator __last1 = end();
 579     const_iterator __first2 = __x.begin();
 580     const_iterator __last2 = __x.end();
 581     while (__first1 != __last1 && __first2 != __last2)
 582       *__first1++ = *__first2++;
 583     if (__first2 == __last2)
 584       erase(__first1, __last1);
 585     else
 586       insert(__last1, __first2, __last2);
 587   }
 588   return *this;
 589 }
 590
 591 template <class _Tp, class _Alloc>
 592 void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
 593   iterator __i = begin();
 594   for ( ; __i != end() && __n > 0; ++__i, --__n)
 595     *__i = __val;
 596   if (__n > 0)
 597     insert(end(), __n, __val);
 598   else
 599     erase(__i, end());
 600 }
 601
 602 template <class _Tp, class _Alloc> template <class _InputIter>
 603 void
 604 list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2,
 605                                       __false_type)
 606 {
 607   iterator __first1 = begin();
 608   iterator __last1 = end();
 609   for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
 610     *__first1 = *__first2;
 611   if (__first2 == __last2)
 612     erase(__first1, __last1);
 613   else
 614     insert(__last1, __first2, __last2);
 615 }
 616
 617 template <class _Tp, class _Alloc>
 618 void list<_Tp, _Alloc>::remove(const _Tp& __value)
 619 {
 620   iterator __first = begin();
 621   iterator __last = end();
 622   while (__first != __last) {
 623     iterator __next = __first;
 624     ++__next;
 625     if (*__first == __value) erase(__first);
 626     __first = __next;
 627   }
 628 }
 629
 630 template <class _Tp, class _Alloc>
 631 void list<_Tp, _Alloc>::unique()
 632 {
 633   iterator __first = begin();
 634   iterator __last = end();
 635   if (__first == __last) return;
 636   iterator __next = __first;
 637   while (++__next != __last) {
 638     if (*__first == *__next)
 639       erase(__next);
 640     else
 641       __first = __next;
 642     __next = __first;
 643   }
 644 }
 645
 646 template <class _Tp, class _Alloc>
 647 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
 648 {
 649   iterator __first1 = begin();
 650   iterator __last1 = end();
 651   iterator __first2 = __x.begin();
 652   iterator __last2 = __x.end();
 653   while (__first1 != __last1 && __first2 != __last2)
 654     if (*__first2 < *__first1) {
 655       iterator __next = __first2;
 656       transfer(__first1, __first2, ++__next);
 657       __first2 = __next;
 658     }
 659     else
 660       ++__first1;
 661   if (__first2 != __last2) transfer(__last1, __first2, __last2);
 662 }
 663
 664 inline void __List_base_reverse(_List_node_base* __p)
 665 {
 666   _List_node_base* __tmp = __p;
 667   do {
 668     std::swap(__tmp->_M_next, __tmp->_M_prev);
 669     __tmp = __tmp->_M_prev;     // Old next node is now prev.
 670   } while (__tmp != __p);
 671 }
 672
 673 template <class _Tp, class _Alloc>
 674 inline void list<_Tp, _Alloc>::reverse()
 675 {
 676   __List_base_reverse(this->_M_node);
 677 }
 678
 679 template <class _Tp, class _Alloc>
 680 void list<_Tp, _Alloc>::sort()
 681 {
 682   // Do nothing if the list has length 0 or 1.
 683   if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
 684     list<_Tp, _Alloc> __carry;
 685     list<_Tp, _Alloc> __counter[64];
 686     int __fill = 0;
 687     while (!empty()) {
 688       __carry.splice(__carry.begin(), *this, begin());
 689       int __i = 0;
 690       while(__i < __fill && !__counter[__i].empty()) {
 691         __counter[__i].merge(__carry);
 692         __carry.swap(__counter[__i++]);
 693       }
 694       __carry.swap(__counter[__i]);
 695       if (__i == __fill) ++__fill;
 696     }
 697
 698     for (int __i = 1; __i < __fill; ++__i)
 699       __counter[__i].merge(__counter[__i-1]);
 700     swap(__counter[__fill-1]);
 701   }
 702 }
 703
 704 template <class _Tp, class _Alloc> template <class _Predicate>
 705 void list<_Tp, _Alloc>::remove_if(_Predicate __pred)
 706 {
 707   iterator __first = begin();
 708   iterator __last = end();
 709   while (__first != __last) {
 710     iterator __next = __first;
 711     ++__next;
 712     if (__pred(*__first)) erase(__first);
 713     __first = __next;
 714   }
 715 }
 716
 717 template <class _Tp, class _Alloc> template <class _BinaryPredicate>
 718 void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
 719 {
 720   iterator __first = begin();
 721   iterator __last = end();
 722   if (__first == __last) return;
 723   iterator __next = __first;
 724   while (++__next != __last) {
 725     if (__binary_pred(*__first, *__next))
 726       erase(__next);
 727     else
 728       __first = __next;
 729     __next = __first;
 730   }
 731 }
 732
 733 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
 734 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x,
 735                               _StrictWeakOrdering __comp)
 736 {
 737   iterator __first1 = begin();
 738   iterator __last1 = end();
 739   iterator __first2 = __x.begin();
 740   iterator __last2 = __x.end();
 741   while (__first1 != __last1 && __first2 != __last2)
 742     if (__comp(*__first2, *__first1)) {
 743       iterator __next = __first2;
 744       transfer(__first1, __first2, ++__next);
 745       __first2 = __next;
 746     }
 747     else
 748       ++__first1;
 749   if (__first2 != __last2) transfer(__last1, __first2, __last2);
 750 }
 751
 752 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
 753 void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
 754 {
 755   // Do nothing if the list has length 0 or 1.
 756   if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
 757     list<_Tp, _Alloc> __carry;
 758     list<_Tp, _Alloc> __counter[64];
 759     int __fill = 0;
 760     while (!empty()) {
 761       __carry.splice(__carry.begin(), *this, begin());
 762       int __i = 0;
 763       while(__i < __fill && !__counter[__i].empty()) {
 764         __counter[__i].merge(__carry, __comp);
 765         __carry.swap(__counter[__i++]);
 766       }
 767       __carry.swap(__counter[__i]);
 768       if (__i == __fill) ++__fill;
 769     }
 770
 771     for (int __i = 1; __i < __fill; ++__i)
 772       __counter[__i].merge(__counter[__i-1], __comp);
 773     swap(__counter[__fill-1]);
 774   }
 775 }
 776
 777 } // namespace std
 778
 779 #endif /* __SGI_STL_INTERNAL_LIST_H */
 780
 781 // Local Variables:
 782 // mode:C++
 783 // End: