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