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>
37namespace 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>
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
53namespace __gnu_debug
54{
55 /// Special iterators swap and invalidation for forward_list because of the
56 /// before_begin iterator.
57 template<typename _SafeSequence>
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,
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
91 _Safe_iterator_base*& __lhs_iterators,
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
185namespace std _GLIBCXX_VISIBILITY(default)
186{
187namespace __debug
188{
189 /// Class std::forward_list with safety/checking/debug instrumentation.
190 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
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;
199
200 typedef typename _Base::iterator _Base_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
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(
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())
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
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
291 operator=(const forward_list&) = default;
292
294 operator=(forward_list&&) = default;
295
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 {
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,
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__]]
374 before_begin() noexcept
375 { return { _Base::before_begin(), this }; }
376
377 [[__nodiscard__]]
379 before_begin() const noexcept
380 { return { _Base::before_begin(), this }; }
381
382 [[__nodiscard__]]
384 begin() noexcept
385 { return { _Base::begin(), this }; }
386
387 [[__nodiscard__]]
389 begin() const noexcept
390 { return { _Base::begin(), this }; }
391
392 [[__nodiscard__]]
394 end() noexcept
395 { return { _Base::end(), this }; }
396
397 [[__nodiscard__]]
399 end() const noexcept
400 { return { _Base::end(), this }; }
401
402 [[__nodiscard__]]
404 cbegin() const noexcept
405 { return { _Base::cbegin(), this }; }
406
407 [[__nodiscard__]]
409 cbefore_begin() const noexcept
410 { return { _Base::cbefore_begin(), this }; }
411
412 [[__nodiscard__]]
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>
458 emplace_after(const_iterator __pos, _Args&&... __args)
459 {
461 return { _Base::emplace_after(__pos.base(),
462 std::forward<_Args>(__args)...),
463 this };
464 }
465
467 insert_after(const_iterator __pos, const _Tp& __val)
468 {
470 return { _Base::insert_after(__pos.base(), __val), this };
471 }
472
474 insert_after(const_iterator __pos, _Tp&& __val)
475 {
477 return { _Base::insert_after(__pos.base(), std::move(__val)), this };
478 }
479
481 insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
482 {
484 return { _Base::insert_after(__pos.base(), __n, __val), this };
485 }
486
487 template<typename _InputIterator,
488 typename = std::_RequireInputIter<_InputIterator>>
490 insert_after(const_iterator __pos,
491 _InputIterator __first, _InputIterator __last)
492 {
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
509 insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
510 {
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>
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
528 erase_after(const_iterator __pos)
529 {
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
539 erase_after(const_iterator __pos, const_iterator __last)
540 {
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 {
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 {
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 {
687 auto __listptr = std::__addressof(__list);
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
909 typename _Allocator = allocator<_ValT>,
910 typename = _RequireInputIter<_InputIterator>,
911 typename = _RequireAllocator<_Allocator>>
912 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator())
914
915 template<typename _Tp, typename _Allocator = allocator<_Tp>,
916 typename = _RequireAllocator<_Allocator>>
917 forward_list(size_t, _Tp, _Allocator = _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())
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
979 noexcept(noexcept(__lx.swap(__ly)))
980 { __lx.swap(__ly); }
981
982} // namespace __debug
983} // namespace std
984
985namespace __gnu_debug
986{
987 template<typename _Tp, typename _Alloc>
988 struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> >
989 {
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 {
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
#define __glibcxx_check_insert_after(_Position)
Definition macros.h:160
#define __glibcxx_check_erase_after(_Position)
Definition macros.h:231
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
Definition macros.h:356
#define __glibcxx_check_insert_range_after(_Position, _First, _Last, _Dist)
Definition macros.h:196
#define __glibcxx_check_erase_range_after(_First, _Last)
Definition macros.h:257
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
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:52
ISO C++ entities toplevel namespace is std.
GNU extensions for public use.
GNU debug classes for public use.
constexpr _Iterator __base(_Iterator __it)
initializer_list
is_nothrow_constructible
Definition type_traits:1236
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
Safe iterator wrapper.
constexpr _Iterator & base() noexcept
Return the underlying iterator.
bool _M_dereferenceable() const
Is the iterator dereferenceable?
bool _M_before_dereferenceable() const
Is the iterator before a dereferenceable one?
bool _M_is_before_begin() const
Is this iterator equal to the sequence's before_begin() iterator if any?
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
The ranges::subrange class template.
One of the comparison functors.
Struct holding two objects of arbitrary type.
Definition stl_pair.h:304
_T2 second
The second member.
Definition stl_pair.h:309
Traits class for iterators.
Base class for constructing a safe sequence type that tracks iterators that reference it.
Basic functionality for a safe iterator.
Definition safe_base.h:51
_Safe_sequence_base * _M_sequence
Definition safe_base.h:57
bool _M_attached_to(const _Safe_sequence_base *__seq) const
Definition safe_base.h:145
_Safe_iterator_base * _M_prior
Definition safe_base.h:70
_Safe_iterator_base * _M_next
Definition safe_base.h:74
Base class that supports tracking of iterators that reference a sequence.
Definition safe_base.h:203
Safe class dealing with some allocator dependent operations.
Class std::forward_list with safety/checking/debug instrumentation.
Special iterators swap and invalidation for forward_list because of the before_begin iterator.
Scoped lock idiom.