OSDN Git Service

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