libstdc++
debug/list
Go to the documentation of this file.
1 // Debugging list implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2026 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>
37 namespace 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>
43 #include <debug/safe_container.h>
44 #include <debug/safe_iterator.h>
45 
46 namespace std _GLIBCXX_VISIBILITY(default)
47 {
48 namespace __debug
49 {
50  /// Class std::list with safety/checking/debug instrumentation.
51  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
52  class list
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>
57  {
58  typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
59  typedef __gnu_debug::_Safe_container<
60  list, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
61 
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;
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 
84  typedef __gnu_debug::_Safe_iterator<_Base_iterator, list>
85  iterator;
86  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
87  const_iterator;
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;
96  typedef std::reverse_iterator<iterator> reverse_iterator;
97  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
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 
114  list(initializer_list<value_type> __l,
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(
125  std::is_nothrow_constructible<_Base,
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())
158  : _Base(__gnu_debug::__base(
159  __glibcxx_check_valid_constructor_range(__first, __last)),
160  __gnu_debug::__base(__last), __a)
161  { }
162 
163 #if __glibcxx_containers_ranges // 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
189  assign(initializer_list<value_type> __l)
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  {
205  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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_containers_ranges // 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
254  iterator
255  begin() _GLIBCXX_NOEXCEPT
256  { return iterator(_Base::begin(), this); }
257 
258  _GLIBCXX_NODISCARD
259  const_iterator
260  begin() const _GLIBCXX_NOEXCEPT
261  { return const_iterator(_Base::begin(), this); }
262 
263  _GLIBCXX_NODISCARD
264  iterator
265  end() _GLIBCXX_NOEXCEPT
266  { return iterator(_Base::end(), this); }
267 
268  _GLIBCXX_NODISCARD
269  const_iterator
270  end() const _GLIBCXX_NOEXCEPT
271  { return const_iterator(_Base::end(), this); }
272 
273  _GLIBCXX_NODISCARD
274  reverse_iterator
275  rbegin() _GLIBCXX_NOEXCEPT
276  { return reverse_iterator(end()); }
277 
278  _GLIBCXX_NODISCARD
279  const_reverse_iterator
280  rbegin() const _GLIBCXX_NOEXCEPT
281  { return const_reverse_iterator(end()); }
282 
283  _GLIBCXX_NODISCARD
284  reverse_iterator
285  rend() _GLIBCXX_NOEXCEPT
286  { return reverse_iterator(begin()); }
287 
288  _GLIBCXX_NODISCARD
289  const_reverse_iterator
290  rend() const _GLIBCXX_NOEXCEPT
291  { return const_reverse_iterator(begin()); }
292 
293 #if __cplusplus >= 201103L
294  [[__nodiscard__]]
295  const_iterator
296  cbegin() const noexcept
297  { return const_iterator(_Base::begin(), this); }
298 
299  [[__nodiscard__]]
300  const_iterator
301  cend() const noexcept
302  { return const_iterator(_Base::end(), this); }
303 
304  [[__nodiscard__]]
305  const_reverse_iterator
306  crbegin() const noexcept
307  { return const_reverse_iterator(end()); }
308 
309  [[__nodiscard__]]
310  const_reverse_iterator
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  const list* __this = this;
325  __this->_M_detach_singular();
326 
327  // if __sz < size(), invalidate all iterators in [begin + __sz, end())
328  _Base_iterator __victim = _Base::begin();
329  _Base_iterator __end = _Base::end();
330  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
331  ++__victim;
332 
333  for (; __victim != __end; ++__victim)
334  this->_M_invalidate_if(_Equal(__victim));
335 
336  __try
337  {
338  _Base::resize(__sz);
339  }
340  __catch(...)
341  {
342  __this->_M_revalidate_singular();
343  __throw_exception_again;
344  }
345  }
346 
347  void
348  resize(size_type __sz, const _Tp& __c)
349  {
350  const list* __this = this;
351  __this->_M_detach_singular();
352 
353  // if __sz < size(), invalidate all iterators in [begin + __sz, end())
354  _Base_iterator __victim = _Base::begin();
355  _Base_iterator __end = _Base::end();
356  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
357  ++__victim;
358 
359  for (; __victim != __end; ++__victim)
360  this->_M_invalidate_if(_Equal(__victim));
361 
362  __try
363  {
364  _Base::resize(__sz, __c);
365  }
366  __catch(...)
367  {
368  __this->_M_revalidate_singular();
369  __throw_exception_again;
370  }
371  }
372 #else
373  void
374  resize(size_type __sz, _Tp __c = _Tp())
375  {
376  const list* __this = this;
377  __this->_M_detach_singular();
378 
379  // if __sz < size(), invalidate all iterators in [begin + __sz, end())
380  _Base_iterator __victim = _Base::begin();
381  _Base_iterator __end = _Base::end();
382  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
383  ++__victim;
384 
385  for (; __victim != __end; ++__victim)
386  this->_M_invalidate_if(_Equal(__victim));
387 
388  __try
389  {
390  _Base::resize(__sz, __c);
391  }
392  __catch(...)
393  {
394  __this->_M_revalidate_singular();
395  __throw_exception_again;
396  }
397  }
398 #endif
399 
400  // element access:
401  _GLIBCXX_NODISCARD
402  reference
403  front() _GLIBCXX_NOEXCEPT
404  {
405  __glibcxx_check_nonempty();
406  return _Base::front();
407  }
408 
409  _GLIBCXX_NODISCARD
410  const_reference
411  front() const _GLIBCXX_NOEXCEPT
412  {
413  __glibcxx_check_nonempty();
414  return _Base::front();
415  }
416 
417  _GLIBCXX_NODISCARD
418  reference
419  back() _GLIBCXX_NOEXCEPT
420  {
421  __glibcxx_check_nonempty();
422  return _Base::back();
423  }
424 
425  _GLIBCXX_NODISCARD
426  const_reference
427  back() const _GLIBCXX_NOEXCEPT
428  {
429  __glibcxx_check_nonempty();
430  return _Base::back();
431  }
432 
433  // 23.2.2.3 modifiers:
434  using _Base::push_front;
435 
436 #if __cplusplus >= 201103L
437  using _Base::emplace_front;
438 #endif
439 
440 #if __glibcxx_containers_ranges // C++ >= 23
441  using _Base::prepend_range;
442  using _Base::append_range;
443 #endif
444 
445  void
446  pop_front() _GLIBCXX_NOEXCEPT
447  {
448  __glibcxx_check_nonempty();
449  this->_M_invalidate_if(_Equal(_Base::begin()));
450  _Base::pop_front();
451  }
452 
453  using _Base::push_back;
454 
455 #if __cplusplus >= 201103L
456  using _Base::emplace_back;
457 #endif
458 
459  void
460  pop_back() _GLIBCXX_NOEXCEPT
461  {
462  __glibcxx_check_nonempty();
463  this->_M_invalidate_if(_Equal(--_Base::end()));
464  _Base::pop_back();
465  }
466 
467 #if __cplusplus >= 201103L
468  template<typename... _Args>
469  iterator
470  emplace(const_iterator __position, _Args&&... __args)
471  {
472  __glibcxx_check_insert(__position);
473  return { _Base::emplace(__position.base(),
474  std::forward<_Args>(__args)...), this };
475  }
476 #endif
477 
478  iterator
479 #if __cplusplus >= 201103L
480  insert(const_iterator __position, const _Tp& __x)
481 #else
482  insert(iterator __position, const _Tp& __x)
483 #endif
484  {
485  __glibcxx_check_insert(__position);
486  return iterator(_Base::insert(__position.base(), __x), this);
487  }
488 
489 #if __cplusplus >= 201103L
490  iterator
491  insert(const_iterator __position, _Tp&& __x)
492  { return emplace(__position, std::move(__x)); }
493 
494  iterator
495  insert(const_iterator __p, initializer_list<value_type> __l)
496  {
497  __glibcxx_check_insert(__p);
498  return { _Base::insert(__p.base(), __l), this };
499  }
500 #endif
501 
502 #if __cplusplus >= 201103L
503  iterator
504  insert(const_iterator __position, size_type __n, const _Tp& __x)
505  {
506  __glibcxx_check_insert(__position);
507  return { _Base::insert(__position.base(), __n, __x), this };
508  }
509 #else
510  void
511  insert(iterator __position, size_type __n, const _Tp& __x)
512  {
513  __glibcxx_check_insert(__position);
514  _Base::insert(__position.base(), __n, __x);
515  }
516 #endif
517 
518 #if __cplusplus >= 201103L
519  template<class _InputIterator,
520  typename = std::_RequireInputIter<_InputIterator>>
521  iterator
522  insert(const_iterator __position, _InputIterator __first,
523  _InputIterator __last)
524  {
525  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
526  __glibcxx_check_insert_range(__position, __first, __last, __dist);
527  if (__dist.second >= __gnu_debug::__dp_sign)
528  return
529  {
530  _Base::insert(__position.base(),
531  __gnu_debug::__unsafe(__first),
532  __gnu_debug::__unsafe(__last)),
533  this
534  };
535  else
536  return { _Base::insert(__position.base(), __first, __last), this };
537  }
538 #else
539  template<class _InputIterator>
540  void
541  insert(iterator __position, _InputIterator __first,
542  _InputIterator __last)
543  {
544  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
545  __glibcxx_check_insert_range(__position, __first, __last, __dist);
546 
547  if (__dist.second >= __gnu_debug::__dp_sign)
548  _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
549  __gnu_debug::__unsafe(__last));
550  else
551  _Base::insert(__position.base(), __first, __last);
552  }
553 #endif
554 
555 #if __glibcxx_containers_ranges // C++ >= 23
556  template<__detail::__container_compatible_range<_Tp> _Rg>
557  iterator
558  insert_range(const_iterator __position, _Rg&& __rg)
559  {
560  auto __ret = _Base::insert_range(__position.base(),
561  std::forward<_Rg>(__rg));
562  return { __ret, this };
563  }
564 #endif
565 
566  private:
567  _Base_iterator
568 #if __cplusplus >= 201103L
569  _M_erase(_Base_const_iterator __position) noexcept
570 #else
571  _M_erase(_Base_iterator __position)
572 #endif
573  {
574  this->_M_invalidate_if(_Equal(__position));
575  return _Base::erase(__position);
576  }
577 
578  public:
579  iterator
580 #if __cplusplus >= 201103L
581  erase(const_iterator __position) noexcept
582 #else
583  erase(iterator __position)
584 #endif
585  {
586  __glibcxx_check_erase(__position);
587  return iterator(_M_erase(__position.base()), this);
588  }
589 
590  iterator
591 #if __cplusplus >= 201103L
592  erase(const_iterator __first, const_iterator __last) noexcept
593 #else
594  erase(iterator __first, iterator __last)
595 #endif
596  {
597  // _GLIBCXX_RESOLVE_LIB_DEFECTS
598  // 151. can't currently clear() empty container
599  __glibcxx_check_erase_range(__first, __last);
600  for (_Base_const_iterator __victim = __first.base();
601  __victim != __last.base(); ++__victim)
602  {
603  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
604  _M_message(__gnu_debug::__msg_valid_range)
605  ._M_iterator(__first, "position")
606  ._M_iterator(__last, "last"));
607  this->_M_invalidate_if(_Equal(__victim));
608  }
609 
610  return iterator(_Base::erase(__first.base(), __last.base()), this);
611  }
612 
613  void
614  swap(list& __x)
615  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
616  {
617  _Safe::_M_swap(__x);
618  _Base::swap(__x);
619  }
620 
621  void
622  clear() _GLIBCXX_NOEXCEPT
623  {
624  _Base::clear();
625  this->_M_invalidate_all();
626  }
627 
628  // 23.2.2.4 list operations:
629  void
630 #if __cplusplus >= 201103L
631  splice(const_iterator __position, list&& __x) noexcept
632 #else
633  splice(iterator __position, list& __x)
634 #endif
635  {
636  _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this,
637  _M_message(__gnu_debug::__msg_self_splice)
638  ._M_sequence(*this, "this"));
639  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
640  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x));
641  }
642 
643 #if __cplusplus >= 201103L
644  void
645  splice(const_iterator __position, list& __x) noexcept
646  { splice(__position, std::move(__x)); }
647 #endif
648 
649  void
650 #if __cplusplus >= 201103L
651  splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
652 #else
653  splice(iterator __position, list& __x, iterator __i)
654 #endif
655  {
656  __glibcxx_check_insert(__position);
657 
658  // We used to perform the splice_alloc check: not anymore, redundant
659  // after implementing the relevant bits of N1599.
660 
661  _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
662  _M_message(__gnu_debug::__msg_splice_bad)
663  ._M_iterator(__i, "__i"));
664  _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)),
665  _M_message(__gnu_debug::__msg_splice_other)
666  ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
667 
668  // _GLIBCXX_RESOLVE_LIB_DEFECTS
669  // 250. splicing invalidates iterators
670  this->_M_transfer_from_if(__x, _Equal(__i.base()));
671  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
672  __i.base());
673  }
674 
675 #if __cplusplus >= 201103L
676  void
677  splice(const_iterator __position, list& __x, const_iterator __i) noexcept
678  { splice(__position, std::move(__x), __i); }
679 #endif
680 
681  void
682 #if __cplusplus >= 201103L
683  splice(const_iterator __position, list&& __x, const_iterator __first,
684  const_iterator __last) noexcept
685 #else
686  splice(iterator __position, list& __x, iterator __first,
687  iterator __last)
688 #endif
689  {
690  __glibcxx_check_insert(__position);
691  __glibcxx_check_valid_range(__first, __last);
692  _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)),
693  _M_message(__gnu_debug::__msg_splice_other)
694  ._M_sequence(__x, "x")
695  ._M_iterator(__first, "first"));
696 
697  // We used to perform the splice_alloc check: not anymore, redundant
698  // after implementing the relevant bits of N1599.
699 
700  for (_Base_const_iterator __tmp = __first.base();
701  __tmp != __last.base(); ++__tmp)
702  {
703  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
704  _M_message(__gnu_debug::__msg_valid_range)
705  ._M_iterator(__first, "first")
706  ._M_iterator(__last, "last"));
707  _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this
708  || __tmp != __position.base(),
709  _M_message(__gnu_debug::__msg_splice_overlap)
710  ._M_iterator(__tmp, "position")
711  ._M_iterator(__first, "first")
712  ._M_iterator(__last, "last"));
713 
714  // _GLIBCXX_RESOLVE_LIB_DEFECTS
715  // 250. splicing invalidates iterators
716  this->_M_transfer_from_if(__x, _Equal(__tmp));
717  }
718 
719  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
720  __first.base(), __last.base());
721  }
722 
723 #if __cplusplus >= 201103L
724  void
725  splice(const_iterator __position, list& __x,
726  const_iterator __first, const_iterator __last) noexcept
727  { splice(__position, std::move(__x), __first, __last); }
728 #endif
729 
730  private:
731 #if __cplusplus > 201703L
732  typedef size_type __remove_return_type;
733 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
734  __attribute__((__abi_tag__("__cxx20")))
735 # define _GLIBCXX20_ONLY(__expr) __expr
736 #else
737  typedef void __remove_return_type;
738 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
739 # define _GLIBCXX20_ONLY(__expr)
740 #endif
741 
742  public:
743  _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
744  __remove_return_type
745  remove(const _Tp& __value)
746  {
747  if (!this->_M_iterators && !this->_M_const_iterators)
748  return _Base::remove(__value);
749 
750 #if !_GLIBCXX_USE_CXX11_ABI
751  size_type __removed __attribute__((__unused__)) = 0;
752 #endif
753  _Base __to_destroy(get_allocator());
754  _Base_iterator __first = _Base::begin();
755  _Base_iterator __last = _Base::end();
756  while (__first != __last)
757  {
758  _Base_iterator __next = __first;
759  ++__next;
760  if (*__first == __value)
761  {
762  // _GLIBCXX_RESOLVE_LIB_DEFECTS
763  // 526. Is it undefined if a function in the standard changes
764  // in parameters?
765  this->_M_invalidate_if(_Equal(__first));
766  __to_destroy.splice(__to_destroy.begin(), *this, __first);
767 #if !_GLIBCXX_USE_CXX11_ABI
768  _GLIBCXX20_ONLY( __removed++ );
769 #endif
770  }
771 
772  __first = __next;
773  }
774 
775 #if !_GLIBCXX_USE_CXX11_ABI
776  return _GLIBCXX20_ONLY( __removed );
777 #else
778  return _GLIBCXX20_ONLY( __to_destroy.size() );
779 #endif
780  }
781 
782  template<class _Predicate>
783  __remove_return_type
784  remove_if(_Predicate __pred)
785  {
786  if (!this->_M_iterators && !this->_M_const_iterators)
787  return _Base::remove_if(__pred);
788 
789 #if !_GLIBCXX_USE_CXX11_ABI
790  size_type __removed __attribute__((__unused__)) = 0;
791 #endif
792  _Base __to_destroy(get_allocator());
793  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
794  {
795  _Base_iterator __next = __x;
796  ++__next;
797  if (__pred(*__x))
798  {
799  this->_M_invalidate_if(_Equal(__x));
800  __to_destroy.splice(__to_destroy.begin(), *this, __x);
801 #if !_GLIBCXX_USE_CXX11_ABI
802  _GLIBCXX20_ONLY( __removed++ );
803 #endif
804  }
805 
806  __x = __next;
807  }
808 
809 #if !_GLIBCXX_USE_CXX11_ABI
810  return _GLIBCXX20_ONLY( __removed );
811 #else
812  return _GLIBCXX20_ONLY( __to_destroy.size() );
813 #endif
814  }
815 
816  _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
817  __remove_return_type
818  unique()
819  {
820  if (!this->_M_iterators && !this->_M_const_iterators)
821  return _Base::unique();
822 
823  if (empty())
824  return _GLIBCXX20_ONLY(0);
825 
826 #if !_GLIBCXX_USE_CXX11_ABI
827  size_type __removed __attribute__((__unused__)) = 0;
828 #endif
829  _Base __to_destroy(get_allocator());
830  _Base_iterator __first = _Base::begin();
831  _Base_iterator __last = _Base::end();
832  _Base_iterator __next = __first;
833  while (++__next != __last)
834  if (*__first == *__next)
835  {
836  this->_M_invalidate_if(_Equal(__next));
837  __to_destroy.splice(__to_destroy.begin(), *this, __next);
838  __next = __first;
839 #if !_GLIBCXX_USE_CXX11_ABI
840  _GLIBCXX20_ONLY( __removed++ );
841 #endif
842  }
843  else
844  __first = __next;
845 
846 #if !_GLIBCXX_USE_CXX11_ABI
847  return _GLIBCXX20_ONLY( __removed );
848 #else
849  return _GLIBCXX20_ONLY( __to_destroy.size() );
850 #endif
851  }
852 
853  template<class _BinaryPredicate>
854  __remove_return_type
855  unique(_BinaryPredicate __binary_pred)
856  {
857  if (!this->_M_iterators && !this->_M_const_iterators)
858  return _Base::unique(__binary_pred);
859 
860  if (empty())
861  return _GLIBCXX20_ONLY(0);
862 
863 
864 #if !_GLIBCXX_USE_CXX11_ABI
865  size_type __removed __attribute__((__unused__)) = 0;
866 #endif
867  _Base __to_destroy(get_allocator());
868  _Base_iterator __first = _Base::begin();
869  _Base_iterator __last = _Base::end();
870  _Base_iterator __next = __first;
871  while (++__next != __last)
872  if (__binary_pred(*__first, *__next))
873  {
874  this->_M_invalidate_if(_Equal(__next));
875  __to_destroy.splice(__to_destroy.begin(), *this, __next);
876  __next = __first;
877 #if !_GLIBCXX_USE_CXX11_ABI
878  _GLIBCXX20_ONLY( __removed++ );
879 #endif
880  }
881  else
882  __first = __next;
883 
884 #if !_GLIBCXX_USE_CXX11_ABI
885  return _GLIBCXX20_ONLY( __removed );
886 #else
887  return _GLIBCXX20_ONLY( __to_destroy.size() );
888 #endif
889  }
890 
891 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
892 #undef _GLIBCXX20_ONLY
893 
894  void
895 #if __cplusplus >= 201103L
896  merge(list&& __x)
897 #else
898  merge(list& __x)
899 #endif
900  {
901  // _GLIBCXX_RESOLVE_LIB_DEFECTS
902  // 300. list::merge() specification incomplete
903  if (this != std::__addressof(__x))
904  {
905  __glibcxx_check_sorted(_Base::begin(), _Base::end());
906  __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
907  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
908  _Base::merge(_GLIBCXX_MOVE(__x));
909  }
910  }
911 
912 #if __cplusplus >= 201103L
913  void
914  merge(list& __x)
915  { merge(std::move(__x)); }
916 #endif
917 
918  template<class _Compare>
919  void
920 #if __cplusplus >= 201103L
921  merge(list&& __x, _Compare __comp)
922 #else
923  merge(list& __x, _Compare __comp)
924 #endif
925  {
926  // _GLIBCXX_RESOLVE_LIB_DEFECTS
927  // 300. list::merge() specification incomplete
928  if (this != std::__addressof(__x))
929  {
930  __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
931  __comp);
932  __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
933  __comp);
934  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
935  _Base::merge(_GLIBCXX_MOVE(__x), __comp);
936  }
937  }
938 
939 #if __cplusplus >= 201103L
940  template<typename _Compare>
941  void
942  merge(list& __x, _Compare __comp)
943  { merge(std::move(__x), __comp); }
944 #endif
945 
946  void
947  sort() { _Base::sort(); }
948 
949  template<typename _StrictWeakOrdering>
950  void
951  sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
952 
953  using _Base::reverse;
954 
955  _Base&
956  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
957 
958  const _Base&
959  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
960  };
961 
962 #if __cpp_deduction_guides >= 201606
963  template<typename _InputIterator, typename _ValT
964  = typename iterator_traits<_InputIterator>::value_type,
965  typename _Allocator = allocator<_ValT>,
966  typename = _RequireInputIter<_InputIterator>,
967  typename = _RequireAllocator<_Allocator>>
968  list(_InputIterator, _InputIterator, _Allocator = _Allocator())
969  -> list<_ValT, _Allocator>;
970 
971  template<typename _Tp, typename _Allocator = allocator<_Tp>,
972  typename = _RequireAllocator<_Allocator>>
973  list(size_t, _Tp, _Allocator = _Allocator())
974  -> list<_Tp, _Allocator>;
975 
976 #if __glibcxx_containers_ranges // C++ >= 23
977  template<ranges::input_range _Rg,
978  typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
979  list(from_range_t, _Rg&&, _Allocator = _Allocator())
980  -> list<ranges::range_value_t<_Rg>, _Allocator>;
981 #endif
982 #endif
983 
984  template<typename _Tp, typename _Alloc>
985  inline bool
986  operator==(const list<_Tp, _Alloc>& __lhs,
987  const list<_Tp, _Alloc>& __rhs)
988  { return __lhs._M_base() == __rhs._M_base(); }
989 
990 #if __cpp_lib_three_way_comparison
991  template<typename _Tp, typename _Alloc>
992  constexpr __detail::__synth3way_t<_Tp>
993  operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
994  { return __x._M_base() <=> __y._M_base(); }
995 #else
996  template<typename _Tp, typename _Alloc>
997  inline bool
998  operator!=(const list<_Tp, _Alloc>& __lhs,
999  const list<_Tp, _Alloc>& __rhs)
1000  { return __lhs._M_base() != __rhs._M_base(); }
1001 
1002  template<typename _Tp, typename _Alloc>
1003  inline bool
1004  operator<(const list<_Tp, _Alloc>& __lhs,
1005  const list<_Tp, _Alloc>& __rhs)
1006  { return __lhs._M_base() < __rhs._M_base(); }
1007 
1008  template<typename _Tp, typename _Alloc>
1009  inline bool
1010  operator<=(const list<_Tp, _Alloc>& __lhs,
1011  const list<_Tp, _Alloc>& __rhs)
1012  { return __lhs._M_base() <= __rhs._M_base(); }
1013 
1014  template<typename _Tp, typename _Alloc>
1015  inline bool
1016  operator>=(const list<_Tp, _Alloc>& __lhs,
1017  const list<_Tp, _Alloc>& __rhs)
1018  { return __lhs._M_base() >= __rhs._M_base(); }
1019 
1020  template<typename _Tp, typename _Alloc>
1021  inline bool
1022  operator>(const list<_Tp, _Alloc>& __lhs,
1023  const list<_Tp, _Alloc>& __rhs)
1024  { return __lhs._M_base() > __rhs._M_base(); }
1025 #endif // three-way comparison
1026 
1027  template<typename _Tp, typename _Alloc>
1028  inline void
1029  swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
1030  _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
1031  { __lhs.swap(__rhs); }
1032 
1033 } // namespace __debug
1034 
1035 #ifdef __glibcxx_erase_if // C++ >= 20 && HOSTED
1036 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1037  template<typename _Tp, typename _Alloc, typename _Predicate>
1038  inline typename __debug::list<_Tp, _Alloc>::size_type
1039  erase_if(__debug::list<_Tp, _Alloc>& __cont, _Predicate __pred)
1040  { return __cont.remove_if(__pred); }
1041 
1042  template<typename _Tp, typename _Alloc,
1043  typename _Up _GLIBCXX26_DEF_VAL_T(_Tp)>
1044  inline typename __debug::list<_Tp, _Alloc>::size_type
1045  erase(__debug::list<_Tp, _Alloc>& __cont, const _Up& __value)
1046  {
1047  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1048  // 4135. helper lambda of std::erase for list should specify return type
1049  return std::erase_if(__cont, [&](const auto& __elem) -> bool {
1050  return __elem == __value;
1051  });
1052  }
1053 _GLIBCXX_END_NAMESPACE_VERSION
1054 #endif // __glibcxx_erase_if
1055 } // namespace std
1056 
1057 namespace __gnu_debug
1058 {
1059 #ifndef _GLIBCXX_USE_CXX11_ABI
1060  // If not using C++11 list::size() is not in O(1) so we do not use it.
1061  template<typename _Tp, typename _Alloc>
1062  struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
1063  {
1064  typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It;
1065 
1066  static typename _Distance_traits<_It>::__type
1067  _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
1068  {
1069  return __seq.empty()
1070  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
1071  }
1072  };
1073 #endif
1074 
1075 #ifndef _GLIBCXX_DEBUG_PEDANTIC
1076  template<class _Tp, class _Alloc>
1077  struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
1078  { enum { __value = 1 }; };
1079 #endif
1080 }
1081 
1082 #endif
std::pair
Struct holding two objects of arbitrary type.
Definition: bits/stl_iterator.h:3122
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition: safe_container.h:41
std::empty
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:294
std::list
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:184
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition: helper_functions.h:339
std::chrono::operator>=
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:873
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:245
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
std::chrono::operator<=
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:859
std::__debug::list
Class std::list with safety/checking/debug instrumentation.
Definition: debug/list:38
safe_container.h
__gnu_debug
GNU debug classes for public use.
Definition: boost_concept_check.h:59
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: boost_concept_check.h:62
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:143
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::_Equal_to
Definition: safe_sequence.h:60
c++config.h
__glibcxx_check_sorted_pred
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
Definition: macros.h:356
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:52
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:209
__glibcxx_check_insert_range
#define __glibcxx_check_insert_range(_Position, _First, _Last, _Dist)
Definition: macros.h:177
std::reverse_iterator
Definition: bits/stl_iterator.h:131
__gnu_debug::_Safe_node_sequence
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Definition: safe_sequence.h:135
__gnu_debug::_Not_equal_to
Definition: safe_sequence.h:44
safe_sequence.h
std::assignable_from
concept assignable_from
[concept.assignable], concept assignable_from
Definition: concepts:149
std::pair::second
_T2 second
The second member.
Definition: stl_pair.h:309
std::chrono::operator>
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:866
std::is_nothrow_constructible
is_nothrow_constructible
Definition: type_traits:1315
std::chrono::operator<
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:826
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:72
list
safe_iterator.h