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>
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
53namespace __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
184namespace std _GLIBCXX_VISIBILITY(default)
185{
186namespace __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} // namespace std
985
986namespace __gnu_debug
987{
988 template<typename _Tp, typename _Alloc>
989 struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> >
990 {
991 typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence;
992
993 template<typename _Iterator>
994 static bool
995 _S_Is(const _Safe_iterator<_Iterator, _Sequence>& __it)
996 {
997 return
998 __it.base() == __it._M_get_sequence()->_M_base().before_begin();
999 }
1000
1001 template<typename _Iterator>
1002 static bool
1003 _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it)
1004 { return _S_Is(__it); }
1005 };
1006
1007 template<typename _Tp, typename _Alloc>
1008 struct _Sequence_traits<std::__debug::forward_list<_Tp, _Alloc> >
1009 {
1010 typedef typename std::__debug::forward_list<_Tp, _Alloc>::iterator _It;
1011
1012 static typename _Distance_traits<_It>::__type
1013 _S_size(const std::__debug::forward_list<_Tp, _Alloc>& __seq)
1014 {
1015 return __seq.empty()
1016 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
1017 }
1018 };
1019
1020#ifndef _GLIBCXX_DEBUG_PEDANTIC
1021 template<class _Tp, class _Alloc>
1022 struct _Insert_range_from_self_is_safe<
1023 std::__debug::forward_list<_Tp, _Alloc> >
1024 { enum { __value = 1 }; };
1025#endif
1026}
1027
1028#endif
__glibcxx_check_insert_after
#define __glibcxx_check_insert_after(_Position)
Definition macros.h:160
__glibcxx_check_erase_after
#define __glibcxx_check_erase_after(_Position)
Definition macros.h:231
__glibcxx_check_sorted_pred
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
Definition macros.h:356
__glibcxx_check_insert_range_after
#define __glibcxx_check_insert_range_after(_Position, _First, _Last, _Dist)
Definition macros.h:196
__glibcxx_check_erase_range_after
#define __glibcxx_check_erase_range_after(_First, _Last)
Definition macros.h:257
std::chrono::operator<=
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
std::chrono::operator>=
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
std::chrono::operator>
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
std::make_pair
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition stl_pair.h:1166
std::declval
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2672
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:52
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
std
ISO C++ entities toplevel namespace is std.
__gnu_debug
GNU debug classes for public use.
Definition boost_concept_check.h:60
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition helper_functions.h:320
std::__debug
GNU debug code, replaces standard behavior with debug behavior.
std::initializer_list
initializer_list
Definition initializer_list:48
std::is_nothrow_constructible
is_nothrow_constructible
Definition type_traits:1274
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition safe_iterator.h:133
__gnu_debug::_Safe_iterator::base
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Definition safe_iterator.h:433
__gnu_debug::_Safe_iterator::_M_dereferenceable
bool _M_dereferenceable() const
Is the iterator dereferenceable?
Definition safe_iterator.h:458
__gnu_debug::_Safe_iterator::_M_before_dereferenceable
bool _M_before_dereferenceable() const
Is the iterator before a dereferenceable one?
Definition safe_iterator.h:463
__gnu_debug::_Safe_iterator::_M_is_before_begin
bool _M_is_before_begin() const
Is this iterator equal to the sequence's before_begin() iterator if any?
Definition safe_iterator.h:537
std::forward_list
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition forward_list.h:768
std::ranges::subrange
The ranges::subrange class template.
Definition ranges_util.h:270
std::equal_to
One of the comparison functors.
Definition stl_function.h:371
std::iterator_traits
Traits class for iterators.
Definition stl_iterator_base_types.h:180
__gnu_debug::_Safe_sequence
Base class for constructing a safe sequence type that tracks iterators that reference it.
Definition safe_sequence.h:109
__gnu_debug::_Safe_sequence< _SafeSequence >::_M_invalidate_if
void _M_invalidate_if(_Predicate __pred) const
Definition safe_sequence.tcc:38
__gnu_debug::_Safe_iterator_base
Basic functionality for a safe iterator.
Definition safe_base.h:51
__gnu_debug::_Safe_iterator_base::_M_attached_to
bool _M_attached_to(const _Safe_sequence_base *__seq) const
Definition safe_base.h:161
__gnu_debug::_Safe_iterator_base::_M_sequence
const _Safe_sequence_base * _M_sequence
Definition safe_base.h:59
__gnu_debug::_Safe_iterator_base::_M_prior
_Safe_iterator_base * _M_prior
Definition safe_base.h:72
__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:43
std::__debug::forward_list
Class std::forward_list with safety/checking/debug instrumentation.
Definition debug/forward_list:194
__gnu_debug::_Safe_forward_list
Special iterators swap and invalidation for forward_list because of the before_begin iterator.
Definition debug/forward_list:60