1// Debugging list implementation -*- C++ -*-
3// Copyright (C) 2003-2024 Free Software Foundation, Inc.
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)
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.
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.
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/>.
26 * This file is a GNU debug extension to the Standard C++ Library.
29#ifndef _GLIBCXX_DEBUG_LIST
30#define _GLIBCXX_DEBUG_LIST 1
33#pragma GCC system_header
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
42#include <debug/safe_sequence.h>
43#include <debug/safe_container.h>
44#include <debug/safe_iterator.h>
46namespace std _GLIBCXX_VISIBILITY(default)
50 /// Class std::list with safety/checking/debug instrumentation.
51 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
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>
58 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
59 typedef __gnu_debug::_Safe_container<
60 list, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
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;
67 template<typename _ItT, typename _SeqT, typename _CatT>
68 friend class ::__gnu_debug::_Safe_iterator;
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.
75 _Base_ref(const _Base& __r) : _M_ref(__r) { }
81 typedef typename _Base::reference reference;
82 typedef typename _Base::const_reference const_reference;
84 typedef __gnu_debug::_Safe_iterator<_Base_iterator, list>
86 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
89 typedef typename _Base::size_type size_type;
90 typedef typename _Base::difference_type difference_type;
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;
99 // 23.2.2.1 construct/copy/destroy:
101#if __cplusplus < 201103L
105 list(const list& __x)
111 list(const list&) = default;
112 list(list&&) = default;
114 list(initializer_list<value_type> __l,
115 const allocator_type& __a = allocator_type())
116 : _Base(__l, __a) { }
120 list(const list& __x, const __type_identity_t<allocator_type>& __a)
121 : _Base(__x, __a) { }
123 list(list&& __x, const __type_identity_t<allocator_type>& __a)
125 std::is_nothrow_constructible<_Base,
126 _Base, const allocator_type&>::value )
127 : _Safe(std::move(__x), __a),
128 _Base(std::move(__x), __a) { }
132 list(const _Allocator& __a) _GLIBCXX_NOEXCEPT
135#if __cplusplus >= 201103L
137 list(size_type __n, const allocator_type& __a = allocator_type())
138 : _Base(__n, __a) { }
140 list(size_type __n, const __type_identity_t<_Tp>& __value,
141 const _Allocator& __a = _Allocator())
142 : _Base(__n, __value, __a) { }
145 list(size_type __n, const _Tp& __value = _Tp(),
146 const _Allocator& __a = _Allocator())
147 : _Base(__n, __value, __a) { }
150#if __cplusplus >= 201103L
151 template<class _InputIterator,
152 typename = std::_RequireInputIter<_InputIterator>>
154 template<class _InputIterator>
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)
163#if __glibcxx_ranges_to_container // 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)
171 : _Base(__x._M_ref) { }
173#if __cplusplus >= 201103L
175 operator=(const list&) = default;
178 operator=(list&&) = default;
181 operator=(initializer_list<value_type> __l)
183 this->_M_invalidate_all();
184 _Base::operator=(__l);
189 assign(initializer_list<value_type> __l)
192 this->_M_invalidate_all();
196#if __cplusplus >= 201103L
197 template<class _InputIterator,
198 typename = std::_RequireInputIter<_InputIterator>>
200 template<class _InputIterator>
203 assign(_InputIterator __first, _InputIterator __last)
205 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
206 __glibcxx_check_valid_range2(__first, __last, __dist);
208 if (__dist.second >= __gnu_debug::__dp_sign)
209 _Base::assign(__gnu_debug::__unsafe(__first),
210 __gnu_debug::__unsafe(__last));
212 _Base::assign(__first, __last);
214 this->_M_invalidate_all();
217#if __glibcxx_ranges_to_container // C++ >= 23
218 template<__detail::__container_compatible_range<_Tp> _Rg>
220 assign_range(_Rg&& __rg)
222 // Have to reimplement this function, so that we use the debug
223 // version of erase, which invalidates the correct iterators.
225 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
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));
238 _Base::insert_range(__last1,
239 ranges::subrange(std::move(__first2), __last2));
244 assign(size_type __n, const _Tp& __t)
246 _Base::assign(__n, __t);
247 this->_M_invalidate_all();
250 using _Base::get_allocator;
255 begin() _GLIBCXX_NOEXCEPT
256 { return iterator(_Base::begin(), this); }
260 begin() const _GLIBCXX_NOEXCEPT
261 { return const_iterator(_Base::begin(), this); }
265 end() _GLIBCXX_NOEXCEPT
266 { return iterator(_Base::end(), this); }
270 end() const _GLIBCXX_NOEXCEPT
271 { return const_iterator(_Base::end(), this); }
275 rbegin() _GLIBCXX_NOEXCEPT
276 { return reverse_iterator(end()); }
279 const_reverse_iterator
280 rbegin() const _GLIBCXX_NOEXCEPT
281 { return const_reverse_iterator(end()); }
285 rend() _GLIBCXX_NOEXCEPT
286 { return reverse_iterator(begin()); }
289 const_reverse_iterator
290 rend() const _GLIBCXX_NOEXCEPT
291 { return const_reverse_iterator(begin()); }
293#if __cplusplus >= 201103L
296 cbegin() const noexcept
297 { return const_iterator(_Base::begin(), this); }
301 cend() const noexcept
302 { return const_iterator(_Base::end(), this); }
305 const_reverse_iterator
306 crbegin() const noexcept
307 { return const_reverse_iterator(end()); }
310 const_reverse_iterator
311 crend() const noexcept
312 { return const_reverse_iterator(begin()); }
315 // 23.2.2.2 capacity:
318 using _Base::max_size;
320#if __cplusplus >= 201103L
322 resize(size_type __sz)
324 this->_M_detach_singular();
326 // if __sz < size(), invalidate all iterators in [begin + __sz, end())
327 _Base_iterator __victim = _Base::begin();
328 _Base_iterator __end = _Base::end();
329 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
332 for (; __victim != __end; ++__victim)
333 this->_M_invalidate_if(_Equal(__victim));
341 this->_M_revalidate_singular();
342 __throw_exception_again;
347 resize(size_type __sz, const _Tp& __c)
349 this->_M_detach_singular();
351 // if __sz < size(), invalidate all iterators in [begin + __sz, end())
352 _Base_iterator __victim = _Base::begin();
353 _Base_iterator __end = _Base::end();
354 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
357 for (; __victim != __end; ++__victim)
358 this->_M_invalidate_if(_Equal(__victim));
362 _Base::resize(__sz, __c);
366 this->_M_revalidate_singular();
367 __throw_exception_again;
372 resize(size_type __sz, _Tp __c = _Tp())
374 this->_M_detach_singular();
376 // if __sz < size(), invalidate all iterators in [begin + __sz, end())
377 _Base_iterator __victim = _Base::begin();
378 _Base_iterator __end = _Base::end();
379 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
382 for (; __victim != __end; ++__victim)
383 this->_M_invalidate_if(_Equal(__victim));
387 _Base::resize(__sz, __c);
391 this->_M_revalidate_singular();
392 __throw_exception_again;
400 front() _GLIBCXX_NOEXCEPT
402 __glibcxx_check_nonempty();
403 return _Base::front();
408 front() const _GLIBCXX_NOEXCEPT
410 __glibcxx_check_nonempty();
411 return _Base::front();
416 back() _GLIBCXX_NOEXCEPT
418 __glibcxx_check_nonempty();
419 return _Base::back();
424 back() const _GLIBCXX_NOEXCEPT
426 __glibcxx_check_nonempty();
427 return _Base::back();
430 // 23.2.2.3 modifiers:
431 using _Base::push_front;
433#if __cplusplus >= 201103L
434 using _Base::emplace_front;
437#if __glibcxx_ranges_to_container // C++ >= 23
438 using _Base::prepend_range;
439 using _Base::append_range;
443 pop_front() _GLIBCXX_NOEXCEPT
445 __glibcxx_check_nonempty();
446 this->_M_invalidate_if(_Equal(_Base::begin()));
450 using _Base::push_back;
452#if __cplusplus >= 201103L
453 using _Base::emplace_back;
457 pop_back() _GLIBCXX_NOEXCEPT
459 __glibcxx_check_nonempty();
460 this->_M_invalidate_if(_Equal(--_Base::end()));
464#if __cplusplus >= 201103L
465 template<typename... _Args>
467 emplace(const_iterator __position, _Args&&... __args)
469 __glibcxx_check_insert(__position);
470 return { _Base::emplace(__position.base(),
471 std::forward<_Args>(__args)...), this };
476#if __cplusplus >= 201103L
477 insert(const_iterator __position, const _Tp& __x)
479 insert(iterator __position, const _Tp& __x)
482 __glibcxx_check_insert(__position);
483 return iterator(_Base::insert(__position.base(), __x), this);
486#if __cplusplus >= 201103L
488 insert(const_iterator __position, _Tp&& __x)
489 { return emplace(__position, std::move(__x)); }
492 insert(const_iterator __p, initializer_list<value_type> __l)
494 __glibcxx_check_insert(__p);
495 return { _Base::insert(__p.base(), __l), this };
499#if __cplusplus >= 201103L
501 insert(const_iterator __position, size_type __n, const _Tp& __x)
503 __glibcxx_check_insert(__position);
504 return { _Base::insert(__position.base(), __n, __x), this };
508 insert(iterator __position, size_type __n, const _Tp& __x)
510 __glibcxx_check_insert(__position);
511 _Base::insert(__position.base(), __n, __x);
515#if __cplusplus >= 201103L
516 template<class _InputIterator,
517 typename = std::_RequireInputIter<_InputIterator>>
519 insert(const_iterator __position, _InputIterator __first,
520 _InputIterator __last)
522 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
523 __glibcxx_check_insert_range(__position, __first, __last, __dist);
524 if (__dist.second >= __gnu_debug::__dp_sign)
527 _Base::insert(__position.base(),
528 __gnu_debug::__unsafe(__first),
529 __gnu_debug::__unsafe(__last)),
533 return { _Base::insert(__position.base(), __first, __last), this };
536 template<class _InputIterator>
538 insert(iterator __position, _InputIterator __first,
539 _InputIterator __last)
541 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
542 __glibcxx_check_insert_range(__position, __first, __last, __dist);
544 if (__dist.second >= __gnu_debug::__dp_sign)
545 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
546 __gnu_debug::__unsafe(__last));
548 _Base::insert(__position.base(), __first, __last);
552#if __glibcxx_ranges_to_container // C++ >= 23
553 template<__detail::__container_compatible_range<_Tp> _Rg>
555 insert_range(const_iterator __position, _Rg&& __rg)
557 auto __ret = _Base::insert_range(__position.base(),
558 std::forward<_Rg>(__rg));
559 return { __ret, this };
565#if __cplusplus >= 201103L
566 _M_erase(_Base_const_iterator __position) noexcept
568 _M_erase(_Base_iterator __position)
571 this->_M_invalidate_if(_Equal(__position));
572 return _Base::erase(__position);
577#if __cplusplus >= 201103L
578 erase(const_iterator __position) noexcept
580 erase(iterator __position)
583 __glibcxx_check_erase(__position);
584 return iterator(_M_erase(__position.base()), this);
588#if __cplusplus >= 201103L
589 erase(const_iterator __first, const_iterator __last) noexcept
591 erase(iterator __first, iterator __last)
594 // _GLIBCXX_RESOLVE_LIB_DEFECTS
595 // 151. can't currently clear() empty container
596 __glibcxx_check_erase_range(__first, __last);
597 for (_Base_const_iterator __victim = __first.base();
598 __victim != __last.base(); ++__victim)
600 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
601 _M_message(__gnu_debug::__msg_valid_range)
602 ._M_iterator(__first, "position")
603 ._M_iterator(__last, "last"));
604 this->_M_invalidate_if(_Equal(__victim));
607 return iterator(_Base::erase(__first.base(), __last.base()), this);
612 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
619 clear() _GLIBCXX_NOEXCEPT
622 this->_M_invalidate_all();
625 // 23.2.2.4 list operations:
627#if __cplusplus >= 201103L
628 splice(const_iterator __position, list&& __x) noexcept
630 splice(iterator __position, list& __x)
633 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this,
634 _M_message(__gnu_debug::__msg_self_splice)
635 ._M_sequence(*this, "this"));
636 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
637 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x));
640#if __cplusplus >= 201103L
642 splice(const_iterator __position, list& __x) noexcept
643 { splice(__position, std::move(__x)); }
647#if __cplusplus >= 201103L
648 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
650 splice(iterator __position, list& __x, iterator __i)
653 __glibcxx_check_insert(__position);
655 // We used to perform the splice_alloc check: not anymore, redundant
656 // after implementing the relevant bits of N1599.
658 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
659 _M_message(__gnu_debug::__msg_splice_bad)
660 ._M_iterator(__i, "__i"));
661 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)),
662 _M_message(__gnu_debug::__msg_splice_other)
663 ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
665 // _GLIBCXX_RESOLVE_LIB_DEFECTS
666 // 250. splicing invalidates iterators
667 this->_M_transfer_from_if(__x, _Equal(__i.base()));
668 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
672#if __cplusplus >= 201103L
674 splice(const_iterator __position, list& __x, const_iterator __i) noexcept
675 { splice(__position, std::move(__x), __i); }
679#if __cplusplus >= 201103L
680 splice(const_iterator __position, list&& __x, const_iterator __first,
681 const_iterator __last) noexcept
683 splice(iterator __position, list& __x, iterator __first,
687 __glibcxx_check_insert(__position);
688 __glibcxx_check_valid_range(__first, __last);
689 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)),
690 _M_message(__gnu_debug::__msg_splice_other)
691 ._M_sequence(__x, "x")
692 ._M_iterator(__first, "first"));
694 // We used to perform the splice_alloc check: not anymore, redundant
695 // after implementing the relevant bits of N1599.
697 for (_Base_const_iterator __tmp = __first.base();
698 __tmp != __last.base(); ++__tmp)
700 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
701 _M_message(__gnu_debug::__msg_valid_range)
702 ._M_iterator(__first, "first")
703 ._M_iterator(__last, "last"));
704 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this
705 || __tmp != __position.base(),
706 _M_message(__gnu_debug::__msg_splice_overlap)
707 ._M_iterator(__tmp, "position")
708 ._M_iterator(__first, "first")
709 ._M_iterator(__last, "last"));
711 // _GLIBCXX_RESOLVE_LIB_DEFECTS
712 // 250. splicing invalidates iterators
713 this->_M_transfer_from_if(__x, _Equal(__tmp));
716 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
717 __first.base(), __last.base());
720#if __cplusplus >= 201103L
722 splice(const_iterator __position, list& __x,
723 const_iterator __first, const_iterator __last) noexcept
724 { splice(__position, std::move(__x), __first, __last); }
728#if __cplusplus > 201703L
729 typedef size_type __remove_return_type;
730# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
731 __attribute__((__abi_tag__("__cxx20")))
732# define _GLIBCXX20_ONLY(__expr) __expr
734 typedef void __remove_return_type;
735# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
736# define _GLIBCXX20_ONLY(__expr)
740 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
742 remove(const _Tp& __value)
744 if (!this->_M_iterators && !this->_M_const_iterators)
745 return _Base::remove(__value);
747#if !_GLIBCXX_USE_CXX11_ABI
748 size_type __removed __attribute__((__unused__)) = 0;
750 _Base __to_destroy(get_allocator());
751 _Base_iterator __first = _Base::begin();
752 _Base_iterator __last = _Base::end();
753 while (__first != __last)
755 _Base_iterator __next = __first;
757 if (*__first == __value)
759 // _GLIBCXX_RESOLVE_LIB_DEFECTS
760 // 526. Is it undefined if a function in the standard changes
762 this->_M_invalidate_if(_Equal(__first));
763 __to_destroy.splice(__to_destroy.begin(), *this, __first);
764#if !_GLIBCXX_USE_CXX11_ABI
765 _GLIBCXX20_ONLY( __removed++ );
772#if !_GLIBCXX_USE_CXX11_ABI
773 return _GLIBCXX20_ONLY( __removed );
775 return _GLIBCXX20_ONLY( __to_destroy.size() );
779 template<class _Predicate>
781 remove_if(_Predicate __pred)
783 if (!this->_M_iterators && !this->_M_const_iterators)
784 return _Base::remove_if(__pred);
786#if !_GLIBCXX_USE_CXX11_ABI
787 size_type __removed __attribute__((__unused__)) = 0;
789 _Base __to_destroy(get_allocator());
790 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
792 _Base_iterator __next = __x;
796 this->_M_invalidate_if(_Equal(__x));
797 __to_destroy.splice(__to_destroy.begin(), *this, __x);
798#if !_GLIBCXX_USE_CXX11_ABI
799 _GLIBCXX20_ONLY( __removed++ );
806#if !_GLIBCXX_USE_CXX11_ABI
807 return _GLIBCXX20_ONLY( __removed );
809 return _GLIBCXX20_ONLY( __to_destroy.size() );
813 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
817 if (!this->_M_iterators && !this->_M_const_iterators)
818 return _Base::unique();
821 return _GLIBCXX20_ONLY(0);
823#if !_GLIBCXX_USE_CXX11_ABI
824 size_type __removed __attribute__((__unused__)) = 0;
826 _Base __to_destroy(get_allocator());
827 _Base_iterator __first = _Base::begin();
828 _Base_iterator __last = _Base::end();
829 _Base_iterator __next = __first;
830 while (++__next != __last)
831 if (*__first == *__next)
833 this->_M_invalidate_if(_Equal(__next));
834 __to_destroy.splice(__to_destroy.begin(), *this, __next);
836#if !_GLIBCXX_USE_CXX11_ABI
837 _GLIBCXX20_ONLY( __removed++ );
843#if !_GLIBCXX_USE_CXX11_ABI
844 return _GLIBCXX20_ONLY( __removed );
846 return _GLIBCXX20_ONLY( __to_destroy.size() );
850 template<class _BinaryPredicate>
852 unique(_BinaryPredicate __binary_pred)
854 if (!this->_M_iterators && !this->_M_const_iterators)
855 return _Base::unique(__binary_pred);
858 return _GLIBCXX20_ONLY(0);
861#if !_GLIBCXX_USE_CXX11_ABI
862 size_type __removed __attribute__((__unused__)) = 0;
864 _Base __to_destroy(get_allocator());
865 _Base_iterator __first = _Base::begin();
866 _Base_iterator __last = _Base::end();
867 _Base_iterator __next = __first;
868 while (++__next != __last)
869 if (__binary_pred(*__first, *__next))
871 this->_M_invalidate_if(_Equal(__next));
872 __to_destroy.splice(__to_destroy.begin(), *this, __next);
874#if !_GLIBCXX_USE_CXX11_ABI
875 _GLIBCXX20_ONLY( __removed++ );
881#if !_GLIBCXX_USE_CXX11_ABI
882 return _GLIBCXX20_ONLY( __removed );
884 return _GLIBCXX20_ONLY( __to_destroy.size() );
888#undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
889#undef _GLIBCXX20_ONLY
892#if __cplusplus >= 201103L
898 // _GLIBCXX_RESOLVE_LIB_DEFECTS
899 // 300. list::merge() specification incomplete
900 if (this != std::__addressof(__x))
902 __glibcxx_check_sorted(_Base::begin(), _Base::end());
903 __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
904 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
905 _Base::merge(_GLIBCXX_MOVE(__x));
909#if __cplusplus >= 201103L
912 { merge(std::move(__x)); }
915 template<class _Compare>
917#if __cplusplus >= 201103L
918 merge(list&& __x, _Compare __comp)
920 merge(list& __x, _Compare __comp)
923 // _GLIBCXX_RESOLVE_LIB_DEFECTS
924 // 300. list::merge() specification incomplete
925 if (this != std::__addressof(__x))
927 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
929 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
931 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
932 _Base::merge(_GLIBCXX_MOVE(__x), __comp);
936#if __cplusplus >= 201103L
937 template<typename _Compare>
939 merge(list& __x, _Compare __comp)
940 { merge(std::move(__x), __comp); }
944 sort() { _Base::sort(); }
946 template<typename _StrictWeakOrdering>
948 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
950 using _Base::reverse;
953 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
956 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
959#if __cpp_deduction_guides >= 201606
960 template<typename _InputIterator, typename _ValT
961 = typename iterator_traits<_InputIterator>::value_type,
962 typename _Allocator = allocator<_ValT>,
963 typename = _RequireInputIter<_InputIterator>,
964 typename = _RequireAllocator<_Allocator>>
965 list(_InputIterator, _InputIterator, _Allocator = _Allocator())
966 -> list<_ValT, _Allocator>;
968 template<typename _Tp, typename _Allocator = allocator<_Tp>,
969 typename = _RequireAllocator<_Allocator>>
970 list(size_t, _Tp, _Allocator = _Allocator())
971 -> list<_Tp, _Allocator>;
973#if __glibcxx_ranges_to_container // C++ >= 23
974 template<ranges::input_range _Rg,
975 typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
976 list(from_range_t, _Rg&&, _Allocator = _Allocator())
977 -> list<ranges::range_value_t<_Rg>, _Allocator>;
981 template<typename _Tp, typename _Alloc>
983 operator==(const list<_Tp, _Alloc>& __lhs,
984 const list<_Tp, _Alloc>& __rhs)
985 { return __lhs._M_base() == __rhs._M_base(); }
987#if __cpp_lib_three_way_comparison
988 template<typename _Tp, typename _Alloc>
989 constexpr __detail::__synth3way_t<_Tp>
990 operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
991 { return __x._M_base() <=> __y._M_base(); }
993 template<typename _Tp, typename _Alloc>
995 operator!=(const list<_Tp, _Alloc>& __lhs,
996 const list<_Tp, _Alloc>& __rhs)
997 { return __lhs._M_base() != __rhs._M_base(); }
999 template<typename _Tp, typename _Alloc>
1001 operator<(const list<_Tp, _Alloc>& __lhs,
1002 const list<_Tp, _Alloc>& __rhs)
1003 { return __lhs._M_base() < __rhs._M_base(); }
1005 template<typename _Tp, typename _Alloc>
1007 operator<=(const list<_Tp, _Alloc>& __lhs,
1008 const list<_Tp, _Alloc>& __rhs)
1009 { return __lhs._M_base() <= __rhs._M_base(); }
1011 template<typename _Tp, typename _Alloc>
1013 operator>=(const list<_Tp, _Alloc>& __lhs,
1014 const list<_Tp, _Alloc>& __rhs)
1015 { return __lhs._M_base() >= __rhs._M_base(); }
1017 template<typename _Tp, typename _Alloc>
1019 operator>(const list<_Tp, _Alloc>& __lhs,
1020 const list<_Tp, _Alloc>& __rhs)
1021 { return __lhs._M_base() > __rhs._M_base(); }
1022#endif // three-way comparison
1024 template<typename _Tp, typename _Alloc>
1026 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
1027 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
1028 { __lhs.swap(__rhs); }
1030} // namespace __debug
1033namespace __gnu_debug
1035#ifndef _GLIBCXX_USE_CXX11_ABI
1036 // If not using C++11 list::size() is not in O(1) so we do not use it.
1037 template<typename _Tp, typename _Alloc>
1038 struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
1040 typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It;
1042 static typename _Distance_traits<_It>::__type
1043 _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
1045 return __seq.empty()
1046 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
1051#ifndef _GLIBCXX_DEBUG_PEDANTIC
1052 template<class _Tp, class _Alloc>
1053 struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
1054 { enum { __value = 1 }; };