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