libstdc++-v3/include/debug/forward_list

   1 // <forward_list> -*- C++ -*-
   2
   3 // Copyright (C) 2010-2014 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/forward_list
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_FORWARD_LIST
  30 #define _GLIBCXX_DEBUG_FORWARD_LIST 1
  31
  32 #pragma GCC system_header
  33
  34 #include <forward_list>
  35 #include <debug/safe_sequence.h>
  36 #include <debug/safe_container.h>
  37 #include <debug/safe_iterator.h>
  38
  39 namespace __gnu_debug
  40 {
  41   /// Special iterators swap and invalidation for forward_list because of the
  42   /// before_begin iterator.
  43   template<typename _SafeSequence>
  44     class _Safe_forward_list
  45     : public _Safe_sequence<_SafeSequence>
  46     {
  47       _SafeSequence&
  48       _M_this() noexcept
  49       { return *static_cast<_SafeSequence*>(this); }
  50
  51       static void
  52       _M_swap_aux(_Safe_sequence_base& __lhs,
  53                   _Safe_iterator_base*& __lhs_iterators,
  54                   _Safe_sequence_base& __rhs,
  55                   _Safe_iterator_base*& __rhs_iterators);
  56
  57       void _M_swap_single(_Safe_sequence_base&) noexcept;
  58
  59     protected:
  60       void
  61       _M_invalidate_all()
  62       {
  63         using _Base_const_iterator = __decltype(_M_this()._M_base().cend());
  64         this->_M_invalidate_if([this](_Base_const_iterator __it)
  65         {
  66           return __it != _M_this()._M_base().cbefore_begin()
  67             && __it != _M_this()._M_base().cend(); });
  68       }
  69
  70       void _M_swap(_Safe_sequence_base&) noexcept;
  71     };
  72
  73    template<typename _SafeSequence>
  74     void
  75     _Safe_forward_list<_SafeSequence>::
  76     _M_swap_aux(_Safe_sequence_base& __lhs,
  77                 _Safe_iterator_base*& __lhs_iterators,
  78                 _Safe_sequence_base& __rhs,
  79                 _Safe_iterator_base*& __rhs_iterators)
  80     {
  81       using const_iterator = typename _SafeSequence::const_iterator;
  82       _Safe_iterator_base* __bbegin_its = 0;
  83       _Safe_iterator_base* __last_bbegin = 0;
  84       _SafeSequence& __rseq = static_cast<_SafeSequence&>(__rhs);
  85
  86       for (_Safe_iterator_base* __iter = __lhs_iterators; __iter;)
  87         {
  88           // Even iterator is cast to const_iterator, not a problem.
  89           const_iterator* __victim = static_cast<const_iterator*>(__iter);
  90           __iter = __iter->_M_next;
  91           if (__victim->base() == __rseq._M_base().cbefore_begin())
  92             {
  93               __victim->_M_unlink();
  94               if (__lhs_iterators == __victim)
  95                 __lhs_iterators = __victim->_M_next;
  96               if (__bbegin_its)
  97                 {
  98                   __victim->_M_next = __bbegin_its;
  99                   __bbegin_its->_M_prior = __victim;
 100                 }
 101               else
 102                 __last_bbegin = __victim;
 103               __bbegin_its = __victim;
 104             }
 105           else
 106             __victim->_M_sequence = &__lhs;
 107         }
 108
 109       if (__bbegin_its)
 110         {
 111           if (__rhs_iterators)
 112             {
 113               __rhs_iterators->_M_prior = __last_bbegin;
 114               __last_bbegin->_M_next = __rhs_iterators;
 115             }
 116           __rhs_iterators = __bbegin_its;
 117         }
 118     }
 119
 120    template<typename _SafeSequence>
 121     void
 122     _Safe_forward_list<_SafeSequence>::
 123     _M_swap_single(_Safe_sequence_base& __other) noexcept
 124     {
 125       std::swap(_M_this()._M_iterators, __other._M_iterators);
 126       std::swap(_M_this()._M_const_iterators, __other._M_const_iterators);
 127       // Useless, always 1 on forward_list
 128       //std::swap(_M_this()_M_version, __other._M_version);
 129       _Safe_iterator_base* __this_its = _M_this()._M_iterators;
 130       _M_swap_aux(__other, __other._M_iterators,
 131                   _M_this(), _M_this()._M_iterators);
 132       _Safe_iterator_base* __this_const_its = _M_this()._M_const_iterators;
 133       _M_swap_aux(__other, __other._M_const_iterators,
 134                   _M_this(), _M_this()._M_const_iterators);
 135       _M_swap_aux(_M_this(), __this_its,
 136                   __other, __other._M_iterators);
 137       _M_swap_aux(_M_this(), __this_const_its,
 138                   __other, __other._M_const_iterators);
 139     }
 140
 141   /* Special forward_list _M_swap version that does not swap the
 142    * before-begin ownership.*/
 143    template<typename _SafeSequence>
 144     void
 145     _Safe_forward_list<_SafeSequence>::
 146     _M_swap(_Safe_sequence_base& __other) noexcept
 147     {
 148       // We need to lock both sequences to swap
 149       using namespace __gnu_cxx;
 150       __mutex *__this_mutex = &_M_this()._M_get_mutex();
 151       __mutex *__other_mutex =
 152         &static_cast<_SafeSequence&>(__other)._M_get_mutex();
 153       if (__this_mutex == __other_mutex)
 154         {
 155           __scoped_lock __lock(*__this_mutex);
 156           _M_swap_single(__other);
 157         }
 158       else
 159         {
 160           __scoped_lock __l1(__this_mutex < __other_mutex
 161                              ? *__this_mutex : *__other_mutex);
 162           __scoped_lock __l2(__this_mutex < __other_mutex
 163                              ? *__other_mutex : *__this_mutex);
 164           _M_swap_single(__other);
 165         }
 166     }
 167 }
 168
 169 namespace std _GLIBCXX_VISIBILITY(default)
 170 {
 171 namespace __debug
 172 {
 173   /// Class std::forward_list with safety/checking/debug instrumentation.
 174   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
 175     class forward_list
 176     : public __gnu_debug::_Safe_container<
 177         forward_list<_Tp, _Alloc>, _Alloc, __gnu_debug::_Safe_forward_list>,
 178       public _GLIBCXX_STD_C::forward_list<_Tp, _Alloc>
 179     {
 180       typedef _GLIBCXX_STD_C::forward_list<_Tp, _Alloc>         _Base;
 181       typedef __gnu_debug::_Safe_container<
 182         forward_list, _Alloc, __gnu_debug::_Safe_forward_list>  _Safe;
 183
 184       typedef typename _Base::iterator          _Base_iterator;
 185       typedef typename _Base::const_iterator    _Base_const_iterator;
 186
 187     public:
 188       typedef typename _Base::reference         reference;
 189       typedef typename _Base::const_reference   const_reference;
 190
 191       typedef __gnu_debug::_Safe_iterator<
 192         _Base_iterator, forward_list>           iterator;
 193       typedef __gnu_debug::_Safe_iterator<
 194         _Base_const_iterator, forward_list>     const_iterator;
 195
 196       typedef typename _Base::size_type         size_type;
 197       typedef typename _Base::difference_type   difference_type;
 198
 199       typedef _Tp                               value_type;
 200       typedef typename _Base::allocator_type    allocator_type;
 201       typedef typename _Base::pointer           pointer;
 202       typedef typename _Base::const_pointer     const_pointer;
 203
 204       // 23.2.3.1 construct/copy/destroy:
 205       explicit
 206       forward_list(const allocator_type& __al = allocator_type())
 207       : _Base(__al) { }
 208
 209       forward_list(const forward_list& __list, const allocator_type& __al)
 210       : _Base(__list, __al)
 211       { }
 212
 213       forward_list(forward_list&& __list, const allocator_type& __al)
 214         : _Safe(std::move(__list._M_safe()), __al),
 215           _Base(std::move(__list._M_base()), __al)
 216       { }
 217
 218       explicit
 219       forward_list(size_type __n, const allocator_type& __al = allocator_type())
 220       : _Base(__n, __al)
 221       { }
 222
 223       forward_list(size_type __n, const _Tp& __value,
 224                    const allocator_type& __al = allocator_type())
 225       : _Base(__n, __value, __al)
 226       { }
 227
 228       template<typename _InputIterator,
 229                typename = std::_RequireInputIter<_InputIterator>>
 230         forward_list(_InputIterator __first, _InputIterator __last,
 231                      const allocator_type& __al = allocator_type())
 232         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 233                                                                      __last)),
 234                 __gnu_debug::__base(__last), __al)
 235         { }
 236
 237       forward_list(const forward_list&) = default;
 238
 239       forward_list(forward_list&&) = default;
 240
 241       forward_list(std::initializer_list<_Tp> __il,
 242                    const allocator_type& __al = allocator_type())
 243       : _Base(__il, __al)
 244       { }
 245
 246       ~forward_list() = default;
 247
 248       forward_list&
 249       operator=(const forward_list&) = default;
 250
 251       forward_list&
 252       operator=(forward_list&&) = default;
 253
 254       forward_list&
 255       operator=(std::initializer_list<_Tp> __il)
 256       {
 257         _M_base() = __il;
 258         this->_M_invalidate_all();
 259         return *this;
 260       }
 261
 262       template<typename _InputIterator,
 263                typename = std::_RequireInputIter<_InputIterator>>
 264         void
 265         assign(_InputIterator __first, _InputIterator __last)
 266         {
 267           __glibcxx_check_valid_range(__first, __last);
 268           _Base::assign(__gnu_debug::__base(__first),
 269                         __gnu_debug::__base(__last));
 270           this->_M_invalidate_all();
 271         }
 272
 273       void
 274       assign(size_type __n, const _Tp& __val)
 275       {
 276         _Base::assign(__n, __val);
 277         this->_M_invalidate_all();
 278       }
 279
 280       void
 281       assign(std::initializer_list<_Tp> __il)
 282       {
 283         _Base::assign(__il);
 284         this->_M_invalidate_all();
 285       }
 286
 287       using _Base::get_allocator;
 288
 289       // iterators:
 290
 291       iterator
 292       before_begin() noexcept
 293       { return iterator(_Base::before_begin(), this); }
 294
 295       const_iterator
 296       before_begin() const noexcept
 297       { return const_iterator(_Base::before_begin(), this); }
 298
 299       iterator
 300       begin() noexcept
 301       { return iterator(_Base::begin(), this); }
 302
 303       const_iterator
 304       begin() const noexcept
 305       { return const_iterator(_Base::begin(), this); }
 306
 307       iterator
 308       end() noexcept
 309       { return iterator(_Base::end(), this); }
 310
 311       const_iterator
 312       end() const noexcept
 313       { return const_iterator(_Base::end(), this); }
 314
 315       const_iterator
 316       cbegin() const noexcept
 317       { return const_iterator(_Base::cbegin(), this); }
 318
 319       const_iterator
 320       cbefore_begin() const noexcept
 321       { return const_iterator(_Base::cbefore_begin(), this); }
 322
 323       const_iterator
 324       cend() const noexcept
 325       { return const_iterator(_Base::cend(), this); }
 326
 327       using _Base::empty;
 328       using _Base::max_size;
 329
 330       // element access:
 331
 332       reference
 333       front()
 334       {
 335         __glibcxx_check_nonempty();
 336         return _Base::front();
 337       }
 338
 339       const_reference
 340       front() const
 341       {
 342         __glibcxx_check_nonempty();
 343         return _Base::front();
 344       }
 345
 346       // modiﬁers:
 347
 348       using _Base::emplace_front;
 349       using _Base::push_front;
 350
 351       void
 352       pop_front()
 353       {
 354         __glibcxx_check_nonempty();
 355         this->_M_invalidate_if([this](_Base_const_iterator __it)
 356           { return __it == this->_M_base().cbegin(); });
 357         _Base::pop_front();
 358       }
 359
 360       template<typename... _Args>
 361         iterator
 362         emplace_after(const_iterator __pos, _Args&&... __args)
 363         {
 364           __glibcxx_check_insert_after(__pos);
 365           return iterator(_Base::emplace_after(__pos.base(),
 366                                         std::forward<_Args>(__args)...),
 367                           this);
 368         }
 369
 370       iterator
 371       insert_after(const_iterator __pos, const _Tp& __val)
 372       {
 373         __glibcxx_check_insert_after(__pos);
 374         return iterator(_Base::insert_after(__pos.base(), __val), this);
 375       }
 376
 377       iterator
 378       insert_after(const_iterator __pos, _Tp&& __val)
 379       {
 380         __glibcxx_check_insert_after(__pos);
 381         return iterator(_Base::insert_after(__pos.base(), std::move(__val)),
 382                         this);
 383       }
 384
 385       iterator
 386       insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
 387       {
 388         __glibcxx_check_insert_after(__pos);
 389         return iterator(_Base::insert_after(__pos.base(), __n, __val),
 390                         this);
 391       }
 392
 393       template<typename _InputIterator,
 394                typename = std::_RequireInputIter<_InputIterator>>
 395         iterator
 396         insert_after(const_iterator __pos,
 397                      _InputIterator __first, _InputIterator __last)
 398         {
 399           __glibcxx_check_insert_range_after(__pos, __first, __last);
 400           return iterator(_Base::insert_after(__pos.base(),
 401                                               __gnu_debug::__base(__first),
 402                                               __gnu_debug::__base(__last)),
 403                           this);
 404         }
 405
 406       iterator
 407       insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
 408       {
 409         __glibcxx_check_insert_after(__pos);
 410         return iterator(_Base::insert_after(__pos.base(), __il), this);
 411       }
 412
 413     private:
 414       _Base_iterator
 415       _M_erase_after(_Base_const_iterator __pos)
 416       {
 417         _Base_const_iterator __next = std::next(__pos);
 418         this->_M_invalidate_if([__next](_Base_const_iterator __it)
 419           { return __it == __next; });
 420         return _Base::erase_after(__pos);
 421       }
 422     public:
 423       iterator
 424       erase_after(const_iterator __pos)
 425       {
 426         __glibcxx_check_erase_after(__pos);
 427         return iterator(_M_erase_after(__pos.base()), this);
 428       }
 429
 430       iterator
 431       erase_after(const_iterator __pos, const_iterator __last)
 432       {
 433         __glibcxx_check_erase_range_after(__pos, __last);
 434         for (_Base_const_iterator __victim = std::next(__pos.base());
 435             __victim != __last.base(); ++__victim)
 436           {
 437             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 438                                   _M_message(__gnu_debug::__msg_valid_range2)
 439                                   ._M_sequence(*this, "this")
 440                                   ._M_iterator(__pos, "pos")
 441                                   ._M_iterator(__last, "last"));
 442             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 443               { return __it == __victim; });
 444           }
 445         return iterator(_Base::erase_after(__pos.base(), __last.base()), this);
 446       }
 447
 448       void
 449       swap(forward_list& __list)
 450         noexcept( noexcept(declval<_Base>().swap(__list)) )
 451       {
 452         _Safe::_M_swap(__list);
 453         _Base::swap(__list);
 454       }
 455
 456       void
 457       resize(size_type __sz)
 458       {
 459         this->_M_detach_singular();
 460
 461         // if __sz < size(), invalidate all iterators in [begin+__sz, end()
 462         _Base_iterator __victim = _Base::begin();
 463         _Base_iterator __end = _Base::end();
 464         for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 465           ++__victim;
 466
 467         for (; __victim != __end; ++__victim)
 468           {
 469             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 470               { return __it == __victim; });
 471           }
 472
 473         __try
 474           {
 475             _Base::resize(__sz);
 476           }
 477         __catch(...)
 478           {
 479             this->_M_revalidate_singular();
 480             __throw_exception_again;
 481           }
 482       }
 483
 484       void
 485       resize(size_type __sz, const value_type& __val)
 486       {
 487         this->_M_detach_singular();
 488
 489         // if __sz < size(), invalidate all iterators in [begin+__sz, end())
 490         _Base_iterator __victim = _Base::begin();
 491         _Base_iterator __end = _Base::end();
 492         for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 493           ++__victim;
 494
 495         for (; __victim != __end; ++__victim)
 496           {
 497             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
 498               { return __it == __victim; });
 499           }
 500
 501         __try
 502           {
 503             _Base::resize(__sz, __val);
 504           }
 505         __catch(...)
 506           {
 507             this->_M_revalidate_singular();
 508             __throw_exception_again;
 509           }
 510       }
 511
 512       void
 513       clear() noexcept
 514       {
 515         _Base::clear();
 516         this->_M_invalidate_all();
 517       }
 518
 519       // 23.2.3.5 forward_list operations:
 520       void
 521       splice_after(const_iterator __pos, forward_list&& __list)
 522       {
 523         __glibcxx_check_insert_after(__pos);
 524         _GLIBCXX_DEBUG_VERIFY(&__list != this,
 525                               _M_message(__gnu_debug::__msg_self_splice)
 526                               ._M_sequence(*this, "this"));
 527         _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
 528                               _M_message(__gnu_debug::__msg_splice_alloc)
 529                               ._M_sequence(*this)
 530                               ._M_sequence(__list, "__list"));
 531         this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it)
 532           {
 533             return __it != __list._M_base().cbefore_begin()
 534                    && __it != __list._M_base().end();
 535           });
 536         _Base::splice_after(__pos.base(), std::move(__list._M_base()));
 537       }
 538
 539       void
 540       splice_after(const_iterator __pos, forward_list& __list)
 541       { splice_after(__pos, std::move(__list)); }
 542
 543       void
 544       splice_after(const_iterator __pos, forward_list&& __list,
 545                    const_iterator __i)
 546       {
 547         __glibcxx_check_insert_after(__pos);
 548         _GLIBCXX_DEBUG_VERIFY(__i._M_before_dereferenceable(),
 549                               _M_message(__gnu_debug::__msg_splice_bad)
 550                               ._M_iterator(__i, "__i"));
 551         _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__list),
 552                               _M_message(__gnu_debug::__msg_splice_other)
 553                               ._M_iterator(__i, "__i")
 554                               ._M_sequence(__list, "__list"));
 555         _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
 556                               _M_message(__gnu_debug::__msg_splice_alloc)
 557                               ._M_sequence(*this)
 558                               ._M_sequence(__list, "__list"));
 559
 560         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 561         // 250. splicing invalidates iterators
 562         _Base_const_iterator __next = std::next(__i.base());
 563         this->_M_transfer_from_if(__list, [__next](_Base_const_iterator __it)
 564           { return __it == __next; });
 565         _Base::splice_after(__pos.base(), std::move(__list._M_base()),
 566                             __i.base());
 567       }
 568
 569       void
 570       splice_after(const_iterator __pos, forward_list& __list,
 571                    const_iterator __i)
 572       { splice_after(__pos, std::move(__list), __i); }
 573
 574       void
 575       splice_after(const_iterator __pos, forward_list&& __list,
 576                    const_iterator __before, const_iterator __last)
 577       {
 578         __glibcxx_check_insert_after(__pos);
 579         __glibcxx_check_valid_range(__before, __last);
 580         _GLIBCXX_DEBUG_VERIFY(__before._M_attached_to(&__list),
 581                               _M_message(__gnu_debug::__msg_splice_other)
 582                               ._M_sequence(__list, "list")
 583                               ._M_iterator(__before, "before"));
 584         _GLIBCXX_DEBUG_VERIFY(__before._M_dereferenceable()
 585                               || __before._M_is_before_begin(),
 586                               _M_message(__gnu_debug::__msg_valid_range2)
 587                               ._M_sequence(__list, "list")
 588                               ._M_iterator(__before, "before")
 589                               ._M_iterator(__last, "last"));
 590         _GLIBCXX_DEBUG_VERIFY(__before != __last,
 591                               _M_message(__gnu_debug::__msg_valid_range2)
 592                               ._M_sequence(__list, "list")
 593                               ._M_iterator(__before, "before")
 594                               ._M_iterator(__last, "last"));
 595         _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
 596                               _M_message(__gnu_debug::__msg_splice_alloc)
 597                               ._M_sequence(*this)
 598                               ._M_sequence(__list, "__list"));
 599
 600         for (_Base_const_iterator __tmp = std::next(__before.base());
 601              __tmp != __last.base(); ++__tmp)
 602           {
 603             _GLIBCXX_DEBUG_VERIFY(__tmp != __list._M_base().end(),
 604                                   _M_message(__gnu_debug::__msg_valid_range2)
 605                                   ._M_sequence(__list, "list")
 606                                   ._M_iterator(__before, "before")
 607                                   ._M_iterator(__last, "last"));
 608             _GLIBCXX_DEBUG_VERIFY(&__list != this || __tmp != __pos.base(),
 609                                   _M_message(__gnu_debug::__msg_splice_overlap)
 610                                   ._M_iterator(__tmp, "position")
 611                                   ._M_iterator(__before, "before")
 612                                   ._M_iterator(__last, "last"));
 613             // _GLIBCXX_RESOLVE_LIB_DEFECTS
 614             // 250. splicing invalidates iterators
 615             this->_M_transfer_from_if(__list, [__tmp](_Base_const_iterator __it)
 616               { return __it == __tmp; });
 617           }
 618
 619         _Base::splice_after(__pos.base(), std::move(__list._M_base()),
 620                             __before.base(), __last.base());
 621       }
 622
 623       void
 624       splice_after(const_iterator __pos, forward_list& __list,
 625                    const_iterator __before, const_iterator __last)
 626       { splice_after(__pos, std::move(__list), __before, __last); }
 627
 628       void
 629       remove(const _Tp& __val)
 630       {
 631         _Base_iterator __x = _Base::before_begin();
 632         _Base_iterator __old = __x++;
 633         while (__x != _Base::end())
 634           {
 635             if (*__x == __val)
 636               __x = _M_erase_after(__old);
 637             else
 638               __old = __x++;
 639           }
 640       }
 641
 642       template<typename _Pred>
 643         void
 644         remove_if(_Pred __pred)
 645         {
 646           _Base_iterator __x = _Base::before_begin();
 647           _Base_iterator __old = __x++;
 648           while (__x != _Base::end())
 649             {
 650               if (__pred(*__x))
 651                 __x = _M_erase_after(__old);
 652               else
 653                 __old = __x++;
 654             }
 655         }
 656
 657       void
 658       unique()
 659       {
 660         _Base_iterator __first = _Base::begin();
 661         _Base_iterator __last = _Base::end();
 662         if (__first == __last)
 663           return;
 664         _Base_iterator __next = std::next(__first);
 665         while (__next != __last)
 666           {
 667             if (*__first == *__next)
 668               __next = _M_erase_after(__first);
 669             else
 670               __first = __next++;
 671           }
 672       }
 673
 674       template<typename _BinPred>
 675         void
 676         unique(_BinPred __binary_pred)
 677         {
 678           _Base_iterator __first = _Base::begin();
 679           _Base_iterator __last = _Base::end();
 680           if (__first == __last)
 681             return;
 682           _Base_iterator __next = std::next(__first);
 683           while (__next != __last)
 684             {
 685               if (__binary_pred(*__first, *__next))
 686                 __next = _M_erase_after(__first);
 687               else
 688                 __first = __next++;
 689             }
 690         }
 691
 692       void
 693       merge(forward_list&& __list)
 694       {
 695         if (this != &__list)
 696         {
 697           __glibcxx_check_sorted(_Base::begin(), _Base::end());
 698           __glibcxx_check_sorted(__list._M_base().begin(),
 699                                  __list._M_base().end());
 700           this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it)
 701             {
 702               return __it != __list._M_base().cbefore_begin()
 703                      && __it != __list._M_base().cend();
 704             });
 705           _Base::merge(std::move(__list._M_base()));
 706         }
 707       }
 708
 709       void
 710       merge(forward_list& __list)
 711       { merge(std::move(__list)); }
 712
 713       template<typename _Comp>
 714         void
 715         merge(forward_list&& __list, _Comp __comp)
 716         {
 717           if (this != &__list)
 718           {
 719             __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
 720             __glibcxx_check_sorted_pred(__list._M_base().begin(),
 721                                         __list._M_base().end(), __comp);
 722             this->_M_transfer_from_if(__list,
 723                                       [&__list](_Base_const_iterator __it)
 724               {
 725                 return __it != __list._M_base().cbefore_begin()
 726                        && __it != __list._M_base().cend();
 727               });
 728             _Base::merge(std::move(__list._M_base()), __comp);
 729           }
 730         }
 731
 732       template<typename _Comp>
 733         void
 734         merge(forward_list& __list, _Comp __comp)
 735         { merge(std::move(__list), __comp); }
 736
 737       using _Base::sort;
 738       using _Base::reverse;
 739
 740       _Base&
 741       _M_base() noexcept { return *this; }
 742
 743       const _Base&
 744       _M_base() const noexcept { return *this; }
 745     };
 746
 747   template<typename _Tp, typename _Alloc>
 748     bool
 749     operator==(const forward_list<_Tp, _Alloc>& __lx,
 750                const forward_list<_Tp, _Alloc>& __ly)
 751     { return __lx._M_base() == __ly._M_base(); }
 752
 753   template<typename _Tp, typename _Alloc>
 754     inline bool
 755     operator<(const forward_list<_Tp, _Alloc>& __lx,
 756               const forward_list<_Tp, _Alloc>& __ly)
 757     { return __lx._M_base() < __ly._M_base(); }
 758
 759   template<typename _Tp, typename _Alloc>
 760     inline bool
 761     operator!=(const forward_list<_Tp, _Alloc>& __lx,
 762                const forward_list<_Tp, _Alloc>& __ly)
 763     { return !(__lx == __ly); }
 764
 765   /// Based on operator<
 766   template<typename _Tp, typename _Alloc>
 767     inline bool
 768     operator>(const forward_list<_Tp, _Alloc>& __lx,
 769               const forward_list<_Tp, _Alloc>& __ly)
 770     { return (__ly < __lx); }
 771
 772   /// Based on operator<
 773   template<typename _Tp, typename _Alloc>
 774     inline bool
 775     operator>=(const forward_list<_Tp, _Alloc>& __lx,
 776                const forward_list<_Tp, _Alloc>& __ly)
 777     { return !(__lx < __ly); }
 778
 779   /// Based on operator<
 780   template<typename _Tp, typename _Alloc>
 781     inline bool
 782     operator<=(const forward_list<_Tp, _Alloc>& __lx,
 783                const forward_list<_Tp, _Alloc>& __ly)
 784     { return !(__ly < __lx); }
 785
 786   /// See std::forward_list::swap().
 787   template<typename _Tp, typename _Alloc>
 788     inline void
 789     swap(forward_list<_Tp, _Alloc>& __lx,
 790          forward_list<_Tp, _Alloc>& __ly)
 791     { __lx.swap(__ly); }
 792
 793 } // namespace __debug
 794 } // namespace std
 795
 796 namespace __gnu_debug
 797 {
 798   template<class _Tp, class _Alloc>
 799     struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> >
 800     {
 801       typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence;
 802
 803       template<typename _Iterator>
 804         static bool
 805         _S_Is(const _Safe_iterator<_Iterator, _Sequence>& __it)
 806         {
 807           return
 808             __it.base() == __it._M_get_sequence()->_M_base().before_begin();
 809         }
 810
 811       template<typename _Iterator>
 812         static bool
 813         _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it)
 814         { return _S_Is(__it); }
 815     };
 816
 817 #ifndef _GLIBCXX_DEBUG_PEDANTIC
 818   template<class _Tp, class _Alloc>
 819     struct _Insert_range_from_self_is_safe<
 820       std::__debug::forward_list<_Tp, _Alloc> >
 821     { enum { __value = 1 }; };
 822 #endif
 823 }
 824
 825 #endif