xref: /openbsd-src/gnu/llvm/libcxx/include/forward_list (revision 4bdff4bed0e3d54e55670334c7d0077db4170f86)

// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_FORWARD_LIST
#define _LIBCPP_FORWARD_LIST

/*
    forward_list synopsis

namespace std
{

template <class T, class Allocator = allocator<T>>
class forward_list
{
public:
    typedef T         value_type;
    typedef Allocator allocator_type;

    typedef value_type&                                                reference;
    typedef const value_type&                                          const_reference;
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;

    typedef <details> iterator;
    typedef <details> const_iterator;

    forward_list()
        noexcept(is_nothrow_default_constructible<allocator_type>::value);
    explicit forward_list(const allocator_type& a);
    explicit forward_list(size_type n);
    explicit forward_list(size_type n, const allocator_type& a); // C++14
    forward_list(size_type n, const value_type& v);
    forward_list(size_type n, const value_type& v, const allocator_type& a);
    template <class InputIterator>
        forward_list(InputIterator first, InputIterator last);
    template <class InputIterator>
        forward_list(InputIterator first, InputIterator last, const allocator_type& a);
    forward_list(const forward_list& x);
    forward_list(const forward_list& x, const allocator_type& a);
    forward_list(forward_list&& x)
        noexcept(is_nothrow_move_constructible<allocator_type>::value);
    forward_list(forward_list&& x, const allocator_type& a);
    forward_list(initializer_list<value_type> il);
    forward_list(initializer_list<value_type> il, const allocator_type& a);

    ~forward_list();

    forward_list& operator=(const forward_list& x);
    forward_list& operator=(forward_list&& x)
        noexcept(
             allocator_type::propagate_on_container_move_assignment::value &&
             is_nothrow_move_assignable<allocator_type>::value);
    forward_list& operator=(initializer_list<value_type> il);

    template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const value_type& v);
    void assign(initializer_list<value_type> il);

    allocator_type get_allocator() const noexcept;

    iterator       begin() noexcept;
    const_iterator begin() const noexcept;
    iterator       end() noexcept;
    const_iterator end() const noexcept;

    const_iterator cbegin() const noexcept;
    const_iterator cend() const noexcept;

    iterator       before_begin() noexcept;
    const_iterator before_begin() const noexcept;
    const_iterator cbefore_begin() const noexcept;

    bool empty() const noexcept;
    size_type max_size() const noexcept;

    reference       front();
    const_reference front() const;

    template <class... Args> reference emplace_front(Args&&... args);  // reference in C++17
    void push_front(const value_type& v);
    void push_front(value_type&& v);

    void pop_front();

    template <class... Args>
        iterator emplace_after(const_iterator p, Args&&... args);
    iterator insert_after(const_iterator p, const value_type& v);
    iterator insert_after(const_iterator p, value_type&& v);
    iterator insert_after(const_iterator p, size_type n, const value_type& v);
    template <class InputIterator>
        iterator insert_after(const_iterator p,
                              InputIterator first, InputIterator last);
    iterator insert_after(const_iterator p, initializer_list<value_type> il);

    iterator erase_after(const_iterator p);
    iterator erase_after(const_iterator first, const_iterator last);

    void swap(forward_list& x)
        noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17

    void resize(size_type n);
    void resize(size_type n, const value_type& v);
    void clear() noexcept;

    void splice_after(const_iterator p, forward_list& x);
    void splice_after(const_iterator p, forward_list&& x);
    void splice_after(const_iterator p, forward_list& x, const_iterator i);
    void splice_after(const_iterator p, forward_list&& x, const_iterator i);
    void splice_after(const_iterator p, forward_list& x,
                      const_iterator first, const_iterator last);
    void splice_after(const_iterator p, forward_list&& x,
                      const_iterator first, const_iterator last);
    size_type remove(const value_type& v);           // void before C++20
    template <class Predicate>
      size_type remove_if(Predicate pred);           // void before C++20
    size_type unique();                              // void before C++20
    template <class BinaryPredicate>
      size_type unique(BinaryPredicate binary_pred); // void before C++20
    void merge(forward_list& x);
    void merge(forward_list&& x);
    template <class Compare> void merge(forward_list& x, Compare comp);
    template <class Compare> void merge(forward_list&& x, Compare comp);
    void sort();
    template <class Compare> void sort(Compare comp);
    void reverse() noexcept;
};


template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
    forward_list(InputIterator, InputIterator, Allocator = Allocator())
    -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;  // C++17

template <class T, class Allocator>
    bool operator==(const forward_list<T, Allocator>& x,
                    const forward_list<T, Allocator>& y);

template <class T, class Allocator>
    bool operator< (const forward_list<T, Allocator>& x,
                    const forward_list<T, Allocator>& y);

template <class T, class Allocator>
    bool operator!=(const forward_list<T, Allocator>& x,
                    const forward_list<T, Allocator>& y);

template <class T, class Allocator>
    bool operator> (const forward_list<T, Allocator>& x,
                    const forward_list<T, Allocator>& y);

template <class T, class Allocator>
    bool operator>=(const forward_list<T, Allocator>& x,
                    const forward_list<T, Allocator>& y);

template <class T, class Allocator>
    bool operator<=(const forward_list<T, Allocator>& x,
                    const forward_list<T, Allocator>& y);

template <class T, class Allocator>
    void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
         noexcept(noexcept(x.swap(y)));

template <class T, class Allocator, class U>
    typename forward_list<T, Allocator>::size_type
    erase(forward_list<T, Allocator>& c, const U& value);       // C++20
template <class T, class Allocator, class Predicate>
    typename forward_list<T, Allocator>::size_type
    erase_if(forward_list<T, Allocator>& c, Predicate pred);    // C++20

}  // std

*/

#include <__algorithm/comp.h>
#include <__algorithm/lexicographical_compare.h>
#include <__algorithm/min.h>
#include <__assert> // all public C++ headers provide the assertion handler
#include <__config>
#include <__iterator/distance.h>
#include <__iterator/iterator_traits.h>
#include <__iterator/move_iterator.h>
#include <__iterator/next.h>
#include <__memory/addressof.h>
#include <__memory/allocator.h>
#include <__memory/allocator_destructor.h>
#include <__memory/allocator_traits.h>
#include <__memory/compressed_pair.h>
#include <__memory/pointer_traits.h>
#include <__memory/swap_allocator.h>
#include <__memory/unique_ptr.h>
#include <__memory_resource/polymorphic_allocator.h>
#include <__type_traits/is_allocator.h>
#include <__utility/forward.h>
#include <__utility/move.h>
#include <limits>
#include <type_traits>
#include <version>

