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