libcxx/include/forward_list

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