libstdc++
forward_list.h
Go to the documentation of this file.
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  */
50  {
51  _Fwd_list_node_base() : _M_next(0) { }
52 
53  _Fwd_list_node_base* _M_next;
54 
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>
94  : public _Fwd_list_node_base
95  {
96  template<typename... _Args>
97  _Fwd_list_node(_Args&&... __args)
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>
111  {
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;
120 
122  : _M_node() { }
123 
124  explicit
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>
179  {
181  typedef const _Fwd_list_node<_Tp> _Node;
183 
184  typedef _Tp value_type;
185  typedef const _Tp* pointer;
186  typedef const _Tp& reference;
187  typedef ptrdiff_t difference_type;
189 
191  : _M_node() { }
192 
193  explicit
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,
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,
260  { return __x._M_node != __y._M_node; }
261 
262  /**
263  * @brief Base class for %forward_list.
264  */
265  template<typename _Tp, typename _Alloc>
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:
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 
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 
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>
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 
366  _M_erase_after(_Fwd_list_node_base* __pos);
367 
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:
409  typedef _Fwd_list_node<_Tp> _Node;
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 
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  */
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&
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&
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
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
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
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
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
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
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
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
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
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
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
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
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
1315  { __lx.swap(__ly); }
1316 
1317 _GLIBCXX_END_NAMESPACE_CONTAINER
1318 } // namespace std
1319 
1320 #endif // _FORWARD_LIST_H