// standard-mandated includes

// [iterator.range]
#include <__iterator/access.h>
#include <__iterator/data.h>
#include <__iterator/empty.h>
#include <__iterator/reverse_access.h>
#include <__iterator/size.h>

// [forward.list.syn]
#include <compare>
#include <initializer_list>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_PUSH_MACROS
#include <__undef_macros>


_LIBCPP_BEGIN_NAMESPACE_STD

template <class _Tp, class _VoidPtr> struct __forward_list_node;
template <class _NodePtr> struct __forward_begin_node;


template <class>
struct __forward_list_node_value_type;

template <class _Tp, class _VoidPtr>
struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
  typedef _Tp type;
};

template <class _NodePtr>
struct __forward_node_traits {

  typedef __remove_cv_t<
        typename pointer_traits<_NodePtr>::element_type>        __node;
  typedef typename __forward_list_node_value_type<__node>::type __node_value_type;
  typedef _NodePtr                                              __node_pointer;
  typedef __forward_begin_node<_NodePtr>                        __begin_node;
  typedef __rebind_pointer_t<_NodePtr, __begin_node>            __begin_node_pointer;
  typedef __rebind_pointer_t<_NodePtr, void>                    __void_pointer;

#if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
  typedef __begin_node_pointer __iter_node_pointer;
#else
  typedef __conditional_t<is_pointer<__void_pointer>::value, __begin_node_pointer, __node_pointer>
      __iter_node_pointer;
#endif

  typedef __conditional_t<is_same<__iter_node_pointer, __node_pointer>::value, __begin_node_pointer, __node_pointer>
      __non_iter_node_pointer;

  _LIBCPP_INLINE_VISIBILITY
  static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) {
      return __p;
  }
  _LIBCPP_INLINE_VISIBILITY
  static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
      return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
  }
};

template <class _NodePtr>
struct __forward_begin_node
{
    typedef _NodePtr pointer;
    typedef __rebind_pointer_t<_NodePtr, __forward_begin_node> __begin_node_pointer;

    pointer __next_;

    _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}

    _LIBCPP_INLINE_VISIBILITY
    __begin_node_pointer __next_as_begin() const {
        return static_cast<__begin_node_pointer>(__next_);
    }
};

template <class _Tp, class _VoidPtr>
using __begin_node_of = __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >;

template <class _Tp, class _VoidPtr>
struct _LIBCPP_STANDALONE_DEBUG __forward_list_node
    : public __begin_node_of<_Tp, _VoidPtr>
{
    typedef _Tp value_type;

    value_type __value_;
};


template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list;
template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;

template <class _NodePtr>
class _LIBCPP_TEMPLATE_VIS __forward_list_iterator
{
    typedef __forward_node_traits<_NodePtr>         __traits;
    typedef typename __traits::__node_pointer       __node_pointer;
    typedef typename __traits::__begin_node_pointer __begin_node_pointer;
    typedef typename __traits::__iter_node_pointer  __iter_node_pointer;
    typedef typename __traits::__void_pointer       __void_pointer;

    __iter_node_pointer __ptr_;

    _LIBCPP_INLINE_VISIBILITY
    __begin_node_pointer __get_begin() const {
        return static_cast<__begin_node_pointer>(
                static_cast<__void_pointer>(__ptr_));
    }
    _LIBCPP_INLINE_VISIBILITY
    __node_pointer __get_unsafe_node_pointer() const {
        return static_cast<__node_pointer>(
                static_cast<__void_pointer>(__ptr_));
    }

    _LIBCPP_INLINE_VISIBILITY
    explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}

    _LIBCPP_INLINE_VISIBILITY
    explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
        : __ptr_(__traits::__as_iter_node(__p)) {}

    _LIBCPP_INLINE_VISIBILITY
    explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
        : __ptr_(__traits::__as_iter_node(__p)) {}

    template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list;
    template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;

public:
    typedef forward_iterator_tag                              iterator_category;
    typedef typename __traits::__node_value_type              value_type;
    typedef value_type&                                       reference;
    typedef typename pointer_traits<__node_pointer>::difference_type
                                                              difference_type;
    typedef __rebind_pointer_t<__node_pointer, value_type> pointer;

    _LIBCPP_INLINE_VISIBILITY
    __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}

    _LIBCPP_INLINE_VISIBILITY
    reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
    _LIBCPP_INLINE_VISIBILITY
    pointer operator->() const {
        return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_);
    }

    _LIBCPP_INLINE_VISIBILITY
    __forward_list_iterator& operator++()
    {
        __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
        return *this;
    }
    _LIBCPP_INLINE_VISIBILITY
    __forward_list_iterator operator++(int)
    {
        __forward_list_iterator __t(*this);
        ++(*this);
        return __t;
    }

    friend _LIBCPP_INLINE_VISIBILITY
    bool operator==(const __forward_list_iterator& __x,
                    const __forward_list_iterator& __y)
        {return __x.__ptr_ == __y.__ptr_;}
    friend _LIBCPP_INLINE_VISIBILITY
    bool operator!=(const __forward_list_iterator& __x,
                    const __forward_list_iterator& __y)
        {return !(__x == __y);}
};

template <class _NodeConstPtr>
class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator
{
    static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), "");
    typedef _NodeConstPtr _NodePtr;

    typedef __forward_node_traits<_NodePtr>         __traits;
    typedef typename __traits::__node               __node;
    typedef typename __traits::__node_pointer       __node_pointer;
    typedef typename __traits::__begin_node_pointer __begin_node_pointer;
    typedef typename __traits::__iter_node_pointer  __iter_node_pointer;
    typedef typename __traits::__void_pointer       __void_pointer;

    __iter_node_pointer __ptr_;

    __begin_node_pointer __get_begin() const {
        return static_cast<__begin_node_pointer>(
                static_cast<__void_pointer>(__ptr_));
    }
    __node_pointer __get_unsafe_node_pointer() const {
        return static_cast<__node_pointer>(
                static_cast<__void_pointer>(__ptr_));
    }

    _LIBCPP_INLINE_VISIBILITY
    explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT
        : __ptr_(nullptr) {}

    _LIBCPP_INLINE_VISIBILITY
    explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
        : __ptr_(__traits::__as_iter_node(__p)) {}

    _LIBCPP_INLINE_VISIBILITY
    explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
        : __ptr_(__traits::__as_iter_node(__p)) {}


    template<class, class> friend class forward_list;

