29 #ifndef _GLIBCXX_DEBUG_LIST
30 #define _GLIBCXX_DEBUG_LIST 1
32 #pragma GCC system_header
35 namespace std _GLIBCXX_VISIBILITY(default) {
namespace __debug {
36 template<
typename _Tp,
typename _Allocator>
class list;
44 namespace 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;
60 typedef typename _Base::iterator _Base_iterator;
61 typedef typename _Base::const_iterator _Base_const_iterator;
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
103 list(
const list& __x)
109 list(
const list&) =
default;
110 list(list&&) =
default;
112 list(initializer_list<value_type> __l,
113 const allocator_type& __a = allocator_type())
114 : _Base(__l, __a) { }
118 list(
const list& __x,
const __type_identity_t<allocator_type>& __a)
119 : _Base(__x, __a) { }
121 list(list&& __x,
const __type_identity_t<allocator_type>& __a)
124 _Base,
const allocator_type&>::value )
125 : _Safe(std::
move(__x), __a),
126 _Base(std::
move(__x), __a) { }
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())
156 : _Base(__gnu_debug::
__base(
157 __glibcxx_check_valid_constructor_range(__first, __last)),
158 __gnu_debug::
__base(__last), __a)
162 : _Base(__x._M_ref) { }
164 #if __cplusplus >= 201103L
166 operator=(
const list&) =
default;
169 operator=(list&&) =
default;
172 operator=(initializer_list<value_type> __l)
174 this->_M_invalidate_all();
175 _Base::operator=(__l);
180 assign(initializer_list<value_type> __l)
183 this->_M_invalidate_all();
187 #if __cplusplus >= 201103L
188 template<
class _InputIterator,
189 typename = std::_RequireInputIter<_InputIterator>>
191 template<
class _InputIterator>
194 assign(_InputIterator __first, _InputIterator __last)
197 __glibcxx_check_valid_range2(__first, __last, __dist);
199 if (__dist.
second >= __gnu_debug::__dp_sign)
200 _Base::assign(__gnu_debug::__unsafe(__first),
201 __gnu_debug::__unsafe(__last));
203 _Base::assign(__first, __last);
205 this->_M_invalidate_all();
209 assign(size_type __n,
const _Tp& __t)
211 _Base::assign(__n, __t);
212 this->_M_invalidate_all();
215 using _Base::get_allocator;
220 begin() _GLIBCXX_NOEXCEPT
221 {
return iterator(_Base::begin(),
this); }
225 begin() const _GLIBCXX_NOEXCEPT
226 {
return const_iterator(_Base::begin(),
this); }
230 end() _GLIBCXX_NOEXCEPT
231 {
return iterator(_Base::end(),
this); }
235 end() const _GLIBCXX_NOEXCEPT
236 {
return const_iterator(_Base::end(),
this); }
240 rbegin() _GLIBCXX_NOEXCEPT
241 {
return reverse_iterator(end()); }
244 const_reverse_iterator
245 rbegin() const _GLIBCXX_NOEXCEPT
246 {
return const_reverse_iterator(end()); }
250 rend() _GLIBCXX_NOEXCEPT
251 {
return reverse_iterator(begin()); }
254 const_reverse_iterator
255 rend() const _GLIBCXX_NOEXCEPT
256 {
return const_reverse_iterator(begin()); }
258 #if __cplusplus >= 201103L
261 cbegin() const noexcept
262 {
return const_iterator(_Base::begin(),
this); }
266 cend() const noexcept
267 {
return const_iterator(_Base::end(),
this); }
270 const_reverse_iterator
271 crbegin() const noexcept
272 {
return const_reverse_iterator(end()); }
275 const_reverse_iterator
276 crend() const noexcept
277 {
return const_reverse_iterator(begin()); }
283 using _Base::max_size;
285 #if __cplusplus >= 201103L
287 resize(size_type __sz)
292 _Base_iterator __victim = _Base::begin();
293 _Base_iterator __end = _Base::end();
294 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
297 for (; __victim != __end; ++__victim)
307 __throw_exception_again;
312 resize(size_type __sz,
const _Tp& __c)
317 _Base_iterator __victim = _Base::begin();
318 _Base_iterator __end = _Base::end();
319 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
322 for (; __victim != __end; ++__victim)
327 _Base::resize(__sz, __c);
332 __throw_exception_again;
337 resize(size_type __sz, _Tp __c = _Tp())
342 _Base_iterator __victim = _Base::begin();
343 _Base_iterator __end = _Base::end();
344 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
347 for (; __victim != __end; ++__victim)
352 _Base::resize(__sz, __c);
357 __throw_exception_again;
365 front() _GLIBCXX_NOEXCEPT
367 __glibcxx_check_nonempty();
368 return _Base::front();
373 front() const _GLIBCXX_NOEXCEPT
375 __glibcxx_check_nonempty();
376 return _Base::front();
381 back() _GLIBCXX_NOEXCEPT
383 __glibcxx_check_nonempty();
384 return _Base::back();
389 back() const _GLIBCXX_NOEXCEPT
391 __glibcxx_check_nonempty();
392 return _Base::back();
396 using _Base::push_front;
398 #if __cplusplus >= 201103L
399 using _Base::emplace_front;
403 pop_front() _GLIBCXX_NOEXCEPT
405 __glibcxx_check_nonempty();
410 using _Base::push_back;
412 #if __cplusplus >= 201103L
413 using _Base::emplace_back;
417 pop_back() _GLIBCXX_NOEXCEPT
419 __glibcxx_check_nonempty();
424 #if __cplusplus >= 201103L
425 template<
typename... _Args>
427 emplace(const_iterator __position, _Args&&... __args)
430 return { _Base::emplace(__position.base(),
431 std::forward<_Args>(__args)...),
this };
436 #if __cplusplus >= 201103L
437 insert(const_iterator __position,
const _Tp& __x)
439 insert(iterator __position,
const _Tp& __x)
443 return iterator(_Base::insert(__position.base(), __x),
this);
446 #if __cplusplus >= 201103L
448 insert(const_iterator __position, _Tp&& __x)
449 {
return emplace(__position,
std::move(__x)); }
452 insert(const_iterator __p, initializer_list<value_type> __l)
455 return { _Base::insert(__p.base(), __l),
this };
459 #if __cplusplus >= 201103L
461 insert(const_iterator __position, size_type __n,
const _Tp& __x)
464 return { _Base::insert(__position.base(), __n, __x),
this };
468 insert(iterator __position, size_type __n,
const _Tp& __x)
471 _Base::insert(__position.base(), __n, __x);
475 #if __cplusplus >= 201103L
476 template<
class _InputIterator,
477 typename = std::_RequireInputIter<_InputIterator>>
479 insert(const_iterator __position, _InputIterator __first,
480 _InputIterator __last)
484 if (__dist.
second >= __gnu_debug::__dp_sign)
487 _Base::insert(__position.base(),
488 __gnu_debug::__unsafe(__first),
489 __gnu_debug::__unsafe(__last)),
493 return { _Base::insert(__position.base(), __first, __last),
this };
496 template<
class _InputIterator>
498 insert(iterator __position, _InputIterator __first,
499 _InputIterator __last)
504 if (__dist.
second >= __gnu_debug::__dp_sign)
505 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
506 __gnu_debug::__unsafe(__last));
508 _Base::insert(__position.base(), __first, __last);
514 #if __cplusplus >= 201103L
515 _M_erase(_Base_const_iterator __position) noexcept
517 _M_erase(_Base_iterator __position)
521 return _Base::erase(__position);
526 #if __cplusplus >= 201103L
527 erase(const_iterator __position) noexcept
529 erase(iterator __position)
533 return iterator(_M_erase(__position.base()),
this);
537 #if __cplusplus >= 201103L
538 erase(const_iterator __first, const_iterator __last) noexcept
540 erase(iterator __first, iterator __last)
546 for (_Base_const_iterator __victim = __first.base();
547 __victim != __last.base(); ++__victim)
549 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
550 _M_message(__gnu_debug::__msg_valid_range)
551 ._M_iterator(__first,
"position")
552 ._M_iterator(__last,
"last"));
556 return iterator(_Base::erase(__first.base(), __last.base()),
this);
561 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
568 clear() _GLIBCXX_NOEXCEPT
571 this->_M_invalidate_all();
576 #if __cplusplus >= 201103L
577 splice(const_iterator __position, list&& __x) noexcept
579 splice(iterator __position, list& __x)
583 _M_message(__gnu_debug::__msg_self_splice)
584 ._M_sequence(*
this,
"this"));
586 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x));
589 #if __cplusplus >= 201103L
591 splice(const_iterator __position, list& __x) noexcept
596 #if __cplusplus >= 201103L
597 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
599 splice(iterator __position, list& __x, iterator __i)
607 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
608 _M_message(__gnu_debug::__msg_splice_bad)
609 ._M_iterator(__i,
"__i"));
611 _M_message(__gnu_debug::__msg_splice_other)
612 ._M_iterator(__i,
"__i")._M_sequence(__x,
"__x"));
617 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
621 #if __cplusplus >= 201103L
623 splice(const_iterator __position, list& __x, const_iterator __i) noexcept
624 { splice(__position,
std::move(__x), __i); }
628 #if __cplusplus >= 201103L
629 splice(const_iterator __position, list&& __x, const_iterator __first,
630 const_iterator __last) noexcept
632 splice(iterator __position, list& __x, iterator __first,
637 __glibcxx_check_valid_range(__first, __last);
639 _M_message(__gnu_debug::__msg_splice_other)
640 ._M_sequence(__x,
"x")
641 ._M_iterator(__first,
"first"));
646 for (_Base_const_iterator __tmp = __first.base();
647 __tmp != __last.
base(); ++__tmp)
649 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
650 _M_message(__gnu_debug::__msg_valid_range)
651 ._M_iterator(__first,
"first")
652 ._M_iterator(__last,
"last"));
654 || __tmp != __position.base(),
655 _M_message(__gnu_debug::__msg_splice_overlap)
656 ._M_iterator(__tmp,
"position")
657 ._M_iterator(__first,
"first")
658 ._M_iterator(__last,
"last"));
665 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
666 __first.base(), __last.base());
669 #if __cplusplus >= 201103L
671 splice(const_iterator __position, list& __x,
672 const_iterator __first, const_iterator __last) noexcept
673 { splice(__position,
std::move(__x), __first, __last); }
677 #if __cplusplus > 201703L
678 typedef size_type __remove_return_type;
679 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
680 __attribute__((__abi_tag__("__cxx20")))
681 # define _GLIBCXX20_ONLY(__expr) __expr
683 typedef void __remove_return_type;
684 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
685 # define _GLIBCXX20_ONLY(__expr)
689 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
691 remove(
const _Tp& __value)
694 return _Base::remove(__value);
696 #if !_GLIBCXX_USE_CXX11_ABI
697 size_type __removed __attribute__((__unused__)) = 0;
699 _Base __to_destroy(get_allocator());
700 _Base_iterator __first = _Base::begin();
701 _Base_iterator __last = _Base::end();
702 while (__first != __last)
704 _Base_iterator __next = __first;
706 if (*__first == __value)
712 __to_destroy.splice(__to_destroy.begin(), *
this, __first);
713 #if !_GLIBCXX_USE_CXX11_ABI
714 _GLIBCXX20_ONLY( __removed++ );
721 #if !_GLIBCXX_USE_CXX11_ABI
722 return _GLIBCXX20_ONLY( __removed );
724 return _GLIBCXX20_ONLY( __to_destroy.size() );
728 template<
class _Predicate>
730 remove_if(_Predicate __pred)
733 return _Base::remove_if(__pred);
735 #if !_GLIBCXX_USE_CXX11_ABI
736 size_type __removed __attribute__((__unused__)) = 0;
738 _Base __to_destroy(get_allocator());
739 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
741 _Base_iterator __next = __x;
746 __to_destroy.splice(__to_destroy.begin(), *
this, __x);
747 #if !_GLIBCXX_USE_CXX11_ABI
748 _GLIBCXX20_ONLY( __removed++ );
755 #if !_GLIBCXX_USE_CXX11_ABI
756 return _GLIBCXX20_ONLY( __removed );
758 return _GLIBCXX20_ONLY( __to_destroy.size() );
762 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
767 return _Base::unique();
770 return _GLIBCXX20_ONLY(0);
772 #if !_GLIBCXX_USE_CXX11_ABI
773 size_type __removed __attribute__((__unused__)) = 0;
775 _Base __to_destroy(get_allocator());
776 _Base_iterator __first = _Base::begin();
777 _Base_iterator __last = _Base::end();
778 _Base_iterator __next = __first;
779 while (++__next != __last)
780 if (*__first == *__next)
783 __to_destroy.splice(__to_destroy.begin(), *
this, __next);
785 #if !_GLIBCXX_USE_CXX11_ABI
786 _GLIBCXX20_ONLY( __removed++ );
792 #if !_GLIBCXX_USE_CXX11_ABI
793 return _GLIBCXX20_ONLY( __removed );
795 return _GLIBCXX20_ONLY( __to_destroy.size() );
799 template<
class _BinaryPredicate>
801 unique(_BinaryPredicate __binary_pred)
804 return _Base::unique(__binary_pred);
807 return _GLIBCXX20_ONLY(0);
810 #if !_GLIBCXX_USE_CXX11_ABI
811 size_type __removed __attribute__((__unused__)) = 0;
813 _Base __to_destroy(get_allocator());
814 _Base_iterator __first = _Base::begin();
815 _Base_iterator __last = _Base::end();
816 _Base_iterator __next = __first;
817 while (++__next != __last)
818 if (__binary_pred(*__first, *__next))
821 __to_destroy.splice(__to_destroy.begin(), *
this, __next);
823 #if !_GLIBCXX_USE_CXX11_ABI
824 _GLIBCXX20_ONLY( __removed++ );
830 #if !_GLIBCXX_USE_CXX11_ABI
831 return _GLIBCXX20_ONLY( __removed );
833 return _GLIBCXX20_ONLY( __to_destroy.size() );
837 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
838 #undef _GLIBCXX20_ONLY
841 #if __cplusplus >= 201103L
851 __glibcxx_check_sorted(_Base::begin(), _Base::end());
852 __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
854 _Base::merge(_GLIBCXX_MOVE(__x));
858 #if __cplusplus >= 201103L
864 template<
class _Compare>
866 #if __cplusplus >= 201103L
867 merge(list&& __x, _Compare __comp)
869 merge(list& __x, _Compare __comp)
881 _Base::merge(_GLIBCXX_MOVE(__x), __comp);
885 #if __cplusplus >= 201103L
886 template<
typename _Compare>
888 merge(list& __x, _Compare __comp)
893 sort() { _Base::sort(); }
895 template<
typename _StrictWeakOrdering>
897 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
899 using _Base::reverse;
902 _M_base() _GLIBCXX_NOEXCEPT {
return *
this; }
905 _M_base() const _GLIBCXX_NOEXCEPT {
return *
this; }
908 #if __cpp_deduction_guides >= 201606
909 template<
typename _InputIterator,
typename _ValT
910 =
typename iterator_traits<_InputIterator>::value_type,
911 typename _Allocator = allocator<_ValT>,
912 typename = _RequireInputIter<_InputIterator>,
913 typename = _RequireAllocator<_Allocator>>
914 list(_InputIterator, _InputIterator, _Allocator = _Allocator())
915 -> list<_ValT, _Allocator>;
917 template<
typename _Tp,
typename _Allocator = allocator<_Tp>,
918 typename = _RequireAllocator<_Allocator>>
919 list(
size_t, _Tp, _Allocator = _Allocator())
920 -> list<_Tp, _Allocator>;
923 template<
typename _Tp,
typename _Alloc>
925 operator==(
const list<_Tp, _Alloc>& __lhs,
926 const list<_Tp, _Alloc>& __rhs)
927 {
return __lhs._M_base() == __rhs._M_base(); }
929 #if __cpp_lib_three_way_comparison
930 template<
typename _Tp,
typename _Alloc>
931 constexpr __detail::__synth3way_t<_Tp>
932 operator<=>(
const list<_Tp, _Alloc>& __x,
const list<_Tp, _Alloc>& __y)
933 {
return __x._M_base() <=> __y._M_base(); }
935 template<
typename _Tp,
typename _Alloc>
937 operator!=(
const list<_Tp, _Alloc>& __lhs,
938 const list<_Tp, _Alloc>& __rhs)
939 {
return __lhs._M_base() != __rhs._M_base(); }
941 template<
typename _Tp,
typename _Alloc>
943 operator<(const list<_Tp, _Alloc>& __lhs,
944 const list<_Tp, _Alloc>& __rhs)
945 {
return __lhs._M_base() < __rhs._M_base(); }
947 template<
typename _Tp,
typename _Alloc>
949 operator<=(const list<_Tp, _Alloc>& __lhs,
950 const list<_Tp, _Alloc>& __rhs)
951 {
return __lhs._M_base() <= __rhs._M_base(); }
953 template<
typename _Tp,
typename _Alloc>
955 operator>=(
const list<_Tp, _Alloc>& __lhs,
956 const list<_Tp, _Alloc>& __rhs)
957 {
return __lhs._M_base() >= __rhs._M_base(); }
959 template<
typename _Tp,
typename _Alloc>
961 operator>(
const list<_Tp, _Alloc>& __lhs,
962 const list<_Tp, _Alloc>& __rhs)
963 {
return __lhs._M_base() > __rhs._M_base(); }
964 #endif // three-way comparison
966 template<
typename _Tp,
typename _Alloc>
968 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
969 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
970 { __lhs.swap(__rhs); }
975 namespace __gnu_debug
977 #ifndef _GLIBCXX_USE_CXX11_ABI
979 template<
typename _Tp,
typename _Alloc>
980 struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
984 static typename _Distance_traits<_It>::__type
988 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
993 #ifndef _GLIBCXX_DEBUG_PEDANTIC
994 template<
class _Tp,
class _Alloc>
995 struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
996 {
enum { __value = 1 }; };
#define __glibcxx_check_erase(_Position)
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
_Safe_iterator_base * _M_iterators
The list of mutable iterators that reference this container.
void _M_invalidate_if(_Predicate __pred)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void _M_detach_singular()
_Safe_iterator_base * _M_const_iterators
The list of constant iterators that reference this container.
Class std::list with safety/checking/debug instrumentation.
void _M_transfer_from_if(_Safe_sequence &__from, _Predicate __pred)
#define __glibcxx_check_erase_range(_First, _Last)
void _M_revalidate_singular()
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Struct holding two objects of arbitrary type.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr _Iterator __base(_Iterator __it)
#define __glibcxx_check_insert(_Position)
Safe class dealing with some allocator dependent operations.
_T2 second
The second member.
#define __glibcxx_check_insert_range(_Position, _First, _Last, _Dist)
_Iterator & base() noexcept
Return the underlying iterator.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.