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

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