libcxx/include/forward_list

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