libstdc++
debug/list
Go to the documentation of this file.
1// Debugging list implementation -*- C++ -*-
2
3// Copyright (C) 2003-2024 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>
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
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;
61
62 typedef typename _Base::iterator _Base_iterator;
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
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;
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
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(
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())
159 __glibcxx_check_valid_constructor_range(__first, __last)),
160 __gnu_debug::__base(__last), __a)
161 { }
162
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)
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
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 {
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_ranges_to_container // 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
255 begin() _GLIBCXX_NOEXCEPT
256 { return iterator(_Base::begin(), this); }
257
258 _GLIBCXX_NODISCARD
260 begin() const _GLIBCXX_NOEXCEPT
261 { return const_iterator(_Base::begin(), this); }
262
263 _GLIBCXX_NODISCARD
265 end() _GLIBCXX_NOEXCEPT
266 { return iterator(_Base::end(), this); }
267
268 _GLIBCXX_NODISCARD
270 end() const _GLIBCXX_NOEXCEPT
271 { return const_iterator(_Base::end(), this); }
272
273 _GLIBCXX_NODISCARD
275 rbegin() _GLIBCXX_NOEXCEPT
276 { return reverse_iterator(end()); }
277
278 _GLIBCXX_NODISCARD
280 rbegin() const _GLIBCXX_NOEXCEPT
281 { return const_reverse_iterator(end()); }
282
283 _GLIBCXX_NODISCARD
285 rend() _GLIBCXX_NOEXCEPT
286 { return reverse_iterator(begin()); }
287
288 _GLIBCXX_NODISCARD
290 rend() const _GLIBCXX_NOEXCEPT
291 { return const_reverse_iterator(begin()); }
292
293#if __cplusplus >= 201103L
294 [[__nodiscard__]]
296 cbegin() const noexcept
297 { return const_iterator(_Base::begin(), this); }
298
299 [[__nodiscard__]]
301 cend() const noexcept
302 { return const_iterator(_Base::end(), this); }
303
304 [[__nodiscard__]]
306 crbegin() const noexcept
307 { return const_reverse_iterator(end()); }
308
309 [[__nodiscard__]]
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 this->_M_detach_singular();
325
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)
330 ++__victim;
331
332 for (; __victim != __end; ++__victim)
333 this->_M_invalidate_if(_Equal(__victim));
334
335 __try
336 {
337 _Base::resize(__sz);
338 }
339 __catch(...)
340 {
341 this->_M_revalidate_singular();
342 __throw_exception_again;
343 }
344 }
345
346 void
347 resize(size_type __sz, const _Tp& __c)
348 {
349 this->_M_detach_singular();
350
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)
355 ++__victim;
356
357 for (; __victim != __end; ++__victim)
358 this->_M_invalidate_if(_Equal(__victim));
359
360 __try
361 {
362 _Base::resize(__sz, __c);
363 }
364 __catch(...)
365 {
366 this->_M_revalidate_singular();
367 __throw_exception_again;
368 }
369 }
370#else
371 void
372 resize(size_type __sz, _Tp __c = _Tp())
373 {
374 this->_M_detach_singular();
375
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)
380 ++__victim;
381
382 for (; __victim != __end; ++__victim)
383 this->_M_invalidate_if(_Equal(__victim));
384
385 __try
386 {
387 _Base::resize(__sz, __c);
388 }
389 __catch(...)
390 {
391 this->_M_revalidate_singular();
392 __throw_exception_again;
393 }
394 }
395#endif
396
397 // element access:
398 _GLIBCXX_NODISCARD
399 reference
400 front() _GLIBCXX_NOEXCEPT
401 {
402 __glibcxx_check_nonempty();
403 return _Base::front();
404 }
405
406 _GLIBCXX_NODISCARD
407 const_reference
408 front() const _GLIBCXX_NOEXCEPT
409 {
410 __glibcxx_check_nonempty();
411 return _Base::front();
412 }
413
414 _GLIBCXX_NODISCARD
415 reference
416 back() _GLIBCXX_NOEXCEPT
417 {
418 __glibcxx_check_nonempty();
419 return _Base::back();
420 }
421
422 _GLIBCXX_NODISCARD
423 const_reference
424 back() const _GLIBCXX_NOEXCEPT
425 {
426 __glibcxx_check_nonempty();
427 return _Base::back();
428 }
429
430 // 23.2.2.3 modifiers:
431 using _Base::push_front;
432
433#if __cplusplus >= 201103L
434 using _Base::emplace_front;
435#endif
436
437#if __glibcxx_ranges_to_container // C++ >= 23
438 using _Base::prepend_range;
439 using _Base::append_range;
440#endif
441
442 void
443 pop_front() _GLIBCXX_NOEXCEPT
444 {
445 __glibcxx_check_nonempty();
446 this->_M_invalidate_if(_Equal(_Base::begin()));
447 _Base::pop_front();
448 }
449
450 using _Base::push_back;
451
452#if __cplusplus >= 201103L
453 using _Base::emplace_back;
454#endif
455
456 void
457 pop_back() _GLIBCXX_NOEXCEPT
458 {
459 __glibcxx_check_nonempty();
460 this->_M_invalidate_if(_Equal(--_Base::end()));
461 _Base::pop_back();
462 }
463
464#if __cplusplus >= 201103L
465 template<typename... _Args>
467 emplace(const_iterator __position, _Args&&... __args)
468 {
469 __glibcxx_check_insert(__position);
470 return { _Base::emplace(__position.base(),
471 std::forward<_Args>(__args)...), this };
472 }
473#endif
474
476#if __cplusplus >= 201103L
477 insert(const_iterator __position, const _Tp& __x)
478#else
479 insert(iterator __position, const _Tp& __x)
480#endif
481 {
482 __glibcxx_check_insert(__position);
483 return iterator(_Base::insert(__position.base(), __x), this);
484 }
485
486#if __cplusplus >= 201103L
488 insert(const_iterator __position, _Tp&& __x)
489 { return emplace(__position, std::move(__x)); }
490
493 {
495 return { _Base::insert(__p.base(), __l), this };
496 }
497#endif
498
499#if __cplusplus >= 201103L
501 insert(const_iterator __position, size_type __n, const _Tp& __x)
502 {
503 __glibcxx_check_insert(__position);
504 return { _Base::insert(__position.base(), __n, __x), this };
505 }
506#else
507 void
508 insert(iterator __position, size_type __n, const _Tp& __x)
509 {
510 __glibcxx_check_insert(__position);
511 _Base::insert(__position.base(), __n, __x);
512 }
513#endif
514
515#if __cplusplus >= 201103L
516 template<class _InputIterator,
517 typename = std::_RequireInputIter<_InputIterator>>
519 insert(const_iterator __position, _InputIterator __first,
520 _InputIterator __last)
521 {
523 __glibcxx_check_insert_range(__position, __first, __last, __dist);
524 if (__dist.second >= __gnu_debug::__dp_sign)
525 return
526 {
527 _Base::insert(__position.base(),
528 __gnu_debug::__unsafe(__first),
529 __gnu_debug::__unsafe(__last)),
530 this
531 };
532 else
533 return { _Base::insert(__position.base(), __first, __last), this };
534 }
535#else
536 template<class _InputIterator>
537 void
538 insert(iterator __position, _InputIterator __first,
539 _InputIterator __last)
540 {
542 __glibcxx_check_insert_range(__position, __first, __last, __dist);
543
544 if (__dist.second >= __gnu_debug::__dp_sign)
545 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
546 __gnu_debug::__unsafe(__last));
547 else
548 _Base::insert(__position.base(), __first, __last);
549 }
550#endif
551
552#if __glibcxx_ranges_to_container // C++ >= 23
553 template<__detail::__container_compatible_range<_Tp> _Rg>
555 insert_range(const_iterator __position, _Rg&& __rg)
556 {
557 auto __ret = _Base::insert_range(__position.base(),
558 std::forward<_Rg>(__rg));
559 return { __ret, this };
560 }
561#endif
562
563 private:
565#if __cplusplus >= 201103L
566 _M_erase(_Base_const_iterator __position) noexcept
567#else
568 _M_erase(_Base_iterator __position)
569#endif
570 {
571 this->_M_invalidate_if(_Equal(__position));
572 return _Base::erase(__position);
573 }
574
575 public:
577#if __cplusplus >= 201103L
578 erase(const_iterator __position) noexcept
579#else
580 erase(iterator __position)
581#endif
582 {
583 __glibcxx_check_erase(__position);
584 return iterator(_M_erase(__position.base()), this);
585 }
586
588#if __cplusplus >= 201103L
589 erase(const_iterator __first, const_iterator __last) noexcept
590#else
591 erase(iterator __first, iterator __last)
592#endif
593 {
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)
599 {
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));
605 }
606
607 return iterator(_Base::erase(__first.base(), __last.base()), this);
608 }
609
610 void
611 swap(list& __x)
612 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
613 {
614 _Safe::_M_swap(__x);
615 _Base::swap(__x);
616 }
617
618 void
619 clear() _GLIBCXX_NOEXCEPT
620 {
621 _Base::clear();
622 this->_M_invalidate_all();
623 }
624
625 // 23.2.2.4 list operations:
626 void
627#if __cplusplus >= 201103L
628 splice(const_iterator __position, list&& __x) noexcept
629#else
630 splice(iterator __position, list& __x)
631#endif
632 {
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));
638 }
639
640#if __cplusplus >= 201103L
641 void
642 splice(const_iterator __position, list& __x) noexcept
643 { splice(__position, std::move(__x)); }
644#endif
645
646 void
647#if __cplusplus >= 201103L
648 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
649#else
650 splice(iterator __position, list& __x, iterator __i)
651#endif
652 {
653 __glibcxx_check_insert(__position);
654
655 // We used to perform the splice_alloc check: not anymore, redundant
656 // after implementing the relevant bits of N1599.
657
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"));
664
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),
669 __i.base());
670 }
671
672#if __cplusplus >= 201103L
673 void
674 splice(const_iterator __position, list& __x, const_iterator __i) noexcept
675 { splice(__position, std::move(__x), __i); }
676#endif
677
678 void
679#if __cplusplus >= 201103L
680 splice(const_iterator __position, list&& __x, const_iterator __first,
681 const_iterator __last) noexcept
682#else
683 splice(iterator __position, list& __x, iterator __first,
684 iterator __last)
685#endif
686 {
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"));
693
694 // We used to perform the splice_alloc check: not anymore, redundant
695 // after implementing the relevant bits of N1599.
696
697 for (_Base_const_iterator __tmp = __first.base();
698 __tmp != __last.base(); ++__tmp)
699 {
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"));
710
711 // _GLIBCXX_RESOLVE_LIB_DEFECTS
712 // 250. splicing invalidates iterators
713 this->_M_transfer_from_if(__x, _Equal(__tmp));
714 }
715
716 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
717 __first.base(), __last.base());
718 }
719
720#if __cplusplus >= 201103L
721 void
722 splice(const_iterator __position, list& __x,
723 const_iterator __first, const_iterator __last) noexcept
724 { splice(__position, std::move(__x), __first, __last); }
725#endif
726
727 private:
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
733#else
734 typedef void __remove_return_type;
735# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
736# define _GLIBCXX20_ONLY(__expr)
737#endif
738
739 public:
740 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
741 __remove_return_type
742 remove(const _Tp& __value)
743 {
744 if (!this->_M_iterators && !this->_M_const_iterators)
745 return _Base::remove(__value);
746
747#if !_GLIBCXX_USE_CXX11_ABI
748 size_type __removed __attribute__((__unused__)) = 0;
749#endif
750 _Base __to_destroy(get_allocator());
751 _Base_iterator __first = _Base::begin();
752 _Base_iterator __last = _Base::end();
753 while (__first != __last)
754 {
755 _Base_iterator __next = __first;
756 ++__next;
757 if (*__first == __value)
758 {
759 // _GLIBCXX_RESOLVE_LIB_DEFECTS
760 // 526. Is it undefined if a function in the standard changes
761 // in parameters?
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++ );
766#endif
767 }
768
769 __first = __next;
770 }
771
772#if !_GLIBCXX_USE_CXX11_ABI
773 return _GLIBCXX20_ONLY( __removed );
774#else
775 return _GLIBCXX20_ONLY( __to_destroy.size() );
776#endif
777 }
778
779 template<class _Predicate>
780 __remove_return_type
781 remove_if(_Predicate __pred)
782 {
783 if (!this->_M_iterators && !this->_M_const_iterators)
784 return _Base::remove_if(__pred);
785
786#if !_GLIBCXX_USE_CXX11_ABI
787 size_type __removed __attribute__((__unused__)) = 0;
788#endif
789 _Base __to_destroy(get_allocator());
790 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
791 {
792 _Base_iterator __next = __x;
793 ++__next;
794 if (__pred(*__x))
795 {
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++ );
800#endif
801 }
802
803 __x = __next;
804 }
805
806#if !_GLIBCXX_USE_CXX11_ABI
807 return _GLIBCXX20_ONLY( __removed );
808#else
809 return _GLIBCXX20_ONLY( __to_destroy.size() );
810#endif
811 }
812
813 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
814 __remove_return_type
815 unique()
816 {
817 if (!this->_M_iterators && !this->_M_const_iterators)
818 return _Base::unique();
819
820 if (empty())
821 return _GLIBCXX20_ONLY(0);
822
823#if !_GLIBCXX_USE_CXX11_ABI
824 size_type __removed __attribute__((__unused__)) = 0;
825#endif
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)
832 {
833 this->_M_invalidate_if(_Equal(__next));
834 __to_destroy.splice(__to_destroy.begin(), *this, __next);
835 __next = __first;
836#if !_GLIBCXX_USE_CXX11_ABI
837 _GLIBCXX20_ONLY( __removed++ );
838#endif
839 }
840 else
841 __first = __next;
842
843#if !_GLIBCXX_USE_CXX11_ABI
844 return _GLIBCXX20_ONLY( __removed );
845#else
846 return _GLIBCXX20_ONLY( __to_destroy.size() );
847#endif
848 }
849
850 template<class _BinaryPredicate>
851 __remove_return_type
852 unique(_BinaryPredicate __binary_pred)
853 {
854 if (!this->_M_iterators && !this->_M_const_iterators)
855 return _Base::unique(__binary_pred);
856
857 if (empty())
858 return _GLIBCXX20_ONLY(0);
859
860
861#if !_GLIBCXX_USE_CXX11_ABI
862 size_type __removed __attribute__((__unused__)) = 0;
863#endif
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))
870 {
871 this->_M_invalidate_if(_Equal(__next));
872 __to_destroy.splice(__to_destroy.begin(), *this, __next);
873 __next = __first;
874#if !_GLIBCXX_USE_CXX11_ABI
875 _GLIBCXX20_ONLY( __removed++ );
876#endif
877 }
878 else
879 __first = __next;
880
881#if !_GLIBCXX_USE_CXX11_ABI
882 return _GLIBCXX20_ONLY( __removed );
883#else
884 return _GLIBCXX20_ONLY( __to_destroy.size() );
885#endif
886 }
887
888#undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
889#undef _GLIBCXX20_ONLY
890
891 void
892#if __cplusplus >= 201103L
893 merge(list&& __x)
894#else
895 merge(list& __x)
896#endif
897 {
898 // _GLIBCXX_RESOLVE_LIB_DEFECTS
899 // 300. list::merge() specification incomplete
900 if (this != std::__addressof(__x))
901 {
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));
906 }
907 }
908
909#if __cplusplus >= 201103L
910 void
911 merge(list& __x)
912 { merge(std::move(__x)); }
913#endif
914
915 template<class _Compare>
916 void
917#if __cplusplus >= 201103L
918 merge(list&& __x, _Compare __comp)
919#else
920 merge(list& __x, _Compare __comp)
921#endif
922 {
923 // _GLIBCXX_RESOLVE_LIB_DEFECTS
924 // 300. list::merge() specification incomplete
925 if (this != std::__addressof(__x))
926 {
927 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
928 __comp);
929 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
930 __comp);
931 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
932 _Base::merge(_GLIBCXX_MOVE(__x), __comp);
933 }
934 }
935
936#if __cplusplus >= 201103L
937 template<typename _Compare>
938 void
939 merge(list& __x, _Compare __comp)
940 { merge(std::move(__x), __comp); }
941#endif
942
943 void
944 sort() { _Base::sort(); }
945
946 template<typename _StrictWeakOrdering>
947 void
948 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
949
950 using _Base::reverse;
951
952 _Base&
953 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
954
955 const _Base&
956 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
957 };
958
959#if __cpp_deduction_guides >= 201606
960 template<typename _InputIterator, typename _ValT
962 typename _Allocator = allocator<_ValT>,
963 typename = _RequireInputIter<_InputIterator>,
964 typename = _RequireAllocator<_Allocator>>
965 list(_InputIterator, _InputIterator, _Allocator = _Allocator())
967
968 template<typename _Tp, typename _Allocator = allocator<_Tp>,
969 typename = _RequireAllocator<_Allocator>>
970 list(size_t, _Tp, _Allocator = _Allocator())
972
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>;
978#endif
979#endif
980
981 template<typename _Tp, typename _Alloc>
982 inline bool
983 operator==(const list<_Tp, _Alloc>& __lhs,
984 const list<_Tp, _Alloc>& __rhs)
985 { return __lhs._M_base() == __rhs._M_base(); }
986
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(); }
992#else
993 template<typename _Tp, typename _Alloc>
994 inline bool
995 operator!=(const list<_Tp, _Alloc>& __lhs,
996 const list<_Tp, _Alloc>& __rhs)
997 { return __lhs._M_base() != __rhs._M_base(); }
998
999 template<typename _Tp, typename _Alloc>
1000 inline bool
1001 operator<(const list<_Tp, _Alloc>& __lhs,
1002 const list<_Tp, _Alloc>& __rhs)
1003 { return __lhs._M_base() < __rhs._M_base(); }
1004
1005 template<typename _Tp, typename _Alloc>
1006 inline bool
1007 operator<=(const list<_Tp, _Alloc>& __lhs,
1008 const list<_Tp, _Alloc>& __rhs)
1009 { return __lhs._M_base() <= __rhs._M_base(); }
1010
1011 template<typename _Tp, typename _Alloc>
1012 inline bool
1013 operator>=(const list<_Tp, _Alloc>& __lhs,
1014 const list<_Tp, _Alloc>& __rhs)
1015 { return __lhs._M_base() >= __rhs._M_base(); }
1016
1017 template<typename _Tp, typename _Alloc>
1018 inline bool
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
1023
1024 template<typename _Tp, typename _Alloc>
1025 inline void
1026 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
1027 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
1028 { __lhs.swap(__rhs); }
1029
1030} // namespace __debug
1031} // namespace std
1032
1033namespace __gnu_debug
1034{
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> >
1039 {
1040 typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It;
1041
1042 static typename _Distance_traits<_It>::__type
1043 _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
1044 {
1045 return __seq.empty()
1046 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
1047 }
1048 };
1049#endif
1050
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 }; };
1055#endif
1056}
1057
1058#endif
#define __glibcxx_check_insert(_Position)
Definition macros.h:143
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
Definition macros.h:356
#define __glibcxx_check_erase_range(_First, _Last)
Definition macros.h:245
#define __glibcxx_check_erase(_Position)
Definition macros.h:209
#define __glibcxx_check_insert_range(_Position, _First, _Last, _Dist)
Definition macros.h:177
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:826
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:127
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:51
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.
GNU debug classes for public use.
constexpr _Iterator __base(_Iterator __it)
initializer_list
is_nothrow_constructible
Definition type_traits:1236
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
Safe iterator wrapper.
constexpr _Iterator & base() noexcept
Return the underlying iterator.
bool _M_dereferenceable() const
Is the iterator dereferenceable?
The ranges::subrange class template.
Struct holding two objects of arbitrary type.
Definition stl_pair.h:286
_T2 second
The second member.
Definition stl_pair.h:291
Traits class for iterators.
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition stl_list.h:1005
bool _M_attached_to(const _Safe_sequence_base *__seq) const
Definition safe_base.h:145
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.
Definition debug/list:57