diff options
Diffstat (limited to 'contrib/llvm-project/libcxx/include/forward_list')
| -rw-r--r-- | contrib/llvm-project/libcxx/include/forward_list | 1575 |
1 files changed, 1575 insertions, 0 deletions
diff --git a/contrib/llvm-project/libcxx/include/forward_list b/contrib/llvm-project/libcxx/include/forward_list new file mode 100644 index 000000000000..b14d2cb6c780 --- /dev/null +++ b/contrib/llvm-project/libcxx/include/forward_list @@ -0,0 +1,1575 @@ +// -*- 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 <__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_assignable.h> +#include <__type_traits/is_nothrow_constructible.h> +#include <__type_traits/is_pointer.h> +#include <__type_traits/is_same.h> +#include <__type_traits/is_swappable.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_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) { return __p; } + _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI __forward_begin_node() : __next_(nullptr) {} + _LIBCPP_HIDE_FROM_ABI explicit __forward_begin_node(pointer __n) : __next_(__n) {} + + _LIBCPP_HIDE_FROM_ABI __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_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_HIDE_FROM_ABI explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {} + + _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT + : __ptr_(__traits::__as_iter_node(__p)) {} + + _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { + return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value()); + } + + _LIBCPP_HIDE_FROM_ABI __forward_list_iterator& operator++() { + __ptr_ = __traits::__as_iter_node(__ptr_->__next_); + return *this; + } + _LIBCPP_HIDE_FROM_ABI __forward_list_iterator operator++(int) { + __forward_list_iterator __t(*this); + ++(*this); + return __t; + } + + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __forward_list_iterator& __x, const __forward_list_iterator& __y) { + return __x.__ptr_ == __y.__ptr_; + } + friend _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {} + + _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT + : __ptr_(__traits::__as_iter_node(__p)) {} + + _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {} + _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT + : __ptr_(__p.__ptr_) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { + return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value()); + } + + _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator& operator++() { + __ptr_ = __traits::__as_iter_node(__ptr_->__next_); + return *this; + } + _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator operator++(int) { + __forward_list_const_iterator __t(*this); + ++(*this); + return __t; + } + + friend _LIBCPP_HIDE_FROM_ABI bool + operator==(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) { + return __x.__ptr_ == __y.__ptr_; + } + friend _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI __begin_node_pointer __before_begin() _NOEXCEPT { + return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first()); + } + _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() const _NOEXCEPT { + return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first())); + } + + _LIBCPP_HIDE_FROM_ABI __node_allocator& __alloc() _NOEXCEPT { return __before_begin_.second(); } + _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI __forward_list_base() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) + : __before_begin_(__begin_node(), __default_init_tag()) {} + _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const allocator_type& __a) + : __before_begin_(__begin_node(), __node_allocator(__a)) {} + _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const __node_allocator& __a) + : __before_begin_(__begin_node(), __a) {} + +public: +#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_HIDE_FROM_ABI + __forward_list_base(__forward_list_base&& __x) noexcept(is_nothrow_move_constructible<__node_allocator>::value); + _LIBCPP_HIDE_FROM_ABI __forward_list_base(__forward_list_base&& __x, const allocator_type& __a); +#endif // _LIBCPP_CXX03_LANG + + __forward_list_base(const __forward_list_base&) = delete; + __forward_list_base& operator=(const __forward_list_base&) = delete; + + _LIBCPP_HIDE_FROM_ABI ~__forward_list_base(); + +protected: + _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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(); + } + + _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_HIDE_FROM_ABI void swap(__forward_list_base& __x) +#if _LIBCPP_STD_VER >= 14 + _NOEXCEPT; +#else + _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>); +#endif + +protected: + _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT; + +private: + _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base&, false_type) {} + _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x, true_type) { + if (__alloc() != __x.__alloc()) + clear(); + __alloc() = __x.__alloc(); + } + + _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT {} + _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x, true_type) + _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) { + __alloc() = std::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_(std::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_v<__node_allocator>) +#endif +{ + std::__swap_allocator( + __alloc(), __x.__alloc(), integral_constant<bool, __node_traits::propagate_on_container_swap::value>()); + using std::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(__check_valid_allocator<allocator_type>::value, ""); + + 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, __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_HIDE_FROM_ABI forward_list() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) { + } // = default; + _LIBCPP_HIDE_FROM_ABI 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 <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0> + _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, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l); + + template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a); + +#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_HIDE_FROM_ABI forward_list(forward_list&& __x) noexcept(is_nothrow_move_constructible<base>::value) + : base(std::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_HIDE_FROM_ABI forward_list& operator=(forward_list&& __x) noexcept( + __node_traits::propagate_on_container_move_assignment::value && + is_nothrow_move_assignable<allocator_type>::value); + + _LIBCPP_HIDE_FROM_ABI forward_list& operator=(initializer_list<value_type> __il); + + _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(base::__alloc()); } + + _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(base::__before_begin()->__next_); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { + return const_iterator(base::__before_begin()->__next_); + } + _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(nullptr); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(nullptr); } + + _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { + return const_iterator(base::__before_begin()->__next_); + } + _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return const_iterator(nullptr); } + + _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT { return iterator(base::__before_begin()); } + _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT { return const_iterator(base::__before_begin()); } + _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT { + return const_iterator(base::__before_begin()); + } + + _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { + return base::__before_begin()->__next_ == nullptr; + } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { + return std::min<size_type>(__node_traits::max_size(base::__alloc()), numeric_limits<difference_type>::max()); + } + + _LIBCPP_HIDE_FROM_ABI reference front() { return base::__before_begin()->__next_->__get_value(); } + _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI void swap(forward_list& __x) +#if _LIBCPP_STD_VER >= 14 + _NOEXCEPT +#else + _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>) +#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_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); } + + _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 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_HIDE_FROM_ABI __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_HIDE_FROM_ABI void merge(forward_list&& __x) { merge(__x, __less<>()); } + template <class _Compare> + _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x, _Compare __comp) { + merge(__x, std::move(__comp)); + } +#endif // _LIBCPP_CXX03_LANG + _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x) { merge(__x, __less<>()); } + template <class _Compare> + _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp); + _LIBCPP_HIDE_FROM_ABI void sort() { sort(__less<>()); } + template <class _Compare> + _LIBCPP_HIDE_FROM_ABI 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, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> > +forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) { + insert_after(cbefore_begin(), __f, __l); +} + +template <class _Tp, class _Alloc> +template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> > +forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a) : 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 != std::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(std::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 = std::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 = std::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 = std::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_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x) { + splice_after(__p, __x); +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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 = std::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 = std::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 = std::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 != std::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_, std::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 = std::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_HIDE_FROM_ABI bool +operator!=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { + return !(__x == __y); +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_HIDE_FROM_ABI bool +operator<(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { + return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_HIDE_FROM_ABI bool +operator>(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { + return __y < __x; +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_HIDE_FROM_ABI bool +operator>=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { + return !(__x < __y); +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_HIDE_FROM_ABI 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); +} + +#endif // #if _LIBCPP_STD_VER <= 17 + +template <class _Tp, class _Alloc> +inline _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI typename forward_list<_Tp, _Allocator>::size_type +erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) { + return std::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 <stdexcept> +# include <type_traits> +# include <typeinfo> +#endif + +#endif // _LIBCPP_FORWARD_LIST |