public:
    typedef forward_iterator_tag                              iterator_category;
    typedef typename __traits::__node_value_type              value_type;
    typedef const value_type&                                 reference;
    typedef typename pointer_traits<__node_pointer>::difference_type
                                                              difference_type;
    typedef __rebind_pointer_t<__node_pointer, const value_type>
                                                              pointer;

    _LIBCPP_INLINE_VISIBILITY
    __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
    _LIBCPP_INLINE_VISIBILITY
    __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
        : __ptr_(__p.__ptr_) {}

    _LIBCPP_INLINE_VISIBILITY
    reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
    _LIBCPP_INLINE_VISIBILITY
    pointer operator->() const {return pointer_traits<pointer>::pointer_to(
                __get_unsafe_node_pointer()->__value_);}

    _LIBCPP_INLINE_VISIBILITY
    __forward_list_const_iterator& operator++()
    {
        __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
        return *this;
    }
    _LIBCPP_INLINE_VISIBILITY
    __forward_list_const_iterator operator++(int)
    {
        __forward_list_const_iterator __t(*this);
        ++(*this);
        return __t;
    }

    friend _LIBCPP_INLINE_VISIBILITY
    bool operator==(const __forward_list_const_iterator& __x,
                    const __forward_list_const_iterator& __y)
        {return __x.__ptr_ == __y.__ptr_;}
    friend _LIBCPP_INLINE_VISIBILITY
    bool operator!=(const __forward_list_const_iterator& __x,
                           const __forward_list_const_iterator& __y)
        {return !(__x == __y);}
};

template <class _Tp, class _Alloc>
class __forward_list_base
{
protected:
    typedef _Tp    value_type;
    typedef _Alloc allocator_type;

    typedef typename allocator_traits<allocator_type>::void_pointer  void_pointer;
    typedef __forward_list_node<value_type, void_pointer>            __node;
    typedef __begin_node_of<value_type, void_pointer>                __begin_node;
    typedef __rebind_alloc<allocator_traits<allocator_type>, __node> __node_allocator;
    typedef allocator_traits<__node_allocator>        __node_traits;
    typedef typename __node_traits::pointer           __node_pointer;

    typedef __rebind_alloc<allocator_traits<allocator_type>, __begin_node> __begin_node_allocator;
    typedef typename allocator_traits<__begin_node_allocator>::pointer
                                                      __begin_node_pointer;

    static_assert((!is_same<allocator_type, __node_allocator>::value),
                  "internal allocator type must differ from user-specified "
                  "type; otherwise overload resolution breaks");

    static_assert(is_same<allocator_type, __rebind_alloc<__node_traits, value_type> >::value,
                  "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
                  "original allocator");

    __compressed_pair<__begin_node, __node_allocator> __before_begin_;

    _LIBCPP_INLINE_VISIBILITY
    __begin_node_pointer        __before_begin() _NOEXCEPT
        {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());}
    _LIBCPP_INLINE_VISIBILITY
    __begin_node_pointer __before_begin() const _NOEXCEPT
        {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));}

    _LIBCPP_INLINE_VISIBILITY
          __node_allocator& __alloc() _NOEXCEPT
            {return __before_begin_.second();}
    _LIBCPP_INLINE_VISIBILITY
    const __node_allocator& __alloc() const _NOEXCEPT
        {return __before_begin_.second();}

    typedef __forward_list_iterator<__node_pointer>             iterator;
    typedef __forward_list_const_iterator<__node_pointer>       const_iterator;

    _LIBCPP_INLINE_VISIBILITY
    __forward_list_base()
        _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
        : __before_begin_(__begin_node(), __default_init_tag()) {}
    _LIBCPP_INLINE_VISIBILITY
    explicit __forward_list_base(const allocator_type& __a)
        : __before_begin_(__begin_node(), __node_allocator(__a)) {}
    _LIBCPP_INLINE_VISIBILITY
    explicit __forward_list_base(const __node_allocator& __a)
        : __before_begin_(__begin_node(), __a) {}
#ifndef _LIBCPP_CXX03_LANG
public:
    _LIBCPP_INLINE_VISIBILITY
    __forward_list_base(__forward_list_base&& __x)
        _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
    _LIBCPP_INLINE_VISIBILITY
    __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
#endif // _LIBCPP_CXX03_LANG

private:
    __forward_list_base(const __forward_list_base&);
    __forward_list_base& operator=(const __forward_list_base&);

public:
    ~__forward_list_base();

protected:
    _LIBCPP_INLINE_VISIBILITY
    void __copy_assign_alloc(const __forward_list_base& __x)
        {__copy_assign_alloc(__x, integral_constant<bool,
              __node_traits::propagate_on_container_copy_assignment::value>());}

    _LIBCPP_INLINE_VISIBILITY
    void __move_assign_alloc(__forward_list_base& __x)
        _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
                   is_nothrow_move_assignable<__node_allocator>::value)
        {__move_assign_alloc(__x, integral_constant<bool,
              __node_traits::propagate_on_container_move_assignment::value>());}

public:
    _LIBCPP_INLINE_VISIBILITY
    void swap(__forward_list_base& __x)
#if _LIBCPP_STD_VER >= 14
        _NOEXCEPT;
#else
        _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
                    __is_nothrow_swappable<__node_allocator>::value);
#endif
protected:
    void clear() _NOEXCEPT;

private:
    _LIBCPP_INLINE_VISIBILITY
    void __copy_assign_alloc(const __forward_list_base&, false_type) {}
    _LIBCPP_INLINE_VISIBILITY
    void __copy_assign_alloc(const __forward_list_base& __x, true_type)
    {
        if (__alloc() != __x.__alloc())
            clear();
        __alloc() = __x.__alloc();
    }

    _LIBCPP_INLINE_VISIBILITY
    void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT
        {}
    _LIBCPP_INLINE_VISIBILITY
    void __move_assign_alloc(__forward_list_base& __x, true_type)
        _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
        {__alloc() = _VSTD::move(__x.__alloc());}
};

