libstdc++-v3/include/debug/list

   1 // Debugging list implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2015 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 #if __cplusplus >= 201103L
 529         noexcept( noexcept(declval<_Base>().swap(__x)) )
 530 #endif
 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   template<typename _Tp, typename _Alloc>
 773     inline bool
 774     operator==(const list<_Tp, _Alloc>& __lhs,
 775                const list<_Tp, _Alloc>& __rhs)
 776     { return __lhs._M_base() == __rhs._M_base(); }
 777
 778   template<typename _Tp, typename _Alloc>
 779     inline bool
 780     operator!=(const list<_Tp, _Alloc>& __lhs,
 781                const list<_Tp, _Alloc>& __rhs)
 782     { return __lhs._M_base() != __rhs._M_base(); }
 783
 784   template<typename _Tp, typename _Alloc>
 785     inline bool
 786     operator<(const list<_Tp, _Alloc>& __lhs,
 787               const list<_Tp, _Alloc>& __rhs)
 788     { return __lhs._M_base() < __rhs._M_base(); }
 789
 790   template<typename _Tp, typename _Alloc>
 791     inline bool
 792     operator<=(const list<_Tp, _Alloc>& __lhs,
 793                const list<_Tp, _Alloc>& __rhs)
 794     { return __lhs._M_base() <= __rhs._M_base(); }
 795
 796   template<typename _Tp, typename _Alloc>
 797     inline bool
 798     operator>=(const list<_Tp, _Alloc>& __lhs,
 799                const list<_Tp, _Alloc>& __rhs)
 800     { return __lhs._M_base() >= __rhs._M_base(); }
 801
 802   template<typename _Tp, typename _Alloc>
 803     inline bool
 804     operator>(const list<_Tp, _Alloc>& __lhs,
 805               const list<_Tp, _Alloc>& __rhs)
 806     { return __lhs._M_base() > __rhs._M_base(); }
 807
 808   template<typename _Tp, typename _Alloc>
 809     inline void
 810     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
 811     { __lhs.swap(__rhs); }
 812
 813 } // namespace __debug
 814 } // namespace std
 815
 816 namespace __gnu_debug
 817 {
 818 #ifndef _GLIBCXX_USE_CXX11_ABI
 819   // If not using C++11 list::size() is not in O(1) so we do not use it.
 820   template<typename _Tp, typename _Alloc>
 821     struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
 822     {
 823       typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It;
 824
 825       static typename _Distance_traits<_It>::__type
 826       _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
 827       {
 828         return __seq.empty()
 829           ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality);
 830       }
 831     };
 832 #endif
 833
 834 #ifndef _GLIBCXX_DEBUG_PEDANTIC
 835   template<class _Tp, class _Alloc>
 836     struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
 837     { enum { __value = 1 }; };
 838 #endif
 839 }
 840
 841 #endif