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