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