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 <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 iterator(_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 iterator(_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 iterator(_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         return iterator(_Base::erase(__first.base(), __last.base()), this);
 534       }
 535
 536       void
 537       swap(list& __x)
 538       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
 539       {
 540         _Safe::_M_swap(__x);
 541         _Base::swap(__x);
 542       }
 543
 544       void
 545       clear() _GLIBCXX_NOEXCEPT
 546       {
 547         _Base::clear();
 548         this->_M_invalidate_all();
 549       }
 550
 551       // 23.2.2.4 list operations:
 552       void
 553 #if __cplusplus >= 201103L
 554       splice(const_iterator __position, list&& __x) noexcept
 555 #else
 556       splice(iterator __position, list& __x)
 557 #endif
 558       {
 559         _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this,
 560                               _M_message(__gnu_debug::__msg_self_splice)
 561                               ._M_sequence(*this, "this"));
 562         this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
 563         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()));
 564       }
 565
 566 #if __cplusplus >= 201103L
 567       void
 568       splice(const_iterator __position, list& __x) noexcept
 569       { splice(__position, std::move(__x)); }
 570 #endif
 571
 572       void
 573 #if __cplusplus >= 201103L
 574       splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
 575 #else
 576       splice(iterator __position, list& __x, iterator __i)
 577 #endif
 578       {
 579         __glibcxx_check_insert(__position);
 580
 581         // We used to perform the splice_alloc check:  not anymore, redundant
 582         // after implementing the relevant bits of N1599.
 583
 584         _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
 585                               _M_message(__gnu_debug::__msg_splice_bad)
 586                               ._M_iterator(__i, "__i"));
 587         _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)),
 588                               _M_message(__gnu_debug::__msg_splice_other)
 589                              ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
 590
 591         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 592         // 250. splicing invalidates iterators
 593         this->_M_transfer_from_if(__x, _Equal(__i.base()));
 594         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 595                       __i.base());
 596       }
 597
 598 #if __cplusplus >= 201103L
 599       void
 600       splice(const_iterator __position, list& __x, const_iterator __i) noexcept
 601       { splice(__position, std::move(__x), __i); }
 602 #endif
 603
 604       void
 605 #if __cplusplus >= 201103L
 606       splice(const_iterator __position, list&& __x, const_iterator __first,
 607              const_iterator __last) noexcept
 608 #else
 609       splice(iterator __position, list& __x, iterator __first,
 610              iterator __last)
 611 #endif
 612       {
 613         __glibcxx_check_insert(__position);
 614         __glibcxx_check_valid_range(__first, __last);
 615         _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)),
 616                               _M_message(__gnu_debug::__msg_splice_other)
 617                               ._M_sequence(__x, "x")
 618                               ._M_iterator(__first, "first"));
 619
 620         // We used to perform the splice_alloc check:  not anymore, redundant
 621         // after implementing the relevant bits of N1599.
 622
 623         for (_Base_const_iterator __tmp = __first.base();
 624              __tmp != __last.base(); ++__tmp)
 625           {
 626             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 627                                   _M_message(__gnu_debug::__msg_valid_range)
 628                                   ._M_iterator(__first, "first")
 629                                   ._M_iterator(__last, "last"));
 630             _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this
 631                                   || __tmp != __position.base(),
 632                                 _M_message(__gnu_debug::__msg_splice_overlap)
 633                                   ._M_iterator(__tmp, "position")
 634                                   ._M_iterator(__first, "first")
 635                                   ._M_iterator(__last, "last"));
 636             // _GLIBCXX_RESOLVE_LIB_DEFECTS
 637             // 250. splicing invalidates iterators
 638             this->_M_transfer_from_if(__x, _Equal(__tmp));
 639           }
 640
 641         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 642                       __first.base(), __last.base());
 643       }
 644
 645 #if __cplusplus >= 201103L
 646       void
 647       splice(const_iterator __position, list& __x,
 648              const_iterator __first, const_iterator __last) noexcept
 649       { splice(__position, std::move(__x), __first, __last); }
 650 #endif
 651
 652     private:
 653 #if __cplusplus > 201703L
 654       typedef size_type __remove_return_type;
 655 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
 656       __attribute__((__abi_tag__("__cxx20")))
 657 # define _GLIBCXX20_ONLY(__expr) __expr
 658 #else
 659       typedef void __remove_return_type;
 660 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
 661 # define _GLIBCXX20_ONLY(__expr)
 662 #endif
 663
 664     public:
 665       _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
 666       __remove_return_type
 667       remove(const _Tp& __value)
 668       {
 669         if (!this->_M_iterators && !this->_M_const_iterators)
 670           return _Base::remove(__value);
 671
 672         size_type __removed __attribute__((__unused__)) = 0;
 673         _Base_iterator __first = _Base::begin();
 674         _Base_iterator __last = _Base::end();
 675         _Base_iterator __extra = __last;
 676         while (__first != __last)
 677           {
 678             if (*__first == __value)
 679               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 680               // 526. Is it undefined if a function in the standard changes
 681               // in parameters?
 682               if (std::__addressof(*__first) != std::__addressof(__value))
 683                 {
 684                   __first = _M_erase(__first);
 685                   _GLIBCXX20_ONLY( __removed++ );
 686                 }
 687               else
 688                 {
 689                   __extra = __first;
 690                   ++__first;
 691                 }
 692             else
 693               ++__first;
 694           }
 695
 696         if (__extra != __last)
 697           {
 698             _M_erase(__extra);
 699             _GLIBCXX20_ONLY( __removed++ );
 700           }
 701         return _GLIBCXX20_ONLY( __removed );
 702       }
 703
 704       template<class _Predicate>
 705         __remove_return_type
 706         remove_if(_Predicate __pred)
 707         {
 708           if (!this->_M_iterators && !this->_M_const_iterators)
 709             return _Base::remove_if(__pred);
 710
 711           size_type __removed __attribute__((__unused__)) = 0;
 712           for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
 713             if (__pred(*__x))
 714               {
 715                 __x = _M_erase(__x);
 716                 _GLIBCXX20_ONLY( __removed++ );
 717               }
 718             else
 719               ++__x;
 720
 721           return _GLIBCXX20_ONLY( __removed );
 722         }
 723
 724       _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
 725       __remove_return_type
 726       unique()
 727       {
 728         if (!this->_M_iterators && !this->_M_const_iterators)
 729           return _Base::unique();
 730
 731         if (empty())
 732           return _GLIBCXX20_ONLY(0);
 733
 734         size_type __removed __attribute__((__unused__)) = 0;
 735         _Base_iterator __first = _Base::begin();
 736         _Base_iterator __last = _Base::end();
 737         _Base_iterator __next = __first;
 738         while (++__next != __last)
 739           if (*__first == *__next)
 740             {
 741               _M_erase(__next);
 742               __next = __first;
 743               _GLIBCXX20_ONLY( __removed++ );
 744             }
 745           else
 746             __first = __next;
 747
 748         return _GLIBCXX20_ONLY( __removed );
 749       }
 750
 751       template<class _BinaryPredicate>
 752         __remove_return_type
 753         unique(_BinaryPredicate __binary_pred)
 754         {
 755           if (!this->_M_iterators && !this->_M_const_iterators)
 756             return _Base::unique(__binary_pred);
 757
 758           if (empty())
 759             return _GLIBCXX20_ONLY(0);
 760
 761           size_type __removed __attribute__((__unused__)) = 0;
 762           _Base_iterator __first = _Base::begin();
 763           _Base_iterator __last = _Base::end();
 764           _Base_iterator __next = __first;;
 765           while (++__next != __last)
 766             if (__binary_pred(*__first, *__next))
 767               {
 768                 _M_erase(__next);
 769                 __next = __first;
 770                 _GLIBCXX20_ONLY( __removed++ );
 771               }
 772             else
 773               __first = __next;
 774
 775           return _GLIBCXX20_ONLY( __removed );
 776         }
 777
 778 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
 779 #undef _GLIBCXX20_ONLY
 780
 781       void
 782 #if __cplusplus >= 201103L
 783       merge(list&& __x)
 784 #else
 785       merge(list& __x)
 786 #endif
 787       {
 788         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 789         // 300. list::merge() specification incomplete
 790         if (this != std::__addressof(__x))
 791           {
 792             __glibcxx_check_sorted(_Base::begin(), _Base::end());
 793             __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
 794             this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
 795             _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
 796           }
 797       }
 798
 799 #if __cplusplus >= 201103L
 800       void
 801       merge(list& __x)
 802       { merge(std::move(__x)); }
 803 #endif
 804
 805       template<class _Compare>
 806         void
 807 #if __cplusplus >= 201103L
 808         merge(list&& __x, _Compare __comp)
 809 #else
 810         merge(list& __x, _Compare __comp)
 811 #endif
 812         {
 813           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 814           // 300. list::merge() specification incomplete
 815           if (this != std::__addressof(__x))
 816             {
 817               __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
 818                                           __comp);
 819               __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
 820                                           __comp);
 821               this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
 822               _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
 823             }
 824         }
 825
 826 #if __cplusplus >= 201103L
 827       template<typename _Compare>
 828         void
 829         merge(list& __x, _Compare __comp)
 830         { merge(std::move(__x), __comp); }
 831 #endif
 832
 833       void
 834       sort() { _Base::sort(); }
 835
 836       template<typename _StrictWeakOrdering>
 837         void
 838         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
 839
 840       using _Base::reverse;
 841
 842       _Base&
 843       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 844
 845       const _Base&
 846       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 847     };
 848
 849 #if __cpp_deduction_guides >= 201606
 850   template<typename _InputIterator, typename _ValT
 851              = typename iterator_traits<_InputIterator>::value_type,
 852            typename _Allocator = allocator<_ValT>,
 853            typename = _RequireInputIter<_InputIterator>,
 854            typename = _RequireAllocator<_Allocator>>
 855     list(_InputIterator, _InputIterator, _Allocator = _Allocator())
 856       -> list<_ValT, _Allocator>;
 857 #endif
 858
 859   template<typename _Tp, typename _Alloc>
 860     inline bool
 861     operator==(const list<_Tp, _Alloc>& __lhs,
 862                const list<_Tp, _Alloc>& __rhs)
 863     { return __lhs._M_base() == __rhs._M_base(); }
 864
 865   template<typename _Tp, typename _Alloc>
 866     inline bool
 867     operator!=(const list<_Tp, _Alloc>& __lhs,
 868                const list<_Tp, _Alloc>& __rhs)
 869     { return __lhs._M_base() != __rhs._M_base(); }
 870
 871   template<typename _Tp, typename _Alloc>
 872     inline bool
 873     operator<(const list<_Tp, _Alloc>& __lhs,
 874               const list<_Tp, _Alloc>& __rhs)
 875     { return __lhs._M_base() < __rhs._M_base(); }
 876
 877   template<typename _Tp, typename _Alloc>
 878     inline bool
 879     operator<=(const list<_Tp, _Alloc>& __lhs,
 880                const list<_Tp, _Alloc>& __rhs)
 881     { return __lhs._M_base() <= __rhs._M_base(); }
 882
 883   template<typename _Tp, typename _Alloc>
 884     inline bool
 885     operator>=(const list<_Tp, _Alloc>& __lhs,
 886                const list<_Tp, _Alloc>& __rhs)
 887     { return __lhs._M_base() >= __rhs._M_base(); }
 888
 889   template<typename _Tp, typename _Alloc>
 890     inline bool
 891     operator>(const list<_Tp, _Alloc>& __lhs,
 892               const list<_Tp, _Alloc>& __rhs)
 893     { return __lhs._M_base() > __rhs._M_base(); }
 894
 895   template<typename _Tp, typename _Alloc>
 896     inline void
 897     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
 898     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
 899     { __lhs.swap(__rhs); }
 900
 901 } // namespace __debug
 902 } // namespace std
 903
 904 namespace __gnu_debug
 905 {
 906 #ifndef _GLIBCXX_USE_CXX11_ABI
 907   // If not using C++11 list::size() is not in O(1) so we do not use it.
 908   template<typename _Tp, typename _Alloc>
 909     struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
 910     {
 911       typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It;
 912
 913       static typename _Distance_traits<_It>::__type
 914       _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
 915       {
 916         return __seq.empty()
 917           ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality);
 918       }
 919     };
 920 #endif
 921
 922 #ifndef _GLIBCXX_DEBUG_PEDANTIC
 923   template<class _Tp, class _Alloc>
 924     struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
 925     { enum { __value = 1 }; };
 926 #endif
 927 }
 928
 929 #endif