1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_FORWARD_LIST
11#define _LIBCPP_FORWARD_LIST
12
13/*
14 forward_list synopsis
15
16namespace std
17{
18
19template <class T, class Allocator = allocator<T>>
20class forward_list
21{
22public:
23 typedef T value_type;
24 typedef Allocator allocator_type;
25
26 typedef value_type& reference;
27 typedef const value_type& const_reference;
28 typedef typename allocator_traits<allocator_type>::pointer pointer;
29 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
30 typedef typename allocator_traits<allocator_type>::size_type size_type;
31 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
32
33 typedef <details> iterator;
34 typedef <details> const_iterator;
35
36 forward_list()
37 noexcept(is_nothrow_default_constructible<allocator_type>::value);
38 explicit forward_list(const allocator_type& a);
39 explicit forward_list(size_type n);
40 explicit forward_list(size_type n, const allocator_type& a); // C++14
41 forward_list(size_type n, const value_type& v);
42 forward_list(size_type n, const value_type& v, const allocator_type& a);
43 template <class InputIterator>
44 forward_list(InputIterator first, InputIterator last);
45 template <class InputIterator>
46 forward_list(InputIterator first, InputIterator last, const allocator_type& a);
47 template<container-compatible-range<T> R>
48 forward_list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
49 forward_list(const forward_list& x);
50 forward_list(const forward_list& x, const allocator_type& a);
51 forward_list(forward_list&& x)
52 noexcept(is_nothrow_move_constructible<allocator_type>::value);
53 forward_list(forward_list&& x, const allocator_type& a);
54 forward_list(initializer_list<value_type> il);
55 forward_list(initializer_list<value_type> il, const allocator_type& a);
56
57 ~forward_list();
58
59 forward_list& operator=(const forward_list& x);
60 forward_list& operator=(forward_list&& x)
61 noexcept(
62 allocator_type::propagate_on_container_move_assignment::value &&
63 is_nothrow_move_assignable<allocator_type>::value);
64 forward_list& operator=(initializer_list<value_type> il);
65
66 template <class InputIterator>
67 void assign(InputIterator first, InputIterator last);
68 template<container-compatible-range<T> R>
69 void assign_range(R&& rg); // C++23
70 void assign(size_type n, const value_type& v);
71 void assign(initializer_list<value_type> il);
72
73 allocator_type get_allocator() const noexcept;
74
75 iterator begin() noexcept;
76 const_iterator begin() const noexcept;
77 iterator end() noexcept;
78 const_iterator end() const noexcept;
79
80 const_iterator cbegin() const noexcept;
81 const_iterator cend() const noexcept;
82
83 iterator before_begin() noexcept;
84 const_iterator before_begin() const noexcept;
85 const_iterator cbefore_begin() const noexcept;
86
87 bool empty() const noexcept;
88 size_type max_size() const noexcept;
89
90 reference front();
91 const_reference front() const;
92
93 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
94 void push_front(const value_type& v);
95 void push_front(value_type&& v);
96 template<container-compatible-range<T> R>
97 void prepend_range(R&& rg); // C++23
98
99 void pop_front();
100
101 template <class... Args>
102 iterator emplace_after(const_iterator p, Args&&... args);
103 iterator insert_after(const_iterator p, const value_type& v);
104 iterator insert_after(const_iterator p, value_type&& v);
105 iterator insert_after(const_iterator p, size_type n, const value_type& v);
106 template <class InputIterator>
107 iterator insert_after(const_iterator p,
108 InputIterator first, InputIterator last);
109 template<container-compatible-range<T> R>
110 iterator insert_range_after(const_iterator position, R&& rg); // C++23
111 iterator insert_after(const_iterator p, initializer_list<value_type> il);
112
113 iterator erase_after(const_iterator p);
114 iterator erase_after(const_iterator first, const_iterator last);
115
116 void swap(forward_list& x)
117 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
118
119 void resize(size_type n);
120 void resize(size_type n, const value_type& v);
121 void clear() noexcept;
122
123 void splice_after(const_iterator p, forward_list& x);
124 void splice_after(const_iterator p, forward_list&& x);
125 void splice_after(const_iterator p, forward_list& x, const_iterator i);
126 void splice_after(const_iterator p, forward_list&& x, const_iterator i);
127 void splice_after(const_iterator p, forward_list& x,
128 const_iterator first, const_iterator last);
129 void splice_after(const_iterator p, forward_list&& x,
130 const_iterator first, const_iterator last);
131 size_type remove(const value_type& v); // void before C++20
132 template <class Predicate>
133 size_type remove_if(Predicate pred); // void before C++20
134 size_type unique(); // void before C++20
135 template <class BinaryPredicate>
136 size_type unique(BinaryPredicate binary_pred); // void before C++20
137 void merge(forward_list& x);
138 void merge(forward_list&& x);
139 template <class Compare> void merge(forward_list& x, Compare comp);
140 template <class Compare> void merge(forward_list&& x, Compare comp);
141 void sort();
142 template <class Compare> void sort(Compare comp);
143 void reverse() noexcept;
144};
145
146
147template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
148 forward_list(InputIterator, InputIterator, Allocator = Allocator())
149 -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
150
151template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
152 forward_list(from_range_t, R&&, Allocator = Allocator())
153 -> forward_list<ranges::range_value_t<R>, Allocator>; // C++23
154
155template <class T, class Allocator>
156 bool operator==(const forward_list<T, Allocator>& x,
157 const forward_list<T, Allocator>& y);
158
159template <class T, class Allocator>
160 bool operator< (const forward_list<T, Allocator>& x,
161 const forward_list<T, Allocator>& y); // removed in C++20
162
163template <class T, class Allocator>
164 bool operator!=(const forward_list<T, Allocator>& x,
165 const forward_list<T, Allocator>& y); // removed in C++20
166
167template <class T, class Allocator>
168 bool operator> (const forward_list<T, Allocator>& x,
169 const forward_list<T, Allocator>& y); // removed in C++20
170
171template <class T, class Allocator>
172 bool operator>=(const forward_list<T, Allocator>& x,
173 const forward_list<T, Allocator>& y); // removed in C++20
174
175template <class T, class Allocator>
176 bool operator<=(const forward_list<T, Allocator>& x,
177 const forward_list<T, Allocator>& y); // removed in C++20
178
179template<class T, class Allocator>
180 synth-three-way-result<T> operator<=>(const forward_list<T, Allocator>& x,
181 const forward_list<T, Allocator>& y); // since C++20
182
183template <class T, class Allocator>
184 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
185 noexcept(noexcept(x.swap(y)));
186
187template <class T, class Allocator, class U>
188 typename forward_list<T, Allocator>::size_type
189 erase(forward_list<T, Allocator>& c, const U& value); // C++20
190template <class T, class Allocator, class Predicate>
191 typename forward_list<T, Allocator>::size_type
192 erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20
193
194} // std
195
196*/
197
198#include <__algorithm/comp.h>
199#include <__algorithm/lexicographical_compare.h>
200#include <__algorithm/lexicographical_compare_three_way.h>
201#include <__algorithm/min.h>
202#include <__config>
203#include <__iterator/distance.h>
204#include <__iterator/iterator_traits.h>
205#include <__iterator/move_iterator.h>
206#include <__iterator/next.h>
207#include <__memory/addressof.h>
208#include <__memory/allocation_guard.h>
209#include <__memory/allocator.h>
210#include <__memory/allocator_traits.h>
211#include <__memory/compressed_pair.h>
212#include <__memory/construct_at.h>
213#include <__memory/pointer_traits.h>
214#include <__memory/swap_allocator.h>
215#include <__memory_resource/polymorphic_allocator.h>
216#include <__ranges/access.h>
217#include <__ranges/concepts.h>
218#include <__ranges/container_compatible_range.h>
219#include <__ranges/from_range.h>
220#include <__type_traits/conditional.h>
221#include <__type_traits/is_allocator.h>
222#include <__type_traits/is_const.h>
223#include <__type_traits/is_nothrow_assignable.h>
224#include <__type_traits/is_nothrow_constructible.h>
225#include <__type_traits/is_pointer.h>
226#include <__type_traits/is_same.h>
227#include <__type_traits/is_swappable.h>
228#include <__type_traits/type_identity.h>
229#include <__utility/forward.h>
230#include <__utility/move.h>
231#include <limits>
232#include <new> // __launder
233#include <version>
234
235// standard-mandated includes
236
237// [iterator.range]
238#include <__iterator/access.h>
239#include <__iterator/data.h>
240#include <__iterator/empty.h>
241#include <__iterator/reverse_access.h>
242#include <__iterator/size.h>
243
244// [forward.list.syn]
245#include <compare>
246#include <initializer_list>
247
248#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
249# pragma GCC system_header
250#endif
251
252_LIBCPP_PUSH_MACROS
253#include <__undef_macros>
254
255_LIBCPP_BEGIN_NAMESPACE_STD
256
257template <class _Tp, class _VoidPtr>
258struct __forward_list_node;
259template <class _NodePtr>
260struct __forward_begin_node;
261
262template <class>
263struct __forward_list_node_value_type;
264
265template <class _Tp, class _VoidPtr>
266struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
267 typedef _Tp type;
268};
269
270template <class _NodePtr>
271struct __forward_node_traits {
272 typedef __remove_cv_t<typename pointer_traits<_NodePtr>::element_type> __node_type;
273 typedef typename __forward_list_node_value_type<__node_type>::type __node_value_type;
274 typedef _NodePtr __node_pointer;
275 typedef __forward_begin_node<_NodePtr> __begin_node;
276 typedef __rebind_pointer_t<_NodePtr, __begin_node> __begin_node_pointer;
277 typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;
278
279#if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
280 typedef __begin_node_pointer __iter_node_pointer;
281#else
282 typedef __conditional_t<is_pointer<__void_pointer>::value, __begin_node_pointer, __node_pointer> __iter_node_pointer;
283#endif
284
285 typedef __conditional_t<is_same<__iter_node_pointer, __node_pointer>::value, __begin_node_pointer, __node_pointer>
286 __non_iter_node_pointer;
287
288 _LIBCPP_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) { return __p; }
289 _LIBCPP_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
290 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
291 }
292};
293
294template <class _NodePtr>
295struct __forward_begin_node {
296 typedef _NodePtr pointer;
297 typedef __rebind_pointer_t<_NodePtr, __forward_begin_node> __begin_node_pointer;
298
299 pointer __next_;
300
301 _LIBCPP_HIDE_FROM_ABI __forward_begin_node() : __next_(nullptr) {}
302 _LIBCPP_HIDE_FROM_ABI explicit __forward_begin_node(pointer __n) : __next_(__n) {}
303
304 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __next_as_begin() const {
305 return static_cast<__begin_node_pointer>(__next_);
306 }
307};
308
309template <class _Tp, class _VoidPtr>
310using __begin_node_of = __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >;
311
312template <class _Tp, class _VoidPtr>
313struct __forward_list_node : public __begin_node_of<_Tp, _VoidPtr> {
314 typedef _Tp value_type;
315 typedef __begin_node_of<_Tp, _VoidPtr> _Base;
316 typedef typename _Base::pointer _NodePtr;
317
318 // We allow starting the lifetime of nodes without initializing the value held by the node,
319 // since that is handled by the list itself in order to be allocator-aware.
320#ifndef _LIBCPP_CXX03_LANG
321
322private:
323 union {
324 _Tp __value_;
325 };
326
327public:
328 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
329#else
330
331private:
332 _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
333
334public:
335 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
336#endif
337
338 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_node(_NodePtr __next) : _Base(__next) {}
339 _LIBCPP_HIDE_FROM_ABI ~__forward_list_node() {}
340};
341
342template <class _Tp, class _Alloc = allocator<_Tp> >
343class _LIBCPP_TEMPLATE_VIS forward_list;
344template <class _NodeConstPtr>
345class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
346
347template <class _NodePtr>
348class _LIBCPP_TEMPLATE_VIS __forward_list_iterator {
349 typedef __forward_node_traits<_NodePtr> __traits;
350 typedef typename __traits::__node_pointer __node_pointer;
351 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
352 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
353 typedef typename __traits::__void_pointer __void_pointer;
354
355 __iter_node_pointer __ptr_;
356
357 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {
358 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_));
359 }
360 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const {
361 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_));
362 }
363
364 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
365
366 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
367 : __ptr_(__traits::__as_iter_node(__p)) {}
368
369 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
370 : __ptr_(__traits::__as_iter_node(__p)) {}
371
372 template <class, class>
373 friend class _LIBCPP_TEMPLATE_VIS forward_list;
374 template <class>
375 friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
376
377public:
378 typedef forward_iterator_tag iterator_category;
379 typedef typename __traits::__node_value_type value_type;
380 typedef value_type& reference;
381 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
382 typedef __rebind_pointer_t<__node_pointer, value_type> pointer;
383
384 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
385
386 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); }
387 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
388 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value());
389 }
390
391 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator& operator++() {
392 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
393 return *this;
394 }
395 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator operator++(int) {
396 __forward_list_iterator __t(*this);
397 ++(*this);
398 return __t;
399 }
400
401 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {
402 return __x.__ptr_ == __y.__ptr_;
403 }
404 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {
405 return !(__x == __y);
406 }
407};
408
409template <class _NodeConstPtr>
410class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator {
411 static_assert(!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value, "");
412 typedef _NodeConstPtr _NodePtr;
413
414 typedef __forward_node_traits<_NodePtr> __traits;
415 typedef typename __traits::__node_type __node_type;
416 typedef typename __traits::__node_pointer __node_pointer;
417 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
418 typedef typename __traits::__iter_node_pointer __iter_node_pointer;
419 typedef typename __traits::__void_pointer __void_pointer;
420
421 __iter_node_pointer __ptr_;
422
423 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {
424 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_));
425 }
426 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const {
427 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_));
428 }
429
430 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
431
432 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
433 : __ptr_(__traits::__as_iter_node(__p)) {}
434
435 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
436 : __ptr_(__traits::__as_iter_node(__p)) {}
437
438 template <class, class>
439 friend class forward_list;
440
441public:
442 typedef forward_iterator_tag iterator_category;
443 typedef typename __traits::__node_value_type value_type;
444 typedef const value_type& reference;
445 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
446 typedef __rebind_pointer_t<__node_pointer, const value_type> pointer;
447
448 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
449 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
450 : __ptr_(__p.__ptr_) {}
451
452 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); }
453 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
454 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value());
455 }
456
457 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator& operator++() {
458 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
459 return *this;
460 }
461 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator operator++(int) {
462 __forward_list_const_iterator __t(*this);
463 ++(*this);
464 return __t;
465 }
466
467 friend _LIBCPP_HIDE_FROM_ABI bool
468 operator==(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {
469 return __x.__ptr_ == __y.__ptr_;
470 }
471 friend _LIBCPP_HIDE_FROM_ABI bool
472 operator!=(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {
473 return !(__x == __y);
474 }
475};
476
477template <class _Tp, class _Alloc>
478class __forward_list_base {
479protected:
480 typedef _Tp value_type;
481 typedef _Alloc allocator_type;
482
483 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
484 typedef __forward_list_node<value_type, void_pointer> __node_type;
485 typedef __begin_node_of<value_type, void_pointer> __begin_node;
486 typedef __rebind_alloc<allocator_traits<allocator_type>, __node_type> __node_allocator;
487 typedef allocator_traits<__node_allocator> __node_traits;
488 typedef typename __node_traits::pointer __node_pointer;
489
490 typedef __rebind_alloc<allocator_traits<allocator_type>, __begin_node> __begin_node_allocator;
491 typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer;
492
493 __compressed_pair<__begin_node, __node_allocator> __before_begin_;
494
495 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() _NOEXCEPT {
496 return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());
497 }
498 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() const _NOEXCEPT {
499 return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));
500 }
501
502 _LIBCPP_HIDE_FROM_ABI __node_allocator& __alloc() _NOEXCEPT { return __before_begin_.second(); }
503 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __alloc() const _NOEXCEPT { return __before_begin_.second(); }
504
505 typedef __forward_list_iterator<__node_pointer> iterator;
506 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
507
508 _LIBCPP_HIDE_FROM_ABI __forward_list_base() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
509 : __before_begin_(__begin_node(), __default_init_tag()) {}
510 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const allocator_type& __a)
511 : __before_begin_(__begin_node(), __node_allocator(__a)) {}
512 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const __node_allocator& __a)
513 : __before_begin_(__begin_node(), __a) {}
514
515public:
516#ifndef _LIBCPP_CXX03_LANG
517 _LIBCPP_HIDE_FROM_ABI
518 __forward_list_base(__forward_list_base&& __x) noexcept(is_nothrow_move_constructible<__node_allocator>::value);
519 _LIBCPP_HIDE_FROM_ABI __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
520#endif // _LIBCPP_CXX03_LANG
521
522 __forward_list_base(const __forward_list_base&) = delete;
523 __forward_list_base& operator=(const __forward_list_base&) = delete;
524
525 _LIBCPP_HIDE_FROM_ABI ~__forward_list_base();
526
527protected:
528 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x) {
529 __copy_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
530 }
531
532 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x)
533 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
534 is_nothrow_move_assignable<__node_allocator>::value) {
535 __move_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
536 }
537
538 template <class... _Args>
539 _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__node_pointer __next, _Args&&... __args) {
540 __node_allocator& __a = __alloc();
541 __allocation_guard<__node_allocator> __guard(__a, 1);
542 // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
543 // held inside the node, since we need to use the allocator's construct() method for that.
544 //
545 // We don't use the allocator's construct() method to construct the node itself since the
546 // Cpp17FooInsertable named requirements don't require the allocator's construct() method
547 // to work on anything other than the value_type.
548 std::__construct_at(std::addressof(*__guard.__get()), __next);
549
550 // Now construct the value_type using the allocator's construct() method.
551 __node_traits::construct(__a, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
552 return __guard.__release_ptr();
553 }
554
555 _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
556 // For the same reason as above, we use the allocator's destroy() method for the value_type,
557 // but not for the node itself.
558 __node_allocator& __a = __alloc();
559 __node_traits::destroy(__a, std::addressof(__node->__get_value()));
560 std::__destroy_at(std::addressof(*__node));
561 __node_traits::deallocate(__a, __node, 1);
562 }
563
564public:
565 _LIBCPP_HIDE_FROM_ABI void swap(__forward_list_base& __x)
566#if _LIBCPP_STD_VER >= 14
567 _NOEXCEPT;
568#else
569 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>);
570#endif
571
572protected:
573 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
574
575private:
576 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base&, false_type) {}
577 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x, true_type) {
578 if (__alloc() != __x.__alloc())
579 clear();
580 __alloc() = __x.__alloc();
581 }
582
583 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT {}
584 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x, true_type)
585 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {
586 __alloc() = std::move(__x.__alloc());
587 }
588};
589
590#ifndef _LIBCPP_CXX03_LANG
591
592template <class _Tp, class _Alloc>
593inline __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x) noexcept(
594 is_nothrow_move_constructible<__node_allocator>::value)
595 : __before_begin_(std::move(__x.__before_begin_)) {
596 __x.__before_begin()->__next_ = nullptr;
597}
598
599template <class _Tp, class _Alloc>
600inline __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x, const allocator_type& __a)
601 : __before_begin_(__begin_node(), __node_allocator(__a)) {
602 if (__alloc() == __x.__alloc()) {
603 __before_begin()->__next_ = __x.__before_begin()->__next_;
604 __x.__before_begin()->__next_ = nullptr;
605 }
606}
607
608#endif // _LIBCPP_CXX03_LANG
609
610template <class _Tp, class _Alloc>
611__forward_list_base<_Tp, _Alloc>::~__forward_list_base() {
612 clear();
613}
614
615template <class _Tp, class _Alloc>
616inline void __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
617#if _LIBCPP_STD_VER >= 14
618 _NOEXCEPT
619#else
620 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
621#endif
622{
623 std::__swap_allocator(
624 __alloc(), __x.__alloc(), integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
625 using std::swap;
626 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
627}
628
629template <class _Tp, class _Alloc>
630void __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT {
631 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) {
632 __node_pointer __next = __p->__next_;
633 __delete_node(__p);
634 __p = __next;
635 }
636 __before_begin()->__next_ = nullptr;
637}
638
639template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
640class _LIBCPP_TEMPLATE_VIS forward_list : private __forward_list_base<_Tp, _Alloc> {
641 typedef __forward_list_base<_Tp, _Alloc> base;
642 typedef typename base::__node_allocator __node_allocator;
643 typedef typename base::__node_type __node_type;
644 typedef typename base::__node_traits __node_traits;
645 typedef typename base::__node_pointer __node_pointer;
646 typedef typename base::__begin_node_pointer __begin_node_pointer;
647
648public:
649 typedef _Tp value_type;
650 typedef _Alloc allocator_type;
651
652 static_assert(__check_valid_allocator<allocator_type>::value, "");
653
654 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
655 "Allocator::value_type must be same type as value_type");
656
657 static_assert(!is_same<allocator_type, __node_allocator>::value,
658 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");
659
660 typedef value_type& reference;
661 typedef const value_type& const_reference;
662 typedef typename allocator_traits<allocator_type>::pointer pointer;
663 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
664 typedef typename allocator_traits<allocator_type>::size_type size_type;
665 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
666
667 typedef typename base::iterator iterator;
668 typedef typename base::const_iterator const_iterator;
669#if _LIBCPP_STD_VER >= 20
670 typedef size_type __remove_return_type;
671#else
672 typedef void __remove_return_type;
673#endif
674
675 _LIBCPP_HIDE_FROM_ABI forward_list() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) {
676 } // = default;
677 _LIBCPP_HIDE_FROM_ABI explicit forward_list(const allocator_type& __a);
678 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n);
679#if _LIBCPP_STD_VER >= 14
680 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n, const allocator_type& __a);
681#endif
682 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v);
683
684 template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
685 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : base(__a) {
686 insert_after(cbefore_begin(), __n, __v);
687 }
688
689 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
690 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l);
691
692 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
693 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a);
694
695#if _LIBCPP_STD_VER >= 23
696 template <_ContainerCompatibleRange<_Tp> _Range>
697 _LIBCPP_HIDE_FROM_ABI forward_list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
698 : base(__a) {
699 prepend_range(std::forward<_Range>(__range));
700 }
701#endif
702
703 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x);
704 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);
705
706 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(const forward_list& __x);
707
708#ifndef _LIBCPP_CXX03_LANG
709 _LIBCPP_HIDE_FROM_ABI forward_list(forward_list&& __x) noexcept(is_nothrow_move_constructible<base>::value)
710 : base(std::move(__x)) {}
711 _LIBCPP_HIDE_FROM_ABI forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a);
712
713 _LIBCPP_HIDE_FROM_ABI forward_list(initializer_list<value_type> __il);
714 _LIBCPP_HIDE_FROM_ABI forward_list(initializer_list<value_type> __il, const allocator_type& __a);
715
716 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(forward_list&& __x) noexcept(
717 __node_traits::propagate_on_container_move_assignment::value &&
718 is_nothrow_move_assignable<allocator_type>::value);
719
720 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(initializer_list<value_type> __il);
721
722 _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il);
723#endif // _LIBCPP_CXX03_LANG
724
725 // ~forward_list() = default;
726
727 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
728 void _LIBCPP_HIDE_FROM_ABI assign(_InputIterator __f, _InputIterator __l);
729
730#if _LIBCPP_STD_VER >= 23
731 template <_ContainerCompatibleRange<_Tp> _Range>
732 _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
733 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
734 }
735#endif
736
737 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);
738
739 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(base::__alloc()); }
740
741 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(base::__before_begin()->__next_); }
742 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {
743 return const_iterator(base::__before_begin()->__next_);
744 }
745 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(nullptr); }
746 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(nullptr); }
747
748 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT {
749 return const_iterator(base::__before_begin()->__next_);
750 }
751 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return const_iterator(nullptr); }
752
753 _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT { return iterator(base::__before_begin()); }
754 _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT { return const_iterator(base::__before_begin()); }
755 _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT {
756 return const_iterator(base::__before_begin());
757 }
758
759 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {
760 return base::__before_begin()->__next_ == nullptr;
761 }
762 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
763 return std::min<size_type>(__node_traits::max_size(base::__alloc()), numeric_limits<difference_type>::max());
764 }
765
766 _LIBCPP_HIDE_FROM_ABI reference front() { return base::__before_begin()->__next_->__get_value(); }
767 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return base::__before_begin()->__next_->__get_value(); }
768
769#ifndef _LIBCPP_CXX03_LANG
770# if _LIBCPP_STD_VER >= 17
771 template <class... _Args>
772 _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
773# else
774 template <class... _Args>
775 _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
776# endif
777 _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v);
778#endif // _LIBCPP_CXX03_LANG
779 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);
780
781#if _LIBCPP_STD_VER >= 23
782 template <_ContainerCompatibleRange<_Tp> _Range>
783 _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) {
784 insert_range_after(cbefore_begin(), std::forward<_Range>(__range));
785 }
786#endif
787
788 _LIBCPP_HIDE_FROM_ABI void pop_front();
789
790#ifndef _LIBCPP_CXX03_LANG
791 template <class... _Args>
792 _LIBCPP_HIDE_FROM_ABI iterator emplace_after(const_iterator __p, _Args&&... __args);
793
794 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, value_type&& __v);
795 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, initializer_list<value_type> __il) {
796 return insert_after(__p, __il.begin(), __il.end());
797 }
798#endif // _LIBCPP_CXX03_LANG
799 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, const value_type& __v);
800 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
801 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
802 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
803
804#if _LIBCPP_STD_VER >= 23
805 template <_ContainerCompatibleRange<_Tp> _Range>
806 _LIBCPP_HIDE_FROM_ABI iterator insert_range_after(const_iterator __position, _Range&& __range) {
807 return __insert_after_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
808 }
809#endif
810
811 template <class _InputIterator, class _Sentinel>
812 _LIBCPP_HIDE_FROM_ABI iterator __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l);
813
814 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p);
815 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l);
816
817 _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x)
818#if _LIBCPP_STD_VER >= 14
819 _NOEXCEPT
820#else
821 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
822#endif
823 {
824 base::swap(__x);
825 }
826
827 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
828 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v);
829 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); }
830
831 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x);
832 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
833 _LIBCPP_HIDE_FROM_ABI void
834 splice_after(const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l);
835 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x);
836 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
837 _LIBCPP_HIDE_FROM_ABI void
838 splice_after(const_iterator __p, forward_list& __x, const_iterator __f, const_iterator __l);
839 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __v);
840 template <class _Predicate>
841 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Predicate __pred);
842 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }
843 template <class _BinaryPredicate>
844 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred);
845#ifndef _LIBCPP_CXX03_LANG
846 _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x) { merge(__x, __less<>()); }
847 template <class _Compare>
848 _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x, _Compare __comp) {
849 merge(__x, std::move(__comp));
850 }
851#endif // _LIBCPP_CXX03_LANG
852 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x) { merge(__x, __less<>()); }
853 template <class _Compare>
854 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp);
855 _LIBCPP_HIDE_FROM_ABI void sort() { sort(__less<>()); }
856 template <class _Compare>
857 _LIBCPP_HIDE_FROM_ABI void sort(_Compare __comp);
858 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
859
860private:
861#ifndef _LIBCPP_CXX03_LANG
862 _LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, true_type)
863 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
864 _LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, false_type);
865#endif // _LIBCPP_CXX03_LANG
866
867 template <class _Iter, class _Sent>
868 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iter __f, _Sent __l);
869
870 template <class _Compare>
871 static _LIBCPP_HIDE_FROM_ABI __node_pointer __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
872
873 // TODO: Make this _LIBCPP_HIDE_FROM_ABI
874 template <class _Compare>
875 static _LIBCPP_HIDDEN __node_pointer __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
876};
877
878#if _LIBCPP_STD_VER >= 17
879template <class _InputIterator,
880 class _Alloc = allocator<__iter_value_type<_InputIterator>>,
881 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
882 class = enable_if_t<__is_allocator<_Alloc>::value> >
883forward_list(_InputIterator, _InputIterator) -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
884
885template <class _InputIterator,
886 class _Alloc,
887 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
888 class = enable_if_t<__is_allocator<_Alloc>::value> >
889forward_list(_InputIterator, _InputIterator, _Alloc) -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
890#endif
891
892#if _LIBCPP_STD_VER >= 23
893template <ranges::input_range _Range,
894 class _Alloc = allocator<ranges::range_value_t<_Range>>,
895 class = enable_if_t<__is_allocator<_Alloc>::value> >
896forward_list(from_range_t, _Range&&, _Alloc = _Alloc()) -> forward_list<ranges::range_value_t<_Range>, _Alloc>;
897#endif
898
899template <class _Tp, class _Alloc>
900inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : base(__a) {}
901
902template <class _Tp, class _Alloc>
903forward_list<_Tp, _Alloc>::forward_list(size_type __n) {
904 if (__n > 0) {
905 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) {
906 __p->__next_ = this->__create_node(/* next = */ nullptr);
907 }
908 }
909}
910
911#if _LIBCPP_STD_VER >= 14
912template <class _Tp, class _Alloc>
913forward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __base_alloc) : base(__base_alloc) {
914 if (__n > 0) {
915 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) {
916 __p->__next_ = this->__create_node(/* next = */ nullptr);
917 }
918 }
919}
920#endif
921
922template <class _Tp, class _Alloc>
923forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) {
924 insert_after(cbefore_begin(), __n, __v);
925}
926
927template <class _Tp, class _Alloc>
928template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
929forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) {
930 insert_after(cbefore_begin(), __f, __l);
931}
932
933template <class _Tp, class _Alloc>
934template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
935forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a) : base(__a) {
936 insert_after(cbefore_begin(), __f, __l);
937}
938
939template <class _Tp, class _Alloc>
940forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
941 : base(__node_traits::select_on_container_copy_construction(__x.__alloc())) {
942 insert_after(cbefore_begin(), __x.begin(), __x.end());
943}
944
945template <class _Tp, class _Alloc>
946forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a)
947 : base(__a) {
948 insert_after(cbefore_begin(), __x.begin(), __x.end());
949}
950
951template <class _Tp, class _Alloc>
952forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) {
953 if (this != std::addressof(__x)) {
954 base::__copy_assign_alloc(__x);
955 assign(__x.begin(), __x.end());
956 }
957 return *this;
958}
959
960#ifndef _LIBCPP_CXX03_LANG
961template <class _Tp, class _Alloc>
962forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a)
963 : base(std::move(__x), __a) {
964 if (base::__alloc() != __x.__alloc()) {
965 typedef move_iterator<iterator> _Ip;
966 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
967 }
968}
969
970template <class _Tp, class _Alloc>
971forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) {
972 insert_after(cbefore_begin(), __il.begin(), __il.end());
973}
974
975template <class _Tp, class _Alloc>
976forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, const allocator_type& __a) : base(__a) {
977 insert_after(cbefore_begin(), __il.begin(), __il.end());
978}
979
980template <class _Tp, class _Alloc>
981void forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
982 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
983 clear();
984 base::__move_assign_alloc(__x);
985 base::__before_begin()->__next_ = __x.__before_begin()->__next_;
986 __x.__before_begin()->__next_ = nullptr;
987}
988
989template <class _Tp, class _Alloc>
990void forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) {
991 if (base::__alloc() == __x.__alloc())
992 __move_assign(__x, true_type());
993 else {
994 typedef move_iterator<iterator> _Ip;
995 assign(_Ip(__x.begin()), _Ip(__x.end()));
996 }
997}
998
999template <class _Tp, class _Alloc>
1000inline forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(forward_list&& __x) _NOEXCEPT_(
1001 __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<allocator_type>::value) {
1002 __move_assign(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1003 return *this;
1004}
1005
1006template <class _Tp, class _Alloc>
1007inline forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) {
1008 assign(__il.begin(), __il.end());
1009 return *this;
1010}
1011
1012#endif // _LIBCPP_CXX03_LANG
1013
1014template <class _Tp, class _Alloc>
1015template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
1016void forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) {
1017 __assign_with_sentinel(__f, __l);
1018}
1019
1020template <class _Tp, class _Alloc>
1021template <class _Iter, class _Sent>
1022_LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::__assign_with_sentinel(_Iter __f, _Sent __l) {
1023 iterator __i = before_begin();
1024 iterator __j = std::next(__i);
1025 iterator __e = end();
1026 for (; __j != __e && __f != __l; ++__i, (void)++__j, ++__f)
1027 *__j = *__f;
1028 if (__j == __e)
1029 __insert_after_with_sentinel(__i, std::move(__f), std::move(__l));
1030 else
1031 erase_after(__i, __e);
1032}
1033
1034template <class _Tp, class _Alloc>
1035void forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) {
1036 iterator __i = before_begin();
1037 iterator __j = std::next(__i);
1038 iterator __e = end();
1039 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1040 *__j = __v;
1041 if (__j == __e)
1042 insert_after(__i, __n, __v);
1043 else
1044 erase_after(__i, __e);
1045}
1046
1047#ifndef _LIBCPP_CXX03_LANG
1048
1049template <class _Tp, class _Alloc>
1050inline void forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) {
1051 assign(__il.begin(), __il.end());
1052}
1053
1054template <class _Tp, class _Alloc>
1055template <class... _Args>
1056# if _LIBCPP_STD_VER >= 17
1057typename forward_list<_Tp, _Alloc>::reference
1058# else
1059void
1060# endif
1061forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) {
1062 base::__before_begin()->__next_ =
1063 this->__create_node(/* next = */ base::__before_begin()->__next_, std::forward<_Args>(__args)...);
1064# if _LIBCPP_STD_VER >= 17
1065 return base::__before_begin()->__next_->__get_value();
1066# endif
1067}
1068
1069template <class _Tp, class _Alloc>
1070void forward_list<_Tp, _Alloc>::push_front(value_type&& __v) {
1071 base::__before_begin()->__next_ = this->__create_node(/* next = */ base::__before_begin()->__next_, std::move(__v));
1072}
1073
1074#endif // _LIBCPP_CXX03_LANG
1075
1076template <class _Tp, class _Alloc>
1077void forward_list<_Tp, _Alloc>::push_front(const value_type& __v) {
1078 base::__before_begin()->__next_ = this->__create_node(/* next = */ base::__before_begin()->__next_, __v);
1079}
1080
1081template <class _Tp, class _Alloc>
1082void forward_list<_Tp, _Alloc>::pop_front() {
1083 __node_pointer __p = base::__before_begin()->__next_;
1084 base::__before_begin()->__next_ = __p->__next_;
1085 this->__delete_node(__p);
1086}
1087
1088#ifndef _LIBCPP_CXX03_LANG
1089
1090template <class _Tp, class _Alloc>
1091template <class... _Args>
1092typename forward_list<_Tp, _Alloc>::iterator
1093forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) {
1094 __begin_node_pointer const __r = __p.__get_begin();
1095 __r->__next_ = this->__create_node(/* next = */ __r->__next_, std::forward<_Args>(__args)...);
1096 return iterator(__r->__next_);
1097}
1098
1099template <class _Tp, class _Alloc>
1100typename forward_list<_Tp, _Alloc>::iterator
1101forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) {
1102 __begin_node_pointer const __r = __p.__get_begin();
1103 __r->__next_ = this->__create_node(/* next = */ __r->__next_, std::move(__v));
1104 return iterator(__r->__next_);
1105}
1106
1107#endif // _LIBCPP_CXX03_LANG
1108
1109template <class _Tp, class _Alloc>
1110typename forward_list<_Tp, _Alloc>::iterator
1111forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) {
1112 __begin_node_pointer const __r = __p.__get_begin();
1113 __r->__next_ = this->__create_node(/* next = */ __r->__next_, __v);
1114 return iterator(__r->__next_);
1115}
1116
1117template <class _Tp, class _Alloc>
1118typename forward_list<_Tp, _Alloc>::iterator
1119forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, const value_type& __v) {
1120 __begin_node_pointer __r = __p.__get_begin();
1121 if (__n > 0) {
1122 __node_pointer __first = this->__create_node(/* next = */ nullptr, __v);
1123 __node_pointer __last = __first;
1124#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1125 try {
1126#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1127 for (--__n; __n != 0; --__n, __last = __last->__next_) {
1128 __last->__next_ = this->__create_node(/* next = */ nullptr, __v);
1129 }
1130#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1131 } catch (...) {
1132 while (__first != nullptr) {
1133 __node_pointer __next = __first->__next_;
1134 this->__delete_node(__first);
1135 __first = __next;
1136 }
1137 throw;
1138 }
1139#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1140 __last->__next_ = __r->__next_;
1141 __r->__next_ = __first;
1142 __r = static_cast<__begin_node_pointer>(__last);
1143 }
1144 return iterator(__r);
1145}
1146
1147template <class _Tp, class _Alloc>
1148template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
1149typename forward_list<_Tp, _Alloc>::iterator
1150forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l) {
1151 return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l));
1152}
1153
1154template <class _Tp, class _Alloc>
1155template <class _InputIterator, class _Sentinel>
1156_LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Alloc>::iterator
1157forward_list<_Tp, _Alloc>::__insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) {
1158 __begin_node_pointer __r = __p.__get_begin();
1159
1160 if (__f != __l) {
1161 __node_pointer __first = this->__create_node(/* next = */ nullptr, *__f);
1162 __node_pointer __last = __first;
1163
1164#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1165 try {
1166#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1167 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) {
1168 __last->__next_ = this->__create_node(/* next = */ nullptr, *__f);
1169 }
1170#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1171 } catch (...) {
1172 while (__first != nullptr) {
1173 __node_pointer __next = __first->__next_;
1174 this->__delete_node(__first);
1175 __first = __next;
1176 }
1177 throw;
1178 }
1179#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1180
1181 __last->__next_ = __r->__next_;
1182 __r->__next_ = __first;
1183 __r = static_cast<__begin_node_pointer>(__last);
1184 }
1185
1186 return iterator(__r);
1187}
1188
1189template <class _Tp, class _Alloc>
1190typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) {
1191 __begin_node_pointer __p = __f.__get_begin();
1192 __node_pointer __n = __p->__next_;
1193 __p->__next_ = __n->__next_;
1194 this->__delete_node(__n);
1195 return iterator(__p->__next_);
1196}
1197
1198template <class _Tp, class _Alloc>
1199typename forward_list<_Tp, _Alloc>::iterator
1200forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) {
1201 __node_pointer __e = __l.__get_unsafe_node_pointer();
1202 if (__f != __l) {
1203 __begin_node_pointer __bp = __f.__get_begin();
1204
1205 __node_pointer __n = __bp->__next_;
1206 if (__n != __e) {
1207 __bp->__next_ = __e;
1208 do {
1209 __node_pointer __tmp = __n->__next_;
1210 this->__delete_node(__n);
1211 __n = __tmp;
1212 } while (__n != __e);
1213 }
1214 }
1215 return iterator(__e);
1216}
1217
1218template <class _Tp, class _Alloc>
1219void forward_list<_Tp, _Alloc>::resize(size_type __n) {
1220 size_type __sz = 0;
1221 iterator __p = before_begin();
1222 iterator __i = begin();
1223 iterator __e = end();
1224 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1225 ;
1226 if (__i != __e)
1227 erase_after(__p, __e);
1228 else {
1229 __n -= __sz;
1230 if (__n > 0) {
1231 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) {
1232 __ptr->__next_ = this->__create_node(/* next = */ nullptr);
1233 }
1234 }
1235 }
1236}
1237
1238template <class _Tp, class _Alloc>
1239void forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) {
1240 size_type __sz = 0;
1241 iterator __p = before_begin();
1242 iterator __i = begin();
1243 iterator __e = end();
1244 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1245 ;
1246 if (__i != __e)
1247 erase_after(__p, __e);
1248 else {
1249 __n -= __sz;
1250 if (__n > 0) {
1251 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) {
1252 __ptr->__next_ = this->__create_node(/* next = */ nullptr, __v);
1253 }
1254 }
1255 }
1256}
1257
1258template <class _Tp, class _Alloc>
1259void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& __x) {
1260 if (!__x.empty()) {
1261 if (__p.__get_begin()->__next_ != nullptr) {
1262 const_iterator __lm1 = __x.before_begin();
1263 while (__lm1.__get_begin()->__next_ != nullptr)
1264 ++__lm1;
1265 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1266 }
1267 __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
1268 __x.__before_begin()->__next_ = nullptr;
1269 }
1270}
1271
1272template <class _Tp, class _Alloc>
1273void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& /*__other*/, const_iterator __i) {
1274 const_iterator __lm1 = std::next(__i);
1275 if (__p != __i && __p != __lm1) {
1276 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
1277 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1278 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
1279 }
1280}
1281
1282template <class _Tp, class _Alloc>
1283void forward_list<_Tp, _Alloc>::splice_after(
1284 const_iterator __p, forward_list& /*__other*/, const_iterator __f, const_iterator __l) {
1285 if (__f != __l && __p != __f) {
1286 const_iterator __lm1 = __f;
1287 while (__lm1.__get_begin()->__next_ != __l.__get_begin())
1288 ++__lm1;
1289 if (__f != __lm1) {
1290 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1291 __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
1292 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
1293 }
1294 }
1295}
1296
1297template <class _Tp, class _Alloc>
1298inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x) {
1299 splice_after(__p, __x);
1300}
1301
1302template <class _Tp, class _Alloc>
1303inline _LIBCPP_HIDE_FROM_ABI void
1304forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x, const_iterator __i) {
1305 splice_after(__p, __x, __i);
1306}
1307
1308template <class _Tp, class _Alloc>
1309inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(
1310 const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l) {
1311 splice_after(__p, __x, __f, __l);
1312}
1313
1314template <class _Tp, class _Alloc>
1315typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove(const value_type& __v) {
1316 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1317 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1318 const iterator __e = end();
1319 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) {
1320 if (__i.__get_begin()->__next_->__get_value() == __v) {
1321 ++__count_removed;
1322 iterator __j = std::next(__i, 2);
1323 for (; __j != __e && *__j == __v; ++__j)
1324 ++__count_removed;
1325 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1326 if (__j == __e)
1327 break;
1328 __i = __j;
1329 } else
1330 ++__i;
1331 }
1332
1333 return (__remove_return_type)__count_removed;
1334}
1335
1336template <class _Tp, class _Alloc>
1337template <class _Predicate>
1338typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) {
1339 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1340 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1341 const iterator __e = end();
1342 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) {
1343 if (__pred(__i.__get_begin()->__next_->__get_value())) {
1344 ++__count_removed;
1345 iterator __j = std::next(__i, 2);
1346 for (; __j != __e && __pred(*__j); ++__j)
1347 ++__count_removed;
1348 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1349 if (__j == __e)
1350 break;
1351 __i = __j;
1352 } else
1353 ++__i;
1354 }
1355
1356 return (__remove_return_type)__count_removed;
1357}
1358
1359template <class _Tp, class _Alloc>
1360template <class _BinaryPredicate>
1361typename forward_list<_Tp, _Alloc>::__remove_return_type
1362forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) {
1363 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1364 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1365 for (iterator __i = begin(), __e = end(); __i != __e;) {
1366 iterator __j = std::next(__i);
1367 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1368 ++__count_removed;
1369 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
1370 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1371 __i = __j;
1372 }
1373
1374 return (__remove_return_type)__count_removed;
1375}
1376
1377template <class _Tp, class _Alloc>
1378template <class _Compare>
1379void forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) {
1380 if (this != std::addressof(__x)) {
1381 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, __x.__before_begin()->__next_, __comp);
1382 __x.__before_begin()->__next_ = nullptr;
1383 }
1384}
1385
1386template <class _Tp, class _Alloc>
1387template <class _Compare>
1388typename forward_list<_Tp, _Alloc>::__node_pointer
1389forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp) {
1390 if (__f1 == nullptr)
1391 return __f2;
1392 if (__f2 == nullptr)
1393 return __f1;
1394 __node_pointer __r;
1395 if (__comp(__f2->__get_value(), __f1->__get_value())) {
1396 __node_pointer __t = __f2;
1397 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))
1398 __t = __t->__next_;
1399 __r = __f2;
1400 __f2 = __t->__next_;
1401 __t->__next_ = __f1;
1402 } else
1403 __r = __f1;
1404 __node_pointer __p = __f1;
1405 __f1 = __f1->__next_;
1406 while (__f1 != nullptr && __f2 != nullptr) {
1407 if (__comp(__f2->__get_value(), __f1->__get_value())) {
1408 __node_pointer __t = __f2;
1409 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))
1410 __t = __t->__next_;
1411 __p->__next_ = __f2;
1412 __f2 = __t->__next_;
1413 __t->__next_ = __f1;
1414 }
1415 __p = __f1;
1416 __f1 = __f1->__next_;
1417 }
1418 if (__f2 != nullptr)
1419 __p->__next_ = __f2;
1420 return __r;
1421}
1422
1423template <class _Tp, class _Alloc>
1424template <class _Compare>
1425inline void forward_list<_Tp, _Alloc>::sort(_Compare __comp) {
1426 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, std::distance(begin(), end()), __comp);
1427}
1428
1429template <class _Tp, class _Alloc>
1430template <class _Compare>
1431typename forward_list<_Tp, _Alloc>::__node_pointer
1432forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, _Compare& __comp) {
1433 switch (__sz) {
1434 case 0:
1435 case 1:
1436 return __f1;
1437 case 2:
1438 if (__comp(__f1->__next_->__get_value(), __f1->__get_value())) {
1439 __node_pointer __t = __f1->__next_;
1440 __t->__next_ = __f1;
1441 __f1->__next_ = nullptr;
1442 __f1 = __t;
1443 }
1444 return __f1;
1445 }
1446 difference_type __sz1 = __sz / 2;
1447 difference_type __sz2 = __sz - __sz1;
1448 __node_pointer __t = std::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
1449 __node_pointer __f2 = __t->__next_;
1450 __t->__next_ = nullptr;
1451 return __merge(__sort(__f1, __sz1, __comp), __sort(__f2, __sz2, __comp), __comp);
1452}
1453
1454template <class _Tp, class _Alloc>
1455void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT {
1456 __node_pointer __p = base::__before_begin()->__next_;
1457 if (__p != nullptr) {
1458 __node_pointer __f = __p->__next_;
1459 __p->__next_ = nullptr;
1460 while (__f != nullptr) {
1461 __node_pointer __t = __f->__next_;
1462 __f->__next_ = __p;
1463 __p = __f;
1464 __f = __t;
1465 }
1466 base::__before_begin()->__next_ = __p;
1467 }
1468}
1469
1470template <class _Tp, class _Alloc>
1471_LIBCPP_HIDE_FROM_ABI bool operator==(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1472 typedef forward_list<_Tp, _Alloc> _Cp;
1473 typedef typename _Cp::const_iterator _Ip;
1474 _Ip __ix = __x.begin();
1475 _Ip __ex = __x.end();
1476 _Ip __iy = __y.begin();
1477 _Ip __ey = __y.end();
1478 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1479 if (!(*__ix == *__iy))
1480 return false;
1481 return (__ix == __ex) == (__iy == __ey);
1482}
1483
1484#if _LIBCPP_STD_VER <= 17
1485
1486template <class _Tp, class _Alloc>
1487inline _LIBCPP_HIDE_FROM_ABI bool
1488operator!=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1489 return !(__x == __y);
1490}
1491
1492template <class _Tp, class _Alloc>
1493inline _LIBCPP_HIDE_FROM_ABI bool
1494operator<(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1495 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1496}
1497
1498template <class _Tp, class _Alloc>
1499inline _LIBCPP_HIDE_FROM_ABI bool
1500operator>(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1501 return __y < __x;
1502}
1503
1504template <class _Tp, class _Alloc>
1505inline _LIBCPP_HIDE_FROM_ABI bool
1506operator>=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1507 return !(__x < __y);
1508}
1509
1510template <class _Tp, class _Alloc>
1511inline _LIBCPP_HIDE_FROM_ABI bool
1512operator<=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1513 return !(__y < __x);
1514}
1515
1516#else // #if _LIBCPP_STD_VER <= 17
1517
1518template <class _Tp, class _Allocator>
1519_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp>
1520operator<=>(const forward_list<_Tp, _Allocator>& __x, const forward_list<_Tp, _Allocator>& __y) {
1521 return std::lexicographical_compare_three_way(
1522 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1523}
1524
1525#endif // #if _LIBCPP_STD_VER <= 17
1526
1527template <class _Tp, class _Alloc>
1528inline _LIBCPP_HIDE_FROM_ABI void swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1529 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1530 __x.swap(__y);
1531}
1532
1533#if _LIBCPP_STD_VER >= 20
1534template <class _Tp, class _Allocator, class _Predicate>
1535inline _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Allocator>::size_type
1536erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) {
1537 return __c.remove_if(__pred);
1538}
1539
1540template <class _Tp, class _Allocator, class _Up>
1541inline _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Allocator>::size_type
1542erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) {
1543 return std::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
1544}
1545#endif
1546
1547_LIBCPP_END_NAMESPACE_STD
1548
1549#if _LIBCPP_STD_VER >= 17
1550_LIBCPP_BEGIN_NAMESPACE_STD
1551namespace pmr {
1552template <class _ValueT>
1553using forward_list _LIBCPP_AVAILABILITY_PMR = std::forward_list<_ValueT, polymorphic_allocator<_ValueT>>;
1554} // namespace pmr
1555_LIBCPP_END_NAMESPACE_STD
1556#endif
1557
1558_LIBCPP_POP_MACROS
1559
1560#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1561# include <algorithm>
1562# include <atomic>
1563# include <concepts>
1564# include <cstdint>
1565# include <cstdlib>
1566# include <cstring>
1567# include <functional>
1568# include <iosfwd>
1569# include <iterator>
1570# include <stdexcept>
1571# include <type_traits>
1572# include <typeinfo>
1573#endif
1574
1575#endif // _LIBCPP_FORWARD_LIST
1576