libstdc++
forward_list.h
Go to the documentation of this file.
1 // <forward_list.h> -*- C++ -*-
2 
3 // Copyright (C) 2008-2025 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 #ifdef _GLIBCXX_SYSHDR
34 #pragma GCC system_header
35 #endif
36 
37 #include <initializer_list>
39 #include <bits/stl_iterator.h>
40 #include <bits/stl_algobase.h>
41 #include <bits/stl_function.h>
42 #include <bits/allocator.h>
43 #include <bits/allocated_ptr.h>
44 #include <bits/ptr_traits.h>
45 #include <debug/assertions.h>
46 #include <ext/alloc_traits.h>
47 #include <ext/aligned_buffer.h>
48 #include <debug/assertions.h>
49 #if __glibcxx_containers_ranges // C++ >= 23
50 # include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
51 # include <bits/ranges_util.h> // ranges::subrange
52 #endif
53 
54 #if ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
55 # define _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 1
56 #endif
57 
58 namespace std _GLIBCXX_VISIBILITY(default)
59 {
60 _GLIBCXX_BEGIN_NAMESPACE_VERSION
61 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
62 
63  /**
64  * @brief A helper basic node class for %forward_list.
65  *
66  * This is just a linked list with nothing inside it.
67  * There are purely list shuffling utility methods here.
68  */
70  {
72 
73  _Fwd_list_node_base() = default;
75  : _M_next(__x._M_next)
76  { __x._M_next = nullptr; }
77 
79  _Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete;
80 
82  operator=(_Fwd_list_node_base&& __x) noexcept
83  {
84  _M_next = __x._M_next;
85  __x._M_next = nullptr;
86  return *this;
87  }
88 
89  _Fwd_list_node_base* _M_next = nullptr;
90 
92  _M_transfer_after(_Fwd_list_node_base* __begin,
93  _Fwd_list_node_base* __end) noexcept
94  {
95  _Fwd_list_node_base* __keep = __begin->_M_next;
96  if (__end)
97  {
98  __begin->_M_next = __end->_M_next;
99  __end->_M_next = _M_next;
100  }
101  else
102  __begin->_M_next = nullptr;
103  _M_next = __keep;
104  return __end;
105  }
106 
107  void
108  _M_reverse_after() noexcept
109  {
110  _Fwd_list_node_base* __tail = _M_next;
111  if (!__tail)
112  return;
113  while (_Fwd_list_node_base* __temp = __tail->_M_next)
114  {
115  _Fwd_list_node_base* __keep = _M_next;
116  _M_next = __temp;
117  __tail->_M_next = __temp->_M_next;
118  _M_next->_M_next = __keep;
119  }
120  }
121 
122  _Fwd_list_node_base* _M_base_ptr() { return this; }
123  const _Fwd_list_node_base* _M_base_ptr() const { return this; }
124  };
125 
126  /**
127  * @brief A helper node class for %forward_list.
128  * This is just a linked list with uninitialized storage for a
129  * data value in each node.
130  * There is a sorting utility method.
131  */
132  template<typename _Tp>
134  : public _Fwd_list_node_base
135  {
136  using _Node_ptr = _Fwd_list_node*;
137 
138  _Fwd_list_node() = default;
139 
140  __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
141 
142  _Tp*
143  _M_valptr() noexcept
144  { return _M_storage._M_ptr(); }
145 
146  const _Tp*
147  _M_valptr() const noexcept
148  { return _M_storage._M_ptr(); }
149 
150  _Node_ptr
151  _M_node_ptr()
152  { return this; }
153  };
154 
155  template<typename _Tp> struct _Fwd_list_const_iterator;
156 
157  /**
158  * @brief A forward_list::iterator.
159  *
160  * All the functions are op overloads.
161  */
162  template<typename _Tp>
164  {
166  typedef _Fwd_list_node<_Tp> _Node;
167 
168  typedef _Tp value_type;
169  typedef _Tp* pointer;
170  typedef _Tp& reference;
171  typedef ptrdiff_t difference_type;
173 
174  _Fwd_list_iterator() noexcept
175  : _M_node() { }
176 
177  explicit
179  : _M_node(__n) { }
180 
181  [[__nodiscard__]]
182  reference
183  operator*() const noexcept
184  { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
185 
186  [[__nodiscard__]]
187  pointer
188  operator->() const noexcept
189  { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
190 
191  _Self&
192  operator++() noexcept
193  {
194  _M_node = _M_node->_M_next;
195  return *this;
196  }
197 
198  _Self
199  operator++(int) noexcept
200  {
201  _Self __tmp(*this);
202  _M_node = _M_node->_M_next;
203  return __tmp;
204  }
205 
206  /**
207  * @brief Forward list iterator equality comparison.
208  */
209  [[__nodiscard__]]
210  friend bool
211  operator==(const _Self& __x, const _Self& __y) noexcept
212  { return __x._M_node == __y._M_node; }
213 
214 #if __cpp_impl_three_way_comparison < 201907L
215  /**
216  * @brief Forward list iterator inequality comparison.
217  */
218  [[__nodiscard__]]
219  friend bool
220  operator!=(const _Self& __x, const _Self& __y) noexcept
221  { return __x._M_node != __y._M_node; }
222 #endif
223 
224  private:
225  template<typename, typename>
226  friend class forward_list;
227  template<typename, typename>
228  friend struct _Fwd_list_base;
229  friend struct _Fwd_list_const_iterator<_Tp>;
230 
231  _Self
232  _M_next() const noexcept
233  {
234  if (_M_node)
235  return _Fwd_list_iterator(_M_node->_M_next);
236  else
237  return _Fwd_list_iterator(nullptr);
238  }
239 
240  _Fwd_list_node_base* _M_node;
241  };
242 
243  /**
244  * @brief A forward_list::const_iterator.
245  *
246  * All the functions are op overloads.
247  */
248  template<typename _Tp>
250  {
252  typedef const _Fwd_list_node<_Tp> _Node;
254 
255  typedef _Tp value_type;
256  typedef const _Tp* pointer;
257  typedef const _Tp& reference;
258  typedef ptrdiff_t difference_type;
260 
261  _Fwd_list_const_iterator() noexcept
262  : _M_node() { }
263 
264  explicit
265  _Fwd_list_const_iterator(const _Fwd_list_node_base* __n) noexcept
266  : _M_node(__n) { }
267 
268  _Fwd_list_const_iterator(const iterator& __iter) noexcept
269  : _M_node(__iter._M_node) { }
270 
271  [[__nodiscard__]]
272  reference
273  operator*() const noexcept
274  { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
275 
276  [[__nodiscard__]]
277  pointer
278  operator->() const noexcept
279  { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
280 
281  _Self&
282  operator++() noexcept
283  {
284  _M_node = _M_node->_M_next;
285  return *this;
286  }
287 
288  _Self
289  operator++(int) noexcept
290  {
291  _Self __tmp(*this);
292  _M_node = _M_node->_M_next;
293  return __tmp;
294  }
295 
296  /**
297  * @brief Forward list const_iterator equality comparison.
298  */
299  [[__nodiscard__]]
300  friend bool
301  operator==(const _Self& __x, const _Self& __y) noexcept
302  { return __x._M_node == __y._M_node; }
303 
304 #if __cpp_impl_three_way_comparison < 201907L
305  /**
306  * @brief Forward list const_iterator inequality comparison.
307  */
308  [[__nodiscard__]]
309  friend bool
310  operator!=(const _Self& __x, const _Self& __y) noexcept
311  { return __x._M_node != __y._M_node; }
312 #endif
313 
314  private:
315  template<typename, typename>
316  friend class forward_list;
317  template<typename, typename>
318  friend struct _Fwd_list_base;
319 
320  _Self
321  _M_next() const noexcept
322  {
323  if (this->_M_node)
324  return _Fwd_list_const_iterator(_M_node->_M_next);
325  else
326  return _Fwd_list_const_iterator(nullptr);
327  }
328 
329  _Fwd_list_iterator<_Tp>
330  _M_const_cast() const noexcept
331  {
332  return _Fwd_list_iterator<_Tp>(
333  const_cast<_Fwd_list_node_base*>(_M_node));
334  }
335 
336  const _Fwd_list_node_base* _M_node;
337  };
338 
339  template<typename _Tp, typename _Allocator> class forward_list;
340  template<typename _Tp, typename _Allocator> struct _Fwd_list_base;
341 
342 namespace __fwdlist
343 {
344 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
345  /// The node-base type for allocators that use fancy pointers.
346  template<typename _VoidPtr>
347  struct _Node_base
348  {
349  using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
350 
351  _Node_base() = default;
352 
353  _Node_base(_Node_base&& __x) noexcept
354  : _M_next(__x._M_next)
355  { __x._M_next = nullptr; }
356 
357  _Node_base(const _Node_base&) = delete;
358  _Node_base& operator=(const _Node_base&) = delete;
359 
360  _Node_base&
361  operator=(_Node_base&& __x) noexcept
362  {
363  _M_next = __x._M_next;
364  __x._M_next = nullptr;
365  return *this;
366  }
367 
368  _Base_ptr _M_next = nullptr;
369 
370  // Splice (begin,end) before _M_next.
371  _Base_ptr
372  _M_transfer_after(_Base_ptr __begin, _Base_ptr __end) noexcept
373  {
374  _Base_ptr __keep = __begin->_M_next;
375  if (__end)
376  {
377  __begin->_M_next = __end->_M_next;
378  __end->_M_next = _M_next;
379  }
380  else
381  __begin->_M_next = nullptr;
382  _M_next = __keep;
383  return __end;
384  }
385 
386  void
387  _M_reverse_after() noexcept
388  {
389  _Base_ptr __tail = _M_next;
390  if (!__tail)
391  return;
392  while (_Base_ptr __temp = __tail->_M_next)
393  {
394  _Base_ptr __keep = _M_next;
395  _M_next = __temp;
396  __tail->_M_next = __temp->_M_next;
397  _M_next->_M_next = __keep;
398  }
399  }
400 
401  // This is not const-correct, but it's only used in a const access path
402  // by std::forward_list::empty(), where it doesn't escape, and by
403  // std::forward_list::before_begin() const, where the pointer is used
404  // to initialize a const_iterator and so constness is restored.
405  _Base_ptr
406  _M_base_ptr() const
407  {
409  pointer_to(const_cast<_Node_base&>(*this));
410  }
411  };
412 
413  /**
414  * @brief A helper node class for %forward_list.
415  */
416  template<typename _ValPtr>
417  struct _Node
418  : public _Node_base<__ptr_rebind<_ValPtr, void>>
419  {
420  using value_type = typename pointer_traits<_ValPtr>::element_type;
421  using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
422 
423  _Node() noexcept { }
424  ~_Node() { }
425  _Node(_Node&&) = delete;
426 
427  union _Uninit_storage
428  {
429  _Uninit_storage() noexcept { }
430  ~_Uninit_storage() { }
431 
432 #if ! _GLIBCXX_INLINE_VERSION
433  // For ABI compatibility we need to overalign this member.
434  alignas(__alignof__(value_type)) // XXX GLIBCXX_ABI Deprecated
435 #endif
436  value_type _M_data;
437  };
438  _Uninit_storage _M_u;
439 
440  value_type*
441  _M_valptr() noexcept
442  { return std::__addressof(_M_u._M_data); }
443 
444  const value_type*
445  _M_valptr() const noexcept
446  { return std::__addressof(_M_u._M_data); }
447 
448  _Node_ptr
449  _M_node_ptr()
450  { return pointer_traits<_Node_ptr>::pointer_to(*this); }
451  };
452 
453  /// A forward_list iterator when the allocator uses fancy pointers.
454  template<bool _Const, typename _Ptr>
455  class _Iterator
456  {
458  using _Base_ptr
459  = typename __fwdlist::_Node_base<__ptr_rebind<_Ptr, void>>::_Base_ptr;
460 
461  template<typename _Tp>
462  using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
463 
464  public:
465  using value_type = typename pointer_traits<_Ptr>::element_type;
466  using difference_type = ptrdiff_t;
468  using pointer = __maybe_const<value_type>*;
469  using reference = __maybe_const<value_type>&;
470 
471  constexpr _Iterator() noexcept : _M_node() { }
472 
473  _Iterator(const _Iterator&) = default;
474  _Iterator& operator=(const _Iterator&) = default;
475 
476 #ifdef __glibcxx_concepts
477  constexpr
478  _Iterator(const _Iterator<false, _Ptr>& __i) requires _Const
479 #else
480  template<bool _OtherConst,
481  typename = __enable_if_t<_Const && !_OtherConst>>
482  constexpr
484 #endif
485  : _M_node(__i._M_node) { }
486 
487  constexpr explicit
488  _Iterator(_Base_ptr __x) noexcept
489  : _M_node(__x) { }
490 
491  [[__nodiscard__]]
492  constexpr reference
493  operator*() const noexcept
494  { return static_cast<_Node&>(*this->_M_node)._M_u._M_data; }
495 
496  [[__nodiscard__]]
497  constexpr pointer
498  operator->() const noexcept
499  { return static_cast<_Node&>(*this->_M_node)._M_valptr(); }
500 
501  _GLIBCXX14_CONSTEXPR _Iterator&
502  operator++() noexcept
503  {
504  _M_node = _M_node->_M_next;
505  return *this;
506  }
507 
508  _GLIBCXX14_CONSTEXPR _Iterator
509  operator++(int) noexcept
510  {
511  _Iterator __tmp(*this);
512  _M_node = _M_node->_M_next;
513  return __tmp;
514  }
515 
516  /**
517  * @brief Forward list iterator equality comparison.
518  */
519  [[__nodiscard__]]
520  friend constexpr bool
521  operator==(const _Iterator& __x, const _Iterator& __y) noexcept
522  { return __x._M_node == __y._M_node; }
523 
524 #if __cpp_impl_three_way_comparison < 201907L
525  /**
526  * @brief Forward list iterator inequality comparison.
527  */
528  [[__nodiscard__]]
529  friend constexpr bool
530  operator!=(const _Iterator& __x, const _Iterator& __y) noexcept
531  { return __x._M_node != __y._M_node; }
532 #endif
533 
534  private:
535  template<typename _Tp, typename _Allocator>
536  friend class _GLIBCXX_STD_C::forward_list;
537  template<typename _Tp, typename _Allocator>
538  friend struct _GLIBCXX_STD_C::_Fwd_list_base;
539 
540  constexpr _Iterator<false, _Ptr>
541  _M_const_cast() const noexcept
542  { return _Iterator<false, _Ptr>(_M_node); }
543 
544  friend _Iterator<!_Const, _Ptr>;
545 
546  constexpr _Iterator
547  _M_next() const noexcept
548  { return _Iterator(_M_node ? _M_node->_M_next : nullptr); }
549 
550  _Base_ptr _M_node;
551  };
552 #endif // USE_ALLOC_PTR_FOR_FWD_LIST
553 
554  // Determine the node and iterator types used by std::forward_list.
555  template<typename _Tp, typename _Ptr>
556  struct _Node_traits;
557 
558 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST <= 9000
559  // Specialization for the simple case where the allocator's pointer type
560  // is the same type as value_type*.
561  // For ABI compatibility we can't change the types used for this case.
562  template<typename _Tp>
563  struct _Node_traits<_Tp, _Tp*>
564  {
565  using _Node_base = _Fwd_list_node_base;
566  using _Node = _Fwd_list_node<_Tp>;
567  using _Iterator = _Fwd_list_iterator<_Tp>;
568  using _Const_iterator = _Fwd_list_const_iterator<_Tp>;
569  };
570 #endif
571 
572 #if ! _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
573  // Always use the T* specialization.
574  template<typename _Tp, typename _Ptr>
575  struct _Node_traits
576  : _Node_traits<_Tp, _Tp*>
577  { };
578 #else
579  // Primary template used when the allocator uses fancy pointers.
580  template<typename _Tp, typename _Ptr>
581  struct _Node_traits
582  {
583  private:
584  using _VoidPtr = __ptr_rebind<_Ptr, void>;
585  using _ValPtr = __ptr_rebind<_Ptr, _Tp>;
586 
587  public:
588  using _Node_base = __fwdlist::_Node_base<_VoidPtr>;
589  using _Node = __fwdlist::_Node<_ValPtr>;
590  using _Iterator = __fwdlist::_Iterator<false, _ValPtr>;
591  using _Const_iterator = __fwdlist::_Iterator<true, _ValPtr>;
592  };
593 #endif // USE_ALLOC_PTR_FOR_FWD_LIST
594 } // namespace __fwdlist
595 
596  /**
597  * @brief Base class for %forward_list.
598  */
599  template<typename _Tp, typename _Alloc>
601  {
602 #if __cplusplus > 201703L || defined __STRICT_ANSI__
603  // The static_assert in forward_list ensures _Alloc::value_type is _Tp.
604  using pointer = typename allocator_traits<_Alloc>::pointer;
605 #else
606  using _Tp_alloc_traits
607  = typename allocator_traits<_Alloc>::template rebind_traits<_Tp>;
608  using pointer = typename _Tp_alloc_traits::pointer;
609 #endif
610 
611  protected:
612  using _Node_traits = __fwdlist::_Node_traits<_Tp, pointer>;
613  using _Node = typename _Node_traits::_Node;
614  using _Node_alloc_type = __alloc_rebind<_Alloc, _Node>;
616  using _Node_ptr = typename _Node_alloc_traits::pointer;
617  using _Base_ptr = typename _Node_traits::_Node_base::_Base_ptr;
618 
619  struct _Fwd_list_impl
620  : public _Node_alloc_type
621  {
622  typename _Node_traits::_Node_base _M_head;
623 
624  _Fwd_list_impl()
626  : _Node_alloc_type(), _M_head()
627  { }
628 
629  _Fwd_list_impl(_Fwd_list_impl&&) = default;
630 
631  _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a)
632  : _Node_alloc_type(std::move(__a)), _M_head(std::move(__fl._M_head))
633  { }
634 
635  _Fwd_list_impl(_Node_alloc_type&& __a)
636  : _Node_alloc_type(std::move(__a)), _M_head()
637  { }
638  };
639 
640  _Fwd_list_impl _M_impl;
641 
642  public:
643  using iterator = typename _Node_traits::_Iterator;
644  using const_iterator = typename _Node_traits::_Const_iterator;
645 
646  _Node_alloc_type&
647  _M_get_Node_allocator() noexcept
648  { return this->_M_impl; }
649 
650  const _Node_alloc_type&
651  _M_get_Node_allocator() const noexcept
652  { return this->_M_impl; }
653 
654  _Fwd_list_base() = default;
655 
656  _Fwd_list_base(_Node_alloc_type&& __a)
657  : _M_impl(std::move(__a)) { }
658 
659  // When allocators are always equal.
660  _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a,
662  : _M_impl(std::move(__lst._M_impl), std::move(__a))
663  { }
664 
665  // When allocators are not always equal.
666  _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a);
667 
668  _Fwd_list_base(_Fwd_list_base&&) = default;
669 
670  ~_Fwd_list_base()
671  { _M_erase_after(_M_impl._M_head._M_base_ptr(), nullptr); }
672 
673  protected:
674 #if ! _GLIBCXX_INLINE_VERSION
675  // XXX GLIBCXX_ABI Deprecated
676  _Node*
677  _M_get_node()
678  {
679  auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
680  return std::__to_address(__ptr);
681  }
682 #endif
683 
684  void
685  _M_put_node(_Node_ptr __p)
686  {
687 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
688  _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);
689 #else
690  typedef typename _Node_alloc_traits::pointer _Ptr;
691  auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__p);
692  _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ptr, 1);
693 #endif
694  }
695 
696  template<typename... _Args>
697  _Node_ptr
698  _M_create_node(_Args&&... __args)
699  {
700  auto& __alloc = _M_get_Node_allocator();
701  auto __guard = std::__allocate_guarded_obj(__alloc);
702  _Node_alloc_traits::construct(__alloc, __guard->_M_valptr(),
703  std::forward<_Args>(__args)...);
704  auto __p = __guard.release();
705 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
706  return __p;
707 #else
708  return std::__to_address(__p);
709 #endif
710  }
711 
712 #pragma GCC diagnostic push
713 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
714  void
715  _M_destroy_node(_Node_ptr __p)
716  {
717  auto& __alloc = _M_get_Node_allocator();
718  // Destroy the element
719  _Node_alloc_traits::destroy(__alloc, __p->_M_valptr());
720  // Only destroy the node if the pointers require it.
722  __p->~_Node();
723  _M_put_node(__p);
724  }
725 #pragma GCC diagnostic pop
726 
727  template<typename... _Args>
728  _Base_ptr
729  _M_insert_after(const_iterator __pos, _Args&&... __args);
730 
731  _Base_ptr
732  _M_erase_after(_Base_ptr __pos);
733 
734  _Base_ptr
735  _M_erase_after(_Base_ptr __pos, _Base_ptr __last);
736  };
737 
738  /**
739  * @brief A standard container with linear time access to elements,
740  * and fixed time insertion/deletion at any point in the sequence.
741  *
742  * @ingroup sequences
743  * @headerfile forward_list
744  * @since C++11
745  *
746  * @tparam _Tp Type of element.
747  * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
748  *
749  * Meets the requirements of a <a href="tables.html#65">container</a>, a
750  * <a href="tables.html#67">sequence</a>, including the
751  * <a href="tables.html#68">optional sequence requirements</a> with the
752  * %exception of `at` and `operator[]`.
753  *
754  * This is a @e singly @e linked %list. Traversal up the
755  * %list requires linear time, but adding and removing elements (or
756  * @e nodes) is done in constant time, regardless of where the
757  * change takes place. Unlike std::vector and std::deque,
758  * random-access iterators are not provided, so subscripting (`[]`)
759  * access is not allowed. For algorithms which only need
760  * sequential access, this lack makes no difference.
761  *
762  * Also unlike the other standard containers, std::forward_list provides
763  * specialized algorithms %unique to linked lists, such as
764  * splicing, sorting, and in-place reversal.
765  */
766  template<typename _Tp, typename _Alloc = allocator<_Tp>>
767  class forward_list : private _Fwd_list_base<_Tp, _Alloc>
768  {
769  static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
770  "std::forward_list must have a non-const, non-volatile value_type");
771 #if __cplusplus > 201703L || defined __STRICT_ANSI__
773  "std::forward_list must have the same value_type as its allocator");
774 #endif
775 
776  private:
779  typedef typename _Base::_Node _Node;
780  typedef typename _Base::_Node_alloc_type _Node_alloc_type;
783 
784  public:
785  // types:
786  typedef _Tp value_type;
787  typedef typename _Alloc_traits::pointer pointer;
788  typedef typename _Alloc_traits::const_pointer const_pointer;
789  typedef value_type& reference;
790  typedef const value_type& const_reference;
791 
792  typedef typename _Base::iterator iterator;
793  typedef typename _Base::const_iterator const_iterator;
794  typedef std::size_t size_type;
795  typedef std::ptrdiff_t difference_type;
796  typedef _Alloc allocator_type;
797 
798  // 23.3.4.2 construct/copy/destroy:
799 
800  /**
801  * @brief Creates a %forward_list with no elements.
802  */
803  forward_list() = default;
804 
805  /**
806  * @brief Creates a %forward_list with no elements.
807  * @param __al An allocator object.
808  */
809  explicit
810  forward_list(const _Alloc& __al) noexcept
811  : _Base(_Node_alloc_type(__al))
812  { }
813 
814  /**
815  * @brief Copy constructor with allocator argument.
816  * @param __list Input list to copy.
817  * @param __al An allocator object.
818  */
819  forward_list(const forward_list& __list,
820  const __type_identity_t<_Alloc>& __al)
821  : _Base(_Node_alloc_type(__al))
822  { _M_range_initialize(__list.begin(), __list.end()); }
823 
824  private:
825  forward_list(forward_list&& __list, _Node_alloc_type&& __al,
826  false_type)
827  : _Base(std::move(__list), std::move(__al))
828  {
829  // If __list is not empty it means its allocator is not equal to __a,
830  // so we need to move from each element individually.
832  std::__make_move_if_noexcept_iterator(__list.begin()),
833  std::__make_move_if_noexcept_iterator(__list.end()));
834  }
835 
836  forward_list(forward_list&& __list, _Node_alloc_type&& __al,
837  true_type)
838  noexcept
839  : _Base(std::move(__list), _Node_alloc_type(__al), true_type{})
840  { }
841 
842  public:
843  /**
844  * @brief Move constructor with allocator argument.
845  * @param __list Input list to move.
846  * @param __al An allocator object.
847  */
849  const __type_identity_t<_Alloc>& __al)
850  noexcept(_Node_alloc_traits::_S_always_equal())
851  : forward_list(std::move(__list), _Node_alloc_type(__al),
852  typename _Node_alloc_traits::is_always_equal{})
853  { }
854 
855  /**
856  * @brief Creates a %forward_list with default constructed elements.
857  * @param __n The number of elements to initially create.
858  * @param __al An allocator object.
859  *
860  * This constructor creates the %forward_list with `__n` default
861  * constructed elements.
862  */
863  explicit
864  forward_list(size_type __n, const _Alloc& __al = _Alloc())
865  : _Base(_Node_alloc_type(__al))
866  { _M_default_initialize(__n); }
867 
868  /**
869  * @brief Creates a %forward_list with copies of an exemplar element.
870  * @param __n The number of elements to initially create.
871  * @param __value An element to copy.
872  * @param __al An allocator object.
873  *
874  * This constructor fills the %forward_list with `__n` copies of
875  * `__value`.
876  */
877  forward_list(size_type __n, const _Tp& __value,
878  const _Alloc& __al = _Alloc())
879  : _Base(_Node_alloc_type(__al))
880  { _M_fill_initialize(__n, __value); }
881 
882  /**
883  * @brief Builds a %forward_list from a range.
884  * @param __first An input iterator.
885  * @param __last An input iterator.
886  * @param __al An allocator object.
887  *
888  * Create a %forward_list consisting of copies of the elements from
889  * `[__first,__last)`. This is linear in N (where N is
890  * `distance(__first,__last)`).
891  */
892  template<typename _InputIterator,
893  typename = std::_RequireInputIter<_InputIterator>>
894  forward_list(_InputIterator __first, _InputIterator __last,
895  const _Alloc& __al = _Alloc())
896  : _Base(_Node_alloc_type(__al))
897  { _M_range_initialize(__first, __last); }
898 
899 #if __glibcxx_containers_ranges // C++ >= 23
900  /**
901  * @brief Construct a forward_list from a range.
902  * @param __rg An input range with elements that are convertible to
903  * the forward_list's value_type.
904  * @param __a An allocator.
905  *
906  * @since C++23
907  */
908  template<__detail::__container_compatible_range<_Tp> _Rg>
909  forward_list(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
910  : _Base(_Node_alloc_type(__a))
911  {
912  auto __to = this->_M_impl._M_head._M_base_ptr();
913  auto __first = ranges::begin(__rg);
914  const auto __last = ranges::end(__rg);
915  for (; __first != __last; ++__first)
916  {
917  __to->_M_next = this->_M_create_node(*__first)->_M_base_ptr();
918  __to = __to->_M_next;
919  }
920  }
921 #endif // containers_ranges
922 
923  /**
924  * @brief The %forward_list copy constructor.
925  * @param __list A %forward_list of identical element and allocator
926  * types.
927  */
928  forward_list(const forward_list& __list)
929  : _Base(_Node_alloc_traits::_S_select_on_copy(
930  __list._M_get_Node_allocator()))
931  { _M_range_initialize(__list.begin(), __list.end()); }
932 
933  /**
934  * @brief The %forward_list move constructor.
935  * @param __list A %forward_list of identical element and allocator
936  * types.
937  *
938  * The newly-created %forward_list contains the exact contents of the
939  * moved instance. The contents of the moved instance are a valid, but
940  * unspecified %forward_list.
941  */
943 
944  /**
945  * @brief Builds a %forward_list from an initializer_list
946  * @param __il An initializer_list of value_type.
947  * @param __al An allocator object.
948  *
949  * Create a %forward_list consisting of copies of the elements
950  * in the initializer_list `__il`. This is linear in `__il.size()`.
951  */
953  const _Alloc& __al = _Alloc())
954  : _Base(_Node_alloc_type(__al))
955  { _M_range_initialize(__il.begin(), __il.end()); }
956 
957  /**
958  * @brief The forward_list dtor.
959  */
960  ~forward_list() noexcept
961  { }
962 
963  /**
964  * @brief The %forward_list assignment operator.
965  * @param __list A %forward_list of identical element and allocator
966  * types.
967  *
968  * All the elements of `__list` are copied.
969  *
970  * Whether the allocator is copied depends on the allocator traits.
971  */
972  forward_list&
973  operator=(const forward_list& __list);
974 
975 #pragma GCC diagnostic push
976 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
977  /**
978  * @brief The %forward_list move assignment operator.
979  * @param __list A %forward_list of identical element and allocator
980  * types.
981  *
982  * The contents of `__list` are moved into this %forward_list
983  * (without copying, if the allocators permit it).
984  *
985  * Afterwards @a __list is a valid, but unspecified %forward_list
986  *
987  * Whether the allocator is moved depends on the allocator traits.
988  */
989  forward_list&
991  noexcept(_Node_alloc_traits::_S_nothrow_move())
992  {
993  constexpr bool __move_storage =
994  _Node_alloc_traits::_S_propagate_on_move_assign()
995  || _Node_alloc_traits::_S_always_equal();
996  if constexpr (!__move_storage)
997  {
998  if (__list._M_get_Node_allocator() != this->_M_get_Node_allocator())
999  {
1000  // The rvalue's allocator cannot be moved, or is not equal,
1001  // so we need to individually move each element.
1002  this->assign(std::make_move_iterator(__list.begin()),
1003  std::make_move_iterator(__list.end()));
1004  return *this;
1005  }
1006  }
1007 
1008  clear();
1009  this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
1010  __list._M_impl._M_head._M_next = nullptr;
1011  if constexpr (_Node_alloc_traits::_S_propagate_on_move_assign())
1012  this->_M_get_Node_allocator()
1013  = std::move(__list._M_get_Node_allocator());
1014  return *this;
1015  }
1016 
1017  /**
1018  * @brief The %forward_list initializer list assignment operator.
1019  * @param __il An initializer_list of value_type.
1020  *
1021  * Replace the contents of the %forward_list with copies of the
1022  * elements in the initializer_list `__il`. This is linear in
1023  * `__il.size()`.
1024  */
1025  forward_list&
1027  {
1028  assign(__il);
1029  return *this;
1030  }
1031 
1032  /**
1033  * @brief Assigns a range to a %forward_list.
1034  * @param __first An input iterator.
1035  * @param __last An input iterator.
1036  *
1037  * This function fills a %forward_list with copies of the elements
1038  * in the range `[ __first,__last)`.
1039  *
1040  * Note that the assignment completely changes the %forward_list and
1041  * that the number of elements of the resulting %forward_list is the
1042  * same as the number of elements assigned.
1043  */
1044  template<typename _InputIterator,
1045  typename = std::_RequireInputIter<_InputIterator>>
1046  void
1047  assign(_InputIterator __first, _InputIterator __last)
1048  {
1049  if constexpr (is_assignable<_Tp, decltype(*__first)>::value)
1050  {
1051  auto __prev = before_begin();
1052  auto __curr = begin();
1053  auto __end = end();
1054  while (__curr != __end && __first != __last)
1055  {
1056  *__curr = *__first;
1057  ++__prev;
1058  ++__curr;
1059  ++__first;
1060  }
1061  if (__first != __last)
1062  insert_after(__prev, __first, __last);
1063  else if (__curr != __end)
1064  erase_after(__prev, __end);
1065  }
1066  else
1067  {
1068  clear();
1069  insert_after(cbefore_begin(), __first, __last);
1070  }
1071  }
1072 #pragma GCC diagnostic pop
1073 
1074 #if __glibcxx_containers_ranges // C++ >= 23
1075  /**
1076  * @brief Assign a range to a forward_list.
1077  * @since C++23
1078  */
1079  template<__detail::__container_compatible_range<_Tp> _Rg>
1080  void
1081  assign_range(_Rg&& __rg)
1082  {
1083  static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
1084 
1085  auto __first = ranges::begin(__rg);
1086  const auto __last = ranges::end(__rg);
1087  iterator __prev = before_begin();
1088  iterator __curr = begin();
1089  const iterator __end = end();
1090 
1091  while (__curr != __end && __first != __last)
1092  {
1093  *__curr = *__first;
1094  __prev = __curr;
1095  ++__first;
1096  ++__curr;
1097  }
1098 
1099  if (__curr != __end)
1100  erase_after(__prev, __end);
1101  else
1102  insert_range_after(__prev,
1103  ranges::subrange(std::move(__first), __last));
1104  }
1105 #endif // containers_ranges
1106 
1107 #pragma GCC diagnostic push
1108 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1109  /**
1110  * @brief Assigns a given value to a %forward_list.
1111  * @param __n Number of elements to be assigned.
1112  * @param __val Value to be assigned.
1113  *
1114  * This function fills a %forward_list with `__n` copies of the
1115  * given value. Note that the assignment completely changes the
1116  * %forward_list, and that the resulting %forward_list has `__n`
1117  * elements.
1118  */
1119  void
1120  assign(size_type __n, const _Tp& __val)
1121  {
1122  if constexpr (is_copy_assignable<_Tp>::value)
1123  {
1124  auto __prev = before_begin();
1125  auto __curr = begin();
1126  auto __end = end();
1127  while (__curr != __end && __n > 0)
1128  {
1129  *__curr = __val;
1130  ++__prev;
1131  ++__curr;
1132  --__n;
1133  }
1134  if (__n > 0)
1135  insert_after(__prev, __n, __val);
1136  else if (__curr != __end)
1137  erase_after(__prev, __end);
1138  }
1139  else
1140  {
1141  clear();
1142  insert_after(cbefore_begin(), __n, __val);
1143  }
1144  }
1145 #pragma GCC diagnostic pop
1146 
1147  /**
1148  * @brief Assigns an initializer_list to a %forward_list.
1149  * @param __il An initializer_list of value_type.
1150  *
1151  * Replace the contents of the %forward_list with copies of the
1152  * elements in the initializer_list `__il`. This is linear in
1153  * `__il.size()`.
1154  */
1155  void
1157  { assign(__il.begin(), __il.end()); }
1158 
1159  /// Get a copy of the memory allocation object.
1160  allocator_type
1161  get_allocator() const noexcept
1162  { return allocator_type(this->_M_get_Node_allocator()); }
1163 
1164  // 23.3.4.3 iterators:
1165 
1166  /**
1167  * Returns a read/write iterator that points before the first element
1168  * in the %forward_list. Iteration is done in ordinary element order.
1169  */
1170  [[__nodiscard__]]
1171  iterator
1172  before_begin() noexcept
1173  { return iterator(this->_M_impl._M_head._M_base_ptr()); }
1174 
1175  /**
1176  * Returns a read-only (constant) iterator that points before the
1177  * first element in the %forward_list. Iteration is done in ordinary
1178  * element order.
1179  */
1180  [[__nodiscard__]]
1181  const_iterator
1182  before_begin() const noexcept
1183  { return const_iterator(this->_M_impl._M_head._M_base_ptr()); }
1184 
1185  /**
1186  * Returns a read/write iterator that points to the first element
1187  * in the %forward_list. Iteration is done in ordinary element order.
1188  */
1189  [[__nodiscard__]]
1190  iterator
1191  begin() noexcept
1192  { return iterator(this->_M_impl._M_head._M_next); }
1193 
1194  /**
1195  * Returns a read-only (constant) iterator that points to the first
1196  * element in the %forward_list. Iteration is done in ordinary
1197  * element order.
1198  */
1199  [[__nodiscard__]]
1200  const_iterator
1201  begin() const noexcept
1202  { return const_iterator(this->_M_impl._M_head._M_next); }
1203 
1204  /**
1205  * Returns a read/write iterator that points one past the last
1206  * element in the %forward_list. Iteration is done in ordinary
1207  * element order.
1208  */
1209  [[__nodiscard__]]
1210  iterator
1211  end() noexcept
1212  { return iterator(nullptr); }
1213 
1214  /**
1215  * Returns a read-only iterator that points one past the last
1216  * element in the %forward_list. Iteration is done in ordinary
1217  * element order.
1218  */
1219  [[__nodiscard__]]
1220  const_iterator
1221  end() const noexcept
1222  { return const_iterator(nullptr); }
1223 
1224  /**
1225  * Returns a read-only (constant) iterator that points to the
1226  * first element in the %forward_list. Iteration is done in ordinary
1227  * element order.
1228  */
1229  [[__nodiscard__]]
1230  const_iterator
1231  cbegin() const noexcept
1232  { return const_iterator(this->_M_impl._M_head._M_next); }
1233 
1234  /**
1235  * Returns a read-only (constant) iterator that points before the
1236  * first element in the %forward_list. Iteration is done in ordinary
1237  * element order.
1238  */
1239  [[__nodiscard__]]
1240  const_iterator
1241  cbefore_begin() const noexcept
1242  { return const_iterator(this->_M_impl._M_head._M_base_ptr()); }
1243 
1244  /**
1245  * Returns a read-only (constant) iterator that points one past
1246  * the last element in the %forward_list. Iteration is done in
1247  * ordinary element order.
1248  */
1249  [[__nodiscard__]]
1250  const_iterator
1251  cend() const noexcept
1252  { return const_iterator(nullptr); }
1253 
1254  /**
1255  * Returns true if the %forward_list is empty. (Thus begin() would
1256  * equal end().)
1257  */
1258  [[__nodiscard__]]
1259  bool
1260  empty() const noexcept
1261  { return this->_M_impl._M_head._M_next == nullptr; }
1262 
1263  /**
1264  * Returns the largest possible number of elements of %forward_list.
1265  */
1266  [[__nodiscard__]]
1267  size_type
1268  max_size() const noexcept
1269  { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); }
1270 
1271  // 23.3.4.4 element access:
1272 
1273  /**
1274  * Returns a read/write reference to the data at the first
1275  * element of the %forward_list.
1276  */
1277  [[__nodiscard__]]
1278  reference
1280  {
1281  __glibcxx_requires_nonempty();
1282  _Node& __front = static_cast<_Node&>(*this->_M_impl._M_head._M_next);
1283  return *__front._M_valptr();
1284  }
1285 
1286  /**
1287  * Returns a read-only (constant) reference to the data at the first
1288  * element of the %forward_list.
1289  */
1290  [[__nodiscard__]]
1291  const_reference
1292  front() const
1293  {
1294  __glibcxx_requires_nonempty();
1295  _Node& __front = static_cast<_Node&>(*this->_M_impl._M_head._M_next);
1296  return *__front._M_valptr();
1297  }
1298 
1299  // 23.3.4.5 modifiers:
1300 
1301  /**
1302  * @brief Constructs object in %forward_list at the front of the
1303  * list.
1304  * @param __args Arguments.
1305  *
1306  * This function will insert an object of type `Tp` constructed
1307  * with `Tp(std::forward<Args>(args)...)` at the front of the list
1308  * Due to the nature of a %forward_list this operation can
1309  * be done in constant time, and does not invalidate iterators
1310  * and references.
1311  */
1312  template<typename... _Args>
1313 #if __cplusplus > 201402L
1314  reference
1315 #else
1316  void
1317 #endif
1318  emplace_front(_Args&&... __args)
1319  {
1320  this->_M_insert_after(cbefore_begin(),
1321  std::forward<_Args>(__args)...);
1322 #if __cplusplus > 201402L
1323  return front();
1324 #endif
1325  }
1326 
1327  /**
1328  * @brief Add data to the front of the %forward_list.
1329  * @param __val Data to be added.
1330  *
1331  * This is a typical stack operation. The function creates an
1332  * element at the front of the %forward_list and assigns the given
1333  * data to it. Due to the nature of a %forward_list this operation
1334  * can be done in constant time, and does not invalidate iterators
1335  * and references.
1336  */
1337  void
1338  push_front(const _Tp& __val)
1339  { this->_M_insert_after(cbefore_begin(), __val); }
1340 
1341  /**
1342  *
1343  */
1344  void
1345  push_front(_Tp&& __val)
1346  { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
1347 
1348 #if __glibcxx_containers_ranges // C++ >= 23
1349  /**
1350  * @brief Insert a range at the beginning of a forward_list.
1351  * @param __rg An input range with elements that are convertible to
1352  * the forward_list's value_type.
1353  *
1354  * The inserted elements will be in the same order as in the range,
1355  * so they are not reversed as would happen with a simple loop calling
1356  * `emplace_front` for each element of the range.
1357  *
1358  * No iterators to existing elements are invalidated by this function.
1359  * If the insertion fails due to an exception, no elements will be added
1360  * and so the list will be unchanged.
1361  *
1362  * @since C++23
1363  */
1364  template<__detail::__container_compatible_range<_Tp> _Rg>
1365  void
1366  prepend_range(_Rg&& __rg)
1367  {
1368  forward_list __tmp(from_range, std::forward<_Rg>(__rg),
1369  get_allocator());
1370  if (!__tmp.empty())
1371  splice_after(before_begin(), __tmp);
1372  }
1373 #endif // containers_ranges
1374 
1375  /**
1376  * @brief Removes first element.
1377  *
1378  * This is a typical stack operation. It shrinks the %forward_list
1379  * by one. Due to the nature of a %forward_list this operation can
1380  * be done in constant time, and only invalidates iterators/references
1381  * to the element being removed.
1382  *
1383  * Note that no data is returned, and if the first element's data
1384  * is needed, it should be retrieved before `pop_front()` is
1385  * called.
1386  */
1387  void
1389  {
1390  __glibcxx_requires_nonempty();
1391  this->_M_erase_after(this->_M_impl._M_head._M_base_ptr());
1392  }
1393 
1394  /**
1395  * @brief Constructs object in %forward_list after the specified
1396  * iterator.
1397  * @param __pos A const_iterator into the %forward_list.
1398  * @param __args Arguments.
1399  * @return An iterator that points to the inserted data.
1400  *
1401  * This function will insert an object of type `T` constructed
1402  * with `T(std::forward<Args>(args)...)` after the specified
1403  * location. Due to the nature of a %forward_list this operation can
1404  * be done in constant time, and does not invalidate iterators
1405  * and references.
1406  */
1407  template<typename... _Args>
1408  iterator
1409  emplace_after(const_iterator __pos, _Args&&... __args)
1410  { return iterator(this->_M_insert_after(__pos,
1411  std::forward<_Args>(__args)...)); }
1412 
1413  /**
1414  * @brief Inserts given value into %forward_list after specified
1415  * iterator.
1416  * @param __pos An iterator into the %forward_list.
1417  * @param __val Data to be inserted.
1418  * @return An iterator that points to the inserted data.
1419  *
1420  * This function will insert a copy of the given value after
1421  * the specified location. Due to the nature of a %forward_list this
1422  * operation can be done in constant time, and does not
1423  * invalidate iterators and references.
1424  */
1425  iterator
1426  insert_after(const_iterator __pos, const _Tp& __val)
1427  { return iterator(this->_M_insert_after(__pos, __val)); }
1428 
1429  /**
1430  *
1431  */
1432  iterator
1433  insert_after(const_iterator __pos, _Tp&& __val)
1434  { return iterator(this->_M_insert_after(__pos, std::move(__val))); }
1435 
1436  /**
1437  * @brief Inserts a number of copies of given data into the
1438  * %forward_list.
1439  * @param __pos An iterator into the %forward_list.
1440  * @param __n Number of elements to be inserted.
1441  * @param __val Data to be inserted.
1442  * @return An iterator pointing to the last inserted copy of
1443  * `val` or `pos` if `n == 0`.
1444  *
1445  * This function will insert a specified number of copies of the
1446  * given data after the location specified by `pos`.
1447  *
1448  * This operation is linear in the number of elements inserted and
1449  * does not invalidate iterators and references.
1450  */
1451  iterator
1452  insert_after(const_iterator __pos, size_type __n, const _Tp& __val);
1453 
1454  /**
1455  * @brief Inserts a range into the %forward_list.
1456  * @param __pos An iterator into the %forward_list.
1457  * @param __first An input iterator.
1458  * @param __last An input iterator.
1459  * @return An iterator pointing to the last inserted element or
1460  * `__pos` if `__first == __last`.
1461  *
1462  * This function will insert copies of the data in the range
1463  * `[ __first, __last)` into the %forward_list after the
1464  * location specified by `__pos.
1465  *
1466  * This operation is linear in the number of elements inserted and
1467  * does not invalidate iterators and references.
1468  */
1469  template<typename _InputIterator,
1470  typename = std::_RequireInputIter<_InputIterator>>
1471  iterator
1472  insert_after(const_iterator __pos,
1473  _InputIterator __first, _InputIterator __last);
1474 
1475  /**
1476  * @brief Inserts the contents of an initializer_list into
1477  * %forward_list after the specified iterator.
1478  * @param __pos An iterator into the %forward_list.
1479  * @param __il An initializer_list of value_type.
1480  * @return An iterator pointing to the last inserted element
1481  * or `__pos` if `__il` is empty.
1482  *
1483  * This function will insert copies of the data in the
1484  * initializer_list `__il` into the %forward_list before the location
1485  * specified by `__pos`.
1486  *
1487  * This operation is linear in the number of elements inserted and
1488  * does not invalidate iterators and references.
1489  */
1490  iterator
1491  insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
1492  { return insert_after(__pos, __il.begin(), __il.end()); }
1493 
1494 #if __glibcxx_containers_ranges // C++ >= 23
1495  /**
1496  * @brief Insert a rangeinto a forward_list.
1497  * @param __position An iterator.
1498  * @param __rg An input range of elements that can be converted to
1499  * the forward_list's value type.
1500  * @return An iterator pointing to the last element inserted,
1501  * or `__position` if the range is empty.
1502  *
1503  * Inserts the elements of `__rg` after `__position`.
1504  * No iterators to existing elements are invalidated by this function.
1505  * If the insertion fails due to an exception, no elements will be added
1506  * and so the list will be unchanged.
1507  *
1508  * @since C++23
1509  */
1510  template<__detail::__container_compatible_range<_Tp> _Rg>
1511  iterator
1512  insert_range_after(const_iterator __position, _Rg&& __rg)
1513  {
1514  forward_list __tmp(from_range, std::forward<_Rg>(__rg),
1515  get_allocator());
1516  return _M_splice_after(__position, __tmp.before_begin(), __tmp.end());
1517  }
1518 #endif // containers_ranges
1519 
1520  /**
1521  * @brief Removes the element pointed to by the iterator following
1522  * `pos`.
1523  * @param __pos Iterator pointing before element to be erased.
1524  * @return An iterator pointing to the element following the one
1525  * that was erased, or `end()` if no such element exists.
1526  *
1527  * This function will erase the element at the given position and
1528  * thus shorten the %forward_list by one.
1529  *
1530  * Due to the nature of a %forward_list this operation can be done
1531  * in constant time, and only invalidates iterators/references to
1532  * the element being removed. The user is also cautioned that
1533  * this function only erases the element, and that if the element
1534  * is itself a pointer, the pointed-to memory is not touched in
1535  * any way. Managing the pointer is the user's responsibility.
1536  */
1537  iterator
1538  erase_after(const_iterator __pos)
1539  { return iterator(this->_M_erase_after(__pos._M_const_cast()._M_node)); }
1540 
1541  /**
1542  * @brief Remove a range of elements.
1543  * @param __pos Iterator pointing before the first element to be
1544  * erased.
1545  * @param __last Iterator pointing to one past the last element to be
1546  * erased.
1547  * @return `__last`
1548  *
1549  * This function will erase the elements in the range
1550  * `(__pos,__last)` and shorten the %forward_list accordingly.
1551  *
1552  * This operation is linear time in the size of the range and only
1553  * invalidates iterators/references to the element being removed.
1554  *
1555  * The user is also cautioned that this function only erases the
1556  * elements, and that if the elements themselves are pointers, the
1557  * pointed-to memory is not touched in any way. Managing the pointer
1558  * is the user's responsibility.
1559  */
1560  iterator
1561  erase_after(const_iterator __pos, const_iterator __last)
1562  {
1563  return iterator(this->_M_erase_after(__pos._M_const_cast()._M_node,
1564  __last._M_const_cast()._M_node));
1565  }
1566 
1567  /**
1568  * @brief Swaps data with another %forward_list.
1569  * @param __list A %forward_list of the same element and allocator
1570  * types.
1571  *
1572  * This exchanges the elements between two lists in constant
1573  * time. Note that the global `std::swap()` function is
1574  * overloaded such that `std::swap(l1, l2)` will feed to this
1575  * function.
1576  *
1577  * Whether the allocators are swapped depends on the allocator traits.
1578  */
1579  void
1580  swap(forward_list& __list) noexcept
1581  {
1582  std::swap(this->_M_impl._M_head._M_next,
1583  __list._M_impl._M_head._M_next);
1584  _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1585  __list._M_get_Node_allocator());
1586  }
1587 
1588  /**
1589  * @brief Resizes the %forward_list to the specified number of
1590  * elements.
1591  * @param __sz Number of elements the %forward_list should contain.
1592  *
1593  * This function will %resize the %forward_list to the specified
1594  * number of elements. If the number is smaller than the
1595  * %forward_list's current number of elements the %forward_list
1596  * is truncated, otherwise the %forward_list is extended and the
1597  * new elements are default constructed.
1598  */
1599  void
1600  resize(size_type __sz);
1601 
1602  /**
1603  * @brief Resizes the %forward_list to the specified number of
1604  * elements.
1605  * @param __sz Number of elements the %forward_list should contain.
1606  * @param __val Data with which new elements should be populated.
1607  *
1608  * This function will %resize the %forward_list to the specified
1609  * number of elements. If the number is smaller than the
1610  * %forward_list's current number of elements the %forward_list
1611  * is truncated, otherwise the %forward_list is extended and new
1612  * elements are populated with given data.
1613  */
1614  void
1615  resize(size_type __sz, const value_type& __val);
1616 
1617  /**
1618  * @brief Erases all the elements.
1619  *
1620  * Note that this function only erases
1621  * the elements, and that if the elements themselves are
1622  * pointers, the pointed-to memory is not touched in any way.
1623  * Managing the pointer is the user's responsibility.
1624  */
1625  void
1626  clear() noexcept
1627  { this->_M_erase_after(this->_M_impl._M_head._M_base_ptr(), nullptr); }
1628 
1629  // 23.3.4.6 forward_list operations:
1630 
1631  /**
1632  * @brief Insert contents of another %forward_list.
1633  * @param __pos Iterator referencing the element to insert after.
1634  * @param __list Source list.
1635  *
1636  * The elements of `list` are inserted in constant time after
1637  * the element referenced by `pos`. `list` becomes an empty
1638  * list.
1639  *
1640  * Requires `this != &x`.
1641  */
1642  void
1643  splice_after(const_iterator __pos, forward_list&& __list) noexcept
1644  {
1645  if (!__list.empty())
1646  _M_splice_after(__pos, __list.before_begin(), __list.end());
1647  }
1648 
1649  void
1650  splice_after(const_iterator __pos, forward_list& __list) noexcept
1651  { splice_after(__pos, std::move(__list)); }
1652 
1653  /**
1654  * @brief Insert element from another %forward_list.
1655  * @param __pos Iterator referencing the element to insert after.
1656  * @param __list Source list.
1657  * @param __i Iterator referencing the element before the element
1658  * to move.
1659  *
1660  * Removes the element in list `__list` referenced by `__i` and
1661  * inserts it into the current list after `__pos`.
1662  */
1663  void
1664  splice_after(const_iterator __pos, forward_list&& __list,
1665  const_iterator __i) noexcept;
1666 
1667  void
1668  splice_after(const_iterator __pos, forward_list& __list,
1669  const_iterator __i) noexcept
1670  { splice_after(__pos, std::move(__list), __i); }
1671 
1672  /**
1673  * @brief Insert range from another %forward_list.
1674  * @param __pos Iterator referencing the element to insert after.
1675  * @param __list Source list.
1676  * @param __before Iterator referencing before the start of range
1677  * in `__list`.
1678  * @param __last Iterator referencing the end of range in `__list`.
1679  *
1680  * Removes elements in the range `(__before,__last)` and inserts them
1681  * after `__pos` in constant time.
1682  *
1683  * Undefined if `__pos` is in `(__before,__last)`.
1684  * @{
1685  */
1686  void
1687  splice_after(const_iterator __pos, forward_list&&,
1688  const_iterator __before, const_iterator __last) noexcept
1689  { _M_splice_after(__pos, __before, __last); }
1690 
1691  void
1692  splice_after(const_iterator __pos, forward_list&,
1693  const_iterator __before, const_iterator __last) noexcept
1694  { _M_splice_after(__pos, __before, __last); }
1695  /// @}
1696 
1697  private:
1698 #ifdef __glibcxx_list_remove_return_type // C++20 && HOSTED
1699  using __remove_return_type = size_type;
1700 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \
1701  __attribute__((__abi_tag__("__cxx20")))
1702 #else
1703  using __remove_return_type = void;
1704 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1705 #endif
1706  public:
1707 
1708  /**
1709  * @brief Remove all elements equal to value.
1710  * @param __val The value to remove.
1711  *
1712  * Removes every element in the list equal to `__val`.
1713  * Remaining elements stay in list order. Note that this
1714  * function only erases the elements, and that if the elements
1715  * themselves are pointers, the pointed-to memory is not
1716  * touched in any way. Managing the pointer is the user's
1717  * responsibility.
1718  */
1719  _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1720  __remove_return_type
1721  remove(const _Tp& __val);
1722 
1723  /**
1724  * @brief Remove all elements satisfying a predicate.
1725  * @param __pred Unary predicate function or object.
1726  *
1727  * Removes every element in the list for which the predicate
1728  * returns true. Remaining elements stay in list order. Note
1729  * that this function only erases the elements, and that if the
1730  * elements themselves are pointers, the pointed-to memory is
1731  * not touched in any way. Managing the pointer is the user's
1732  * responsibility.
1733  */
1734  template<typename _Pred>
1735  __remove_return_type
1736  remove_if(_Pred __pred);
1737 
1738  /**
1739  * @brief Remove consecutive duplicate elements.
1740  *
1741  * For each consecutive set of elements with the same value,
1742  * remove all but the first one. Remaining elements stay in
1743  * list order. Note that this function only erases the
1744  * elements, and that if the elements themselves are pointers,
1745  * the pointed-to memory is not touched in any way. Managing
1746  * the pointer is the user's responsibility.
1747  */
1748  _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1749  __remove_return_type
1751  { return unique(std::equal_to<_Tp>()); }
1752 
1753 #undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1754 
1755  /**
1756  * @brief Remove consecutive elements satisfying a predicate.
1757  * @param __binary_pred Binary predicate function or object.
1758  *
1759  * For each consecutive set of elements [first,last) that
1760  * satisfy predicate(first,i) where i is an iterator in
1761  * [first,last), remove all but the first one. Remaining
1762  * elements stay in list order. Note that this function only
1763  * erases the elements, and that if the elements themselves are
1764  * pointers, the pointed-to memory is not touched in any way.
1765  * Managing the pointer is the user's responsibility.
1766  */
1767  template<typename _BinPred>
1768  __remove_return_type
1769  unique(_BinPred __binary_pred);
1770 
1771  /**
1772  * @brief Merge sorted lists.
1773  * @param __list Sorted list to merge.
1774  *
1775  * Assumes that both `__list` and this list are sorted according to
1776  * operator<(). Merges elements of `__list` into this list in
1777  * sorted order, leaving `__list` empty when complete. Elements in
1778  * this list precede elements in `__list` that are equal.
1779  */
1780  void
1782  { merge(std::move(__list), std::less<_Tp>()); }
1783 
1784  void
1785  merge(forward_list& __list)
1786  { merge(std::move(__list)); }
1787 
1788  /**
1789  * @brief Merge sorted lists according to comparison function.
1790  * @param __list Sorted list to merge.
1791  * @param __comp Comparison function defining sort order.
1792  *
1793  * Assumes that both `__list` and this list are sorted according to
1794  * comp. Merges elements of `__list` into this list
1795  * in sorted order, leaving `__list` empty when complete. Elements
1796  * in this list precede elements in `__list` that are equivalent
1797  * according to comp().
1798  */
1799  template<typename _Comp>
1800  void
1801  merge(forward_list&& __list, _Comp __comp);
1802 
1803  template<typename _Comp>
1804  void
1805  merge(forward_list& __list, _Comp __comp)
1806  { merge(std::move(__list), __comp); }
1807 
1808  /**
1809  * @brief Sort the elements of the list.
1810  *
1811  * Sorts the elements of this list in NlogN time. Equivalent
1812  * elements remain in list order.
1813  */
1814  void
1816  { sort(std::less<_Tp>()); }
1817 
1818  /**
1819  * @brief Sort the forward_list using a comparison function.
1820  *
1821  * Sorts the elements of this list in NlogN time. Equivalent
1822  * elements remain in list order.
1823  */
1824  template<typename _Comp>
1825  void
1826  sort(_Comp __comp);
1827 
1828  /**
1829  * @brief Reverse the elements in list.
1830  *
1831  * Reverse the order of elements in the list in linear time.
1832  */
1833  void
1834  reverse() noexcept
1835  { this->_M_impl._M_head._M_reverse_after(); }
1836 
1837  private:
1838  // Called by the range constructor to implement [23.3.4.2]/9
1839  template<typename _InputIterator>
1840  void
1841  _M_range_initialize(_InputIterator __first, _InputIterator __last);
1842 
1843  // Called by forward_list(n,v,a), and the range constructor when it
1844  // turns out to be the same thing.
1845  void
1846  _M_fill_initialize(size_type __n, const value_type& __value);
1847 
1848  // Called by splice_after and insert_after.
1849  iterator
1850  _M_splice_after(const_iterator __pos, const_iterator __before,
1851  const_iterator __last);
1852 
1853  // Called by forward_list(n).
1854  void
1855  _M_default_initialize(size_type __n);
1856 
1857  // Called by resize(sz).
1858  void
1859  _M_default_insert_after(const_iterator __pos, size_type __n);
1860 
1861 #if ! _GLIBCXX_INLINE_VERSION
1862 #pragma GCC diagnostic push
1863 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1864  // XXX GLIBCXX_ABI Deprecated
1865  // These members are unused by std::forward_list now, but we keep them
1866  // here so that an explicit instantiation will define them.
1867  // This ensures that explicit instantiations still define these symbols,
1868  // so that explicit instantiation declarations of std::forward_list that
1869  // were compiled with old versions of GCC can still find these symbols.
1870 
1871  // Use 'if constexpr' so that the functions don't do anything for
1872  // specializations using _Node_traits<T, fancy-pointer>, because any
1873  // old code referencing these symbols wasn't using the fancy-pointer
1874  // specializations.
1875 
1876  void
1877  _M_move_assign(forward_list&& __list, true_type) noexcept
1878  {
1879 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
1881 #endif
1882  {
1883  clear();
1884  this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
1885  __list._M_impl._M_head._M_next = nullptr;
1886  std::__alloc_on_move(this->_M_get_Node_allocator(),
1887  __list._M_get_Node_allocator());
1888  }
1889  }
1890 
1891  void
1892  _M_move_assign(forward_list&& __list, false_type)
1893  {
1894 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
1895  if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value)
1896 #endif
1897  {
1898  if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
1899  _M_move_assign(std::move(__list), true_type());
1900  else
1901  // The rvalue's allocator cannot be moved, or is not equal,
1902  // so we need to individually move each element.
1903  this->assign(std::make_move_iterator(__list.begin()),
1904  std::make_move_iterator(__list.end()));
1905  }
1906  }
1907 
1908  void
1909  _M_assign_n(size_type __n, const _Tp& __val, true_type)
1910  {
1911 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
1912  if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value)
1913 #endif
1914  {
1915  auto __prev = before_begin();
1916  auto __curr = begin();
1917  auto __end = end();
1918  while (__curr != __end && __n > 0)
1919  {
1920  *__curr = __val;
1921  ++__prev;
1922  ++__curr;
1923  --__n;
1924  }
1925  if (__n > 0)
1926  insert_after(__prev, __n, __val);
1927  else if (__curr != __end)
1928  erase_after(__prev, __end);
1929  }
1930  }
1931 
1932  void
1933  _M_assign_n(size_type __n, const _Tp& __val, false_type)
1934  {
1935 #if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
1936  if constexpr (is_same<typename _Alloc_traits::pointer, _Tp*>::value)
1937 #endif
1938  {
1939  clear();
1940  insert_after(cbefore_begin(), __n, __val);
1941  }
1942  }
1943 #pragma GCC diagnostic pop
1944 #endif // ! _GLIBCXX_INLINE_VERSION
1945  };
1946 
1947 #if __cpp_deduction_guides >= 201606
1948  template<typename _InputIterator, typename _ValT
1949  = typename iterator_traits<_InputIterator>::value_type,
1950  typename _Allocator = allocator<_ValT>,
1951  typename = _RequireInputIter<_InputIterator>,
1952  typename = _RequireAllocator<_Allocator>>
1953  forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator())
1954  -> forward_list<_ValT, _Allocator>;
1955 
1956 #if __glibcxx_containers_ranges // C++ >= 23
1957  template<ranges::input_range _Rg,
1958  typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
1959  forward_list(from_range_t, _Rg&&, _Allocator = _Allocator())
1960  -> forward_list<ranges::range_value_t<_Rg>, _Allocator>;
1961 #endif
1962 #endif
1963 
1964  /**
1965  * @brief Forward list equality comparison.
1966  * @param __lx A %forward_list
1967  * @param __ly A %forward_list of the same type as `__lx`.
1968  * @return True iff the elements of the forward lists are equal.
1969  *
1970  * This is an equivalence relation. It is linear in the number of
1971  * elements of the forward lists. Deques are considered equivalent
1972  * if corresponding elements compare equal.
1973  */
1974  template<typename _Tp, typename _Alloc>
1975  [[__nodiscard__]]
1976  bool
1977  operator==(const forward_list<_Tp, _Alloc>& __lx,
1978  const forward_list<_Tp, _Alloc>& __ly);
1979 
1980 #if __cpp_lib_three_way_comparison
1981  /**
1982  * @brief Forward list ordering relation.
1983  * @param __x A `forward_list`.
1984  * @param __y A `forward_list` of the same type as `__x`.
1985  * @return A value indicating whether `__x` is less than, equal to,
1986  * greater than, or incomparable with `__y`.
1987  *
1988  * See `std::lexicographical_compare_three_way()` for how the determination
1989  * is made. This operator is used to synthesize relational operators like
1990  * `<` and `>=` etc.
1991  */
1992  template<typename _Tp, typename _Alloc>
1993  [[nodiscard]]
1994  inline __detail::__synth3way_t<_Tp>
1995  operator<=>(const forward_list<_Tp, _Alloc>& __x,
1996  const forward_list<_Tp, _Alloc>& __y)
1997  {
1998  return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
1999  __y.begin(), __y.end(),
2000  __detail::__synth3way);
2001  }
2002 #else
2003  /**
2004  * @brief Forward list ordering relation.
2005  * @param __lx A %forward_list.
2006  * @param __ly A %forward_list of the same type as `__lx`.
2007  * @return True iff `__lx` is lexicographically less than `__ly`.
2008  *
2009  * This is a total ordering relation. It is linear in the number of
2010  * elements of the forward lists. The elements must be comparable
2011  * with `<`.
2012  *
2013  * See std::lexicographical_compare() for how the determination is made.
2014  */
2015  template<typename _Tp, typename _Alloc>
2016  [[__nodiscard__]]
2017  inline bool
2018  operator<(const forward_list<_Tp, _Alloc>& __lx,
2019  const forward_list<_Tp, _Alloc>& __ly)
2020  { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(),
2021  __ly.cbegin(), __ly.cend()); }
2022 
2023  /// Based on operator==
2024  template<typename _Tp, typename _Alloc>
2025  [[__nodiscard__]]
2026  inline bool
2027  operator!=(const forward_list<_Tp, _Alloc>& __lx,
2028  const forward_list<_Tp, _Alloc>& __ly)
2029  { return !(__lx == __ly); }
2030 
2031  /// Based on operator<
2032  template<typename _Tp, typename _Alloc>
2033  [[__nodiscard__]]
2034  inline bool
2035  operator>(const forward_list<_Tp, _Alloc>& __lx,
2036  const forward_list<_Tp, _Alloc>& __ly)
2037  { return (__ly < __lx); }
2038 
2039  /// Based on operator<
2040  template<typename _Tp, typename _Alloc>
2041  [[__nodiscard__]]
2042  inline bool
2043  operator>=(const forward_list<_Tp, _Alloc>& __lx,
2044  const forward_list<_Tp, _Alloc>& __ly)
2045  { return !(__lx < __ly); }
2046 
2047  /// Based on operator<
2048  template<typename _Tp, typename _Alloc>
2049  [[__nodiscard__]]
2050  inline bool
2051  operator<=(const forward_list<_Tp, _Alloc>& __lx,
2052  const forward_list<_Tp, _Alloc>& __ly)
2053  { return !(__ly < __lx); }
2054 #endif // three-way comparison
2055 
2056  /// See std::forward_list::swap().
2057  template<typename _Tp, typename _Alloc>
2058  inline void
2061  noexcept(noexcept(__lx.swap(__ly)))
2062  { __lx.swap(__ly); }
2063 
2064 _GLIBCXX_END_NAMESPACE_CONTAINER
2065 _GLIBCXX_END_NAMESPACE_VERSION
2066 } // namespace std
2067 
2068 #endif // _FORWARD_LIST_H
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:873
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:866
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:116
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:119
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:52
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1251
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1229
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.
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
Definition: ptr_traits.h:201
initializer_list
is_same
Definition: type_traits:1540
is_nothrow_default_constructible
Definition: type_traits:1245
is_assignable
Definition: type_traits:1277
is_copy_assignable
Definition: type_traits:1287
is_trivially_destructible
Definition: type_traits:1459
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.
Definition: forward_list.h:70
A helper node class for forward_list. This is just a linked list with uninitialized storage for a dat...
Definition: forward_list.h:135
A forward_list::const_iterator.
Definition: forward_list.h:250
friend bool operator==(const _Self &__x, const _Self &__y) noexcept
Forward list const_iterator equality comparison.
Definition: forward_list.h:301
A forward_list::iterator.
Definition: forward_list.h:164
friend bool operator==(const _Self &__x, const _Self &__y) noexcept
Forward list iterator equality comparison.
Definition: forward_list.h:211
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: forward_list.h:768
__remove_return_type unique(_BinPred __binary_pred)
Remove consecutive elements satisfying a predicate.
iterator begin() noexcept
const_iterator before_begin() const noexcept
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:960
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
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:810
void sort()
Sort the elements of the list.
iterator before_begin() noexcept
forward_list(const forward_list &__list, const __type_identity_t< _Alloc > &__al)
Copy constructor with allocator argument.
Definition: forward_list.h:819
iterator emplace_after(const_iterator __pos, _Args &&... __args)
Constructs object in forward_list after the specified iterator.
forward_list(const forward_list &__list)
The forward_list copy constructor.
Definition: forward_list.h:928
forward_list & operator=(std::initializer_list< _Tp > __il)
The forward_list initializer list assignment operator.
iterator insert_after(const_iterator __pos, const _Tp &__val)
Inserts given value into forward_list after specified iterator.
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
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:877
void assign(size_type __n, const _Tp &__val)
Assigns a given value to a forward_list.
const_iterator begin() const noexcept
void splice_after(const_iterator __pos, forward_list &&__list) noexcept
Insert contents of another forward_list.
const_iterator cbefore_begin() const noexcept
forward_list(std::initializer_list< _Tp > __il, const _Alloc &__al=_Alloc())
Builds a forward_list from an initializer_list.
Definition: forward_list.h:952
reference emplace_front(_Args &&... __args)
Constructs object in forward_list at the front of the list.
forward_list(size_type __n, const _Alloc &__al=_Alloc())
Creates a forward_list with default constructed elements.
Definition: forward_list.h:864
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
void splice_after(const_iterator __pos, forward_list &&, const_iterator __before, const_iterator __last) noexcept
Insert range from another forward_list.
reference front()
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:848
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
forward_list & operator=(forward_list &&__list) noexcept(_Node_alloc_traits::_S_nothrow_move())
The forward_list move assignment operator.
Definition: forward_list.h:990
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a forward_list.
bool empty() const noexcept
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
void push_front(const _Tp &__val)
Add data to the front of the forward_list.
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:894
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
void pop_front()
Removes first element.
void assign(std::initializer_list< _Tp > __il)
Assigns an initializer_list to a forward_list.
size_type max_size() const noexcept
Base class for forward_list.
Definition: forward_list.h:601
The node-base type for allocators that use fancy pointers.
Definition: forward_list.h:348
A helper node class for forward_list.
Definition: forward_list.h:419
A forward_list iterator when the allocator uses fancy pointers.
Definition: forward_list.h:456
constexpr friend bool operator==(const _Iterator &__x, const _Iterator &__y) noexcept
Forward list iterator equality comparison.
Definition: forward_list.h:521
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.