#ifndef _LIBCPP_CXX03_LANG

template <class _Tp, class _Alloc>
inline
__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
        _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
    : __before_begin_(_VSTD::move(__x.__before_begin_))
{
    __x.__before_begin()->__next_ = nullptr;
}

template <class _Tp, class _Alloc>
inline
__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
                                                      const allocator_type& __a)
    : __before_begin_(__begin_node(), __node_allocator(__a))
{
    if (__alloc() == __x.__alloc())
    {
        __before_begin()->__next_ = __x.__before_begin()->__next_;
        __x.__before_begin()->__next_ = nullptr;
    }
}

#endif // _LIBCPP_CXX03_LANG

template <class _Tp, class _Alloc>
__forward_list_base<_Tp, _Alloc>::~__forward_list_base()
{
    clear();
}

template <class _Tp, class _Alloc>
inline
void
__forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
#if _LIBCPP_STD_VER >= 14
        _NOEXCEPT
#else
        _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
                    __is_nothrow_swappable<__node_allocator>::value)
#endif
{
    _VSTD::__swap_allocator(__alloc(), __x.__alloc(),
            integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
    using _VSTD::swap;
    swap(__before_begin()->__next_, __x.__before_begin()->__next_);
}

template <class _Tp, class _Alloc>
void
__forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
{
    __node_allocator& __a = __alloc();
    for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
    {
        __node_pointer __next = __p->__next_;
        __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
        __node_traits::deallocate(__a, __p, 1);
        __p = __next;
    }
    __before_begin()->__next_ = nullptr;
}

template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
class _LIBCPP_TEMPLATE_VIS forward_list
    : private __forward_list_base<_Tp, _Alloc>
{
    typedef __forward_list_base<_Tp, _Alloc> base;
    typedef typename base::__node_allocator  __node_allocator;
    typedef typename base::__node               __node;
    typedef typename base::__node_traits        __node_traits;
    typedef typename base::__node_pointer       __node_pointer;
    typedef typename base::__begin_node_pointer __begin_node_pointer;

public:
    typedef _Tp    value_type;
    typedef _Alloc allocator_type;

    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
                  "Allocator::value_type must be same type as value_type");

    typedef value_type&                                                 reference;
    typedef const value_type&                                           const_reference;
    typedef typename allocator_traits<allocator_type>::pointer          pointer;
    typedef typename allocator_traits<allocator_type>::const_pointer    const_pointer;
    typedef typename allocator_traits<allocator_type>::size_type        size_type;
    typedef typename allocator_traits<allocator_type>::difference_type  difference_type;

    typedef typename base::iterator       iterator;
    typedef typename base::const_iterator const_iterator;
#if _LIBCPP_STD_VER > 17
    typedef size_type                                __remove_return_type;
#else
    typedef void                                     __remove_return_type;
#endif

    _LIBCPP_INLINE_VISIBILITY
    forward_list()
        _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
        {} // = default;
    _LIBCPP_INLINE_VISIBILITY
    explicit forward_list(const allocator_type& __a);
    explicit forward_list(size_type __n);
#if _LIBCPP_STD_VER > 11
    explicit forward_list(size_type __n, const allocator_type& __a);
#endif
    forward_list(size_type __n, const value_type& __v);

    template <class = __enable_if_t<__is_allocator<_Alloc>::value> >
    forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : base(__a)
    {
        insert_after(cbefore_begin(), __n, __v);
    }

    template <class _InputIterator>
        forward_list(_InputIterator __f, _InputIterator __l,
                     __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>* = nullptr);
    template <class _InputIterator>
        forward_list(_InputIterator __f, _InputIterator __l,
                     const allocator_type& __a,
                     __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>* = nullptr);
    forward_list(const forward_list& __x);
    forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);

    forward_list& operator=(const forward_list& __x);

#ifndef _LIBCPP_CXX03_LANG
    _LIBCPP_INLINE_VISIBILITY
    forward_list(forward_list&& __x)
        _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
        : base(_VSTD::move(__x)) {}
    forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a);

    forward_list(initializer_list<value_type> __il);
    forward_list(initializer_list<value_type> __il, const allocator_type& __a);

    _LIBCPP_INLINE_VISIBILITY
    forward_list& operator=(forward_list&& __x)
        _NOEXCEPT_(
             __node_traits::propagate_on_container_move_assignment::value &&
             is_nothrow_move_assignable<allocator_type>::value);

    _LIBCPP_INLINE_VISIBILITY
    forward_list& operator=(initializer_list<value_type> __il);

    _LIBCPP_INLINE_VISIBILITY
    void assign(initializer_list<value_type> __il);
#endif // _LIBCPP_CXX03_LANG

    // ~forward_list() = default;

    template <class _InputIterator>
    __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>
        assign(_InputIterator __f, _InputIterator __l);
    void assign(size_type __n, const value_type& __v);

    _LIBCPP_INLINE_VISIBILITY
    allocator_type get_allocator() const _NOEXCEPT
        {return allocator_type(base::__alloc());}

    _LIBCPP_INLINE_VISIBILITY
    iterator       begin() _NOEXCEPT
        {return       iterator(base::__before_begin()->__next_);}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator begin() const _NOEXCEPT
        {return const_iterator(base::__before_begin()->__next_);}
    _LIBCPP_INLINE_VISIBILITY
    iterator       end() _NOEXCEPT
        {return       iterator(nullptr);}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator end() const _NOEXCEPT
        {return const_iterator(nullptr);}

    _LIBCPP_INLINE_VISIBILITY
    const_iterator cbegin() const _NOEXCEPT
        {return const_iterator(base::__before_begin()->__next_);}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator cend() const _NOEXCEPT
        {return const_iterator(nullptr);}

    _LIBCPP_INLINE_VISIBILITY
    iterator       before_begin() _NOEXCEPT
        {return       iterator(base::__before_begin());}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator before_begin() const _NOEXCEPT
        {return const_iterator(base::__before_begin());}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator cbefore_begin() const _NOEXCEPT
        {return const_iterator(base::__before_begin());}

    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
    bool empty() const _NOEXCEPT
        {return base::__before_begin()->__next_ == nullptr;}
    _LIBCPP_INLINE_VISIBILITY
    size_type max_size() const _NOEXCEPT {
        return _VSTD::min<size_type>(
            __node_traits::max_size(base::__alloc()),
            numeric_limits<difference_type>::max());
    }

    _LIBCPP_INLINE_VISIBILITY
    reference       front()       {return base::__before_begin()->__next_->__value_;}
    _LIBCPP_INLINE_VISIBILITY
    const_reference front() const {return base::__before_begin()->__next_->__value_;}

