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