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