#ifndef _LIBCPP_CXX03_LANG
#if _LIBCPP_STD_VER > 14
    template <class... _Args> reference emplace_front(_Args&&... __args);
#else
    template <class... _Args> void      emplace_front(_Args&&... __args);
#endif
    void push_front(value_type&& __v);
#endif // _LIBCPP_CXX03_LANG
    void push_front(const value_type& __v);

    void pop_front();

#ifndef _LIBCPP_CXX03_LANG
    template <class... _Args>
        iterator emplace_after(const_iterator __p, _Args&&... __args);

    iterator insert_after(const_iterator __p, value_type&& __v);
    iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
        {return insert_after(__p, __il.begin(), __il.end());}
#endif // _LIBCPP_CXX03_LANG
    iterator insert_after(const_iterator __p, const value_type& __v);
    iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
    template <class _InputIterator>
    _LIBCPP_INLINE_VISIBILITY
    __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, iterator>
        insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);

    iterator erase_after(const_iterator __p);
    iterator erase_after(const_iterator __f, const_iterator __l);

    _LIBCPP_INLINE_VISIBILITY
    void swap(forward_list& __x)
#if _LIBCPP_STD_VER >= 14
        _NOEXCEPT
#else
        _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
                   __is_nothrow_swappable<__node_allocator>::value)
#endif
        {base::swap(__x);}

    void resize(size_type __n);
    void resize(size_type __n, const value_type& __v);
    _LIBCPP_INLINE_VISIBILITY
    void clear() _NOEXCEPT {base::clear();}

    _LIBCPP_INLINE_VISIBILITY
    void splice_after(const_iterator __p, forward_list&& __x);
    _LIBCPP_INLINE_VISIBILITY
    void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
    _LIBCPP_INLINE_VISIBILITY
    void splice_after(const_iterator __p, forward_list&& __x,
                      const_iterator __f, const_iterator __l);
    void splice_after(const_iterator __p, forward_list& __x);
    void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
    void splice_after(const_iterator __p, forward_list& __x,
                      const_iterator __f, const_iterator __l);
    __remove_return_type remove(const value_type& __v);
    template <class _Predicate> __remove_return_type remove_if(_Predicate __pred);
    _LIBCPP_INLINE_VISIBILITY
    __remove_return_type unique() { return unique(__equal_to()); }
    template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred);
#ifndef _LIBCPP_CXX03_LANG
    _LIBCPP_INLINE_VISIBILITY
    void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
    template <class _Compare>
        _LIBCPP_INLINE_VISIBILITY
        void merge(forward_list&& __x, _Compare __comp)
        {merge(__x, _VSTD::move(__comp));}
#endif // _LIBCPP_CXX03_LANG
    _LIBCPP_INLINE_VISIBILITY
    void merge(forward_list& __x) {merge(__x, __less<value_type>());}
    template <class _Compare> void merge(forward_list& __x, _Compare __comp);
    _LIBCPP_INLINE_VISIBILITY
    void sort() {sort(__less<value_type>());}
    template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
    void reverse() _NOEXCEPT;

private:

#ifndef _LIBCPP_CXX03_LANG
    void __move_assign(forward_list& __x, true_type)
        _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
    void __move_assign(forward_list& __x, false_type);
#endif // _LIBCPP_CXX03_LANG

    template <class _Compare>
        static
        __node_pointer
        __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);

    template <class _Compare>
        static
        __node_pointer
        __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
};


#if _LIBCPP_STD_VER >= 17
template<class _InputIterator,
         class _Alloc = allocator<__iter_value_type<_InputIterator>>,
         class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
         class = enable_if_t<__is_allocator<_Alloc>::value>
         >
forward_list(_InputIterator, _InputIterator)
  -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;

template<class _InputIterator,
         class _Alloc,
         class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
         class = enable_if_t<__is_allocator<_Alloc>::value>
         >
forward_list(_InputIterator, _InputIterator, _Alloc)
  -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
#endif

template <class _Tp, class _Alloc>
inline
forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
    : base(__a)
{
}

template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>::forward_list(size_type __n)
{
    if (__n > 0)
    {
        __node_allocator& __a = base::__alloc();
        typedef __allocator_destructor<__node_allocator> _Dp;
        unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
        for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
                                                             __p = __p->__next_as_begin())
        {
            __h.reset(__node_traits::allocate(__a, 1));
            __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
            __h->__next_ = nullptr;
            __p->__next_ = __h.release();
        }
    }
}

#if _LIBCPP_STD_VER > 11
template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>::forward_list(size_type __n,
                                        const allocator_type& __base_alloc)
    : base ( __base_alloc )
{
    if (__n > 0)
    {
        __node_allocator& __a = base::__alloc();
        typedef __allocator_destructor<__node_allocator> _Dp;
        unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
        for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
                                                             __p = __p->__next_as_begin())
        {
            __h.reset(__node_traits::allocate(__a, 1));
            __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
            __h->__next_ = nullptr;
            __p->__next_ = __h.release();
        }
    }
}
#endif

template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
{
    insert_after(cbefore_begin(), __n, __v);
}

template <class _Tp, class _Alloc>
template <class _InputIterator>
forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
                                        __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>*)
{
    insert_after(cbefore_begin(), __f, __l);
}

template <class _Tp, class _Alloc>
template <class _InputIterator>
forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
                                        const allocator_type& __a,
                                        __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>*)
    : base(__a)
{
    insert_after(cbefore_begin(), __f, __l);
}

template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
    : base(
          __node_traits::select_on_container_copy_construction(__x.__alloc())) {
  insert_after(cbefore_begin(), __x.begin(), __x.end());
}

template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
                                        const __type_identity_t<allocator_type>& __a)
    : base(__a)
{
    insert_after(cbefore_begin(), __x.begin(), __x.end());
}

