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