libstdc++
debug/forward_list
Go to the documentation of this file.
1 // <forward_list> -*- C++ -*-
2 
3 // Copyright (C) 2010-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 debug/forward_list
26  * This file is a GNU debug extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_DEBUG_FORWARD_LIST
30 #define _GLIBCXX_DEBUG_FORWARD_LIST 1
31 
32 #ifdef _GLIBCXX_SYSHDR
33 #pragma GCC system_header
34 #endif
35 
36 #include <bits/c++config.h>
37 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
38  template<typename _Tp, typename _Allocator> class forward_list;
39 } } // namespace std::__debug
40 
41 #include <forward_list>
42 #include <debug/safe_sequence.h>
43 #include <debug/safe_container.h>
44 #include <debug/safe_iterator.h>
45 
46 // Special validity check for forward_list ranges.
47 #define __glibcxx_check_valid_fl_range(_First,_Last,_Dist) \
48 _GLIBCXX_DEBUG_VERIFY(_First._M_valid_range(_Last, _Dist, false), \
49  _M_message(__gnu_debug::__msg_valid_range) \
50  ._M_iterator(_First, #_First) \
51  ._M_iterator(_Last, #_Last))
52 
53 namespace __gnu_debug
54 {
55  /// Special iterators swap and invalidation for forward_list because of the
56  /// before_begin iterator.
57  template<typename _SafeSequence>
58  class _Safe_forward_list
59  : public _Safe_sequence<_SafeSequence>
60  {
61  _SafeSequence&
62  _M_this() noexcept
63  { return *static_cast<_SafeSequence*>(this); }
64 
65  static void
66  _M_swap_aux(_Safe_sequence_base& __lhs,
67  _Safe_iterator_base*& __lhs_iterators,
68  _Safe_sequence_base& __rhs,
69  _Safe_iterator_base*& __rhs_iterators);
70 
71  void _M_swap_single(_Safe_sequence_base&) noexcept;
72 
73  protected:
74  void
75  _M_invalidate_all()
76  {
77  using _Base_const_iterator = __decltype(_M_this()._M_base().cend());
78  this->_M_invalidate_if([this](_Base_const_iterator __it)
79  {
80  return __it != _M_this()._M_base().cbefore_begin()
81  && __it != _M_this()._M_base().cend(); });
82  }
83 
84  void _M_swap(_Safe_sequence_base&) noexcept;
85  };
86 
87  template<typename _SafeSequence>
88  void
89  _Safe_forward_list<_SafeSequence>::
90  _M_swap_aux(_Safe_sequence_base& __lhs,
91  _Safe_iterator_base*& __lhs_iterators,
92  _Safe_sequence_base& __rhs,
93  _Safe_iterator_base*& __rhs_iterators)
94  {
95  using const_iterator = typename _SafeSequence::const_iterator;
96  _Safe_iterator_base* __bbegin_its = 0;
97  _Safe_iterator_base* __last_bbegin = 0;
98  _SafeSequence& __rseq = static_cast<_SafeSequence&>(__rhs);
99 
100  for (_Safe_iterator_base* __iter = __lhs_iterators; __iter;)
101  {
102  // Even iterator is cast to const_iterator, not a problem.
103  _Safe_iterator_base* __victim_base = __iter;
104  const_iterator* __victim =
105  static_cast<const_iterator*>(__victim_base);
106  __iter = __iter->_M_next;
107  if (__victim->base() == __rseq._M_base().cbefore_begin())
108  {
109  __victim->_M_unlink();
110  if (__lhs_iterators == __victim_base)
111  __lhs_iterators = __victim_base->_M_next;
112  if (__bbegin_its)
113  {
114  __victim_base->_M_next = __bbegin_its;
115  __bbegin_its->_M_prior = __victim_base;
116  }
117  else
118  __last_bbegin = __victim_base;
119  __bbegin_its = __victim_base;
120  }
121  else
122  __victim_base->_M_sequence = std::__addressof(__lhs);
123  }
124 
125  if (__bbegin_its)
126  {
127  if (__rhs_iterators)
128  {
129  __rhs_iterators->_M_prior = __last_bbegin;
130  __last_bbegin->_M_next = __rhs_iterators;
131  }
132  __rhs_iterators = __bbegin_its;
133  }
134  }
135 
136  template<typename _SafeSequence>
137  void
138  _Safe_forward_list<_SafeSequence>::
139  _M_swap_single(_Safe_sequence_base& __other) noexcept
140  {
141  std::swap(_M_this()._M_iterators, __other._M_iterators);
142  std::swap(_M_this()._M_const_iterators, __other._M_const_iterators);
143  // Useless, always 1 on forward_list
144  //std::swap(_M_this()_M_version, __other._M_version);
145  _Safe_iterator_base* __this_its = _M_this()._M_iterators;
146  _M_swap_aux(__other, __other._M_iterators,
147  _M_this(), _M_this()._M_iterators);
148  _Safe_iterator_base* __this_const_its = _M_this()._M_const_iterators;
149  _M_swap_aux(__other, __other._M_const_iterators,
150  _M_this(), _M_this()._M_const_iterators);
151  _M_swap_aux(_M_this(), __this_its,
152  __other, __other._M_iterators);
153  _M_swap_aux(_M_this(), __this_const_its,
154  __other, __other._M_const_iterators);
155  }
156 
157  /* Special forward_list _M_swap version that does not swap the
158  * before-begin ownership.*/
159  template<typename _SafeSequence>
160  void
161  _Safe_forward_list<_SafeSequence>::
162  _M_swap(_Safe_sequence_base& __other) noexcept
163  {
164  // We need to lock both sequences to swap
165  using namespace __gnu_cxx;
166  __mutex *__this_mutex = &_M_this()._M_get_mutex();
167  __mutex *__other_mutex =
168  &static_cast<_SafeSequence&>(__other)._M_get_mutex();
169  if (__this_mutex == __other_mutex)
170  {
171  __scoped_lock __lock(*__this_mutex);
172  _M_swap_single(__other);
173  }
174  else
175  {
176  __scoped_lock __l1(__this_mutex < __other_mutex
177  ? *__this_mutex : *__other_mutex);
178  __scoped_lock __l2(__this_mutex < __other_mutex
179  ? *__other_mutex : *__this_mutex);
180  _M_swap_single(__other);
181  }
182  }
183 }
184 
185 namespace std _GLIBCXX_VISIBILITY(default)
186 {
187 namespace __debug
188 {
189  /// Class std::forward_list with safety/checking/debug instrumentation.
190  template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
191  class forward_list
192  : public __gnu_debug::_Safe_container<
193  forward_list<_Tp, _Alloc>, _Alloc, __gnu_debug::_Safe_forward_list>,
194  public _GLIBCXX_STD_C::forward_list<_Tp, _Alloc>
195  {
196  typedef _GLIBCXX_STD_C::forward_list<_Tp, _Alloc> _Base;
197  typedef __gnu_debug::_Safe_container<
198  forward_list, _Alloc, __gnu_debug::_Safe_forward_list> _Safe;
199 
200  typedef typename _Base::iterator _Base_iterator;
201  typedef typename _Base::const_iterator _Base_const_iterator;
202 
203  template<typename _ItT, typename _SeqT, typename _CatT>
204  friend class ::__gnu_debug::_Safe_iterator;
205 
206  // Reference wrapper for base class. See PR libstdc++/90102.
207  struct _Base_ref
208  {
209  _Base_ref(const _Base& __r) : _M_ref(__r) { }
210 
211  const _Base& _M_ref;
212  };
213 
214  public:
215  typedef typename _Base::reference reference;
216  typedef typename _Base::const_reference const_reference;
217 
218  typedef __gnu_debug::_Safe_iterator<
219  _Base_iterator, forward_list> iterator;
220  typedef __gnu_debug::_Safe_iterator<
221  _Base_const_iterator, forward_list> const_iterator;
222 
223  typedef typename _Base::size_type size_type;
224  typedef typename _Base::difference_type difference_type;
225 
226  typedef _Tp value_type;
227  typedef typename _Base::allocator_type allocator_type;
228  typedef typename _Base::pointer pointer;
229  typedef typename _Base::const_pointer const_pointer;
230 
231  // 23.2.3.1 construct/copy/destroy:
232 
233  forward_list() = default;
234 
235  explicit
236  forward_list(const allocator_type& __al) noexcept
237  : _Base(__al) { }
238 
239  forward_list(const forward_list& __list, const allocator_type& __al)
240  : _Base(__list, __al)
241  { }
242 
243  forward_list(forward_list&& __list, const allocator_type& __al)
244  noexcept(
245  std::is_nothrow_constructible<_Base,
246  _Base, const allocator_type&>::value )
247  : _Safe(std::move(__list), __al),
248  _Base(std::move(__list), __al)
249  { }
250 
251  explicit
252  forward_list(size_type __n, const allocator_type& __al = allocator_type())
253  : _Base(__n, __al)
254  { }
255 
256  forward_list(size_type __n, const __type_identity_t<_Tp>& __value,
257  const allocator_type& __al = allocator_type())
258  : _Base(__n, __value, __al)
259  { }
260 
261  template<typename _InputIterator,
262  typename = std::_RequireInputIter<_InputIterator>>
263  forward_list(_InputIterator __first, _InputIterator __last,
264  const allocator_type& __al = allocator_type())
265  : _Base(__gnu_debug::__base(
266  __glibcxx_check_valid_constructor_range(__first, __last)),
267  __gnu_debug::__base(__last), __al)
268  { }
269 
270 #if __glibcxx_containers_ranges // C++ >= 23
271  template<__detail::__container_compatible_range<_Tp> _Rg>
272  forward_list(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
273  : _Base(std::from_range, std::forward<_Rg>(__rg), __a)
274  { }
275 #endif
276 
277  forward_list(const forward_list&) = default;
278 
279  forward_list(forward_list&&) = default;
280 
281  forward_list(std::initializer_list<_Tp> __il,
282  const allocator_type& __al = allocator_type())
283  : _Base(__il, __al)
284  { }
285 
286  ~forward_list() = default;
287 
288  forward_list(_Base_ref __x) : _Base(__x._M_ref) { }
289 
290  forward_list&
291  operator=(const forward_list&) = default;
292 
293  forward_list&
294  operator=(forward_list&&) = default;
295 
296  forward_list&
297  operator=(std::initializer_list<_Tp> __il)
298  {
299  _Base::operator=(__il);
300  this->_M_invalidate_all();
301  return *this;
302  }
303 
304  template<typename _InputIterator,
305  typename = std::_RequireInputIter<_InputIterator>>
306  void
307  assign(_InputIterator __first, _InputIterator __last)
308  {
309  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
310  __glibcxx_check_valid_range2(__first, __last, __dist);
311 
312  if (__dist.second >= __gnu_debug::__dp_sign)
313  _Base::assign(__gnu_debug::__unsafe(__first),
314  __gnu_debug::__unsafe(__last));
315  else
316  _Base::assign(__first, __last);
317 
318  this->_M_invalidate_all();
319  }
320 
321 #if __glibcxx_containers_ranges // C++ >= 23
322  template<__detail::__container_compatible_range<_Tp> _Rg>
323  void
324  assign_range(_Rg&& __rg)
325  {
326  // Have to reimplement this function, so that we use the debug
327  // version of erase_after, which invalidates the correct iterators.
328 
329  static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
330 
331  auto __first = ranges::begin(__rg);
332  const auto __last = ranges::end(__rg);
333  auto __prev = _Base::before_begin();
334  auto __curr = _Base::begin();
335  const auto __end = _Base::end();
336 
337  while (__curr != __end && __first != __last)
338  {
339  *__curr = *__first;
340  __prev = __curr;
341  ++__first;
342  ++__curr;
343  }
344 
345  if (__curr != __end)
346  erase_after(const_iterator(__prev, this), end());
347  else
348  _Base::insert_range_after(__prev,
349  ranges::subrange(std::move(__first),
350  __last));
351  }
352 #endif
353 
354  void
355  assign(size_type __n, const _Tp& __val)
356  {
357  _Base::assign(__n, __val);
358  this->_M_invalidate_all();
359  }
360 
361  void
362  assign(std::initializer_list<_Tp> __il)
363  {
364  _Base::assign(__il);
365  this->_M_invalidate_all();
366  }
367 
368  using _Base::get_allocator;
369 
370  // iterators:
371 
372  [[__nodiscard__]]
373  iterator
374  before_begin() noexcept
375  { return { _Base::before_begin(), this }; }
376 
377  [[__nodiscard__]]
378  const_iterator
379  before_begin() const noexcept
380  { return { _Base::before_begin(), this }; }
381 
382  [[__nodiscard__]]
383  iterator
384  begin() noexcept
385  { return { _Base::begin(), this }; }
386 
387  [[__nodiscard__]]
388  const_iterator
389  begin() const noexcept
390  { return { _Base::begin(), this }; }
391 
392  [[__nodiscard__]]
393  iterator
394  end() noexcept
395  { return { _Base::end(), this }; }
396 
397  [[__nodiscard__]]
398  const_iterator
399  end() const noexcept
400  { return { _Base::end(), this }; }
401 
402  [[__nodiscard__]]
403  const_iterator
404  cbegin() const noexcept
405  { return { _Base::cbegin(), this }; }
406 
407  [[__nodiscard__]]
408  const_iterator
409  cbefore_begin() const noexcept
410  { return { _Base::cbefore_begin(), this }; }
411 
412  [[__nodiscard__]]
413  const_iterator
414  cend() const noexcept
415  { return { _Base::cend(), this }; }
416 
417  using _Base::empty;
418  using _Base::max_size;
419 
420  // element access:
421 
422  [[__nodiscard__]]
423  reference
424  front()
425  {
426  __glibcxx_check_nonempty();
427  return _Base::front();
428  }
429 
430  [[__nodiscard__]]
431  const_reference
432  front() const
433  {
434  __glibcxx_check_nonempty();
435  return _Base::front();
436  }
437 
438  // modifiers:
439 
440  using _Base::emplace_front;
441  using _Base::push_front;
442 
443 #if __glibcxx_containers_ranges // C++ >= 23
444  using _Base::prepend_range;
445 #endif
446 
447  void
448  pop_front()
449  {
450  __glibcxx_check_nonempty();
451  this->_M_invalidate_if([this](_Base_const_iterator __it)
452  { return __it == this->_M_base().cbegin(); });
453  _Base::pop_front();
454  }
455 
456  template<typename... _Args>
457  iterator
458  emplace_after(const_iterator __pos, _Args&&... __args)
459  {
460  __glibcxx_check_insert_after(__pos);
461  return { _Base::emplace_after(__pos.base(),
462  std::forward<_Args>(__args)...),
463  this };
464  }
465 
466  iterator
467  insert_after(const_iterator __pos, const _Tp& __val)
468  {
469  __glibcxx_check_insert_after(__pos);
470  return { _Base::insert_after(__pos.base(), __val), this };
471  }
472 
473  iterator
474  insert_after(const_iterator __pos, _Tp&& __val)
475  {
476  __glibcxx_check_insert_after(__pos);
477  return { _Base::insert_after(__pos.base(), std::move(__val)), this };
478  }
479 
480  iterator
481  insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
482  {
483  __glibcxx_check_insert_after(__pos);
484  return { _Base::insert_after(__pos.base(), __n, __val), this };
485  }
486 
487  template<typename _InputIterator,
488  typename = std::_RequireInputIter<_InputIterator>>
489  iterator
490  insert_after(const_iterator __pos,
491  _InputIterator __first, _InputIterator __last)
492  {
493  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
494  __glibcxx_check_insert_range_after(__pos, __first, __last, __dist);
495 
496  if (__dist.second >= __gnu_debug::__dp_sign)
497  return
498  {
499  _Base::insert_after(__pos.base(),
500  __gnu_debug::__unsafe(__first),
501  __gnu_debug::__unsafe(__last)),
502  this
503  };
504  else
505  return { _Base::insert_after(__pos.base(), __first, __last), this };
506  }
507 
508  iterator
509  insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
510  {
511  __glibcxx_check_insert_after(__pos);
512  return { _Base::insert_after(__pos.base(), __il), this };
513  }
514 
515 #if __glibcxx_containers_ranges // C++ >= 23
516  template<__detail::__container_compatible_range<_Tp> _Rg>
517  iterator
518  insert_range_after(const_iterator __position, _Rg&& __rg)
519  {
520  auto __ret
521  = _Base::insert_range_after(__position.base(),
522  std::forward<_Rg>(__rg));
523  return { __ret, this };
524  }
525 #endif
526 
527  iterator
528  erase_after(const_iterator __pos)
529  {
530  __glibcxx_check_erase_after(__pos);
531 
532  _Base_const_iterator __next = std::next(__pos.base());
533  this->_M_invalidate_if([__next](_Base_const_iterator __it)
534  { return __it == __next; });
535  return { _Base::erase_after(__pos.base()), this };
536  }
537 
538  iterator
539  erase_after(const_iterator __pos, const_iterator __last)
540  {
541  __glibcxx_check_erase_range_after(__pos, __last);
542  for (_Base_const_iterator __victim = std::next(__pos.base());
543  __victim != __last.base(); ++__victim)
544  {
545  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
546  _M_message(__gnu_debug::__msg_valid_range2)
547  ._M_sequence(*this, "this")
548  ._M_iterator(__pos, "pos")
549  ._M_iterator(__last, "last"));
550  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
551  { return __it == __victim; });
552  }
553 
554  return { _Base::erase_after(__pos.base(), __last.base()), this };
555  }
556 
557  void
558  swap(forward_list& __list)
559  noexcept( noexcept(declval<_Base&>().swap(__list)) )
560  {
561  _Safe::_M_swap(__list);
562  _Base::swap(__list);
563  }
564 
565  void
566  resize(size_type __sz)
567  {
568  this->_M_detach_singular();
569 
570  // if __sz < size(), invalidate all iterators in [begin+__sz, end()
571  _Base_iterator __victim = _Base::begin();
572  _Base_iterator __end = _Base::end();
573  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
574  ++__victim;
575 
576  for (; __victim != __end; ++__victim)
577  {
578  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
579  { return __it == __victim; });
580  }
581 
582  __try
583  {
584  _Base::resize(__sz);
585  }
586  __catch(...)
587  {
588  this->_M_revalidate_singular();
589  __throw_exception_again;
590  }
591  }
592 
593  void
594  resize(size_type __sz, const value_type& __val)
595  {
596  this->_M_detach_singular();
597 
598  // if __sz < size(), invalidate all iterators in [begin+__sz, end())
599  _Base_iterator __victim = _Base::begin();
600  _Base_iterator __end = _Base::end();
601  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
602  ++__victim;
603 
604  for (; __victim != __end; ++__victim)
605  {
606  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
607  { return __it == __victim; });
608  }
609 
610  __try
611  {
612  _Base::resize(__sz, __val);
613  }
614  __catch(...)
615  {
616  this->_M_revalidate_singular();
617  __throw_exception_again;
618  }
619  }
620 
621  void
622  clear() noexcept
623  {
624  _Base::clear();
625  this->_M_invalidate_all();
626  }
627 
628  // 23.2.3.5 forward_list operations:
629  void
630  splice_after(const_iterator __pos, forward_list&& __list)
631  {
632  __glibcxx_check_insert_after(__pos);
633  _GLIBCXX_DEBUG_VERIFY(std::__addressof(__list) != this,
634  _M_message(__gnu_debug::__msg_self_splice)
635  ._M_sequence(*this, "this"));
636  _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
637  _M_message(__gnu_debug::__msg_splice_alloc)
638  ._M_sequence(*this)
639  ._M_sequence(__list, "__list"));
640  this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it)
641  {
642  return __it != __list._M_base().cbefore_begin()
643  && __it != __list._M_base().end();
644  });
645  _Base::splice_after(__pos.base(), std::move(__list));
646  }
647 
648  void
649  splice_after(const_iterator __pos, forward_list& __list)
650  { splice_after(__pos, std::move(__list)); }
651 
652  void
653  splice_after(const_iterator __pos, forward_list&& __list,
654  const_iterator __i)
655  {
656  __glibcxx_check_insert_after(__pos);
657  _GLIBCXX_DEBUG_VERIFY(__i._M_before_dereferenceable(),
658  _M_message(__gnu_debug::__msg_splice_bad)
659  ._M_iterator(__i, "__i"));
660  _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__list)),
661  _M_message(__gnu_debug::__msg_splice_other)
662  ._M_iterator(__i, "__i")
663  ._M_sequence(__list, "__list"));
664  _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
665  _M_message(__gnu_debug::__msg_splice_alloc)
666  ._M_sequence(*this)
667  ._M_sequence(__list, "__list"));
668 
669  // _GLIBCXX_RESOLVE_LIB_DEFECTS
670  // 250. splicing invalidates iterators
671  _Base_const_iterator __next = std::next(__i.base());
672  this->_M_transfer_from_if(__list, [__next](_Base_const_iterator __it)
673  { return __it == __next; });
674  _Base::splice_after(__pos.base(), std::move(__list), __i.base());
675  }
676 
677  void
678  splice_after(const_iterator __pos, forward_list& __list,
679  const_iterator __i)
680  { splice_after(__pos, std::move(__list), __i); }
681 
682  void
683  splice_after(const_iterator __pos, forward_list&& __list,
684  const_iterator __before, const_iterator __last)
685  {
686  typename __gnu_debug::_Distance_traits<const_iterator>::__type __dist;
687  auto __listptr = std::__addressof(__list);
688  __glibcxx_check_insert_after(__pos);
689  __glibcxx_check_valid_fl_range(__before, __last, __dist);
690  _GLIBCXX_DEBUG_VERIFY(__before._M_attached_to(__listptr),
691  _M_message(__gnu_debug::__msg_splice_other)
692  ._M_sequence(__list, "list")
693  ._M_iterator(__before, "before"));
694  _GLIBCXX_DEBUG_VERIFY(__before._M_dereferenceable()
695  || __before._M_is_before_begin(),
696  _M_message(__gnu_debug::__msg_valid_range2)
697  ._M_sequence(__list, "list")
698  ._M_iterator(__before, "before")
699  ._M_iterator(__last, "last"));
700  _GLIBCXX_DEBUG_VERIFY(__before != __last,
701  _M_message(__gnu_debug::__msg_valid_range2)
702  ._M_sequence(__list, "list")
703  ._M_iterator(__before, "before")
704  ._M_iterator(__last, "last"));
705  _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
706  _M_message(__gnu_debug::__msg_splice_alloc)
707  ._M_sequence(*this)
708  ._M_sequence(__list, "__list"));
709 
710  for (_Base_const_iterator __tmp = std::next(__before.base());
711  __tmp != __last.base(); ++__tmp)
712  {
713  _GLIBCXX_DEBUG_VERIFY(__tmp != __list._M_base().end(),
714  _M_message(__gnu_debug::__msg_valid_range2)
715  ._M_sequence(__list, "list")
716  ._M_iterator(__before, "before")
717  ._M_iterator(__last, "last"));
718  _GLIBCXX_DEBUG_VERIFY(__listptr != this || __tmp != __pos.base(),
719  _M_message(__gnu_debug::__msg_splice_overlap)
720  ._M_iterator(__tmp, "position")
721  ._M_iterator(__before, "before")
722  ._M_iterator(__last, "last"));
723  // _GLIBCXX_RESOLVE_LIB_DEFECTS
724  // 250. splicing invalidates iterators
725  this->_M_transfer_from_if(__list, [__tmp](_Base_const_iterator __it)
726  { return __it == __tmp; });
727  }
728 
729  _Base::splice_after(__pos.base(), std::move(__list),
730  __before.base(), __last.base());
731  }
732 
733  void
734  splice_after(const_iterator __pos, forward_list& __list,
735  const_iterator __before, const_iterator __last)
736  { splice_after(__pos, std::move(__list), __before, __last); }
737 
738  private:
739 #if __cplusplus > 201703L
740  using __remove_return_type = size_type;
741 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \
742  __attribute__((__abi_tag__("__cxx20")))
743 # define _GLIBCXX20_ONLY(__expr) __expr
744 #else
745  using __remove_return_type = void;
746 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
747 # define _GLIBCXX20_ONLY(__expr)
748 #endif
749 
750  public:
751  _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
752  __remove_return_type
753  remove(const _Tp& __val)
754  {
755  if (!this->_M_iterators && !this->_M_const_iterators)
756  return _Base::remove(__val);
757 
758  size_type __removed __attribute__((__unused__)) = 0;
759  _Base __to_destroy(get_allocator());
760  _Base_const_iterator __x = _Base::cbefore_begin();
761  _Base_const_iterator __old = __x++;
762  while (__x != _Base::cend())
763  {
764  if (*__x == __val)
765  {
766  _Base_const_iterator __next = std::next(__old);
767  this->_M_invalidate_if([__next](_Base_const_iterator __it)
768  { return __it == __next; });
769  __to_destroy.splice_after(__to_destroy.cbefore_begin(),
770  *this, __old);
771  __x = __old;
772  _GLIBCXX20_ONLY( __removed++ );
773  }
774 
775  __old = __x++;
776  }
777 
778  return _GLIBCXX20_ONLY( __removed );
779  }
780 
781  template<typename _Pred>
782  __remove_return_type
783  remove_if(_Pred __pred)
784  {
785  if (!this->_M_iterators && !this->_M_const_iterators)
786  return _Base::remove_if(__pred);
787 
788  size_type __removed __attribute__((__unused__)) = 0;
789  _Base __to_destroy(get_allocator());
790  _Base_iterator __x = _Base::before_begin();
791  _Base_iterator __old = __x++;
792  while (__x != _Base::end())
793  {
794  if (__pred(*__x))
795  {
796  this->_M_invalidate_if([__x](_Base_const_iterator __it)
797  { return __it == __x; });
798  __to_destroy.splice_after(__to_destroy.cbefore_begin(),
799  *this, __old);
800  __x = __old;
801  _GLIBCXX20_ONLY( __removed++ );
802  }
803 
804  __old = __x++;
805  }
806 
807  return _GLIBCXX20_ONLY( __removed );
808  }
809 
810  _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
811  __remove_return_type
812  unique()
813  { return unique(std::equal_to<_Tp>()); }
814 
815  template<typename _BinPred>
816  __remove_return_type
817  unique(_BinPred __binary_pred)
818  {
819  if (!this->_M_iterators && !this->_M_const_iterators)
820  return _Base::unique(__binary_pred);
821 
822  _Base_const_iterator __first = _Base::cbegin();
823  _Base_const_iterator __last = _Base::cend();
824  if (__first == __last)
825  return _GLIBCXX20_ONLY(0);
826 
827  size_type __removed __attribute__((__unused__)) = 0;
828  _Base __to_destroy(get_allocator());
829  _Base_const_iterator __next = std::next(__first);
830  while (__next != __last)
831  {
832  if (__binary_pred(*__first, *__next))
833  {
834  this->_M_invalidate_if([__next](_Base_const_iterator __it)
835  { return __it == __next; });
836  __to_destroy.splice_after(__to_destroy.cbefore_begin(),
837  *this, __first);
838  __next = __first;
839  _GLIBCXX20_ONLY( __removed++ );
840  }
841 
842  __first = __next++;
843  }
844 
845  return _GLIBCXX20_ONLY( __removed );
846  }
847 
848 #undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
849 #undef _GLIBCXX20_ONLY
850 
851  void
852  merge(forward_list&& __list)
853  {
854  if (this != std::__addressof(__list))
855  {
856  __glibcxx_check_sorted(_Base::begin(), _Base::end());
857  __glibcxx_check_sorted(__list._M_base().begin(),
858  __list._M_base().end());
859  this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it)
860  {
861  return __it != __list._M_base().cbefore_begin()
862  && __it != __list._M_base().cend();
863  });
864  _Base::merge(std::move(__list));
865  }
866  }
867 
868  void
869  merge(forward_list& __list)
870  { merge(std::move(__list)); }
871 
872  template<typename _Comp>
873  void
874  merge(forward_list&& __list, _Comp __comp)
875  {
876  if (this != std::__addressof(__list))
877  {
878  __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
879  __glibcxx_check_sorted_pred(__list._M_base().begin(),
880  __list._M_base().end(), __comp);
881  this->_M_transfer_from_if(__list,
882  [&__list](_Base_const_iterator __it)
883  {
884  return __it != __list._M_base().cbefore_begin()
885  && __it != __list._M_base().cend();
886  });
887  _Base::merge(std::move(__list), __comp);
888  }
889  }
890 
891  template<typename _Comp>
892  void
893  merge(forward_list& __list, _Comp __comp)
894  { merge(std::move(__list), __comp); }
895 
896  using _Base::sort;
897  using _Base::reverse;
898 
899  _Base&
900  _M_base() noexcept { return *this; }
901 
902  const _Base&
903  _M_base() const noexcept { return *this; }
904  };
905 
906 #if __cpp_deduction_guides >= 201606
907  template<typename _InputIterator, typename _ValT
908  = typename iterator_traits<_InputIterator>::value_type,
909  typename _Allocator = allocator<_ValT>,
910  typename = _RequireInputIter<_InputIterator>,
911  typename = _RequireAllocator<_Allocator>>
912  forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator())
913  -> forward_list<_ValT, _Allocator>;
914 
915  template<typename _Tp, typename _Allocator = allocator<_Tp>,
916  typename = _RequireAllocator<_Allocator>>
917  forward_list(size_t, _Tp, _Allocator = _Allocator())
918  -> forward_list<_Tp, _Allocator>;
919 
920 #if __glibcxx_containers_ranges // C++ >= 23
921  template<ranges::input_range _Rg,
922  typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
923  forward_list(from_range_t, _Rg&&, _Allocator = _Allocator())
924  -> forward_list<ranges::range_value_t<_Rg>, _Allocator>;
925 #endif
926 #endif
927 
928  template<typename _Tp, typename _Alloc>
929  bool
930  operator==(const forward_list<_Tp, _Alloc>& __lx,
931  const forward_list<_Tp, _Alloc>& __ly)
932  { return __lx._M_base() == __ly._M_base(); }
933 
934 #if __cpp_lib_three_way_comparison
935  template<typename _Tp, typename _Alloc>
936  constexpr __detail::__synth3way_t<_Tp>
937  operator<=>(const forward_list<_Tp, _Alloc>& __x,
938  const forward_list<_Tp, _Alloc>& __y)
939  { return __x._M_base() <=> __y._M_base(); }
940 #else
941  template<typename _Tp, typename _Alloc>
942  inline bool
943  operator<(const forward_list<_Tp, _Alloc>& __lx,
944  const forward_list<_Tp, _Alloc>& __ly)
945  { return __lx._M_base() < __ly._M_base(); }
946 
947  template<typename _Tp, typename _Alloc>
948  inline bool
949  operator!=(const forward_list<_Tp, _Alloc>& __lx,
950  const forward_list<_Tp, _Alloc>& __ly)
951  { return !(__lx == __ly); }
952 
953  /// Based on operator<
954  template<typename _Tp, typename _Alloc>
955  inline bool
956  operator>(const forward_list<_Tp, _Alloc>& __lx,
957  const forward_list<_Tp, _Alloc>& __ly)
958  { return (__ly < __lx); }
959 
960  /// Based on operator<
961  template<typename _Tp, typename _Alloc>
962  inline bool
963  operator>=(const forward_list<_Tp, _Alloc>& __lx,
964  const forward_list<_Tp, _Alloc>& __ly)
965  { return !(__lx < __ly); }
966 
967  /// Based on operator<
968  template<typename _Tp, typename _Alloc>
969  inline bool
970  operator<=(const forward_list<_Tp, _Alloc>& __lx,
971  const forward_list<_Tp, _Alloc>& __ly)
972  { return !(__ly < __lx); }
973 #endif // three-way comparison
974 
975  /// See std::forward_list::swap().
976  template<typename _Tp, typename _Alloc>
977  inline void
978  swap(forward_list<_Tp, _Alloc>& __lx, forward_list<_Tp, _Alloc>& __ly)
979  noexcept(noexcept(__lx.swap(__ly)))
980  { __lx.swap(__ly); }
981 
982 } // namespace __debug
983 } // namespace std
984 
985 namespace __gnu_debug
986 {
987  template<typename _Tp, typename _Alloc>
988  struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> >
989  {
990  typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence;
991 
992  template<typename _Iterator>
993  static bool
994  _S_Is(const _Safe_iterator<_Iterator, _Sequence>& __it)
995  {
996  return
997  __it.base() == __it._M_get_sequence()->_M_base().before_begin();
998  }
999 
1000  template<typename _Iterator>
1001  static bool
1002  _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it)
1003  { return _S_Is(__it); }
1004  };
1005 
1006  template<typename _Tp, typename _Alloc>
1007  struct _Sequence_traits<std::__debug::forward_list<_Tp, _Alloc> >
1008  {
1009  typedef typename std::__debug::forward_list<_Tp, _Alloc>::iterator _It;
1010 
1011  static typename _Distance_traits<_It>::__type
1012  _S_size(const std::__debug::forward_list<_Tp, _Alloc>& __seq)
1013  {
1014  return __seq.empty()
1015  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
1016  }
1017  };
1018 
1019 #ifndef _GLIBCXX_DEBUG_PEDANTIC
1020  template<class _Tp, class _Alloc>
1021  struct _Insert_range_from_self_is_safe<
1022  std::__debug::forward_list<_Tp, _Alloc> >
1023  { enum { __value = 1 }; };
1024 #endif
1025 }
1026 
1027 #endif