template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>&
forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
{
    if (this != _VSTD::addressof(__x))
    {
        base::__copy_assign_alloc(__x);
        assign(__x.begin(), __x.end());
    }
    return *this;
}

#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
                                        const __type_identity_t<allocator_type>& __a)
    : base(_VSTD::move(__x), __a)
{
    if (base::__alloc() != __x.__alloc())
    {
        typedef move_iterator<iterator> _Ip;
        insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
    }
}

template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
{
    insert_after(cbefore_begin(), __il.begin(), __il.end());
}

template <class _Tp, class _Alloc>
forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
                                        const allocator_type& __a)
    : base(__a)
{
    insert_after(cbefore_begin(), __il.begin(), __il.end());
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
    _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
{
    clear();
    base::__move_assign_alloc(__x);
    base::__before_begin()->__next_ = __x.__before_begin()->__next_;
    __x.__before_begin()->__next_ = nullptr;
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
{
    if (base::__alloc() == __x.__alloc())
        __move_assign(__x, true_type());
    else
    {
        typedef move_iterator<iterator> _Ip;
        assign(_Ip(__x.begin()), _Ip(__x.end()));
    }
}

template <class _Tp, class _Alloc>
inline
forward_list<_Tp, _Alloc>&
forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
    _NOEXCEPT_(
             __node_traits::propagate_on_container_move_assignment::value &&
             is_nothrow_move_assignable<allocator_type>::value)
{
    __move_assign(__x, integral_constant<bool,
          __node_traits::propagate_on_container_move_assignment::value>());
    return *this;
}

template <class _Tp, class _Alloc>
inline
forward_list<_Tp, _Alloc>&
forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
{
    assign(__il.begin(), __il.end());
    return *this;
}

#endif // _LIBCPP_CXX03_LANG

template <class _Tp, class _Alloc>
template <class _InputIterator>
__enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>
forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
{
    iterator __i = before_begin();
    iterator __j = _VSTD::next(__i);
    iterator __e = end();
    for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)
        *__j = *__f;
    if (__j == __e)
        insert_after(__i, __f, __l);
    else
        erase_after(__i, __e);
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
{
    iterator __i = before_begin();
    iterator __j = _VSTD::next(__i);
    iterator __e = end();
    for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
        *__j = __v;
    if (__j == __e)
        insert_after(__i, __n, __v);
    else
        erase_after(__i, __e);
}

#ifndef _LIBCPP_CXX03_LANG

template <class _Tp, class _Alloc>
inline
void
forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
{
    assign(__il.begin(), __il.end());
}

template <class _Tp, class _Alloc>
template <class... _Args>
#if _LIBCPP_STD_VER > 14
typename forward_list<_Tp, _Alloc>::reference
#else
void
#endif
forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
{
    __node_allocator& __a = base::__alloc();
    typedef __allocator_destructor<__node_allocator> _Dp;
    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
    __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
                                  _VSTD::forward<_Args>(__args)...);
    __h->__next_ = base::__before_begin()->__next_;
    base::__before_begin()->__next_ = __h.release();
#if _LIBCPP_STD_VER > 14
    return base::__before_begin()->__next_->__value_;
#endif
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
{
    __node_allocator& __a = base::__alloc();
    typedef __allocator_destructor<__node_allocator> _Dp;
    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
    __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
    __h->__next_ = base::__before_begin()->__next_;
    base::__before_begin()->__next_ = __h.release();
}

#endif // _LIBCPP_CXX03_LANG

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
{
    __node_allocator& __a = base::__alloc();
    typedef __allocator_destructor<__node_allocator> _Dp;
    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
    __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
    __h->__next_ = base::__before_begin()->__next_;
    base::__before_begin()->__next_ = __h.release();
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::pop_front()
{
    __node_allocator& __a = base::__alloc();
    __node_pointer __p = base::__before_begin()->__next_;
    base::__before_begin()->__next_ = __p->__next_;
    __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
    __node_traits::deallocate(__a, __p, 1);
}

#ifndef _LIBCPP_CXX03_LANG

template <class _Tp, class _Alloc>
template <class... _Args>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
{
    __begin_node_pointer const __r = __p.__get_begin();
    __node_allocator& __a = base::__alloc();
    typedef __allocator_destructor<__node_allocator> _Dp;
    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
    __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
                                  _VSTD::forward<_Args>(__args)...);
    __h->__next_ = __r->__next_;
    __r->__next_ = __h.release();
    return iterator(__r->__next_);
}

template <class _Tp, class _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
{
    __begin_node_pointer const __r = __p.__get_begin();
    __node_allocator& __a = base::__alloc();
    typedef __allocator_destructor<__node_allocator> _Dp;
    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
    __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
    __h->__next_ = __r->__next_;
    __r->__next_ = __h.release();
    return iterator(__r->__next_);
}

#endif // _LIBCPP_CXX03_LANG

template <class _Tp, class _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
{
    __begin_node_pointer const __r = __p.__get_begin();
    __node_allocator& __a = base::__alloc();
    typedef __allocator_destructor<__node_allocator> _Dp;
    unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
    __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
    __h->__next_ = __r->__next_;
    __r->__next_ = __h.release();
    return iterator(__r->__next_);
}

template <class _Tp, class _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
                                        const value_type& __v)
{
    __begin_node_pointer __r = __p.__get_begin();
    if (__n > 0)
    {
        __node_allocator& __a = base::__alloc();
        typedef __allocator_destructor<__node_allocator> _Dp;
        unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
        __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
        __node_pointer __first = __h.release();
        __node_pointer __last = __first;
#ifndef _LIBCPP_NO_EXCEPTIONS
        try
        {
#endif // _LIBCPP_NO_EXCEPTIONS
            for (--__n; __n != 0; --__n, __last = __last->__next_)
            {
                __h.reset(__node_traits::allocate(__a, 1));
                __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
                __last->__next_ = __h.release();
            }
#ifndef _LIBCPP_NO_EXCEPTIONS
        }
        catch (...)
        {
            while (__first != nullptr)
            {
                __node_pointer __next = __first->__next_;
                __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
                __node_traits::deallocate(__a, __first, 1);
                __first = __next;
            }
            throw;
        }
#endif // _LIBCPP_NO_EXCEPTIONS
        __last->__next_ = __r->__next_;
        __r->__next_ = __first;
        __r = static_cast<__begin_node_pointer>(__last);
    }
    return iterator(__r);
}

template <class _Tp, class _Alloc>
template <class _InputIterator>
__enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, typename forward_list<_Tp, _Alloc>::iterator>
forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
                                        _InputIterator __f, _InputIterator __l)
{
    __begin_node_pointer __r = __p.__get_begin();
    if (__f != __l)
    {
        __node_allocator& __a = base::__alloc();
        typedef __allocator_destructor<__node_allocator> _Dp;
        unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
        __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
        __node_pointer __first = __h.release();
        __node_pointer __last = __first;
#ifndef _LIBCPP_NO_EXCEPTIONS
        try
        {
#endif // _LIBCPP_NO_EXCEPTIONS
            for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
            {
                __h.reset(__node_traits::allocate(__a, 1));
                __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
                __last->__next_ = __h.release();
            }
#ifndef _LIBCPP_NO_EXCEPTIONS
        }
        catch (...)
        {
            while (__first != nullptr)
            {
                __node_pointer __next = __first->__next_;
                __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
                __node_traits::deallocate(__a, __first, 1);
                __first = __next;
            }
            throw;
        }
#endif // _LIBCPP_NO_EXCEPTIONS
        __last->__next_ = __r->__next_;
        __r->__next_ = __first;
        __r = static_cast<__begin_node_pointer>(__last);
    }
    return iterator(__r);
}

