30 #ifndef _FORWARD_LIST_H
31 #define _FORWARD_LIST_H 1
33 #pragma GCC system_header
44 namespace std _GLIBCXX_VISIBILITY(default)
46 _GLIBCXX_BEGIN_NAMESPACE_VERSION
47 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
58 : _M_next(__x._M_next)
59 { __x._M_next =
nullptr; }
67 _M_next = __x._M_next;
68 __x._M_next =
nullptr;
81 __begin->_M_next = __end->_M_next;
82 __end->_M_next = _M_next;
85 __begin->_M_next =
nullptr;
91 _M_reverse_after() noexcept
100 __tail->_M_next = __temp->_M_next;
101 _M_next->_M_next = __keep;
112 template<
typename _Tp>
118 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
122 {
return _M_storage._M_ptr(); }
125 _M_valptr()
const noexcept
126 {
return _M_storage._M_ptr(); }
134 template<
typename _Tp>
140 typedef _Tp value_type;
141 typedef _Tp* pointer;
142 typedef _Tp& reference;
143 typedef ptrdiff_t difference_type;
155 operator*()
const noexcept
156 {
return *
static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
160 operator->()
const noexcept
161 {
return static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
164 operator++() noexcept
166 _M_node = _M_node->_M_next;
171 operator++(
int) noexcept
174 _M_node = _M_node->_M_next;
184 {
return __x._M_node == __y._M_node; }
186 #if __cpp_impl_three_way_comparison < 201907L
192 operator!=(
const _Self& __x,
const _Self& __y) noexcept
193 {
return __x._M_node != __y._M_node; }
197 _M_next() const noexcept
200 return _Fwd_list_iterator(_M_node->_M_next);
202 return _Fwd_list_iterator(
nullptr);
205 _Fwd_list_node_base* _M_node;
213 template<
typename _Tp>
220 typedef _Tp value_type;
221 typedef const _Tp* pointer;
222 typedef const _Tp& reference;
223 typedef ptrdiff_t difference_type;
234 : _M_node(__iter._M_node) { }
238 operator*()
const noexcept
239 {
return *
static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
243 operator->()
const noexcept
244 {
return static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
247 operator++() noexcept
249 _M_node = _M_node->_M_next;
254 operator++(
int) noexcept
257 _M_node = _M_node->_M_next;
267 {
return __x._M_node == __y._M_node; }
269 #if __cpp_impl_three_way_comparison < 201907L
275 operator!=(
const _Self& __x,
const _Self& __y) noexcept
276 {
return __x._M_node != __y._M_node; }
280 _M_next() const noexcept
283 return _Fwd_list_const_iterator(_M_node->_M_next);
285 return _Fwd_list_const_iterator(
nullptr);
288 const _Fwd_list_node_base* _M_node;
294 template<
typename _Tp,
typename _Alloc>
298 typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
301 struct _Fwd_list_impl
302 :
public _Node_alloc_type
308 : _Node_alloc_type(), _M_head()
311 _Fwd_list_impl(_Fwd_list_impl&&) =
default;
313 _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a)
317 _Fwd_list_impl(_Node_alloc_type&& __a)
318 : _Node_alloc_type(
std::move(__a)), _M_head()
322 _Fwd_list_impl _M_impl;
330 _M_get_Node_allocator() noexcept
331 {
return this->_M_impl; }
333 const _Node_alloc_type&
334 _M_get_Node_allocator()
const noexcept
335 {
return this->_M_impl; }
354 { _M_erase_after(&_M_impl._M_head,
nullptr); }
361 return std::__to_address(__ptr);
364 template<
typename... _Args>
366 _M_create_node(_Args&&... __args)
368 _Node* __node = this->_M_get_node();
371 ::new ((
void*)__node)
_Node;
372 _Node_alloc_traits::construct(_M_get_Node_allocator(),
374 std::forward<_Args>(__args)...);
378 this->_M_put_node(__node);
379 __throw_exception_again;
384 template<
typename... _Args>
389 _M_put_node(
_Node* __p)
391 typedef typename _Node_alloc_traits::pointer _Ptr;
430 template<
typename _Tp,
typename _Alloc = allocator<_Tp>>
433 static_assert(
is_same<
typename remove_cv<_Tp>::type, _Tp>::value,
434 "std::forward_list must have a non-const, non-volatile value_type");
435 #if __cplusplus > 201703L || defined __STRICT_ANSI__
437 "std::forward_list must have the same value_type as its allocator");
444 typedef typename _Base::_Node_alloc_type _Node_alloc_type;
450 typedef _Tp value_type;
453 typedef value_type& reference;
454 typedef const value_type& const_reference;
458 typedef std::size_t size_type;
459 typedef std::ptrdiff_t difference_type;
460 typedef _Alloc allocator_type;
475 :
_Base(_Node_alloc_type(__al))
484 const __type_identity_t<_Alloc>& __al)
485 :
_Base(_Node_alloc_type(__al))
486 { _M_range_initialize(__list.
begin(), __list.
end()); }
496 std::__make_move_if_noexcept_iterator(__list.begin()),
497 std::__make_move_if_noexcept_iterator(__list.end()));
513 const __type_identity_t<_Alloc>& __al)
514 noexcept(_Node_alloc_traits::_S_always_equal())
529 :
_Base(_Node_alloc_type(__al))
530 { _M_default_initialize(__n); }
542 const _Alloc& __al = _Alloc())
543 :
_Base(_Node_alloc_type(__al))
544 { _M_fill_initialize(__n, __value); }
556 template<
typename _InputIterator,
557 typename = std::_RequireInputIter<_InputIterator>>
559 const _Alloc& __al = _Alloc())
560 :
_Base(_Node_alloc_type(__al))
561 { _M_range_initialize(__first, __last); }
570 __list._M_get_Node_allocator()))
571 { _M_range_initialize(__list.
begin(), __list.
end()); }
593 const _Alloc& __al = _Alloc())
594 :
_Base(_Node_alloc_type(__al))
595 { _M_range_initialize(__il.begin(), __il.end()); }
629 noexcept(_Node_alloc_traits::_S_nothrow_move())
631 constexpr
bool __move_storage =
632 _Node_alloc_traits::_S_propagate_on_move_assign()
633 || _Node_alloc_traits::_S_always_equal();
634 _M_move_assign(
std::move(__list), __bool_constant<__move_storage>());
665 template<
typename _InputIterator,
666 typename = std::_RequireInputIter<_InputIterator>>
668 assign(_InputIterator __first, _InputIterator __last)
671 _M_assign(__first, __last, __assignable());
698 {
assign(__il.begin(), __il.end()); }
703 {
return allocator_type(this->_M_get_Node_allocator()); }
714 {
return iterator(&this->_M_impl._M_head); }
733 {
return iterator(this->_M_impl._M_head._M_next); }
802 {
return this->_M_impl._M_head._M_next ==
nullptr; }
822 _Node* __front =
static_cast<_Node*
>(this->_M_impl._M_head._M_next);
823 return *__front->_M_valptr();
834 _Node* __front =
static_cast<_Node*
>(this->_M_impl._M_head._M_next);
835 return *__front->_M_valptr();
851 template<
typename... _Args>
852 #if __cplusplus > 201402L
860 std::forward<_Args>(__args)...);
861 #if __cplusplus > 201402L
901 { this->_M_erase_after(&this->_M_impl._M_head); }
916 template<
typename... _Args>
919 {
return iterator(this->_M_insert_after(__pos,
920 std::forward<_Args>(__args)...)); }
936 {
return iterator(this->_M_insert_after(__pos, __val)); }
961 insert_after(const_iterator __pos, size_type __n,
const _Tp& __val);
978 template<
typename _InputIterator,
979 typename = std::_RequireInputIter<_InputIterator>>
982 _InputIterator __first, _InputIterator __last);
1001 {
return insert_after(__pos, __il.begin(), __il.end()); }
1023 (__pos._M_node))); }
1048 (__last._M_node))); }
1065 std::swap(this->_M_impl._M_head._M_next,
1066 __list._M_impl._M_head._M_next);
1067 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1068 __list._M_get_Node_allocator());
1098 resize(size_type __sz,
const value_type& __val);
1110 { this->_M_erase_after(&this->_M_impl._M_head,
nullptr); }
1128 if (!__list.empty())
1129 _M_splice_after(__pos, __list.before_begin(), __list.end());
1148 const_iterator __i) noexcept;
1152 const_iterator __i) noexcept
1172 { _M_splice_after(__pos, __before, __last); }
1177 { _M_splice_after(__pos, __before, __last); }
1181 #if __cplusplus > 201703L
1182 # define __cpp_lib_list_remove_return_type 201806L
1183 using __remove_return_type = size_type;
1184 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \
1185 __attribute__((__abi_tag__("__cxx20")))
1187 using __remove_return_type = void;
1188 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1203 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1204 __remove_return_type
1205 remove(
const _Tp& __val);
1218 template<
typename _Pred>
1219 __remove_return_type
1232 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1233 __remove_return_type
1237 #undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1251 template<
typename _BinPred>
1252 __remove_return_type
1283 template<
typename _Comp>
1287 template<
typename _Comp>
1308 template<
typename _Comp>
1319 { this->_M_impl._M_head._M_reverse_after(); }
1323 template<
typename _InputIterator>
1325 _M_range_initialize(_InputIterator __first, _InputIterator __last);
1330 _M_fill_initialize(size_type __n,
const value_type& __value);
1334 _M_splice_after(const_iterator __pos, const_iterator __before,
1335 const_iterator __last);
1339 _M_default_initialize(size_type __n);
1343 _M_default_insert_after(const_iterator __pos, size_type __n);
1350 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
1351 __list._M_impl._M_head._M_next =
nullptr;
1352 std::__alloc_on_move(this->_M_get_Node_allocator(),
1353 __list._M_get_Node_allocator());
1360 if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
1365 this->
assign(std::make_move_iterator(__list.begin()),
1366 std::make_move_iterator(__list.end()));
1371 template<
typename _InputIterator>
1373 _M_assign(_InputIterator __first, _InputIterator __last,
true_type)
1376 auto __curr =
begin();
1378 while (__curr != __end && __first != __last)
1385 if (__first != __last)
1387 else if (__curr != __end)
1393 template<
typename _InputIterator>
1395 _M_assign(_InputIterator __first, _InputIterator __last,
false_type)
1403 _M_assign_n(size_type __n,
const _Tp& __val,
true_type)
1406 auto __curr =
begin();
1408 while (__curr != __end && __n > 0)
1417 else if (__curr != __end)
1423 _M_assign_n(size_type __n,
const _Tp& __val,
false_type)
1430 #if __cpp_deduction_guides >= 201606
1431 template<
typename _InputIterator,
typename _ValT
1432 =
typename iterator_traits<_InputIterator>::value_type,
1433 typename _Allocator = allocator<_ValT>,
1434 typename = _RequireInputIter<_InputIterator>,
1435 typename = _RequireAllocator<_Allocator>>
1436 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator())
1437 -> forward_list<_ValT, _Allocator>;
1450 template<
typename _Tp,
typename _Alloc>
1453 operator==(
const forward_list<_Tp, _Alloc>& __lx,
1454 const forward_list<_Tp, _Alloc>& __ly);
1456 #if __cpp_lib_three_way_comparison
1468 template<
typename _Tp,
typename _Alloc>
1470 inline __detail::__synth3way_t<_Tp>
1471 operator<=>(
const forward_list<_Tp, _Alloc>& __x,
1472 const forward_list<_Tp, _Alloc>& __y)
1474 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
1475 __y.begin(), __y.end(),
1476 __detail::__synth3way);
1491 template<
typename _Tp,
typename _Alloc>
1500 template<
typename _Tp,
typename _Alloc>
1505 {
return !(__lx == __ly); }
1508 template<
typename _Tp,
typename _Alloc>
1513 {
return (__ly < __lx); }
1516 template<
typename _Tp,
typename _Alloc>
1521 {
return !(__lx < __ly); }
1524 template<
typename _Tp,
typename _Alloc>
1529 {
return !(__ly < __lx); }
1530 #endif // three-way comparison
1533 template<
typename _Tp,
typename _Alloc>
1537 noexcept(noexcept(__lx.swap(__ly)))
1538 { __lx.swap(__ly); }
1540 _GLIBCXX_END_NAMESPACE_CONTAINER
1541 _GLIBCXX_END_NAMESPACE_VERSION
1544 #endif // _FORWARD_LIST_H