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