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