libstdc++
forward_list.h
Go to the documentation of this file.
00001 // <forward_list.h> -*- C++ -*-
00002 
00003 // Copyright (C) 2008-2013 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 /** @file bits/forward_list.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{forward_list}
00028  */
00029 
00030 #ifndef _FORWARD_LIST_H
00031 #define _FORWARD_LIST_H 1
00032 
00033 #pragma GCC system_header
00034 
00035 #include <memory>
00036 #if __cplusplus >= 201103L
00037 #include <initializer_list>
00038 #endif
00039 
00040 namespace std _GLIBCXX_VISIBILITY(default)
00041 {
00042 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00043 
00044   /**
00045    *  @brief  A helper basic node class for %forward_list.
00046    *          This is just a linked list with nothing inside it.
00047    *          There are purely list shuffling utility methods here.
00048    */
00049   struct _Fwd_list_node_base
00050   {
00051     _Fwd_list_node_base() = default;
00052 
00053     _Fwd_list_node_base* _M_next = nullptr;
00054 
00055     _Fwd_list_node_base*
00056     _M_transfer_after(_Fwd_list_node_base* __begin,
00057               _Fwd_list_node_base* __end)
00058     {
00059       _Fwd_list_node_base* __keep = __begin->_M_next;
00060       if (__end)
00061     {
00062       __begin->_M_next = __end->_M_next;
00063       __end->_M_next = _M_next;
00064     }
00065       else
00066     __begin->_M_next = 0;
00067       _M_next = __keep;
00068       return __end;
00069     }
00070 
00071     void
00072     _M_reverse_after() noexcept
00073     {
00074       _Fwd_list_node_base* __tail = _M_next;
00075       if (!__tail)
00076     return;
00077       while (_Fwd_list_node_base* __temp = __tail->_M_next)
00078     {
00079       _Fwd_list_node_base* __keep = _M_next;
00080       _M_next = __temp;
00081       __tail->_M_next = __temp->_M_next;
00082       _M_next->_M_next = __keep;
00083     }
00084     }
00085   };
00086 
00087   /**
00088    *  @brief  A helper node class for %forward_list.
00089    *          This is just a linked list with uninitialized storage for a
00090    *          data value in each node.
00091    *          There is a sorting utility method.
00092    */
00093   template<typename _Tp>
00094     struct _Fwd_list_node
00095     : public _Fwd_list_node_base
00096     {
00097       _Fwd_list_node() = default;
00098 
00099       typename aligned_storage<sizeof(_Tp), alignment_of<_Tp>::value>::type
00100     _M_storage;
00101 
00102       _Tp*
00103       _M_valptr() noexcept
00104       {
00105     return static_cast<_Tp*>(static_cast<void*>(&_M_storage));
00106       }
00107 
00108       const _Tp*
00109       _M_valptr() const noexcept
00110       {
00111     return static_cast<const _Tp*>(static_cast<const void*>(&_M_storage));
00112       }
00113     };
00114 
00115   /**
00116    *   @brief A forward_list::iterator.
00117    * 
00118    *   All the functions are op overloads.
00119    */
00120   template<typename _Tp>
00121     struct _Fwd_list_iterator
00122     {
00123       typedef _Fwd_list_iterator<_Tp>            _Self;
00124       typedef _Fwd_list_node<_Tp>                _Node;
00125 
00126       typedef _Tp                                value_type;
00127       typedef _Tp*                               pointer;
00128       typedef _Tp&                               reference;
00129       typedef ptrdiff_t                          difference_type;
00130       typedef std::forward_iterator_tag          iterator_category;
00131 
00132       _Fwd_list_iterator()
00133       : _M_node() { }
00134 
00135       explicit
00136       _Fwd_list_iterator(_Fwd_list_node_base* __n) 
00137       : _M_node(__n) { }
00138 
00139       reference
00140       operator*() const
00141       { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
00142 
00143       pointer
00144       operator->() const
00145       { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
00146 
00147       _Self&
00148       operator++()
00149       {
00150         _M_node = _M_node->_M_next;
00151         return *this;
00152       }
00153 
00154       _Self
00155       operator++(int)
00156       {
00157         _Self __tmp(*this);
00158         _M_node = _M_node->_M_next;
00159         return __tmp;
00160       }
00161 
00162       bool
00163       operator==(const _Self& __x) const
00164       { return _M_node == __x._M_node; }
00165 
00166       bool
00167       operator!=(const _Self& __x) const
00168       { return _M_node != __x._M_node; }
00169 
00170       _Self
00171       _M_next() const
00172       {
00173         if (_M_node)
00174           return _Fwd_list_iterator(_M_node->_M_next);
00175         else
00176           return _Fwd_list_iterator(0);
00177       }
00178 
00179       _Fwd_list_node_base* _M_node;
00180     };
00181 
00182   /**
00183    *   @brief A forward_list::const_iterator.
00184    * 
00185    *   All the functions are op overloads.
00186    */
00187   template<typename _Tp>
00188     struct _Fwd_list_const_iterator
00189     {
00190       typedef _Fwd_list_const_iterator<_Tp>      _Self;
00191       typedef const _Fwd_list_node<_Tp>          _Node;
00192       typedef _Fwd_list_iterator<_Tp>            iterator;
00193 
00194       typedef _Tp                                value_type;
00195       typedef const _Tp*                         pointer;
00196       typedef const _Tp&                         reference;
00197       typedef ptrdiff_t                          difference_type;
00198       typedef std::forward_iterator_tag          iterator_category;
00199 
00200       _Fwd_list_const_iterator()
00201       : _M_node() { }
00202 
00203       explicit
00204       _Fwd_list_const_iterator(const _Fwd_list_node_base* __n) 
00205       : _M_node(__n) { }
00206 
00207       _Fwd_list_const_iterator(const iterator& __iter)
00208       : _M_node(__iter._M_node) { }
00209 
00210       reference
00211       operator*() const
00212       { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
00213 
00214       pointer
00215       operator->() const
00216       { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
00217 
00218       _Self&
00219       operator++()
00220       {
00221         _M_node = _M_node->_M_next;
00222         return *this;
00223       }
00224 
00225       _Self
00226       operator++(int)
00227       {
00228         _Self __tmp(*this);
00229         _M_node = _M_node->_M_next;
00230         return __tmp;
00231       }
00232 
00233       bool
00234       operator==(const _Self& __x) const
00235       { return _M_node == __x._M_node; }
00236 
00237       bool
00238       operator!=(const _Self& __x) const
00239       { return _M_node != __x._M_node; }
00240 
00241       _Self
00242       _M_next() const
00243       {
00244         if (this->_M_node)
00245           return _Fwd_list_const_iterator(_M_node->_M_next);
00246         else
00247           return _Fwd_list_const_iterator(0);
00248       }
00249 
00250       const _Fwd_list_node_base* _M_node;
00251     };
00252 
00253   /**
00254    *  @brief  Forward list iterator equality comparison.
00255    */
00256   template<typename _Tp>
00257     inline bool
00258     operator==(const _Fwd_list_iterator<_Tp>& __x,
00259                const _Fwd_list_const_iterator<_Tp>& __y)
00260     { return __x._M_node == __y._M_node; }
00261 
00262   /**
00263    *  @brief  Forward list iterator inequality comparison.
00264    */
00265   template<typename _Tp>
00266     inline bool
00267     operator!=(const _Fwd_list_iterator<_Tp>& __x,
00268                const _Fwd_list_const_iterator<_Tp>& __y)
00269     { return __x._M_node != __y._M_node; }
00270 
00271   /**
00272    *  @brief  Base class for %forward_list.
00273    */
00274   template<typename _Tp, typename _Alloc>
00275     struct _Fwd_list_base
00276     {
00277     protected:
00278       typedef typename __gnu_cxx::__alloc_traits<_Alloc> _Alloc_traits;
00279       typedef typename _Alloc_traits::template rebind<_Tp>::other
00280         _Tp_alloc_type;
00281 
00282       typedef typename _Alloc_traits::template
00283         rebind<_Fwd_list_node<_Tp>>::other _Node_alloc_type;
00284 
00285       typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
00286 
00287       struct _Fwd_list_impl 
00288       : public _Node_alloc_type
00289       {
00290         _Fwd_list_node_base _M_head;
00291 
00292         _Fwd_list_impl()
00293         : _Node_alloc_type(), _M_head()
00294         { }
00295 
00296         _Fwd_list_impl(const _Node_alloc_type& __a)
00297         : _Node_alloc_type(__a), _M_head()
00298         { }
00299 
00300         _Fwd_list_impl(_Node_alloc_type&& __a)
00301     : _Node_alloc_type(std::move(__a)), _M_head()
00302         { }
00303       };
00304 
00305       _Fwd_list_impl _M_impl;
00306 
00307     public:
00308       typedef _Fwd_list_iterator<_Tp>                 iterator;
00309       typedef _Fwd_list_const_iterator<_Tp>           const_iterator;
00310       typedef _Fwd_list_node<_Tp>                     _Node;
00311 
00312       _Node_alloc_type&
00313       _M_get_Node_allocator() noexcept
00314       { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
00315 
00316       const _Node_alloc_type&
00317       _M_get_Node_allocator() const noexcept
00318       { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
00319 
00320       _Fwd_list_base()
00321       : _M_impl() { }
00322 
00323       _Fwd_list_base(const _Node_alloc_type& __a)
00324       : _M_impl(__a) { }
00325 
00326       _Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a);
00327 
00328       _Fwd_list_base(_Fwd_list_base&& __lst)
00329       : _M_impl(std::move(__lst._M_get_Node_allocator()))
00330       {
00331     this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
00332     __lst._M_impl._M_head._M_next = 0;
00333       }
00334 
00335       ~_Fwd_list_base()
00336       { _M_erase_after(&_M_impl._M_head, 0); }
00337 
00338     protected:
00339 
00340       _Node*
00341       _M_get_node()
00342       { return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); }
00343 
00344       template<typename... _Args>
00345         _Node*
00346         _M_create_node(_Args&&... __args)
00347         {
00348           _Node* __node = this->_M_get_node();
00349           __try
00350             {
00351           _Tp_alloc_type __a(_M_get_Node_allocator());
00352           typedef allocator_traits<_Tp_alloc_type> _Alloc_traits;
00353           ::new ((void*)__node) _Node();
00354           _Alloc_traits::construct(__a, __node->_M_valptr(),
00355                        std::forward<_Args>(__args)...);
00356             }
00357           __catch(...)
00358             {
00359               this->_M_put_node(__node);
00360               __throw_exception_again;
00361             }
00362           return __node;
00363         }
00364 
00365       template<typename... _Args>
00366         _Fwd_list_node_base*
00367         _M_insert_after(const_iterator __pos, _Args&&... __args);
00368 
00369       void
00370       _M_put_node(_Node* __p)
00371       { _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
00372 
00373       _Fwd_list_node_base*
00374       _M_erase_after(_Fwd_list_node_base* __pos);
00375 
00376       _Fwd_list_node_base*
00377       _M_erase_after(_Fwd_list_node_base* __pos, 
00378                      _Fwd_list_node_base* __last);
00379     };
00380 
00381   /**
00382    *  @brief A standard container with linear time access to elements,
00383    *  and fixed time insertion/deletion at any point in the sequence.
00384    *
00385    *  @ingroup sequences
00386    *
00387    *  @tparam _Tp  Type of element.
00388    *  @tparam _Alloc  Allocator type, defaults to allocator<_Tp>.
00389    *
00390    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00391    *  <a href="tables.html#67">sequence</a>, including the
00392    *  <a href="tables.html#68">optional sequence requirements</a> with the
00393    *  %exception of @c at and @c operator[].
00394    *
00395    *  This is a @e singly @e linked %list.  Traversal up the
00396    *  %list requires linear time, but adding and removing elements (or
00397    *  @e nodes) is done in constant time, regardless of where the
00398    *  change takes place.  Unlike std::vector and std::deque,
00399    *  random-access iterators are not provided, so subscripting ( @c
00400    *  [] ) access is not allowed.  For algorithms which only need
00401    *  sequential access, this lack makes no difference.
00402    *
00403    *  Also unlike the other standard containers, std::forward_list provides
00404    *  specialized algorithms %unique to linked lists, such as
00405    *  splicing, sorting, and in-place reversal.
00406    */
00407   template<typename _Tp, typename _Alloc = allocator<_Tp> >
00408     class forward_list : private _Fwd_list_base<_Tp, _Alloc>
00409     {
00410     private:
00411       typedef _Fwd_list_base<_Tp, _Alloc>                  _Base;
00412       typedef _Fwd_list_node<_Tp>                          _Node;
00413       typedef _Fwd_list_node_base                          _Node_base;
00414       typedef typename _Base::_Tp_alloc_type               _Tp_alloc_type;
00415       typedef typename _Base::_Node_alloc_type             _Node_alloc_type;
00416       typedef typename _Base::_Node_alloc_traits           _Node_alloc_traits;
00417       typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>    _Alloc_traits;
00418 
00419     public:
00420       // types:
00421       typedef _Tp                                          value_type;
00422       typedef typename _Alloc_traits::pointer              pointer;
00423       typedef typename _Alloc_traits::const_pointer        const_pointer;
00424       typedef typename _Alloc_traits::reference            reference;
00425       typedef typename _Alloc_traits::const_reference      const_reference;
00426  
00427       typedef _Fwd_list_iterator<_Tp>                      iterator;
00428       typedef _Fwd_list_const_iterator<_Tp>                const_iterator;
00429       typedef std::size_t                                  size_type;
00430       typedef std::ptrdiff_t                               difference_type;
00431       typedef _Alloc                                       allocator_type;
00432 
00433       // 23.3.4.2 construct/copy/destroy:
00434 
00435       /**
00436        *  @brief  Creates a %forward_list with no elements.
00437        *  @param  __al  An allocator object.
00438        */
00439       explicit
00440       forward_list(const _Alloc& __al = _Alloc())
00441       : _Base(_Node_alloc_type(__al))
00442       { }
00443 
00444       /**
00445        *  @brief  Copy constructor with allocator argument.
00446        *  @param  __list  Input list to copy.
00447        *  @param  __al    An allocator object.
00448        */
00449       forward_list(const forward_list& __list, const _Alloc& __al)
00450       : _Base(_Node_alloc_type(__al))
00451       { _M_range_initialize(__list.begin(), __list.end()); }
00452 
00453       /**
00454        *  @brief  Move constructor with allocator argument.
00455        *  @param  __list  Input list to move.
00456        *  @param  __al    An allocator object.
00457        */
00458       forward_list(forward_list&& __list, const _Alloc& __al)
00459       noexcept(_Node_alloc_traits::_S_always_equal())
00460       : _Base(std::move(__list), _Node_alloc_type(__al))
00461       { }
00462 
00463       /**
00464        *  @brief  Creates a %forward_list with default constructed elements.
00465        *  @param  __n  The number of elements to initially create.
00466        *
00467        *  This constructor creates the %forward_list with @a __n default
00468        *  constructed elements.
00469        */
00470       explicit
00471       forward_list(size_type __n, const _Alloc& __al = _Alloc())
00472       : _Base(_Node_alloc_type(__al))
00473       { _M_default_initialize(__n); }
00474 
00475       /**
00476        *  @brief  Creates a %forward_list with copies of an exemplar element.
00477        *  @param  __n      The number of elements to initially create.
00478        *  @param  __value  An element to copy.
00479        *  @param  __al     An allocator object.
00480        *
00481        *  This constructor fills the %forward_list with @a __n copies of
00482        *  @a __value.
00483        */
00484       forward_list(size_type __n, const _Tp& __value,
00485                    const _Alloc& __al = _Alloc())
00486       : _Base(_Node_alloc_type(__al))
00487       { _M_fill_initialize(__n, __value); }
00488 
00489       /**
00490        *  @brief  Builds a %forward_list from a range.
00491        *  @param  __first  An input iterator.
00492        *  @param  __last   An input iterator.
00493        *  @param  __al     An allocator object.
00494        *
00495        *  Create a %forward_list consisting of copies of the elements from
00496        *  [@a __first,@a __last).  This is linear in N (where N is
00497        *  distance(@a __first,@a __last)).
00498        */
00499       template<typename _InputIterator,
00500            typename = std::_RequireInputIter<_InputIterator>>
00501         forward_list(_InputIterator __first, _InputIterator __last,
00502                      const _Alloc& __al = _Alloc())
00503     : _Base(_Node_alloc_type(__al))
00504         { _M_range_initialize(__first, __last); }
00505 
00506       /**
00507        *  @brief  The %forward_list copy constructor.
00508        *  @param  __list  A %forward_list of identical element and allocator
00509        *                  types.
00510        */
00511       forward_list(const forward_list& __list)
00512       : _Base(_Node_alloc_traits::_S_select_on_copy(
00513                 __list._M_get_Node_allocator()))
00514       { _M_range_initialize(__list.begin(), __list.end()); }
00515 
00516       /**
00517        *  @brief  The %forward_list move constructor.
00518        *  @param  __list  A %forward_list of identical element and allocator
00519        *                  types.
00520        *
00521        *  The newly-created %forward_list contains the exact contents of @a
00522        *  __list. The contents of @a __list are a valid, but unspecified
00523        *  %forward_list.
00524        */
00525       forward_list(forward_list&& __list) noexcept
00526       : _Base(std::move(__list)) { }
00527 
00528       /**
00529        *  @brief  Builds a %forward_list from an initializer_list
00530        *  @param  __il  An initializer_list of value_type.
00531        *  @param  __al  An allocator object.
00532        *
00533        *  Create a %forward_list consisting of copies of the elements
00534        *  in the initializer_list @a __il.  This is linear in __il.size().
00535        */
00536       forward_list(std::initializer_list<_Tp> __il,
00537                    const _Alloc& __al = _Alloc())
00538       : _Base(_Node_alloc_type(__al))
00539       { _M_range_initialize(__il.begin(), __il.end()); }
00540 
00541       /**
00542        *  @brief  The forward_list dtor.
00543        */
00544       ~forward_list() noexcept
00545       { }
00546 
00547       /**
00548        *  @brief  The %forward_list assignment operator.
00549        *  @param  __list  A %forward_list of identical element and allocator
00550        *                types.
00551        *
00552        *  All the elements of @a __list are copied, but unlike the copy
00553        *  constructor, the allocator object is not copied.
00554        */
00555       forward_list&
00556       operator=(const forward_list& __list);
00557 
00558       /**
00559        *  @brief  The %forward_list move assignment operator.
00560        *  @param  __list  A %forward_list of identical element and allocator
00561        *                types.
00562        *
00563        *  The contents of @a __list are moved into this %forward_list
00564        *  (without copying, if the allocators permit it).
00565        *  @a __list is a valid, but unspecified %forward_list
00566        */
00567       forward_list&
00568       operator=(forward_list&& __list)
00569       noexcept(_Node_alloc_traits::_S_nothrow_move())
00570       {
00571         constexpr bool __move_storage =
00572           _Node_alloc_traits::_S_propagate_on_move_assign()
00573           || _Node_alloc_traits::_S_always_equal();
00574         _M_move_assign(std::move(__list),
00575                        integral_constant<bool, __move_storage>());
00576     return *this;
00577       }
00578 
00579       /**
00580        *  @brief  The %forward_list initializer list assignment operator.
00581        *  @param  __il  An initializer_list of value_type.
00582        *
00583        *  Replace the contents of the %forward_list with copies of the
00584        *  elements in the initializer_list @a __il.  This is linear in
00585        *  __il.size().
00586        */
00587       forward_list&
00588       operator=(std::initializer_list<_Tp> __il)
00589       {
00590         assign(__il);
00591         return *this;
00592       }
00593 
00594       /**
00595        *  @brief  Assigns a range to a %forward_list.
00596        *  @param  __first  An input iterator.
00597        *  @param  __last   An input iterator.
00598        *
00599        *  This function fills a %forward_list with copies of the elements
00600        *  in the range [@a __first,@a __last).
00601        *
00602        *  Note that the assignment completely changes the %forward_list and
00603        *  that the number of elements of the resulting %forward_list is the
00604        *  same as the number of elements assigned.  Old data is lost.
00605        */
00606       template<typename _InputIterator,
00607            typename = std::_RequireInputIter<_InputIterator>>
00608     void
00609         assign(_InputIterator __first, _InputIterator __last)
00610         {
00611       typedef is_assignable<_Tp, decltype(*__first)> __assignable;
00612       _M_assign(__first, __last, __assignable());
00613     }
00614 
00615       /**
00616        *  @brief  Assigns a given value to a %forward_list.
00617        *  @param  __n  Number of elements to be assigned.
00618        *  @param  __val  Value to be assigned.
00619        *
00620        *  This function fills a %forward_list with @a __n copies of the
00621        *  given value.  Note that the assignment completely changes the
00622        *  %forward_list, and that the resulting %forward_list has __n
00623        *  elements.  Old data is lost.
00624        */
00625       void
00626       assign(size_type __n, const _Tp& __val)
00627       { _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); }
00628 
00629       /**
00630        *  @brief  Assigns an initializer_list to a %forward_list.
00631        *  @param  __il  An initializer_list of value_type.
00632        *
00633        *  Replace the contents of the %forward_list with copies of the
00634        *  elements in the initializer_list @a __il.  This is linear in
00635        *  il.size().
00636        */
00637       void
00638       assign(std::initializer_list<_Tp> __il)
00639       { assign(__il.begin(), __il.end()); }
00640 
00641       /// Get a copy of the memory allocation object.
00642       allocator_type
00643       get_allocator() const noexcept
00644       { return allocator_type(this->_M_get_Node_allocator()); }
00645 
00646       // 23.3.4.3 iterators:
00647 
00648       /**
00649        *  Returns a read/write iterator that points before the first element
00650        *  in the %forward_list.  Iteration is done in ordinary element order.
00651        */
00652       iterator
00653       before_begin() noexcept
00654       { return iterator(&this->_M_impl._M_head); }
00655 
00656       /**
00657        *  Returns a read-only (constant) iterator that points before the
00658        *  first element in the %forward_list.  Iteration is done in ordinary
00659        *  element order.
00660        */
00661       const_iterator
00662       before_begin() const noexcept
00663       { return const_iterator(&this->_M_impl._M_head); }
00664 
00665       /**
00666        *  Returns a read/write iterator that points to the first element
00667        *  in the %forward_list.  Iteration is done in ordinary element order.
00668        */
00669       iterator
00670       begin() noexcept
00671       { return iterator(this->_M_impl._M_head._M_next); }
00672 
00673       /**
00674        *  Returns a read-only (constant) iterator that points to the first
00675        *  element in the %forward_list.  Iteration is done in ordinary
00676        *  element order.
00677        */
00678       const_iterator
00679       begin() const noexcept
00680       { return const_iterator(this->_M_impl._M_head._M_next); }
00681 
00682       /**
00683        *  Returns a read/write iterator that points one past the last
00684        *  element in the %forward_list.  Iteration is done in ordinary
00685        *  element order.
00686        */
00687       iterator
00688       end() noexcept
00689       { return iterator(0); }
00690 
00691       /**
00692        *  Returns a read-only iterator that points one past the last
00693        *  element in the %forward_list.  Iteration is done in ordinary
00694        *  element order.
00695        */
00696       const_iterator
00697       end() const noexcept
00698       { return const_iterator(0); }
00699 
00700       /**
00701        *  Returns a read-only (constant) iterator that points to the
00702        *  first element in the %forward_list.  Iteration is done in ordinary
00703        *  element order.
00704        */
00705       const_iterator
00706       cbegin() const noexcept
00707       { return const_iterator(this->_M_impl._M_head._M_next); }
00708 
00709       /**
00710        *  Returns a read-only (constant) iterator that points before the
00711        *  first element in the %forward_list.  Iteration is done in ordinary
00712        *  element order.
00713        */
00714       const_iterator
00715       cbefore_begin() const noexcept
00716       { return const_iterator(&this->_M_impl._M_head); }
00717 
00718       /**
00719        *  Returns a read-only (constant) iterator that points one past
00720        *  the last element in the %forward_list.  Iteration is done in
00721        *  ordinary element order.
00722        */
00723       const_iterator
00724       cend() const noexcept
00725       { return const_iterator(0); }
00726 
00727       /**
00728        *  Returns true if the %forward_list is empty.  (Thus begin() would
00729        *  equal end().)
00730        */
00731       bool
00732       empty() const noexcept
00733       { return this->_M_impl._M_head._M_next == 0; }
00734 
00735       /**
00736        *  Returns the largest possible number of elements of %forward_list.
00737        */
00738       size_type
00739       max_size() const noexcept
00740       { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); }
00741 
00742       // 23.3.4.4 element access:
00743 
00744       /**
00745        *  Returns a read/write reference to the data at the first
00746        *  element of the %forward_list.
00747        */
00748       reference
00749       front()
00750       {
00751         _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
00752         return *__front->_M_valptr();
00753       }
00754 
00755       /**
00756        *  Returns a read-only (constant) reference to the data at the first
00757        *  element of the %forward_list.
00758        */
00759       const_reference
00760       front() const
00761       {
00762         _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
00763         return *__front->_M_valptr();
00764       }
00765 
00766       // 23.3.4.5 modifiers:
00767 
00768       /**
00769        *  @brief  Constructs object in %forward_list at the front of the
00770        *          list.
00771        *  @param  __args  Arguments.
00772        *
00773        *  This function will insert an object of type Tp constructed
00774        *  with Tp(std::forward<Args>(args)...) at the front of the list
00775        *  Due to the nature of a %forward_list this operation can
00776        *  be done in constant time, and does not invalidate iterators
00777        *  and references.
00778        */
00779       template<typename... _Args>
00780         void
00781         emplace_front(_Args&&... __args)
00782         { this->_M_insert_after(cbefore_begin(),
00783                                 std::forward<_Args>(__args)...); }
00784 
00785       /**
00786        *  @brief  Add data to the front of the %forward_list.
00787        *  @param  __val  Data to be added.
00788        *
00789        *  This is a typical stack operation.  The function creates an
00790        *  element at the front of the %forward_list and assigns the given
00791        *  data to it.  Due to the nature of a %forward_list this operation
00792        *  can be done in constant time, and does not invalidate iterators
00793        *  and references.
00794        */
00795       void
00796       push_front(const _Tp& __val)
00797       { this->_M_insert_after(cbefore_begin(), __val); }
00798 
00799       /**
00800        *
00801        */
00802       void
00803       push_front(_Tp&& __val)
00804       { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
00805 
00806       /**
00807        *  @brief  Removes first element.
00808        *
00809        *  This is a typical stack operation.  It shrinks the %forward_list
00810        *  by one.  Due to the nature of a %forward_list this operation can
00811        *  be done in constant time, and only invalidates iterators/references
00812        *  to the element being removed.
00813        *
00814        *  Note that no data is returned, and if the first element's data
00815        *  is needed, it should be retrieved before pop_front() is
00816        *  called.
00817        */
00818       void
00819       pop_front()
00820       { this->_M_erase_after(&this->_M_impl._M_head); }
00821 
00822       /**
00823        *  @brief  Constructs object in %forward_list after the specified
00824        *          iterator.
00825        *  @param  __pos  A const_iterator into the %forward_list.
00826        *  @param  __args  Arguments.
00827        *  @return  An iterator that points to the inserted data.
00828        *
00829        *  This function will insert an object of type T constructed
00830        *  with T(std::forward<Args>(args)...) after the specified
00831        *  location.  Due to the nature of a %forward_list this operation can
00832        *  be done in constant time, and does not invalidate iterators
00833        *  and references.
00834        */
00835       template<typename... _Args>
00836         iterator
00837         emplace_after(const_iterator __pos, _Args&&... __args)
00838         { return iterator(this->_M_insert_after(__pos,
00839                                           std::forward<_Args>(__args)...)); }
00840 
00841       /**
00842        *  @brief  Inserts given value into %forward_list after specified
00843        *          iterator.
00844        *  @param  __pos  An iterator into the %forward_list.
00845        *  @param  __val  Data to be inserted.
00846        *  @return  An iterator that points to the inserted data.
00847        *
00848        *  This function will insert a copy of the given value after
00849        *  the specified location.  Due to the nature of a %forward_list this
00850        *  operation can be done in constant time, and does not
00851        *  invalidate iterators and references.
00852        */
00853       iterator
00854       insert_after(const_iterator __pos, const _Tp& __val)
00855       { return iterator(this->_M_insert_after(__pos, __val)); }
00856 
00857       /**
00858        *
00859        */
00860       iterator
00861       insert_after(const_iterator __pos, _Tp&& __val)
00862       { return iterator(this->_M_insert_after(__pos, std::move(__val))); }
00863 
00864       /**
00865        *  @brief  Inserts a number of copies of given data into the
00866        *          %forward_list.
00867        *  @param  __pos  An iterator into the %forward_list.
00868        *  @param  __n  Number of elements to be inserted.
00869        *  @param  __val  Data to be inserted.
00870        *  @return  An iterator pointing to the last inserted copy of
00871        *           @a val or @a pos if @a n == 0.
00872        *
00873        *  This function will insert a specified number of copies of the
00874        *  given data after the location specified by @a pos.
00875        *
00876        *  This operation is linear in the number of elements inserted and
00877        *  does not invalidate iterators and references.
00878        */
00879       iterator
00880       insert_after(const_iterator __pos, size_type __n, const _Tp& __val);
00881 
00882       /**
00883        *  @brief  Inserts a range into the %forward_list.
00884        *  @param  __pos  An iterator into the %forward_list.
00885        *  @param  __first  An input iterator.
00886        *  @param  __last   An input iterator.
00887        *  @return  An iterator pointing to the last inserted element or
00888        *           @a __pos if @a __first == @a __last.
00889        *
00890        *  This function will insert copies of the data in the range
00891        *  [@a __first,@a __last) into the %forward_list after the
00892        *  location specified by @a __pos.
00893        *
00894        *  This operation is linear in the number of elements inserted and
00895        *  does not invalidate iterators and references.
00896        */
00897       template<typename _InputIterator,
00898            typename = std::_RequireInputIter<_InputIterator>>
00899         iterator
00900         insert_after(const_iterator __pos,
00901                      _InputIterator __first, _InputIterator __last);
00902 
00903       /**
00904        *  @brief  Inserts the contents of an initializer_list into
00905        *          %forward_list after the specified iterator.
00906        *  @param  __pos  An iterator into the %forward_list.
00907        *  @param  __il  An initializer_list of value_type.
00908        *  @return  An iterator pointing to the last inserted element
00909        *           or @a __pos if @a __il is empty.
00910        *
00911        *  This function will insert copies of the data in the
00912        *  initializer_list @a __il into the %forward_list before the location
00913        *  specified by @a __pos.
00914        *
00915        *  This operation is linear in the number of elements inserted and
00916        *  does not invalidate iterators and references.
00917        */
00918       iterator
00919       insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
00920       { return insert_after(__pos, __il.begin(), __il.end()); }
00921 
00922       /**
00923        *  @brief  Removes the element pointed to by the iterator following
00924        *          @c pos.
00925        *  @param  __pos  Iterator pointing before element to be erased.
00926        *  @return  An iterator pointing to the element following the one
00927        *           that was erased, or end() if no such element exists.
00928        *
00929        *  This function will erase the element at the given position and
00930        *  thus shorten the %forward_list by one.
00931        *
00932        *  Due to the nature of a %forward_list this operation can be done
00933        *  in constant time, and only invalidates iterators/references to
00934        *  the element being removed.  The user is also cautioned that
00935        *  this function only erases the element, and that if the element
00936        *  is itself a pointer, the pointed-to memory is not touched in
00937        *  any way.  Managing the pointer is the user's responsibility.
00938        */
00939       iterator
00940       erase_after(const_iterator __pos)
00941       { return iterator(this->_M_erase_after(const_cast<_Node_base*>
00942                          (__pos._M_node))); }
00943 
00944       /**
00945        *  @brief  Remove a range of elements.
00946        *  @param  __pos  Iterator pointing before the first element to be
00947        *                 erased.
00948        *  @param  __last  Iterator pointing to one past the last element to be
00949        *                  erased.
00950        *  @return  @ __last.
00951        *
00952        *  This function will erase the elements in the range
00953        *  @a (__pos,__last) and shorten the %forward_list accordingly.
00954        *
00955        *  This operation is linear time in the size of the range and only
00956        *  invalidates iterators/references to the element being removed.
00957        *  The user is also cautioned that this function only erases the
00958        *  elements, and that if the elements themselves are pointers, the
00959        *  pointed-to memory is not touched in any way.  Managing the pointer
00960        *  is the user's responsibility.
00961        */
00962       iterator
00963       erase_after(const_iterator __pos, const_iterator __last)
00964       { return iterator(this->_M_erase_after(const_cast<_Node_base*>
00965                          (__pos._M_node),
00966                          const_cast<_Node_base*>
00967                          (__last._M_node))); }
00968 
00969       /**
00970        *  @brief  Swaps data with another %forward_list.
00971        *  @param  __list  A %forward_list of the same element and allocator
00972        *                  types.
00973        *
00974        *  This exchanges the elements between two lists in constant
00975        *  time.  Note that the global std::swap() function is
00976        *  specialized such that std::swap(l1,l2) will feed to this
00977        *  function.
00978        */
00979       void
00980       swap(forward_list& __list)
00981       noexcept(_Node_alloc_traits::_S_nothrow_swap())
00982       {
00983         std::swap(this->_M_impl._M_head._M_next,
00984           __list._M_impl._M_head._M_next);
00985     _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
00986                                        __list._M_get_Node_allocator());
00987       }
00988 
00989       /**
00990        *  @brief Resizes the %forward_list to the specified number of
00991        *         elements.
00992        *  @param __sz Number of elements the %forward_list should contain.
00993        *
00994        *  This function will %resize the %forward_list to the specified
00995        *  number of elements.  If the number is smaller than the
00996        *  %forward_list's current number of elements the %forward_list
00997        *  is truncated, otherwise the %forward_list is extended and the
00998        *  new elements are default constructed.
00999        */
01000       void
01001       resize(size_type __sz);
01002 
01003       /**
01004        *  @brief Resizes the %forward_list to the specified number of
01005        *         elements.
01006        *  @param __sz Number of elements the %forward_list should contain.
01007        *  @param __val Data with which new elements should be populated.
01008        *
01009        *  This function will %resize the %forward_list to the specified
01010        *  number of elements.  If the number is smaller than the
01011        *  %forward_list's current number of elements the %forward_list
01012        *  is truncated, otherwise the %forward_list is extended and new
01013        *  elements are populated with given data.
01014        */
01015       void
01016       resize(size_type __sz, const value_type& __val);
01017 
01018       /**
01019        *  @brief  Erases all the elements.
01020        *
01021        *  Note that this function only erases
01022        *  the elements, and that if the elements themselves are
01023        *  pointers, the pointed-to memory is not touched in any way.
01024        *  Managing the pointer is the user's responsibility.
01025        */
01026       void
01027       clear() noexcept
01028       { this->_M_erase_after(&this->_M_impl._M_head, 0); }
01029 
01030       // 23.3.4.6 forward_list operations:
01031 
01032       /**
01033        *  @brief  Insert contents of another %forward_list.
01034        *  @param  __pos  Iterator referencing the element to insert after.
01035        *  @param  __list  Source list.
01036        *
01037        *  The elements of @a list are inserted in constant time after
01038        *  the element referenced by @a pos.  @a list becomes an empty
01039        *  list.
01040        *
01041        *  Requires this != @a x.
01042        */
01043       void
01044       splice_after(const_iterator __pos, forward_list&& __list)
01045       {
01046     if (!__list.empty())
01047       _M_splice_after(__pos, __list.before_begin(), __list.end());
01048       }
01049 
01050       void
01051       splice_after(const_iterator __pos, forward_list& __list)
01052       { splice_after(__pos, std::move(__list)); }
01053 
01054       /**
01055        *  @brief  Insert element from another %forward_list.
01056        *  @param  __pos  Iterator referencing the element to insert after.
01057        *  @param  __list  Source list.
01058        *  @param  __i   Iterator referencing the element before the element
01059        *                to move.
01060        *
01061        *  Removes the element in list @a list referenced by @a i and
01062        *  inserts it into the current list after @a pos.
01063        */
01064       void
01065       splice_after(const_iterator __pos, forward_list&& __list,
01066                    const_iterator __i);
01067 
01068       void
01069       splice_after(const_iterator __pos, forward_list& __list,
01070                    const_iterator __i)
01071       { splice_after(__pos, std::move(__list), __i); }
01072 
01073       /**
01074        *  @brief  Insert range from another %forward_list.
01075        *  @param  __pos  Iterator referencing the element to insert after.
01076        *  @param  __list  Source list.
01077        *  @param  __before  Iterator referencing before the start of range
01078        *                    in list.
01079        *  @param  __last  Iterator referencing the end of range in list.
01080        *
01081        *  Removes elements in the range (__before,__last) and inserts them
01082        *  after @a __pos in constant time.
01083        *
01084        *  Undefined if @a __pos is in (__before,__last).
01085        */
01086       void
01087       splice_after(const_iterator __pos, forward_list&&,
01088                    const_iterator __before, const_iterator __last)
01089       { _M_splice_after(__pos, __before, __last); }
01090 
01091       void
01092       splice_after(const_iterator __pos, forward_list&,
01093                    const_iterator __before, const_iterator __last)
01094       { _M_splice_after(__pos, __before, __last); }
01095 
01096       /**
01097        *  @brief  Remove all elements equal to value.
01098        *  @param  __val  The value to remove.
01099        *
01100        *  Removes every element in the list equal to @a __val.
01101        *  Remaining elements stay in list order.  Note that this
01102        *  function only erases the elements, and that if the elements
01103        *  themselves are pointers, the pointed-to memory is not
01104        *  touched in any way.  Managing the pointer is the user's
01105        *  responsibility.
01106        */
01107       void
01108       remove(const _Tp& __val);
01109 
01110       /**
01111        *  @brief  Remove all elements satisfying a predicate.
01112        *  @param  __pred  Unary predicate function or object.
01113        *
01114        *  Removes every element in the list for which the predicate
01115        *  returns true.  Remaining elements stay in list order.  Note
01116        *  that this function only erases the elements, and that if the
01117        *  elements themselves are pointers, the pointed-to memory is
01118        *  not touched in any way.  Managing the pointer is the user's
01119        *  responsibility.
01120        */
01121       template<typename _Pred>
01122         void
01123         remove_if(_Pred __pred);
01124 
01125       /**
01126        *  @brief  Remove consecutive duplicate elements.
01127        *
01128        *  For each consecutive set of elements with the same value,
01129        *  remove all but the first one.  Remaining elements stay in
01130        *  list order.  Note that this function only erases the
01131        *  elements, and that if the elements themselves are pointers,
01132        *  the pointed-to memory is not touched in any way.  Managing
01133        *  the pointer is the user's responsibility.
01134        */
01135       void
01136       unique()
01137       { unique(std::equal_to<_Tp>()); }
01138 
01139       /**
01140        *  @brief  Remove consecutive elements satisfying a predicate.
01141        *  @param  __binary_pred  Binary predicate function or object.
01142        *
01143        *  For each consecutive set of elements [first,last) that
01144        *  satisfy predicate(first,i) where i is an iterator in
01145        *  [first,last), remove all but the first one.  Remaining
01146        *  elements stay in list order.  Note that this function only
01147        *  erases the elements, and that if the elements themselves are
01148        *  pointers, the pointed-to memory is not touched in any way.
01149        *  Managing the pointer is the user's responsibility.
01150        */
01151       template<typename _BinPred>
01152         void
01153         unique(_BinPred __binary_pred);
01154 
01155       /**
01156        *  @brief  Merge sorted lists.
01157        *  @param  __list  Sorted list to merge.
01158        *
01159        *  Assumes that both @a list and this list are sorted according to
01160        *  operator<().  Merges elements of @a __list into this list in
01161        *  sorted order, leaving @a __list empty when complete.  Elements in
01162        *  this list precede elements in @a __list that are equal.
01163        */
01164       void
01165       merge(forward_list&& __list)
01166       { merge(std::move(__list), std::less<_Tp>()); }
01167 
01168       void
01169       merge(forward_list& __list)
01170       { merge(std::move(__list)); }
01171 
01172       /**
01173        *  @brief  Merge sorted lists according to comparison function.
01174        *  @param  __list  Sorted list to merge.
01175        *  @param  __comp Comparison function defining sort order.
01176        *
01177        *  Assumes that both @a __list and this list are sorted according to
01178        *  comp.  Merges elements of @a __list into this list
01179        *  in sorted order, leaving @a __list empty when complete.  Elements
01180        *  in this list precede elements in @a __list that are equivalent
01181        *  according to comp().
01182        */
01183       template<typename _Comp>
01184         void
01185         merge(forward_list&& __list, _Comp __comp);
01186 
01187       template<typename _Comp>
01188         void
01189         merge(forward_list& __list, _Comp __comp)
01190         { merge(std::move(__list), __comp); }
01191 
01192       /**
01193        *  @brief  Sort the elements of the list.
01194        *
01195        *  Sorts the elements of this list in NlogN time.  Equivalent
01196        *  elements remain in list order.
01197        */
01198       void
01199       sort()
01200       { sort(std::less<_Tp>()); }
01201 
01202       /**
01203        *  @brief  Sort the forward_list using a comparison function.
01204        *
01205        *  Sorts the elements of this list in NlogN time.  Equivalent
01206        *  elements remain in list order.
01207        */
01208       template<typename _Comp>
01209         void
01210         sort(_Comp __comp);
01211 
01212       /**
01213        *  @brief  Reverse the elements in list.
01214        *
01215        *  Reverse the order of elements in the list in linear time.
01216        */
01217       void
01218       reverse() noexcept
01219       { this->_M_impl._M_head._M_reverse_after(); }
01220 
01221     private:
01222       // Called by the range constructor to implement [23.3.4.2]/9
01223       template<typename _InputIterator>
01224         void
01225         _M_range_initialize(_InputIterator __first, _InputIterator __last);
01226 
01227       // Called by forward_list(n,v,a), and the range constructor when it
01228       // turns out to be the same thing.
01229       void
01230       _M_fill_initialize(size_type __n, const value_type& __value);
01231 
01232       // Called by splice_after and insert_after.
01233       iterator
01234       _M_splice_after(const_iterator __pos, const_iterator __before,
01235               const_iterator __last);
01236 
01237       // Called by forward_list(n).
01238       void
01239       _M_default_initialize(size_type __n);
01240 
01241       // Called by resize(sz).
01242       void
01243       _M_default_insert_after(const_iterator __pos, size_type __n);
01244 
01245       // Called by operator=(forward_list&&)
01246       void
01247       _M_move_assign(forward_list&& __list, std::true_type) noexcept
01248       {
01249         clear();
01250         std::swap(this->_M_impl._M_head._M_next,
01251                   __list._M_impl._M_head._M_next);
01252         std::__alloc_on_move(this->_M_get_Node_allocator(),
01253                              __list._M_get_Node_allocator());
01254       }
01255 
01256       // Called by operator=(forward_list&&)
01257       void
01258       _M_move_assign(forward_list&& __list, std::false_type)
01259       {
01260         if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
01261           _M_move_assign(std::move(__list), std::true_type());
01262         else
01263       // The rvalue's allocator cannot be moved, or is not equal,
01264       // so we need to individually move each element.
01265       this->assign(std::__make_move_if_noexcept_iterator(__list.begin()),
01266                std::__make_move_if_noexcept_iterator(__list.end()));
01267       }
01268 
01269       // Called by assign(_InputIterator, _InputIterator) if _Tp is
01270       // CopyAssignable.
01271       template<typename _InputIterator>
01272     void
01273         _M_assign(_InputIterator __first, _InputIterator __last, true_type)
01274     {
01275       auto __prev = before_begin();
01276       auto __curr = begin();
01277       auto __end = end();
01278       while (__curr != __end && __first != __last)
01279         {
01280           *__curr = *__first;
01281           ++__prev;
01282           ++__curr;
01283           ++__first;
01284         }
01285       if (__first != __last)
01286         insert_after(__prev, __first, __last);
01287       else if (__curr != __end)
01288         erase_after(__prev, __end);
01289         }
01290 
01291       // Called by assign(_InputIterator, _InputIterator) if _Tp is not
01292       // CopyAssignable.
01293       template<typename _InputIterator>
01294     void
01295         _M_assign(_InputIterator __first, _InputIterator __last, false_type)
01296     {
01297       clear();
01298       insert_after(cbefore_begin(), __first, __last);
01299     }
01300 
01301       // Called by assign(size_type, const _Tp&) if Tp is CopyAssignable
01302       void
01303       _M_assign_n(size_type __n, const _Tp& __val, true_type)
01304       {
01305     auto __prev = before_begin();
01306     auto __curr = begin();
01307     auto __end = end();
01308     while (__curr != __end && __n > 0)
01309       {
01310         *__curr = __val;
01311         ++__prev;
01312         ++__curr;
01313         --__n;
01314       }
01315     if (__n > 0)
01316       insert_after(__prev, __n, __val);
01317     else if (__curr != __end)
01318       erase_after(__prev, __end);
01319       }
01320 
01321       // Called by assign(size_type, const _Tp&) if Tp is non-CopyAssignable
01322       void
01323       _M_assign_n(size_type __n, const _Tp& __val, false_type)
01324       {
01325     clear();
01326     insert_after(cbefore_begin(), __n, __val);
01327       }
01328     };
01329 
01330   /**
01331    *  @brief  Forward list equality comparison.
01332    *  @param  __lx  A %forward_list
01333    *  @param  __ly  A %forward_list of the same type as @a __lx.
01334    *  @return  True iff the elements of the forward lists are equal.
01335    *
01336    *  This is an equivalence relation.  It is linear in the number of 
01337    *  elements of the forward lists.  Deques are considered equivalent
01338    *  if corresponding elements compare equal.
01339    */
01340   template<typename _Tp, typename _Alloc>
01341     bool
01342     operator==(const forward_list<_Tp, _Alloc>& __lx,
01343                const forward_list<_Tp, _Alloc>& __ly);
01344 
01345   /**
01346    *  @brief  Forward list ordering relation.
01347    *  @param  __lx  A %forward_list.
01348    *  @param  __ly  A %forward_list of the same type as @a __lx.
01349    *  @return  True iff @a __lx is lexicographically less than @a __ly.
01350    *
01351    *  This is a total ordering relation.  It is linear in the number of 
01352    *  elements of the forward lists.  The elements must be comparable
01353    *  with @c <.
01354    *
01355    *  See std::lexicographical_compare() for how the determination is made.
01356    */
01357   template<typename _Tp, typename _Alloc>
01358     inline bool
01359     operator<(const forward_list<_Tp, _Alloc>& __lx,
01360               const forward_list<_Tp, _Alloc>& __ly)
01361     { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(),
01362                       __ly.cbegin(), __ly.cend()); }
01363 
01364   /// Based on operator==
01365   template<typename _Tp, typename _Alloc>
01366     inline bool
01367     operator!=(const forward_list<_Tp, _Alloc>& __lx,
01368                const forward_list<_Tp, _Alloc>& __ly)
01369     { return !(__lx == __ly); }
01370 
01371   /// Based on operator<
01372   template<typename _Tp, typename _Alloc>
01373     inline bool
01374     operator>(const forward_list<_Tp, _Alloc>& __lx,
01375               const forward_list<_Tp, _Alloc>& __ly)
01376     { return (__ly < __lx); }
01377 
01378   /// Based on operator<
01379   template<typename _Tp, typename _Alloc>
01380     inline bool
01381     operator>=(const forward_list<_Tp, _Alloc>& __lx,
01382                const forward_list<_Tp, _Alloc>& __ly)
01383     { return !(__lx < __ly); }
01384 
01385   /// Based on operator<
01386   template<typename _Tp, typename _Alloc>
01387     inline bool
01388     operator<=(const forward_list<_Tp, _Alloc>& __lx,
01389                const forward_list<_Tp, _Alloc>& __ly)
01390     { return !(__ly < __lx); }
01391 
01392   /// See std::forward_list::swap().
01393   template<typename _Tp, typename _Alloc>
01394     inline void
01395     swap(forward_list<_Tp, _Alloc>& __lx,
01396      forward_list<_Tp, _Alloc>& __ly)
01397     { __lx.swap(__ly); }
01398 
01399 _GLIBCXX_END_NAMESPACE_CONTAINER
01400 } // namespace std
01401 
01402 #endif // _FORWARD_LIST_H