template <class _Tp, class _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
{
    __begin_node_pointer __p = __f.__get_begin();
    __node_pointer __n = __p->__next_;
    __p->__next_ = __n->__next_;
    __node_allocator& __a = base::__alloc();
    __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
    __node_traits::deallocate(__a, __n, 1);
    return iterator(__p->__next_);
}

template <class _Tp, class _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
{
    __node_pointer __e = __l.__get_unsafe_node_pointer();
    if (__f != __l)
    {
        __begin_node_pointer __bp = __f.__get_begin();

        __node_pointer __n = __bp->__next_;
        if (__n != __e)
        {
            __bp->__next_ = __e;
            __node_allocator& __a = base::__alloc();
            do
            {
                __node_pointer __tmp = __n->__next_;
                __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
                __node_traits::deallocate(__a, __n, 1);
                __n = __tmp;
            } while (__n != __e);
        }
    }
    return iterator(__e);
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::resize(size_type __n)
{
    size_type __sz = 0;
    iterator __p = before_begin();
    iterator __i = begin();
    iterator __e = end();
    for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
        ;
    if (__i != __e)
        erase_after(__p, __e);
    else
    {
        __n -= __sz;
        if (__n > 0)
        {
            __node_allocator& __a = base::__alloc();
            typedef __allocator_destructor<__node_allocator> _Dp;
            unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
            for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
                                                         __ptr = __ptr->__next_as_begin())
            {
                __h.reset(__node_traits::allocate(__a, 1));
                __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
                __h->__next_ = nullptr;
                __ptr->__next_ = __h.release();
            }
        }
    }
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
{
    size_type __sz = 0;
    iterator __p = before_begin();
    iterator __i = begin();
    iterator __e = end();
    for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
        ;
    if (__i != __e)
        erase_after(__p, __e);
    else
    {
        __n -= __sz;
        if (__n > 0)
        {
            __node_allocator& __a = base::__alloc();
            typedef __allocator_destructor<__node_allocator> _Dp;
            unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
            for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
                                                         __ptr = __ptr->__next_as_begin())
            {
                __h.reset(__node_traits::allocate(__a, 1));
                __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
                __h->__next_ = nullptr;
                __ptr->__next_ = __h.release();
            }
        }
    }
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
                                        forward_list& __x)
{
    if (!__x.empty())
    {
        if (__p.__get_begin()->__next_ != nullptr)
        {
            const_iterator __lm1 = __x.before_begin();
            while (__lm1.__get_begin()->__next_ != nullptr)
                ++__lm1;
            __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
        }
        __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
        __x.__before_begin()->__next_ = nullptr;
    }
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
                                        forward_list& /*__other*/,
                                        const_iterator __i)
{
    const_iterator __lm1 = _VSTD::next(__i);
    if (__p != __i && __p != __lm1)
    {
        __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
        __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
        __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
    }
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
                                        forward_list& /*__other*/,
                                        const_iterator __f, const_iterator __l)
{
    if (__f != __l && __p != __f)
    {
        const_iterator __lm1 = __f;
        while (__lm1.__get_begin()->__next_ != __l.__get_begin())
            ++__lm1;
        if (__f != __lm1)
        {
            __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
            __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
            __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
        }
    }
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
void
forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
                                        forward_list&& __x)
{
    splice_after(__p, __x);
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
void
forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
                                        forward_list&& __x,
                                        const_iterator __i)
{
    splice_after(__p, __x, __i);
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
void
forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
                                        forward_list&& __x,
                                        const_iterator __f, const_iterator __l)
{
    splice_after(__p, __x, __f, __l);
}

template <class _Tp, class _Alloc>
typename forward_list<_Tp, _Alloc>::__remove_return_type
forward_list<_Tp, _Alloc>::remove(const value_type& __v)
{
    forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
    typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
    const iterator __e = end();
    for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
    {
        if (__i.__get_begin()->__next_->__value_ == __v)
        {
            ++__count_removed;
            iterator __j = _VSTD::next(__i, 2);
            for (; __j != __e && *__j == __v; ++__j)
                ++__count_removed;
            __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
            if (__j == __e)
                break;
            __i = __j;
        }
        else
            ++__i;
    }

    return (__remove_return_type) __count_removed;
}

template <class _Tp, class _Alloc>
template <class _Predicate>
typename forward_list<_Tp, _Alloc>::__remove_return_type
forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
{
    forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
    typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
    const iterator __e = end();
    for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
    {
        if (__pred(__i.__get_begin()->__next_->__value_))
        {
            ++__count_removed;
            iterator __j = _VSTD::next(__i, 2);
            for (; __j != __e && __pred(*__j); ++__j)
                ++__count_removed;
            __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
            if (__j == __e)
                break;
            __i = __j;
        }
        else
            ++__i;
    }

    return (__remove_return_type) __count_removed;
}

