contrib/libc++/include/forward_list

   1 // -*- C++ -*-
   2 //===----------------------- forward_list ---------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_FORWARD_LIST
  11 #define _LIBCPP_FORWARD_LIST
  12
  13 /*
  14     forward_list synopsis
  15
  16 namespace std
  17 {
  18
  19 template <class T, class Allocator = allocator<T>>
  20 class forward_list
  21 {
  22 public:
  23     typedef T         value_type;
  24     typedef Allocator allocator_type;
  25
  26     typedef value_type&                                                reference;
  27     typedef const value_type&                                          const_reference;
  28     typedef typename allocator_traits<allocator_type>::pointer         pointer;
  29     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
  30     typedef typename allocator_traits<allocator_type>::size_type       size_type;
  31     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  32
  33     typedef <details> iterator;
  34     typedef <details> const_iterator;
  35
  36     forward_list()
  37         noexcept(is_nothrow_default_constructible<allocator_type>::value);
  38     explicit forward_list(const allocator_type& a);
  39     explicit forward_list(size_type n);
  40     explicit forward_list(size_type n, const allocator_type& a); // C++14
  41     forward_list(size_type n, const value_type& v);
  42     forward_list(size_type n, const value_type& v, const allocator_type& a);
  43     template <class InputIterator>
  44         forward_list(InputIterator first, InputIterator last);
  45     template <class InputIterator>
  46         forward_list(InputIterator first, InputIterator last, const allocator_type& a);
  47     forward_list(const forward_list& x);
  48     forward_list(const forward_list& x, const allocator_type& a);
  49     forward_list(forward_list&& x)
  50         noexcept(is_nothrow_move_constructible<allocator_type>::value);
  51     forward_list(forward_list&& x, const allocator_type& a);
  52     forward_list(initializer_list<value_type> il);
  53     forward_list(initializer_list<value_type> il, const allocator_type& a);
  54
  55     ~forward_list();
  56
  57     forward_list& operator=(const forward_list& x);
  58     forward_list& operator=(forward_list&& x)
  59         noexcept(
  60              allocator_type::propagate_on_container_move_assignment::value &&
  61              is_nothrow_move_assignable<allocator_type>::value);
  62     forward_list& operator=(initializer_list<value_type> il);
  63
  64     template <class InputIterator>
  65         void assign(InputIterator first, InputIterator last);
  66     void assign(size_type n, const value_type& v);
  67     void assign(initializer_list<value_type> il);
  68
  69     allocator_type get_allocator() const noexcept;
  70
  71     iterator       begin() noexcept;
  72     const_iterator begin() const noexcept;
  73     iterator       end() noexcept;
  74     const_iterator end() const noexcept;
  75
  76     const_iterator cbegin() const noexcept;
  77     const_iterator cend() const noexcept;
  78
  79     iterator       before_begin() noexcept;
  80     const_iterator before_begin() const noexcept;
  81     const_iterator cbefore_begin() const noexcept;
  82
  83     bool empty() const noexcept;
  84     size_type max_size() const noexcept;
  85
  86     reference       front();
  87     const_reference front() const;
  88
  89     template <class... Args> reference emplace_front(Args&&... args);  // reference in C++17
  90     void push_front(const value_type& v);
  91     void push_front(value_type&& v);
  92
  93     void pop_front();
  94
  95     template <class... Args>
  96         iterator emplace_after(const_iterator p, Args&&... args);
  97     iterator insert_after(const_iterator p, const value_type& v);
  98     iterator insert_after(const_iterator p, value_type&& v);
  99     iterator insert_after(const_iterator p, size_type n, const value_type& v);
 100     template <class InputIterator>
 101         iterator insert_after(const_iterator p,
 102                               InputIterator first, InputIterator last);
 103     iterator insert_after(const_iterator p, initializer_list<value_type> il);
 104
 105     iterator erase_after(const_iterator p);
 106     iterator erase_after(const_iterator first, const_iterator last);
 107
 108     void swap(forward_list& x)
 109         noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
 110
 111     void resize(size_type n);
 112     void resize(size_type n, const value_type& v);
 113     void clear() noexcept;
 114
 115     void splice_after(const_iterator p, forward_list& x);
 116     void splice_after(const_iterator p, forward_list&& x);
 117     void splice_after(const_iterator p, forward_list& x, const_iterator i);
 118     void splice_after(const_iterator p, forward_list&& x, const_iterator i);
 119     void splice_after(const_iterator p, forward_list& x,
 120                       const_iterator first, const_iterator last);
 121     void splice_after(const_iterator p, forward_list&& x,
 122                       const_iterator first, const_iterator last);
 123     size_type remove(const value_type& v);           // void before C++20
 124     template <class Predicate>
 125       size_type remove_if(Predicate pred);           // void before C++20
 126     size_type unique();                              // void before C++20
 127     template <class BinaryPredicate>
 128       size_type unique(BinaryPredicate binary_pred); // void before C++20
 129     void merge(forward_list& x);
 130     void merge(forward_list&& x);
 131     template <class Compare> void merge(forward_list& x, Compare comp);
 132     template <class Compare> void merge(forward_list&& x, Compare comp);
 133     void sort();
 134     template <class Compare> void sort(Compare comp);
 135     void reverse() noexcept;
 136 };
 137
 138
 139 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 140     forward_list(InputIterator, InputIterator, Allocator = Allocator())
 141     -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;  // C++17
 142
 143 template <class T, class Allocator>
 144     bool operator==(const forward_list<T, Allocator>& x,
 145                     const forward_list<T, Allocator>& y);
 146
 147 template <class T, class Allocator>
 148     bool operator< (const forward_list<T, Allocator>& x,
 149                     const forward_list<T, Allocator>& y);
 150
 151 template <class T, class Allocator>
 152     bool operator!=(const forward_list<T, Allocator>& x,
 153                     const forward_list<T, Allocator>& y);
 154
 155 template <class T, class Allocator>
 156     bool operator> (const forward_list<T, Allocator>& x,
 157                     const forward_list<T, Allocator>& y);
 158
 159 template <class T, class Allocator>
 160     bool operator>=(const forward_list<T, Allocator>& x,
 161                     const forward_list<T, Allocator>& y);
 162
 163 template <class T, class Allocator>
 164     bool operator<=(const forward_list<T, Allocator>& x,
 165                     const forward_list<T, Allocator>& y);
 166
 167 template <class T, class Allocator>
 168     void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
 169          noexcept(noexcept(x.swap(y)));
 170
 171 template <class T, class Allocator, class U>
 172     void erase(forward_list<T, Allocator>& c, const U& value);       // C++20
 173 template <class T, class Allocator, class Predicate>
 174     void erase_if(forward_list<T, Allocator>& c, Predicate pred);    // C++20
 175
 176 }  // std
 177
 178 */
 179
 180 #include <__config>
 181 #include <initializer_list>
 182 #include <memory>
 183 #include <limits>
 184 #include <iterator>
 185 #include <algorithm>
 186 #include <version>
 187
 188 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 189 #pragma GCC system_header
 190 #endif
 191
 192 _LIBCPP_PUSH_MACROS
 193 #include <__undef_macros>
 194
 195
 196 _LIBCPP_BEGIN_NAMESPACE_STD
 197
 198 template <class _Tp, class _VoidPtr> struct __forward_list_node;
 199 template <class _NodePtr> struct __forward_begin_node;
 200
 201
 202 template <class>
 203 struct __forward_list_node_value_type;
 204
 205 template <class _Tp, class _VoidPtr>
 206 struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
 207   typedef _Tp type;
 208 };
 209
 210 template <class _NodePtr>
 211 struct __forward_node_traits {
 212
 213   typedef typename remove_cv<
 214         typename pointer_traits<_NodePtr>::element_type>::type  __node;
 215   typedef typename __forward_list_node_value_type<__node>::type __node_value_type;
 216   typedef _NodePtr                                              __node_pointer;
 217   typedef __forward_begin_node<_NodePtr>                        __begin_node;
 218   typedef typename __rebind_pointer<_NodePtr, __begin_node>::type
 219                                                                 __begin_node_pointer;
 220   typedef typename __rebind_pointer<_NodePtr, void>::type       __void_pointer;
 221
 222 #if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
 223   typedef __begin_node_pointer __iter_node_pointer;
 224 #else
 225   typedef typename conditional<
 226           is_pointer<__void_pointer>::value,
 227           __begin_node_pointer,
 228           __node_pointer
 229     >::type __iter_node_pointer;
 230 #endif
 231
 232   typedef typename conditional<
 233           is_same<__iter_node_pointer, __node_pointer>::value,
 234           __begin_node_pointer,
 235           __node_pointer
 236     >::type __non_iter_node_pointer;
 237
 238   _LIBCPP_INLINE_VISIBILITY
 239   static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) {
 240       return __p;
 241   }
 242   _LIBCPP_INLINE_VISIBILITY
 243   static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
 244       return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
 245   }
 246 };
 247
 248 template <class _NodePtr>
 249 struct __forward_begin_node
 250 {
 251     typedef _NodePtr pointer;
 252     typedef typename __rebind_pointer<_NodePtr, __forward_begin_node>::type __begin_node_pointer;
 253
 254     pointer __next_;
 255
 256     _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}
 257
 258     _LIBCPP_INLINE_VISIBILITY
 259     __begin_node_pointer __next_as_begin() const {
 260         return static_cast<__begin_node_pointer>(__next_);
 261     }
 262 };
 263
 264 template <class _Tp, class _VoidPtr>
 265 struct _LIBCPP_HIDDEN __begin_node_of
 266 {
 267     typedef __forward_begin_node<
 268         typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type
 269     > type;
 270 };
 271
 272 template <class _Tp, class _VoidPtr>
 273 struct __forward_list_node
 274     : public __begin_node_of<_Tp, _VoidPtr>::type
 275 {
 276     typedef _Tp value_type;
 277
 278     value_type __value_;
 279 };
 280
 281
 282 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list;
 283 template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
 284
 285 template <class _NodePtr>
 286 class _LIBCPP_TEMPLATE_VIS __forward_list_iterator
 287 {
 288     typedef __forward_node_traits<_NodePtr>         __traits;
 289     typedef typename __traits::__node_pointer       __node_pointer;
 290     typedef typename __traits::__begin_node_pointer __begin_node_pointer;
 291     typedef typename __traits::__iter_node_pointer  __iter_node_pointer;
 292     typedef typename __traits::__void_pointer       __void_pointer;
 293
 294     __iter_node_pointer __ptr_;
 295
 296     _LIBCPP_INLINE_VISIBILITY
 297     __begin_node_pointer __get_begin() const {
 298         return static_cast<__begin_node_pointer>(
 299                 static_cast<__void_pointer>(__ptr_));
 300     }
 301     _LIBCPP_INLINE_VISIBILITY
 302     __node_pointer __get_unsafe_node_pointer() const {
 303         return static_cast<__node_pointer>(
 304                 static_cast<__void_pointer>(__ptr_));
 305     }
 306
 307     _LIBCPP_INLINE_VISIBILITY
 308     explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
 309
 310     _LIBCPP_INLINE_VISIBILITY
 311     explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
 312         : __ptr_(__traits::__as_iter_node(__p)) {}
 313
 314     _LIBCPP_INLINE_VISIBILITY
 315     explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
 316         : __ptr_(__traits::__as_iter_node(__p)) {}
 317
 318     template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list;
 319     template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
 320
 321 public:
 322     typedef forward_iterator_tag                              iterator_category;
 323     typedef typename __traits::__node_value_type              value_type;
 324     typedef value_type&                                       reference;
 325     typedef typename pointer_traits<__node_pointer>::difference_type
 326                                                               difference_type;
 327     typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
 328
 329     _LIBCPP_INLINE_VISIBILITY
 330     __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
 331
 332     _LIBCPP_INLINE_VISIBILITY
 333     reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
 334     _LIBCPP_INLINE_VISIBILITY
 335     pointer operator->() const {
 336         return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_);
 337     }
 338
 339     _LIBCPP_INLINE_VISIBILITY
 340     __forward_list_iterator& operator++()
 341     {
 342         __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
 343         return *this;
 344     }
 345     _LIBCPP_INLINE_VISIBILITY
 346     __forward_list_iterator operator++(int)
 347     {
 348         __forward_list_iterator __t(*this);
 349         ++(*this);
 350         return __t;
 351     }
 352
 353     friend _LIBCPP_INLINE_VISIBILITY
 354     bool operator==(const __forward_list_iterator& __x,
 355                     const __forward_list_iterator& __y)
 356         {return __x.__ptr_ == __y.__ptr_;}
 357     friend _LIBCPP_INLINE_VISIBILITY
 358     bool operator!=(const __forward_list_iterator& __x,
 359                     const __forward_list_iterator& __y)
 360         {return !(__x == __y);}
 361 };
 362
 363 template <class _NodeConstPtr>
 364 class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator
 365 {
 366     static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), "");
 367     typedef _NodeConstPtr _NodePtr;
 368
 369     typedef __forward_node_traits<_NodePtr>         __traits;
 370     typedef typename __traits::__node               __node;
 371     typedef typename __traits::__node_pointer       __node_pointer;
 372     typedef typename __traits::__begin_node_pointer __begin_node_pointer;
 373     typedef typename __traits::__iter_node_pointer  __iter_node_pointer;
 374     typedef typename __traits::__void_pointer       __void_pointer;
 375
 376     __iter_node_pointer __ptr_;
 377
 378     __begin_node_pointer __get_begin() const {
 379         return static_cast<__begin_node_pointer>(
 380                 static_cast<__void_pointer>(__ptr_));
 381     }
 382     __node_pointer __get_unsafe_node_pointer() const {
 383         return static_cast<__node_pointer>(
 384                 static_cast<__void_pointer>(__ptr_));
 385     }
 386
 387     _LIBCPP_INLINE_VISIBILITY
 388     explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT
 389         : __ptr_(nullptr) {}
 390
 391     _LIBCPP_INLINE_VISIBILITY
 392     explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
 393         : __ptr_(__traits::__as_iter_node(__p)) {}
 394
 395     _LIBCPP_INLINE_VISIBILITY
 396     explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
 397         : __ptr_(__traits::__as_iter_node(__p)) {}
 398
 399
 400     template<class, class> friend class forward_list;
 401
 402 public:
 403     typedef forward_iterator_tag                              iterator_category;
 404     typedef typename __traits::__node_value_type              value_type;
 405     typedef const value_type&                                 reference;
 406     typedef typename pointer_traits<__node_pointer>::difference_type
 407                                                               difference_type;
 408     typedef typename __rebind_pointer<__node_pointer, const value_type>::type
 409                                                               pointer;
 410
 411     _LIBCPP_INLINE_VISIBILITY
 412     __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
 413     _LIBCPP_INLINE_VISIBILITY
 414     __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
 415         : __ptr_(__p.__ptr_) {}
 416
 417     _LIBCPP_INLINE_VISIBILITY
 418     reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
 419     _LIBCPP_INLINE_VISIBILITY
 420     pointer operator->() const {return pointer_traits<pointer>::pointer_to(
 421                 __get_unsafe_node_pointer()->__value_);}
 422
 423     _LIBCPP_INLINE_VISIBILITY
 424     __forward_list_const_iterator& operator++()
 425     {
 426         __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
 427         return *this;
 428     }
 429     _LIBCPP_INLINE_VISIBILITY
 430     __forward_list_const_iterator operator++(int)
 431     {
 432         __forward_list_const_iterator __t(*this);
 433         ++(*this);
 434         return __t;
 435     }
 436
 437     friend _LIBCPP_INLINE_VISIBILITY
 438     bool operator==(const __forward_list_const_iterator& __x,
 439                     const __forward_list_const_iterator& __y)
 440         {return __x.__ptr_ == __y.__ptr_;}
 441     friend _LIBCPP_INLINE_VISIBILITY
 442     bool operator!=(const __forward_list_const_iterator& __x,
 443                            const __forward_list_const_iterator& __y)
 444         {return !(__x == __y);}
 445 };
 446
 447 template <class _Tp, class _Alloc>
 448 class __forward_list_base
 449 {
 450 protected:
 451     typedef _Tp    value_type;
 452     typedef _Alloc allocator_type;
 453
 454     typedef typename allocator_traits<allocator_type>::void_pointer  void_pointer;
 455     typedef __forward_list_node<value_type, void_pointer>            __node;
 456     typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node;
 457     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __node>::type __node_allocator;
 458     typedef allocator_traits<__node_allocator>        __node_traits;
 459     typedef typename __node_traits::pointer           __node_pointer;
 460
 461     typedef typename __rebind_alloc_helper<
 462         allocator_traits<allocator_type>, __begin_node
 463     >::type                                           __begin_node_allocator;
 464     typedef typename allocator_traits<__begin_node_allocator>::pointer
 465                                                       __begin_node_pointer;
 466
 467     static_assert((!is_same<allocator_type, __node_allocator>::value),
 468                   "internal allocator type must differ from user-specified "
 469                   "type; otherwise overload resolution breaks");
 470
 471     __compressed_pair<__begin_node, __node_allocator> __before_begin_;
 472
 473     _LIBCPP_INLINE_VISIBILITY
 474     __begin_node_pointer        __before_begin() _NOEXCEPT
 475         {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());}
 476     _LIBCPP_INLINE_VISIBILITY
 477     __begin_node_pointer __before_begin() const _NOEXCEPT
 478         {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));}
 479
 480     _LIBCPP_INLINE_VISIBILITY
 481           __node_allocator& __alloc() _NOEXCEPT
 482             {return __before_begin_.second();}
 483     _LIBCPP_INLINE_VISIBILITY
 484     const __node_allocator& __alloc() const _NOEXCEPT
 485         {return __before_begin_.second();}
 486
 487     typedef __forward_list_iterator<__node_pointer>             iterator;
 488     typedef __forward_list_const_iterator<__node_pointer>       const_iterator;
 489
 490     _LIBCPP_INLINE_VISIBILITY
 491     __forward_list_base()
 492         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
 493         : __before_begin_(__begin_node()) {}
 494     _LIBCPP_INLINE_VISIBILITY
 495     explicit __forward_list_base(const allocator_type& __a)
 496         : __before_begin_(__begin_node(), __node_allocator(__a)) {}
 497     _LIBCPP_INLINE_VISIBILITY
 498     explicit __forward_list_base(const __node_allocator& __a)
 499         : __before_begin_(__begin_node(), __a) {}
 500 #ifndef _LIBCPP_CXX03_LANG
 501 public:
 502     _LIBCPP_INLINE_VISIBILITY
 503     __forward_list_base(__forward_list_base&& __x)
 504         _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
 505     _LIBCPP_INLINE_VISIBILITY
 506     __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
 507 #endif  // _LIBCPP_CXX03_LANG
 508
 509 private:
 510     __forward_list_base(const __forward_list_base&);
 511     __forward_list_base& operator=(const __forward_list_base&);
 512
 513 public:
 514     ~__forward_list_base();
 515
 516 protected:
 517     _LIBCPP_INLINE_VISIBILITY
 518     void __copy_assign_alloc(const __forward_list_base& __x)
 519         {__copy_assign_alloc(__x, integral_constant<bool,
 520               __node_traits::propagate_on_container_copy_assignment::value>());}
 521
 522     _LIBCPP_INLINE_VISIBILITY
 523     void __move_assign_alloc(__forward_list_base& __x)
 524         _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
 525                    is_nothrow_move_assignable<__node_allocator>::value)
 526         {__move_assign_alloc(__x, integral_constant<bool,
 527               __node_traits::propagate_on_container_move_assignment::value>());}
 528
 529 public:
 530     _LIBCPP_INLINE_VISIBILITY
 531     void swap(__forward_list_base& __x)
 532 #if _LIBCPP_STD_VER >= 14
 533         _NOEXCEPT;
 534 #else
 535         _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
 536                     __is_nothrow_swappable<__node_allocator>::value);
 537 #endif
 538 protected:
 539     void clear() _NOEXCEPT;
 540
 541 private:
 542     _LIBCPP_INLINE_VISIBILITY
 543     void __copy_assign_alloc(const __forward_list_base&, false_type) {}
 544     _LIBCPP_INLINE_VISIBILITY
 545     void __copy_assign_alloc(const __forward_list_base& __x, true_type)
 546     {
 547         if (__alloc() != __x.__alloc())
 548             clear();
 549         __alloc() = __x.__alloc();
 550     }
 551
 552     _LIBCPP_INLINE_VISIBILITY
 553     void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT
 554         {}
 555     _LIBCPP_INLINE_VISIBILITY
 556     void __move_assign_alloc(__forward_list_base& __x, true_type)
 557         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
 558         {__alloc() = _VSTD::move(__x.__alloc());}
 559 };
 560
 561 #ifndef _LIBCPP_CXX03_LANG
 562
 563 template <class _Tp, class _Alloc>
 564 inline
 565 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
 566         _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
 567     : __before_begin_(_VSTD::move(__x.__before_begin_))
 568 {
 569     __x.__before_begin()->__next_ = nullptr;
 570 }
 571
 572 template <class _Tp, class _Alloc>
 573 inline
 574 __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
 575                                                       const allocator_type& __a)
 576     : __before_begin_(__begin_node(), __node_allocator(__a))
 577 {
 578     if (__alloc() == __x.__alloc())
 579     {
 580         __before_begin()->__next_ = __x.__before_begin()->__next_;
 581         __x.__before_begin()->__next_ = nullptr;
 582     }
 583 }
 584
 585 #endif  // _LIBCPP_CXX03_LANG
 586
 587 template <class _Tp, class _Alloc>
 588 __forward_list_base<_Tp, _Alloc>::~__forward_list_base()
 589 {
 590     clear();
 591 }
 592
 593 template <class _Tp, class _Alloc>
 594 inline
 595 void
 596 __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
 597 #if _LIBCPP_STD_VER >= 14
 598         _NOEXCEPT
 599 #else
 600         _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
 601                     __is_nothrow_swappable<__node_allocator>::value)
 602 #endif
 603 {
 604     __swap_allocator(__alloc(), __x.__alloc(),
 605             integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
 606     using _VSTD::swap;
 607     swap(__before_begin()->__next_, __x.__before_begin()->__next_);
 608 }
 609
 610 template <class _Tp, class _Alloc>
 611 void
 612 __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
 613 {
 614     __node_allocator& __a = __alloc();
 615     for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
 616     {
 617         __node_pointer __next = __p->__next_;
 618         __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
 619         __node_traits::deallocate(__a, __p, 1);
 620         __p = __next;
 621     }
 622     __before_begin()->__next_ = nullptr;
 623 }
 624
 625 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
 626 class _LIBCPP_TEMPLATE_VIS forward_list
 627     : private __forward_list_base<_Tp, _Alloc>
 628 {
 629     typedef __forward_list_base<_Tp, _Alloc> base;
 630     typedef typename base::__node_allocator  __node_allocator;
 631     typedef typename base::__node               __node;
 632     typedef typename base::__node_traits        __node_traits;
 633     typedef typename base::__node_pointer       __node_pointer;
 634     typedef typename base::__begin_node_pointer __begin_node_pointer;
 635
 636 public:
 637     typedef _Tp    value_type;
 638     typedef _Alloc allocator_type;
 639
 640     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
 641                   "Allocator::value_type must be same type as value_type");
 642
 643     typedef value_type&                                                reference;
 644     typedef const value_type&                                          const_reference;
 645     typedef typename allocator_traits<allocator_type>::pointer         pointer;
 646     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 647     typedef typename allocator_traits<allocator_type>::size_type       size_type;
 648     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 649
 650     typedef typename base::iterator       iterator;
 651     typedef typename base::const_iterator const_iterator;
 652 #if _LIBCPP_STD_VER > 17
 653     typedef size_type                                __remove_return_type;
 654 #else
 655     typedef void                                     __remove_return_type;
 656 #endif
 657
 658     _LIBCPP_INLINE_VISIBILITY
 659     forward_list()
 660         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
 661         {} // = default;
 662     _LIBCPP_INLINE_VISIBILITY
 663     explicit forward_list(const allocator_type& __a);
 664     explicit forward_list(size_type __n);
 665 #if _LIBCPP_STD_VER > 11
 666     explicit forward_list(size_type __n, const allocator_type& __a);
 667 #endif
 668     forward_list(size_type __n, const value_type& __v);
 669     forward_list(size_type __n, const value_type& __v, const allocator_type& __a);
 670     template <class _InputIterator>
 671         forward_list(_InputIterator __f, _InputIterator __l,
 672                      typename enable_if<
 673                        __is_input_iterator<_InputIterator>::value
 674                      >::type* = nullptr);
 675     template <class _InputIterator>
 676         forward_list(_InputIterator __f, _InputIterator __l,
 677                      const allocator_type& __a,
 678                      typename enable_if<
 679                        __is_input_iterator<_InputIterator>::value
 680                      >::type* = nullptr);
 681     forward_list(const forward_list& __x);
 682     forward_list(const forward_list& __x, const allocator_type& __a);
 683
 684     forward_list& operator=(const forward_list& __x);
 685
 686 #ifndef _LIBCPP_CXX03_LANG
 687     _LIBCPP_INLINE_VISIBILITY
 688     forward_list(forward_list&& __x)
 689         _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
 690         : base(_VSTD::move(__x)) {}
 691     forward_list(forward_list&& __x, const allocator_type& __a);
 692
 693     forward_list(initializer_list<value_type> __il);
 694     forward_list(initializer_list<value_type> __il, const allocator_type& __a);
 695
 696     _LIBCPP_INLINE_VISIBILITY
 697     forward_list& operator=(forward_list&& __x)
 698         _NOEXCEPT_(
 699              __node_traits::propagate_on_container_move_assignment::value &&
 700              is_nothrow_move_assignable<allocator_type>::value);
 701
 702     _LIBCPP_INLINE_VISIBILITY
 703     forward_list& operator=(initializer_list<value_type> __il);
 704
 705     _LIBCPP_INLINE_VISIBILITY
 706     void assign(initializer_list<value_type> __il);
 707 #endif  // _LIBCPP_CXX03_LANG
 708
 709     // ~forward_list() = default;
 710
 711     template <class _InputIterator>
 712         typename enable_if
 713         <
 714             __is_input_iterator<_InputIterator>::value,
 715             void
 716         >::type
 717         assign(_InputIterator __f, _InputIterator __l);
 718     void assign(size_type __n, const value_type& __v);
 719
 720     _LIBCPP_INLINE_VISIBILITY
 721     allocator_type get_allocator() const _NOEXCEPT
 722         {return allocator_type(base::__alloc());}
 723
 724     _LIBCPP_INLINE_VISIBILITY
 725     iterator       begin() _NOEXCEPT
 726         {return       iterator(base::__before_begin()->__next_);}
 727     _LIBCPP_INLINE_VISIBILITY
 728     const_iterator begin() const _NOEXCEPT
 729         {return const_iterator(base::__before_begin()->__next_);}
 730     _LIBCPP_INLINE_VISIBILITY
 731     iterator       end() _NOEXCEPT
 732         {return       iterator(nullptr);}
 733     _LIBCPP_INLINE_VISIBILITY
 734     const_iterator end() const _NOEXCEPT
 735         {return const_iterator(nullptr);}
 736
 737     _LIBCPP_INLINE_VISIBILITY
 738     const_iterator cbegin() const _NOEXCEPT
 739         {return const_iterator(base::__before_begin()->__next_);}
 740     _LIBCPP_INLINE_VISIBILITY
 741     const_iterator cend() const _NOEXCEPT
 742         {return const_iterator(nullptr);}
 743
 744     _LIBCPP_INLINE_VISIBILITY
 745     iterator       before_begin() _NOEXCEPT
 746         {return       iterator(base::__before_begin());}
 747     _LIBCPP_INLINE_VISIBILITY
 748     const_iterator before_begin() const _NOEXCEPT
 749         {return const_iterator(base::__before_begin());}
 750     _LIBCPP_INLINE_VISIBILITY
 751     const_iterator cbefore_begin() const _NOEXCEPT
 752         {return const_iterator(base::__before_begin());}
 753
 754     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 755     bool empty() const _NOEXCEPT
 756         {return base::__before_begin()->__next_ == nullptr;}
 757     _LIBCPP_INLINE_VISIBILITY
 758     size_type max_size() const _NOEXCEPT {
 759         return std::min<size_type>(
 760             __node_traits::max_size(base::__alloc()),
 761             numeric_limits<difference_type>::max());
 762     }
 763
 764     _LIBCPP_INLINE_VISIBILITY
 765     reference       front()       {return base::__before_begin()->__next_->__value_;}
 766     _LIBCPP_INLINE_VISIBILITY
 767     const_reference front() const {return base::__before_begin()->__next_->__value_;}
 768
 769 #ifndef _LIBCPP_CXX03_LANG
 770 #if _LIBCPP_STD_VER > 14
 771     template <class... _Args> reference emplace_front(_Args&&... __args);
 772 #else
 773     template <class... _Args> void      emplace_front(_Args&&... __args);
 774 #endif
 775     void push_front(value_type&& __v);
 776 #endif  // _LIBCPP_CXX03_LANG
 777     void push_front(const value_type& __v);
 778
 779     void pop_front();
 780
 781 #ifndef _LIBCPP_CXX03_LANG
 782     template <class... _Args>
 783         iterator emplace_after(const_iterator __p, _Args&&... __args);
 784
 785     iterator insert_after(const_iterator __p, value_type&& __v);
 786     iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
 787         {return insert_after(__p, __il.begin(), __il.end());}
 788 #endif  // _LIBCPP_CXX03_LANG
 789     iterator insert_after(const_iterator __p, const value_type& __v);
 790     iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
 791     template <class _InputIterator>
 792         _LIBCPP_INLINE_VISIBILITY
 793         typename enable_if
 794         <
 795             __is_input_iterator<_InputIterator>::value,
 796             iterator
 797         >::type
 798         insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
 799
 800     iterator erase_after(const_iterator __p);
 801     iterator erase_after(const_iterator __f, const_iterator __l);
 802
 803     _LIBCPP_INLINE_VISIBILITY
 804     void swap(forward_list& __x)
 805 #if _LIBCPP_STD_VER >= 14
 806         _NOEXCEPT
 807 #else
 808         _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
 809                    __is_nothrow_swappable<__node_allocator>::value)
 810 #endif
 811         {base::swap(__x);}
 812
 813     void resize(size_type __n);
 814     void resize(size_type __n, const value_type& __v);
 815     _LIBCPP_INLINE_VISIBILITY
 816     void clear() _NOEXCEPT {base::clear();}
 817
 818     _LIBCPP_INLINE_VISIBILITY
 819     void splice_after(const_iterator __p, forward_list&& __x);
 820     _LIBCPP_INLINE_VISIBILITY
 821     void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
 822     _LIBCPP_INLINE_VISIBILITY
 823     void splice_after(const_iterator __p, forward_list&& __x,
 824                       const_iterator __f, const_iterator __l);
 825     void splice_after(const_iterator __p, forward_list& __x);
 826     void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
 827     void splice_after(const_iterator __p, forward_list& __x,
 828                       const_iterator __f, const_iterator __l);
 829     __remove_return_type remove(const value_type& __v);
 830     template <class _Predicate> __remove_return_type remove_if(_Predicate __pred);
 831     _LIBCPP_INLINE_VISIBILITY
 832     __remove_return_type unique() {return unique(__equal_to<value_type>());}
 833     template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred);
 834 #ifndef _LIBCPP_CXX03_LANG
 835     _LIBCPP_INLINE_VISIBILITY
 836     void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
 837     template <class _Compare>
 838         _LIBCPP_INLINE_VISIBILITY
 839         void merge(forward_list&& __x, _Compare __comp)
 840         {merge(__x, _VSTD::move(__comp));}
 841 #endif  // _LIBCPP_CXX03_LANG
 842     _LIBCPP_INLINE_VISIBILITY
 843     void merge(forward_list& __x) {merge(__x, __less<value_type>());}
 844     template <class _Compare> void merge(forward_list& __x, _Compare __comp);
 845     _LIBCPP_INLINE_VISIBILITY
 846     void sort() {sort(__less<value_type>());}
 847     template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
 848     void reverse() _NOEXCEPT;
 849
 850 private:
 851
 852 #ifndef _LIBCPP_CXX03_LANG
 853     void __move_assign(forward_list& __x, true_type)
 854         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
 855     void __move_assign(forward_list& __x, false_type);
 856 #endif  // _LIBCPP_CXX03_LANG
 857
 858     template <class _Compare>
 859         static
 860         __node_pointer
 861         __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
 862
 863     template <class _Compare>
 864         static
 865         __node_pointer
 866         __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
 867 };
 868
 869
 870 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
 871 template<class _InputIterator,
 872          class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
 873          class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
 874          >
 875 forward_list(_InputIterator, _InputIterator)
 876   -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
 877
 878 template<class _InputIterator,
 879          class _Alloc,
 880          class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
 881          >
 882 forward_list(_InputIterator, _InputIterator, _Alloc)
 883   -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
 884 #endif
 885
 886 template <class _Tp, class _Alloc>
 887 inline
 888 forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
 889     : base(__a)
 890 {
 891 }
 892
 893 template <class _Tp, class _Alloc>
 894 forward_list<_Tp, _Alloc>::forward_list(size_type __n)
 895 {
 896     if (__n > 0)
 897     {
 898         __node_allocator& __a = base::__alloc();
 899         typedef __allocator_destructor<__node_allocator> _Dp;
 900         unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
 901         for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
 902                                                              __p = __p->__next_as_begin())
 903         {
 904             __h.reset(__node_traits::allocate(__a, 1));
 905             __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
 906             __h->__next_ = nullptr;
 907             __p->__next_ = __h.release();
 908         }
 909     }
 910 }
 911
 912 #if _LIBCPP_STD_VER > 11
 913 template <class _Tp, class _Alloc>
 914 forward_list<_Tp, _Alloc>::forward_list(size_type __n,
 915                                         const allocator_type& __base_alloc)
 916     : base ( __base_alloc )
 917 {
 918     if (__n > 0)
 919     {
 920         __node_allocator& __a = base::__alloc();
 921         typedef __allocator_destructor<__node_allocator> _Dp;
 922         unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
 923         for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
 924                                                              __p = __p->__next_as_begin())
 925         {
 926             __h.reset(__node_traits::allocate(__a, 1));
 927             __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
 928             __h->__next_ = nullptr;
 929             __p->__next_ = __h.release();
 930         }
 931     }
 932 }
 933 #endif
 934
 935 template <class _Tp, class _Alloc>
 936 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
 937 {
 938     insert_after(cbefore_begin(), __n, __v);
 939 }
 940
 941 template <class _Tp, class _Alloc>
 942 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v,
 943                                         const allocator_type& __a)
 944     : base(__a)
 945 {
 946     insert_after(cbefore_begin(), __n, __v);
 947 }
 948
 949 template <class _Tp, class _Alloc>
 950 template <class _InputIterator>
 951 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
 952                                         typename enable_if<
 953                                           __is_input_iterator<_InputIterator>::value
 954                                         >::type*)
 955 {
 956     insert_after(cbefore_begin(), __f, __l);
 957 }
 958
 959 template <class _Tp, class _Alloc>
 960 template <class _InputIterator>
 961 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
 962                                         const allocator_type& __a,
 963                                         typename enable_if<
 964                                           __is_input_iterator<_InputIterator>::value
 965                                         >::type*)
 966     : base(__a)
 967 {
 968     insert_after(cbefore_begin(), __f, __l);
 969 }
 970
 971 template <class _Tp, class _Alloc>
 972 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
 973     : base(
 974           __node_traits::select_on_container_copy_construction(__x.__alloc())) {
 975   insert_after(cbefore_begin(), __x.begin(), __x.end());
 976 }
 977
 978 template <class _Tp, class _Alloc>
 979 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
 980                                         const allocator_type& __a)
 981     : base(__a)
 982 {
 983     insert_after(cbefore_begin(), __x.begin(), __x.end());
 984 }
 985
 986 template <class _Tp, class _Alloc>
 987 forward_list<_Tp, _Alloc>&
 988 forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
 989 {
 990     if (this != &__x)
 991     {
 992         base::__copy_assign_alloc(__x);
 993         assign(__x.begin(), __x.end());
 994     }
 995     return *this;
 996 }
 997
 998 #ifndef _LIBCPP_CXX03_LANG
 999 template <class _Tp, class _Alloc>
