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