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