1000 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
1001                                         const allocator_type& __a)
1002     : base(_VSTD::move(__x), __a)
1003 {
1004     if (base::__alloc() != __x.__alloc())
1005     {
1006         typedef move_iterator<iterator> _Ip;
1007         insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
1008     }
1009 }
1010
1011 template <class _Tp, class _Alloc>
1012 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
1013 {
1014     insert_after(cbefore_begin(), __il.begin(), __il.end());
1015 }
1016
1017 template <class _Tp, class _Alloc>
1018 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
1019                                         const allocator_type& __a)
1020     : base(__a)
1021 {
1022     insert_after(cbefore_begin(), __il.begin(), __il.end());
1023 }
1024
1025 template <class _Tp, class _Alloc>
1026 void
1027 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
1028     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1029 {
1030     clear();
1031     base::__move_assign_alloc(__x);
1032     base::__before_begin()->__next_ = __x.__before_begin()->__next_;
1033     __x.__before_begin()->__next_ = nullptr;
1034 }
1035
1036 template <class _Tp, class _Alloc>
1037 void
1038 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
1039 {
1040     if (base::__alloc() == __x.__alloc())
1041         __move_assign(__x, true_type());
1042     else
1043     {
1044         typedef move_iterator<iterator> _Ip;
1045         assign(_Ip(__x.begin()), _Ip(__x.end()));
1046     }
1047 }
1048
1049 template <class _Tp, class _Alloc>
1050 inline
1051 forward_list<_Tp, _Alloc>&
1052 forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
1053     _NOEXCEPT_(
1054              __node_traits::propagate_on_container_move_assignment::value &&
1055              is_nothrow_move_assignable<allocator_type>::value)
1056 {
1057     __move_assign(__x, integral_constant<bool,
1058           __node_traits::propagate_on_container_move_assignment::value>());
1059     return *this;
1060 }
1061
1062 template <class _Tp, class _Alloc>
1063 inline
1064 forward_list<_Tp, _Alloc>&
1065 forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
1066 {
1067     assign(__il.begin(), __il.end());
1068     return *this;
1069 }
1070
1071 #endif  // _LIBCPP_CXX03_LANG
1072
1073 template <class _Tp, class _Alloc>
1074 template <class _InputIterator>
1075 typename enable_if
1076 <
1077     __is_input_iterator<_InputIterator>::value,
1078     void
1079 >::type
1080 forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
1081 {
1082     iterator __i = before_begin();
1083     iterator __j = _VSTD::next(__i);
1084     iterator __e = end();
1085     for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)
1086         *__j = *__f;
1087     if (__j == __e)
1088         insert_after(__i, __f, __l);
1089     else
1090         erase_after(__i, __e);
1091 }
1092
1093 template <class _Tp, class _Alloc>
1094 void
1095 forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
1096 {
1097     iterator __i = before_begin();
1098     iterator __j = _VSTD::next(__i);
1099     iterator __e = end();
1100     for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1101         *__j = __v;
1102     if (__j == __e)
1103         insert_after(__i, __n, __v);
1104     else
1105         erase_after(__i, __e);
1106 }
1107
1108 #ifndef _LIBCPP_CXX03_LANG
1109
1110 template <class _Tp, class _Alloc>
1111 inline
1112 void
1113 forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
1114 {
1115     assign(__il.begin(), __il.end());
1116 }
1117
1118 template <class _Tp, class _Alloc>
1119 template <class... _Args>
1120 #if _LIBCPP_STD_VER > 14
1121 typename forward_list<_Tp, _Alloc>::reference
1122 #else
1123 void
1124 #endif
1125 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1126 {
1127     __node_allocator& __a = base::__alloc();
1128     typedef __allocator_destructor<__node_allocator> _Dp;
1129     unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1130     __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1131                                   _VSTD::forward<_Args>(__args)...);
1132     __h->__next_ = base::__before_begin()->__next_;
1133     base::__before_begin()->__next_ = __h.release();
1134 #if _LIBCPP_STD_VER > 14
1135     return base::__before_begin()->__next_->__value_;
1136 #endif
1137 }
1138
1139 template <class _Tp, class _Alloc>
1140 void
1141 forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
1142 {
1143     __node_allocator& __a = base::__alloc();
1144     typedef __allocator_destructor<__node_allocator> _Dp;
1145     unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1146     __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1147     __h->__next_ = base::__before_begin()->__next_;
1148     base::__before_begin()->__next_ = __h.release();
1149 }
1150
1151 #endif  // _LIBCPP_CXX03_LANG
1152
1153 template <class _Tp, class _Alloc>
1154 void
1155 forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
1156 {
1157     __node_allocator& __a = base::__alloc();
1158     typedef __allocator_destructor<__node_allocator> _Dp;
1159     unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1160     __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1161     __h->__next_ = base::__before_begin()->__next_;
1162     base::__before_begin()->__next_ = __h.release();
1163 }
1164
1165 template <class _Tp, class _Alloc>
1166 void
1167 forward_list<_Tp, _Alloc>::pop_front()
1168 {
1169     __node_allocator& __a = base::__alloc();
1170     __node_pointer __p = base::__before_begin()->__next_;
1171     base::__before_begin()->__next_ = __p->__next_;
1172     __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
1173     __node_traits::deallocate(__a, __p, 1);
1174 }
1175
1176 #ifndef _LIBCPP_CXX03_LANG
1177
1178 template <class _Tp, class _Alloc>
1179 template <class... _Args>
1180 typename forward_list<_Tp, _Alloc>::iterator
1181 forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
1182 {
1183     __begin_node_pointer const __r = __p.__get_begin();
1184     __node_allocator& __a = base::__alloc();
1185     typedef __allocator_destructor<__node_allocator> _Dp;
1186     unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1187     __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
1188                                   _VSTD::forward<_Args>(__args)...);
1189     __h->__next_ = __r->__next_;
1190     __r->__next_ = __h.release();
1191     return iterator(__r->__next_);
1192 }
1193
1194 template <class _Tp, class _Alloc>
1195 typename forward_list<_Tp, _Alloc>::iterator
1196 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
1197 {
1198     __begin_node_pointer const __r = __p.__get_begin();
1199     __node_allocator& __a = base::__alloc();
1200     typedef __allocator_destructor<__node_allocator> _Dp;
1201     unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1202     __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1203     __h->__next_ = __r->__next_;
1204     __r->__next_ = __h.release();
1205     return iterator(__r->__next_);
1206 }
1207
1208 #endif  // _LIBCPP_CXX03_LANG
1209
1210 template <class _Tp, class _Alloc>
1211 typename forward_list<_Tp, _Alloc>::iterator
1212 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
1213 {
1214     __begin_node_pointer const __r = __p.__get_begin();
1215     __node_allocator& __a = base::__alloc();
1216     typedef __allocator_destructor<__node_allocator> _Dp;
1217     unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1218     __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1219     __h->__next_ = __r->__next_;
1220     __r->__next_ = __h.release();
1221     return iterator(__r->__next_);
1222 }
1223
1224 template <class _Tp, class _Alloc>
1225 typename forward_list<_Tp, _Alloc>::iterator
1226 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
1227                                         const value_type& __v)
1228 {
1229     __begin_node_pointer __r = __p.__get_begin();
1230     if (__n > 0)
1231     {
1232         __node_allocator& __a = base::__alloc();
1233         typedef __allocator_destructor<__node_allocator> _Dp;
1234         unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1235         __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1236         __node_pointer __first = __h.release();
1237         __node_pointer __last = __first;
1238 #ifndef _LIBCPP_NO_EXCEPTIONS
1239         try
1240         {
1241 #endif  // _LIBCPP_NO_EXCEPTIONS
1242             for (--__n; __n != 0; --__n, __last = __last->__next_)
1243             {
1244                 __h.reset(__node_traits::allocate(__a, 1));
1245                 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1246                 __last->__next_ = __h.release();
1247             }
1248 #ifndef _LIBCPP_NO_EXCEPTIONS
1249         }
1250         catch (...)
1251         {
1252             while (__first != nullptr)
1253             {
1254                 __node_pointer __next = __first->__next_;
1255                 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1256                 __node_traits::deallocate(__a, __first, 1);
1257                 __first = __next;
1258             }
1259             throw;
1260         }
1261 #endif  // _LIBCPP_NO_EXCEPTIONS
1262         __last->__next_ = __r->__next_;
1263         __r->__next_ = __first;
1264         __r = static_cast<__begin_node_pointer>(__last);
1265     }
1266     return iterator(__r);
1267 }
1268
1269 template <class _Tp, class _Alloc>
1270 template <class _InputIterator>
1271 typename enable_if
1272 <
1273     __is_input_iterator<_InputIterator>::value,
1274     typename forward_list<_Tp, _Alloc>::iterator
1275 >::type
1276 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
1277                                         _InputIterator __f, _InputIterator __l)
1278 {
1279     __begin_node_pointer __r = __p.__get_begin();
1280     if (__f != __l)
1281     {
1282         __node_allocator& __a = base::__alloc();
1283         typedef __allocator_destructor<__node_allocator> _Dp;
1284         unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
1285         __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1286         __node_pointer __first = __h.release();
1287         __node_pointer __last = __first;
1288 #ifndef _LIBCPP_NO_EXCEPTIONS
1289         try
1290         {
1291 #endif  // _LIBCPP_NO_EXCEPTIONS
1292             for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
1293             {
1294                 __h.reset(__node_traits::allocate(__a, 1));
1295                 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
1296                 __last->__next_ = __h.release();
1297             }
1298 #ifndef _LIBCPP_NO_EXCEPTIONS
1299         }
1300         catch (...)
1301         {
1302             while (__first != nullptr)
1303             {
1304                 __node_pointer __next = __first->__next_;
1305                 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
1306                 __node_traits::deallocate(__a, __first, 1);
1307                 __first = __next;
1308             }
1309             throw;
1310         }
1311 #endif  // _LIBCPP_NO_EXCEPTIONS
1312         __last->__next_ = __r->__next_;
1313         __r->__next_ = __first;
1314         __r = static_cast<__begin_node_pointer>(__last);
1315     }
1316     return iterator(__r);
1317 }
1318
1319 template <class _Tp, class _Alloc>
1320 typename forward_list<_Tp, _Alloc>::iterator
1321 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
1322 {
1323     __begin_node_pointer __p = __f.__get_begin();
1324     __node_pointer __n = __p->__next_;
1325     __p->__next_ = __n->__next_;
1326     __node_allocator& __a = base::__alloc();
1327     __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1328     __node_traits::deallocate(__a, __n, 1);
1329     return iterator(__p->__next_);
1330 }
1331
1332 template <class _Tp, class _Alloc>
1333 typename forward_list<_Tp, _Alloc>::iterator
1334 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
1335 {
1336     __node_pointer __e = __l.__get_unsafe_node_pointer();
1337     if (__f != __l)
1338     {
1339         __begin_node_pointer __bp = __f.__get_begin();
1340
1341         __node_pointer __n = __bp->__next_;
1342         if (__n != __e)
1343         {
1344             __bp->__next_ = __e;
1345             __node_allocator& __a = base::__alloc();
1346             do
1347             {
1348                 __node_pointer __tmp = __n->__next_;
1349                 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
1350                 __node_traits::deallocate(__a, __n, 1);
1351                 __n = __tmp;
1352             } while (__n != __e);
1353         }
1354     }
1355     return iterator(__e);
1356 }
1357
1358 template <class _Tp, class _Alloc>
1359 void
1360 forward_list<_Tp, _Alloc>::resize(size_type __n)
1361 {
1362     size_type __sz = 0;
1363     iterator __p = before_begin();
1364     iterator __i = begin();
1365     iterator __e = end();
1366     for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1367         ;
1368     if (__i != __e)
1369         erase_after(__p, __e);
1370     else
1371     {
1372         __n -= __sz;
1373         if (__n > 0)
1374         {
1375             __node_allocator& __a = base::__alloc();
1376             typedef __allocator_destructor<__node_allocator> _Dp;
1377             unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1378             for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1379                                                          __ptr = __ptr->__next_as_begin())
1380             {
1381                 __h.reset(__node_traits::allocate(__a, 1));
1382                 __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
1383                 __h->__next_ = nullptr;
1384                 __ptr->__next_ = __h.release();
1385             }
1386         }
1387     }
1388 }
1389
1390 template <class _Tp, class _Alloc>
1391 void
1392 forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
1393 {
1394     size_type __sz = 0;
1395     iterator __p = before_begin();
1396     iterator __i = begin();
1397     iterator __e = end();
1398     for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1399         ;
1400     if (__i != __e)
1401         erase_after(__p, __e);
1402     else
1403     {
1404         __n -= __sz;
1405         if (__n > 0)
1406         {
1407             __node_allocator& __a = base::__alloc();
1408             typedef __allocator_destructor<__node_allocator> _Dp;
1409             unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
1410             for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
1411                                                          __ptr = __ptr->__next_as_begin())
1412             {
1413                 __h.reset(__node_traits::allocate(__a, 1));
1414                 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
1415                 __h->__next_ = nullptr;
1416                 __ptr->__next_ = __h.release();
1417             }
1418         }
1419     }
1420 }
1421
1422 template <class _Tp, class _Alloc>
1423 void
1424 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1425                                         forward_list& __x)
1426 {
1427     if (!__x.empty())
1428     {
1429         if (__p.__get_begin()->__next_ != nullptr)
1430         {
1431             const_iterator __lm1 = __x.before_begin();
1432             while (__lm1.__get_begin()->__next_ != nullptr)
1433                 ++__lm1;
1434             __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1435         }
1436         __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
1437         __x.__before_begin()->__next_ = nullptr;
1438     }
1439 }
1440
1441 template <class _Tp, class _Alloc>
1442 void
1443 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1444                                         forward_list& /*__other*/,
1445                                         const_iterator __i)
1446 {
1447     const_iterator __lm1 = _VSTD::next(__i);
1448     if (__p != __i && __p != __lm1)
1449     {
1450         __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
1451         __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1452         __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
1453     }
1454 }
1455
1456 template <class _Tp, class _Alloc>
1457 void
1458 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1459                                         forward_list& /*__other*/,
1460                                         const_iterator __f, const_iterator __l)
1461 {
1462     if (__f != __l && __p != __f)
1463     {
1464         const_iterator __lm1 = __f;
1465         while (__lm1.__get_begin()->__next_ != __l.__get_begin())
1466             ++__lm1;
1467         if (__f != __lm1)
1468         {
1469             __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1470             __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
1471             __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
1472         }
1473     }
1474 }
1475
1476 template <class _Tp, class _Alloc>
1477 inline _LIBCPP_INLINE_VISIBILITY
1478 void
1479 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1480                                         forward_list&& __x)
1481 {
1482     splice_after(__p, __x);
1483 }
1484
1485 template <class _Tp, class _Alloc>
1486 inline _LIBCPP_INLINE_VISIBILITY
1487 void
1488 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1489                                         forward_list&& __x,
1490                                         const_iterator __i)
1491 {
1492     splice_after(__p, __x, __i);
1493 }
1494
1495 template <class _Tp, class _Alloc>
1496 inline _LIBCPP_INLINE_VISIBILITY
1497 void
1498 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1499                                         forward_list&& __x,
1500                                         const_iterator __f, const_iterator __l)
1501 {
1502     splice_after(__p, __x, __f, __l);
1503 }
1504
1505 template <class _Tp, class _Alloc>
1506 typename forward_list<_Tp, _Alloc>::__remove_return_type
1507 forward_list<_Tp, _Alloc>::remove(const value_type& __v)
1508 {
1509     forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1510     typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1511     const iterator __e = end();
1512     for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1513     {
1514         if (__i.__get_begin()->__next_->__value_ == __v)
1515         {
1516             ++__count_removed;
1517             iterator __j = _VSTD::next(__i, 2);
1518             for (; __j != __e && *__j == __v; ++__j)
1519                 ++__count_removed;
1520             __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1521             if (__j == __e)
1522                 break;
1523             __i = __j;
1524         }
1525         else
1526             ++__i;
1527     }
1528
1529     return (__remove_return_type) __count_removed;
1530 }
1531
1532 template <class _Tp, class _Alloc>
1533 template <class _Predicate>
1534 typename forward_list<_Tp, _Alloc>::__remove_return_type
1535 forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
1536 {
1537     forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1538     typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1539     const iterator __e = end();
1540     for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
1541     {
1542         if (__pred(__i.__get_begin()->__next_->__value_))
1543         {
1544             ++__count_removed;
1545             iterator __j = _VSTD::next(__i, 2);
1546             for (; __j != __e && __pred(*__j); ++__j)
1547                 ++__count_removed;
1548             __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1549             if (__j == __e)
1550                 break;
1551             __i = __j;
1552         }
1553         else
1554             ++__i;
1555     }
1556
1557     return (__remove_return_type) __count_removed;
1558 }
1559
1560 template <class _Tp, class _Alloc>
1561 template <class _BinaryPredicate>
1562 typename forward_list<_Tp, _Alloc>::__remove_return_type
1563 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
1564 {
1565     forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1566     typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1567     for (iterator __i = begin(), __e = end(); __i != __e;)
1568     {
1569         iterator __j = _VSTD::next(__i);
1570         for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1571             ++__count_removed;
1572         if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
1573             __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1574         __i = __j;
1575     }
1576
1577     return (__remove_return_type) __count_removed;
1578 }
1579
1580 template <class _Tp, class _Alloc>
1581 template <class _Compare>
1582 void
1583 forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
1584 {
1585     if (this != &__x)
1586     {
1587         base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
1588                                                     __x.__before_begin()->__next_,
1589                                                     __comp);
1590         __x.__before_begin()->__next_ = nullptr;
1591     }
1592 }
1593
1594 template <class _Tp, class _Alloc>
1595 template <class _Compare>
1596 typename forward_list<_Tp, _Alloc>::__node_pointer
1597 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
1598                                    _Compare& __comp)
1599 {
1600     if (__f1 == nullptr)
1601         return __f2;
1602     if (__f2 == nullptr)
1603         return __f1;
1604     __node_pointer __r;
1605     if (__comp(__f2->__value_, __f1->__value_))
1606     {
1607         __node_pointer __t = __f2;
1608         while (__t->__next_ != nullptr &&
1609                              __comp(__t->__next_->__value_, __f1->__value_))
1610             __t = __t->__next_;
1611         __r = __f2;
1612         __f2 = __t->__next_;
1613         __t->__next_ = __f1;
1614     }
1615     else
1616         __r = __f1;
1617     __node_pointer __p = __f1;
1618     __f1 = __f1->__next_;
1619     while (__f1 != nullptr && __f2 != nullptr)
1620     {
1621         if (__comp(__f2->__value_, __f1->__value_))
1622         {
1623             __node_pointer __t = __f2;
1624             while (__t->__next_ != nullptr &&
1625                                  __comp(__t->__next_->__value_, __f1->__value_))
1626                 __t = __t->__next_;
1627             __p->__next_ = __f2;
1628             __f2 = __t->__next_;
1629             __t->__next_ = __f1;
1630         }
1631         __p = __f1;
1632         __f1 = __f1->__next_;
1633     }
1634     if (__f2 != nullptr)
1635         __p->__next_ = __f2;
1636     return __r;
1637 }
1638
1639 template <class _Tp, class _Alloc>
1640 template <class _Compare>
1641 inline
1642 void
1643 forward_list<_Tp, _Alloc>::sort(_Compare __comp)
1644 {
1645     base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
1646                                        _VSTD::distance(begin(), end()), __comp);
1647 }
1648
1649 template <class _Tp, class _Alloc>
1650 template <class _Compare>
1651 typename forward_list<_Tp, _Alloc>::__node_pointer
1652 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
1653                                   _Compare& __comp)
1654 {
1655     switch (__sz)
1656     {
1657     case 0:
1658     case 1:
1659         return __f1;
1660     case 2:
1661         if (__comp(__f1->__next_->__value_, __f1->__value_))
1662         {
1663             __node_pointer __t = __f1->__next_;
1664             __t->__next_ = __f1;
1665             __f1->__next_ = nullptr;
1666             __f1 = __t;
1667         }
1668         return __f1;
1669     }
1670     difference_type __sz1 = __sz / 2;
1671     difference_type __sz2 = __sz - __sz1;
1672     __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
1673     __node_pointer __f2 = __t->__next_;
1674     __t->__next_ = nullptr;
1675     return __merge(__sort(__f1, __sz1, __comp),
1676                    __sort(__f2, __sz2, __comp), __comp);
1677 }
1678
1679 template <class _Tp, class _Alloc>
1680 void
1681 forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
1682 {
1683     __node_pointer __p = base::__before_begin()->__next_;
1684     if (__p != nullptr)
1685     {
1686         __node_pointer __f = __p->__next_;
1687         __p->__next_ = nullptr;
1688         while (__f != nullptr)
1689         {
1690             __node_pointer __t = __f->__next_;
1691             __f->__next_ = __p;
1692             __p = __f;
1693             __f = __t;
1694         }
1695         base::__before_begin()->__next_ = __p;
1696     }
1697 }
1698
1699 template <class _Tp, class _Alloc>
1700 bool operator==(const forward_list<_Tp, _Alloc>& __x,
1701                 const forward_list<_Tp, _Alloc>& __y)
1702 {
1703     typedef forward_list<_Tp, _Alloc> _Cp;
1704     typedef typename _Cp::const_iterator _Ip;
1705     _Ip __ix = __x.begin();
1706     _Ip __ex = __x.end();
1707     _Ip __iy = __y.begin();
1708     _Ip __ey = __y.end();
1709     for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1710         if (!(*__ix == *__iy))
1711             return false;
1712     return (__ix == __ex) == (__iy == __ey);
1713 }
1714
1715 template <class _Tp, class _Alloc>
1716 inline _LIBCPP_INLINE_VISIBILITY
1717 bool operator!=(const forward_list<_Tp, _Alloc>& __x,
1718                 const forward_list<_Tp, _Alloc>& __y)
1719 {
1720     return !(__x == __y);
1721 }
1722
1723 template <class _Tp, class _Alloc>
1724 inline _LIBCPP_INLINE_VISIBILITY
1725 bool operator< (const forward_list<_Tp, _Alloc>& __x,
1726                 const forward_list<_Tp, _Alloc>& __y)
1727 {
1728     return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
1729                                          __y.begin(), __y.end());
1730 }
1731
1732 template <class _Tp, class _Alloc>
1733 inline _LIBCPP_INLINE_VISIBILITY
1734 bool operator> (const forward_list<_Tp, _Alloc>& __x,
1735                 const forward_list<_Tp, _Alloc>& __y)
1736 {
1737     return __y < __x;
1738 }
1739
1740 template <class _Tp, class _Alloc>
1741 inline _LIBCPP_INLINE_VISIBILITY
1742 bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1743                 const forward_list<_Tp, _Alloc>& __y)
1744 {
1745     return !(__x < __y);
1746 }
1747
1748 template <class _Tp, class _Alloc>
1749 inline _LIBCPP_INLINE_VISIBILITY
1750 bool operator<=(const forward_list<_Tp, _Alloc>& __x,
1751                 const forward_list<_Tp, _Alloc>& __y)
1752 {
1753     return !(__y < __x);
1754 }
1755
1756 template <class _Tp, class _Alloc>
1757 inline _LIBCPP_INLINE_VISIBILITY
1758 void
1759 swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1760     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1761 {
1762     __x.swap(__y);
1763 }
1764
1765 #if _LIBCPP_STD_VER > 17
1766 template <class _Tp, class _Allocator, class _Predicate>
1767 inline _LIBCPP_INLINE_VISIBILITY
1768 void erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred)
1769 { __c.remove_if(__pred); }
1770
1771 template <class _Tp, class _Allocator, class _Up>
1772 inline _LIBCPP_INLINE_VISIBILITY
1773 void erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v)
1774 { _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; }); }
1775 #endif
1776
1777 _LIBCPP_END_NAMESPACE_STD
1778
1779 _LIBCPP_POP_MACROS
1780
1781 #endif  // _LIBCPP_FORWARD_LIST