- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_list.h

    00001 /*
    00002  *
    00003  * Copyright (c) 1994
    00004  * Hewlett-Packard Company
    00005  *
    00006  * Permission to use, copy, modify, distribute and sell this software
    00007  * and its documentation for any purpose is hereby granted without fee,
    00008  * provided that the above copyright notice appear in all copies and
    00009  * that both that copyright notice and this permission notice appear
    00010  * in supporting documentation.  Hewlett-Packard Company makes no
    00011  * representations about the suitability of this software for any
    00012  * purpose.  It is provided "as is" without express or implied warranty.
    00013  *
    00014  *
    00015  * Copyright (c) 1996,1997
    00016  * Silicon Graphics Computer Systems, Inc.
    00017  *
    00018  * Permission to use, copy, modify, distribute and sell this software
    00019  * and its documentation for any purpose is hereby granted without fee,
    00020  * provided that the above copyright notice appear in all copies and
    00021  * that both that copyright notice and this permission notice appear
    00022  * in supporting documentation.  Silicon Graphics makes no
    00023  * representations about the suitability of this software for any
    00024  * purpose.  It is provided "as is" without express or implied warranty.
    00025  */
    00026
    00027 /* NOTE: This is an internal header file, included by other STL headers.
    00028  *   You should not attempt to use it directly.
    00029  */
    00030
    00031 #ifndef __SGI_STL_INTERNAL_LIST_H
    00032 #define __SGI_STL_INTERNAL_LIST_H
    00033
    00034 __STL_BEGIN_NAMESPACE
    00035
    00036 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00037 #pragma set woff 1174
    00038 #pragma set woff 1375
    00039 #endif
    00040
    00041 template <class _Tp>
    00042 struct _List_node {
    00043   typedef void* _Void_pointer;
    00044   _Void_pointer _M_next;
    00045   _Void_pointer _M_prev;
    00046   _Tp _M_data;
    00047 };
    00048
    00049 template<class _Tp, class _Ref, class _Ptr>
    00050 struct _List_iterator {
    00051   typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
    00052   typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
    00053   typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;
    00054
    00055   typedef bidirectional_iterator_tag iterator_category;
    00056   typedef _Tp value_type;
    00057   typedef _Ptr pointer;
    00058   typedef _Ref reference;
    00059   typedef _List_node<_Tp> _Node;
    00060   typedef size_t size_type;
    00061   typedef ptrdiff_t difference_type;
    00062
    00063   _Node* _M_node;
    00064
    00065   _List_iterator(_Node* __x) : _M_node(__x) {}
    00066   _List_iterator() {}
    00067   _List_iterator(const iterator& __x) : _M_node(__x._M_node) {}
    00068
    00069   bool operator==(const _Self& __x) const { return _M_node == __x._M_node; }
    00070   bool operator!=(const _Self& __x) const { return _M_node != __x._M_node; }
    00071   reference operator*() const { return (*_M_node)._M_data; }
    00072
    00073 #ifndef __SGI_STL_NO_ARROW_OPERATOR
    00074   pointer operator->() const { return &(operator*()); }
    00075 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
    00076
    00077   _Self& operator++() {
    00078     _M_node = (_Node*)(_M_node->_M_next);
    00079     return *this;
    00080   }
    00081   _Self operator++(int) {
    00082     _Self __tmp = *this;
    00083     ++*this;
    00084     return __tmp;
    00085   }
    00086   _Self& operator--() {
    00087     _M_node = (_Node*)(_M_node->_M_prev);
    00088     return *this;
    00089   }
    00090   _Self operator--(int) {
    00091     _Self __tmp = *this;
    00092     --*this;
    00093     return __tmp;
    00094   }
    00095 };
    00096
    00097 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
    00098
    00099 template <class _Tp, class _Ref, class _Ptr>
    00100 inline bidirectional_iterator_tag
    00101 iterator_category(const _List_iterator<_Tp, _Ref, _Ptr>&)
    00102 {
    00103   return bidirectional_iterator_tag();
    00104 }
    00105
    00106 template <class _Tp, class _Ref, class _Ptr>
    00107 inline _Tp*
    00108 value_type(const _List_iterator<_Tp, _Ref, _Ptr>&)
    00109 {
    00110   return 0;
    00111 }
    00112
    00113 template <class _Tp, class _Ref, class _Ptr>
    00114 inline ptrdiff_t*
    00115 distance_type(const _List_iterator<_Tp, _Ref, _Ptr>&)
    00116 {
    00117   return 0;
    00118 }
    00119
    00120 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00121
    00122
    00123 // Base class that encapsulates details of allocators.  Three cases:
    00124 // an ordinary standard-conforming allocator, a standard-conforming
    00125 // allocator with no non-static data, and an SGI-style allocator.
    00126 // This complexity is necessary only because we're worrying about backward
    00127 // compatibility and because we want to avoid wasting storage on an
    00128 // allocator instance if it isn't necessary.
    00129
    00130 #ifdef __STL_USE_STD_ALLOCATORS
    00131
    00132 // Base for general standard-conforming allocators.
    00133 template <class _Tp, class _Allocator, bool _IsStatic>
    00134 class _List_alloc_base {
    00135 public:
    00136   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
    00137           allocator_type;
    00138   allocator_type get_allocator() const { return _Node_allocator; }
    00139
    00140   _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
    00141
    00142 protected:
    00143   _List_node<_Tp>* _M_get_node()
    00144    { return _Node_allocator.allocate(1); }
    00145   void _M_put_node(_List_node<_Tp>* __p)
    00146     { _Node_allocator.deallocate(__p, 1); }
    00147
    00148 protected:
    00149   typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
    00150            _Node_allocator;
    00151   _List_node<_Tp>* _M_node;
    00152 };
    00153
    00154 // Specialization for instanceless allocators.
    00155
    00156 template <class _Tp, class _Allocator>
    00157 class _List_alloc_base<_Tp, _Allocator, true> {
    00158 public:
    00159   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
    00160           allocator_type;
    00161   allocator_type get_allocator() const { return allocator_type(); }
    00162
    00163   _List_alloc_base(const allocator_type&) {}
    00164
    00165 protected:
    00166   typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
    00167           _Alloc_type;
    00168   _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
    00169   void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
    00170
    00171 protected:
    00172   _List_node<_Tp>* _M_node;
    00173 };
    00174
    00175 template <class _Tp, class _Alloc>
    00176 class _List_base
    00177   : public _List_alloc_base<_Tp, _Alloc,
    00178                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    00179 {
    00180 public:
    00181   typedef _List_alloc_base<_Tp, _Alloc,
    00182                            _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    00183           _Base;
    00184   typedef typename _Base::allocator_type allocator_type;
    00185
    00186   _List_base(const allocator_type& __a) : _Base(__a) {
    00187     _M_node = _M_get_node();
    00188     _M_node->_M_next = _M_node;
    00189     _M_node->_M_prev = _M_node;
    00190   }
    00191   ~_List_base() {
    00192     clear();
    00193     _M_put_node(_M_node);
    00194   }
    00195
    00196   void clear();
    00197 };
    00198
    00199 #else /* __STL_USE_STD_ALLOCATORS */
    00200
    00201 template <class _Tp, class _Alloc>
    00202 class _List_base
    00203 {
    00204 public:
    00205   typedef _Alloc allocator_type;
    00206   allocator_type get_allocator() const { return allocator_type(); }
    00207
    00208   _List_base(const allocator_type&) {
    00209     _M_node = _M_get_node();
    00210     _M_node->_M_next = _M_node;
    00211     _M_node->_M_prev = _M_node;
    00212   }
    00213   ~_List_base() {
    00214     clear();
    00215     _M_put_node(_M_node);
    00216   }
    00217
    00218   void clear();
    00219
    00220 protected:
    00221   typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type;
    00222   _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
    00223   void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
    00224
    00225 protected:
    00226   _List_node<_Tp>* _M_node;
    00227 };
    00228
    00229 #endif /* __STL_USE_STD_ALLOCATORS */
    00230
    00231 template <class _Tp, class _Alloc>
    00232 void
    00233 _List_base<_Tp,_Alloc>::clear()
    00234 {
    00235   _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;
    00236   while (__cur != _M_node) {
    00237     _List_node<_Tp>* __tmp = __cur;
    00238     __cur = (_List_node<_Tp>*) __cur->_M_next;
    00239     destroy(&__tmp->_M_data);
    00240     _M_put_node(__tmp);
    00241   }
    00242   _M_node->_M_next = _M_node;
    00243   _M_node->_M_prev = _M_node;
    00244 }
    00245
    00246 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    00247 class list : protected _List_base<_Tp, _Alloc> {
    00248   typedef _List_base<_Tp, _Alloc> _Base;
    00249 protected:
    00250   typedef void* _Void_pointer;
    00251
    00252 public:
    00253   typedef _Tp value_type;
    00254   typedef value_type* pointer;
    00255   typedef const value_type* const_pointer;
    00256   typedef value_type& reference;
    00257   typedef const value_type& const_reference;
    00258   typedef _List_node<_Tp> _Node;
    00259   typedef size_t size_type;
    00260   typedef ptrdiff_t difference_type;
    00261
    00262   typedef typename _Base::allocator_type allocator_type;
    00263   allocator_type get_allocator() const { return _Base::get_allocator(); }
    00264
    00265 public:
    00266   typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
    00267   typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
    00268
    00269 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    00270   typedef reverse_iterator<const_iterator> const_reverse_iterator;
    00271   typedef reverse_iterator<iterator>       reverse_iterator;
    00272 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00273   typedef reverse_bidirectional_iterator<const_iterator,value_type,
    00274                                          const_reference,difference_type>
    00275           const_reverse_iterator;
    00276   typedef reverse_bidirectional_iterator<iterator,value_type,reference,
    00277                                          difference_type>
    00278           reverse_iterator;
    00279 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00280
    00281 protected:
    00282 #ifdef __STL_HAS_NAMESPACES
    00283   using _Base::_M_node;
    00284   using _Base::_M_put_node;
    00285   using _Base::_M_get_node;
    00286 #endif /* __STL_HAS_NAMESPACES */
    00287
    00288 protected:
    00289   _Node* _M_create_node(const _Tp& __x)
    00290   {
    00291     _Node* __p = _M_get_node();
    00292     __STL_TRY {
    00293       construct(&__p->_M_data, __x);
    00294     }
    00295     __STL_UNWIND(_M_put_node(__p));
    00296     return __p;
    00297   }
    00298
    00299   _Node* _M_create_node()
    00300   {
    00301     _Node* __p = _M_get_node();
    00302     __STL_TRY {
    00303       construct(&__p->_M_data);
    00304     }
    00305     __STL_UNWIND(_M_put_node(__p));
    00306     return __p;
    00307   }
    00308
    00309 public:
    00310   explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
    00311
    00312   iterator begin()             { return (_Node*)(_M_node->_M_next); }
    00313   const_iterator begin() const { return (_Node*)(_M_node->_M_next); }
    00314
    00315   iterator end()             { return _M_node; }
    00316   const_iterator end() const { return _M_node; }
    00317
    00318   reverse_iterator rbegin()
    00319     { return reverse_iterator(end()); }
    00320   const_reverse_iterator rbegin() const
    00321     { return const_reverse_iterator(end()); }
    00322
    00323   reverse_iterator rend()
    00324     { return reverse_iterator(begin()); }
    00325   const_reverse_iterator rend() const
    00326     { return const_reverse_iterator(begin()); }
    00327
    00328   bool empty() const { return _M_node->_M_next == _M_node; }
    00329   size_type size() const {
    00330     size_type __result = 0;
    00331     distance(begin(), end(), __result);
    00332     return __result;
    00333   }
    00334   size_type max_size() const { return size_type(-1); }
    00335
    00336   reference front() { return *begin(); }
    00337   const_reference front() const { return *begin(); }
    00338   reference back() { return *(--end()); }
    00339   const_reference back() const { return *(--end()); }
    00340
    00341   void swap(list<_Tp, _Alloc>& __x) { __STD::swap(_M_node, __x._M_node); }
    00342
    00343   iterator insert(iterator __position, const _Tp& __x) {
    00344     _Node* __tmp = _M_create_node(__x);
    00345     __tmp->_M_next = __position._M_node;
    00346     __tmp->_M_prev = __position._M_node->_M_prev;
    00347     ((_Node*) (__position._M_node->_M_prev))->_M_next = __tmp;
    00348     __position._M_node->_M_prev = __tmp;
    00349     return __tmp;
    00350   }
    00351   iterator insert(iterator __position) { return insert(__position, _Tp()); }
    00352 #ifdef __STL_MEMBER_TEMPLATES
    00353   // Check whether it's an integral type.  If so, it's not an iterator.
    00354
    00355   template<class _Integer>
    00356   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
    00357                           __true_type) {
    00358     insert(__pos, (size_type) __n, (_Tp) __x);
    00359   }
    00360
    00361   template <class _InputIterator>
    00362   void _M_insert_dispatch(iterator __pos,
    00363                           _InputIterator __first, _InputIterator __last,
    00364                           __false_type);
    00365
    00366   template <class _InputIterator>
    00367   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
    00368     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00369     _M_insert_dispatch(__pos, __first, __last, _Integral());
    00370   }
    00371
    00372 #else /* __STL_MEMBER_TEMPLATES */
    00373   void insert(iterator __position, const _Tp* __first, const _Tp* __last);
    00374   void insert(iterator __position,
    00375               const_iterator __first, const_iterator __last);
    00376 #endif /* __STL_MEMBER_TEMPLATES */
    00377   void insert(iterator __pos, size_type __n, const _Tp& __x);
    00378
    00379   void push_front(const _Tp& __x) { insert(begin(), __x); }
    00380   void push_front() {insert(begin());}
    00381   void push_back(const _Tp& __x) { insert(end(), __x); }
    00382   void push_back() {insert(end());}
    00383
    00384   iterator erase(iterator __position) {
    00385     _Node* __next_node = (_Node*) (__position._M_node->_M_next);
    00386     _Node* __prev_node = (_Node*) (__position._M_node->_M_prev);
    00387     __prev_node->_M_next = __next_node;
    00388     __next_node->_M_prev = __prev_node;
    00389     destroy(&__position._M_node->_M_data);
    00390     _M_put_node(__position._M_node);
    00391     return iterator(__next_node);
    00392   }
    00393   iterator erase(iterator __first, iterator __last);
    00394   void clear() { _Base::clear(); }
    00395
    00396   void resize(size_type __new_size, const _Tp& __x);
    00397   void resize(size_type __new_size) { resize(__new_size, _Tp()); }
    00398
    00399   void pop_front() { erase(begin()); }
    00400   void pop_back() {
    00401     iterator __tmp = end();
    00402     erase(--__tmp);
    00403   }
    00404   list(size_type __n, const _Tp& __value,
    00405        const allocator_type& __a = allocator_type())
    00406     : _Base(__a)
    00407     { insert(begin(), __n, __value); }
    00408   explicit list(size_type __n)
    00409     : _Base(allocator_type())
    00410     { insert(begin(), __n, _Tp()); }
    00411
    00412 #ifdef __STL_MEMBER_TEMPLATES
    00413
    00414   // We don't need any dispatching tricks here, because insert does all of
    00415   // that anyway.
    00416   template <class _InputIterator>
    00417   list(_InputIterator __first, _InputIterator __last,
    00418        const allocator_type& __a = allocator_type())
    00419     : _Base(__a)
    00420     { insert(begin(), __first, __last); }
    00421
    00422 #else /* __STL_MEMBER_TEMPLATES */
    00423
    00424   list(const _Tp* __first, const _Tp* __last,
    00425        const allocator_type& __a = allocator_type())
    00426     : _Base(__a)
    00427     { insert(begin(), __first, __last); }
    00428   list(const_iterator __first, const_iterator __last,
    00429        const allocator_type& __a = allocator_type())
    00430     : _Base(__a)
    00431     { insert(begin(), __first, __last); }
    00432
    00433 #endif /* __STL_MEMBER_TEMPLATES */
    00434   list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
    00435     { insert(begin(), __x.begin(), __x.end()); }
    00436
    00437   ~list() { }
    00438
    00439   list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x);
    00440
    00441 public:
    00442   // assign(), a generalized assignment member function.  Two
    00443   // versions: one that takes a count, and one that takes a range.
    00444   // The range version is a member template, so we dispatch on whether
    00445   // or not the type is an integer.
    00446
    00447   void assign(size_type __n, const _Tp& __val);
    00448
    00449 #ifdef __STL_MEMBER_TEMPLATES
    00450
    00451   template <class _InputIterator>
    00452   void assign(_InputIterator __first, _InputIterator __last) {
    00453     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00454     _M_assign_dispatch(__first, __last, _Integral());
    00455   }
    00456
    00457   template <class _Integer>
    00458   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    00459     { assign((size_type) __n, (_Tp) __val); }
    00460
    00461   template <class _InputIterator>
    00462   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
    00463                           __false_type);
    00464
    00465 #endif /* __STL_MEMBER_TEMPLATES */
    00466
    00467 protected:
    00468   void transfer(iterator __position, iterator __first, iterator __last) {
    00469     if (__position != __last) {
    00470       // Remove [first, last) from its old position.
    00471       ((_Node*) (__last._M_node->_M_prev))->_M_next     = __position._M_node;
    00472       ((_Node*) (__first._M_node->_M_prev))->_M_next    = __last._M_node;
    00473       ((_Node*) (__position._M_node->_M_prev))->_M_next = __first._M_node;
    00474
    00475       // Splice [first, last) into its new position.
    00476       _Node* __tmp = (_Node*) (__position._M_node->_M_prev);
    00477       __position._M_node->_M_prev = __last._M_node->_M_prev;
    00478       __last._M_node->_M_prev      = __first._M_node->_M_prev;
    00479       __first._M_node->_M_prev    = __tmp;
    00480     }
    00481   }
    00482
    00483 public:
    00484   void splice(iterator __position, list& __x) {
    00485     if (!__x.empty())
    00486       transfer(__position, __x.begin(), __x.end());
    00487   }
    00488   void splice(iterator __position, list&, iterator __i) {
    00489     iterator __j = __i;
    00490     ++__j;
    00491     if (__position == __i || __position == __j) return;
    00492     transfer(__position, __i, __j);
    00493   }
    00494   void splice(iterator __position, list&, iterator __first, iterator __last) {
    00495     if (__first != __last)
    00496       transfer(__position, __first, __last);
    00497   }
    00498   void remove(const _Tp& __value);
    00499   void unique();
    00500   void merge(list& __x);
    00501   void reverse();
    00502   void sort();
    00503
    00504 #ifdef __STL_MEMBER_TEMPLATES
    00505   template <class _Predicate> void remove_if(_Predicate);
    00506   template <class _BinaryPredicate> void unique(_BinaryPredicate);
    00507   template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering);
    00508   template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering);
    00509 #endif /* __STL_MEMBER_TEMPLATES */
    00510
    00511   friend bool operator== __STL_NULL_TMPL_ARGS (
    00512     const list& __x, const list& __y);
    00513 };
    00514
    00515 template <class _Tp, class _Alloc>
    00516 inline bool operator==(const list<_Tp,_Alloc>& __x,
    00517                        const list<_Tp,_Alloc>& __y)
    00518 {
    00519   typedef typename list<_Tp,_Alloc>::_Node _Node;
    00520   _Node* __e1 = __x._M_node;
    00521   _Node* __e2 = __y._M_node;
    00522   _Node* __n1 = (_Node*) __e1->_M_next;
    00523   _Node* __n2 = (_Node*) __e2->_M_next;
    00524   for ( ; __n1 != __e1 && __n2 != __e2 ;
    00525           __n1 = (_Node*) __n1->_M_next, __n2 = (_Node*) __n2->_M_next)
    00526     if (__n1->_M_data != __n2->_M_data)
    00527       return false;
    00528   return __n1 == __e1 && __n2 == __e2;
    00529 }
    00530
    00531 template <class _Tp, class _Alloc>
    00532 inline bool operator<(const list<_Tp,_Alloc>& __x,
    00533                       const list<_Tp,_Alloc>& __y)
    00534 {
    00535   return lexicographical_compare(__x.begin(), __x.end(),
    00536                                  __y.begin(), __y.end());
    00537 }
    00538
    00539 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
    00540
    00541 template <class _Tp, class _Alloc>
    00542 inline void
    00543 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
    00544 {
    00545   __x.swap(__y);
    00546 }
    00547
    00548 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
    00549
    00550 #ifdef __STL_MEMBER_TEMPLATES
    00551
    00552 template <class _Tp, class _Alloc> template <class _InputIter>
    00553 void
    00554 list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position,
    00555                                       _InputIter __first, _InputIter __last,
    00556                                       __false_type)
    00557 {
    00558   for ( ; __first != __last; ++__first)
    00559     insert(__position, *__first);
    00560 }
    00561
    00562 #else /* __STL_MEMBER_TEMPLATES */
    00563
    00564 template <class _Tp, class _Alloc>
    00565 void
    00566 list<_Tp, _Alloc>::insert(iterator __position,
    00567                           const _Tp* __first, const _Tp* __last)
    00568 {
    00569   for ( ; __first != __last; ++__first)
    00570     insert(__position, *__first);
    00571 }
    00572
    00573 template <class _Tp, class _Alloc>
    00574 void
    00575 list<_Tp, _Alloc>::insert(iterator __position,
    00576                          const_iterator __first, const_iterator __last)
    00577 {
    00578   for ( ; __first != __last; ++__first)
    00579     insert(__position, *__first);
    00580 }
    00581
    00582 #endif /* __STL_MEMBER_TEMPLATES */
    00583
    00584 template <class _Tp, class _Alloc>
    00585 void
    00586 list<_Tp, _Alloc>::insert(iterator __position, size_type __n, const _Tp& __x)
    00587 {
    00588   for ( ; __n > 0; --__n)
    00589     insert(__position, __x);
    00590 }
    00591
    00592 template <class _Tp, class _Alloc>
    00593 list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
    00594                                                     iterator __last)
    00595 {
    00596   while (__first != __last)
    00597     erase(__first++);
    00598   return __last;
    00599 }
    00600
    00601 template <class _Tp, class _Alloc>
    00602 void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
    00603 {
    00604   iterator __i = begin();
    00605   size_type __len = 0;
    00606   for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
    00607     ;
    00608   if (__len == __new_size)
    00609     erase(__i, end());
    00610   else                          // __i == end()
    00611     insert(end(), __new_size - __len, __x);
    00612 }
    00613
    00614 template <class _Tp, class _Alloc>
    00615 list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
    00616 {
    00617   if (this != &__x) {
    00618     iterator __first1 = begin();
    00619     iterator __last1 = end();
    00620     const_iterator __first2 = __x.begin();
    00621     const_iterator __last2 = __x.end();
    00622     while (__first1 != __last1 && __first2 != __last2)
    00623       *__first1++ = *__first2++;
    00624     if (__first2 == __last2)
    00625       erase(__first1, __last1);
    00626     else
    00627       insert(__last1, __first2, __last2);
    00628   }
    00629   return *this;
    00630 }
    00631
    00632 template <class _Tp, class _Alloc>
    00633 void list<_Tp, _Alloc>::assign(size_type __n, const _Tp& __val) {
    00634   iterator __i = begin();
    00635   for ( ; __i != end() && __n > 0; ++__i, --__n)
    00636     *__i = __val;
    00637   if (__n > 0)
    00638     insert(end(), __n, __val);
    00639   else
    00640     erase(__i, end());
    00641 }
    00642
    00643 #ifdef __STL_MEMBER_TEMPLATES
    00644
    00645 template <class _Tp, class _Alloc> template <class _InputIter>
    00646 void
    00647 list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2,
    00648                                       __false_type)
    00649 {
    00650   iterator __first1 = begin();
    00651   iterator __last1 = end();
    00652   for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
    00653     *__first1 = *__first2;
    00654   if (__first2 == __last2)
    00655     erase(__first1, __last1);
    00656   else
    00657     insert(__last1, __first2, __last2);
    00658 }
    00659
    00660 #endif /* __STL_MEMBER_TEMPLATES */
    00661
    00662 template <class _Tp, class _Alloc>
    00663 void list<_Tp, _Alloc>::remove(const _Tp& __value)
    00664 {
    00665   iterator __first = begin();
    00666   iterator __last = end();
    00667   while (__first != __last) {
    00668     iterator __next = __first;
    00669     ++__next;
    00670     if (*__first == __value) erase(__first);
    00671     __first = __next;
    00672   }
    00673 }
    00674
    00675 template <class _Tp, class _Alloc>
    00676 void list<_Tp, _Alloc>::unique()
    00677 {
    00678   iterator __first = begin();
    00679   iterator __last = end();
    00680   if (__first == __last) return;
    00681   iterator __next = __first;
    00682   while (++__next != __last) {
    00683     if (*__first == *__next)
    00684       erase(__next);
    00685     else
    00686       __first = __next;
    00687     __next = __first;
    00688   }
    00689 }
    00690
    00691 template <class _Tp, class _Alloc>
    00692 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
    00693 {
    00694   iterator __first1 = begin();
    00695   iterator __last1 = end();
    00696   iterator __first2 = __x.begin();
    00697   iterator __last2 = __x.end();
    00698   while (__first1 != __last1 && __first2 != __last2)
    00699     if (*__first2 < *__first1) {
    00700       iterator __next = __first2;
    00701       transfer(__first1, __first2, ++__next);
    00702       __first2 = __next;
    00703     }
    00704     else
    00705       ++__first1;
    00706   if (__first2 != __last2) transfer(__last1, __first2, __last2);
    00707 }
    00708
    00709 template <class _Tp, class _Alloc>
    00710 void list<_Tp, _Alloc>::reverse()
    00711 {
    00712   // Do nothing if the list has length 0 or 1.
    00713   if (_M_node->_M_next != _M_node &&
    00714       ((_Node*) (_M_node->_M_next))->_M_next != _M_node) {
    00715     iterator __first = begin();
    00716     ++__first;
    00717     while (__first != end()) {
    00718       iterator __old = __first;
    00719       ++__first;
    00720       transfer(begin(), __old, __first);
    00721     }
    00722   }
    00723 }
    00724
    00725 template <class _Tp, class _Alloc>
    00726 void list<_Tp, _Alloc>::sort()
    00727 {
    00728   // Do nothing if the list has length 0 or 1.
    00729   if (_M_node->_M_next != _M_node &&
    00730       ((_Node*) (_M_node->_M_next))->_M_next != _M_node) {
    00731     list<_Tp, _Alloc> __carry;
    00732     list<_Tp, _Alloc> __counter[64];
    00733     int __fill = 0;
    00734     while (!empty()) {
    00735       __carry.splice(__carry.begin(), *this, begin());
    00736       int __i = 0;
    00737       while(__i < __fill && !__counter[__i].empty()) {
    00738         __counter[__i].merge(__carry);
    00739         __carry.swap(__counter[__i++]);
    00740       }
    00741       __carry.swap(__counter[__i]);
    00742       if (__i == __fill) ++__fill;
    00743     }
    00744
    00745     for (int __i = 1; __i < __fill; ++__i)
    00746       __counter[__i].merge(__counter[__i-1]);
    00747     swap(__counter[__fill-1]);
    00748   }
    00749 }
    00750
    00751 #ifdef __STL_MEMBER_TEMPLATES
    00752
    00753 template <class _Tp, class _Alloc> template <class _Predicate>
    00754 void list<_Tp, _Alloc>::remove_if(_Predicate __pred)
    00755 {
    00756   iterator __first = begin();
    00757   iterator __last = end();
    00758   while (__first != __last) {
    00759     iterator __next = __first;
    00760     ++__next;
    00761     if (__pred(*__first)) erase(__first);
    00762     __first = __next;
    00763   }
    00764 }
    00765
    00766 template <class _Tp, class _Alloc> template <class _BinaryPredicate>
    00767 void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
    00768 {
    00769   iterator __first = begin();
    00770   iterator __last = end();
    00771   if (__first == __last) return;
    00772   iterator __next = __first;
    00773   while (++__next != __last) {
    00774     if (__binary_pred(*__first, *__next))
    00775       erase(__next);
    00776     else
    00777       __first = __next;
    00778     __next = __first;
    00779   }
    00780 }
    00781
    00782 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
    00783 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x,
    00784                               _StrictWeakOrdering __comp)
    00785 {
    00786   iterator __first1 = begin();
    00787   iterator __last1 = end();
    00788   iterator __first2 = __x.begin();
    00789   iterator __last2 = __x.end();
    00790   while (__first1 != __last1 && __first2 != __last2)
    00791     if (__comp(*__first2, *__first1)) {
    00792       iterator __next = __first2;
    00793       transfer(__first1, __first2, ++__next);
    00794       __first2 = __next;
    00795     }
    00796     else
    00797       ++__first1;
    00798   if (__first2 != __last2) transfer(__last1, __first2, __last2);
    00799 }
    00800
    00801 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
    00802 void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
    00803 {
    00804   // Do nothing if the list has length 0 or 1.
    00805   if (_M_node->_M_next != _M_node &&
    00806       ((_Node*) (_M_node->_M_next))->_M_next != _M_node) {
    00807     list<_Tp, _Alloc> __carry;
    00808     list<_Tp, _Alloc> __counter[64];
    00809     int __fill = 0;
    00810     while (!empty()) {
    00811       __carry.splice(__carry.begin(), *this, begin());
    00812       int __i = 0;
    00813       while(__i < __fill && !__counter[__i].empty()) {
    00814         __counter[__i].merge(__carry, __comp);
    00815         __carry.swap(__counter[__i++]);
    00816       }
    00817       __carry.swap(__counter[__i]);
    00818       if (__i == __fill) ++__fill;
    00819     }
    00820
    00821     for (int __i = 1; __i < __fill; ++__i)
    00822       __counter[__i].merge(__counter[__i-1], __comp);
    00823     swap(__counter[__fill-1]);
    00824   }
    00825 }
    00826
    00827 #endif /* __STL_MEMBER_TEMPLATES */
    00828
    00829 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00830 #pragma reset woff 1174
    00831 #pragma reset woff 1375
    00832 #endif
    00833
    00834 __STL_END_NAMESPACE
    00835
    00836 #endif /* __SGI_STL_INTERNAL_LIST_H */
    00837
    00838 // Local Variables:
    00839 // mode:C++
    00840 // End: