// -*- 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; __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr>>; template <class _NodePtr> struct __forward_node_traits { … }; template <class _NodePtr> struct __forward_begin_node { … }; __begin_node_of; template <class _Tp, class _VoidPtr> struct __forward_list_node : public __begin_node_of<_Tp, _VoidPtr> { … }; 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 { … }; template <class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator { … }; template <class _Tp, class _Alloc> class __forward_list_base { … }; #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) : … { … } template <class _Tp, class _Alloc> inline __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x, const allocator_type& __a) : … { … } #endif // _LIBCPP_CXX03_LANG template <class _Tp, class _Alloc> __forward_list_base<_Tp, _Alloc>::~__forward_list_base() { … } 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 { … } template <class _Tp, class _Alloc> void __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT { … } template <class _Tp, class _Alloc /*= allocator<_Tp>*/> class _LIBCPP_TEMPLATE_VIS forward_list : private __forward_list_base<_Tp, _Alloc> { … }; #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) : … { … } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(size_type __n) { … } #if _LIBCPP_STD_VER >= 14 template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __base_alloc) : … { … } #endif template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __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) { … } 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) { … } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) : … { … } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a) : … { … } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) { … } #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) : … { … } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) { … } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, const allocator_type& __a) : … { … } 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) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) { … } 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) { … } template <class _Tp, class _Alloc> inline forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) { … } #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) { … } 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) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) { … } #ifndef _LIBCPP_CXX03_LANG template <class _Tp, class _Alloc> inline void forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) { … } 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) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::push_front(value_type&& __v) { … } #endif // _LIBCPP_CXX03_LANG template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::push_front(const value_type& __v) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::pop_front() { … } #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) { … } template <class _Tp, class _Alloc> typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) { … } #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) { … } 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) { … } 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) { … } 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) { … } template <class _Tp, class _Alloc> typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) { … } template <class _Tp, class _Alloc> typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::resize(size_type __n) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& __x) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& /*__other*/, const_iterator __i) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::splice_after( const_iterator __p, forward_list& /*__other*/, const_iterator __f, const_iterator __l) { … } template <class _Tp, class _Alloc> inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __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) { … } 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) { … } template <class _Tp, class _Alloc> typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove(const value_type& __v) { … } template <class _Tp, class _Alloc> template <class _Predicate> typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) { … } template <class _Tp, class _Alloc> template <class _BinaryPredicate> typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) { … } template <class _Tp, class _Alloc> template <class _Compare> void forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) { … } 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) { … } template <class _Tp, class _Alloc> template <class _Compare> inline void forward_list<_Tp, _Alloc>::sort(_Compare __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) { … } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT { … } template <class _Tp, class _Alloc> _LIBCPP_HIDE_FROM_ABI bool operator==(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { … } #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) { … } #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))) { … } #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) { … } 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) { … } #endif _LIBCPP_END_NAMESPACE_STD #if _LIBCPP_STD_VER >= 17 _LIBCPP_BEGIN_NAMESPACE_STD namespace pmr { forward_list; } // 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
Codebase Browser
chromium