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;
154 operator*()
const noexcept
155 {
return *
static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
158 operator->()
const noexcept
159 {
return static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
162 operator++() noexcept
164 _M_node = _M_node->_M_next;
169 operator++(
int) noexcept
172 _M_node = _M_node->_M_next;
181 {
return __x._M_node == __y._M_node; }
183 #if __cpp_impl_three_way_comparison < 201907L
189 {
return __x._M_node != __y._M_node; }
193 _M_next() const noexcept
201 _Fwd_list_node_base* _M_node;
209 template<
typename _Tp>
216 typedef _Tp value_type;
217 typedef const _Tp* pointer;
218 typedef const _Tp& reference;
219 typedef ptrdiff_t difference_type;
230 : _M_node(__iter._M_node) { }
233 operator*()
const noexcept
234 {
return *
static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
237 operator->()
const noexcept
238 {
return static_cast<_Node*
>(this->_M_node)->_M_valptr(); }
241 operator++() noexcept
243 _M_node = _M_node->_M_next;
248 operator++(
int) noexcept
251 _M_node = _M_node->_M_next;
260 {
return __x._M_node == __y._M_node; }
262 #if __cpp_impl_three_way_comparison < 201907L
268 {
return __x._M_node != __y._M_node; }
272 _M_next() const noexcept
280 const _Fwd_list_node_base* _M_node;
286 template<
typename _Tp,
typename _Alloc>
290 typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
293 struct _Fwd_list_impl
294 :
public _Node_alloc_type
300 : _Node_alloc_type(), _M_head()
303 _Fwd_list_impl(_Fwd_list_impl&&) =
default;
305 _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a)
309 _Fwd_list_impl(_Node_alloc_type&& __a)
310 : _Node_alloc_type(
std::move(__a)), _M_head()
314 _Fwd_list_impl _M_impl;
322 _M_get_Node_allocator() noexcept
323 {
return this->_M_impl; }
325 const _Node_alloc_type&
326 _M_get_Node_allocator()
const noexcept
327 {
return this->_M_impl; }
346 { _M_erase_after(&_M_impl._M_head,
nullptr); }
353 return std::__to_address(__ptr);
356 template<
typename... _Args>
358 _M_create_node(_Args&&... __args)
360 _Node* __node = this->_M_get_node();
363 ::new ((
void*)__node)
_Node;
364 _Node_alloc_traits::construct(_M_get_Node_allocator(),
366 std::forward<_Args>(__args)...);
370 this->_M_put_node(__node);
371 __throw_exception_again;
376 template<
typename... _Args>
381 _M_put_node(
_Node* __p)
383 typedef typename _Node_alloc_traits::pointer _Ptr;
422 template<
typename _Tp,
typename _Alloc = allocator<_Tp>>
425 static_assert(
is_same<
typename remove_cv<_Tp>::type, _Tp>::value,
426 "std::forward_list must have a non-const, non-volatile value_type");
427 #if __cplusplus > 201703L || defined __STRICT_ANSI__
429 "std::forward_list must have the same value_type as its allocator");
436 typedef typename _Base::_Node_alloc_type _Node_alloc_type;
442 typedef _Tp value_type;
445 typedef value_type& reference;
446 typedef const value_type& const_reference;
450 typedef std::size_t size_type;
451 typedef std::ptrdiff_t difference_type;
452 typedef _Alloc allocator_type;
467 :
_Base(_Node_alloc_type(__al))
476 :
_Base(_Node_alloc_type(__al))
477 { _M_range_initialize(__list.
begin(), __list.
end()); }
487 std::__make_move_if_noexcept_iterator(__list.begin()),
488 std::__make_move_if_noexcept_iterator(__list.end()));
504 noexcept(_Node_alloc_traits::_S_always_equal())
519 :
_Base(_Node_alloc_type(__al))
520 { _M_default_initialize(__n); }
532 const _Alloc& __al = _Alloc())
533 :
_Base(_Node_alloc_type(__al))
534 { _M_fill_initialize(__n, __value); }
546 template<
typename _InputIterator,
547 typename = std::_RequireInputIter<_InputIterator>>
549 const _Alloc& __al = _Alloc())
550 :
_Base(_Node_alloc_type(__al))
551 { _M_range_initialize(__first, __last); }
560 __list._M_get_Node_allocator()))
561 { _M_range_initialize(__list.
begin(), __list.
end()); }
583 const _Alloc& __al = _Alloc())
584 :
_Base(_Node_alloc_type(__al))
585 { _M_range_initialize(__il.begin(), __il.end()); }
619 noexcept(_Node_alloc_traits::_S_nothrow_move())
621 constexpr
bool __move_storage =
622 _Node_alloc_traits::_S_propagate_on_move_assign()
623 || _Node_alloc_traits::_S_always_equal();
655 template<
typename _InputIterator,
656 typename = std::_RequireInputIter<_InputIterator>>
658 assign(_InputIterator __first, _InputIterator __last)
661 _M_assign(__first, __last, __assignable());
688 {
assign(__il.begin(), __il.end()); }
693 {
return allocator_type(this->_M_get_Node_allocator()); }
703 {
return iterator(&this->_M_impl._M_head); }
720 {
return iterator(this->_M_impl._M_head._M_next); }
780 _GLIBCXX_NODISCARD
bool
782 {
return this->_M_impl._M_head._M_next ==
nullptr; }
800 _Node* __front =
static_cast<_Node*
>(this->_M_impl._M_head._M_next);
801 return *__front->_M_valptr();
811 _Node* __front =
static_cast<_Node*
>(this->_M_impl._M_head._M_next);
812 return *__front->_M_valptr();
828 template<
typename... _Args>
829 #if __cplusplus > 201402L
837 std::forward<_Args>(__args)...);
838 #if __cplusplus > 201402L
878 { this->_M_erase_after(&this->_M_impl._M_head); }
893 template<
typename... _Args>
896 {
return iterator(this->_M_insert_after(__pos,
897 std::forward<_Args>(__args)...)); }
913 {
return iterator(this->_M_insert_after(__pos, __val)); }
938 insert_after(const_iterator __pos, size_type __n,
const _Tp& __val);
955 template<
typename _InputIterator,
956 typename = std::_RequireInputIter<_InputIterator>>
959 _InputIterator __first, _InputIterator __last);
978 {
return insert_after(__pos, __il.begin(), __il.end()); }
1000 (__pos._M_node))); }
1025 (__last._M_node))); }
1042 std::swap(this->_M_impl._M_head._M_next,
1043 __list._M_impl._M_head._M_next);
1044 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1045 __list._M_get_Node_allocator());
1075 resize(size_type __sz,
const value_type& __val);
1087 { this->_M_erase_after(&this->_M_impl._M_head,
nullptr); }
1105 if (!__list.empty())
1106 _M_splice_after(__pos, __list.before_begin(), __list.end());
1125 const_iterator __i) noexcept;
1129 const_iterator __i) noexcept
1149 { _M_splice_after(__pos, __before, __last); }
1154 { _M_splice_after(__pos, __before, __last); }
1158 #if __cplusplus > 201703L
1159 # define __cpp_lib_list_remove_return_type 201806L
1160 using __remove_return_type = size_type;
1161 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \
1162 __attribute__((__abi_tag__("__cxx20")))
1164 using __remove_return_type = void;
1165 # define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1180 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1181 __remove_return_type
1182 remove(
const _Tp& __val);
1195 template<
typename _Pred>
1196 __remove_return_type
1209 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1210 __remove_return_type
1214 #undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
1228 template<
typename _BinPred>
1229 __remove_return_type
1230 unique(_BinPred __binary_pred);
1260 template<
typename _Comp>
1264 template<
typename _Comp>
1285 template<
typename _Comp>
1296 { this->_M_impl._M_head._M_reverse_after(); }
1300 template<
typename _InputIterator>
1302 _M_range_initialize(_InputIterator __first, _InputIterator __last);
1307 _M_fill_initialize(size_type __n,
const value_type& __value);
1311 _M_splice_after(const_iterator __pos, const_iterator __before,
1312 const_iterator __last);
1316 _M_default_initialize(size_type __n);
1320 _M_default_insert_after(const_iterator __pos, size_type __n);
1327 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next;
1328 __list._M_impl._M_head._M_next =
nullptr;
1329 std::__alloc_on_move(this->_M_get_Node_allocator(),
1330 __list._M_get_Node_allocator());
1337 if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
1342 this->
assign(std::make_move_iterator(__list.begin()),
1343 std::make_move_iterator(__list.end()));
1348 template<
typename _InputIterator>
1350 _M_assign(_InputIterator __first, _InputIterator __last,
true_type)
1353 auto __curr =
begin();
1355 while (__curr != __end && __first != __last)
1362 if (__first != __last)
1364 else if (__curr != __end)
1370 template<
typename _InputIterator>
1372 _M_assign(_InputIterator __first, _InputIterator __last,
false_type)
1380 _M_assign_n(size_type __n,
const _Tp& __val,
true_type)
1383 auto __curr =
begin();
1385 while (__curr != __end && __n > 0)
1394 else if (__curr != __end)
1400 _M_assign_n(size_type __n,
const _Tp& __val,
false_type)
1407 #if __cpp_deduction_guides >= 201606
1408 template<
typename _InputIterator,
typename _ValT
1409 =
typename iterator_traits<_InputIterator>::value_type,
1410 typename _Allocator = allocator<_ValT>,
1411 typename = _RequireInputIter<_InputIterator>,
1412 typename = _RequireAllocator<_Allocator>>
1413 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator())
1414 -> forward_list<_ValT, _Allocator>;
1427 template<
typename _Tp,
typename _Alloc>
1429 operator==(
const forward_list<_Tp, _Alloc>& __lx,
1430 const forward_list<_Tp, _Alloc>& __ly);
1432 #if __cpp_lib_three_way_comparison
1444 template<
typename _Tp,
typename _Alloc>
1445 inline __detail::__synth3way_t<_Tp>
1446 operator<=>(
const forward_list<_Tp, _Alloc>& __x,
1447 const forward_list<_Tp, _Alloc>& __y)
1449 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
1450 __y.begin(), __y.end(),
1451 __detail::__synth3way);
1466 template<
typename _Tp,
typename _Alloc>
1474 template<
typename _Tp,
typename _Alloc>
1478 {
return !(__lx == __ly); }
1481 template<
typename _Tp,
typename _Alloc>
1485 {
return (__ly < __lx); }
1488 template<
typename _Tp,
typename _Alloc>
1492 {
return !(__lx < __ly); }
1495 template<
typename _Tp,
typename _Alloc>
1499 {
return !(__ly < __lx); }
1500 #endif // three-way comparison
1503 template<
typename _Tp,
typename _Alloc>
1507 noexcept(noexcept(__lx.swap(__ly)))
1508 { __lx.swap(__ly); }
1510 _GLIBCXX_END_NAMESPACE_CONTAINER
1511 _GLIBCXX_END_NAMESPACE_VERSION
1514 #endif // _FORWARD_LIST_H