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