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