| // -*- C++ -*- |
| //===----------------------- forward_list ---------------------------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is dual licensed under the MIT and the University of Illinois Open |
| // Source Licenses. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef _LIBCPP_FORWARD_LIST |
| #define _LIBCPP_FORWARD_LIST |
| |
| /* |
| forward_list synopsis |
| |
| namespace std |
| { |
| |
| template <class T, class Allocator = allocator<T>> |
| class forward_list |
| { |
| public: |
| typedef T value_type; |
| typedef Allocator allocator_type; |
| |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef typename allocator_traits<allocator_type>::pointer pointer; |
| typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; |
| typedef typename allocator_traits<allocator_type>::size_type size_type; |
| typedef typename allocator_traits<allocator_type>::difference_type difference_type; |
| |
| typedef <details> iterator; |
| typedef <details> const_iterator; |
| |
| forward_list() |
| noexcept(is_nothrow_default_constructible<allocator_type>::value); |
| explicit forward_list(const allocator_type& a); |
| explicit forward_list(size_type n); |
| explicit forward_list(size_type n, const allocator_type& a); // C++14 |
| forward_list(size_type n, const value_type& v); |
| forward_list(size_type n, const value_type& v, const allocator_type& a); |
| template <class InputIterator> |
| forward_list(InputIterator first, InputIterator last); |
| template <class InputIterator> |
| forward_list(InputIterator first, InputIterator last, const allocator_type& a); |
| forward_list(const forward_list& x); |
| forward_list(const forward_list& x, const allocator_type& a); |
| forward_list(forward_list&& x) |
| noexcept(is_nothrow_move_constructible<allocator_type>::value); |
| forward_list(forward_list&& x, const allocator_type& a); |
| forward_list(initializer_list<value_type> il); |
| forward_list(initializer_list<value_type> il, const allocator_type& a); |
| |
| ~forward_list(); |
| |
| forward_list& operator=(const forward_list& x); |
| forward_list& operator=(forward_list&& x) |
| noexcept( |
| allocator_type::propagate_on_container_move_assignment::value && |
| is_nothrow_move_assignable<allocator_type>::value); |
| forward_list& operator=(initializer_list<value_type> il); |
| |
| template <class InputIterator> |
| void assign(InputIterator first, InputIterator last); |
| void assign(size_type n, const value_type& v); |
| void assign(initializer_list<value_type> il); |
| |
| allocator_type get_allocator() const noexcept; |
| |
| iterator begin() noexcept; |
| const_iterator begin() const noexcept; |
| iterator end() noexcept; |
| const_iterator end() const noexcept; |
| |
| const_iterator cbegin() const noexcept; |
| const_iterator cend() const noexcept; |
| |
| iterator before_begin() noexcept; |
| const_iterator before_begin() const noexcept; |
| const_iterator cbefore_begin() const noexcept; |
| |
| bool empty() const noexcept; |
| size_type max_size() const noexcept; |
| |
| reference front(); |
| const_reference front() const; |
| |
| template <class... Args> reference emplace_front(Args&&... args); // reference in C++17 |
| void push_front(const value_type& v); |
| void push_front(value_type&& v); |
| |
| void pop_front(); |
| |
| template <class... Args> |
| iterator emplace_after(const_iterator p, Args&&... args); |
| iterator insert_after(const_iterator p, const value_type& v); |
| iterator insert_after(const_iterator p, value_type&& v); |
| iterator insert_after(const_iterator p, size_type n, const value_type& v); |
| template <class InputIterator> |
| iterator insert_after(const_iterator p, |
| InputIterator first, InputIterator last); |
| iterator insert_after(const_iterator p, initializer_list<value_type> il); |
| |
| iterator erase_after(const_iterator p); |
| iterator erase_after(const_iterator first, const_iterator last); |
| |
| void swap(forward_list& x) |
| noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 |
| |
| void resize(size_type n); |
| void resize(size_type n, const value_type& v); |
| void clear() noexcept; |
| |
| void splice_after(const_iterator p, forward_list& x); |
| void splice_after(const_iterator p, forward_list&& x); |
| void splice_after(const_iterator p, forward_list& x, const_iterator i); |
| void splice_after(const_iterator p, forward_list&& x, const_iterator i); |
| void splice_after(const_iterator p, forward_list& x, |
| const_iterator first, const_iterator last); |
| void splice_after(const_iterator p, forward_list&& x, |
| const_iterator first, const_iterator last); |
| void remove(const value_type& v); |
| template <class Predicate> void remove_if(Predicate pred); |
| void unique(); |
| template <class BinaryPredicate> void unique(BinaryPredicate binary_pred); |
| void merge(forward_list& x); |
| void merge(forward_list&& x); |
| template <class Compare> void merge(forward_list& x, Compare comp); |
| template <class Compare> void merge(forward_list&& x, Compare comp); |
| void sort(); |
| template <class Compare> void sort(Compare comp); |
| void reverse() noexcept; |
| }; |
| |
| |
| template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> |
| forward_list(InputIterator, InputIterator, Allocator = Allocator()) |
| -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17 |
| |
| template <class T, class Allocator> |
| bool operator==(const forward_list<T, Allocator>& x, |
| const forward_list<T, Allocator>& y); |
| |
| template <class T, class Allocator> |
| bool operator< (const forward_list<T, Allocator>& x, |
| const forward_list<T, Allocator>& y); |
| |
| template <class T, class Allocator> |
| bool operator!=(const forward_list<T, Allocator>& x, |
| const forward_list<T, Allocator>& y); |
| |
| template <class T, class Allocator> |
| bool operator> (const forward_list<T, Allocator>& x, |
| const forward_list<T, Allocator>& y); |
| |
| template <class T, class Allocator> |
| bool operator>=(const forward_list<T, Allocator>& x, |
| const forward_list<T, Allocator>& y); |
| |
| template <class T, class Allocator> |
| bool operator<=(const forward_list<T, Allocator>& x, |
| const forward_list<T, Allocator>& y); |
| |
| template <class T, class Allocator> |
| void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y) |
| noexcept(noexcept(x.swap(y))); |
| |
| template <class T, class Allocator, class U> |
| void erase(forward_list<T, Allocator>& c, const U& value); // C++20 |
| template <class T, class Allocator, class Predicate> |
| void erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20 |
| |
| } // std |
| |
| */ |
| |
| #include <__config> |
| #include <initializer_list> |
| #include <memory> |
| #include <limits> |
| #include <iterator> |
| #include <algorithm> |
| #include <version> |
| |
| #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 typename remove_cv< |
| typename pointer_traits<_NodePtr>::element_type>::type __node; |
| typedef typename __forward_list_node_value_type<__node>::type __node_value_type; |
| typedef _NodePtr __node_pointer; |
| typedef __forward_begin_node<_NodePtr> __begin_node; |
| typedef typename __rebind_pointer<_NodePtr, __begin_node>::type |
| __begin_node_pointer; |
| typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer; |
| |
| #if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB) |
| typedef __begin_node_pointer __iter_node_pointer; |
| #else |
| typedef typename conditional< |
| is_pointer<__void_pointer>::value, |
| __begin_node_pointer, |
| __node_pointer |
| >::type __iter_node_pointer; |
| #endif |
| |
| typedef typename conditional< |
| is_same<__iter_node_pointer, __node_pointer>::value, |
| __begin_node_pointer, |
| __node_pointer |
| >::type __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 typename __rebind_pointer<_NodePtr, __forward_begin_node>::type __begin_node_pointer; |
| |
| pointer __next_; |
| |
| _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| __begin_node_pointer __next_as_begin() const { |
| return static_cast<__begin_node_pointer>(__next_); |
| } |
| }; |
| |
| template <class _Tp, class _VoidPtr> |
| struct _LIBCPP_HIDDEN __begin_node_of |
| { |
| typedef __forward_begin_node< |
| typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type |
| > type; |
| }; |
| |
| template <class _Tp, class _VoidPtr> |
| struct __forward_list_node |
| : public __begin_node_of<_Tp, _VoidPtr>::type |
| { |
| typedef _Tp value_type; |
| |
| value_type __value_; |
| }; |
| |
| |
| template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list; |
| template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator; |
| |
| template <class _NodePtr> |
| class _LIBCPP_TEMPLATE_VIS __forward_list_iterator |
| { |
| typedef __forward_node_traits<_NodePtr> __traits; |
| typedef typename __traits::__node_pointer __node_pointer; |
| typedef typename __traits::__begin_node_pointer __begin_node_pointer; |
| typedef typename __traits::__iter_node_pointer __iter_node_pointer; |
| typedef typename __traits::__void_pointer __void_pointer; |
| |
| __iter_node_pointer __ptr_; |
| |
| _LIBCPP_INLINE_VISIBILITY |
| __begin_node_pointer __get_begin() const { |
| return static_cast<__begin_node_pointer>( |
| static_cast<__void_pointer>(__ptr_)); |
| } |
| _LIBCPP_INLINE_VISIBILITY |
| __node_pointer __get_unsafe_node_pointer() const { |
| return static_cast<__node_pointer>( |
| static_cast<__void_pointer>(__ptr_)); |
| } |
| |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT |
| : __ptr_(__traits::__as_iter_node(__p)) {} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT |
| : __ptr_(__traits::__as_iter_node(__p)) {} |
| |
| template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list; |
| template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator; |
| |
| public: |
| typedef forward_iterator_tag iterator_category; |
| typedef typename __traits::__node_value_type value_type; |
| typedef value_type& reference; |
| typedef typename pointer_traits<__node_pointer>::difference_type |
| difference_type; |
| typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer; |
| |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| reference operator*() const {return __get_unsafe_node_pointer()->__value_;} |
| _LIBCPP_INLINE_VISIBILITY |
| pointer operator->() const { |
| return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_); |
| } |
| |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_iterator& operator++() |
| { |
| __ptr_ = __traits::__as_iter_node(__ptr_->__next_); |
| return *this; |
| } |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_iterator operator++(int) |
| { |
| __forward_list_iterator __t(*this); |
| ++(*this); |
| return __t; |
| } |
| |
| friend _LIBCPP_INLINE_VISIBILITY |
| bool operator==(const __forward_list_iterator& __x, |
| const __forward_list_iterator& __y) |
| {return __x.__ptr_ == __y.__ptr_;} |
| friend _LIBCPP_INLINE_VISIBILITY |
| bool operator!=(const __forward_list_iterator& __x, |
| const __forward_list_iterator& __y) |
| {return !(__x == __y);} |
| }; |
| |
| template <class _NodeConstPtr> |
| class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator |
| { |
| static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), ""); |
| typedef _NodeConstPtr _NodePtr; |
| |
| typedef __forward_node_traits<_NodePtr> __traits; |
| typedef typename __traits::__node __node; |
| typedef typename __traits::__node_pointer __node_pointer; |
| typedef typename __traits::__begin_node_pointer __begin_node_pointer; |
| typedef typename __traits::__iter_node_pointer __iter_node_pointer; |
| typedef typename __traits::__void_pointer __void_pointer; |
| |
| __iter_node_pointer __ptr_; |
| |
| __begin_node_pointer __get_begin() const { |
| return static_cast<__begin_node_pointer>( |
| static_cast<__void_pointer>(__ptr_)); |
| } |
| __node_pointer __get_unsafe_node_pointer() const { |
| return static_cast<__node_pointer>( |
| static_cast<__void_pointer>(__ptr_)); |
| } |
| |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT |
| : __ptr_(nullptr) {} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT |
| : __ptr_(__traits::__as_iter_node(__p)) {} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT |
| : __ptr_(__traits::__as_iter_node(__p)) {} |
| |
| |
| template<class, class> friend class forward_list; |
| |
| public: |
| typedef forward_iterator_tag iterator_category; |
| typedef typename __traits::__node_value_type value_type; |
| typedef const value_type& reference; |
| typedef typename pointer_traits<__node_pointer>::difference_type |
| difference_type; |
| typedef typename __rebind_pointer<__node_pointer, const value_type>::type |
| pointer; |
| |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {} |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT |
| : __ptr_(__p.__ptr_) {} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| reference operator*() const {return __get_unsafe_node_pointer()->__value_;} |
| _LIBCPP_INLINE_VISIBILITY |
| pointer operator->() const {return pointer_traits<pointer>::pointer_to( |
| __get_unsafe_node_pointer()->__value_);} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_const_iterator& operator++() |
| { |
| __ptr_ = __traits::__as_iter_node(__ptr_->__next_); |
| return *this; |
| } |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_const_iterator operator++(int) |
| { |
| __forward_list_const_iterator __t(*this); |
| ++(*this); |
| return __t; |
| } |
| |
| friend _LIBCPP_INLINE_VISIBILITY |
| bool operator==(const __forward_list_const_iterator& __x, |
| const __forward_list_const_iterator& __y) |
| {return __x.__ptr_ == __y.__ptr_;} |
| friend _LIBCPP_INLINE_VISIBILITY |
| bool operator!=(const __forward_list_const_iterator& __x, |
| const __forward_list_const_iterator& __y) |
| {return !(__x == __y);} |
| }; |
| |
| template <class _Tp, class _Alloc> |
| class __forward_list_base |
| { |
| protected: |
| typedef _Tp value_type; |
| typedef _Alloc allocator_type; |
| |
| typedef typename allocator_traits<allocator_type>::void_pointer void_pointer; |
| typedef __forward_list_node<value_type, void_pointer> __node; |
| typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node; |
| typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __node>::type __node_allocator; |
| typedef allocator_traits<__node_allocator> __node_traits; |
| typedef typename __node_traits::pointer __node_pointer; |
| |
| typedef typename __rebind_alloc_helper< |
| allocator_traits<allocator_type>, __begin_node |
| >::type __begin_node_allocator; |
| typedef typename allocator_traits<__begin_node_allocator>::pointer |
| __begin_node_pointer; |
| |
| static_assert((!is_same<allocator_type, __node_allocator>::value), |
| "internal allocator type must differ from user-specified " |
| "type; otherwise overload resolution breaks"); |
| |
| __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()) {} |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __forward_list_base(const allocator_type& __a) |
| : __before_begin_(__begin_node(), __node_allocator(__a)) {} |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __forward_list_base(const __node_allocator& __a) |
| : __before_begin_(__begin_node(), __a) {} |
| #ifndef _LIBCPP_CXX03_LANG |
| public: |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_base(__forward_list_base&& __x) |
| _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); |
| _LIBCPP_INLINE_VISIBILITY |
| __forward_list_base(__forward_list_base&& __x, const allocator_type& __a); |
| #endif // _LIBCPP_CXX03_LANG |
| |
| private: |
| __forward_list_base(const __forward_list_base&); |
| __forward_list_base& operator=(const __forward_list_base&); |
| |
| public: |
| ~__forward_list_base(); |
| |
| protected: |
| _LIBCPP_INLINE_VISIBILITY |
| void __copy_assign_alloc(const __forward_list_base& __x) |
| {__copy_assign_alloc(__x, integral_constant<bool, |
| __node_traits::propagate_on_container_copy_assignment::value>());} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| void __move_assign_alloc(__forward_list_base& __x) |
| _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || |
| is_nothrow_move_assignable<__node_allocator>::value) |
| {__move_assign_alloc(__x, integral_constant<bool, |
| __node_traits::propagate_on_container_move_assignment::value>());} |
| |
| public: |
| _LIBCPP_INLINE_VISIBILITY |
| void swap(__forward_list_base& __x) |
| #if _LIBCPP_STD_VER >= 14 |
| _NOEXCEPT; |
| #else |
| _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || |
| __is_nothrow_swappable<__node_allocator>::value); |
| #endif |
| protected: |
| void clear() _NOEXCEPT; |
| |
| private: |
| _LIBCPP_INLINE_VISIBILITY |
| void __copy_assign_alloc(const __forward_list_base&, false_type) {} |
| _LIBCPP_INLINE_VISIBILITY |
| void __copy_assign_alloc(const __forward_list_base& __x, true_type) |
| { |
| if (__alloc() != __x.__alloc()) |
| clear(); |
| __alloc() = __x.__alloc(); |
| } |
| |
| _LIBCPP_INLINE_VISIBILITY |
| void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT |
| {} |
| _LIBCPP_INLINE_VISIBILITY |
| void __move_assign_alloc(__forward_list_base& __x, true_type) |
| _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) |
| {__alloc() = _VSTD::move(__x.__alloc());} |
| }; |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| |
| template <class _Tp, class _Alloc> |
| inline |
| __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x) |
| _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) |
| : __before_begin_(_VSTD::move(__x.__before_begin_)) |
| { |
| __x.__before_begin()->__next_ = nullptr; |
| } |
| |
| template <class _Tp, class _Alloc> |
| inline |
| __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x, |
| const allocator_type& __a) |
| : __before_begin_(__begin_node(), __node_allocator(__a)) |
| { |
| if (__alloc() == __x.__alloc()) |
| { |
| __before_begin()->__next_ = __x.__before_begin()->__next_; |
| __x.__before_begin()->__next_ = nullptr; |
| } |
| } |
| |
| #endif // _LIBCPP_CXX03_LANG |
| |
| template <class _Tp, class _Alloc> |
| __forward_list_base<_Tp, _Alloc>::~__forward_list_base() |
| { |
| clear(); |
| } |
| |
| template <class _Tp, class _Alloc> |
| inline |
| void |
| __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x) |
| #if _LIBCPP_STD_VER >= 14 |
| _NOEXCEPT |
| #else |
| _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || |
| __is_nothrow_swappable<__node_allocator>::value) |
| #endif |
| { |
| __swap_allocator(__alloc(), __x.__alloc(), |
| integral_constant<bool, __node_traits::propagate_on_container_swap::value>()); |
| using _VSTD::swap; |
| swap(__before_begin()->__next_, __x.__before_begin()->__next_); |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT |
| { |
| __node_allocator& __a = __alloc(); |
| for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) |
| { |
| __node_pointer __next = __p->__next_; |
| __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); |
| __node_traits::deallocate(__a, __p, 1); |
| __p = __next; |
| } |
| __before_begin()->__next_ = nullptr; |
| } |
| |
| template <class _Tp, class _Alloc /*= allocator<_Tp>*/> |
| class _LIBCPP_TEMPLATE_VIS forward_list |
| : private __forward_list_base<_Tp, _Alloc> |
| { |
| typedef __forward_list_base<_Tp, _Alloc> base; |
| typedef typename base::__node_allocator __node_allocator; |
| typedef typename base::__node __node; |
| typedef typename base::__node_traits __node_traits; |
| typedef typename base::__node_pointer __node_pointer; |
| typedef typename base::__begin_node_pointer __begin_node_pointer; |
| |
| public: |
| typedef _Tp value_type; |
| typedef _Alloc allocator_type; |
| |
| static_assert((is_same<typename allocator_type::value_type, value_type>::value), |
| "Allocator::value_type must be same type as value_type"); |
| |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef typename allocator_traits<allocator_type>::pointer pointer; |
| typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; |
| typedef typename allocator_traits<allocator_type>::size_type size_type; |
| typedef typename allocator_traits<allocator_type>::difference_type difference_type; |
| |
| typedef typename base::iterator iterator; |
| typedef typename base::const_iterator const_iterator; |
| |
| _LIBCPP_INLINE_VISIBILITY |
| forward_list() |
| _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) |
| {} // = default; |
| _LIBCPP_INLINE_VISIBILITY |
| explicit forward_list(const allocator_type& __a); |
| explicit forward_list(size_type __n); |
| #if _LIBCPP_STD_VER > 11 |
| explicit forward_list(size_type __n, const allocator_type& __a); |
| #endif |
| forward_list(size_type __n, const value_type& __v); |
| forward_list(size_type __n, const value_type& __v, const allocator_type& __a); |
| template <class _InputIterator> |
| forward_list(_InputIterator __f, _InputIterator __l, |
| typename enable_if< |
| __is_input_iterator<_InputIterator>::value |
| >::type* = nullptr); |
| template <class _InputIterator> |
| forward_list(_InputIterator __f, _InputIterator __l, |
| const allocator_type& __a, |
| typename enable_if< |
| __is_input_iterator<_InputIterator>::value |
| >::type* = nullptr); |
| forward_list(const forward_list& __x); |
| forward_list(const forward_list& __x, const allocator_type& __a); |
| |
| forward_list& operator=(const forward_list& __x); |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| _LIBCPP_INLINE_VISIBILITY |
| forward_list(forward_list&& __x) |
| _NOEXCEPT_(is_nothrow_move_constructible<base>::value) |
| : base(_VSTD::move(__x)) {} |
| forward_list(forward_list&& __x, const allocator_type& __a); |
| |
| forward_list(initializer_list<value_type> __il); |
| forward_list(initializer_list<value_type> __il, const allocator_type& __a); |
| |
| _LIBCPP_INLINE_VISIBILITY |
| forward_list& operator=(forward_list&& __x) |
| _NOEXCEPT_( |
| __node_traits::propagate_on_container_move_assignment::value && |
| is_nothrow_move_assignable<allocator_type>::value); |
| |
| _LIBCPP_INLINE_VISIBILITY |
| forward_list& operator=(initializer_list<value_type> __il); |
| |
| _LIBCPP_INLINE_VISIBILITY |
| void assign(initializer_list<value_type> __il); |
| #endif // _LIBCPP_CXX03_LANG |
| |
| // ~forward_list() = default; |
| |
| template <class _InputIterator> |
| typename enable_if |
| < |
| __is_input_iterator<_InputIterator>::value, |
| void |
| >::type |
| assign(_InputIterator __f, _InputIterator __l); |
| void assign(size_type __n, const value_type& __v); |
| |
| _LIBCPP_INLINE_VISIBILITY |
| allocator_type get_allocator() const _NOEXCEPT |
| {return allocator_type(base::__alloc());} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| iterator begin() _NOEXCEPT |
| {return iterator(base::__before_begin()->__next_);} |
| _LIBCPP_INLINE_VISIBILITY |
| const_iterator begin() const _NOEXCEPT |
| {return const_iterator(base::__before_begin()->__next_);} |
| _LIBCPP_INLINE_VISIBILITY |
| iterator end() _NOEXCEPT |
| {return iterator(nullptr);} |
| _LIBCPP_INLINE_VISIBILITY |
| const_iterator end() const _NOEXCEPT |
| {return const_iterator(nullptr);} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| const_iterator cbegin() const _NOEXCEPT |
| {return const_iterator(base::__before_begin()->__next_);} |
| _LIBCPP_INLINE_VISIBILITY |
| const_iterator cend() const _NOEXCEPT |
| {return const_iterator(nullptr);} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| iterator before_begin() _NOEXCEPT |
| {return iterator(base::__before_begin());} |
| _LIBCPP_INLINE_VISIBILITY |
| const_iterator before_begin() const _NOEXCEPT |
| {return const_iterator(base::__before_begin());} |
| _LIBCPP_INLINE_VISIBILITY |
| const_iterator cbefore_begin() const _NOEXCEPT |
| {return const_iterator(base::__before_begin());} |
| |
| _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY |
| bool empty() const _NOEXCEPT |
| {return base::__before_begin()->__next_ == nullptr;} |
| _LIBCPP_INLINE_VISIBILITY |
| size_type max_size() const _NOEXCEPT { |
| return std::min<size_type>( |
| __node_traits::max_size(base::__alloc()), |
| numeric_limits<difference_type>::max()); |
| } |
| |
| _LIBCPP_INLINE_VISIBILITY |
| reference front() {return base::__before_begin()->__next_->__value_;} |
| _LIBCPP_INLINE_VISIBILITY |
| const_reference front() const {return base::__before_begin()->__next_->__value_;} |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| #if _LIBCPP_STD_VER > 14 |
| template <class... _Args> reference emplace_front(_Args&&... __args); |
| #else |
| template <class... _Args> void emplace_front(_Args&&... __args); |
| #endif |
| void push_front(value_type&& __v); |
| #endif // _LIBCPP_CXX03_LANG |
| void push_front(const value_type& __v); |
| |
| void pop_front(); |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| template <class... _Args> |
| iterator emplace_after(const_iterator __p, _Args&&... __args); |
| |
| iterator insert_after(const_iterator __p, value_type&& __v); |
| iterator insert_after(const_iterator __p, initializer_list<value_type> __il) |
| {return insert_after(__p, __il.begin(), __il.end());} |
| #endif // _LIBCPP_CXX03_LANG |
| iterator insert_after(const_iterator __p, const value_type& __v); |
| iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); |
| template <class _InputIterator> |
| _LIBCPP_INLINE_VISIBILITY |
| typename enable_if |
| < |
| __is_input_iterator<_InputIterator>::value, |
| iterator |
| >::type |
| insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); |
| |
| iterator erase_after(const_iterator __p); |
| iterator erase_after(const_iterator __f, const_iterator __l); |
| |
| _LIBCPP_INLINE_VISIBILITY |
| void swap(forward_list& __x) |
| #if _LIBCPP_STD_VER >= 14 |
| _NOEXCEPT |
| #else |
| _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || |
| __is_nothrow_swappable<__node_allocator>::value) |
| #endif |
| {base::swap(__x);} |
| |
| void resize(size_type __n); |
| void resize(size_type __n, const value_type& __v); |
| _LIBCPP_INLINE_VISIBILITY |
| void clear() _NOEXCEPT {base::clear();} |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| _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); |
| #endif // _LIBCPP_CXX03_LANG |
| void splice_after(const_iterator __p, forward_list& __x); |
| void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); |
| void splice_after(const_iterator __p, forward_list& __x, |
| const_iterator __f, const_iterator __l); |
| void remove(const value_type& __v); |
| template <class _Predicate> void remove_if(_Predicate __pred); |
| _LIBCPP_INLINE_VISIBILITY |
| void unique() {unique(__equal_to<value_type>());} |
| template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred); |
| #ifndef _LIBCPP_CXX03_LANG |
| _LIBCPP_INLINE_VISIBILITY |
| void merge(forward_list&& __x) {merge(__x, __less<value_type>());} |
| template <class _Compare> |
| _LIBCPP_INLINE_VISIBILITY |
| void merge(forward_list&& __x, _Compare __comp) |
| {merge(__x, _VSTD::move(__comp));} |
| #endif // _LIBCPP_CXX03_LANG |
| _LIBCPP_INLINE_VISIBILITY |
| void merge(forward_list& __x) {merge(__x, __less<value_type>());} |
| template <class _Compare> void merge(forward_list& __x, _Compare __comp); |
| _LIBCPP_INLINE_VISIBILITY |
| void sort() {sort(__less<value_type>());} |
| template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp); |
| void reverse() _NOEXCEPT; |
| |
| private: |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| void __move_assign(forward_list& __x, true_type) |
| _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); |
| void __move_assign(forward_list& __x, false_type); |
| #endif // _LIBCPP_CXX03_LANG |
| |
| template <class _Compare> |
| static |
| __node_pointer |
| __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); |
| |
| template <class _Compare> |
| static |
| __node_pointer |
| __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); |
| }; |
| |
| |
| #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES |
| template<class _InputIterator, |
| class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>, |
| class = typename enable_if<__is_allocator<_Alloc>::value, void>::type |
| > |
| forward_list(_InputIterator, _InputIterator) |
| -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>; |
| |
| template<class _InputIterator, |
| class _Alloc, |
| class = typename enable_if<__is_allocator<_Alloc>::value, void>::type |
| > |
| forward_list(_InputIterator, _InputIterator, _Alloc) |
| -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>; |
| #endif |
| |
| template <class _Tp, class _Alloc> |
| inline |
| forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) |
| : base(__a) |
| { |
| } |
| |
| template <class _Tp, class _Alloc> |
| forward_list<_Tp, _Alloc>::forward_list(size_type __n) |
| { |
| if (__n > 0) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); |
| for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, |
| __p = __p->__next_as_begin()) |
| { |
| __h.reset(__node_traits::allocate(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); |
| __h->__next_ = nullptr; |
| __p->__next_ = __h.release(); |
| } |
| } |
| } |
| |
| #if _LIBCPP_STD_VER > 11 |
| template <class _Tp, class _Alloc> |
| forward_list<_Tp, _Alloc>::forward_list(size_type __n, |
| const allocator_type& __base_alloc) |
| : base ( __base_alloc ) |
| { |
| if (__n > 0) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); |
| for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, |
| __p = __p->__next_as_begin()) |
| { |
| __h.reset(__node_traits::allocate(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); |
| __h->__next_ = nullptr; |
| __p->__next_ = __h.release(); |
| } |
| } |
| } |
| #endif |
| |
| template <class _Tp, class _Alloc> |
| forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) |
| { |
| insert_after(cbefore_begin(), __n, __v); |
| } |
| |
| template <class _Tp, class _Alloc> |
| forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v, |
| const allocator_type& __a) |
| : base(__a) |
| { |
| insert_after(cbefore_begin(), __n, __v); |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class _InputIterator> |
| forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, |
| typename enable_if< |
| __is_input_iterator<_InputIterator>::value |
| >::type*) |
| { |
| 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, |
| typename enable_if< |
| __is_input_iterator<_InputIterator>::value |
| >::type*) |
| : 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 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 != &__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 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> |
| typename enable_if |
| < |
| __is_input_iterator<_InputIterator>::value, |
| void |
| >::type |
| forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) |
| { |
| iterator __i = before_begin(); |
| iterator __j = _VSTD::next(__i); |
| iterator __e = end(); |
| for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f) |
| *__j = *__f; |
| if (__j == __e) |
| insert_after(__i, __f, __l); |
| else |
| erase_after(__i, __e); |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) |
| { |
| iterator __i = before_begin(); |
| iterator __j = _VSTD::next(__i); |
| iterator __e = end(); |
| for (; __j != __e && __n > 0; --__n, ++__i, ++__j) |
| *__j = __v; |
| if (__j == __e) |
| insert_after(__i, __n, __v); |
| else |
| erase_after(__i, __e); |
| } |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| |
| template <class _Tp, class _Alloc> |
| inline |
| void |
| forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) |
| { |
| assign(__il.begin(), __il.end()); |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class... _Args> |
| #if _LIBCPP_STD_VER > 14 |
| typename forward_list<_Tp, _Alloc>::reference |
| #else |
| void |
| #endif |
| forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), |
| _VSTD::forward<_Args>(__args)...); |
| __h->__next_ = base::__before_begin()->__next_; |
| base::__before_begin()->__next_ = __h.release(); |
| #if _LIBCPP_STD_VER > 14 |
| return base::__before_begin()->__next_->__value_; |
| #endif |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::push_front(value_type&& __v) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); |
| __h->__next_ = base::__before_begin()->__next_; |
| base::__before_begin()->__next_ = __h.release(); |
| } |
| |
| #endif // _LIBCPP_CXX03_LANG |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::push_front(const value_type& __v) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); |
| __h->__next_ = base::__before_begin()->__next_; |
| base::__before_begin()->__next_ = __h.release(); |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::pop_front() |
| { |
| __node_allocator& __a = base::__alloc(); |
| __node_pointer __p = base::__before_begin()->__next_; |
| base::__before_begin()->__next_ = __p->__next_; |
| __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); |
| __node_traits::deallocate(__a, __p, 1); |
| } |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| |
| template <class _Tp, class _Alloc> |
| template <class... _Args> |
| typename forward_list<_Tp, _Alloc>::iterator |
| forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) |
| { |
| __begin_node_pointer const __r = __p.__get_begin(); |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), |
| _VSTD::forward<_Args>(__args)...); |
| __h->__next_ = __r->__next_; |
| __r->__next_ = __h.release(); |
| return iterator(__r->__next_); |
| } |
| |
| template <class _Tp, class _Alloc> |
| typename forward_list<_Tp, _Alloc>::iterator |
| forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) |
| { |
| __begin_node_pointer const __r = __p.__get_begin(); |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); |
| __h->__next_ = __r->__next_; |
| __r->__next_ = __h.release(); |
| return iterator(__r->__next_); |
| } |
| |
| #endif // _LIBCPP_CXX03_LANG |
| |
| template <class _Tp, class _Alloc> |
| typename forward_list<_Tp, _Alloc>::iterator |
| forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) |
| { |
| __begin_node_pointer const __r = __p.__get_begin(); |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); |
| __h->__next_ = __r->__next_; |
| __r->__next_ = __h.release(); |
| return iterator(__r->__next_); |
| } |
| |
| template <class _Tp, class _Alloc> |
| typename forward_list<_Tp, _Alloc>::iterator |
| forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, |
| const value_type& __v) |
| { |
| __begin_node_pointer __r = __p.__get_begin(); |
| if (__n > 0) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); |
| __node_pointer __first = __h.release(); |
| __node_pointer __last = __first; |
| #ifndef _LIBCPP_NO_EXCEPTIONS |
| try |
| { |
| #endif // _LIBCPP_NO_EXCEPTIONS |
| for (--__n; __n != 0; --__n, __last = __last->__next_) |
| { |
| __h.reset(__node_traits::allocate(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); |
| __last->__next_ = __h.release(); |
| } |
| #ifndef _LIBCPP_NO_EXCEPTIONS |
| } |
| catch (...) |
| { |
| while (__first != nullptr) |
| { |
| __node_pointer __next = __first->__next_; |
| __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); |
| __node_traits::deallocate(__a, __first, 1); |
| __first = __next; |
| } |
| throw; |
| } |
| #endif // _LIBCPP_NO_EXCEPTIONS |
| __last->__next_ = __r->__next_; |
| __r->__next_ = __first; |
| __r = static_cast<__begin_node_pointer>(__last); |
| } |
| return iterator(__r); |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class _InputIterator> |
| typename enable_if |
| < |
| __is_input_iterator<_InputIterator>::value, |
| typename forward_list<_Tp, _Alloc>::iterator |
| >::type |
| forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, |
| _InputIterator __f, _InputIterator __l) |
| { |
| __begin_node_pointer __r = __p.__get_begin(); |
| if (__f != __l) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); |
| __node_pointer __first = __h.release(); |
| __node_pointer __last = __first; |
| #ifndef _LIBCPP_NO_EXCEPTIONS |
| try |
| { |
| #endif // _LIBCPP_NO_EXCEPTIONS |
| for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) |
| { |
| __h.reset(__node_traits::allocate(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); |
| __last->__next_ = __h.release(); |
| } |
| #ifndef _LIBCPP_NO_EXCEPTIONS |
| } |
| catch (...) |
| { |
| while (__first != nullptr) |
| { |
| __node_pointer __next = __first->__next_; |
| __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); |
| __node_traits::deallocate(__a, __first, 1); |
| __first = __next; |
| } |
| throw; |
| } |
| #endif // _LIBCPP_NO_EXCEPTIONS |
| __last->__next_ = __r->__next_; |
| __r->__next_ = __first; |
| __r = static_cast<__begin_node_pointer>(__last); |
| } |
| return iterator(__r); |
| } |
| |
| template <class _Tp, class _Alloc> |
| typename forward_list<_Tp, _Alloc>::iterator |
| forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) |
| { |
| __begin_node_pointer __p = __f.__get_begin(); |
| __node_pointer __n = __p->__next_; |
| __p->__next_ = __n->__next_; |
| __node_allocator& __a = base::__alloc(); |
| __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); |
| __node_traits::deallocate(__a, __n, 1); |
| return iterator(__p->__next_); |
| } |
| |
| template <class _Tp, class _Alloc> |
| typename forward_list<_Tp, _Alloc>::iterator |
| forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) |
| { |
| __node_pointer __e = __l.__get_unsafe_node_pointer(); |
| if (__f != __l) |
| { |
| __begin_node_pointer __bp = __f.__get_begin(); |
| |
| __node_pointer __n = __bp->__next_; |
| if (__n != __e) |
| { |
| __bp->__next_ = __e; |
| __node_allocator& __a = base::__alloc(); |
| do |
| { |
| __node_pointer __tmp = __n->__next_; |
| __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); |
| __node_traits::deallocate(__a, __n, 1); |
| __n = __tmp; |
| } while (__n != __e); |
| } |
| } |
| return iterator(__e); |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::resize(size_type __n) |
| { |
| size_type __sz = 0; |
| iterator __p = before_begin(); |
| iterator __i = begin(); |
| iterator __e = end(); |
| for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) |
| ; |
| if (__i != __e) |
| erase_after(__p, __e); |
| else |
| { |
| __n -= __sz; |
| if (__n > 0) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); |
| for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, |
| __ptr = __ptr->__next_as_begin()) |
| { |
| __h.reset(__node_traits::allocate(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); |
| __h->__next_ = nullptr; |
| __ptr->__next_ = __h.release(); |
| } |
| } |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) |
| { |
| size_type __sz = 0; |
| iterator __p = before_begin(); |
| iterator __i = begin(); |
| iterator __e = end(); |
| for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) |
| ; |
| if (__i != __e) |
| erase_after(__p, __e); |
| else |
| { |
| __n -= __sz; |
| if (__n > 0) |
| { |
| __node_allocator& __a = base::__alloc(); |
| typedef __allocator_destructor<__node_allocator> _Dp; |
| unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); |
| for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, |
| __ptr = __ptr->__next_as_begin()) |
| { |
| __h.reset(__node_traits::allocate(__a, 1)); |
| __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); |
| __h->__next_ = nullptr; |
| __ptr->__next_ = __h.release(); |
| } |
| } |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, |
| forward_list& __x) |
| { |
| if (!__x.empty()) |
| { |
| if (__p.__get_begin()->__next_ != nullptr) |
| { |
| const_iterator __lm1 = __x.before_begin(); |
| while (__lm1.__get_begin()->__next_ != nullptr) |
| ++__lm1; |
| __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; |
| } |
| __p.__get_begin()->__next_ = __x.__before_begin()->__next_; |
| __x.__before_begin()->__next_ = nullptr; |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, |
| forward_list& /*__other*/, |
| const_iterator __i) |
| { |
| const_iterator __lm1 = _VSTD::next(__i); |
| if (__p != __i && __p != __lm1) |
| { |
| __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_; |
| __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; |
| __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer(); |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, |
| forward_list& /*__other*/, |
| const_iterator __f, const_iterator __l) |
| { |
| if (__f != __l && __p != __f) |
| { |
| const_iterator __lm1 = __f; |
| while (__lm1.__get_begin()->__next_ != __l.__get_begin()) |
| ++__lm1; |
| if (__f != __lm1) |
| { |
| __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; |
| __p.__get_begin()->__next_ = __f.__get_begin()->__next_; |
| __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer(); |
| } |
| } |
| } |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| |
| 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); |
| } |
| |
| #endif // _LIBCPP_CXX03_LANG |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::remove(const value_type& __v) |
| { |
| forward_list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing |
| iterator __e = end(); |
| for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) |
| { |
| if (__i.__get_begin()->__next_->__value_ == __v) |
| { |
| iterator __j = _VSTD::next(__i, 2); |
| for (; __j != __e && *__j == __v; ++__j) |
| ; |
| __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); |
| if (__j == __e) |
| break; |
| __i = __j; |
| } |
| else |
| ++__i; |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class _Predicate> |
| void |
| forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) |
| { |
| iterator __e = end(); |
| for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) |
| { |
| if (__pred(__i.__get_begin()->__next_->__value_)) |
| { |
| iterator __j = _VSTD::next(__i, 2); |
| for (; __j != __e && __pred(*__j); ++__j) |
| ; |
| erase_after(__i, __j); |
| if (__j == __e) |
| break; |
| __i = __j; |
| } |
| else |
| ++__i; |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class _BinaryPredicate> |
| void |
| forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) |
| { |
| for (iterator __i = begin(), __e = end(); __i != __e;) |
| { |
| iterator __j = _VSTD::next(__i); |
| for (; __j != __e && __binary_pred(*__i, *__j); ++__j) |
| ; |
| if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer()) |
| erase_after(__i, __j); |
| __i = __j; |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class _Compare> |
| void |
| forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) |
| { |
| if (this != &__x) |
| { |
| base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, |
| __x.__before_begin()->__next_, |
| __comp); |
| __x.__before_begin()->__next_ = nullptr; |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class _Compare> |
| typename forward_list<_Tp, _Alloc>::__node_pointer |
| forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, |
| _Compare& __comp) |
| { |
| if (__f1 == nullptr) |
| return __f2; |
| if (__f2 == nullptr) |
| return __f1; |
| __node_pointer __r; |
| if (__comp(__f2->__value_, __f1->__value_)) |
| { |
| __node_pointer __t = __f2; |
| while (__t->__next_ != nullptr && |
| __comp(__t->__next_->__value_, __f1->__value_)) |
| __t = __t->__next_; |
| __r = __f2; |
| __f2 = __t->__next_; |
| __t->__next_ = __f1; |
| } |
| else |
| __r = __f1; |
| __node_pointer __p = __f1; |
| __f1 = __f1->__next_; |
| while (__f1 != nullptr && __f2 != nullptr) |
| { |
| if (__comp(__f2->__value_, __f1->__value_)) |
| { |
| __node_pointer __t = __f2; |
| while (__t->__next_ != nullptr && |
| __comp(__t->__next_->__value_, __f1->__value_)) |
| __t = __t->__next_; |
| __p->__next_ = __f2; |
| __f2 = __t->__next_; |
| __t->__next_ = __f1; |
| } |
| __p = __f1; |
| __f1 = __f1->__next_; |
| } |
| if (__f2 != nullptr) |
| __p->__next_ = __f2; |
| return __r; |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class _Compare> |
| inline |
| void |
| forward_list<_Tp, _Alloc>::sort(_Compare __comp) |
| { |
| base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, |
| _VSTD::distance(begin(), end()), __comp); |
| } |
| |
| template <class _Tp, class _Alloc> |
| template <class _Compare> |
| typename forward_list<_Tp, _Alloc>::__node_pointer |
| forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, |
| _Compare& __comp) |
| { |
| switch (__sz) |
| { |
| case 0: |
| case 1: |
| return __f1; |
| case 2: |
| if (__comp(__f1->__next_->__value_, __f1->__value_)) |
| { |
| __node_pointer __t = __f1->__next_; |
| __t->__next_ = __f1; |
| __f1->__next_ = nullptr; |
| __f1 = __t; |
| } |
| return __f1; |
| } |
| difference_type __sz1 = __sz / 2; |
| difference_type __sz2 = __sz - __sz1; |
| __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer(); |
| __node_pointer __f2 = __t->__next_; |
| __t->__next_ = nullptr; |
| return __merge(__sort(__f1, __sz1, __comp), |
| __sort(__f2, __sz2, __comp), __comp); |
| } |
| |
| template <class _Tp, class _Alloc> |
| void |
| forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT |
| { |
| __node_pointer __p = base::__before_begin()->__next_; |
| if (__p != nullptr) |
| { |
| __node_pointer __f = __p->__next_; |
| __p->__next_ = nullptr; |
| while (__f != nullptr) |
| { |
| __node_pointer __t = __f->__next_; |
| __f->__next_ = __p; |
| __p = __f; |
| __f = __t; |
| } |
| base::__before_begin()->__next_ = __p; |
| } |
| } |
| |
| template <class _Tp, class _Alloc> |
| bool operator==(const forward_list<_Tp, _Alloc>& __x, |
| const forward_list<_Tp, _Alloc>& __y) |
| { |
| typedef forward_list<_Tp, _Alloc> _Cp; |
| typedef typename _Cp::const_iterator _Ip; |
| _Ip __ix = __x.begin(); |
| _Ip __ex = __x.end(); |
| _Ip __iy = __y.begin(); |
| _Ip __ey = __y.end(); |
| for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) |
| if (!(*__ix == *__iy)) |
| return false; |
| return (__ix == __ex) == (__iy == __ey); |
| } |
| |
| template <class _Tp, class _Alloc> |
| inline _LIBCPP_INLINE_VISIBILITY |
| bool operator!=(const forward_list<_Tp, _Alloc>& __x, |
| const forward_list<_Tp, _Alloc>& __y) |
| { |
| return !(__x == __y); |
| } |
| |
| template <class _Tp, class _Alloc> |
| inline _LIBCPP_INLINE_VISIBILITY |
| bool operator< (const forward_list<_Tp, _Alloc>& __x, |
| const forward_list<_Tp, _Alloc>& __y) |
| { |
| return _VSTD::lexicographical_compare(__x.begin(), __x.end(), |
| __y.begin(), __y.end()); |
| } |
| |
| template <class _Tp, class _Alloc> |
| inline _LIBCPP_INLINE_VISIBILITY |
| bool operator> (const forward_list<_Tp, _Alloc>& __x, |
| const forward_list<_Tp, _Alloc>& __y) |
| { |
| return __y < __x; |
| } |
| |
| template <class _Tp, class _Alloc> |
| inline _LIBCPP_INLINE_VISIBILITY |
| bool operator>=(const forward_list<_Tp, _Alloc>& __x, |
| const forward_list<_Tp, _Alloc>& __y) |
| { |
| return !(__x < __y); |
| } |
| |
| template <class _Tp, class _Alloc> |
| inline _LIBCPP_INLINE_VISIBILITY |
| bool operator<=(const forward_list<_Tp, _Alloc>& __x, |
| const forward_list<_Tp, _Alloc>& __y) |
| { |
| return !(__y < __x); |
| } |
| |
| template <class _Tp, class _Alloc> |
| inline _LIBCPP_INLINE_VISIBILITY |
| void |
| swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) |
| _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
| { |
| __x.swap(__y); |
| } |
| |
| #if _LIBCPP_STD_VER > 17 |
| template <class _Tp, class _Allocator, class _Predicate> |
| inline _LIBCPP_INLINE_VISIBILITY |
| void erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) |
| { __c.remove_if(__pred); } |
| |
| template <class _Tp, class _Allocator, class _Up> |
| inline _LIBCPP_INLINE_VISIBILITY |
| void erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) |
| { _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; }); } |
| #endif |
| |
| _LIBCPP_END_NAMESPACE_STD |
| |
| _LIBCPP_POP_MACROS |
| |
| #endif // _LIBCPP_FORWARD_LIST |