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