libcxx/include/forward_list

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