29#ifndef _GLIBCXX_DEBUG_LIST
30#define _GLIBCXX_DEBUG_LIST 1
32#pragma GCC system_header
35namespace std _GLIBCXX_VISIBILITY(default) {
namespace __debug {
36 template<
typename _Tp,
typename _Allocator>
class list;
44namespace std _GLIBCXX_VISIBILITY(default)
49 template<
typename _Tp,
typename _Allocator = std::allocator<_Tp> >
52 list<_Tp, _Allocator>, _Allocator,
53 __gnu_debug::_Safe_node_sequence>,
54 public _GLIBCXX_STD_C::list<_Tp, _Allocator>
56 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator>
_Base;
65 template<
typename _ItT,
typename _SeqT,
typename _CatT>
66 friend class ::__gnu_debug::_Safe_iterator;
73 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
79 typedef typename _Base::reference reference;
80 typedef typename _Base::const_reference const_reference;
87 typedef typename _Base::size_type size_type;
88 typedef typename _Base::difference_type difference_type;
90 typedef _Tp value_type;
91 typedef _Allocator allocator_type;
92 typedef typename _Base::pointer pointer;
93 typedef typename _Base::const_pointer const_pointer;
99#if __cplusplus < 201103L
113 const allocator_type& __a = allocator_type())
114 :
_Base(__l, __a) { }
118 list(
const list& __x,
const allocator_type& __a)
119 :
_Base(__x, __a) { }
121 list(
list&& __x,
const allocator_type& __a)
124 _Base,
const allocator_type&>::value )
130 list(
const _Allocator& __a) _GLIBCXX_NOEXCEPT
133#if __cplusplus >= 201103L
135 list(size_type __n,
const allocator_type& __a = allocator_type())
136 :
_Base(__n, __a) { }
138 list(size_type __n,
const __type_identity_t<_Tp>& __value,
139 const _Allocator& __a = _Allocator())
140 :
_Base(__n, __value, __a) { }
143 list(size_type __n,
const _Tp& __value = _Tp(),
144 const _Allocator& __a = _Allocator())
145 :
_Base(__n, __value, __a) { }
148#if __cplusplus >= 201103L
149 template<
class _InputIterator,
150 typename = std::_RequireInputIter<_InputIterator>>
152 template<
class _InputIterator>
154 list(_InputIterator __first, _InputIterator __last,
155 const _Allocator& __a = _Allocator())
157 __glibcxx_check_valid_constructor_range(__first, __last)),
162 :
_Base(__x._M_ref) { }
164#if __cplusplus < 201103L
166 operator=(
const list& __x)
168 this->_M_safe() = __x;
174 operator=(
const list&) =
default;
177 operator=(
list&&) =
default;
182 this->_M_invalidate_all();
191 this->_M_invalidate_all();
195#if __cplusplus >= 201103L
196 template<
class _InputIterator,
197 typename = std::_RequireInputIter<_InputIterator>>
199 template<
class _InputIterator>
202 assign(_InputIterator __first, _InputIterator __last)
205 __glibcxx_check_valid_range2(__first, __last, __dist);
207 if (__dist.
second >= __gnu_debug::__dp_sign)
208 _Base::assign(__gnu_debug::__unsafe(__first),
209 __gnu_debug::__unsafe(__last));
211 _Base::assign(__first, __last);
213 this->_M_invalidate_all();
217 assign(size_type __n,
const _Tp& __t)
219 _Base::assign(__n, __t);
220 this->_M_invalidate_all();
223 using _Base::get_allocator;
227 begin() _GLIBCXX_NOEXCEPT
228 {
return iterator(_Base::begin(),
this); }
231 begin()
const _GLIBCXX_NOEXCEPT
235 end() _GLIBCXX_NOEXCEPT
236 {
return iterator(_Base::end(),
this); }
239 end()
const _GLIBCXX_NOEXCEPT
243 rbegin() _GLIBCXX_NOEXCEPT
247 rbegin()
const _GLIBCXX_NOEXCEPT
251 rend() _GLIBCXX_NOEXCEPT
255 rend()
const _GLIBCXX_NOEXCEPT
258#if __cplusplus >= 201103L
260 cbegin()
const noexcept
264 cend()
const noexcept
268 crbegin()
const noexcept
272 crend()
const noexcept
279 using _Base::max_size;
281#if __cplusplus >= 201103L
283 resize(size_type __sz)
288 _Base_iterator __victim = _Base::begin();
290 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
293 for (; __victim != __end; ++__victim)
303 __throw_exception_again;
308 resize(size_type __sz,
const _Tp& __c)
313 _Base_iterator __victim = _Base::begin();
315 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
318 for (; __victim != __end; ++__victim)
323 _Base::resize(__sz, __c);
328 __throw_exception_again;
333 resize(size_type __sz, _Tp __c = _Tp())
338 _Base_iterator __victim = _Base::begin();
340 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
343 for (; __victim != __end; ++__victim)
348 _Base::resize(__sz, __c);
353 __throw_exception_again;
360 front() _GLIBCXX_NOEXCEPT
362 __glibcxx_check_nonempty();
363 return _Base::front();
367 front()
const _GLIBCXX_NOEXCEPT
369 __glibcxx_check_nonempty();
370 return _Base::front();
374 back() _GLIBCXX_NOEXCEPT
376 __glibcxx_check_nonempty();
377 return _Base::back();
381 back()
const _GLIBCXX_NOEXCEPT
383 __glibcxx_check_nonempty();
384 return _Base::back();
388 using _Base::push_front;
390#if __cplusplus >= 201103L
391 using _Base::emplace_front;
395 pop_front() _GLIBCXX_NOEXCEPT
397 __glibcxx_check_nonempty();
402 using _Base::push_back;
404#if __cplusplus >= 201103L
405 using _Base::emplace_back;
409 pop_back() _GLIBCXX_NOEXCEPT
411 __glibcxx_check_nonempty();
416#if __cplusplus >= 201103L
417 template<
typename... _Args>
422 return { _Base::emplace(__position.
base(),
423 std::forward<_Args>(__args)...),
this };
428#if __cplusplus >= 201103L
431 insert(
iterator __position,
const _Tp& __x)
435 return iterator(_Base::insert(__position.
base(), __x),
this);
438#if __cplusplus >= 201103L
441 {
return emplace(__position,
std::move(__x)); }
447 return { _Base::insert(__p.
base(), __l),
this };
451#if __cplusplus >= 201103L
456 return { _Base::insert(__position.
base(), __n, __x),
this };
460 insert(
iterator __position, size_type __n,
const _Tp& __x)
463 _Base::insert(__position.
base(), __n, __x);
467#if __cplusplus >= 201103L
468 template<
class _InputIterator,
469 typename = std::_RequireInputIter<_InputIterator>>
472 _InputIterator __last)
476 if (__dist.
second >= __gnu_debug::__dp_sign)
479 _Base::insert(__position.
base(),
480 __gnu_debug::__unsafe(__first),
481 __gnu_debug::__unsafe(__last)),
485 return { _Base::insert(__position.
base(), __first, __last),
this };
488 template<
class _InputIterator>
490 insert(
iterator __position, _InputIterator __first,
491 _InputIterator __last)
496 if (__dist.
second >= __gnu_debug::__dp_sign)
497 _Base::insert(__position.
base(), __gnu_debug::__unsafe(__first),
498 __gnu_debug::__unsafe(__last));
500 _Base::insert(__position.
base(), __first, __last);
506#if __cplusplus >= 201103L
513 return _Base::erase(__position);
518#if __cplusplus >= 201103L
529#if __cplusplus >= 201103L
539 __victim != __last.base(); ++__victim)
541 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
542 _M_message(__gnu_debug::__msg_valid_range)
543 ._M_iterator(__first,
"position")
544 ._M_iterator(__last,
"last"));
548 return iterator(_Base::erase(__first.base(), __last.base()),
this);
553 _GLIBCXX_NOEXCEPT_IF(
noexcept(declval<_Base&>().swap(__x)) )
560 clear() _GLIBCXX_NOEXCEPT
563 this->_M_invalidate_all();
568#if __cplusplus >= 201103L
575 _M_message(__gnu_debug::__msg_self_splice)
576 ._M_sequence(*
this,
"this"));
578 _Base::splice(__position.
base(), _GLIBCXX_MOVE(__x._M_base()));
581#if __cplusplus >= 201103L
588#if __cplusplus >= 201103L
600 _M_message(__gnu_debug::__msg_splice_bad)
601 ._M_iterator(__i,
"__i"));
603 _M_message(__gnu_debug::__msg_splice_other)
604 ._M_iterator(__i,
"__i")._M_sequence(__x,
"__x"));
609 _Base::splice(__position.
base(), _GLIBCXX_MOVE(__x._M_base()),
613#if __cplusplus >= 201103L
616 { splice(__position,
std::move(__x), __i); }
620#if __cplusplus >= 201103L
629 __glibcxx_check_valid_range(__first, __last);
631 _M_message(__gnu_debug::__msg_splice_other)
632 ._M_sequence(__x,
"x")
633 ._M_iterator(__first,
"first"));
639 __tmp != __last.base(); ++__tmp)
641 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
642 _M_message(__gnu_debug::__msg_valid_range)
643 ._M_iterator(__first,
"first")
644 ._M_iterator(__last,
"last"));
646 || __tmp != __position.
base(),
647 _M_message(__gnu_debug::__msg_splice_overlap)
648 ._M_iterator(__tmp,
"position")
649 ._M_iterator(__first,
"first")
650 ._M_iterator(__last,
"last"));
657 _Base::splice(__position.
base(), _GLIBCXX_MOVE(__x._M_base()),
658 __first.base(), __last.base());
661#if __cplusplus >= 201103L
665 { splice(__position,
std::move(__x), __first, __last); }
669#if __cplusplus > 201703L
670 typedef size_type __remove_return_type;
671# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
672 __attribute__((__abi_tag__("__cxx20")))
673# define _GLIBCXX20_ONLY(__expr) __expr
675 typedef void __remove_return_type;
676# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
677# define _GLIBCXX20_ONLY(__expr)
681 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
683 remove(
const _Tp& __value)
686 return _Base::remove(__value);
688#if !_GLIBCXX_USE_CXX11_ABI
689 size_type __removed __attribute__((__unused__)) = 0;
691 _Base __to_destroy(get_allocator());
694 while (__first != __last)
698 if (*__first == __value)
704 __to_destroy.splice(__to_destroy.begin(), _M_base(), __first);
705#if !_GLIBCXX_USE_CXX11_ABI
706 _GLIBCXX20_ONLY( __removed++ );
713#if !_GLIBCXX_USE_CXX11_ABI
714 return _GLIBCXX20_ONLY( __removed );
716 return _GLIBCXX20_ONLY( __to_destroy.size() );
720 template<
class _Predicate>
722 remove_if(_Predicate __pred)
725 return _Base::remove_if(__pred);
727#if !_GLIBCXX_USE_CXX11_ABI
728 size_type __removed __attribute__((__unused__)) = 0;
730 _Base __to_destroy(get_allocator());
738 __to_destroy.splice(__to_destroy.begin(), _M_base(), __x);
739#if !_GLIBCXX_USE_CXX11_ABI
740 _GLIBCXX20_ONLY( __removed++ );
747#if !_GLIBCXX_USE_CXX11_ABI
748 return _GLIBCXX20_ONLY( __removed );
750 return _GLIBCXX20_ONLY( __to_destroy.size() );
754 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
759 return _Base::unique();
762 return _GLIBCXX20_ONLY(0);
764#if !_GLIBCXX_USE_CXX11_ABI
765 size_type __removed __attribute__((__unused__)) = 0;
767 _Base __to_destroy(get_allocator());
771 while (++__next != __last)
772 if (*__first == *__next)
775 __to_destroy.splice(__to_destroy.begin(), _M_base(), __next);
777#if !_GLIBCXX_USE_CXX11_ABI
778 _GLIBCXX20_ONLY( __removed++ );
784#if !_GLIBCXX_USE_CXX11_ABI
785 return _GLIBCXX20_ONLY( __removed );
787 return _GLIBCXX20_ONLY( __to_destroy.size() );
791 template<
class _BinaryPredicate>
793 unique(_BinaryPredicate __binary_pred)
796 return _Base::unique(__binary_pred);
799 return _GLIBCXX20_ONLY(0);
802#if !_GLIBCXX_USE_CXX11_ABI
803 size_type __removed __attribute__((__unused__)) = 0;
805 _Base __to_destroy(get_allocator());
809 while (++__next != __last)
810 if (__binary_pred(*__first, *__next))
813 __to_destroy.splice(__to_destroy.begin(), _M_base(), __next);
815#if !_GLIBCXX_USE_CXX11_ABI
816 _GLIBCXX20_ONLY( __removed++ );
822#if !_GLIBCXX_USE_CXX11_ABI
823 return _GLIBCXX20_ONLY( __removed );
825 return _GLIBCXX20_ONLY( __to_destroy.size() );
829#undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
830#undef _GLIBCXX20_ONLY
833#if __cplusplus >= 201103L
843 __glibcxx_check_sorted(_Base::begin(), _Base::end());
844 __glibcxx_check_sorted(__x.begin().
base(), __x.end().
base());
846 _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
850#if __cplusplus >= 201103L
856 template<
class _Compare>
858#if __cplusplus >= 201103L
859 merge(
list&& __x, _Compare __comp)
861 merge(
list& __x, _Compare __comp)
873 _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
877#if __cplusplus >= 201103L
878 template<
typename _Compare>
880 merge(
list& __x, _Compare __comp)
885 sort() { _Base::sort(); }
887 template<
typename _StrictWeakOrdering>
889 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
891 using _Base::reverse;
894 _M_base() _GLIBCXX_NOEXCEPT {
return *
this; }
897 _M_base()
const _GLIBCXX_NOEXCEPT {
return *
this; }
900#if __cpp_deduction_guides >= 201606
901 template<
typename _InputIterator,
typename _ValT
904 typename = _RequireInputIter<_InputIterator>,
905 typename = _RequireAllocator<_Allocator>>
906 list(_InputIterator, _InputIterator, _Allocator = _Allocator())
909 template<
typename _Tp,
typename _Allocator = allocator<_Tp>,
910 typename = _RequireAllocator<_Allocator>>
911 list(
size_t, _Tp, _Allocator = _Allocator())
915 template<
typename _Tp,
typename _Alloc>
919 {
return __lhs._M_base() == __rhs._M_base(); }
921#if __cpp_lib_three_way_comparison
922 template<
typename _Tp,
typename _Alloc>
923 constexpr __detail::__synth3way_t<_Tp>
925 {
return __x._M_base() <=> __y._M_base(); }
927 template<
typename _Tp,
typename _Alloc>
929 operator!=(
const list<_Tp, _Alloc>& __lhs,
930 const list<_Tp, _Alloc>& __rhs)
931 {
return __lhs._M_base() != __rhs._M_base(); }
933 template<
typename _Tp,
typename _Alloc>
935 operator<(
const list<_Tp, _Alloc>& __lhs,
936 const list<_Tp, _Alloc>& __rhs)
937 {
return __lhs._M_base() < __rhs._M_base(); }
939 template<
typename _Tp,
typename _Alloc>
941 operator<=(
const list<_Tp, _Alloc>& __lhs,
942 const list<_Tp, _Alloc>& __rhs)
943 {
return __lhs._M_base() <= __rhs._M_base(); }
945 template<
typename _Tp,
typename _Alloc>
947 operator>=(
const list<_Tp, _Alloc>& __lhs,
948 const list<_Tp, _Alloc>& __rhs)
949 {
return __lhs._M_base() >= __rhs._M_base(); }
951 template<
typename _Tp,
typename _Alloc>
953 operator>(
const list<_Tp, _Alloc>& __lhs,
954 const list<_Tp, _Alloc>& __rhs)
955 {
return __lhs._M_base() > __rhs._M_base(); }
958 template<
typename _Tp,
typename _Alloc>
960 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
961 _GLIBCXX_NOEXCEPT_IF(
noexcept(__lhs.swap(__rhs)))
962 { __lhs.swap(__rhs); }
969#ifndef _GLIBCXX_USE_CXX11_ABI
971 template<
typename _Tp,
typename _Alloc>
972 struct _Sequence_traits<
std::__debug::list<_Tp, _Alloc> >
976 static typename _Distance_traits<_It>::__type
980 ? std::make_pair(0, __dp_exact) :
std::make_pair(1, __dp_sign);
985#ifndef _GLIBCXX_DEBUG_PEDANTIC
986 template<
class _Tp,
class _Alloc>
987 struct _Insert_range_from_self_is_safe<
std::__debug::list<_Tp, _Alloc> >
988 {
enum { __value = 1 }; };
#define __glibcxx_check_insert(_Position)
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_erase(_Position)
#define __glibcxx_check_insert_range(_Position, _First, _Last, _Dist)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
GNU debug classes for public use.
constexpr _Iterator __base(_Iterator __it)
The standard allocator, as per C++03 [20.4.1].
Traits class for iterators.
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Struct holding two objects of arbitrary type.
_T2 second
The second member.
bool _M_dereferenceable() const
Is the iterator dereferenceable?
_Iterator & base() noexcept
Return the underlying iterator.
void _M_invalidate_if(_Predicate __pred)
void _M_transfer_from_if(_Safe_sequence &__from, _Predicate __pred)
bool _M_attached_to(const _Safe_sequence_base *__seq) const
_Safe_iterator_base * _M_const_iterators
The list of constant iterators that reference this container.
void _M_revalidate_singular()
_Safe_iterator_base * _M_iterators
The list of mutable iterators that reference this container.
void _M_detach_singular()
Safe class dealing with some allocator dependent operations.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Class std::list with safety/checking/debug instrumentation.