libstdc++-v3/include/bits/forward_list.h

   1 // <forward_list.h> -*- C++ -*-
   2
   3 // Copyright (C) 2008 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 // Boston, MA 02110-1301, USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file forward_list.h
  31  *  This is a Standard C++ Library header.
  32  */
  33
  34 #ifndef _FORWARD_LIST_H
  35 #define _FORWARD_LIST_H 1
  36
  37 #pragma GCC system_header
  38
  39 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  40 # include <c++0x_warning.h>
  41 #else
  42
  43 #include <memory>
  44 #include <initializer_list>
  45
  46 _GLIBCXX_BEGIN_NAMESPACE(std)
  47
  48   /**
  49    *  @brief  A helper basic node class for @forward_list.
  50    *          This is just a linked list with nothing inside it.
  51    *          There are purely list shuffling utility methods here.
  52    */
  53   struct _Fwd_list_node_base
  54   {
  55     _Fwd_list_node_base() : _M_next(0) { }
  56
  57     _Fwd_list_node_base* _M_next;
  58
  59     static void
  60     swap(_Fwd_list_node_base& __x, _Fwd_list_node_base& __y)
  61     { std::swap(__x._M_next, __y._M_next); }
  62
  63     void
  64     _M_transfer_after(_Fwd_list_node_base* __bbegin,
  65                       _Fwd_list_node_base* __bend)
  66     {
  67       _Fwd_list_node_base* __keep = __bbegin->_M_next;
  68       if (__bend)
  69         {
  70           __bbegin->_M_next = __bend->_M_next;
  71           __bend->_M_next = this->_M_next;
  72         }
  73       else
  74         __bbegin->_M_next = 0;
  75       this->_M_next = __keep;
  76     }
  77
  78     void
  79     _M_transfer_after(_Fwd_list_node_base* __bbegin)
  80     {
  81       _Fwd_list_node_base* __bend = __bbegin;
  82       while (__bend && __bend->_M_next)
  83         __bend = __bend->_M_next;
  84       _M_transfer_after(__bbegin, __bend);
  85     }
  86
  87     void
  88     _M_reverse_after()
  89     {
  90       _Fwd_list_node_base* __tail = this->_M_next;
  91       if (!__tail)
  92         return;
  93       while (_Fwd_list_node_base* __temp = __tail->_M_next)
  94         {
  95           _Fwd_list_node_base* __keep = this->_M_next;
  96           this->_M_next = __temp;
  97           __tail->_M_next = __temp->_M_next;
  98           this->_M_next->_M_next = __keep;
  99         }
 100     }
 101   };
 102
 103   /**
 104    *  @brief  A helper node class for @forward_list.
 105    *          This is just a linked list with a data value in each node.
 106    *          There is a sorting utility method.
 107    */
 108   template<typename _Tp>
 109     struct _Fwd_list_node : public _Fwd_list_node_base
 110     {
 111       template<typename... _Args>
 112         _Fwd_list_node(_Args&&... __args)
 113         : _Fwd_list_node_base(), _M_value(std::forward<_Args>(__args)...) { }
 114
 115       template<typename _Comp>
 116         void
 117         _M_sort_after(_Comp __comp);
 118
 119       _Tp _M_value;
 120     };
 121
 122   /**
 123    *   @brief A forward_list::iterator.
 124    *
 125    *   All the functions are op overloads.
 126    */
 127   template<typename _Tp>
 128     struct _Fwd_list_iterator
 129     {
 130       typedef _Fwd_list_iterator<_Tp>           _Self;
 131       typedef _Fwd_list_node<_Tp>               _Node;
 132
 133       typedef _Tp                               value_type;
 134       typedef _Tp*                              pointer;
 135       typedef _Tp&                              reference;
 136       typedef ptrdiff_t                         difference_type;
 137       typedef std::forward_iterator_tag         iterator_category;
 138
 139       _Fwd_list_iterator() : _M_node() { }
 140
 141       explicit
 142       _Fwd_list_iterator(_Fwd_list_node_base* __n) : _M_node(__n) { }
 143
 144       reference
 145       operator*() const
 146       { return static_cast<_Node*>(this->_M_node)->_M_value; }
 147
 148       pointer
 149       operator->() const
 150       { return &static_cast<_Node*>(this->_M_node)->_M_value; }
 151
 152       _Self&
 153       operator++()
 154       {
 155         this->_M_node = this->_M_node->_M_next;
 156         return *this;
 157       }
 158
 159       _Self
 160       operator++(int)
 161       {
 162         _Self __tmp(*this);
 163         this->_M_node = this->_M_node->_M_next;
 164         return __tmp;
 165       }
 166
 167       bool
 168       operator==(const _Self& __x) const
 169       { return this->_M_node == __x._M_node; }
 170
 171       bool
 172       operator!=(const _Self& __x) const
 173       { return this->_M_node != __x._M_node; }
 174
 175       const _Self&
 176       _M_next() const
 177       {
 178         if (_M_node)
 179           return _Fwd_list_iterator(this->_M_node->_M_next);
 180         else
 181           return _Fwd_list_iterator(0);
 182       }
 183
 184       _Fwd_list_node_base* _M_node;
 185     };
 186
 187   /**
 188    *   @brief A forward_list::const_iterator.
 189    *
 190    *   All the functions are op overloads.
 191    */
 192   template<typename _Tp>
 193     struct _Fwd_list_const_iterator
 194     {
 195       typedef _Fwd_list_const_iterator<_Tp>     _Self;
 196       typedef const _Fwd_list_node<_Tp>         _Node;
 197       typedef _Fwd_list_iterator<_Tp>           iterator;
 198
 199       typedef _Tp                               value_type;
 200       typedef const _Tp*                        pointer;
 201       typedef const _Tp&                        reference;
 202       typedef ptrdiff_t                         difference_type;
 203       typedef std::forward_iterator_tag         iterator_category;
 204
 205       _Fwd_list_const_iterator() : _M_node() { }
 206
 207       explicit
 208       _Fwd_list_const_iterator(const _Fwd_list_node_base* __n)
 209       : _M_node(__n) { }
 210
 211       _Fwd_list_const_iterator(const iterator& __iter)
 212       : _M_node(__iter._M_node) { }
 213
 214       reference
 215       operator*() const
 216       { return static_cast<_Node*>(this->_M_node)->_M_value; }
 217
 218       pointer
 219       operator->() const
 220       { return &static_cast<_Node*>(this->_M_node)->_M_value; }
 221
 222       _Self&
 223       operator++()
 224       {
 225         this->_M_node = this->_M_node->_M_next;
 226         return *this;
 227       }
 228
 229       _Self
 230       operator++(int)
 231       {
 232         _Self __tmp(*this);
 233         this->_M_node = this->_M_node->_M_next;
 234         return __tmp;
 235       }
 236
 237       bool
 238       operator==(const _Self& __x) const
 239       { return this->_M_node == __x._M_node; }
 240
 241       bool
 242       operator!=(const _Self& __x) const
 243       { return this->_M_node != __x._M_node; }
 244
 245       const _Self&
 246       _M_next() const
 247       {
 248         if (this->_M_node)
 249           return _Fwd_list_const_iterator(this->_M_node->_M_next);
 250         else
 251           return _Fwd_list_const_iterator(0);
 252       }
 253
 254       const _Fwd_list_node_base* _M_node;
 255     };
 256
 257   /**
 258    *  @brief  Forward list iterator equality comparison.
 259    */
 260   template<typename _Tp>
 261     inline bool
 262     operator==(const _Fwd_list_iterator<_Tp>& __x,
 263                const _Fwd_list_const_iterator<_Tp>& __y)
 264     { return __x._M_node == __y._M_node; }
 265
 266   /**
 267    *  @brief  Forward list iterator inequality comparison.
 268    */
 269   template<typename _Tp>
 270     inline bool
 271     operator!=(const _Fwd_list_iterator<_Tp>& __x,
 272                const _Fwd_list_const_iterator<_Tp>& __y)
 273     { return __x._M_node != __y._M_node; }
 274
 275   /**
 276    *  @brief  Base class for @forward_list.
 277    */
 278   template<typename _Tp, typename _Alloc>
 279     struct _Fwd_list_base
 280     {
 281     protected:
 282       typedef typename _Alloc::template rebind<_Fwd_list_node<_Tp>>::other
 283         _Node_alloc_type;
 284
 285       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
 286
 287       struct _Fwd_list_impl
 288       : public _Node_alloc_type
 289       {
 290         _Fwd_list_node_base _M_head;
 291
 292         _Fwd_list_impl()
 293         : _Node_alloc_type(), _M_head()
 294         { }
 295
 296         _Fwd_list_impl(const _Node_alloc_type& __a)
 297         : _Node_alloc_type(__a), _M_head()
 298         { }
 299       };
 300
 301       _Fwd_list_impl _M_impl;
 302
 303     public:
 304       typedef _Fwd_list_iterator<_Tp>         iterator;
 305       typedef _Fwd_list_const_iterator<_Tp>   const_iterator;
 306
 307       typedef _Fwd_list_node<_Tp>             _Node;
 308
 309       _Node_alloc_type&
 310       _M_get_Node_allocator()
 311       { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
 312
 313       const _Node_alloc_type&
 314       _M_get_Node_allocator() const
 315       { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
 316
 317       _Fwd_list_base()
 318       : _M_impl()
 319       { this->_M_impl._M_head._M_next = 0; }
 320
 321       _Fwd_list_base(const _Alloc& __a)
 322       : _M_impl(__a)
 323       { this->_M_impl._M_head._M_next = 0; }
 324
 325       _Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a);
 326
 327       _Fwd_list_base(_Fwd_list_base&& __lst, const _Alloc& __a)
 328       : _M_impl(__a)
 329       { _Fwd_list_node_base::swap(this->_M_impl._M_head,
 330                                   __lst._M_impl._M_head); }
 331
 332       _Fwd_list_base(_Fwd_list_base&& __lst)
 333       : _M_impl(__lst._M_get_Node_allocator())
 334       { _Fwd_list_node_base::swap(this->_M_impl._M_head,
 335                                   __lst._M_impl._M_head); }
 336
 337       ~_Fwd_list_base()
 338       { _M_erase_after(&_M_impl._M_head, 0); }
 339
 340     protected:
 341
 342       _Node*
 343       _M_get_node()
 344       { return _M_get_Node_allocator().allocate(1); }
 345
 346       template<typename... _Args>
 347         _Node*
 348         _M_create_node(_Args&&... __args)
 349         {
 350           _Node* __node = this->_M_get_node();
 351           try
 352             {
 353               _M_get_Node_allocator().construct(__node,
 354                                               std::forward<_Args>(__args)...);
 355               __node->_M_next = 0;
 356             }
 357           catch(...)
 358             {
 359               this->_M_put_node(__node);
 360               __throw_exception_again;
 361             }
 362           return __node;
 363         }
 364
 365       template<typename... _Args>
 366         _Fwd_list_node_base*
 367         _M_insert_after(const_iterator __pos, _Args&&... __args);
 368
 369       void
 370       _M_put_node(_Node* __p)
 371       { _M_get_Node_allocator().deallocate(__p, 1); }
 372
 373       _Fwd_list_node_base*
 374       _M_erase_after(_Fwd_list_node_base* __pos);
 375
 376       _Fwd_list_node_base*
 377       _M_erase_after(_Fwd_list_node_base* __pos,
 378                      _Fwd_list_node_base* __last);
 379     };
 380
 381   /**
 382    *  @brief A standard container with linear time access to elements,
 383    *  and fixed time insertion/deletion at any point in the sequence.
 384    *
 385    *  @ingroup Containers
 386    *  @ingroup Sequences
 387    *
 388    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
 389    *  <a href="tables.html#67">sequence</a>, including the
 390    *  <a href="tables.html#68">optional sequence requirements</a> with the
 391    *  %exception of @c at and @c operator[].
 392    *
 393    *  This is a @e singly @e linked %list.  Traversal up the
 394    *  %list requires linear time, but adding and removing elements (or
 395    *  @e nodes) is done in constant time, regardless of where the
 396    *  change takes place.  Unlike std::vector and std::deque,
 397    *  random-access iterators are not provided, so subscripting ( @c
 398    *  [] ) access is not allowed.  For algorithms which only need
 399    *  sequential access, this lack makes no difference.
 400    *
 401    *  Also unlike the other standard containers, std::forward_list provides
 402    *  specialized algorithms %unique to linked lists, such as
 403    *  splicing, sorting, and in-place reversal.
 404    *
 405    *  A couple points on memory allocation for forward_list<Tp>:
 406    *
 407    *  First, we never actually allocate a Tp, we allocate
 408    *  Fwd_list_node<Tp>'s and trust [20.1.5]/4 to DTRT.  This is to ensure
 409    *  that after elements from %forward_list<X,Alloc1> are spliced into
 410    *  %forward_list<X,Alloc2>, destroying the memory of the second %list is a
 411    *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
 412    */
 413   template<typename _Tp, typename _Alloc = allocator<_Tp> >
 414     class forward_list : private _Fwd_list_base<_Tp, _Alloc>
 415     {
 416     private:
 417       typedef _Fwd_list_base<_Tp, _Alloc>                  _Base;
 418       typedef _Fwd_list_node<_Tp>                          _Node;
 419       typedef typename _Base::_Tp_alloc_type               _Tp_alloc_type;
 420
 421     public:
 422       // types:
 423       typedef _Tp                                          value_type;
 424       typedef typename _Tp_alloc_type::pointer             pointer;
 425       typedef typename _Tp_alloc_type::const_pointer       const_pointer;
 426       typedef typename _Tp_alloc_type::reference           reference;
 427       typedef typename _Tp_alloc_type::const_reference     const_reference;
 428       typedef _Fwd_list_iterator<_Tp>                      iterator;
 429       typedef _Fwd_list_const_iterator<_Tp>                const_iterator;
 430       typedef std::size_t                                  size_type;
 431       typedef std::ptrdiff_t                               difference_type;
 432       typedef _Alloc                                       allocator_type;
 433
 434       // 23.2.3.1 construct/copy/destroy:
 435
 436       /**
 437        *  @brief  Creates a %forward_list with no elements.
 438        *  @param  al  An allocator object.
 439        */
 440       explicit
 441       forward_list(const _Alloc& __al = _Alloc())
 442       : _Base(__al)
 443       { }
 444
 445       /**
 446        *  @brief  Copy constructor with allocator argument.
 447        *  @param  list  Input list to copy.
 448        *  @param  al    An allocator object.
 449        */
 450       forward_list(const forward_list& __list, const _Alloc& __al)
 451       : _Base(__list, __al)
 452       { }
 453
 454       /**
 455        *  @brief  Move constructor with allocator argument.
 456        *  @param  list  Input list to move.
 457        *  @param  al    An allocator object.
 458        */
 459       forward_list(forward_list&& __list, const _Alloc& __al)
 460       : _Base(std::forward<_Base>(__list), __al)
 461       { }
 462
 463       /**
 464        *  @brief  Creates a %forward_list with copies of the default element
 465        *          type.
 466        *  @param  n  The number of elements to initially create.
 467        *
 468        *  This constructor fills the %forward_list with @a n copies of
 469        *  the default value.
 470        */
 471       explicit
 472       forward_list(size_type __n)
 473       : _Base()
 474       { _M_fill_initialize(__n, value_type()); }
 475
 476       /**
 477        *  @brief  Creates a %forward_list with copies of an exemplar element.
 478        *  @param  n      The number of elements to initially create.
 479        *  @param  value  An element to copy.
 480        *  @param  al     An allocator object.
 481        *
 482        *  This constructor fills the %forward_list with @a n copies of @a
 483        *  value.
 484        */
 485       forward_list(size_type __n, const _Tp& __value,
 486                    const _Alloc& __al = _Alloc())
 487       : _Base(__al)
 488       { _M_fill_initialize(__n, __value); }
 489
 490       /**
 491        *  @brief  Builds a %forward_list from a range.
 492        *  @param  first  An input iterator.
 493        *  @param  last   An input iterator.
 494        *  @param  al     An allocator object.
 495        *
 496        *  Create a %forward_list consisting of copies of the elements from
 497        *  [@a first,@a last).  This is linear in N (where N is
 498        *  distance(@a first,@a last)).
 499        */
 500       template<typename _InputIterator>
 501         forward_list(_InputIterator __first, _InputIterator __last,
 502                      const _Alloc& __al = _Alloc())
 503         : _Base(__al)
 504         {
 505           // Check whether it's an integral type.  If so, it's not an iterator.
 506           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 507           _M_initialize_dispatch(__first, __last, _Integral());
 508         }
 509
 510       /**
 511        *  @brief  The %forward_list copy constructor.
 512        *  @param  list  A %forward_list of identical element and allocator
 513        *                types.
 514        *
 515        *  The newly-created %forward_list uses a copy of the allocation
 516        *  object used by @a list.
 517        */
 518       forward_list(const forward_list& __list)
 519       : _Base(__list.get_allocator())
 520       { _M_initialize_dispatch(__list.begin(), __list.end(), __false_type()); }
 521
 522       /**
 523        *  @brief  The %forward_list move constructor.
 524        *  @param  list  A %forward_list of identical element and allocator
 525        *                types.
 526        *
 527        *  The newly-created %forward_list contains the exact contents of @a
 528        *  forward_list. The contents of @a list are a valid, but unspecified
 529        *  %forward_list.
 530        */
 531       forward_list(forward_list&& __list)
 532       : _Base(std::forward<_Base>(__list)) { }
 533
 534       /**
 535        *  @brief  Builds a %forward_list from an initializer_list
 536        *  @param  il  An initializer_list of value_type.
 537        *  @param  al  An allocator object.
 538        *
 539        *  Create a %forward_list consisting of copies of the elements
 540        *  in the initializer_list @a il.  This is linear in il.size().
 541        */
 542       forward_list(std::initializer_list<_Tp> __il,
 543                    const _Alloc& __al = _Alloc())
 544       : _Base(__al)
 545       { _M_initialize_dispatch(__il.begin(), __il.end(), __false_type()); }
 546
 547       /**
 548        *  @brief  The forward_list dtor.
 549        */
 550       ~forward_list()
 551       { _M_erase_after(&this->_M_impl._M_head, 0); }
 552
 553       /**
 554        *  @brief  The %forward_list assignment operator.
 555        *  @param  list  A %forward_list of identical element and allocator
 556        *                types.
 557        *
 558        *  All the elements of @a list are copied, but unlike the copy
 559        *  constructor, the allocator object is not copied.
 560        */
 561       forward_list&
 562       operator=(const forward_list& __list);
 563
 564       /**
 565        *  @brief  The %forward_list move assignment operator.
 566        *  @param  list  A %forward_list of identical element and allocator
 567        *                types.
 568        *
 569        *  The contents of @a list are moved into this %forward_list
 570        *  (without copying). @a list is a valid, but unspecified
 571        *  %forward_list
 572        */
 573       forward_list&
 574       operator=(forward_list&& __list)
 575       {
 576         if (&__list != this)
 577           {
 578             this->clear();
 579             this->swap(__list);
 580           }
 581         return *this;
 582       }
 583
 584       /**
 585        *  @brief  The %forward_list initializer list assignment operator.
 586        *  @param  il  An initializer_list of value_type.
 587        *
 588        *  Replace the contents of the %forward_list with copies of the
 589        *  elements in the initializer_list @a il.  This is linear in
 590        *  il.size().
 591        */
 592       forward_list&
 593       operator=(std::initializer_list<_Tp> __il)
 594       {
 595         assign(__il);
 596         return *this;
 597       }
 598
 599       /**
 600        *  @brief  Assigns a range to a %forward_list.
 601        *  @param  first  An input iterator.
 602        *  @param  last   An input iterator.
 603        *
 604        *  This function fills a %forward_list with copies of the elements
 605        *  in the range [@a first,@a last).
 606        *
 607        *  Note that the assignment completely changes the %forward_list and
 608        *  that the resulting %forward_list's size is the same as the number
 609        *  of elements assigned.  Old data may be lost.
 610        */
 611       template<typename _InputIterator>
 612         void
 613         assign(_InputIterator __first, _InputIterator __last)
 614         {
 615           clear();
 616           insert_after(cbefore_begin(), __first, __last);
 617         }
 618
 619       /**
 620        *  @brief  Assigns a given value to a %forward_list.
 621        *  @param  n  Number of elements to be assigned.
 622        *  @param  val  Value to be assigned.
 623        *
 624        *  This function fills a %forward_list with @a n copies of the given
 625        *  value.  Note that the assignment completely changes the
 626        *  %forward_list and that the resulting %forward_list's size is the
 627        *  same as the number of elements assigned.  Old data may be lost.
 628        */
 629       void
 630       assign(size_type __n, const _Tp& __val)
 631       {
 632         clear();
 633         insert_after(cbefore_begin(), __n, __val);
 634       }
 635
 636       /**
 637        *  @brief  Assigns an initializer_list to a %forward_list.
 638        *  @param  il  An initializer_list of value_type.
 639        *
 640        *  Replace the contents of the %forward_list with copies of the
 641        *  elements in the initializer_list @a il.  This is linear in
 642        *  il.size().
 643        */
 644       void
 645       assign(std::initializer_list<_Tp> __il)
 646       {
 647         clear();
 648         insert_after(cbefore_begin(), __il);
 649       }
 650
 651       /// Get a copy of the memory allocation object.
 652       allocator_type
 653       get_allocator() const
 654       { return this->_M_get_Node_allocator(); }
 655
 656       // 23.2.3.2 iterators:
 657
 658       /**
 659        *  Returns a read/write iterator that points before the first element
 660        *  in the %forward_list.  Iteration is done in ordinary element order.
 661        */
 662       iterator
 663       before_begin()
 664       { return iterator(&this->_M_impl._M_head); }
 665
 666       /**
 667        *  Returns a read-only (constant) iterator that points before the
 668        *  first element in the %forward_list.  Iteration is done in ordinary
 669        *  element order.
 670        */
 671       const_iterator
 672       before_begin() const
 673       { return const_iterator(&this->_M_impl._M_head); }
 674
 675       /**
 676        *  Returns a read/write iterator that points to the first element
 677        *  in the %forward_list.  Iteration is done in ordinary element order.
 678        */
 679       iterator
 680       begin()
 681       { return iterator(this->_M_impl._M_head._M_next); }
 682
 683       /**
 684        *  Returns a read-only (constant) iterator that points to the first
 685        *  element in the %forward_list.  Iteration is done in ordinary
 686        *  element order.
 687        */
 688       const_iterator
 689       begin() const
 690       { return const_iterator(this->_M_impl._M_head._M_next); }
 691
 692       /**
 693        *  Returns a read/write iterator that points one past the last
 694        *  element in the %forward_list.  Iteration is done in ordinary
 695        *  element order.
 696        */
 697       iterator
 698       end()
 699       { return iterator(0); }
 700
 701       /**
 702        *  Returns a read-only iterator that points one past the last
 703        *  element in the %forward_list.  Iteration is done in ordinary
 704        *  element order.
 705        */
 706       const_iterator
 707       end() const
 708       { return const_iterator(0); }
 709
 710       /**
 711        *  Returns a read-only (constant) iterator that points to the
 712        *  first element in the %forward_list.  Iteration is done in ordinary
 713        *  element order.
 714        */
 715       const_iterator
 716       cbegin() const
 717       { return const_iterator(this->_M_impl._M_head._M_next); }
 718
 719       /**
 720        *  Returns a read-only (constant) iterator that points before the
 721        *  first element in the %forward_list.  Iteration is done in ordinary
 722        *  element order.
 723        */
 724       const_iterator
 725       cbefore_begin() const
 726       { return const_iterator(&this->_M_impl._M_head); }
 727
 728       /**
 729        *  Returns a read-only (constant) iterator that points one past
 730        *  the last element in the %forward_list.  Iteration is done in
 731        *  ordinary element order.
 732        */
 733       const_iterator
 734       cend() const
 735       { return const_iterator(0); }
 736
 737       /**
 738        *  Returns true if the %forward_list is empty.  (Thus begin() would
 739        *  equal end().)
 740        */
 741       bool
 742       empty() const
 743       { return this->_M_impl._M_head._M_next == 0; }
 744
 745       /**
 746        *  Returns the largest possible size of %forward_list.
 747        */
 748       size_type
 749       max_size() const
 750       { return this->_M_get_Node_allocator().max_size(); }
 751
 752       // 23.2.3.3 element access:
 753
 754       /**
 755        *  Returns a read/write reference to the data at the first
 756        *  element of the %forward_list.
 757        */
 758       reference
 759       front()
 760       {
 761         _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
 762         return __front->_M_value;
 763       }
 764
 765       /**
 766        *  Returns a read-only (constant) reference to the data at the first
 767        *  element of the %forward_list.
 768        */
 769       const_reference
 770       front() const
 771       {
 772         _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
 773         return __front->_M_value;
 774       }
 775
 776       // 23.2.3.4 modiﬁers:
 777
 778       /**
 779        *  @brief  Constructs object in %forward_list at the front of the
 780        *          list.
 781        *  @param  args  Arguments.
 782        *
 783        *  This function will insert an object of type Tp constructed
 784        *  with Tp(std::forward<Args>(args)...) at the front of the list
 785        *  Due to the nature of a %forward_list this operation can
 786        *  be done in constant time, and does not invalidate iterators
 787        *  and references.
 788        */
 789       template<typename... _Args>
 790         void
 791         emplace_front(_Args&&... __args)
 792         { this->_M_insert_after(cbefore_begin(),
 793                                 std::forward<_Args>(__args)...); }
 794
 795       /**
 796        *  @brief  Add data to the front of the %forward_list.
 797        *  @param  val  Data to be added.
 798        *
 799        *  This is a typical stack operation.  The function creates an
 800        *  element at the front of the %forward_list and assigns the given
 801        *  data to it.  Due to the nature of a %forward_list this operation
 802        *  can be done in constant time, and does not invalidate iterators
 803        *  and references.
 804        */
 805       void
 806       push_front(const _Tp& __val)
 807       { this->_M_insert_after(cbefore_begin(), __val); }
 808
 809       /**
 810        *
 811        */
 812       void
 813       push_front(_Tp&& __val)
 814       { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
 815
 816       /**
 817        *  @brief  Removes first element.
 818        *
 819        *  This is a typical stack operation.  It shrinks the %forward_list
 820        *  by one.  Due to the nature of a %forward_list this operation can
 821        *  be done in constant time, and only invalidates iterators/references
 822        *  to the element being removed.
 823        *
 824        *  Note that no data is returned, and if the first element's data
 825        *  is needed, it should be retrieved before pop_front() is
 826        *  called.
 827        */
 828       void
 829       pop_front()
 830       { this->_M_erase_after(&this->_M_impl._M_head); }
 831
 832       /**
 833        *  @brief  Constructs object in %forward_list after the specified
 834        *          iterator.
 835        *  @param  pos  A const_iterator into the %forward_list.
 836        *  @param  args  Arguments.
 837        *  @return  An iterator that points to the inserted data.
 838        *
 839        *  This function will insert an object of type T constructed
 840        *  with T(std::forward<Args>(args)...) after the specified
 841        *  location.  Due to the nature of a %forward_list this operation can
 842        *  be done in constant time, and does not invalidate iterators
 843        *  and references.
 844        */
 845       template<typename... _Args>
 846         iterator
 847         emplace_after(const_iterator __pos, _Args&&... __args)
 848         { return iterator(this->_M_insert_after(__pos,
 849                                           std::forward<_Args>(__args)...)); }
 850
 851       /**
 852        *  @brief  Inserts given value into %forward_list after specified
 853        *          iterator.
 854        *  @param  pos  An iterator into the %forward_list.
 855        *  @param  val  Data to be inserted.
 856        *  @return  An iterator that points to the inserted data.
 857        *
 858        *  This function will insert a copy of the given value after
 859        *  the specified location.  Due to the nature of a %forward_list this
 860        *  operation can be done in constant time, and does not
 861        *  invalidate iterators and references.
 862        */
 863       iterator
 864       insert_after(const_iterator __pos, const _Tp& __val)
 865       { return iterator(this->_M_insert_after(__pos, __val)); }
 866
 867       /**
 868        *
 869        */
 870       iterator
 871       insert_after(const_iterator __pos, _Tp&& __val)
 872       { return iterator(this->_M_insert_after(__pos, std::move(__val))); }
 873
 874       /**
 875        *  @brief  Inserts a number of copies of given data into the
 876        *          %forward_list.
 877        *  @param  pos  An iterator into the %forward_list.
 878        *  @param  n  Number of elements to be inserted.
 879        *  @param  val  Data to be inserted.
 880        *
 881        *  This function will insert a specified number of copies of the
 882        *  given data after the location specified by @a pos.
 883        *
 884        *  This operation is linear in the number of elements inserted and
 885        *  does not invalidate iterators and references.
 886        */
 887       void
 888       insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
 889       {
 890         forward_list __tmp(__n, __val, this->get_allocator());
 891         this->splice_after(__pos, std::move(__tmp));
 892       }
 893
 894       /**
 895        *  @brief  Inserts a range into the %forward_list.
 896        *  @param  position  An iterator into the %forward_list.
 897        *  @param  first  An input iterator.
 898        *  @param  last   An input iterator.
 899        *
 900        *  This function will insert copies of the data in the range [@a
 901        *  first,@a last) into the %forward_list after the location specified
 902        *  by @a pos.
 903        *
 904        *  This operation is linear in the number of elements inserted and
 905        *  does not invalidate iterators and references.
 906        */
 907       template<typename _InputIterator>
 908         void
 909         insert_after(const_iterator __pos,
 910                      _InputIterator __first, _InputIterator __last)
 911         {
 912           forward_list __tmp(__first, __last, this->get_allocator());
 913           this->splice_after(__pos, std::move(__tmp));
 914         }
 915
 916       /**
 917        *  @brief  Inserts the contents of an initializer_list into
 918        *          %forward_list after the specified iterator.
 919        *  @param  pos  An iterator into the %forward_list.
 920        *  @param  il  An initializer_list of value_type.
 921        *
 922        *  This function will insert copies of the data in the
 923        *  initializer_list @a il into the %forward_list before the location
 924        *  specified by @a pos.
 925        *
 926        *  This operation is linear in the number of elements inserted and
 927        *  does not invalidate iterators and references.
 928        */
 929       void
 930       insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
 931       {
 932         forward_list __tmp(__il, this->get_allocator());
 933         this->splice_after(__pos, std::move(__tmp));
 934       }
 935
 936       /**
 937        *  @brief  Removes the element pointed to by the iterator following
 938        *          @c pos.
 939        *  @param  pos  Iterator pointing to element to be erased.
 940        *  @return  An iterator pointing to the next element (or end()).
 941        *
 942        *  This function will erase the element at the given position and
 943        *  thus shorten the %forward_list by one.
 944        *
 945        *  Due to the nature of a %forward_list this operation can be done
 946        *  in constant time, and only invalidates iterators/references to
 947        *  the element being removed.  The user is also cautioned that
 948        *  this function only erases the element, and that if the element
 949        *  is itself a pointer, the pointed-to memory is not touched in
 950        *  any way.  Managing the pointer is the user's responsibility.
 951        */
 952       iterator
 953       erase_after(const_iterator __pos)
 954       {
 955         _Fwd_list_node_base* __tmp
 956           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
 957         if (__tmp)
 958           return iterator(this->_M_erase_after(__tmp));
 959         else
 960           return end();
 961       }
 962
 963       /**
 964        *  @brief  Remove a range of elements.
 965        *  @param  pos  Iterator pointing before the first element to be
 966        *               erased.
 967        *  @param  last  Iterator pointing to one past the last element to be
 968        *                erased.
 969        *  @return  An iterator pointing to the element pointed to by @a last
 970        *           prior to erasing (or end()).
 971        *
 972        *  This function will erase the elements in the range @a
 973        *  (pos,last) and shorten the %forward_list accordingly.
 974        *
 975        *  This operation is linear time in the size of the range and only
 976        *  invalidates iterators/references to the element being removed.
 977        *  The user is also cautioned that this function only erases the
 978        *  elements, and that if the elements themselves are pointers, the
 979        *  pointed-to memory is not touched in any way.  Managing the pointer
 980        *  is the user's responsibility.
 981        */
 982       iterator
 983       erase_after(const_iterator __pos, iterator __last)
 984       {
 985         _Fwd_list_node_base* __tmp
 986           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
 987         return iterator(this->_M_erase_after(__tmp, __last._M_node));
 988       }
 989
 990       /**
 991        *  @brief  Swaps data with another %forward_list.
 992        *  @param  list  A %forward_list of the same element and allocator
 993        *                types.
 994        *
 995        *  This exchanges the elements between two lists in constant
 996        *  time.  Note that the global std::swap() function is
 997        *  specialized such that std::swap(l1,l2) will feed to this
 998        *  function.
 999        */
1000       void
1001       swap(forward_list&& __list)
1002       { _Fwd_list_node_base::swap(this->_M_impl._M_head,
1003                                   __list._M_impl._M_head); }
1004
1005       /**
1006        *  @brief Resizes the %forward_list to the specified number of
1007        *         elements.
1008        *  @param sz Number of elements the %forward_list should contain.
1009        *
1010        *  This function will %resize the %forward_list to the specified
1011        *  number of elements.  If the number is smaller than the
1012        *  %forward_list's current size the %forward_list is truncated,
1013        *  otherwise the %forward_list is extended and new elements are
1014        *  populated with given data.
1015        */
1016       void
1017       resize(size_type __sz)
1018       { resize(__sz, _Tp()); }
1019
1020       /**
1021        *  @brief Resizes the %forward_list to the specified number of
1022        *         elements.
1023        *  @param sz Number of elements the %forward_list should contain.
1024        *  @param val Data with which new elements should be populated.
1025        *
1026        *  This function will %resize the %forward_list to the specified
1027        *  number of elements.  If the number is smaller than the
1028        *  %forward_list's current size the %forward_list is truncated,
1029        *  otherwise the %forward_list is extended and new elements are
1030        *  populated with given data.
1031        */
1032       void
1033       resize(size_type __sz, value_type __val);
1034
1035       /**
1036        *  @brief  Erases all the elements.
1037        *
1038        *  Note that this function only erases
1039        *  the elements, and that if the elements themselves are
1040        *  pointers, the pointed-to memory is not touched in any way.
1041        *  Managing the pointer is the user's responsibility.
1042        */
1043       void
1044       clear()
1045       { this->_M_erase_after(&this->_M_impl._M_head, 0); }
1046
1047       // 23.2.3.5 forward_list operations:
1048
1049       /**
1050        *  @brief  Insert contents of another %forward_list.
1051        *  @param  pos  Iterator referencing the element to insert after.
1052        *  @param  list  Source list.
1053        *
1054        *  The elements of @a list are inserted in constant time after
1055        *  the element referenced by @a pos.  @a list becomes an empty
1056        *  list.
1057        *
1058        *  Requires this != @a x.
1059        */
1060       void
1061       splice_after(const_iterator __pos, forward_list&& __list);
1062
1063       /**
1064        *  @brief  Insert element from another %forward_list.
1065        *  @param  pos  Iterator referencing the element to insert after.
1066        *  @param  list  Source list.
1067        *  @param  it  Iterator referencing the element before the element
1068        *              to move.
1069        *
1070        *  Removes the element in list @a list referenced by @a i and
1071        *  inserts it into the current list after @a pos.
1072        */
1073       void
1074       splice_after(const_iterator __pos, forward_list&& __list,
1075                    const_iterator __it)
1076       { this->splice_after(__pos, __list, __it, __it._M_next()); }
1077
1078       /**
1079        *  @brief  Insert range from another %forward_list.
1080        *  @param  pos  Iterator referencing the element to insert after.
1081        *  @param  list  Source list.
1082        *  @param  before  Iterator referencing before the start of range
1083        *                  in list.
1084        *  @param  last  Iterator referencing the end of range in list.
1085        *
1086        *  Removes elements in the range (before,last) and inserts them
1087        *  after @a pos in constant time.
1088        *
1089        *  Undefined if @a pos is in (before,last).
1090        */
1091       void
1092       splice_after(const_iterator __pos, forward_list&& __list,
1093                    const_iterator __before, const_iterator __last);
1094
1095       /**
1096        *  @brief  Remove all elements equal to value.
1097        *  @param  val  The value to remove.
1098        *
1099        *  Removes every element in the list equal to @a value.
1100        *  Remaining elements stay in list order.  Note that this
1101        *  function only erases the elements, and that if the elements
1102        *  themselves are pointers, the pointed-to memory is not
1103        *  touched in any way.  Managing the pointer is the user's
1104        *  responsibility.
1105        */
1106       void
1107       remove(const _Tp& __val);
1108
1109       /**
1110        *  @brief  Remove all elements satisfying a predicate.
1111        *  @param  pred  Unary predicate function or object.
1112        *
1113        *  Removes every element in the list for which the predicate
1114        *  returns true.  Remaining elements stay in list order.  Note
1115        *  that this function only erases the elements, and that if the
1116        *  elements themselves are pointers, the pointed-to memory is
1117        *  not touched in any way.  Managing the pointer is the user's
1118        *  responsibility.
1119        */
1120       template<typename _Pred>
1121         void
1122         remove_if(_Pred __pred);
1123
1124       /**
1125        *  @brief  Remove consecutive duplicate elements.
1126        *
1127        *  For each consecutive set of elements with the same value,
1128        *  remove all but the first one.  Remaining elements stay in
1129        *  list order.  Note that this function only erases the
1130        *  elements, and that if the elements themselves are pointers,
1131        *  the pointed-to memory is not touched in any way.  Managing
1132        *  the pointer is the user's responsibility.
1133        */
1134       void
1135       unique()
1136       { this->unique(std::equal_to<_Tp>()); }
1137
1138       /**
1139        *  @brief  Remove consecutive elements satisfying a predicate.
1140        *  @param  binary_pred  Binary predicate function or object.
1141        *
1142        *  For each consecutive set of elements [first,last) that
1143        *  satisfy predicate(first,i) where i is an iterator in
1144        *  [first,last), remove all but the first one.  Remaining
1145        *  elements stay in list order.  Note that this function only
1146        *  erases the elements, and that if the elements themselves are
1147        *  pointers, the pointed-to memory is not touched in any way.
1148        *  Managing the pointer is the user's responsibility.
1149        */
1150       template<typename _BinPred>
1151         void
1152         unique(_BinPred __binary_pred);
1153
1154       /**
1155        *  @brief  Merge sorted lists.
1156        *  @param  list  Sorted list to merge.
1157        *
1158        *  Assumes that both @a list and this list are sorted according to
1159        *  operator<().  Merges elements of @a list into this list in
1160        *  sorted order, leaving @a list empty when complete.  Elements in
1161        *  this list precede elements in @a list that are equal.
1162        */
1163       void
1164       merge(forward_list&& __list)
1165       { this->merge(__list, std::less<_Tp>()); }
1166
1167       /**
1168        *  @brief  Merge sorted lists according to comparison function.
1169        *  @param  list  Sorted list to merge.
1170        *  @param  comp Comparison function defining sort order.
1171        *
1172        *  Assumes that both @a list and this list are sorted according to
1173        *  comp.  Merges elements of @a list into this list
1174        *  in sorted order, leaving @a list empty when complete.  Elements
1175        *  in this list precede elements in @a list that are equivalent
1176        *  according to comp().
1177        */
1178       template<typename _Comp>
1179         void
1180         merge(forward_list&& __list, _Comp __comp);
1181
1182       /**
1183        *  @brief  Sort the elements of the list.
1184        *
1185        *  Sorts the elements of this list in NlogN time.  Equivalent
1186        *  elements remain in list order.
1187        */
1188       void
1189       sort()
1190       {
1191         _Node* __tmp = static_cast<_Node*>(&this->_M_impl._M_head);
1192         __tmp->_M_sort_after(std::less<_Tp>());
1193       }
1194
1195       /**
1196        *  @brief  Sort the forward_list using a comparison function.
1197        *
1198        *  Sorts the elements of this list in NlogN time.  Equivalent
1199        *  elements remain in list order.
1200        */
1201       template<typename _Comp>
1202         void
1203         sort(_Comp __comp)
1204         {
1205           _Node* __tmp = static_cast<_Node*>(&this->_M_impl._M_head);
1206           __tmp->_M_sort_after(__comp);
1207         }
1208
1209       /**
1210        *  @brief  Reverse the elements in list.
1211        *
1212        *  Reverse the order of elements in the list in linear time.
1213        */
1214       void
1215       reverse();
1216
1217     private:
1218       template<typename _Integer>
1219         void
1220         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1221         { _M_fill_initialize(static_cast<size_type>(__n), __x); }
1222
1223       // Called by the range constructor to implement [23.1.1]/9
1224       template<typename _InputIterator>
1225         void
1226         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1227                                __false_type);
1228
1229       // Called by forward_list(n,v,a), and the range constructor when it
1230       // turns out to be the same thing.
1231       void
1232       _M_fill_initialize(size_type __n, const value_type& __value);
1233     };
1234
1235   /**
1236    *  @brief  Forward list equality comparison.
1237    *  @param  lx  A %forward_list
1238    *  @param  ly  A %forward_list of the same type as @a lx.
1239    *  @return  True iff the size and elements of the forward lists are equal.
1240    *
1241    *  This is an equivalence relation.  It is linear in the size of the
1242    *  forward lists.  Deques are considered equivalent if corresponding
1243    *  elements compare equal.
1244    */
1245   template<typename _Tp, typename _Alloc>
1246     bool
1247     operator==(const forward_list<_Tp, _Alloc>& __lx,
1248                const forward_list<_Tp, _Alloc>& __ly);
1249
1250   /**
1251    *  @brief  Forward list ordering relation.
1252    *  @param  lx  A %forward_list.
1253    *  @param  ly  A %forward_list of the same type as @a lx.
1254    *  @return  True iff @a lx is lexicographically less than @a ly.
1255    *
1256    *  This is a total ordering relation.  It is linear in the size of the
1257    *  forward lists.  The elements must be comparable with @c <.
1258    *
1259    *  See std::lexicographical_compare() for how the determination is made.
1260    */
1261   template<typename _Tp, typename _Alloc>
1262     inline bool
1263     operator<(const forward_list<_Tp, _Alloc>& __lx,
1264               const forward_list<_Tp, _Alloc>& __ly)
1265     { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(),
1266                                           __ly.cbegin(), __ly.cend()); }
1267
1268   /// Based on operator==
1269   template<typename _Tp, typename _Alloc>
1270     inline bool
1271     operator!=(const forward_list<_Tp, _Alloc>& __lx,
1272                const forward_list<_Tp, _Alloc>& __ly)
1273     { return !(__lx == __ly); }
1274
1275   /// Based on operator<
1276   template<typename _Tp, typename _Alloc>
1277     inline bool
1278     operator>(const forward_list<_Tp, _Alloc>& __lx,
1279               const forward_list<_Tp, _Alloc>& __ly)
1280     { return (__ly < __lx); }
1281
1282   /// Based on operator<
1283   template<typename _Tp, typename _Alloc>
1284     inline bool
1285     operator>=(const forward_list<_Tp, _Alloc>& __lx,
1286                const forward_list<_Tp, _Alloc>& __ly)
1287     { return !(__lx < __ly); }
1288
1289   /// Based on operator<
1290   template<typename _Tp, typename _Alloc>
1291     inline bool
1292     operator<=(const forward_list<_Tp, _Alloc>& __lx,
1293                const forward_list<_Tp, _Alloc>& __ly)
1294     { return !(__ly < __lx); }
1295
1296   /// See std::forward_list::forward_swap().
1297   template<typename _Tp, typename _Alloc>
1298     inline void
1299     swap(forward_list<_Tp, _Alloc>& __lx,
1300          forward_list<_Tp, _Alloc>& __ly)
1301     { __lx.swap(__ly); }
1302
1303   /// See std::forward_list::forward_swap().
1304   template<typename _Tp, typename _Alloc>
1305     inline void
1306     swap(forward_list<_Tp, _Alloc>&& __lx,
1307          forward_list<_Tp, _Alloc>& __ly)
1308     { __lx.swap(__ly); }
1309
1310   /// See std::forward_list::forward_swap().
1311   template<typename _Tp, typename _Alloc>
1312     inline void
1313     swap(forward_list<_Tp, _Alloc>& __lx,
1314          forward_list<_Tp, _Alloc>&& __ly)
1315     { __lx.swap(__ly); }
1316
1317 _GLIBCXX_END_NAMESPACE // namespace std
1318
1319 #endif // __GXX_EXPERIMENTAL_CXX0X__
1320
1321 #endif // _FORWARD_LIST_H