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