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

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