30#ifndef _FORWARD_LIST_H
31#define _FORWARD_LIST_H 1
34#pragma GCC system_header
46#if __glibcxx_ranges_to_container
51namespace std _GLIBCXX_VISIBILITY(default)
53_GLIBCXX_BEGIN_NAMESPACE_VERSION
54_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
65 : _M_next(__x._M_next)
66 { __x._M_next =
nullptr; }
74 _M_next = __x._M_next;
75 __x._M_next =
nullptr;
88 __begin->_M_next = __end->_M_next;
89 __end->_M_next = _M_next;
92 __begin->_M_next =
nullptr;
98 _M_reverse_after()
noexcept
107 __tail->_M_next = __temp->_M_next;
108 _M_next->_M_next = __keep;
119 template<
typename _Tp>
125 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
129 {
return _M_storage._M_ptr(); }
132 _M_valptr()
const noexcept
133 {
return _M_storage._M_ptr(); }
141 template<
typename _Tp>
147 typedef _Tp value_type;
148 typedef _Tp* pointer;
149 typedef _Tp& reference;
150 typedef ptrdiff_t difference_type;
162 operator*()
const noexcept
163 {
return *
static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
167 operator->()
const noexcept
168 {
return static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
171 operator++()
noexcept
173 _M_node = _M_node->_M_next;
178 operator++(
int)
noexcept
181 _M_node = _M_node->_M_next;
191 {
return __x._M_node == __y._M_node; }
193#if __cpp_impl_three_way_comparison < 201907L
199 operator!=(
const _Self& __x,
const _Self& __y)
noexcept
200 {
return __x._M_node != __y._M_node; }
204 _M_next() const noexcept
207 return _Fwd_list_iterator(_M_node->_M_next);
209 return _Fwd_list_iterator(
nullptr);
212 _Fwd_list_node_base* _M_node;
220 template<
typename _Tp>
227 typedef _Tp value_type;
228 typedef const _Tp* pointer;
229 typedef const _Tp& reference;
230 typedef ptrdiff_t difference_type;
241 : _M_node(__iter._M_node) { }
245 operator*()
const noexcept
246 {
return *
static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
250 operator->()
const noexcept
251 {
return static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
254 operator++()
noexcept
256 _M_node = _M_node->_M_next;
261 operator++(
int)
noexcept
264 _M_node = _M_node->_M_next;
274 {
return __x._M_node == __y._M_node; }
276#if __cpp_impl_three_way_comparison < 201907L
282 operator!=(
const _Self& __x,
const _Self& __y)
noexcept
283 {
return __x._M_node != __y._M_node; }
287 _M_next() const noexcept
290 return _Fwd_list_const_iterator(_M_node->_M_next);
292 return _Fwd_list_const_iterator(
nullptr);
295 const _Fwd_list_node_base* _M_node;
301 template<
typename _Tp,
typename _Alloc>
305 typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
308 struct _Fwd_list_impl
309 :
public _Node_alloc_type
315 : _Node_alloc_type(), _M_head()
318 _Fwd_list_impl(_Fwd_list_impl&&) =
default;
320 _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a)
324 _Fwd_list_impl(_Node_alloc_type&& __a)
325 : _Node_alloc_type(
std::move(__a)), _M_head()
329 _Fwd_list_impl _M_impl;
337 _M_get_Node_allocator()
noexcept
338 {
return this->_M_impl; }
340 const _Node_alloc_type&
341 _M_get_Node_allocator()
const noexcept
342 {
return this->_M_impl; }
361 { _M_erase_after(&_M_impl._M_head,
nullptr); }
368 return std::__to_address(__ptr);
371 template<
typename... _Args>
373 _M_create_node(_Args&&... __args)
375 _Node* __node = this->_M_get_node();
378 ::new ((
void*)__node) _Node;
379 _Node_alloc_traits::construct(_M_get_Node_allocator(),
381 std::forward<_Args>(__args)...);
385 this->_M_put_node(__node);
386 __throw_exception_again;
391 template<
typename... _Args>
396 _M_put_node(_Node* __p)
398 typedef typename _Node_alloc_traits::pointer _Ptr;
439 template<
typename _Tp,
typename _Alloc = allocator<_Tp>>
443 "std::forward_list must have a non-const, non-volatile value_type");
444#if __cplusplus > 201703L || defined __STRICT_ANSI__
446 "std::forward_list must have the same value_type as its allocator");
452 typedef typename _Base::_Node _Node;
453 typedef typename _Base::_Node_alloc_type _Node_alloc_type;
459 typedef _Tp value_type;
460 typedef typename _Alloc_traits::pointer pointer;
461 typedef typename _Alloc_traits::const_pointer const_pointer;
462 typedef value_type& reference;
463 typedef const value_type& const_reference;
465 typedef typename _Base::iterator iterator;
467 typedef std::size_t size_type;
468 typedef std::ptrdiff_t difference_type;
469 typedef _Alloc allocator_type;
484 :
_Base(_Node_alloc_type(__al))
493 const __type_identity_t<_Alloc>& __al)
494 :
_Base(_Node_alloc_type(__al))
495 { _M_range_initialize(__list.
begin(), __list.
end()); }
505 std::__make_move_if_noexcept_iterator(__list.begin()),
506 std::__make_move_if_noexcept_iterator(__list.end()));
522 const __type_identity_t<_Alloc>& __al)
523 noexcept(_Node_alloc_traits::_S_always_equal())
538 :
_Base(_Node_alloc_type(__al))
539 { _M_default_initialize(__n); }
551 const _Alloc& __al = _Alloc())
552 :
_Base(_Node_alloc_type(__al))
553 { _M_fill_initialize(__n, __value); }
565 template<
typename _InputIterator,
566 typename = std::_RequireInputIter<_InputIterator>>
568 const _Alloc& __al = _Alloc())
569 :
_Base(_Node_alloc_type(__al))
570 { _M_range_initialize(__first, __last); }
572#if __glibcxx_ranges_to_container
581 template<__detail::__container_compatible_range<_Tp> _Rg>
582 forward_list(from_range_t, _Rg&& __rg,
const _Alloc& __a = _Alloc())
583 : _Base(_Node_alloc_type(__a))
585 _Node_base* __to = &this->_M_impl._M_head;
586 auto __first = ranges::begin(__rg);
587 const auto __last = ranges::end(__rg);
588 for (; __first != __last; ++__first)
590 __to->_M_next = this->_M_create_node(*__first);
591 __to = __to->_M_next;
603 __list._M_get_Node_allocator()))
604 { _M_range_initialize(__list.
begin(), __list.
end()); }
626 const _Alloc& __al = _Alloc())
627 :
_Base(_Node_alloc_type(__al))
628 { _M_range_initialize(__il.begin(), __il.end()); }
648#pragma GCC diagnostic push
649#pragma GCC diagnostic ignored "-Wc++17-extensions"
664 noexcept(_Node_alloc_traits::_S_nothrow_move())
666 constexpr bool __move_storage =
667 _Node_alloc_traits::_S_propagate_on_move_assign()
668 || _Node_alloc_traits::_S_always_equal();
669 if constexpr (!__move_storage)
671 if (__list._M_get_Node_allocator() != this->_M_get_Node_allocator())
675 this->
assign(std::make_move_iterator(__list.begin()),
676 std::make_move_iterator(__list.end()));
682 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
683 __list._M_impl._M_head._M_next =
nullptr;
684 if constexpr (_Node_alloc_traits::_S_propagate_on_move_assign())
685 this->_M_get_Node_allocator()
686 =
std::move(__list._M_get_Node_allocator());
717 template<
typename _InputIterator,
718 typename = std::_RequireInputIter<_InputIterator>>
720 assign(_InputIterator __first, _InputIterator __last)
725 auto __curr =
begin();
727 while (__curr != __end && __first != __last)
734 if (__first != __last)
736 else if (__curr != __end)
745#pragma GCC diagnostic pop
747#if __glibcxx_ranges_to_container
752 template<__detail::__container_compatible_range<_Tp> _Rg>
754 assign_range(_Rg&& __rg)
756 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
758 auto __first = ranges::begin(__rg);
759 const auto __last = ranges::end(__rg);
764 while (__curr != __end && __first != __last)
775 insert_range_after(__prev,
776 ranges::subrange(
std::move(__first), __last));
780#pragma GCC diagnostic push
781#pragma GCC diagnostic ignored "-Wc++17-extensions"
798 auto __curr =
begin();
800 while (__curr != __end && __n > 0)
809 else if (__curr != __end)
818#pragma GCC diagnostic pop
830 {
assign(__il.begin(), __il.end()); }
835 {
return allocator_type(this->_M_get_Node_allocator()); }
846 {
return iterator(&this->_M_impl._M_head); }
865 {
return iterator(this->_M_impl._M_head._M_next); }
885 {
return iterator(
nullptr); }
934 {
return this->_M_impl._M_head._M_next ==
nullptr; }
954 __glibcxx_requires_nonempty();
955 _Node* __front =
static_cast<_Node*
>(this->_M_impl._M_head._M_next);
956 return *__front->_M_valptr();
967 __glibcxx_requires_nonempty();
968 _Node* __front =
static_cast<_Node*
>(this->_M_impl._M_head._M_next);
969 return *__front->_M_valptr();
985 template<
typename... _Args>
986#if __cplusplus > 201402L
994 std::forward<_Args>(__args)...);
995#if __cplusplus > 201402L
1021#if __glibcxx_ranges_to_container
1037 template<__detail::__container_compatible_range<_Tp> _Rg>
1039 prepend_range(_Rg&& __rg)
1041 forward_list __tmp(from_range, std::forward<_Rg>(__rg),
1062 { this->_M_erase_after(&this->_M_impl._M_head); }
1077 template<
typename... _Args>
1080 {
return iterator(this->_M_insert_after(__pos,
1081 std::forward<_Args>(__args)...)); }
1097 {
return iterator(this->_M_insert_after(__pos, __val)); }
1122 insert_after(const_iterator __pos, size_type __n,
const _Tp& __val);
1139 template<
typename _InputIterator,
1140 typename = std::_RequireInputIter<_InputIterator>>
1143 _InputIterator __first, _InputIterator __last);
1162 {
return insert_after(__pos, __il.begin(), __il.end()); }
1164#if __glibcxx_ranges_to_container
1180 template<__detail::__container_compatible_range<_Tp> _Rg>
1182 insert_range_after(const_iterator __position, _Rg&& __rg)
1184 forward_list __tmp(from_range, std::forward<_Rg>(__rg),
1186 return _M_splice_after(__position, __tmp.before_begin(), __tmp.end());
1209 {
return iterator(this->_M_erase_after(
const_cast<_Node_base*
>
1210 (__pos._M_node))); }
1233 {
return iterator(this->_M_erase_after(
const_cast<_Node_base*
>
1236 (__last._M_node))); }
1253 std::swap(this->_M_impl._M_head._M_next,
1254 __list._M_impl._M_head._M_next);
1255 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1256 __list._M_get_Node_allocator());
1286 resize(size_type __sz,
const value_type& __val);
1298 { this->_M_erase_after(&this->_M_impl._M_head,
nullptr); }
1316 if (!__list.empty())
1317 _M_splice_after(__pos, __list.before_begin(), __list.end());
1336 const_iterator __i)
noexcept;
1340 const_iterator __i)
noexcept
1360 { _M_splice_after(__pos, __before, __last); }
1365 { _M_splice_after(__pos, __before, __last); }
1369#ifdef __glibcxx_list_remove_return_type
1370 using __remove_return_type = size_type;
1371# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \
1372 __attribute__((__abi_tag__("__cxx20")))
1374 using __remove_return_type = void;
1375# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1390 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1391 __remove_return_type
1392 remove(
const _Tp& __val);
1405 template<
typename _Pred>
1406 __remove_return_type
1419 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1420 __remove_return_type
1424#undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1438 template<
typename _BinPred>
1439 __remove_return_type
1470 template<
typename _Comp>
1474 template<
typename _Comp>
1495 template<
typename _Comp>
1506 { this->_M_impl._M_head._M_reverse_after(); }
1510 template<
typename _InputIterator>
1512 _M_range_initialize(_InputIterator __first, _InputIterator __last);
1517 _M_fill_initialize(size_type __n,
const value_type& __value);
1521 _M_splice_after(const_iterator __pos, const_iterator __before,
1522 const_iterator __last);
1526 _M_default_initialize(size_type __n);
1530 _M_default_insert_after(const_iterator __pos, size_type __n);
1532#if ! _GLIBCXX_INLINE_VERSION
1544 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
1545 __list._M_impl._M_head._M_next =
nullptr;
1546 std::__alloc_on_move(this->_M_get_Node_allocator(),
1547 __list._M_get_Node_allocator());
1553 if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
1558 this->
assign(std::make_move_iterator(__list.begin()),
1559 std::make_move_iterator(__list.end()));
1563 _M_assign_n(size_type __n,
const _Tp& __val,
true_type)
1566 auto __curr =
begin();
1568 while (__curr != __end && __n > 0)
1577 else if (__curr != __end)
1582 _M_assign_n(size_type __n,
const _Tp& __val,
false_type)
1590#if __cpp_deduction_guides >= 201606
1591 template<
typename _InputIterator,
typename _ValT
1592 =
typename iterator_traits<_InputIterator>::value_type,
1593 typename _Allocator = allocator<_ValT>,
1594 typename = _RequireInputIter<_InputIterator>,
1595 typename = _RequireAllocator<_Allocator>>
1596 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator())
1597 -> forward_list<_ValT, _Allocator>;
1599#if __glibcxx_ranges_to_container
1600 template<ranges::input_range _Rg,
1601 typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
1602 forward_list(from_range_t, _Rg&&, _Allocator = _Allocator())
1603 -> forward_list<ranges::range_value_t<_Rg>, _Allocator>;
1617 template<
typename _Tp,
typename _Alloc>
1623#if __cpp_lib_three_way_comparison
1635 template<
typename _Tp,
typename _Alloc>
1637 inline __detail::__synth3way_t<_Tp>
1642 __y.begin(), __y.end(),
1643 __detail::__synth3way);
1658 template<
typename _Tp,
typename _Alloc>
1661 operator<(
const forward_list<_Tp, _Alloc>& __lx,
1662 const forward_list<_Tp, _Alloc>& __ly)
1663 {
return std::lexicographical_compare(__lx.cbegin(), __lx.cend(),
1664 __ly.cbegin(), __ly.cend()); }
1667 template<
typename _Tp,
typename _Alloc>
1670 operator!=(
const forward_list<_Tp, _Alloc>& __lx,
1671 const forward_list<_Tp, _Alloc>& __ly)
1672 {
return !(__lx == __ly); }
1675 template<
typename _Tp,
typename _Alloc>
1678 operator>(
const forward_list<_Tp, _Alloc>& __lx,
1679 const forward_list<_Tp, _Alloc>& __ly)
1680 {
return (__ly < __lx); }
1683 template<
typename _Tp,
typename _Alloc>
1686 operator>=(
const forward_list<_Tp, _Alloc>& __lx,
1687 const forward_list<_Tp, _Alloc>& __ly)
1688 {
return !(__lx < __ly); }
1691 template<
typename _Tp,
typename _Alloc>
1694 operator<=(
const forward_list<_Tp, _Alloc>& __lx,
1695 const forward_list<_Tp, _Alloc>& __ly)
1696 {
return !(__ly < __lx); }
1700 template<
typename _Tp,
typename _Alloc>
1704 noexcept(
noexcept(__lx.swap(__ly)))
1705 { __lx.swap(__ly); }
1707_GLIBCXX_END_NAMESPACE_CONTAINER
1708_GLIBCXX_END_NAMESPACE_VERSION
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
ISO C++ entities toplevel namespace is std.
is_nothrow_default_constructible
Uniform interface to all allocator types.
A helper basic node class for forward_list. This is just a linked list with nothing inside it....
A helper node class for forward_list. This is just a linked list with uninitialized storage for a dat...
A forward_list::iterator.
friend bool operator==(const _Self &__x, const _Self &__y) noexcept
Forward list iterator equality comparison.
A forward_list::const_iterator.
friend bool operator==(const _Self &__x, const _Self &__y) noexcept
Forward list const_iterator equality comparison.
Base class for forward_list.
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
__remove_return_type unique(_BinPred __binary_pred)
Remove consecutive elements satisfying a predicate.
iterator begin() noexcept
const_iterator before_begin() const noexcept
void reverse() noexcept
Reverse the elements in list.
forward_list()=default
Creates a forward_list with no elements.
~forward_list() noexcept
The forward_list dtor.
iterator erase_after(const_iterator __pos)
Removes the element pointed to by the iterator following pos.
void swap(forward_list &__list) noexcept
Swaps data with another forward_list.
const_reference front() const
void merge(forward_list &&__list)
Merge sorted lists.
forward_list(const _Alloc &__al) noexcept
Creates a forward_list with no elements.
void sort()
Sort the elements of the list.
iterator before_begin() noexcept
forward_list(const forward_list &__list, const __type_identity_t< _Alloc > &__al)
Copy constructor with allocator argument.
iterator emplace_after(const_iterator __pos, _Args &&... __args)
Constructs object in forward_list after the specified iterator.
forward_list(const forward_list &__list)
The forward_list copy constructor.
iterator insert_after(const_iterator __pos, const _Tp &__val)
Inserts given value into forward_list after specified iterator.
forward_list & operator=(forward_list &&__list) noexcept(_Node_alloc_traits::_S_nothrow_move())
The forward_list move assignment operator.
void resize(size_type __sz)
Resizes the forward_list to the specified number of elements.
forward_list & operator=(const forward_list &__list)
The forward_list assignment operator.
__remove_return_type remove_if(_Pred __pred)
Remove all elements satisfying a predicate.
forward_list(size_type __n, const _Tp &__value, const _Alloc &__al=_Alloc())
Creates a forward_list with copies of an exemplar element.
void assign(size_type __n, const _Tp &__val)
Assigns a given value to a forward_list.
const_iterator begin() const noexcept
void splice_after(const_iterator __pos, forward_list &&__list) noexcept
Insert contents of another forward_list.
const_iterator cbefore_begin() const noexcept
forward_list & operator=(std::initializer_list< _Tp > __il)
The forward_list initializer list assignment operator.
forward_list(std::initializer_list< _Tp > __il, const _Alloc &__al=_Alloc())
Builds a forward_list from an initializer_list.
reference emplace_front(_Args &&... __args)
Constructs object in forward_list at the front of the list.
forward_list(size_type __n, const _Alloc &__al=_Alloc())
Creates a forward_list with default constructed elements.
iterator insert_after(const_iterator __pos, std::initializer_list< _Tp > __il)
Inserts the contents of an initializer_list into forward_list after the specified iterator.
const_iterator end() const noexcept
void splice_after(const_iterator __pos, forward_list &&, const_iterator __before, const_iterator __last) noexcept
Insert range from another forward_list.
forward_list(forward_list &&__list, const __type_identity_t< _Alloc > &__al) noexcept(_Node_alloc_traits::_S_always_equal())
Move constructor with allocator argument.
iterator erase_after(const_iterator __pos, const_iterator __last)
Remove a range of elements.
__remove_return_type unique()
Remove consecutive duplicate elements.
void clear() noexcept
Erases all the elements.
__remove_return_type remove(const _Tp &__val)
Remove all elements equal to value.
const_iterator cend() const noexcept
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a forward_list.
bool empty() const noexcept
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
void push_front(const _Tp &__val)
Add data to the front of the forward_list.
forward_list(forward_list &&)=default
The forward_list move constructor.
forward_list(_InputIterator __first, _InputIterator __last, const _Alloc &__al=_Alloc())
Builds a forward_list from a range.
void splice_after(const_iterator __pos, forward_list &, const_iterator __before, const_iterator __last) noexcept
Insert range from another forward_list.
const_iterator cbegin() const noexcept
void pop_front()
Removes first element.
void assign(std::initializer_list< _Tp > __il)
Assigns an initializer_list to a forward_list.
size_type max_size() const noexcept
Uniform interface to all pointer-like types.
One of the comparison functors.
One of the comparison functors.
Forward iterators support a superset of input iterator operations.
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.