libstdc++
forward_list.h
Go to the documentation of this file.
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  */
48  {
49  _Fwd_list_node_base() : _M_next(0) { }
50 
51  _Fwd_list_node_base* _M_next;
52 
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 
63  _M_transfer_after(_Fwd_list_node_base* __begin,
64  _Fwd_list_node_base* __end)
65  {
66  _Fwd_list_node_base* __keep = __begin->_M_next;
67  if (__end)
68  {
69  __begin->_M_next = __end->_M_next;
70  __end->_M_next = _M_next;
71  }
72  else
73  __begin->_M_next = 0;
74  _M_next = __keep;
75  return __end;
76  }
77 
78  void
79  _M_reverse_after()
80  {
81  _Fwd_list_node_base* __tail = _M_next;
82  if (!__tail)
83  return;
84  while (_Fwd_list_node_base* __temp = __tail->_M_next)
85  {
86  _Fwd_list_node_base* __keep = _M_next;
87  _M_next = __temp;
88  __tail->_M_next = __temp->_M_next;
89  _M_next->_M_next = __keep;
90  }
91  }
92  };
93 
94  /**
95  * @brief A helper node class for %forward_list.
96  * This is just a linked list with a data value in each node.
97  * There is a sorting utility method.
98  */
99  template<typename _Tp>
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>
118  {
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;
127 
129  : _M_node() { }
130 
131  explicit
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>
186  {
188  typedef const _Fwd_list_node<_Tp> _Node;
190 
191  typedef _Tp value_type;
192  typedef const _Tp* pointer;
193  typedef const _Tp& reference;
194  typedef ptrdiff_t difference_type;
196 
198  : _M_node() { }
199 
200  explicit
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,
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,
267  { return __x._M_node != __y._M_node; }
268 
269  /**
270  * @brief Base class for %forward_list.
271  */
272  template<typename _Tp, typename _Alloc>
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:
300  typedef _Fwd_list_node<_Tp> _Node;
301 
302  _Node_alloc_type&
303  _M_get_Node_allocator()
304  { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
305 
306  const _Node_alloc_type&
307  _M_get_Node_allocator() const
308  { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
309 
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 
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>
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 
369  _M_erase_after(_Fwd_list_node_base* __pos);
370 
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:
412  typedef _Fwd_list_node<_Tp> _Node;
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 
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  */
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  */
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  */
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&
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&
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
640  {
641  clear();
642  insert_after(cbefore_begin(), __il);
643  }
644 
645  /// Get a copy of the memory allocation object.
646  allocator_type
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
658  { return iterator(&this->_M_impl._M_head); }
659 
660  /**
661  * Returns a read-only (constant) iterator that points before the
662  * first element in the %forward_list. Iteration is done in ordinary
663  * element order.
664  */
665  const_iterator
666  before_begin() const
667  { return const_iterator(&this->_M_impl._M_head); }
668 
669  /**
670  * Returns a read/write iterator that points to the first element
671  * in the %forward_list. Iteration is done in ordinary element order.
672  */
673  iterator
675  { return iterator(this->_M_impl._M_head._M_next); }
676 
677  /**
678  * Returns a read-only (constant) iterator that points to the first
679  * element in the %forward_list. Iteration is done in ordinary
680  * element order.
681  */
682  const_iterator
683  begin() const
684  { return const_iterator(this->_M_impl._M_head._M_next); }
685 
686  /**
687  * Returns a read/write iterator that points one past the last
688  * element in the %forward_list. Iteration is done in ordinary
689  * element order.
690  */
691  iterator
692  end()
693  { return iterator(0); }
694 
695  /**
696  * Returns a read-only iterator that points one past the last
697  * element in the %forward_list. Iteration is done in ordinary
698  * element order.
699  */
700  const_iterator
701  end() const
702  { return const_iterator(0); }
703 
704  /**
705  * Returns a read-only (constant) iterator that points to the
706  * first element in the %forward_list. Iteration is done in ordinary
707  * element order.
708  */
709  const_iterator
710  cbegin() const
711  { return const_iterator(this->_M_impl._M_head._M_next); }
712 
713  /**
714  * Returns a read-only (constant) iterator that points before the
715  * first element in the %forward_list. Iteration is done in ordinary
716  * element order.
717  */
718  const_iterator
720  { return const_iterator(&this->_M_impl._M_head); }
721 
722  /**
723  * Returns a read-only (constant) iterator that points one past
724  * the last element in the %forward_list. Iteration is done in
725  * ordinary element order.
726  */
727  const_iterator
728  cend() const
729  { return const_iterator(0); }
730 
731  /**
732  * Returns true if the %forward_list is empty. (Thus begin() would
733  * equal end().)
734  */
735  bool
736  empty() const
737  { return this->_M_impl._M_head._M_next == 0; }
738 
739  /**
740  * Returns the largest possible size of %forward_list.
741  */
742  size_type
743  max_size() const
744  { return this->_M_get_Node_allocator().max_size(); }
745 
746  // 23.2.3.3 element access:
747 
748  /**
749  * Returns a read/write reference to the data at the first
750  * element of the %forward_list.
751  */
752  reference
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
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
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
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
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
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
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
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
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
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
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
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
1298  { __lx.swap(__ly); }
1299 
1300 _GLIBCXX_END_NAMESPACE_CONTAINER
1301 } // namespace std
1302 
1303 #endif // _FORWARD_LIST_H