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