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