libstdc++
debug/list
Go to the documentation of this file.
1 // Debugging list implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2025 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  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_containers_ranges // 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>
466  iterator
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 
475  iterator
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
487  iterator
488  insert(const_iterator __position, _Tp&& __x)
489  { return emplace(__position, std::move(__x)); }
490 
491  iterator
492  insert(const_iterator __p, initializer_list<value_type> __l)
493  {
494  __glibcxx_check_insert(__p);
495  return { _Base::insert(__p.base(), __l), this };
496  }
497 #endif
498 
499 #if __cplusplus >= 201103L
500  iterator
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>>
518  iterator
519  insert(const_iterator __position, _InputIterator __first,
520  _InputIterator __last)
521  {
522  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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  {
541  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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_containers_ranges // C++ >= 23
553  template<__detail::__container_compatible_range<_Tp> _Rg>
554  iterator
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:
564  _Base_iterator
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:
576  iterator
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 
587  iterator
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
961  = typename iterator_traits<_InputIterator>::value_type,
962  typename _Allocator = allocator<_ValT>,
963  typename = _RequireInputIter<_InputIterator>,
964  typename = _RequireAllocator<_Allocator>>
965  list(_InputIterator, _InputIterator, _Allocator = _Allocator())
966  -> list<_ValT, _Allocator>;
967 
968  template<typename _Tp, typename _Allocator = allocator<_Tp>,
969  typename = _RequireAllocator<_Allocator>>
970  list(size_t, _Tp, _Allocator = _Allocator())
971  -> list<_Tp, _Allocator>;
972 
973 #if __glibcxx_containers_ranges // 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 
1033 namespace __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