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