libstdc++-v3/include/debug/list

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