headers/cpp/stl_list.h

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