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