stl_list.h

Go to the documentation of this file.
00001 // List implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 2, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /*
00032  *
00033  * Copyright (c) 1994
00034  * Hewlett-Packard Company
00035  *
00036  * Permission to use, copy, modify, distribute and sell this software
00037  * and its documentation for any purpose is hereby granted without fee,
00038  * provided that the above copyright notice appear in all copies and
00039  * that both that copyright notice and this permission notice appear
00040  * in supporting documentation.  Hewlett-Packard Company makes no
00041  * representations about the suitability of this software for any
00042  * purpose.  It is provided "as is" without express or implied warranty.
00043  *
00044  *
00045  * Copyright (c) 1996,1997
00046  * Silicon Graphics Computer Systems, Inc.
00047  *
00048  * Permission to use, copy, modify, distribute and sell this software
00049  * and its documentation for any purpose is hereby granted without fee,
00050  * provided that the above copyright notice appear in all copies and
00051  * that both that copyright notice and this permission notice appear
00052  * in supporting documentation.  Silicon Graphics makes no
00053  * representations about the suitability of this software for any
00054  * purpose.  It is provided "as is" without express or implied warranty.
00055  */
00056 
00057 /** @file stl_list.h
00058  *  This is an internal header file, included by other library headers.
00059  *  You should not attempt to use it directly.
00060  */
00061 
00062 #ifndef _STL_LIST_H
00063 #define _STL_LIST_H 1
00064 
00065 #include <bits/concept_check.h>
00066 
00067 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00068 
00069   // Supporting structures are split into common and templated types; the
00070   // latter publicly inherits from the former in an effort to reduce code
00071   // duplication.  This results in some "needless" static_cast'ing later on,
00072   // but it's all safe downcasting.
00073 
00074   /// Common part of a node in the %list. 
00075   struct _List_node_base
00076   {
00077     _List_node_base* _M_next;
00078     _List_node_base* _M_prev;
00079 
00080     static void
00081     swap(_List_node_base& __x, _List_node_base& __y);
00082 
00083     void
00084     transfer(_List_node_base * const __first,
00085          _List_node_base * const __last);
00086 
00087     void
00088     reverse();
00089 
00090     void
00091     hook(_List_node_base * const __position);
00092 
00093     void
00094     unhook();
00095   };
00096 
00097   /// An actual node in the %list.
00098   template<typename _Tp>
00099     struct _List_node : public _List_node_base
00100     {
00101       ///< User's data.
00102       _Tp _M_data;
00103     };
00104 
00105   /**
00106    *  @brief A list::iterator.
00107    *
00108    *  All the functions are op overloads.
00109   */
00110   template<typename _Tp>
00111     struct _List_iterator
00112     {
00113       typedef _List_iterator<_Tp>                _Self;
00114       typedef _List_node<_Tp>                    _Node;
00115 
00116       typedef ptrdiff_t                          difference_type;
00117       typedef std::bidirectional_iterator_tag    iterator_category;
00118       typedef _Tp                                value_type;
00119       typedef _Tp*                               pointer;
00120       typedef _Tp&                               reference;
00121 
00122       _List_iterator()
00123       : _M_node() { }
00124 
00125       explicit
00126       _List_iterator(_List_node_base* __x)
00127       : _M_node(__x) { }
00128 
00129       // Must downcast from List_node_base to _List_node to get to _M_data.
00130       reference
00131       operator*() const
00132       { return static_cast<_Node*>(_M_node)->_M_data; }
00133 
00134       pointer
00135       operator->() const
00136       { return &static_cast<_Node*>(_M_node)->_M_data; }
00137 
00138       _Self&
00139       operator++()
00140       {
00141     _M_node = _M_node->_M_next;
00142     return *this;
00143       }
00144 
00145       _Self
00146       operator++(int)
00147       {
00148     _Self __tmp = *this;
00149     _M_node = _M_node->_M_next;
00150     return __tmp;
00151       }
00152 
00153       _Self&
00154       operator--()
00155       {
00156     _M_node = _M_node->_M_prev;
00157     return *this;
00158       }
00159 
00160       _Self
00161       operator--(int)
00162       {
00163     _Self __tmp = *this;
00164     _M_node = _M_node->_M_prev;
00165     return __tmp;
00166       }
00167 
00168       bool
00169       operator==(const _Self& __x) const
00170       { return _M_node == __x._M_node; }
00171 
00172       bool
00173       operator!=(const _Self& __x) const
00174       { return _M_node != __x._M_node; }
00175 
00176       // The only member points to the %list element.
00177       _List_node_base* _M_node;
00178     };
00179 
00180   /**
00181    *  @brief A list::const_iterator.
00182    *
00183    *  All the functions are op overloads.
00184   */
00185   template<typename _Tp>
00186     struct _List_const_iterator
00187     {
00188       typedef _List_const_iterator<_Tp>          _Self;
00189       typedef const _List_node<_Tp>              _Node;
00190       typedef _List_iterator<_Tp>                iterator;
00191 
00192       typedef ptrdiff_t                          difference_type;
00193       typedef std::bidirectional_iterator_tag    iterator_category;
00194       typedef _Tp                                value_type;
00195       typedef const _Tp*                         pointer;
00196       typedef const _Tp&                         reference;
00197 
00198       _List_const_iterator()
00199       : _M_node() { }
00200 
00201       explicit
00202       _List_const_iterator(const _List_node_base* __x)
00203       : _M_node(__x) { }
00204 
00205       _List_const_iterator(const iterator& __x)
00206       : _M_node(__x._M_node) { }
00207 
00208       // Must downcast from List_node_base to _List_node to get to
00209       // _M_data.
00210       reference
00211       operator*() const
00212       { return static_cast<_Node*>(_M_node)->_M_data; }
00213 
00214       pointer
00215       operator->() const
00216       { return &static_cast<_Node*>(_M_node)->_M_data; }
00217 
00218       _Self&
00219       operator++()
00220       {
00221     _M_node = _M_node->_M_next;
00222     return *this;
00223       }
00224 
00225       _Self
00226       operator++(int)
00227       {
00228     _Self __tmp = *this;
00229     _M_node = _M_node->_M_next;
00230     return __tmp;
00231       }
00232 
00233       _Self&
00234       operator--()
00235       {
00236     _M_node = _M_node->_M_prev;
00237     return *this;
00238       }
00239 
00240       _Self
00241       operator--(int)
00242       {
00243     _Self __tmp = *this;
00244     _M_node = _M_node->_M_prev;
00245     return __tmp;
00246       }
00247 
00248       bool
00249       operator==(const _Self& __x) const
00250       { return _M_node == __x._M_node; }
00251 
00252       bool
00253       operator!=(const _Self& __x) const
00254       { return _M_node != __x._M_node; }
00255 
00256       // The only member points to the %list element.
00257       const _List_node_base* _M_node;
00258     };
00259 
00260   template<typename _Val>
00261     inline bool
00262     operator==(const _List_iterator<_Val>& __x,
00263            const _List_const_iterator<_Val>& __y)
00264     { return __x._M_node == __y._M_node; }
00265 
00266   template<typename _Val>
00267     inline bool
00268     operator!=(const _List_iterator<_Val>& __x,
00269                const _List_const_iterator<_Val>& __y)
00270     { return __x._M_node != __y._M_node; }
00271 
00272 
00273   /// See bits/stl_deque.h's _Deque_base for an explanation.
00274   template<typename _Tp, typename _Alloc>
00275     class _List_base
00276     {
00277     protected:
00278       // NOTA BENE
00279       // The stored instance is not actually of "allocator_type"'s
00280       // type.  Instead we rebind the type to
00281       // Allocator<List_node<Tp>>, which according to [20.1.5]/4
00282       // should probably be the same.  List_node<Tp> is not the same
00283       // size as Tp (it's two pointers larger), and specializations on
00284       // Tp may go unused because List_node<Tp> is being bound
00285       // instead.
00286       //
00287       // We put this to the test in the constructors and in
00288       // get_allocator, where we use conversions between
00289       // allocator_type and _Node_alloc_type. The conversion is
00290       // required by table 32 in [20.1.5].
00291       typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
00292         _Node_alloc_type;
00293 
00294       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
00295 
00296       struct _List_impl 
00297       : public _Node_alloc_type
00298       {
00299     _List_node_base _M_node;
00300 
00301     _List_impl()
00302     : _Node_alloc_type(), _M_node()
00303     { }
00304 
00305     _List_impl(const _Node_alloc_type& __a)
00306     : _Node_alloc_type(__a), _M_node()
00307     { }
00308       };
00309 
00310       _List_impl _M_impl;
00311 
00312       _List_node<_Tp>*
00313       _M_get_node()
00314       { return _M_impl._Node_alloc_type::allocate(1); }
00315       
00316       void
00317       _M_put_node(_List_node<_Tp>* __p)
00318       { _M_impl._Node_alloc_type::deallocate(__p, 1); }
00319       
00320   public:
00321       typedef _Alloc allocator_type;
00322 
00323       _Node_alloc_type&
00324       _M_get_Node_allocator()
00325       { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
00326 
00327       const _Node_alloc_type&
00328       _M_get_Node_allocator() const
00329       { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
00330 
00331       _Tp_alloc_type
00332       _M_get_Tp_allocator() const
00333       { return _Tp_alloc_type(_M_get_Node_allocator()); }
00334 
00335       allocator_type
00336       get_allocator() const
00337       { return allocator_type(_M_get_Node_allocator()); }
00338 
00339       _List_base()
00340       : _M_impl()
00341       { _M_init(); }
00342 
00343       _List_base(const allocator_type& __a)
00344       : _M_impl(__a)
00345       { _M_init(); }
00346 
00347 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00348       _List_base(_List_base&& __x)
00349       : _M_impl(__x._M_get_Node_allocator())
00350       {
00351     _M_init();
00352     _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node);  
00353       }
00354 #endif
00355 
00356       // This is what actually destroys the list.
00357       ~_List_base()
00358       { _M_clear(); }
00359 
00360       void
00361       _M_clear();
00362 
00363       void
00364       _M_init()
00365       {
00366         this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
00367         this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
00368       }
00369     };
00370 
00371   /**
00372    *  @brief A standard container with linear time access to elements,
00373    *  and fixed time insertion/deletion at any point in the sequence.
00374    *
00375    *  @ingroup Containers
00376    *  @ingroup Sequences
00377    *
00378    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00379    *  <a href="tables.html#66">reversible container</a>, and a
00380    *  <a href="tables.html#67">sequence</a>, including the
00381    *  <a href="tables.html#68">optional sequence requirements</a> with the
00382    *  %exception of @c at and @c operator[].
00383    *
00384    *  This is a @e doubly @e linked %list.  Traversal up and down the
00385    *  %list requires linear time, but adding and removing elements (or
00386    *  @e nodes) is done in constant time, regardless of where the
00387    *  change takes place.  Unlike std::vector and std::deque,
00388    *  random-access iterators are not provided, so subscripting ( @c
00389    *  [] ) access is not allowed.  For algorithms which only need
00390    *  sequential access, this lack makes no difference.
00391    *
00392    *  Also unlike the other standard containers, std::list provides
00393    *  specialized algorithms %unique to linked lists, such as
00394    *  splicing, sorting, and in-place reversal.
00395    *
00396    *  A couple points on memory allocation for list<Tp>:
00397    *
00398    *  First, we never actually allocate a Tp, we allocate
00399    *  List_node<Tp>'s and trust [20.1.5]/4 to DTRT.  This is to ensure
00400    *  that after elements from %list<X,Alloc1> are spliced into
00401    *  %list<X,Alloc2>, destroying the memory of the second %list is a
00402    *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
00403    *
00404    *  Second, a %list conceptually represented as
00405    *  @code
00406    *    A <---> B <---> C <---> D
00407    *  @endcode
00408    *  is actually circular; a link exists between A and D.  The %list
00409    *  class holds (as its only data member) a private list::iterator
00410    *  pointing to @e D, not to @e A!  To get to the head of the %list,
00411    *  we start at the tail and move forward by one.  When this member
00412    *  iterator's next/previous pointers refer to itself, the %list is
00413    *  %empty. 
00414   */
00415   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00416     class list : protected _List_base<_Tp, _Alloc>
00417     {
00418       // concept requirements
00419       typedef typename _Alloc::value_type                _Alloc_value_type;
00420       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00421       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00422 
00423       typedef _List_base<_Tp, _Alloc>                    _Base;
00424       typedef typename _Base::_Tp_alloc_type         _Tp_alloc_type;
00425 
00426     public:
00427       typedef _Tp                                        value_type;
00428       typedef typename _Tp_alloc_type::pointer           pointer;
00429       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
00430       typedef typename _Tp_alloc_type::reference         reference;
00431       typedef typename _Tp_alloc_type::const_reference   const_reference;
00432       typedef _List_iterator<_Tp>                        iterator;
00433       typedef _List_const_iterator<_Tp>                  const_iterator;
00434       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
00435       typedef std::reverse_iterator<iterator>            reverse_iterator;
00436       typedef size_t                                     size_type;
00437       typedef ptrdiff_t                                  difference_type;
00438       typedef _Alloc                                     allocator_type;
00439 
00440     protected:
00441       // Note that pointers-to-_Node's can be ctor-converted to
00442       // iterator types.
00443       typedef _List_node<_Tp>                _Node;
00444 
00445       using _Base::_M_impl;
00446       using _Base::_M_put_node;
00447       using _Base::_M_get_node;
00448       using _Base::_M_get_Tp_allocator;
00449       using _Base::_M_get_Node_allocator;
00450 
00451       /**
00452        *  @param  x  An instance of user data.
00453        *
00454        *  Allocates space for a new node and constructs a copy of @a x in it.
00455        */
00456 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00457       _Node*
00458       _M_create_node(const value_type& __x)
00459       {
00460     _Node* __p = this->_M_get_node();
00461     try
00462       {
00463         _M_get_Tp_allocator().construct(&__p->_M_data, __x);
00464       }
00465     catch(...)
00466       {
00467         _M_put_node(__p);
00468         __throw_exception_again;
00469       }
00470     return __p;
00471       }
00472 #else
00473       template<typename... _Args>
00474         _Node*
00475         _M_create_node(_Args&&... __args)
00476     {
00477       _Node* __p = this->_M_get_node();
00478       try
00479         {
00480           _M_get_Tp_allocator().construct(&__p->_M_data,
00481                           std::forward<_Args>(__args)...);
00482         }
00483       catch(...)
00484         {
00485           _M_put_node(__p);
00486           __throw_exception_again;
00487         }
00488       return __p;
00489     }
00490 #endif
00491 
00492     public:
00493       // [23.2.2.1] construct/copy/destroy
00494       // (assign() and get_allocator() are also listed in this section)
00495       /**
00496        *  @brief  Default constructor creates no elements.
00497        */
00498       list()
00499       : _Base() { }
00500 
00501       /**
00502        *  @brief  Creates a %list with no elements.
00503        *  @param  a  An allocator object.
00504        */
00505       explicit
00506       list(const allocator_type& __a)
00507       : _Base(__a) { }
00508 
00509       /**
00510        *  @brief  Creates a %list with copies of an exemplar element.
00511        *  @param  n  The number of elements to initially create.
00512        *  @param  value  An element to copy.
00513        *  @param  a  An allocator object.
00514        *
00515        *  This constructor fills the %list with @a n copies of @a value.
00516        */
00517       explicit
00518       list(size_type __n, const value_type& __value = value_type(),
00519        const allocator_type& __a = allocator_type())
00520       : _Base(__a)
00521       { _M_fill_initialize(__n, __value); }
00522 
00523       /**
00524        *  @brief  %List copy constructor.
00525        *  @param  x  A %list of identical element and allocator types.
00526        *
00527        *  The newly-created %list uses a copy of the allocation object used
00528        *  by @a x.
00529        */
00530       list(const list& __x)
00531       : _Base(__x._M_get_Node_allocator())
00532       { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
00533 
00534 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00535       /**
00536        *  @brief  %List move constructor.
00537        *  @param  x  A %list of identical element and allocator types.
00538        *
00539        *  The newly-created %list contains the exact contents of @a x.
00540        *  The contents of @a x are a valid, but unspecified %list.
00541        */
00542       list(list&& __x)
00543       : _Base(std::forward<_Base>(__x)) { }
00544 #endif
00545 
00546       /**
00547        *  @brief  Builds a %list from a range.
00548        *  @param  first  An input iterator.
00549        *  @param  last  An input iterator.
00550        *  @param  a  An allocator object.
00551        *
00552        *  Create a %list consisting of copies of the elements from
00553        *  [@a first,@a last).  This is linear in N (where N is
00554        *  distance(@a first,@a last)).
00555        */
00556       template<typename _InputIterator>
00557         list(_InputIterator __first, _InputIterator __last,
00558          const allocator_type& __a = allocator_type())
00559         : _Base(__a)
00560         { 
00561       // Check whether it's an integral type.  If so, it's not an iterator.
00562       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00563       _M_initialize_dispatch(__first, __last, _Integral());
00564     }
00565 
00566       /**
00567        *  No explicit dtor needed as the _Base dtor takes care of
00568        *  things.  The _Base dtor only erases the elements, and note
00569        *  that if the elements themselves are pointers, the pointed-to
00570        *  memory is not touched in any way.  Managing the pointer is
00571        *  the user's responsibility.
00572        */
00573 
00574       /**
00575        *  @brief  %List assignment operator.
00576        *  @param  x  A %list of identical element and allocator types.
00577        *
00578        *  All the elements of @a x are copied, but unlike the copy
00579        *  constructor, the allocator object is not copied.
00580        */
00581       list&
00582       operator=(const list& __x);
00583 
00584 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00585       /**
00586        *  @brief  %List move assignment operator.
00587        *  @param  x  A %list of identical element and allocator types.
00588        *
00589        *  The contents of @a x are moved into this %list (without copying).
00590        *  @a x is a valid, but unspecified %list
00591        */
00592       list&
00593       operator=(list&& __x)
00594       {
00595     // NB: DR 675.
00596     this->clear();
00597     this->swap(__x); 
00598     return *this;
00599       }
00600 #endif
00601 
00602       /**
00603        *  @brief  Assigns a given value to a %list.
00604        *  @param  n  Number of elements to be assigned.
00605        *  @param  val  Value to be assigned.
00606        *
00607        *  This function fills a %list with @a n copies of the given
00608        *  value.  Note that the assignment completely changes the %list
00609        *  and that the resulting %list's size is the same as the number
00610        *  of elements assigned.  Old data may be lost.
00611        */
00612       void
00613       assign(size_type __n, const value_type& __val)
00614       { _M_fill_assign(__n, __val); }
00615 
00616       /**
00617        *  @brief  Assigns a range to a %list.
00618        *  @param  first  An input iterator.
00619        *  @param  last   An input iterator.
00620        *
00621        *  This function fills a %list with copies of the elements in the
00622        *  range [@a first,@a last).
00623        *
00624        *  Note that the assignment completely changes the %list and
00625        *  that the resulting %list's size is the same as the number of
00626        *  elements assigned.  Old data may be lost.
00627        */
00628       template<typename _InputIterator>
00629         void
00630         assign(_InputIterator __first, _InputIterator __last)
00631         {
00632       // Check whether it's an integral type.  If so, it's not an iterator.
00633       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00634       _M_assign_dispatch(__first, __last, _Integral());
00635     }
00636 
00637       /// Get a copy of the memory allocation object.
00638       allocator_type
00639       get_allocator() const
00640       { return _Base::get_allocator(); }
00641 
00642       // iterators
00643       /**
00644        *  Returns a read/write iterator that points to the first element in the
00645        *  %list.  Iteration is done in ordinary element order.
00646        */
00647       iterator
00648       begin()
00649       { return iterator(this->_M_impl._M_node._M_next); }
00650 
00651       /**
00652        *  Returns a read-only (constant) iterator that points to the
00653        *  first element in the %list.  Iteration is done in ordinary
00654        *  element order.
00655        */
00656       const_iterator
00657       begin() const
00658       { return const_iterator(this->_M_impl._M_node._M_next); }
00659 
00660       /**
00661        *  Returns a read/write iterator that points one past the last
00662        *  element in the %list.  Iteration is done in ordinary element
00663        *  order.
00664        */
00665       iterator
00666       end()
00667       { return iterator(&this->_M_impl._M_node); }
00668 
00669       /**
00670        *  Returns a read-only (constant) iterator that points one past
00671        *  the last element in the %list.  Iteration is done in ordinary
00672        *  element order.
00673        */
00674       const_iterator
00675       end() const
00676       { return const_iterator(&this->_M_impl._M_node); }
00677 
00678       /**
00679        *  Returns a read/write reverse iterator that points to the last
00680        *  element in the %list.  Iteration is done in reverse element
00681        *  order.
00682        */
00683       reverse_iterator
00684       rbegin()
00685       { return reverse_iterator(end()); }
00686 
00687       /**
00688        *  Returns a read-only (constant) reverse iterator that points to
00689        *  the last element in the %list.  Iteration is done in reverse
00690        *  element order.
00691        */
00692       const_reverse_iterator
00693       rbegin() const
00694       { return const_reverse_iterator(end()); }
00695 
00696       /**
00697        *  Returns a read/write reverse iterator that points to one
00698        *  before the first element in the %list.  Iteration is done in
00699        *  reverse element order.
00700        */
00701       reverse_iterator
00702       rend()
00703       { return reverse_iterator(begin()); }
00704 
00705       /**
00706        *  Returns a read-only (constant) reverse iterator that points to one
00707        *  before the first element in the %list.  Iteration is done in reverse
00708        *  element order.
00709        */
00710       const_reverse_iterator
00711       rend() const
00712       { return const_reverse_iterator(begin()); }
00713 
00714 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00715       /**
00716        *  Returns a read-only (constant) iterator that points to the
00717        *  first element in the %list.  Iteration is done in ordinary
00718        *  element order.
00719        */
00720       const_iterator
00721       cbegin() const
00722       { return const_iterator(this->_M_impl._M_node._M_next); }
00723 
00724       /**
00725        *  Returns a read-only (constant) iterator that points one past
00726        *  the last element in the %list.  Iteration is done in ordinary
00727        *  element order.
00728        */
00729       const_iterator
00730       cend() const
00731       { return const_iterator(&this->_M_impl._M_node); }
00732 
00733       /**
00734        *  Returns a read-only (constant) reverse iterator that points to
00735        *  the last element in the %list.  Iteration is done in reverse
00736        *  element order.
00737        */
00738       const_reverse_iterator
00739       crbegin() const
00740       { return const_reverse_iterator(end()); }
00741 
00742       /**
00743        *  Returns a read-only (constant) reverse iterator that points to one
00744        *  before the first element in the %list.  Iteration is done in reverse
00745        *  element order.
00746        */
00747       const_reverse_iterator
00748       crend() const
00749       { return const_reverse_iterator(begin()); }
00750 #endif
00751 
00752       // [23.2.2.2] capacity
00753       /**
00754        *  Returns true if the %list is empty.  (Thus begin() would equal
00755        *  end().)
00756        */
00757       bool
00758       empty() const
00759       { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
00760 
00761       /**  Returns the number of elements in the %list.  */
00762       size_type
00763       size() const
00764       { return std::distance(begin(), end()); }
00765 
00766       /**  Returns the size() of the largest possible %list.  */
00767       size_type
00768       max_size() const
00769       { return _M_get_Tp_allocator().max_size(); }
00770 
00771       /**
00772        *  @brief Resizes the %list to the specified number of elements.
00773        *  @param new_size Number of elements the %list should contain.
00774        *  @param x Data with which new elements should be populated.
00775        *
00776        *  This function will %resize the %list to the specified number
00777        *  of elements.  If the number is smaller than the %list's
00778        *  current size the %list is truncated, otherwise the %list is
00779        *  extended and new elements are populated with given data.
00780        */
00781       void
00782       resize(size_type __new_size, value_type __x = value_type());
00783 
00784       // element access
00785       /**
00786        *  Returns a read/write reference to the data at the first
00787        *  element of the %list.
00788        */
00789       reference
00790       front()
00791       { return *begin(); }
00792 
00793       /**
00794        *  Returns a read-only (constant) reference to the data at the first
00795        *  element of the %list.
00796        */
00797       const_reference
00798       front() const
00799       { return *begin(); }
00800 
00801       /**
00802        *  Returns a read/write reference to the data at the last element
00803        *  of the %list.
00804        */
00805       reference
00806       back()
00807       { 
00808     iterator __tmp = end();
00809     --__tmp;
00810     return *__tmp;
00811       }
00812 
00813       /**
00814        *  Returns a read-only (constant) reference to the data at the last
00815        *  element of the %list.
00816        */
00817       const_reference
00818       back() const
00819       { 
00820     const_iterator __tmp = end();
00821     --__tmp;
00822     return *__tmp;
00823       }
00824 
00825       // [23.2.2.3] modifiers
00826       /**
00827        *  @brief  Add data to the front of the %list.
00828        *  @param  x  Data to be added.
00829        *
00830        *  This is a typical stack operation.  The function creates an
00831        *  element at the front of the %list and assigns the given data
00832        *  to it.  Due to the nature of a %list this operation can be
00833        *  done in constant time, and does not invalidate iterators and
00834        *  references.
00835        */
00836 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00837       void
00838       push_front(const value_type& __x)
00839       { this->_M_insert(begin(), __x); }
00840 #else
00841       template<typename... _Args>
00842         void
00843         push_front(_Args&&... __args)
00844     { this->_M_insert(begin(), std::forward<_Args>(__args)...); }
00845 #endif
00846 
00847       /**
00848        *  @brief  Removes first element.
00849        *
00850        *  This is a typical stack operation.  It shrinks the %list by
00851        *  one.  Due to the nature of a %list this operation can be done
00852        *  in constant time, and only invalidates iterators/references to
00853        *  the element being removed.
00854        *
00855        *  Note that no data is returned, and if the first element's data
00856        *  is needed, it should be retrieved before pop_front() is
00857        *  called.
00858        */
00859       void
00860       pop_front()
00861       { this->_M_erase(begin()); }
00862 
00863       /**
00864        *  @brief  Add data to the end of the %list.
00865        *  @param  x  Data to be added.
00866        *
00867        *  This is a typical stack operation.  The function creates an
00868        *  element at the end of the %list and assigns the given data to
00869        *  it.  Due to the nature of a %list this operation can be done
00870        *  in constant time, and does not invalidate iterators and
00871        *  references.
00872        */
00873 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00874       void
00875       push_back(const value_type& __x)
00876       { this->_M_insert(end(), __x); }
00877 #else
00878       template<typename... _Args>
00879         void
00880         push_back(_Args&&... __args)
00881     { this->_M_insert(end(), std::forward<_Args>(__args)...); }
00882 #endif
00883 
00884       /**
00885        *  @brief  Removes last element.
00886        *
00887        *  This is a typical stack operation.  It shrinks the %list by
00888        *  one.  Due to the nature of a %list this operation can be done
00889        *  in constant time, and only invalidates iterators/references to
00890        *  the element being removed.
00891        *
00892        *  Note that no data is returned, and if the last element's data
00893        *  is needed, it should be retrieved before pop_back() is called.
00894        */
00895       void
00896       pop_back()
00897       { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
00898 
00899 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00900       /**
00901        *  @brief  Constructs object in %list before specified iterator.
00902        *  @param  position  A const_iterator into the %list.
00903        *  @param  args  Arguments.
00904        *  @return  An iterator that points to the inserted data.
00905        *
00906        *  This function will insert an object of type T constructed
00907        *  with T(std::forward<Args>(args)...) before the specified
00908        *  location.  Due to the nature of a %list this operation can
00909        *  be done in constant time, and does not invalidate iterators
00910        *  and references.
00911        */
00912       template<typename... _Args>
00913         iterator
00914         emplace(iterator __position, _Args&&... __args);
00915 #endif
00916 
00917       /**
00918        *  @brief  Inserts given value into %list before specified iterator.
00919        *  @param  position  An iterator into the %list.
00920        *  @param  x  Data to be inserted.
00921        *  @return  An iterator that points to the inserted data.
00922        *
00923        *  This function will insert a copy of the given value before
00924        *  the specified location.  Due to the nature of a %list this
00925        *  operation can be done in constant time, and does not
00926        *  invalidate iterators and references.
00927        */
00928       iterator
00929       insert(iterator __position, const value_type& __x);
00930 
00931 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00932       /**
00933        *  @brief  Inserts given rvalue into %list before specified iterator.
00934        *  @param  position  An iterator into the %list.
00935        *  @param  x  Data to be inserted.
00936        *  @return  An iterator that points to the inserted data.
00937        *
00938        *  This function will insert a copy of the given rvalue before
00939        *  the specified location.  Due to the nature of a %list this
00940        *  operation can be done in constant time, and does not
00941        *  invalidate iterators and references.
00942         */
00943       iterator
00944       insert(iterator __position, value_type&& __x)
00945       { return emplace(__position, std::move(__x)); }
00946 #endif
00947 
00948       /**
00949        *  @brief  Inserts a number of copies of given data into the %list.
00950        *  @param  position  An iterator into the %list.
00951        *  @param  n  Number of elements to be inserted.
00952        *  @param  x  Data to be inserted.
00953        *
00954        *  This function will insert a specified number of copies of the
00955        *  given data before the location specified by @a position.
00956        *
00957        *  This operation is linear in the number of elements inserted and
00958        *  does not invalidate iterators and references.
00959        */
00960       void
00961       insert(iterator __position, size_type __n, const value_type& __x)
00962       {  
00963     list __tmp(__n, __x, _M_get_Node_allocator());
00964     splice(__position, __tmp);
00965       }
00966 
00967       /**
00968        *  @brief  Inserts a range into the %list.
00969        *  @param  position  An iterator into the %list.
00970        *  @param  first  An input iterator.
00971        *  @param  last   An input iterator.
00972        *
00973        *  This function will insert copies of the data in the range [@a
00974        *  first,@a last) into the %list before the location specified by
00975        *  @a position.
00976        *
00977        *  This operation is linear in the number of elements inserted and
00978        *  does not invalidate iterators and references.
00979        */
00980       template<typename _InputIterator>
00981         void
00982         insert(iterator __position, _InputIterator __first,
00983            _InputIterator __last)
00984         {
00985       list __tmp(__first, __last, _M_get_Node_allocator());
00986       splice(__position, __tmp);
00987     }
00988 
00989       /**
00990        *  @brief  Remove element at given position.
00991        *  @param  position  Iterator pointing to element to be erased.
00992        *  @return  An iterator pointing to the next element (or end()).
00993        *
00994        *  This function will erase the element at the given position and thus
00995        *  shorten the %list by one.
00996        *
00997        *  Due to the nature of a %list this operation can be done in
00998        *  constant time, and only invalidates iterators/references to
00999        *  the element being removed.  The user is also cautioned that
01000        *  this function only erases the element, and that if the element
01001        *  is itself a pointer, the pointed-to memory is not touched in
01002        *  any way.  Managing the pointer is the user's responsibility.
01003        */
01004       iterator
01005       erase(iterator __position);
01006 
01007       /**
01008        *  @brief  Remove a range of elements.
01009        *  @param  first  Iterator pointing to the first element to be erased.
01010        *  @param  last  Iterator pointing to one past the last element to be
01011        *                erased.
01012        *  @return  An iterator pointing to the element pointed to by @a last
01013        *           prior to erasing (or end()).
01014        *
01015        *  This function will erase the elements in the range @a
01016        *  [first,last) and shorten the %list accordingly.
01017        *
01018        *  This operation is linear time in the size of the range and only
01019        *  invalidates iterators/references to the element being removed.
01020        *  The user is also cautioned that this function only erases the
01021        *  elements, and that if the elements themselves are pointers, the
01022        *  pointed-to memory is not touched in any way.  Managing the pointer
01023        *  is the user's responsibility.
01024        */
01025       iterator
01026       erase(iterator __first, iterator __last)
01027       {
01028     while (__first != __last)
01029       __first = erase(__first);
01030     return __last;
01031       }
01032 
01033       /**
01034        *  @brief  Swaps data with another %list.
01035        *  @param  x  A %list of the same element and allocator types.
01036        *
01037        *  This exchanges the elements between two lists in constant
01038        *  time.  Note that the global std::swap() function is
01039        *  specialized such that std::swap(l1,l2) will feed to this
01040        *  function.
01041        */
01042       void
01043 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01044       swap(list&& __x)
01045 #else
01046       swap(list& __x)
01047 #endif
01048       {
01049     _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node);
01050 
01051     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01052     // 431. Swapping containers with unequal allocators.
01053     std::__alloc_swap<typename _Base::_Node_alloc_type>::
01054 	  _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator());
01055       }
01056 
01057       /**
01058        *  Erases all the elements.  Note that this function only erases
01059        *  the elements, and that if the elements themselves are
01060        *  pointers, the pointed-to memory is not touched in any way.
01061        *  Managing the pointer is the user's responsibility.
01062        */
01063       void
01064       clear()
01065       {
01066         _Base::_M_clear();
01067         _Base::_M_init();
01068       }
01069 
01070       // [23.2.2.4] list operations
01071       /**
01072        *  @brief  Insert contents of another %list.
01073        *  @param  position  Iterator referencing the element to insert before.
01074        *  @param  x  Source list.
01075        *
01076        *  The elements of @a x are inserted in constant time in front of
01077        *  the element referenced by @a position.  @a x becomes an empty
01078        *  list.
01079        *
01080        *  Requires this != @a x.
01081        */
01082       void
01083 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01084       splice(iterator __position, list&& __x)
01085 #else
01086       splice(iterator __position, list& __x)
01087 #endif
01088       {
01089     if (!__x.empty())
01090       {
01091         _M_check_equal_allocators(__x);
01092 
01093         this->_M_transfer(__position, __x.begin(), __x.end());
01094       }
01095       }
01096 
01097       /**
01098        *  @brief  Insert element from another %list.
01099        *  @param  position  Iterator referencing the element to insert before.
01100        *  @param  x  Source list.
01101        *  @param  i  Iterator referencing the element to move.
01102        *
01103        *  Removes the element in list @a x referenced by @a i and
01104        *  inserts it into the current list before @a position.
01105        */
01106       void
01107 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01108       splice(iterator __position, list&& __x, iterator __i)
01109 #else
01110       splice(iterator __position, list& __x, iterator __i)
01111 #endif
01112       {
01113     iterator __j = __i;
01114     ++__j;
01115     if (__position == __i || __position == __j)
01116       return;
01117 
01118     if (this != &__x)
01119       _M_check_equal_allocators(__x);
01120 
01121     this->_M_transfer(__position, __i, __j);
01122       }
01123 
01124       /**
01125        *  @brief  Insert range from another %list.
01126        *  @param  position  Iterator referencing the element to insert before.
01127        *  @param  x  Source list.
01128        *  @param  first  Iterator referencing the start of range in x.
01129        *  @param  last  Iterator referencing the end of range in x.
01130        *
01131        *  Removes elements in the range [first,last) and inserts them
01132        *  before @a position in constant time.
01133        *
01134        *  Undefined if @a position is in [first,last).
01135        */
01136       void
01137 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01138       splice(iterator __position, list&& __x, iterator __first,
01139          iterator __last)
01140 #else
01141       splice(iterator __position, list& __x, iterator __first,
01142          iterator __last)
01143 #endif
01144       {
01145     if (__first != __last)
01146       {
01147         if (this != &__x)
01148           _M_check_equal_allocators(__x);
01149 
01150         this->_M_transfer(__position, __first, __last);
01151       }
01152       }
01153 
01154       /**
01155        *  @brief  Remove all elements equal to value.
01156        *  @param  value  The value to remove.
01157        *
01158        *  Removes every element in the list equal to @a value.
01159        *  Remaining elements stay in list order.  Note that this
01160        *  function only erases the elements, and that if the elements
01161        *  themselves are pointers, the pointed-to memory is not
01162        *  touched in any way.  Managing the pointer is the user's
01163        *  responsibility.
01164        */
01165       void
01166       remove(const _Tp& __value);
01167 
01168       /**
01169        *  @brief  Remove all elements satisfying a predicate.
01170        *  @param  Predicate  Unary predicate function or object.
01171        *
01172        *  Removes every element in the list for which the predicate
01173        *  returns true.  Remaining elements stay in list order.  Note
01174        *  that this function only erases the elements, and that if the
01175        *  elements themselves are pointers, the pointed-to memory is
01176        *  not touched in any way.  Managing the pointer is the user's
01177        *  responsibility.
01178        */
01179       template<typename _Predicate>
01180         void
01181         remove_if(_Predicate);
01182 
01183       /**
01184        *  @brief  Remove consecutive duplicate elements.
01185        *
01186        *  For each consecutive set of elements with the same value,
01187        *  remove all but the first one.  Remaining elements stay in
01188        *  list order.  Note that this function only erases the
01189        *  elements, and that if the elements themselves are pointers,
01190        *  the pointed-to memory is not touched in any way.  Managing
01191        *  the pointer is the user's responsibility.
01192        */
01193       void
01194       unique();
01195 
01196       /**
01197        *  @brief  Remove consecutive elements satisfying a predicate.
01198        *  @param  BinaryPredicate  Binary predicate function or object.
01199        *
01200        *  For each consecutive set of elements [first,last) that
01201        *  satisfy predicate(first,i) where i is an iterator in
01202        *  [first,last), remove all but the first one.  Remaining
01203        *  elements stay in list order.  Note that this function only
01204        *  erases the elements, and that if the elements themselves are
01205        *  pointers, the pointed-to memory is not touched in any way.
01206        *  Managing the pointer is the user's responsibility.
01207        */
01208       template<typename _BinaryPredicate>
01209         void
01210         unique(_BinaryPredicate);
01211 
01212       /**
01213        *  @brief  Merge sorted lists.
01214        *  @param  x  Sorted list to merge.
01215        *
01216        *  Assumes that both @a x and this list are sorted according to
01217        *  operator<().  Merges elements of @a x into this list in
01218        *  sorted order, leaving @a x empty when complete.  Elements in
01219        *  this list precede elements in @a x that are equal.
01220        */
01221       void
01222 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01223       merge(list&& __x);
01224 #else
01225       merge(list& __x);
01226 #endif
01227 
01228       /**
01229        *  @brief  Merge sorted lists according to comparison function.
01230        *  @param  x  Sorted list to merge.
01231        *  @param StrictWeakOrdering Comparison function defining
01232        *  sort order.
01233        *
01234        *  Assumes that both @a x and this list are sorted according to
01235        *  StrictWeakOrdering.  Merges elements of @a x into this list
01236        *  in sorted order, leaving @a x empty when complete.  Elements
01237        *  in this list precede elements in @a x that are equivalent
01238        *  according to StrictWeakOrdering().
01239        */
01240       template<typename _StrictWeakOrdering>
01241         void
01242 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01243         merge(list&&, _StrictWeakOrdering);
01244 #else
01245         merge(list&, _StrictWeakOrdering);
01246 #endif
01247 
01248       /**
01249        *  @brief  Reverse the elements in list.
01250        *
01251        *  Reverse the order of elements in the list in linear time.
01252        */
01253       void
01254       reverse()
01255       { this->_M_impl._M_node.reverse(); }
01256 
01257       /**
01258        *  @brief  Sort the elements.
01259        *
01260        *  Sorts the elements of this list in NlogN time.  Equivalent
01261        *  elements remain in list order.
01262        */
01263       void
01264       sort();
01265 
01266       /**
01267        *  @brief  Sort the elements according to comparison function.
01268        *
01269        *  Sorts the elements of this list in NlogN time.  Equivalent
01270        *  elements remain in list order.
01271        */
01272       template<typename _StrictWeakOrdering>
01273         void
01274         sort(_StrictWeakOrdering);
01275 
01276     protected:
01277       // Internal constructor functions follow.
01278 
01279       // Called by the range constructor to implement [23.1.1]/9
01280 
01281       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01282       // 438. Ambiguity in the "do the right thing" clause
01283       template<typename _Integer>
01284         void
01285         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01286         { _M_fill_initialize(static_cast<size_type>(__n), __x); }
01287 
01288       // Called by the range constructor to implement [23.1.1]/9
01289       template<typename _InputIterator>
01290         void
01291         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01292                    __false_type)
01293         {
01294       for (; __first != __last; ++__first)
01295         push_back(*__first);
01296     }
01297 
01298       // Called by list(n,v,a), and the range constructor when it turns out
01299       // to be the same thing.
01300       void
01301       _M_fill_initialize(size_type __n, const value_type& __x)
01302       {
01303     for (; __n > 0; --__n)
01304       push_back(__x);
01305       }
01306 
01307 
01308       // Internal assign functions follow.
01309 
01310       // Called by the range assign to implement [23.1.1]/9
01311 
01312       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01313       // 438. Ambiguity in the "do the right thing" clause
01314       template<typename _Integer>
01315         void
01316         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01317         { _M_fill_assign(__n, __val); }
01318 
01319       // Called by the range assign to implement [23.1.1]/9
01320       template<typename _InputIterator>
01321         void
01322         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01323                __false_type);
01324 
01325       // Called by assign(n,t), and the range assign when it turns out
01326       // to be the same thing.
01327       void
01328       _M_fill_assign(size_type __n, const value_type& __val);
01329 
01330 
01331       // Moves the elements from [first,last) before position.
01332       void
01333       _M_transfer(iterator __position, iterator __first, iterator __last)
01334       { __position._M_node->transfer(__first._M_node, __last._M_node); }
01335 
01336       // Inserts new element at position given and with value given.
01337 #ifndef __GXX_EXPERIMENTAL_CXX0X__
01338       void
01339       _M_insert(iterator __position, const value_type& __x)
01340       {
01341         _Node* __tmp = _M_create_node(__x);
01342         __tmp->hook(__position._M_node);
01343       }
01344 #else
01345      template<typename... _Args>
01346        void
01347        _M_insert(iterator __position, _Args&&... __args)
01348        {
01349      _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
01350      __tmp->hook(__position._M_node);
01351        }
01352 #endif
01353 
01354       // Erases element at position given.
01355       void
01356       _M_erase(iterator __position)
01357       {
01358         __position._M_node->unhook();
01359         _Node* __n = static_cast<_Node*>(__position._M_node);
01360         _M_get_Tp_allocator().destroy(&__n->_M_data);
01361         _M_put_node(__n);
01362       }
01363 
01364       // To implement the splice (and merge) bits of N1599.
01365       void
01366       _M_check_equal_allocators(list& __x)
01367       {
01368     if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
01369         _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
01370       __throw_runtime_error(__N("list::_M_check_equal_allocators"));
01371       }
01372     };
01373 
01374   /**
01375    *  @brief  List equality comparison.
01376    *  @param  x  A %list.
01377    *  @param  y  A %list of the same type as @a x.
01378    *  @return  True iff the size and elements of the lists are equal.
01379    *
01380    *  This is an equivalence relation.  It is linear in the size of
01381    *  the lists.  Lists are considered equivalent if their sizes are
01382    *  equal, and if corresponding elements compare equal.
01383   */
01384   template<typename _Tp, typename _Alloc>
01385     inline bool
01386     operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01387     {
01388       typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
01389       const_iterator __end1 = __x.end();
01390       const_iterator __end2 = __y.end();
01391 
01392       const_iterator __i1 = __x.begin();
01393       const_iterator __i2 = __y.begin();
01394       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
01395     {
01396       ++__i1;
01397       ++__i2;
01398     }
01399       return __i1 == __end1 && __i2 == __end2;
01400     }
01401 
01402   /**
01403    *  @brief  List ordering relation.
01404    *  @param  x  A %list.
01405    *  @param  y  A %list of the same type as @a x.
01406    *  @return  True iff @a x is lexicographically less than @a y.
01407    *
01408    *  This is a total ordering relation.  It is linear in the size of the
01409    *  lists.  The elements must be comparable with @c <.
01410    *
01411    *  See std::lexicographical_compare() for how the determination is made.
01412   */
01413   template<typename _Tp, typename _Alloc>
01414     inline bool
01415     operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01416     { return std::lexicographical_compare(__x.begin(), __x.end(),
01417                       __y.begin(), __y.end()); }
01418 
01419   /// Based on operator==
01420   template<typename _Tp, typename _Alloc>
01421     inline bool
01422     operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01423     { return !(__x == __y); }
01424 
01425   /// Based on operator<
01426   template<typename _Tp, typename _Alloc>
01427     inline bool
01428     operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01429     { return __y < __x; }
01430 
01431   /// Based on operator<
01432   template<typename _Tp, typename _Alloc>
01433     inline bool
01434     operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01435     { return !(__y < __x); }
01436 
01437   /// Based on operator<
01438   template<typename _Tp, typename _Alloc>
01439     inline bool
01440     operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01441     { return !(__x < __y); }
01442 
01443   /// See std::list::swap().
01444   template<typename _Tp, typename _Alloc>
01445     inline void
01446     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
01447     { __x.swap(__y); }
01448 
01449 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01450   template<typename _Tp, typename _Alloc>
01451     inline void
01452     swap(list<_Tp, _Alloc>&& __x, list<_Tp, _Alloc>& __y)
01453     { __x.swap(__y); }
01454 
01455   template<typename _Tp, typename _Alloc>
01456     inline void
01457     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>&& __y)
01458     { __x.swap(__y); }
01459 #endif
01460 
01461 _GLIBCXX_END_NESTED_NAMESPACE
01462 
01463 #endif /* _STL_LIST_H */

Generated on Wed Mar 26 00:43:14 2008 for libstdc++ by  doxygen 1.5.1