// -*- 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);
template<container-compatible-range<T> R>
forward_list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
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);
template<container-compatible-range<T> R>
void assign_range(R&& rg); // C++23
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);
template<container-compatible-range<T> R>
void prepend_range(R&& rg); // C++23
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);
template<container-compatible-range<T> R>
iterator insert_range_after(const_iterator position, R&& rg); // C++23
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<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
forward_list(from_range_t, R&&, Allocator = Allocator())
-> forward_list<ranges::range_value_t<R>, Allocator>; // C++23
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); // removed in C++20
template <class T, class Allocator>
bool operator!=(const forward_list<T, Allocator>& x,
const forward_list<T, Allocator>& y); // removed in C++20
template <class T, class Allocator>
bool operator> (const forward_list<T, Allocator>& x,
const forward_list<T, Allocator>& y); // removed in C++20
template <class T, class Allocator>
bool operator>=(const forward_list<T, Allocator>& x,
const forward_list<T, Allocator>& y); // removed in C++20
template <class T, class Allocator>
bool operator<=(const forward_list<T, Allocator>& x,
const forward_list<T, Allocator>& y); // removed in C++20
template<class T, class Allocator>
synth-three-way-result<T> operator<=>(const forward_list<T, Allocator>& x,
const forward_list<T, Allocator>& y); // since C++20
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/lexicographical_compare_three_way.h>
#include <__algorithm/min.h>
#include <__assert> // all public C++ headers provide the assertion handler
#include <__availability>
#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/allocation_guard.h>
#include <__memory/allocator.h>
#include <__memory/allocator_traits.h>
#include <__memory/compressed_pair.h>
#include <__memory/construct_at.h>
#include <__memory/pointer_traits.h>
#include <__memory/swap_allocator.h>
#include <__memory_resource/polymorphic_allocator.h>
#include <__ranges/access.h>
#include <__ranges/concepts.h>
#include <__ranges/container_compatible_range.h>
#include <__ranges/from_range.h>
#include <__type_traits/conditional.h>
#include <__type_traits/is_allocator.h>
#include <__type_traits/is_const.h>
#include <__type_traits/is_nothrow_default_constructible.h>
#include <__type_traits/is_nothrow_move_assignable.h>
#include <__type_traits/is_nothrow_move_constructible.h>
#include <__type_traits/is_pointer.h>
#include <__type_traits/is_same.h>
#include <__type_traits/type_identity.h>
#include <__utility/forward.h>
#include <__utility/move.h>
#include <limits>
#include <new> // __launder
#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_type;
typedef typename __forward_list_node_value_type<__node_type>::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 explicit __forward_begin_node(pointer __n) : __next_(__n) {}
_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 __forward_list_node
: public __begin_node_of<_Tp, _VoidPtr>
{
typedef _Tp value_type;
typedef __begin_node_of<_Tp, _VoidPtr> _Base;
typedef typename _Base::pointer _NodePtr;
// We allow starting the lifetime of nodes without initializing the value held by the node,
// since that is handled by the list itself in order to be allocator-aware.
#ifndef _LIBCPP_CXX03_LANG
private:
union {
_Tp __value_;
};
public:
_LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
#else
private:
_ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
public:
_LIBCPP_HIDE_FROM_ABI _Tp& __get_value() {
return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_));
}
#endif
_LIBCPP_HIDE_FROM_ABI explicit __forward_list_node(_NodePtr __next) : _Base(__next) {}
_LIBCPP_HIDE_FROM_ABI ~__forward_list_node() {}
};
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()->__get_value();}
_LIBCPP_INLINE_VISIBILITY
pointer operator->() const {
return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_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_type __node_type;
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_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {
return static_cast<__begin_node_pointer>(
static_cast<__void_pointer>(__ptr_));
}
_LIBCPP_HIDE_FROM_ABI __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()->__get_value();}
_LIBCPP_INLINE_VISIBILITY
pointer operator->() const {return pointer_traits<pointer>::pointer_to(
__get_unsafe_node_pointer()->__get_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_type;
typedef __begin_node_of<value_type, void_pointer> __begin_node;
typedef __rebind_alloc<allocator_traits<allocator_type>, __node_type> __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;
__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:
_LIBCPP_HIDE_FROM_ABI ~__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>());}
template <class ..._Args>
_LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__node_pointer __next, _Args&& ...__args) {
__node_allocator& __a = __alloc();
__allocation_guard<__node_allocator> __guard(__a, 1);
// Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
// held inside the node, since we need to use the allocator's construct() method for that.
//
// We don't use the allocator's construct() method to construct the node itself since the
// Cpp17FooInsertable named requirements don't require the allocator's construct() method
// to work on anything other than the value_type.
std::__construct_at(std::addressof(*__guard.__get()), __next);
// Now construct the value_type using the allocator's construct() method.
__node_traits::construct(__a, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
return __guard.__release_ptr();
}
template <class ..._Args>
_LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
// For the same reason as above, we use the allocator's destroy() method for the value_type,
// but not for the node itself.
__node_allocator& __a = __alloc();
__node_traits::destroy(__a, std::addressof(__node->__get_value()));
std::__destroy_at(std::addressof(*__node));
__node_traits::deallocate(__a, __node, 1);
}
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:
_LIBCPP_HIDE_FROM_ABI 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
{
for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
{
__node_pointer __next = __p->__next_;
__delete_node(__p);
__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_type __node_type;
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<value_type, typename allocator_type::value_type>::value,
"Allocator::value_type must be same type as value_type");
static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value,
"[allocator.requirements] states that rebinding an allocator to the same type should result in the "
"original allocator");
static_assert((!is_same<allocator_type, __node_allocator>::value),
"internal allocator type must differ from user-specified "
"type; otherwise overload resolution breaks");
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 >= 20
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);
_LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n);
#if _LIBCPP_STD_VER >= 14
_LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n, const allocator_type& __a);
#endif
_LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v);
template <class = __enable_if_t<__is_allocator<_Alloc>::value> >
_LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : base(__a)
{
insert_after(cbefore_begin(), __n, __v);
}
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l,
__enable_if_t<__has_input_iterator_category<_InputIterator>::value>* = nullptr);
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l,
const allocator_type& __a,
__enable_if_t<__has_input_iterator_category<_InputIterator>::value>* = nullptr);
#if _LIBCPP_STD_VER >= 23
template <_ContainerCompatibleRange<_Tp> _Range>
_LIBCPP_HIDE_FROM_ABI forward_list(from_range_t, _Range&& __range,
const allocator_type& __a = allocator_type()) : base(__a) {
prepend_range(std::forward<_Range>(__range));
}
#endif
_LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x);
_LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);
_LIBCPP_HIDE_FROM_ABI 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)) {}
_LIBCPP_HIDE_FROM_ABI forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a);
_LIBCPP_HIDE_FROM_ABI forward_list(initializer_list<value_type> __il);
_LIBCPP_HIDE_FROM_ABI 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<__has_input_iterator_category<_InputIterator>::value, int> = 0>
void
_LIBCPP_HIDE_FROM_ABI assign(_InputIterator __f, _InputIterator __l);
#if _LIBCPP_STD_VER >= 23
template <_ContainerCompatibleRange<_Tp> _Range>
_LIBCPP_HIDE_FROM_ABI
void assign_range(_Range&& __range) {
__assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
}
#endif
_LIBCPP_HIDE_FROM_ABI 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_->__get_value();}
_LIBCPP_INLINE_VISIBILITY
const_reference front() const {return base::__before_begin()->__next_->__get_value();}
#ifndef _LIBCPP_CXX03_LANG
#if _LIBCPP_STD_VER >= 17
template <class... _Args>
_LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
#else
template <class... _Args>
_LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
#endif
_LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v);
#endif // _LIBCPP_CXX03_LANG
_LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);
#if _LIBCPP_STD_VER >= 23
template <_ContainerCompatibleRange<_Tp> _Range>
_LIBCPP_HIDE_FROM_ABI
void prepend_range(_Range&& __range) {
insert_range_after(cbefore_begin(), std::forward<_Range>(__range));
}
#endif
_LIBCPP_HIDE_FROM_ABI void pop_front();
#ifndef _LIBCPP_CXX03_LANG
template <class... _Args>
_LIBCPP_HIDE_FROM_ABI iterator emplace_after(const_iterator __p, _Args&&... __args);
_LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, value_type&& __v);
_LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
{return insert_after(__p, __il.begin(), __il.end());}
#endif // _LIBCPP_CXX03_LANG
_LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, const value_type& __v);
_LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
_LIBCPP_INLINE_VISIBILITY
iterator
insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
#if _LIBCPP_STD_VER >= 23
template <_ContainerCompatibleRange<_Tp> _Range>
_LIBCPP_HIDE_FROM_ABI
iterator insert_range_after(const_iterator __position, _Range&& __range) {
return __insert_after_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
}
#endif
template <class _InputIterator, class _Sentinel>
_LIBCPP_HIDE_FROM_ABI
iterator __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l);
_LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p);
_LIBCPP_HIDE_FROM_ABI 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);}
_LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
_LIBCPP_HIDE_FROM_ABI 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);
_LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x);
_LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
_LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x,
const_iterator __f, const_iterator __l);
_LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __v);
template <class _Predicate>
_LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Predicate __pred);
_LIBCPP_INLINE_VISIBILITY
__remove_return_type unique() { return unique(__equal_to()); }
template <class _BinaryPredicate>
_LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred);
#ifndef _LIBCPP_CXX03_LANG
_LIBCPP_INLINE_VISIBILITY
void merge(forward_list&& __x) {merge(__x, __less<>());}
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<>());}
template <class _Compare>
_LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp);
_LIBCPP_INLINE_VISIBILITY
void sort() {sort(__less<>());}
template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
_LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
private:
#ifndef _LIBCPP_CXX03_LANG
_LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, true_type)
_NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
_LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, false_type);
#endif // _LIBCPP_CXX03_LANG
template <class _Iter, class _Sent>
_LIBCPP_HIDE_FROM_ABI
void __assign_with_sentinel(_Iter __f, _Sent __l);
template <class _Compare>
static _LIBCPP_HIDE_FROM_ABI
__node_pointer
__merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
// TODO: Make this _LIBCPP_HIDE_FROM_ABI
template <class _Compare>
static _LIBCPP_HIDDEN
__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<__has_input_iterator_category<_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<__has_input_iterator_category<_InputIterator>::value>,
class = enable_if_t<__is_allocator<_Alloc>::value>
>
forward_list(_InputIterator, _InputIterator, _Alloc)
-> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
#endif
#if _LIBCPP_STD_VER >= 23
template <ranges::input_range _Range,
class _Alloc = allocator<ranges::range_value_t<_Range>>,
class = enable_if_t<__is_allocator<_Alloc>::value>
>
forward_list(from_range_t, _Range&&, _Alloc = _Alloc())
-> forward_list<ranges::range_value_t<_Range>, _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)
{
for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
__p = __p->__next_as_begin())
{
__p->__next_ = this->__create_node(/* next = */nullptr);
}
}
}
#if _LIBCPP_STD_VER >= 14
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)
{
for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
__p = __p->__next_as_begin())
{
__p->__next_ = this->__create_node(/* next = */nullptr);
}
}
}
#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<__has_input_iterator_category<_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<__has_input_iterator_category<_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<__has_input_iterator_category<_InputIterator>::value, int> >
void
forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
{
__assign_with_sentinel(__f, __l);
}
template <class _Tp, class _Alloc>
template <class _Iter, class _Sent>
_LIBCPP_HIDE_FROM_ABI
void forward_list<_Tp, _Alloc>::__assign_with_sentinel(_Iter __f, _Sent __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_with_sentinel(__i, std::move(__f), std::move(__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 >= 17
typename forward_list<_Tp, _Alloc>::reference
#else
void
#endif
forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
{
base::__before_begin()->__next_ = this->__create_node(/* next = */base::__before_begin()->__next_, std::forward<_Args>(__args)...);
#if _LIBCPP_STD_VER >= 17
return base::__before_begin()->__next_->__get_value();
#endif
}
template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
{
base::__before_begin()->__next_ = this->__create_node(/* next = */base::__before_begin()->__next_, std::move(__v));
}
#endif // _LIBCPP_CXX03_LANG
template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
{
base::__before_begin()->__next_ = this->__create_node(/* next = */base::__before_begin()->__next_, __v);
}
template <class _Tp, class _Alloc>
void
forward_list<_Tp, _Alloc>::pop_front()
{
__node_pointer __p = base::__before_begin()->__next_;
base::__before_begin()->__next_ = __p->__next_;
this->__delete_node(__p);
}
#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();
__r->__next_ = this->__create_node(/* next = */__r->__next_, std::forward<_Args>(__args)...);
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();
__r->__next_ = this->__create_node(/* next = */__r->__next_, std::move(__v));
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();
__r->__next_ = this->__create_node(/* next = */__r->__next_, __v);
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_pointer __first = this->__create_node(/* next = */nullptr, __v);
__node_pointer __last = __first;
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
try
{
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
for (--__n; __n != 0; --__n, __last = __last->__next_)
{
__last->__next_ = this->__create_node(/* next = */nullptr, __v);
}
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
}
catch (...)
{
while (__first != nullptr)
{
__node_pointer __next = __first->__next_;
this->__delete_node(__first);
__first = __next;
}
throw;
}
#endif // _LIBCPP_HAS_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<__has_input_iterator_category<_InputIterator>::value, int> >
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
_InputIterator __f, _InputIterator __l)
{
return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l));
}
template <class _Tp, class _Alloc>
template <class _InputIterator, class _Sentinel>
_LIBCPP_HIDE_FROM_ABI
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::__insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) {
__begin_node_pointer __r = __p.__get_begin();
if (__f != __l)
{
__node_pointer __first = this->__create_node(/* next = */nullptr, *__f);
__node_pointer __last = __first;
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
try
{
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
{
__last->__next_ = this->__create_node(/* next = */nullptr, *__f);
}
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
}
catch (...)
{
while (__first != nullptr)
{
__node_pointer __next = __first->__next_;
this->__delete_node(__first);
__first = __next;
}
throw;
}
#endif // _LIBCPP_HAS_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_;
this->__delete_node(__n);
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;
do
{
__node_pointer __tmp = __n->__next_;
this->__delete_node(__n);
__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)
{
for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
__ptr = __ptr->__next_as_begin())
{
__ptr->__next_ = this->__create_node(/* next = */nullptr);
}
}
}
}
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)
{
for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
__ptr = __ptr->__next_as_begin())
{
__ptr->__next_ = this->__create_node(/* next = */nullptr, __v);
}
}
}
}
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_->__get_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_->__get_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->__get_value(), __f1->__get_value()))
{
__node_pointer __t = __f2;
while (__t->__next_ != nullptr &&
__comp(__t->__next_->__get_value(), __f1->__get_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->__get_value(), __f1->__get_value()))
{
__node_pointer __t = __f2;
while (__t->__next_ != nullptr &&
__comp(__t->__next_->__get_value(), __f1->__get_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_->__get_value(), __f1->__get_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);
}
#if _LIBCPP_STD_VER <= 17
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);
}
#else // #if _LIBCPP_STD_VER <= 17
template <class _Tp, class _Allocator>
_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp>
operator<=>(const forward_list<_Tp, _Allocator>& __x, const forward_list<_Tp, _Allocator>& __y) {
return std::lexicographical_compare_three_way(
__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Tp, _Tp>);
}
#endif // #if _LIBCPP_STD_VER <= 17
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 >= 20
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 >= 17
_LIBCPP_BEGIN_NAMESPACE_STD
namespace pmr {
template <class _ValueT>
using forward_list _LIBCPP_AVAILABILITY_PMR = 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 <cstdint>
# include <cstdlib>
# include <cstring>
# include <functional>
# include <iosfwd>
# include <iterator>
# include <type_traits>
# include <typeinfo>
#endif
#endif // _LIBCPP_FORWARD_LIST