libstdc++-v3/include/debug/list

   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