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

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