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;
69 typedef typename _Base::reference reference;
70 typedef typename _Base::const_reference const_reference;
77 typedef typename _Base::size_type size_type;
78 typedef typename _Base::difference_type difference_type;
80 typedef _Tp value_type;
81 typedef _Allocator allocator_type;
82 typedef typename _Base::pointer pointer;
83 typedef typename _Base::const_pointer const_pointer;
89 #if __cplusplus < 201103L
99 list(
const list&) =
default;
100 list(list&&) =
default;
102 list(initializer_list<value_type> __l,
103 const allocator_type& __a = allocator_type())
104 : _Base(__l, __a) { }
108 list(
const list& __x,
const allocator_type& __a)
109 : _Base(__x, __a) { }
111 list(list&& __x,
const allocator_type& __a)
112 : _Base(std::move(__x), __a) { }
116 list(
const _Allocator& __a) _GLIBCXX_NOEXCEPT
119 #if __cplusplus >= 201103L
121 list(size_type __n,
const allocator_type& __a = allocator_type())
122 : _Base(__n, __a) { }
124 list(size_type __n,
const _Tp& __value,
125 const _Allocator& __a = _Allocator())
126 : _Base(__n, __value, __a) { }
129 list(size_type __n,
const _Tp& __value = _Tp(),
130 const _Allocator& __a = _Allocator())
131 : _Base(__n, __value, __a) { }
134 #if __cplusplus >= 201103L
135 template<
class _InputIterator,
136 typename = std::_RequireInputIter<_InputIterator>>
138 template<
class _InputIterator>
140 list(_InputIterator __first, _InputIterator __last,
141 const _Allocator& __a = _Allocator())
142 : _Base(__gnu_debug::
__base(
143 __glibcxx_check_valid_constructor_range(__first, __last)),
144 __gnu_debug::
__base(__last), __a)
147 list(
const _Base& __x)
150 #if __cplusplus < 201103L
152 operator=(
const list& __x)
154 this->_M_safe() = __x;
160 operator=(
const list&) =
default;
163 operator=(list&&) =
default;
166 operator=(initializer_list<value_type> __l)
168 this->_M_invalidate_all();
174 assign(initializer_list<value_type> __l)
177 this->_M_invalidate_all();
181 #if __cplusplus >= 201103L
182 template<
class _InputIterator,
183 typename = std::_RequireInputIter<_InputIterator>>
185 template<
class _InputIterator>
188 assign(_InputIterator __first, _InputIterator __last)
191 __glibcxx_check_valid_range2(__first, __last, __dist);
193 if (__dist.
second >= __gnu_debug::__dp_sign)
194 _Base::assign(__gnu_debug::__unsafe(__first),
195 __gnu_debug::__unsafe(__last));
197 _Base::assign(__first, __last);
199 this->_M_invalidate_all();
203 assign(size_type __n,
const _Tp& __t)
205 _Base::assign(__n, __t);
206 this->_M_invalidate_all();
209 using _Base::get_allocator;
213 begin() _GLIBCXX_NOEXCEPT
214 {
return iterator(_Base::begin(),
this); }
217 begin() const _GLIBCXX_NOEXCEPT
218 {
return const_iterator(_Base::begin(),
this); }
221 end() _GLIBCXX_NOEXCEPT
222 {
return iterator(_Base::end(),
this); }
225 end() const _GLIBCXX_NOEXCEPT
226 {
return const_iterator(_Base::end(),
this); }
229 rbegin() _GLIBCXX_NOEXCEPT
230 {
return reverse_iterator(end()); }
232 const_reverse_iterator
233 rbegin() const _GLIBCXX_NOEXCEPT
234 {
return const_reverse_iterator(end()); }
237 rend() _GLIBCXX_NOEXCEPT
238 {
return reverse_iterator(begin()); }
240 const_reverse_iterator
241 rend() const _GLIBCXX_NOEXCEPT
242 {
return const_reverse_iterator(begin()); }
244 #if __cplusplus >= 201103L
246 cbegin() const noexcept
247 {
return const_iterator(_Base::begin(),
this); }
250 cend() const noexcept
251 {
return const_iterator(_Base::end(),
this); }
253 const_reverse_iterator
254 crbegin() const noexcept
255 {
return const_reverse_iterator(end()); }
257 const_reverse_iterator
258 crend() const noexcept
259 {
return const_reverse_iterator(begin()); }
265 using _Base::max_size;
267 #if __cplusplus >= 201103L
269 resize(size_type __sz)
274 _Base_iterator __victim = _Base::begin();
275 _Base_iterator __end = _Base::end();
276 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
279 for (; __victim != __end; ++__victim)
289 __throw_exception_again;
294 resize(size_type __sz,
const _Tp& __c)
299 _Base_iterator __victim = _Base::begin();
300 _Base_iterator __end = _Base::end();
301 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
304 for (; __victim != __end; ++__victim)
309 _Base::resize(__sz, __c);
314 __throw_exception_again;
319 resize(size_type __sz, _Tp __c = _Tp())
324 _Base_iterator __victim = _Base::begin();
325 _Base_iterator __end = _Base::end();
326 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
329 for (; __victim != __end; ++__victim)
334 _Base::resize(__sz, __c);
339 __throw_exception_again;
346 front() _GLIBCXX_NOEXCEPT
348 __glibcxx_check_nonempty();
349 return _Base::front();
353 front() const _GLIBCXX_NOEXCEPT
355 __glibcxx_check_nonempty();
356 return _Base::front();
360 back() _GLIBCXX_NOEXCEPT
362 __glibcxx_check_nonempty();
363 return _Base::back();
367 back() const _GLIBCXX_NOEXCEPT
369 __glibcxx_check_nonempty();
370 return _Base::back();
374 using _Base::push_front;
376 #if __cplusplus >= 201103L
377 using _Base::emplace_front;
381 pop_front() _GLIBCXX_NOEXCEPT
383 __glibcxx_check_nonempty();
388 using _Base::push_back;
390 #if __cplusplus >= 201103L
391 using _Base::emplace_back;
395 pop_back() _GLIBCXX_NOEXCEPT
397 __glibcxx_check_nonempty();
402 #if __cplusplus >= 201103L
403 template<
typename... _Args>
405 emplace(const_iterator __position, _Args&&... __args)
408 return { _Base::emplace(__position.base(),
409 std::forward<_Args>(__args)...),
this };
414 #if __cplusplus >= 201103L
415 insert(const_iterator __position,
const _Tp& __x)
417 insert(iterator __position,
const _Tp& __x)
421 return iterator(_Base::insert(__position.base(), __x),
this);
424 #if __cplusplus >= 201103L
426 insert(const_iterator __position, _Tp&& __x)
427 {
return emplace(__position, std::move(__x)); }
430 insert(const_iterator __p, initializer_list<value_type> __l)
433 return { _Base::insert(__p.base(), __l),
this };
437 #if __cplusplus >= 201103L
439 insert(const_iterator __position, size_type __n,
const _Tp& __x)
442 return { _Base::insert(__position.base(), __n, __x),
this };
446 insert(iterator __position, size_type __n,
const _Tp& __x)
449 _Base::insert(__position.base(), __n, __x);
453 #if __cplusplus >= 201103L
454 template<
class _InputIterator,
455 typename = std::_RequireInputIter<_InputIterator>>
457 insert(const_iterator __position, _InputIterator __first,
458 _InputIterator __last)
462 if (__dist.
second >= __gnu_debug::__dp_sign)
465 _Base::insert(__position.base(),
466 __gnu_debug::__unsafe(__first),
467 __gnu_debug::__unsafe(__last)),
471 return { _Base::insert(__position.base(), __first, __last),
this };
474 template<
class _InputIterator>
476 insert(iterator __position, _InputIterator __first,
477 _InputIterator __last)
482 if (__dist.
second >= __gnu_debug::__dp_sign)
483 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
484 __gnu_debug::__unsafe(__last));
486 _Base::insert(__position.base(), __first, __last);
492 #if __cplusplus >= 201103L
493 _M_erase(_Base_const_iterator __position) noexcept
495 _M_erase(_Base_iterator __position)
499 return _Base::erase(__position);
504 #if __cplusplus >= 201103L
505 erase(const_iterator __position) noexcept
507 erase(iterator __position)
511 return iterator(_M_erase(__position.base()),
this);
515 #if __cplusplus >= 201103L
516 erase(const_iterator __first, const_iterator __last) noexcept
518 erase(iterator __first, iterator __last)
524 for (_Base_const_iterator __victim = __first.base();
525 __victim != __last.base(); ++__victim)
527 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
528 _M_message(__gnu_debug::__msg_valid_range)
529 ._M_iterator(__first,
"position")
530 ._M_iterator(__last,
"last"));
534 return iterator(_Base::erase(__first.base(), __last.base()),
this);
539 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
546 clear() _GLIBCXX_NOEXCEPT
549 this->_M_invalidate_all();
554 #if __cplusplus >= 201103L
555 splice(const_iterator __position, list&& __x) noexcept
557 splice(iterator __position, list& __x)
561 _M_message(__gnu_debug::__msg_self_splice)
562 ._M_sequence(*
this,
"this"));
564 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()));
567 #if __cplusplus >= 201103L
569 splice(const_iterator __position, list& __x) noexcept
570 { splice(__position, std::move(__x)); }
574 #if __cplusplus >= 201103L
575 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
577 splice(iterator __position, list& __x, iterator __i)
585 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
586 _M_message(__gnu_debug::__msg_splice_bad)
587 ._M_iterator(__i,
"__i"));
589 _M_message(__gnu_debug::__msg_splice_other)
590 ._M_iterator(__i,
"__i")._M_sequence(__x,
"__x"));
595 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
599 #if __cplusplus >= 201103L
601 splice(const_iterator __position, list& __x, const_iterator __i) noexcept
602 { splice(__position, std::move(__x), __i); }
606 #if __cplusplus >= 201103L
607 splice(const_iterator __position, list&& __x, const_iterator __first,
608 const_iterator __last) noexcept
610 splice(iterator __position, list& __x, iterator __first,
615 __glibcxx_check_valid_range(__first, __last);
617 _M_message(__gnu_debug::__msg_splice_other)
618 ._M_sequence(__x,
"x")
619 ._M_iterator(__first,
"first"));
624 for (_Base_const_iterator __tmp = __first.base();
625 __tmp != __last.
base(); ++__tmp)
627 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
628 _M_message(__gnu_debug::__msg_valid_range)
629 ._M_iterator(__first,
"first")
630 ._M_iterator(__last,
"last"));
632 || __tmp != __position.base(),
633 _M_message(__gnu_debug::__msg_splice_overlap)
634 ._M_iterator(__tmp,
"position")
635 ._M_iterator(__first,
"first")
636 ._M_iterator(__last,
"last"));
643 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
644 __first.base(), __last.base());
647 #if __cplusplus >= 201103L
649 splice(const_iterator __position, list& __x,
650 const_iterator __first, const_iterator __last) noexcept
651 { splice(__position, std::move(__x), __first, __last); }
655 #if __cplusplus > 201703L
656 typedef size_type __remove_return_type;
657 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
658 __attribute__((__abi_tag__("__cxx20")))
659 # define _GLIBCXX20_ONLY(__expr) __expr
661 typedef void __remove_return_type;
662 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
663 # define _GLIBCXX20_ONLY(__expr)
667 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
669 remove(
const _Tp& __value)
672 return _Base::remove(__value);
674 size_type __removed __attribute__((__unused__)) = 0;
675 _Base_iterator __first = _Base::begin();
676 _Base_iterator __last = _Base::end();
677 _Base_iterator __extra = __last;
678 while (__first != __last)
680 if (*__first == __value)
686 __first = _M_erase(__first);
687 _GLIBCXX20_ONLY( __removed++ );
698 if (__extra != __last)
701 _GLIBCXX20_ONLY( __removed++ );
703 return _GLIBCXX20_ONLY( __removed );
706 template<
class _Predicate>
708 remove_if(_Predicate __pred)
711 return _Base::remove_if(__pred);
713 size_type __removed __attribute__((__unused__)) = 0;
714 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
718 _GLIBCXX20_ONLY( __removed++ );
723 return _GLIBCXX20_ONLY( __removed );
726 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
731 return _Base::unique();
734 return _GLIBCXX20_ONLY(0);
736 size_type __removed __attribute__((__unused__)) = 0;
737 _Base_iterator __first = _Base::begin();
738 _Base_iterator __last = _Base::end();
739 _Base_iterator __next = __first;
740 while (++__next != __last)
741 if (*__first == *__next)
745 _GLIBCXX20_ONLY( __removed++ );
750 return _GLIBCXX20_ONLY( __removed );
753 template<
class _BinaryPredicate>
755 unique(_BinaryPredicate __binary_pred)
758 return _Base::unique(__binary_pred);
761 return _GLIBCXX20_ONLY(0);
763 size_type __removed __attribute__((__unused__)) = 0;
764 _Base_iterator __first = _Base::begin();
765 _Base_iterator __last = _Base::end();
766 _Base_iterator __next = __first;;
767 while (++__next != __last)
768 if (__binary_pred(*__first, *__next))
772 _GLIBCXX20_ONLY( __removed++ );
777 return _GLIBCXX20_ONLY( __removed );
780 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
781 #undef _GLIBCXX20_ONLY
784 #if __cplusplus >= 201103L
794 __glibcxx_check_sorted(_Base::begin(), _Base::end());
795 __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
797 _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
801 #if __cplusplus >= 201103L
804 { merge(std::move(__x)); }
807 template<
class _Compare>
809 #if __cplusplus >= 201103L
810 merge(list&& __x, _Compare __comp)
812 merge(list& __x, _Compare __comp)
824 _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
828 #if __cplusplus >= 201103L
829 template<
typename _Compare>
831 merge(list& __x, _Compare __comp)
832 { merge(std::move(__x), __comp); }
836 sort() { _Base::sort(); }
838 template<
typename _StrictWeakOrdering>
840 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
842 using _Base::reverse;
845 _M_base() _GLIBCXX_NOEXCEPT {
return *
this; }
848 _M_base() const _GLIBCXX_NOEXCEPT {
return *
this; }
851 #if __cpp_deduction_guides >= 201606
852 template<
typename _InputIterator,
typename _ValT
853 =
typename iterator_traits<_InputIterator>::value_type,
854 typename _Allocator = allocator<_ValT>,
855 typename = _RequireInputIter<_InputIterator>,
856 typename = _RequireAllocator<_Allocator>>
857 list(_InputIterator, _InputIterator, _Allocator = _Allocator())
858 -> list<_ValT, _Allocator>;
861 template<
typename _Tp,
typename _Alloc>
863 operator==(
const list<_Tp, _Alloc>& __lhs,
864 const list<_Tp, _Alloc>& __rhs)
865 {
return __lhs._M_base() == __rhs._M_base(); }
867 template<
typename _Tp,
typename _Alloc>
869 operator!=(
const list<_Tp, _Alloc>& __lhs,
870 const list<_Tp, _Alloc>& __rhs)
871 {
return __lhs._M_base() != __rhs._M_base(); }
873 template<
typename _Tp,
typename _Alloc>
875 operator<(const list<_Tp, _Alloc>& __lhs,
876 const list<_Tp, _Alloc>& __rhs)
877 {
return __lhs._M_base() < __rhs._M_base(); }
879 template<
typename _Tp,
typename _Alloc>
881 operator<=(const list<_Tp, _Alloc>& __lhs,
882 const list<_Tp, _Alloc>& __rhs)
883 {
return __lhs._M_base() <= __rhs._M_base(); }
885 template<
typename _Tp,
typename _Alloc>
887 operator>=(
const list<_Tp, _Alloc>& __lhs,
888 const list<_Tp, _Alloc>& __rhs)
889 {
return __lhs._M_base() >= __rhs._M_base(); }
891 template<
typename _Tp,
typename _Alloc>
893 operator>(
const list<_Tp, _Alloc>& __lhs,
894 const list<_Tp, _Alloc>& __rhs)
895 {
return __lhs._M_base() > __rhs._M_base(); }
897 template<
typename _Tp,
typename _Alloc>
899 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
900 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
901 { __lhs.swap(__rhs); }
906 namespace __gnu_debug
908 #ifndef _GLIBCXX_USE_CXX11_ABI
910 template<
typename _Tp,
typename _Alloc>
911 struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
915 static typename _Distance_traits<_It>::__type
924 #ifndef _GLIBCXX_DEBUG_PEDANTIC
925 template<
class _Tp,
class _Alloc>
926 struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
927 {
enum { __value = 1 }; };
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.
void _M_invalidate_if(_Predicate __pred)
Class std::list with safety/checking/debug instrumentation.
Safe class dealing with some allocator dependent operations.
#define __glibcxx_check_insert_range(_Position, _First, _Last, _Dist)
_Safe_iterator_base * _M_const_iterators
The list of constant iterators that reference this container.
_Iterator & base() noexcept
Return the underlying iterator.
void _M_transfer_from_if(_Safe_sequence &__from, _Predicate __pred)
Struct holding two objects of arbitrary type.
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
_Iterator __base(_Iterator __it)
_T2 second
first is a copy of the first object
_Safe_iterator_base * _M_iterators
The list of mutable iterators that reference this container.
void _M_detach_singular()
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_insert(_Position)
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
#define __glibcxx_check_erase(_Position)
void _M_revalidate_singular()
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...