contrib/gcc-8.0/libstdc++-v3/include/debug/list

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