libstdc++
debug/list
Go to the documentation of this file.
1 // Debugging list implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2022 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 #pragma GCC system_header
33 
34 #include <bits/c++config.h>
35 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
36  template<typename _Tp, typename _Allocator> class list;
37 } } // namespace std::__debug
38 
39 #include <list>
40 #include <debug/safe_sequence.h>
41 #include <debug/safe_container.h>
42 #include <debug/safe_iterator.h>
43 
44 namespace std _GLIBCXX_VISIBILITY(default)
45 {
46 namespace __debug
47 {
48  /// Class std::list with safety/checking/debug instrumentation.
49  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
50  class list
51  : public __gnu_debug::_Safe_container<
52  list<_Tp, _Allocator>, _Allocator,
53  __gnu_debug::_Safe_node_sequence>,
54  public _GLIBCXX_STD_C::list<_Tp, _Allocator>
55  {
56  typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
57  typedef __gnu_debug::_Safe_container<
58  list, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
59 
60  typedef typename _Base::iterator _Base_iterator;
61  typedef typename _Base::const_iterator _Base_const_iterator;
62  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
63  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
64 
65  template<typename _ItT, typename _SeqT, typename _CatT>
66  friend class ::__gnu_debug::_Safe_iterator;
67 
68  // Reference wrapper for base class. Disambiguates list(const _Base&)
69  // from copy constructor by requiring a user-defined conversion.
70  // See PR libstdc++/90102.
71  struct _Base_ref
72  {
73  _Base_ref(const _Base& __r) : _M_ref(__r) { }
74 
75  const _Base& _M_ref;
76  };
77 
78  public:
79  typedef typename _Base::reference reference;
80  typedef typename _Base::const_reference const_reference;
81 
82  typedef __gnu_debug::_Safe_iterator<_Base_iterator, list>
83  iterator;
84  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
85  const_iterator;
86 
87  typedef typename _Base::size_type size_type;
88  typedef typename _Base::difference_type difference_type;
89 
90  typedef _Tp value_type;
91  typedef _Allocator allocator_type;
92  typedef typename _Base::pointer pointer;
93  typedef typename _Base::const_pointer const_pointer;
94  typedef std::reverse_iterator<iterator> reverse_iterator;
95  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
96 
97  // 23.2.2.1 construct/copy/destroy:
98 
99 #if __cplusplus < 201103L
100  list()
101  : _Base() { }
102 
103  list(const list& __x)
104  : _Base(__x) { }
105 
106  ~list() { }
107 #else
108  list() = default;
109  list(const list&) = default;
110  list(list&&) = default;
111 
112  list(initializer_list<value_type> __l,
113  const allocator_type& __a = allocator_type())
114  : _Base(__l, __a) { }
115 
116  ~list() = default;
117 
118  list(const list& __x, const __type_identity_t<allocator_type>& __a)
119  : _Base(__x, __a) { }
120 
121  list(list&& __x, const __type_identity_t<allocator_type>& __a)
122  noexcept(
123  std::is_nothrow_constructible<_Base,
124  _Base, const allocator_type&>::value )
125  : _Safe(std::move(__x), __a),
126  _Base(std::move(__x), __a) { }
127 #endif
128 
129  explicit
130  list(const _Allocator& __a) _GLIBCXX_NOEXCEPT
131  : _Base(__a) { }
132 
133 #if __cplusplus >= 201103L
134  explicit
135  list(size_type __n, const allocator_type& __a = allocator_type())
136  : _Base(__n, __a) { }
137 
138  list(size_type __n, const __type_identity_t<_Tp>& __value,
139  const _Allocator& __a = _Allocator())
140  : _Base(__n, __value, __a) { }
141 #else
142  explicit
143  list(size_type __n, const _Tp& __value = _Tp(),
144  const _Allocator& __a = _Allocator())
145  : _Base(__n, __value, __a) { }
146 #endif
147 
148 #if __cplusplus >= 201103L
149  template<class _InputIterator,
150  typename = std::_RequireInputIter<_InputIterator>>
151 #else
152  template<class _InputIterator>
153 #endif
154  list(_InputIterator __first, _InputIterator __last,
155  const _Allocator& __a = _Allocator())
156  : _Base(__gnu_debug::__base(
157  __glibcxx_check_valid_constructor_range(__first, __last)),
158  __gnu_debug::__base(__last), __a)
159  { }
160 
161  list(_Base_ref __x)
162  : _Base(__x._M_ref) { }
163 
164 #if __cplusplus >= 201103L
165  list&
166  operator=(const list&) = default;
167 
168  list&
169  operator=(list&&) = default;
170 
171  list&
172  operator=(initializer_list<value_type> __l)
173  {
174  this->_M_invalidate_all();
175  _Base::operator=(__l);
176  return *this;
177  }
178 
179  void
180  assign(initializer_list<value_type> __l)
181  {
182  _Base::assign(__l);
183  this->_M_invalidate_all();
184  }
185 #endif
186 
187 #if __cplusplus >= 201103L
188  template<class _InputIterator,
189  typename = std::_RequireInputIter<_InputIterator>>
190 #else
191  template<class _InputIterator>
192 #endif
193  void
194  assign(_InputIterator __first, _InputIterator __last)
195  {
196  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
197  __glibcxx_check_valid_range2(__first, __last, __dist);
198 
199  if (__dist.second >= __gnu_debug::__dp_sign)
200  _Base::assign(__gnu_debug::__unsafe(__first),
201  __gnu_debug::__unsafe(__last));
202  else
203  _Base::assign(__first, __last);
204 
205  this->_M_invalidate_all();
206  }
207 
208  void
209  assign(size_type __n, const _Tp& __t)
210  {
211  _Base::assign(__n, __t);
212  this->_M_invalidate_all();
213  }
214 
215  using _Base::get_allocator;
216 
217  // iterators:
218  _GLIBCXX_NODISCARD
219  iterator
220  begin() _GLIBCXX_NOEXCEPT
221  { return iterator(_Base::begin(), this); }
222 
223  _GLIBCXX_NODISCARD
224  const_iterator
225  begin() const _GLIBCXX_NOEXCEPT
226  { return const_iterator(_Base::begin(), this); }
227 
228  _GLIBCXX_NODISCARD
229  iterator
230  end() _GLIBCXX_NOEXCEPT
231  { return iterator(_Base::end(), this); }
232 
233  _GLIBCXX_NODISCARD
234  const_iterator
235  end() const _GLIBCXX_NOEXCEPT
236  { return const_iterator(_Base::end(), this); }
237 
238  _GLIBCXX_NODISCARD
239  reverse_iterator
240  rbegin() _GLIBCXX_NOEXCEPT
241  { return reverse_iterator(end()); }
242 
243  _GLIBCXX_NODISCARD
244  const_reverse_iterator
245  rbegin() const _GLIBCXX_NOEXCEPT
246  { return const_reverse_iterator(end()); }
247 
248  _GLIBCXX_NODISCARD
249  reverse_iterator
250  rend() _GLIBCXX_NOEXCEPT
251  { return reverse_iterator(begin()); }
252 
253  _GLIBCXX_NODISCARD
254  const_reverse_iterator
255  rend() const _GLIBCXX_NOEXCEPT
256  { return const_reverse_iterator(begin()); }
257 
258 #if __cplusplus >= 201103L
259  [[__nodiscard__]]
260  const_iterator
261  cbegin() const noexcept
262  { return const_iterator(_Base::begin(), this); }
263 
264  [[__nodiscard__]]
265  const_iterator
266  cend() const noexcept
267  { return const_iterator(_Base::end(), this); }
268 
269  [[__nodiscard__]]
270  const_reverse_iterator
271  crbegin() const noexcept
272  { return const_reverse_iterator(end()); }
273 
274  [[__nodiscard__]]
275  const_reverse_iterator
276  crend() const noexcept
277  { return const_reverse_iterator(begin()); }
278 #endif
279 
280  // 23.2.2.2 capacity:
281  using _Base::empty;
282  using _Base::size;
283  using _Base::max_size;
284 
285 #if __cplusplus >= 201103L
286  void
287  resize(size_type __sz)
288  {
289  this->_M_detach_singular();
290 
291  // if __sz < size(), invalidate all iterators in [begin + __sz, end())
292  _Base_iterator __victim = _Base::begin();
293  _Base_iterator __end = _Base::end();
294  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
295  ++__victim;
296 
297  for (; __victim != __end; ++__victim)
298  this->_M_invalidate_if(_Equal(__victim));
299 
300  __try
301  {
302  _Base::resize(__sz);
303  }
304  __catch(...)
305  {
306  this->_M_revalidate_singular();
307  __throw_exception_again;
308  }
309  }
310 
311  void
312  resize(size_type __sz, const _Tp& __c)
313  {
314  this->_M_detach_singular();
315 
316  // if __sz < size(), invalidate all iterators in [begin + __sz, end())
317  _Base_iterator __victim = _Base::begin();
318  _Base_iterator __end = _Base::end();
319  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
320  ++__victim;
321 
322  for (; __victim != __end; ++__victim)
323  this->_M_invalidate_if(_Equal(__victim));
324 
325  __try
326  {
327  _Base::resize(__sz, __c);
328  }
329  __catch(...)
330  {
331  this->_M_revalidate_singular();
332  __throw_exception_again;
333  }
334  }
335 #else
336  void
337  resize(size_type __sz, _Tp __c = _Tp())
338  {
339  this->_M_detach_singular();
340 
341  // if __sz < size(), invalidate all iterators in [begin + __sz, end())
342  _Base_iterator __victim = _Base::begin();
343  _Base_iterator __end = _Base::end();
344  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
345  ++__victim;
346 
347  for (; __victim != __end; ++__victim)
348  this->_M_invalidate_if(_Equal(__victim));
349 
350  __try
351  {
352  _Base::resize(__sz, __c);
353  }
354  __catch(...)
355  {
356  this->_M_revalidate_singular();
357  __throw_exception_again;
358  }
359  }
360 #endif
361 
362  // element access:
363  _GLIBCXX_NODISCARD
364  reference
365  front() _GLIBCXX_NOEXCEPT
366  {
367  __glibcxx_check_nonempty();
368  return _Base::front();
369  }
370 
371  _GLIBCXX_NODISCARD
372  const_reference
373  front() const _GLIBCXX_NOEXCEPT
374  {
375  __glibcxx_check_nonempty();
376  return _Base::front();
377  }
378 
379  _GLIBCXX_NODISCARD
380  reference
381  back() _GLIBCXX_NOEXCEPT
382  {
383  __glibcxx_check_nonempty();
384  return _Base::back();
385  }
386 
387  _GLIBCXX_NODISCARD
388  const_reference
389  back() const _GLIBCXX_NOEXCEPT
390  {
391  __glibcxx_check_nonempty();
392  return _Base::back();
393  }
394 
395  // 23.2.2.3 modifiers:
396  using _Base::push_front;
397 
398 #if __cplusplus >= 201103L
399  using _Base::emplace_front;
400 #endif
401 
402  void
403  pop_front() _GLIBCXX_NOEXCEPT
404  {
405  __glibcxx_check_nonempty();
406  this->_M_invalidate_if(_Equal(_Base::begin()));
407  _Base::pop_front();
408  }
409 
410  using _Base::push_back;
411 
412 #if __cplusplus >= 201103L
413  using _Base::emplace_back;
414 #endif
415 
416  void
417  pop_back() _GLIBCXX_NOEXCEPT
418  {
419  __glibcxx_check_nonempty();
420  this->_M_invalidate_if(_Equal(--_Base::end()));
421  _Base::pop_back();
422  }
423 
424 #if __cplusplus >= 201103L
425  template<typename... _Args>
426  iterator
427  emplace(const_iterator __position, _Args&&... __args)
428  {
429  __glibcxx_check_insert(__position);
430  return { _Base::emplace(__position.base(),
431  std::forward<_Args>(__args)...), this };
432  }
433 #endif
434 
435  iterator
436 #if __cplusplus >= 201103L
437  insert(const_iterator __position, const _Tp& __x)
438 #else
439  insert(iterator __position, const _Tp& __x)
440 #endif
441  {
442  __glibcxx_check_insert(__position);
443  return iterator(_Base::insert(__position.base(), __x), this);
444  }
445 
446 #if __cplusplus >= 201103L
447  iterator
448  insert(const_iterator __position, _Tp&& __x)
449  { return emplace(__position, std::move(__x)); }
450 
451  iterator
452  insert(const_iterator __p, initializer_list<value_type> __l)
453  {
454  __glibcxx_check_insert(__p);
455  return { _Base::insert(__p.base(), __l), this };
456  }
457 #endif
458 
459 #if __cplusplus >= 201103L
460  iterator
461  insert(const_iterator __position, size_type __n, const _Tp& __x)
462  {
463  __glibcxx_check_insert(__position);
464  return { _Base::insert(__position.base(), __n, __x), this };
465  }
466 #else
467  void
468  insert(iterator __position, size_type __n, const _Tp& __x)
469  {
470  __glibcxx_check_insert(__position);
471  _Base::insert(__position.base(), __n, __x);
472  }
473 #endif
474 
475 #if __cplusplus >= 201103L
476  template<class _InputIterator,
477  typename = std::_RequireInputIter<_InputIterator>>
478  iterator
479  insert(const_iterator __position, _InputIterator __first,
480  _InputIterator __last)
481  {
482  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
483  __glibcxx_check_insert_range(__position, __first, __last, __dist);
484  if (__dist.second >= __gnu_debug::__dp_sign)
485  return
486  {
487  _Base::insert(__position.base(),
488  __gnu_debug::__unsafe(__first),
489  __gnu_debug::__unsafe(__last)),
490  this
491  };
492  else
493  return { _Base::insert(__position.base(), __first, __last), this };
494  }
495 #else
496  template<class _InputIterator>
497  void
498  insert(iterator __position, _InputIterator __first,
499  _InputIterator __last)
500  {
501  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
502  __glibcxx_check_insert_range(__position, __first, __last, __dist);
503 
504  if (__dist.second >= __gnu_debug::__dp_sign)
505  _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
506  __gnu_debug::__unsafe(__last));
507  else
508  _Base::insert(__position.base(), __first, __last);
509  }
510 #endif
511 
512  private:
513  _Base_iterator
514 #if __cplusplus >= 201103L
515  _M_erase(_Base_const_iterator __position) noexcept
516 #else
517  _M_erase(_Base_iterator __position)
518 #endif
519  {
520  this->_M_invalidate_if(_Equal(__position));
521  return _Base::erase(__position);
522  }
523 
524  public:
525  iterator
526 #if __cplusplus >= 201103L
527  erase(const_iterator __position) noexcept
528 #else
529  erase(iterator __position)
530 #endif
531  {
532  __glibcxx_check_erase(__position);
533  return iterator(_M_erase(__position.base()), this);
534  }
535 
536  iterator
537 #if __cplusplus >= 201103L
538  erase(const_iterator __first, const_iterator __last) noexcept
539 #else
540  erase(iterator __first, iterator __last)
541 #endif
542  {
543  // _GLIBCXX_RESOLVE_LIB_DEFECTS
544  // 151. can't currently clear() empty container
545  __glibcxx_check_erase_range(__first, __last);
546  for (_Base_const_iterator __victim = __first.base();
547  __victim != __last.base(); ++__victim)
548  {
549  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
550  _M_message(__gnu_debug::__msg_valid_range)
551  ._M_iterator(__first, "position")
552  ._M_iterator(__last, "last"));
553  this->_M_invalidate_if(_Equal(__victim));
554  }
555 
556  return iterator(_Base::erase(__first.base(), __last.base()), this);
557  }
558 
559  void
560  swap(list& __x)
561  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
562  {
563  _Safe::_M_swap(__x);
564  _Base::swap(__x);
565  }
566 
567  void
568  clear() _GLIBCXX_NOEXCEPT
569  {
570  _Base::clear();
571  this->_M_invalidate_all();
572  }
573 
574  // 23.2.2.4 list operations:
575  void
576 #if __cplusplus >= 201103L
577  splice(const_iterator __position, list&& __x) noexcept
578 #else
579  splice(iterator __position, list& __x)
580 #endif
581  {
582  _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this,
583  _M_message(__gnu_debug::__msg_self_splice)
584  ._M_sequence(*this, "this"));
585  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
586  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x));
587  }
588 
589 #if __cplusplus >= 201103L
590  void
591  splice(const_iterator __position, list& __x) noexcept
592  { splice(__position, std::move(__x)); }
593 #endif
594 
595  void
596 #if __cplusplus >= 201103L
597  splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
598 #else
599  splice(iterator __position, list& __x, iterator __i)
600 #endif
601  {
602  __glibcxx_check_insert(__position);
603 
604  // We used to perform the splice_alloc check: not anymore, redundant
605  // after implementing the relevant bits of N1599.
606 
607  _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
608  _M_message(__gnu_debug::__msg_splice_bad)
609  ._M_iterator(__i, "__i"));
610  _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)),
611  _M_message(__gnu_debug::__msg_splice_other)
612  ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
613 
614  // _GLIBCXX_RESOLVE_LIB_DEFECTS
615  // 250. splicing invalidates iterators
616  this->_M_transfer_from_if(__x, _Equal(__i.base()));
617  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
618  __i.base());
619  }
620 
621 #if __cplusplus >= 201103L
622  void
623  splice(const_iterator __position, list& __x, const_iterator __i) noexcept
624  { splice(__position, std::move(__x), __i); }
625 #endif
626 
627  void
628 #if __cplusplus >= 201103L
629  splice(const_iterator __position, list&& __x, const_iterator __first,
630  const_iterator __last) noexcept
631 #else
632  splice(iterator __position, list& __x, iterator __first,
633  iterator __last)
634 #endif
635  {
636  __glibcxx_check_insert(__position);
637  __glibcxx_check_valid_range(__first, __last);
638  _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)),
639  _M_message(__gnu_debug::__msg_splice_other)
640  ._M_sequence(__x, "x")
641  ._M_iterator(__first, "first"));
642 
643  // We used to perform the splice_alloc check: not anymore, redundant
644  // after implementing the relevant bits of N1599.
645 
646  for (_Base_const_iterator __tmp = __first.base();
647  __tmp != __last.base(); ++__tmp)
648  {
649  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
650  _M_message(__gnu_debug::__msg_valid_range)
651  ._M_iterator(__first, "first")
652  ._M_iterator(__last, "last"));
653  _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this
654  || __tmp != __position.base(),
655  _M_message(__gnu_debug::__msg_splice_overlap)
656  ._M_iterator(__tmp, "position")
657  ._M_iterator(__first, "first")
658  ._M_iterator(__last, "last"));
659 
660  // _GLIBCXX_RESOLVE_LIB_DEFECTS
661  // 250. splicing invalidates iterators
662  this->_M_transfer_from_if(__x, _Equal(__tmp));
663  }
664 
665  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
666  __first.base(), __last.base());
667  }
668 
669 #if __cplusplus >= 201103L
670  void
671  splice(const_iterator __position, list& __x,
672  const_iterator __first, const_iterator __last) noexcept
673  { splice(__position, std::move(__x), __first, __last); }
674 #endif
675 
676  private:
677 #if __cplusplus > 201703L
678  typedef size_type __remove_return_type;
679 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
680  __attribute__((__abi_tag__("__cxx20")))
681 # define _GLIBCXX20_ONLY(__expr) __expr
682 #else
683  typedef void __remove_return_type;
684 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
685 # define _GLIBCXX20_ONLY(__expr)
686 #endif
687 
688  public:
689  _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
690  __remove_return_type
691  remove(const _Tp& __value)
692  {
693  if (!this->_M_iterators && !this->_M_const_iterators)
694  return _Base::remove(__value);
695 
696 #if !_GLIBCXX_USE_CXX11_ABI
697  size_type __removed __attribute__((__unused__)) = 0;
698 #endif
699  _Base __to_destroy(get_allocator());
700  _Base_iterator __first = _Base::begin();
701  _Base_iterator __last = _Base::end();
702  while (__first != __last)
703  {
704  _Base_iterator __next = __first;
705  ++__next;
706  if (*__first == __value)
707  {
708  // _GLIBCXX_RESOLVE_LIB_DEFECTS
709  // 526. Is it undefined if a function in the standard changes
710  // in parameters?
711  this->_M_invalidate_if(_Equal(__first));
712  __to_destroy.splice(__to_destroy.begin(), *this, __first);
713 #if !_GLIBCXX_USE_CXX11_ABI
714  _GLIBCXX20_ONLY( __removed++ );
715 #endif
716  }
717 
718  __first = __next;
719  }
720 
721 #if !_GLIBCXX_USE_CXX11_ABI
722  return _GLIBCXX20_ONLY( __removed );
723 #else
724  return _GLIBCXX20_ONLY( __to_destroy.size() );
725 #endif
726  }
727 
728  template<class _Predicate>
729  __remove_return_type
730  remove_if(_Predicate __pred)
731  {
732  if (!this->_M_iterators && !this->_M_const_iterators)
733  return _Base::remove_if(__pred);
734 
735 #if !_GLIBCXX_USE_CXX11_ABI
736  size_type __removed __attribute__((__unused__)) = 0;
737 #endif
738  _Base __to_destroy(get_allocator());
739  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
740  {
741  _Base_iterator __next = __x;
742  ++__next;
743  if (__pred(*__x))
744  {
745  this->_M_invalidate_if(_Equal(__x));
746  __to_destroy.splice(__to_destroy.begin(), *this, __x);
747 #if !_GLIBCXX_USE_CXX11_ABI
748  _GLIBCXX20_ONLY( __removed++ );
749 #endif
750  }
751 
752  __x = __next;
753  }
754 
755 #if !_GLIBCXX_USE_CXX11_ABI
756  return _GLIBCXX20_ONLY( __removed );
757 #else
758  return _GLIBCXX20_ONLY( __to_destroy.size() );
759 #endif
760  }
761 
762  _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
763  __remove_return_type
764  unique()
765  {
766  if (!this->_M_iterators && !this->_M_const_iterators)
767  return _Base::unique();
768 
769  if (empty())
770  return _GLIBCXX20_ONLY(0);
771 
772 #if !_GLIBCXX_USE_CXX11_ABI
773  size_type __removed __attribute__((__unused__)) = 0;
774 #endif
775  _Base __to_destroy(get_allocator());
776  _Base_iterator __first = _Base::begin();
777  _Base_iterator __last = _Base::end();
778  _Base_iterator __next = __first;
779  while (++__next != __last)
780  if (*__first == *__next)
781  {
782  this->_M_invalidate_if(_Equal(__next));
783  __to_destroy.splice(__to_destroy.begin(), *this, __next);
784  __next = __first;
785 #if !_GLIBCXX_USE_CXX11_ABI
786  _GLIBCXX20_ONLY( __removed++ );
787 #endif
788  }
789  else
790  __first = __next;
791 
792 #if !_GLIBCXX_USE_CXX11_ABI
793  return _GLIBCXX20_ONLY( __removed );
794 #else
795  return _GLIBCXX20_ONLY( __to_destroy.size() );
796 #endif
797  }
798 
799  template<class _BinaryPredicate>
800  __remove_return_type
801  unique(_BinaryPredicate __binary_pred)
802  {
803  if (!this->_M_iterators && !this->_M_const_iterators)
804  return _Base::unique(__binary_pred);
805 
806  if (empty())
807  return _GLIBCXX20_ONLY(0);
808 
809 
810 #if !_GLIBCXX_USE_CXX11_ABI
811  size_type __removed __attribute__((__unused__)) = 0;
812 #endif
813  _Base __to_destroy(get_allocator());
814  _Base_iterator __first = _Base::begin();
815  _Base_iterator __last = _Base::end();
816  _Base_iterator __next = __first;
817  while (++__next != __last)
818  if (__binary_pred(*__first, *__next))
819  {
820  this->_M_invalidate_if(_Equal(__next));
821  __to_destroy.splice(__to_destroy.begin(), *this, __next);
822  __next = __first;
823 #if !_GLIBCXX_USE_CXX11_ABI
824  _GLIBCXX20_ONLY( __removed++ );
825 #endif
826  }
827  else
828  __first = __next;
829 
830 #if !_GLIBCXX_USE_CXX11_ABI
831  return _GLIBCXX20_ONLY( __removed );
832 #else
833  return _GLIBCXX20_ONLY( __to_destroy.size() );
834 #endif
835  }
836 
837 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
838 #undef _GLIBCXX20_ONLY
839 
840  void
841 #if __cplusplus >= 201103L
842  merge(list&& __x)
843 #else
844  merge(list& __x)
845 #endif
846  {
847  // _GLIBCXX_RESOLVE_LIB_DEFECTS
848  // 300. list::merge() specification incomplete
849  if (this != std::__addressof(__x))
850  {
851  __glibcxx_check_sorted(_Base::begin(), _Base::end());
852  __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
853  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
854  _Base::merge(_GLIBCXX_MOVE(__x));
855  }
856  }
857 
858 #if __cplusplus >= 201103L
859  void
860  merge(list& __x)
861  { merge(std::move(__x)); }
862 #endif
863 
864  template<class _Compare>
865  void
866 #if __cplusplus >= 201103L
867  merge(list&& __x, _Compare __comp)
868 #else
869  merge(list& __x, _Compare __comp)
870 #endif
871  {
872  // _GLIBCXX_RESOLVE_LIB_DEFECTS
873  // 300. list::merge() specification incomplete
874  if (this != std::__addressof(__x))
875  {
876  __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
877  __comp);
878  __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
879  __comp);
880  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
881  _Base::merge(_GLIBCXX_MOVE(__x), __comp);
882  }
883  }
884 
885 #if __cplusplus >= 201103L
886  template<typename _Compare>
887  void
888  merge(list& __x, _Compare __comp)
889  { merge(std::move(__x), __comp); }
890 #endif
891 
892  void
893  sort() { _Base::sort(); }
894 
895  template<typename _StrictWeakOrdering>
896  void
897  sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
898 
899  using _Base::reverse;
900 
901  _Base&
902  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
903 
904  const _Base&
905  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
906  };
907 
908 #if __cpp_deduction_guides >= 201606
909  template<typename _InputIterator, typename _ValT
910  = typename iterator_traits<_InputIterator>::value_type,
911  typename _Allocator = allocator<_ValT>,
912  typename = _RequireInputIter<_InputIterator>,
913  typename = _RequireAllocator<_Allocator>>
914  list(_InputIterator, _InputIterator, _Allocator = _Allocator())
915  -> list<_ValT, _Allocator>;
916 
917  template<typename _Tp, typename _Allocator = allocator<_Tp>,
918  typename = _RequireAllocator<_Allocator>>
919  list(size_t, _Tp, _Allocator = _Allocator())
920  -> list<_Tp, _Allocator>;
921 #endif
922 
923  template<typename _Tp, typename _Alloc>
924  inline bool
925  operator==(const list<_Tp, _Alloc>& __lhs,
926  const list<_Tp, _Alloc>& __rhs)
927  { return __lhs._M_base() == __rhs._M_base(); }
928 
929 #if __cpp_lib_three_way_comparison
930  template<typename _Tp, typename _Alloc>
931  constexpr __detail::__synth3way_t<_Tp>
932  operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
933  { return __x._M_base() <=> __y._M_base(); }
934 #else
935  template<typename _Tp, typename _Alloc>
936  inline bool
937  operator!=(const list<_Tp, _Alloc>& __lhs,
938  const list<_Tp, _Alloc>& __rhs)
939  { return __lhs._M_base() != __rhs._M_base(); }
940 
941  template<typename _Tp, typename _Alloc>
942  inline bool
943  operator<(const list<_Tp, _Alloc>& __lhs,
944  const list<_Tp, _Alloc>& __rhs)
945  { return __lhs._M_base() < __rhs._M_base(); }
946 
947  template<typename _Tp, typename _Alloc>
948  inline bool
949  operator<=(const list<_Tp, _Alloc>& __lhs,
950  const list<_Tp, _Alloc>& __rhs)
951  { return __lhs._M_base() <= __rhs._M_base(); }
952 
953  template<typename _Tp, typename _Alloc>
954  inline bool
955  operator>=(const list<_Tp, _Alloc>& __lhs,
956  const list<_Tp, _Alloc>& __rhs)
957  { return __lhs._M_base() >= __rhs._M_base(); }
958 
959  template<typename _Tp, typename _Alloc>
960  inline bool
961  operator>(const list<_Tp, _Alloc>& __lhs,
962  const list<_Tp, _Alloc>& __rhs)
963  { return __lhs._M_base() > __rhs._M_base(); }
964 #endif // three-way comparison
965 
966  template<typename _Tp, typename _Alloc>
967  inline void
968  swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
969  _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
970  { __lhs.swap(__rhs); }
971 
972 } // namespace __debug
973 } // namespace std
974 
975 namespace __gnu_debug
976 {
977 #ifndef _GLIBCXX_USE_CXX11_ABI
978  // If not using C++11 list::size() is not in O(1) so we do not use it.
979  template<typename _Tp, typename _Alloc>
980  struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
981  {
982  typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It;
983 
984  static typename _Distance_traits<_It>::__type
985  _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
986  {
987  return __seq.empty()
988  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
989  }
990  };
991 #endif
992 
993 #ifndef _GLIBCXX_DEBUG_PEDANTIC
994  template<class _Tp, class _Alloc>
995  struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
996  { enum { __value = 1 }; };
997 #endif
998 }
999 
1000 #endif