xref: /freebsd/contrib/llvm-project/libcxx/include/forward_list (revision 5ca8e32633c4ffbbcd6762e5888b6a4ba0708c6c) 
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
16namespace std
17{
18
19template <class T, class Allocator = allocator<T>>
20class forward_list
21{
22public:
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
147template <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
151template<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
155template <class T, class Allocator>
156    bool operator==(const forward_list<T, Allocator>& x,
157                    const forward_list<T, Allocator>& y);
158
159template <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
163template <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
167template <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
171template <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
175template <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
179template<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
183template <class T, class Allocator>
184    void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
185         noexcept(noexcept(x.swap(y)));
186
187template <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
190template <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
260template <class _Tp, class _VoidPtr> struct __forward_list_node;
261template <class _NodePtr> struct __forward_begin_node;
262
263
264template <class>
265struct __forward_list_node_value_type;
266
267template <class _Tp, class _VoidPtr>
268struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
269  typedef _Tp type;
270};
271
272template <class _NodePtr>
273struct __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
303template <class _NodePtr>
304struct __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
320template <class _Tp, class _VoidPtr>
321using __begin_node_of = __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >;
322
323template <class _Tp, class _VoidPtr>
324struct _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
338template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list;
339template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
340
341template <class _NodePtr>
342class _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
377public:
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
419template <class _NodeConstPtr>
420class _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
458public:
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
503template <class _Tp, class _Alloc>
504class __forward_list_base
505{
506protected:
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
551public:
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
559private:
560    __forward_list_base(const __forward_list_base&);
561    __forward_list_base& operator=(const __forward_list_base&);
562
563public:
564    _LIBCPP_HIDE_FROM_ABI ~__forward_list_base();
565
566protected:
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
579public:
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
588protected:
589    _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
590
591private:
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
613template <class _Tp, class _Alloc>
614inline
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
622template <class _Tp, class _Alloc>
623inline
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
637template <class _Tp, class _Alloc>
638__forward_list_base<_Tp, _Alloc>::~__forward_list_base()
639{
640    clear();
641}
642
643template <class _Tp, class _Alloc>
644inline
645void
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
660template <class _Tp, class _Alloc>
661void
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
675template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
676class _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
686public:
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>
781    __enable_if_t<__has_input_iterator_category<_InputIterator>::value, 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>
876    _LIBCPP_INLINE_VISIBILITY
877    __enable_if_t<__has_input_iterator_category<_InputIterator>::value, 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
945private:
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
971template<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         >
976forward_list(_InputIterator, _InputIterator)
977  -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
978
979template<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         >
984forward_list(_InputIterator, _InputIterator, _Alloc)
985  -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
986#endif
987
988#if _LIBCPP_STD_VER >= 23
989template <ranges::input_range _Range,
990          class _Alloc = allocator<ranges::range_value_t<_Range>>,
991          class = enable_if_t<__is_allocator<_Alloc>::value>
992          >
993forward_list(from_range_t, _Range&&, _Alloc = _Alloc())
994  -> forward_list<ranges::range_value_t<_Range>, _Alloc>;
995#endif
996
997template <class _Tp, class _Alloc>
998inline
999forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
1000    : base(__a)
1001{
1002}
1003
1004template <class _Tp, class _Alloc>
1005forward_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
1024template <class _Tp, class _Alloc>
1025forward_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
1046template <class _Tp, class _Alloc>
1047forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
1048{
1049    insert_after(cbefore_begin(), __n, __v);
1050}
1051
1052template <class _Tp, class _Alloc>
1053template <class _InputIterator>
1054forward_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
1060template <class _Tp, class _Alloc>
1061template <class _InputIterator>
1062forward_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
1070template <class _Tp, class _Alloc>
1071forward_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
1077template <class _Tp, class _Alloc>
1078forward_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
1085template <class _Tp, class _Alloc>
1086forward_list<_Tp, _Alloc>&
1087forward_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
1098template <class _Tp, class _Alloc>
1099forward_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
1110template <class _Tp, class _Alloc>
1111forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
1112{
1113    insert_after(cbefore_begin(), __il.begin(), __il.end());
1114}
1115
1116template <class _Tp, class _Alloc>
1117forward_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
1124template <class _Tp, class _Alloc>
1125void
1126forward_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
1135template <class _Tp, class _Alloc>
1136void
1137forward_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
1148template <class _Tp, class _Alloc>
1149inline
1150forward_list<_Tp, _Alloc>&
1151forward_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
1161template <class _Tp, class _Alloc>
1162inline
1163forward_list<_Tp, _Alloc>&
1164forward_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
1172template <class _Tp, class _Alloc>
1173template <class _InputIterator>
1174__enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>
1175forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
1176{
1177  __assign_with_sentinel(__f, __l);
1178}
1179
1180template <class _Tp, class _Alloc>
1181template <class _Iter, class _Sent>
1182_LIBCPP_HIDE_FROM_ABI
1183void 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
1195template <class _Tp, class _Alloc>
1196void
1197forward_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
1212template <class _Tp, class _Alloc>
1213inline
1214void
1215forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
1216{
1217    assign(__il.begin(), __il.end());
1218}
1219
1220template <class _Tp, class _Alloc>
1221template <class... _Args>
1222#if _LIBCPP_STD_VER >= 17
1223typename forward_list<_Tp, _Alloc>::reference
1224#else
1225void
1226#endif
1227forward_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
1241template <class _Tp, class _Alloc>
1242void
1243forward_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
1255template <class _Tp, class _Alloc>
1256void
1257forward_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
1267template <class _Tp, class _Alloc>
1268void
1269forward_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
1280template <class _Tp, class _Alloc>
1281template <class... _Args>
1282typename forward_list<_Tp, _Alloc>::iterator
1283forward_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
1296template <class _Tp, class _Alloc>
1297typename forward_list<_Tp, _Alloc>::iterator
1298forward_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
1312template <class _Tp, class _Alloc>
1313typename forward_list<_Tp, _Alloc>::iterator
1314forward_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
1326template <class _Tp, class _Alloc>
1327typename forward_list<_Tp, _Alloc>::iterator
1328forward_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
1378template <class _Tp, class _Alloc>
1379template <class _InputIterator>
1380__enable_if_t<__has_input_iterator_category<_InputIterator>::value, typename forward_list<_Tp, _Alloc>::iterator>
1381forward_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
1387template <class _Tp, class _Alloc>
1388template <class _InputIterator, class _Sentinel>
1389_LIBCPP_HIDE_FROM_ABI
1390typename forward_list<_Tp, _Alloc>::iterator
1391forward_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
1441template <class _Tp, class _Alloc>
1442typename forward_list<_Tp, _Alloc>::iterator
1443forward_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
1454template <class _Tp, class _Alloc>
1455typename forward_list<_Tp, _Alloc>::iterator
1456forward_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
1480template <class _Tp, class _Alloc>
1481void
1482forward_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
1512template <class _Tp, class _Alloc>
1513void
1514forward_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
1544template <class _Tp, class _Alloc>
1545void
1546forward_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
1563template <class _Tp, class _Alloc>
1564void
1565forward_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
1578template <class _Tp, class _Alloc>
1579void
1580forward_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
1598template <class _Tp, class _Alloc>
1599inline _LIBCPP_INLINE_VISIBILITY
1600void
1601forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
1602                                        forward_list&& __x)
1603{
1604    splice_after(__p, __x);
1605}
1606
1607template <class _Tp, class _Alloc>
1608inline _LIBCPP_INLINE_VISIBILITY
1609void
1610forward_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
1617template <class _Tp, class _Alloc>
1618inline _LIBCPP_INLINE_VISIBILITY
1619void
1620forward_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
1627template <class _Tp, class _Alloc>
1628typename forward_list<_Tp, _Alloc>::__remove_return_type
1629forward_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
1654template <class _Tp, class _Alloc>
1655template <class _Predicate>
1656typename forward_list<_Tp, _Alloc>::__remove_return_type
1657forward_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
1682template <class _Tp, class _Alloc>
1683template <class _BinaryPredicate>
1684typename forward_list<_Tp, _Alloc>::__remove_return_type
1685forward_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
1702template <class _Tp, class _Alloc>
1703template <class _Compare>
1704void
1705forward_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
1716template <class _Tp, class _Alloc>
1717template <class _Compare>
1718typename forward_list<_Tp, _Alloc>::__node_pointer
1719forward_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
1761template <class _Tp, class _Alloc>
1762template <class _Compare>
1763inline
1764void
1765forward_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
1771template <class _Tp, class _Alloc>
1772template <class _Compare>
1773typename forward_list<_Tp, _Alloc>::__node_pointer
1774forward_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
1801template <class _Tp, class _Alloc>
1802void
1803forward_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
1821template <class _Tp, class _Alloc>
1822_LIBCPP_HIDE_FROM_ABI
1823bool 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
1840template <class _Tp, class _Alloc>
1841inline _LIBCPP_INLINE_VISIBILITY
1842bool operator!=(const forward_list<_Tp, _Alloc>& __x,
1843                const forward_list<_Tp, _Alloc>& __y)
1844{
1845    return !(__x == __y);
1846}
1847
1848template <class _Tp, class _Alloc>
1849inline _LIBCPP_INLINE_VISIBILITY
1850bool 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
1857template <class _Tp, class _Alloc>
1858inline _LIBCPP_INLINE_VISIBILITY
1859bool operator> (const forward_list<_Tp, _Alloc>& __x,
1860                const forward_list<_Tp, _Alloc>& __y)
1861{
1862    return __y < __x;
1863}
1864
1865template <class _Tp, class _Alloc>
1866inline _LIBCPP_INLINE_VISIBILITY
1867bool operator>=(const forward_list<_Tp, _Alloc>& __x,
1868                const forward_list<_Tp, _Alloc>& __y)
1869{
1870    return !(__x < __y);
1871}
1872
1873template <class _Tp, class _Alloc>
1874inline _LIBCPP_INLINE_VISIBILITY
1875bool 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
1883template <class _Tp, class _Allocator>
1884_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp>
1885operator<=>(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
1892template <class _Tp, class _Alloc>
1893inline _LIBCPP_INLINE_VISIBILITY
1894void
1895swap(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
1902template <class _Tp, class _Allocator, class _Predicate>
1903inline _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
1909template <class _Tp, class _Allocator, class _Up>
1910inline _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
1921namespace pmr {
1922template <class _ValueT>
1923using 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
1943