contrib/gcc-4.4/libstdc++-v3/include/bits/forward_list.h

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