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