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