template <class _Tp, class _Alloc>
template <class _BinaryPredicate>
typename forward_list<_Tp, _Alloc>::__remove_return_type
forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
{
    forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
    typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
    for (iterator __i = begin(), __e = end(); __i != __e;)
    {
        iterator __j = _VSTD::next(__i);
        for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
            ++__count_removed;
        if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
            __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
        __i = __j;
    }

    return (__remove_return_type) __count_removed;
}

template <class _Tp, class _Alloc>
template <class _Compare>
void
forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
{
    if (this != _VSTD::addressof(__x))
    {
        base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
                                                    __x.__before_begin()->__next_,
                                                    __comp);
        __x.__before_begin()->__next_ = nullptr;
    }
}

template <class _Tp, class _Alloc>
template <class _Compare>
typename forward_list<_Tp, _Alloc>::__node_pointer
forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
                                   _Compare& __comp)
{
    if (__f1 == nullptr)
        return __f2;
    if (__f2 == nullptr)
        return __f1;
    __node_pointer __r;
    if (__comp(__f2->__value_, __f1->__value_))
    {
        __node_pointer __t = __f2;
        while (__t->__next_ != nullptr &&
                             __comp(__t->__next_->__value_, __f1->__value_))
            __t = __t->__next_;
        __r = __f2;
        __f2 = __t->__next_;
        __t->__next_ = __f1;
    }
    else
        __r = __f1;
    __node_pointer __p = __f1;
    __f1 = __f1->__next_;
    while (__f1 != nullptr && __f2 != nullptr)
    {
        if (__comp(__f2->__value_, __f1->__value_))
        {
            __node_pointer __t = __f2;
            while (__t->__next_ != nullptr &&
                                 __comp(__t->__next_->__value_, __f1->__value_))
                __t = __t->__next_;
            __p->__next_ = __f2;
            __f2 = __t->__next_;
            __t->__next_ = __f1;
        }
        __p = __f1;
        __f1 = __f1->__next_;
    }
    if (__f2 != nullptr)
        __p->__next_ = __f2;
    return __r;
}

template <class _Tp, class _Alloc>
template <class _Compare>
inline
void
forward_list<_Tp, _Alloc>::sort(_Compare __comp)
{
    base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
                                       _VSTD::distance(begin(), end()), __comp);
}

template <class _Tp, class _Alloc>
template <class _Compare>
typename forward_list<_Tp, _Alloc>::__node_pointer
forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
                                  _Compare& __comp)
{
    switch (__sz)
    {
    case 0:
    case 1:
        return __f1;
    case 2:
        if (__comp(__f1->__next_->__value_, __f1->__value_))
        {
            __node_pointer __t = __f1->__next_;
            __t->__next_ = __f1;
            __f1->__next_ = nullptr;
            __f1 = __t;
        }
        return __f1;
    }
    difference_type __sz1 = __sz / 2;
    difference_type __sz2 = __sz - __sz1;
    __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
    __node_pointer __f2 = __t->__next_;
    __t->__next_ = nullptr;
    return __merge(__sort(__f1, __sz1, __comp),
                   __sort(__f2, __sz2, __comp), __comp);
}

template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
{
    __node_pointer __p = base::__before_begin()->__next_;
    if (__p != nullptr)
    {
        __node_pointer __f = __p->__next_;
        __p->__next_ = nullptr;
        while (__f != nullptr)
        {
            __node_pointer __t = __f->__next_;
            __f->__next_ = __p;
            __p = __f;
            __f = __t;
        }
        base::__before_begin()->__next_ = __p;
    }
}

template <class _Tp, class _Alloc>
_LIBCPP_HIDE_FROM_ABI
bool operator==(const forward_list<_Tp, _Alloc>& __x,
                const forward_list<_Tp, _Alloc>& __y)
{
    typedef forward_list<_Tp, _Alloc> _Cp;
    typedef typename _Cp::const_iterator _Ip;
    _Ip __ix = __x.begin();
    _Ip __ex = __x.end();
    _Ip __iy = __y.begin();
    _Ip __ey = __y.end();
    for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
        if (!(*__ix == *__iy))
            return false;
    return (__ix == __ex) == (__iy == __ey);
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
bool operator!=(const forward_list<_Tp, _Alloc>& __x,
                const forward_list<_Tp, _Alloc>& __y)
{
    return !(__x == __y);
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
bool operator< (const forward_list<_Tp, _Alloc>& __x,
                const forward_list<_Tp, _Alloc>& __y)
{
    return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
                                         __y.begin(), __y.end());
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
bool operator> (const forward_list<_Tp, _Alloc>& __x,
                const forward_list<_Tp, _Alloc>& __y)
{
    return __y < __x;
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
bool operator>=(const forward_list<_Tp, _Alloc>& __x,
                const forward_list<_Tp, _Alloc>& __y)
{
    return !(__x < __y);
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
bool operator<=(const forward_list<_Tp, _Alloc>& __x,
                const forward_list<_Tp, _Alloc>& __y)
{
    return !(__y < __x);
}

template <class _Tp, class _Alloc>
inline _LIBCPP_INLINE_VISIBILITY
void
swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
{
    __x.swap(__y);
}

#if _LIBCPP_STD_VER > 17
template <class _Tp, class _Allocator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
    typename forward_list<_Tp, _Allocator>::size_type
    erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) {
  return __c.remove_if(__pred);
}

template <class _Tp, class _Allocator, class _Up>
inline _LIBCPP_INLINE_VISIBILITY
    typename forward_list<_Tp, _Allocator>::size_type
    erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) {
  return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
}
#endif

_LIBCPP_END_NAMESPACE_STD

#if _LIBCPP_STD_VER > 14
_LIBCPP_BEGIN_NAMESPACE_STD
namespace pmr {
template <class _ValueT>
using forward_list = std::forward_list<_ValueT, polymorphic_allocator<_ValueT>>;
} // namespace pmr
_LIBCPP_END_NAMESPACE_STD
#endif

_LIBCPP_POP_MACROS

#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
#  include <algorithm>
#  include <atomic>
#  include <concepts>
#  include <functional>
#  include <iosfwd>
#  include <iterator>
#  include <typeinfo>
#endif

#endif // _LIBCPP_FORWARD_LIST