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