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