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