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