stl_list.h

Go to the documentation of this file.
00001 // List implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996,1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00061 #ifndef __GLIBCPP_INTERNAL_LIST_H
00062 #define __GLIBCPP_INTERNAL_LIST_H
00063 
00064 #include <bits/concept_check.h>
00065 
00066 namespace std
00067 {
00068 
00069   struct _List_node_base
00070   {
00071     _List_node_base* _M_next;
00072     _List_node_base* _M_prev;
00073   };
00074 
00075   template<typename _Tp>
00076     struct _List_node : public _List_node_base
00077     {
00078       _Tp _M_data;
00079     };
00080 
00081   struct _List_iterator_base
00082   {
00083     typedef size_t                     size_type;
00084     typedef ptrdiff_t                  difference_type;
00085     typedef bidirectional_iterator_tag iterator_category;
00086 
00087     _List_node_base* _M_node;
00088 
00089     _List_iterator_base(_List_node_base* __x)
00090     : _M_node(__x)
00091     { }
00092 
00093     _List_iterator_base()
00094     { }
00095 
00096     void
00097     _M_incr()
00098     { _M_node = _M_node->_M_next; }
00099 
00100     void
00101     _M_decr()
00102     { _M_node = _M_node->_M_prev; }
00103 
00104     bool
00105     operator==(const _List_iterator_base& __x) const
00106     { return _M_node == __x._M_node; }
00107 
00108     bool
00109     operator!=(const _List_iterator_base& __x) const
00110     { return _M_node != __x._M_node; }
00111   };  
00112 
00113   template<typename _Tp, typename _Ref, typename _Ptr>
00114     struct _List_iterator : public _List_iterator_base
00115     {
00116       typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
00117       typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00118       typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;
00119 
00120       typedef _Tp value_type;
00121       typedef _Ptr pointer;
00122       typedef _Ref reference;
00123       typedef _List_node<_Tp> _Node;
00124 
00125       _List_iterator(_Node* __x)
00126       : _List_iterator_base(__x)
00127       { }
00128 
00129       _List_iterator()
00130       { }
00131 
00132       _List_iterator(const iterator& __x)
00133       : _List_iterator_base(__x._M_node)
00134       { }
00135 
00136       reference
00137       operator*() const
00138       { return ((_Node*) _M_node)->_M_data; }
00139 
00140       pointer
00141       operator->() const
00142       { return &(operator*()); }
00143 
00144       _Self&
00145       operator++()
00146       { 
00147         this->_M_incr();
00148         return *this;
00149       }
00150 
00151       _Self
00152       operator++(int)
00153       { 
00154         _Self __tmp = *this;
00155         this->_M_incr();
00156         return __tmp;
00157       }
00158 
00159       _Self&
00160       operator--()
00161       { 
00162         this->_M_decr();
00163         return *this;
00164       }
00165 
00166       _Self
00167       operator--(int)
00168       { 
00169         _Self __tmp = *this;
00170         this->_M_decr();
00171         return __tmp;
00172       }
00173     };
00174 
00175 
00176   // Base class that encapsulates details of allocators.  Three cases:
00177   // an ordinary standard-conforming allocator, a standard-conforming
00178   // allocator with no non-static data, and an SGI-style allocator.
00179   // This complexity is necessary only because we're worrying about backward
00180   // compatibility and because we want to avoid wasting storage on an 
00181   // allocator instance if it isn't necessary.
00182 
00183 
00184   // Base for general standard-conforming allocators.
00185   template<typename _Tp, typename _Allocator, bool _IsStatic>
00186     class _List_alloc_base
00187     {
00188     public:
00189       typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00190               allocator_type;
00191 
00192       allocator_type
00193       get_allocator() const
00194       { return _Node_allocator; }
00195 
00196       _List_alloc_base(const allocator_type& __a)
00197       : _Node_allocator(__a)
00198       { }
00199 
00200     protected:
00201       _List_node<_Tp>*
00202       _M_get_node()
00203       { return _Node_allocator.allocate(1); }
00204 
00205       void
00206       _M_put_node(_List_node<_Tp>* __p)
00207       { _Node_allocator.deallocate(__p, 1); }
00208 
00209     protected:
00210       typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
00211                _Node_allocator;
00212 
00213       _List_node<_Tp>* _M_node;
00214     };
00215 
00216   // Specialization for instanceless allocators.
00217 
00218   template<typename _Tp, typename _Allocator>
00219     class _List_alloc_base<_Tp, _Allocator, true>
00220     {
00221     public:
00222       typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00223               allocator_type;
00224 
00225       allocator_type
00226       get_allocator() const
00227       { return allocator_type(); }
00228 
00229       _List_alloc_base(const allocator_type&)
00230       { }
00231 
00232     protected:
00233       typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
00234               _Alloc_type;
00235 
00236       _List_node<_Tp>*
00237       _M_get_node()
00238       { return _Alloc_type::allocate(1); }
00239 
00240       void
00241       _M_put_node(_List_node<_Tp>* __p)
00242       { _Alloc_type::deallocate(__p, 1); }
00243 
00244     protected:
00245       _List_node<_Tp>* _M_node;
00246     };
00247 
00248   template<typename _Tp, typename _Alloc>
00249     class _List_base 
00250       : public _List_alloc_base<_Tp, _Alloc,
00251                                 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00252     {
00253     public:
00254       typedef _List_alloc_base<_Tp, _Alloc,
00255                                _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00256               _Base; 
00257       typedef typename _Base::allocator_type allocator_type;
00258 
00259       _List_base(const allocator_type& __a)
00260       : _Base(__a)
00261       {
00262         _M_node = _M_get_node();
00263         _M_node->_M_next = _M_node;
00264         _M_node->_M_prev = _M_node;
00265       }
00266 
00267       ~_List_base()
00268       {
00269         clear();
00270         _M_put_node(_M_node);
00271       }
00272 
00273       void clear();
00274     };
00275 
00289   template<typename _Tp, typename _Alloc = allocator<_Tp> >
00290     class list : protected _List_base<_Tp, _Alloc>
00291     {
00292       // concept requirements
00293       __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00294 
00295       typedef _List_base<_Tp, _Alloc> _Base;
00296     protected:
00297       typedef void* _Void_pointer;
00298 
00299     public:      
00300       typedef _Tp value_type;
00301       typedef value_type* pointer;
00302       typedef const value_type* const_pointer;
00303       typedef value_type& reference;
00304       typedef const value_type& const_reference;
00305       typedef _List_node<_Tp> _Node;
00306       typedef size_t size_type;
00307       typedef ptrdiff_t difference_type;
00308 
00309       typedef typename _Base::allocator_type allocator_type;
00310 
00311       typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
00312       typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00313 
00314       typedef reverse_iterator<const_iterator> const_reverse_iterator;
00315       typedef reverse_iterator<iterator>       reverse_iterator;
00316 
00317     protected:
00318       using _Base::_M_node;
00319       using _Base::_M_put_node;
00320       using _Base::_M_get_node;
00321 
00322     protected:
00323       _Node*
00324       _M_create_node(const _Tp& __x)
00325       {
00326         _Node* __p = _M_get_node();
00327         try {
00328           _Construct(&__p->_M_data, __x);
00329         }
00330         catch(...)
00331         { 
00332           _M_put_node(__p);
00333           __throw_exception_again; 
00334         }
00335         return __p;
00336       }
00337 
00338       _Node*
00339       _M_create_node()
00340       {
00341         _Node* __p = _M_get_node();
00342         try {
00343           _Construct(&__p->_M_data);
00344         }
00345         catch(...)
00346         { 
00347           _M_put_node(__p);
00348           __throw_exception_again; 
00349         }
00350         return __p;
00351       }
00352 
00353     public:
00354       allocator_type
00355       get_allocator() const
00356       { return _Base::get_allocator(); }
00357 
00358       explicit
00359       list(const allocator_type& __a = allocator_type())
00360       : _Base(__a)
00361       { }
00362 
00363       iterator
00364       begin()
00365       { return static_cast<_Node*>(_M_node->_M_next); }
00366 
00367       const_iterator
00368       begin() const
00369       { return static_cast<_Node*>(_M_node->_M_next); }
00370 
00371       iterator
00372       end()
00373       { return _M_node; }
00374 
00375       const_iterator
00376       end() const
00377       { return _M_node; }
00378 
00379       reverse_iterator
00380       rbegin() 
00381       { return reverse_iterator(end()); }
00382 
00383       const_reverse_iterator
00384       rbegin() const 
00385       { return const_reverse_iterator(end()); }
00386 
00387       reverse_iterator
00388       rend()
00389       { return reverse_iterator(begin()); }
00390 
00391       const_reverse_iterator
00392       rend() const
00393       { return const_reverse_iterator(begin()); }
00394 
00395       bool
00396       empty() const
00397       { return _M_node->_M_next == _M_node; }
00398 
00399       size_type
00400       size() const
00401       { return distance(begin(), end()); }
00402 
00403       size_type
00404       max_size() const
00405       { return size_type(-1); }
00406 
00407       reference
00408       front()
00409       { return *begin(); }
00410 
00411       const_reference
00412       front() const
00413       { return *begin(); }
00414 
00415       reference
00416       back()
00417       { return *(--end()); }
00418 
00419       const_reference
00420       back() const
00421       { return *(--end()); }
00422 
00423       void
00424       swap(list<_Tp, _Alloc>& __x)
00425       { std::swap(_M_node, __x._M_node); }
00426 
00427       iterator
00428       insert(iterator __position, const _Tp& __x)
00429       {
00430         _Node* __tmp = _M_create_node(__x);
00431         __tmp->_M_next = __position._M_node;
00432         __tmp->_M_prev = __position._M_node->_M_prev;
00433         __position._M_node->_M_prev->_M_next = __tmp;
00434         __position._M_node->_M_prev = __tmp;
00435         return __tmp;
00436       }
00437 
00438       iterator
00439       insert(iterator __position)
00440       { return insert(__position, _Tp()); }
00441 
00442       // Check whether it's an integral type.  If so, it's not an iterator.
00443       template<typename _Integer>
00444         void
00445         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
00446         { _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); }
00447 
00448       template<typename _InputIterator>
00449         void
00450         _M_insert_dispatch(iterator __pos,
00451                            _InputIterator __first, _InputIterator __last,
00452                            __false_type);
00453 
00454       template<typename _InputIterator>
00455         void
00456         insert(iterator __pos, _InputIterator __first, _InputIterator __last)
00457         {
00458           typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00459           _M_insert_dispatch(__pos, __first, __last, _Integral());
00460         }
00461 
00462       void
00463       insert(iterator __pos, size_type __n, const _Tp& __x)
00464       { _M_fill_insert(__pos, __n, __x); }
00465 
00466       void
00467       _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x); 
00468 
00469       void
00470       push_front(const _Tp& __x)
00471       { insert(begin(), __x); }
00472 
00473       void
00474       push_front()
00475       { insert(begin()); }
00476 
00477       void
00478       push_back(const _Tp& __x)
00479       { insert(end(), __x); }
00480 
00481       void
00482       push_back()
00483       { insert(end()); }
00484 
00485       iterator
00486       erase(iterator __position)
00487       {
00488         _List_node_base* __next_node = __position._M_node->_M_next;
00489         _List_node_base* __prev_node = __position._M_node->_M_prev;
00490         _Node* __n = static_cast<_Node*>(__position._M_node);
00491         __prev_node->_M_next = __next_node;
00492         __next_node->_M_prev = __prev_node;
00493         _Destroy(&__n->_M_data);
00494         _M_put_node(__n);
00495         return iterator(static_cast<_Node*>(__next_node));
00496       }
00497 
00498       iterator
00499       erase(iterator __first, iterator __last);
00500 
00501       void
00502       clear()
00503       { _Base::clear(); }
00504 
00505       void
00506       resize(size_type __new_size, const _Tp& __x);
00507       
00508       void
00509       resize(size_type __new_size)
00510       { this->resize(__new_size, _Tp()); }
00511 
00512       void
00513       pop_front()
00514       { erase(begin()); }
00515 
00516       void
00517       pop_back()
00518       { 
00519         iterator __tmp = end();
00520         erase(--__tmp);
00521       }
00522 
00523       list(size_type __n, const _Tp& __value,
00524            const allocator_type& __a = allocator_type())
00525       : _Base(__a)
00526       { insert(begin(), __n, __value); }
00527 
00528       explicit
00529       list(size_type __n)
00530       : _Base(allocator_type())
00531       { insert(begin(), __n, _Tp()); }
00532 
00533       // We don't need any dispatching tricks here, because insert does all of
00534       // that anyway.  
00535       template<typename _InputIterator>
00536       list(_InputIterator __first, _InputIterator __last,
00537            const allocator_type& __a = allocator_type())
00538       : _Base(__a)
00539       { insert(begin(), __first, __last); }
00540 
00541       list(const list<_Tp, _Alloc>& __x)
00542       : _Base(__x.get_allocator())
00543       { insert(begin(), __x.begin(), __x.end()); }
00544 
00545       ~list()
00546       { }
00547 
00548       list<_Tp, _Alloc>&
00549       operator=(const list<_Tp, _Alloc>& __x);
00550 
00551     public:
00552       // assign(), a generalized assignment member function.  Two
00553       // versions: one that takes a count, and one that takes a range.
00554       // The range version is a member template, so we dispatch on whether
00555       // or not the type is an integer.
00556 
00557       void
00558       assign(size_type __n, const _Tp& __val)
00559       { _M_fill_assign(__n, __val); }
00560 
00561       void
00562       _M_fill_assign(size_type __n, const _Tp& __val);
00563 
00564       template<typename _InputIterator>
00565         void
00566         assign(_InputIterator __first, _InputIterator __last)
00567         {
00568           typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00569           _M_assign_dispatch(__first, __last, _Integral());
00570         }
00571 
00572       template<typename _Integer>
00573         void
00574         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00575         { _M_fill_assign((size_type) __n, (_Tp) __val); }
00576 
00577       template<typename _InputIterator>
00578         void
00579         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00580                            __false_type);
00581 
00582     protected:
00583       void
00584       _M_transfer(iterator __position, iterator __first, iterator __last)
00585       {
00586         if (__position != __last) {
00587           // Remove [first, last) from its old position.
00588           __last._M_node->_M_prev->_M_next     = __position._M_node;
00589           __first._M_node->_M_prev->_M_next    = __last._M_node;
00590           __position._M_node->_M_prev->_M_next = __first._M_node; 
00591 
00592           // Splice [first, last) into its new position.
00593           _List_node_base* __tmp      = __position._M_node->_M_prev;
00594           __position._M_node->_M_prev = __last._M_node->_M_prev;
00595           __last._M_node->_M_prev     = __first._M_node->_M_prev; 
00596           __first._M_node->_M_prev    = __tmp;
00597         }
00598       }
00599 
00600     public:
00601       void
00602       splice(iterator __position, list& __x)
00603       {
00604         if (!__x.empty()) 
00605           this->_M_transfer(__position, __x.begin(), __x.end());
00606       }
00607 
00608       void
00609       splice(iterator __position, list&, iterator __i)
00610       {
00611         iterator __j = __i;
00612         ++__j;
00613         if (__position == __i || __position == __j) return;
00614         this->_M_transfer(__position, __i, __j);
00615       }
00616 
00617       void
00618       splice(iterator __position, list&, iterator __first, iterator __last)
00619       {
00620         if (__first != __last) 
00621           this->_M_transfer(__position, __first, __last);
00622       }
00623 
00624       void
00625       remove(const _Tp& __value);
00626 
00627       void
00628       unique();
00629 
00630       void
00631       merge(list& __x);
00632 
00633       void
00634       reverse();
00635 
00636       void
00637       sort();
00638 
00639       template<typename _Predicate>
00640         void
00641         remove_if(_Predicate);
00642 
00643       template<typename _BinaryPredicate>
00644         void
00645         unique(_BinaryPredicate);
00646 
00647       template<typename _StrictWeakOrdering>
00648         void
00649         merge(list&, _StrictWeakOrdering);
00650 
00651       template<typename _StrictWeakOrdering>
00652         void
00653         sort(_StrictWeakOrdering);
00654     };
00655 
00656   template<typename _Tp, typename _Alloc>
00657     inline bool 
00658     operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
00659     {
00660       typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
00661       const_iterator __end1 = __x.end();
00662       const_iterator __end2 = __y.end();
00663 
00664       const_iterator __i1 = __x.begin();
00665       const_iterator __i2 = __y.begin();
00666       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
00667         ++__i1;
00668         ++__i2;
00669       }
00670       return __i1 == __end1 && __i2 == __end2;
00671     }
00672 
00673   template<typename _Tp, typename _Alloc>
00674     inline bool
00675     operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
00676     {
00677       return lexicographical_compare(__x.begin(), __x.end(),
00678                                      __y.begin(), __y.end());
00679     }
00680 
00681   template<typename _Tp, typename _Alloc>
00682     inline bool
00683     operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
00684     { return !(__x == __y); }
00685 
00686   template<typename _Tp, typename _Alloc>
00687     inline bool
00688     operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
00689     { return __y < __x; }
00690 
00691   template<typename _Tp, typename _Alloc>
00692     inline bool
00693     operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
00694     { return !(__y < __x); }
00695 
00696   template<typename _Tp, typename _Alloc>
00697     inline bool
00698     operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
00699     { return !(__x < __y); }
00700 
00701   template<typename _Tp, typename _Alloc>
00702     inline void 
00703     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
00704     { __x.swap(__y); }
00705 
00706   // move these to stl_list.tcc
00707 
00708   template<typename _Tp, typename _Alloc>
00709     void _List_base<_Tp,_Alloc>::
00710     clear() 
00711     {
00712       _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
00713       while (__cur != _M_node) {
00714         _List_node<_Tp>* __tmp = __cur;
00715         __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
00716         _Destroy(&__tmp->_M_data);
00717         _M_put_node(__tmp);
00718       }
00719       _M_node->_M_next = _M_node;
00720       _M_node->_M_prev = _M_node;
00721     }
00722 
00723   template<typename _Tp, typename _Alloc>
00724     template <typename _InputIter>
00725       void list<_Tp, _Alloc>::
00726       _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
00727                                             __false_type)
00728       {
00729         for ( ; __first != __last; ++__first)
00730           insert(__position, *__first);
00731       
00732       }
00733 
00734   template<typename _Tp, typename _Alloc>
00735     void list<_Tp, _Alloc>::
00736     _M_fill_insert(iterator __position, size_type __n, const _Tp& __x)
00737     {
00738       for ( ; __n > 0; --__n)
00739         insert(__position, __x);
00740     }
00741 
00742   template<typename _Tp, typename _Alloc>
00743     typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::
00744     erase(iterator __first, iterator __last)
00745     {
00746       while (__first != __last)
00747         erase(__first++);
00748       return __last;
00749     }
00750 
00751   template<typename _Tp, typename _Alloc>
00752     void list<_Tp, _Alloc>::
00753     resize(size_type __new_size, const _Tp& __x)
00754     {
00755       iterator __i = begin();
00756       size_type __len = 0;
00757       for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
00758         ;
00759       if (__len == __new_size)
00760         erase(__i, end());
00761       else                          // __i == end()
00762         insert(end(), __new_size - __len, __x);
00763     }
00764 
00765   template<typename _Tp, typename _Alloc>
00766     list<_Tp, _Alloc>& list<_Tp, _Alloc>::
00767     operator=(const list<_Tp, _Alloc>& __x)
00768     {
00769       if (this != &__x) {
00770         iterator __first1 = begin();
00771         iterator __last1 = end();
00772         const_iterator __first2 = __x.begin();
00773         const_iterator __last2 = __x.end();
00774         while (__first1 != __last1 && __first2 != __last2) 
00775           *__first1++ = *__first2++;
00776         if (__first2 == __last2)
00777           erase(__first1, __last1);
00778         else
00779           insert(__last1, __first2, __last2);
00780       }
00781       return *this;
00782     }
00783 
00784   template<typename _Tp, typename _Alloc>
00785     void list<_Tp, _Alloc>::
00786     _M_fill_assign(size_type __n, const _Tp& __val) {
00787       iterator __i = begin();
00788       for ( ; __i != end() && __n > 0; ++__i, --__n)
00789         *__i = __val;
00790       if (__n > 0)
00791         insert(end(), __n, __val);
00792       else
00793         erase(__i, end());
00794     }
00795 
00796   template<typename _Tp, typename _Alloc>
00797     template <typename _InputIter>
00798       void list<_Tp, _Alloc>::
00799       _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type)
00800       {
00801         iterator __first1 = begin();
00802         iterator __last1 = end();
00803         for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
00804           *__first1 = *__first2;
00805         if (__first2 == __last2)
00806           erase(__first1, __last1);
00807         else
00808           insert(__last1, __first2, __last2);
00809       }
00810 
00811   template<typename _Tp, typename _Alloc>
00812     void list<_Tp, _Alloc>::
00813     remove(const _Tp& __value)
00814     {
00815       iterator __first = begin();
00816       iterator __last = end();
00817       while (__first != __last) {
00818         iterator __next = __first;
00819         ++__next;
00820         if (*__first == __value) erase(__first);
00821         __first = __next;
00822       }
00823     }
00824 
00825   template<typename _Tp, typename _Alloc>
00826     void list<_Tp, _Alloc>::
00827     unique()
00828     {
00829       iterator __first = begin();
00830       iterator __last = end();
00831       if (__first == __last) return;
00832       iterator __next = __first;
00833       while (++__next != __last) {
00834         if (*__first == *__next)
00835           erase(__next);
00836         else
00837           __first = __next;
00838         __next = __first;
00839       }
00840     }
00841 
00842   template<typename _Tp, typename _Alloc>
00843     void list<_Tp, _Alloc>::
00844     merge(list<_Tp, _Alloc>& __x)
00845     {
00846       iterator __first1 = begin();
00847       iterator __last1 = end();
00848       iterator __first2 = __x.begin();
00849       iterator __last2 = __x.end();
00850       while (__first1 != __last1 && __first2 != __last2)
00851         if (*__first2 < *__first1) {
00852           iterator __next = __first2;
00853           _M_transfer(__first1, __first2, ++__next);
00854           __first2 = __next;
00855         }
00856         else
00857           ++__first1;
00858       if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
00859     }
00860 
00861   inline void
00862   __List_base_reverse(_List_node_base* __p)
00863   {
00864     _List_node_base* __tmp = __p;
00865     do {
00866       std::swap(__tmp->_M_next, __tmp->_M_prev);
00867       __tmp = __tmp->_M_prev;     // Old next node is now prev.
00868     } while (__tmp != __p);
00869   }
00870 
00871   template<typename _Tp, typename _Alloc>
00872   inline void list<_Tp, _Alloc>::
00873   reverse() 
00874   { __List_base_reverse(this->_M_node); }    
00875 
00876   template<typename _Tp, typename _Alloc>
00877     void list<_Tp, _Alloc>::
00878     sort()
00879     {
00880       // Do nothing if the list has length 0 or 1.
00881       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
00882         list<_Tp, _Alloc> __carry;
00883         list<_Tp, _Alloc> __counter[64];
00884         int __fill = 0;
00885         while (!empty()) {
00886           __carry.splice(__carry.begin(), *this, begin());
00887           int __i = 0;
00888           while(__i < __fill && !__counter[__i].empty()) {
00889             __counter[__i].merge(__carry);
00890             __carry.swap(__counter[__i++]);
00891           }
00892           __carry.swap(__counter[__i]);         
00893           if (__i == __fill) ++__fill;
00894         } 
00895 
00896         for (int __i = 1; __i < __fill; ++__i)
00897           __counter[__i].merge(__counter[__i-1]);
00898         swap(__counter[__fill-1]);
00899       }
00900     }
00901 
00902   template<typename _Tp, typename _Alloc>
00903     template <typename _Predicate>
00904       void list<_Tp, _Alloc>::
00905       remove_if(_Predicate __pred)
00906       {
00907         iterator __first = begin();
00908         iterator __last = end();
00909         while (__first != __last) {
00910           iterator __next = __first;
00911           ++__next;
00912           if (__pred(*__first)) erase(__first);
00913           __first = __next;
00914         }
00915       }
00916 
00917   template<typename _Tp, typename _Alloc>
00918     template <typename _BinaryPredicate>
00919       void list<_Tp, _Alloc>::
00920       unique(_BinaryPredicate __binary_pred)
00921       {
00922         iterator __first = begin();
00923         iterator __last = end();
00924         if (__first == __last) return;
00925         iterator __next = __first;
00926         while (++__next != __last) {
00927           if (__binary_pred(*__first, *__next))
00928             erase(__next);
00929           else
00930             __first = __next;
00931           __next = __first;
00932         }
00933       }
00934 
00935   template<typename _Tp, typename _Alloc>
00936     template <typename _StrictWeakOrdering>
00937       void list<_Tp, _Alloc>::
00938       merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp)
00939       {
00940         iterator __first1 = begin();
00941         iterator __last1 = end();
00942         iterator __first2 = __x.begin();
00943         iterator __last2 = __x.end();
00944         while (__first1 != __last1 && __first2 != __last2)
00945           if (__comp(*__first2, *__first1)) {
00946             iterator __next = __first2;
00947             _M_transfer(__first1, __first2, ++__next);
00948             __first2 = __next;
00949           }
00950           else
00951             ++__first1;
00952         if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
00953       }
00954 
00955   template<typename _Tp, typename _Alloc>
00956     template <typename _StrictWeakOrdering>
00957     void list<_Tp, _Alloc>::
00958     sort(_StrictWeakOrdering __comp)
00959     {
00960       // Do nothing if the list has length 0 or 1.
00961       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
00962         list<_Tp, _Alloc> __carry;
00963         list<_Tp, _Alloc> __counter[64];
00964         int __fill = 0;
00965         while (!empty()) {
00966           __carry.splice(__carry.begin(), *this, begin());
00967           int __i = 0;
00968           while(__i < __fill && !__counter[__i].empty()) {
00969             __counter[__i].merge(__carry, __comp);
00970             __carry.swap(__counter[__i++]);
00971           }
00972           __carry.swap(__counter[__i]);         
00973           if (__i == __fill) ++__fill;
00974         } 
00975 
00976         for (int __i = 1; __i < __fill; ++__i) 
00977           __counter[__i].merge(__counter[__i-1], __comp);
00978         swap(__counter[__fill-1]);
00979       }
00980     }
00981 
00982 } // namespace std 
00983 
00984 #endif /* __GLIBCPP_INTERNAL_LIST_H */
00985 
00986 // vi:set ts=2 sw=2:
00987 // Local Variables:
00988 // mode:C++
00989 // End:

Generated on Tue Dec 23 12:34:09 2003 for libstdc++-v3 Source by doxygen 1.3.4