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

Generated on Thu Jul 23 21:16:21 2009 for libstdc++ by  doxygen 1.5.8