libstdc++-v3/include/debug/list

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