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((__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# if _LIBCPP_STD_VER >= 14
668 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n, const allocator_type& __a);
669# endif
670 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v);
671
672 template <__enable_if_t<__is_allocator_v<_Alloc>, int> = 0>
673 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
674 forward_list(size_type __n, const value_type& __v, const allocator_type& __a)
675 : __base(__a) {
676 insert_after(cbefore_begin(), __n, __v);
677 }
678
679 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
680 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l);
681
682 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
683 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
684 forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a);
685
686# if _LIBCPP_STD_VER >= 23
687 template <_ContainerCompatibleRange<_Tp> _Range>
688 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
689 forward_list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
690 : __base(__a) {
691 prepend_range(std::forward<_Range>(__range));
692 }
693# endif
694
695 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x);
696 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
697 forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);
698
699 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(const forward_list& __x);
700
701# ifndef _LIBCPP_CXX03_LANG
702 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
703 forward_list(forward_list&& __x) noexcept(is_nothrow_move_constructible<__base>::value)
704 : __base(std::move(__x)) {}
705 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
706 forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a);
707
708 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(initializer_list<value_type> __il);
709 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
710 forward_list(initializer_list<value_type> __il, const allocator_type& __a);
711
712 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(forward_list&& __x) noexcept(
713 (__node_traits::propagate_on_container_move_assignment::value &&
714 is_nothrow_move_assignable<allocator_type>::value) ||
715 allocator_traits<allocator_type>::is_always_equal::value);
716
717 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(initializer_list<value_type> __il);
718
719 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il);
720# endif // _LIBCPP_CXX03_LANG
721
722 // ~forward_list() = default;
723
724 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
725 _LIBCPP_CONSTEXPR_SINCE_CXX26 void _LIBCPP_HIDE_FROM_ABI assign(_InputIterator __f, _InputIterator __l);
726
727# if _LIBCPP_STD_VER >= 23
728 template <_ContainerCompatibleRange<_Tp> _Range>
729 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
730 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
731 }
732# endif
733
734 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);
735
736 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
737 return allocator_type(this->__alloc_);
738 }
739
740 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT {
741 return iterator(__base::__before_begin()->__next_);
742 }
743 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {
744 return const_iterator(__base::__before_begin()->__next_);
745 }
746 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT {
747 return iterator(nullptr);
748 }
749 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT {
750 return const_iterator(nullptr);
751 }
752
753 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT {
754 return const_iterator(__base::__before_begin()->__next_);
755 }
756 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT {
757 return const_iterator(nullptr);
758 }
759
760 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT {
761 return iterator(__base::__before_begin());
762 }
763 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT {
764 return const_iterator(__base::__before_begin());
765 }
766 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT {
767 return const_iterator(__base::__before_begin());
768 }
769
770 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {
771 return __base::__before_begin()->__next_ == nullptr;
772 }
773 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
774 return std::min<size_type>(__node_traits::max_size(this->__alloc_), numeric_limits<difference_type>::max());
775 }
776
777 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI reference front() {
778 _LIBCPP_ASSERT_NON_NULL(!empty(), "forward_list::front called on an empty list");
779 return __base::__before_begin()->__next_->__get_value();
780 }
781 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_reference front() const {
782 _LIBCPP_ASSERT_NON_NULL(!empty(), "forward_list::front called on an empty list");
783 return __base::__before_begin()->__next_->__get_value();
784 }
785
786# ifndef _LIBCPP_CXX03_LANG
787# if _LIBCPP_STD_VER >= 17
788 template <class... _Args>
789 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
790# else
791 template <class... _Args>
792 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
793# endif
794 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v);
795# endif // _LIBCPP_CXX03_LANG
796 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);
797
798# if _LIBCPP_STD_VER >= 23
799 template <_ContainerCompatibleRange<_Tp> _Range>
800 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) {
801 insert_range_after(cbefore_begin(), std::forward<_Range>(__range));
802 }
803# endif
804
805 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void pop_front();
806
807# ifndef _LIBCPP_CXX03_LANG
808 template <class... _Args>
809 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator emplace_after(const_iterator __p, _Args&&... __args);
810
811 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, value_type&& __v);
812 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
813 insert_after(const_iterator __p, initializer_list<value_type> __il) {
814 return insert_after(__p, __il.begin(), __il.end());
815 }
816# endif // _LIBCPP_CXX03_LANG
817 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, const value_type& __v);
818 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
819 insert_after(const_iterator __p, size_type __n, const value_type& __v) {
820 return __insert_after(__p, __n, __v);
821 }
822 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
823 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
824 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
825
826# if _LIBCPP_STD_VER >= 23
827 template <_ContainerCompatibleRange<_Tp> _Range>
828 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
829 insert_range_after(const_iterator __position, _Range&& __range) {
830 return __insert_after_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
831 }
832# endif
833
834 template <class _InputIterator, class _Sentinel>
835 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
836 __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l);
837
838 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p);
839 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l);
840
841 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x)
842# if _LIBCPP_STD_VER >= 14
843 _NOEXCEPT
844# else
845 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
846# endif
847 {
848 __base::swap(__x);
849 }
850
851 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
852 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v);
853 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __base::clear(); }
854
855 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x);
856 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
857 splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
858 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
859 splice_after(const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l);
860 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x);
861 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
862 splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
863 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
864 splice_after(const_iterator __p, forward_list& __x, const_iterator __f, const_iterator __l);
865 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __v);
866 template <class _Predicate>
867 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Predicate __pred);
868 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }
869 template <class _BinaryPredicate>
870 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred);
871# ifndef _LIBCPP_CXX03_LANG
872 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x) { merge(__x, __less<>()); }
873 template <class _Compare>
874 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x, _Compare __comp) {
875 merge(__x, std::move(__comp));
876 }
877# endif // _LIBCPP_CXX03_LANG
878 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x) { merge(__x, __less<>()); }
879 template <class _Compare>
880 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp);
881 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void sort() { sort(__less<>()); }
882 template <class _Compare>
883 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void sort(_Compare __comp);
884 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
885
886private:
887# ifndef _LIBCPP_CXX03_LANG
888 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, true_type)
889 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
890 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, false_type);
891# endif // _LIBCPP_CXX03_LANG
892
893 template <class _Iter, class _Sent>
894 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iter __f, _Sent __l);
895
896 template <class... _Args>
897 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
898 __insert_after(const_iterator __p, size_type __n, _Args&&... __args);
899
900 template <class _Compare>
901 _LIBCPP_CONSTEXPR_SINCE_CXX26 static _LIBCPP_HIDE_FROM_ABI __node_pointer
902 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
903
904 // TODO: Make this _LIBCPP_HIDE_FROM_ABI
905 template <class _Compare>
906 _LIBCPP_CONSTEXPR_SINCE_CXX26 static _LIBCPP_HIDDEN __node_pointer
907 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
908};
909
910# if _LIBCPP_STD_VER >= 17
911template <class _InputIterator,
912 class _Alloc = allocator<__iterator_value_type<_InputIterator>>,
913 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
914 class = enable_if_t<__is_allocator_v<_Alloc>>>
915forward_list(_InputIterator, _InputIterator) -> forward_list<__iterator_value_type<_InputIterator>, _Alloc>;
916
917template <class _InputIterator,
918 class _Alloc,
919 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
920 class = enable_if_t<__is_allocator_v<_Alloc>>>
921forward_list(_InputIterator, _InputIterator, _Alloc) -> forward_list<__iterator_value_type<_InputIterator>, _Alloc>;
922# endif
923
924# if _LIBCPP_STD_VER >= 23
925template <ranges::input_range _Range,
926 class _Alloc = allocator<ranges::range_value_t<_Range>>,
927 class = enable_if_t<__is_allocator_v<_Alloc>>>
928forward_list(from_range_t, _Range&&, _Alloc = _Alloc()) -> forward_list<ranges::range_value_t<_Range>, _Alloc>;
929# endif
930
931template <class _Tp, class _Alloc>
932_LIBCPP_CONSTEXPR_SINCE_CXX26 inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : __base(__a) {}
933
934template <class _Tp, class _Alloc>
935_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(size_type __n) {
936 if (__n > 0) {
937 for (__begin_node_pointer __p = __base::__before_begin(); __n > 0;
938 --__n, __p = std::__static_fancy_pointer_cast<__begin_node_pointer>(__p->__next_)) {
939 __p->__next_ = this->__create_node(/* next = */ nullptr);
940 }
941 }
942}
943
944# if _LIBCPP_STD_VER >= 14
945template <class _Tp, class _Alloc>
946_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __base_alloc)
947 : __base(__base_alloc) {
948 if (__n > 0) {
949 for (__begin_node_pointer __p = __base::__before_begin(); __n > 0;
950 --__n, __p = std::__static_fancy_pointer_cast<__begin_node_pointer>(__p->__next_)) {
951 __p->__next_ = this->__create_node(/* next = */ nullptr);
952 }
953 }
954}
955# endif
956
957template <class _Tp, class _Alloc>
958_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) {
959 insert_after(cbefore_begin(), __n, __v);
960}
961
962template <class _Tp, class _Alloc>
963template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
964_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) {
965 insert_after(cbefore_begin(), __f, __l);
966}
967
968template <class _Tp, class _Alloc>
969template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
970_LIBCPP_CONSTEXPR_SINCE_CXX26
971forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
972 : __base(__a) {
973 insert_after(cbefore_begin(), __f, __l);
974}
975
976template <class _Tp, class _Alloc>
977_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
978 : __base(__node_traits::select_on_container_copy_construction(__x.__alloc_)) {
979 insert_after(cbefore_begin(), __x.begin(), __x.end());
980}
981
982template <class _Tp, class _Alloc>
983_LIBCPP_CONSTEXPR_SINCE_CXX26
984forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a)
985 : __base(__a) {
986 insert_after(cbefore_begin(), __x.begin(), __x.end());
987}
988
989template <class _Tp, class _Alloc>
990_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) {
991 if (this != std::addressof(__x)) {
992 __base::__copy_assign_alloc(__x);
993 assign(__x.begin(), __x.end());
994 }
995 return *this;
996}
997
998# ifndef _LIBCPP_CXX03_LANG
999template <class _Tp, class _Alloc>
1000_LIBCPP_CONSTEXPR_SINCE_CXX26
1001forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a)
1002 : __base(std::move(__x), __a) {
1003 if (this->__alloc_ != __x.__alloc_) {
1004 typedef move_iterator<iterator> _Ip;
1005 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
1006 }
1007}
1008
1009template <class _Tp, class _Alloc>
1010_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) {
1011 insert_after(cbefore_begin(), __il.begin(), __il.end());
1012}
1013
1014template <class _Tp, class _Alloc>
1015_LIBCPP_CONSTEXPR_SINCE_CXX26
1016forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, const allocator_type& __a)
1017 : __base(__a) {
1018 insert_after(cbefore_begin(), __il.begin(), __il.end());
1019}
1020
1021template <class _Tp, class _Alloc>
1022_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
1023 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
1024 clear();
1025 __base::__move_assign_alloc(__x);
1026 __base::__before_begin()->__next_ = std::__exchange(__x.__before_begin()->__next_, nullptr);
1027}
1028
1029template <class _Tp, class _Alloc>
1030_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) {
1031 if (this->__alloc_ == __x.__alloc_)
1032 __move_assign(__x, true_type());
1033 else {
1034 typedef move_iterator<iterator> _Ip;
1035 assign(_Ip(__x.begin()), _Ip(__x.end()));
1036 }
1037}
1038
1039template <class _Tp, class _Alloc>
1040_LIBCPP_CONSTEXPR_SINCE_CXX26 inline forward_list<_Tp, _Alloc>&
1041forward_list<_Tp, _Alloc>::operator=(forward_list&& __x) noexcept(
1042 (__node_traits::propagate_on_container_move_assignment::value &&
1043 is_nothrow_move_assignable<allocator_type>::value) ||
1044 allocator_traits<allocator_type>::is_always_equal::value) {
1045 __move_assign(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1046 return *this;
1047}
1048
1049template <class _Tp, class _Alloc>
1050_LIBCPP_CONSTEXPR_SINCE_CXX26 inline forward_list<_Tp, _Alloc>&
1051forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) {
1052 assign(__il.begin(), __il.end());
1053 return *this;
1054}
1055
1056# endif // _LIBCPP_CXX03_LANG
1057
1058template <class _Tp, class _Alloc>
1059template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
1060_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) {
1061 __assign_with_sentinel(__f, __l);
1062}
1063
1064template <class _Tp, class _Alloc>
1065template <class _Iter, class _Sent>
1066_LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
1067forward_list<_Tp, _Alloc>::__assign_with_sentinel(_Iter __f, _Sent __l) {
1068 iterator __i = before_begin();
1069 iterator __j = std::next(__i);
1070 iterator __e = end();
1071 for (; __j != __e && __f != __l; ++__i, (void)++__j, ++__f)
1072 *__j = *__f;
1073 if (__j == __e)
1074 __insert_after_with_sentinel(__i, std::move(__f), std::move(__l));
1075 else
1076 erase_after(__i, __e);
1077}
1078
1079template <class _Tp, class _Alloc>
1080_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) {
1081 iterator __i = before_begin();
1082 iterator __j = std::next(__i);
1083 iterator __e = end();
1084 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1085 *__j = __v;
1086 if (__j == __e)
1087 insert_after(__i, __n, __v);
1088 else
1089 erase_after(__i, __e);
1090}
1091
1092# ifndef _LIBCPP_CXX03_LANG
1093
1094template <class _Tp, class _Alloc>
1095_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) {
1096 assign(__il.begin(), __il.end());
1097}
1098
1099template <class _Tp, class _Alloc>
1100template <class... _Args>
1101_LIBCPP_CONSTEXPR_SINCE_CXX26
1102# if _LIBCPP_STD_VER >= 17
1103 typename forward_list<_Tp, _Alloc>::reference
1104# else
1105 void
1106# endif
1107 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) {
1108 __base::__before_begin()->__next_ =
1109 this->__create_node(/* next = */ __base::__before_begin()->__next_, std::forward<_Args>(__args)...);
1110# if _LIBCPP_STD_VER >= 17
1111 return __base::__before_begin()->__next_->__get_value();
1112# endif
1113}
1114
1115template <class _Tp, class _Alloc>
1116_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::push_front(value_type&& __v) {
1117 __base::__before_begin()->__next_ =
1118 this->__create_node(/* next = */ __base::__before_begin()->__next_, std::move(__v));
1119}
1120
1121# endif // _LIBCPP_CXX03_LANG
1122
1123template <class _Tp, class _Alloc>
1124_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::push_front(const value_type& __v) {
1125 __base::__before_begin()->__next_ = this->__create_node(/* next = */ __base::__before_begin()->__next_, __v);
1126}
1127
1128template <class _Tp, class _Alloc>
1129_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::pop_front() {
1130 _LIBCPP_ASSERT_NON_NULL(!empty(), "forward_list::pop_front called on an empty list");
1131 __node_pointer __p = __base::__before_begin()->__next_;
1132 __base::__before_begin()->__next_ = __p->__next_;
1133 this->__delete_node(__p);
1134}
1135
1136# ifndef _LIBCPP_CXX03_LANG
1137
1138template <class _Tp, class _Alloc>
1139template <class... _Args>
1140_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator
1141forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) {
1142 __begin_node_pointer const __r = __p.__ptr_;
1143 __r->__next_ = this->__create_node(/* next = */ __r->__next_, std::forward<_Args>(__args)...);
1144 return iterator(__r->__next_);
1145}
1146
1147template <class _Tp, class _Alloc>
1148_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator
1149forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) {
1150 __begin_node_pointer const __r = __p.__ptr_;
1151 __r->__next_ = this->__create_node(/* next = */ __r->__next_, std::move(__v));
1152 return iterator(__r->__next_);
1153}
1154
1155# endif // _LIBCPP_CXX03_LANG
1156
1157template <class _Tp, class _Alloc>
1158_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator
1159forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) {
1160 __begin_node_pointer const __r = __p.__ptr_;
1161 __r->__next_ = this->__create_node(/* next = */ __r->__next_, __v);
1162 return iterator(__r->__next_);
1163}
1164
1165template <class _Tp, class _Alloc>
1166template <class... _Args>
1167_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator
1168forward_list<_Tp, _Alloc>::__insert_after(const_iterator __p, size_type __n, _Args&&... __args) {
1169 __begin_node_pointer __r = __p.__ptr_;
1170 if (__n > 0) {
1171 __node_pointer __first = this->__create_node(/* next = */ nullptr, std::forward<_Args>(__args)...);
1172 __node_pointer __last = __first;
1173 auto __guard = std::__make_exception_guard([&] {
1174 while (__first != nullptr) {
1175 __node_pointer __next = __first->__next_;
1176 this->__delete_node(__first);
1177 __first = __next;
1178 }
1179 });
1180 for (--__n; __n != 0; --__n, __last = __last->__next_) {
1181 __last->__next_ = this->__create_node(/* next = */ nullptr, std::forward<_Args>(__args)...);
1182 }
1183 __guard.__complete();
1184 __last->__next_ = __r->__next_;
1185 __r->__next_ = __first;
1186 __r = std::__static_fancy_pointer_cast<__begin_node_pointer>(__last);
1187 }
1188 return iterator(__r);
1189}
1190
1191template <class _Tp, class _Alloc>
1192template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
1193_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator
1194forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l) {
1195 return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l));
1196}
1197
1198template <class _Tp, class _Alloc>
1199template <class _InputIterator, class _Sentinel>
1200_LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Alloc>::iterator
1201forward_list<_Tp, _Alloc>::__insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) {
1202 __begin_node_pointer __r = __p.__ptr_;
1203
1204 if (__f != __l) {
1205 __node_pointer __first = this->__create_node(/* next = */ nullptr, *__f);
1206 __node_pointer __last = __first;
1207
1208 auto __guard = std::__make_exception_guard([&] {
1209 while (__first != nullptr) {
1210 __node_pointer __next = __first->__next_;
1211 this->__delete_node(__first);
1212 __first = __next;
1213 }
1214 });
1215 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) {
1216 __last->__next_ = this->__create_node(/* next = */ nullptr, *__f);
1217 }
1218 __guard.__complete();
1219
1220 __last->__next_ = __r->__next_;
1221 __r->__next_ = __first;
1222 __r = std::__static_fancy_pointer_cast<__begin_node_pointer>(__last);
1223 }
1224
1225 return iterator(__r);
1226}
1227
1228template <class _Tp, class _Alloc>
1229_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator
1230forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) {
1231 __begin_node_pointer __p = __f.__ptr_;
1232 __node_pointer __n = __p->__next_;
1233 __p->__next_ = __n->__next_;
1234 this->__delete_node(__n);
1235 return iterator(__p->__next_);
1236}
1237
1238template <class _Tp, class _Alloc>
1239_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator
1240forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) {
1241 __node_pointer __e = std::__static_fancy_pointer_cast<__node_pointer>(__l.__ptr_);
1242 if (__f != __l) {
1243 __begin_node_pointer __bp = __f.__ptr_;
1244
1245 __node_pointer __n = __bp->__next_;
1246 if (__n != __e) {
1247 __bp->__next_ = __e;
1248 do {
1249 __node_pointer __tmp = __n->__next_;
1250 this->__delete_node(__n);
1251 __n = __tmp;
1252 } while (__n != __e);
1253 }
1254 }
1255 return iterator(__e);
1256}
1257
1258template <class _Tp, class _Alloc>
1259_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::resize(size_type __n) {
1260 size_type __sz = 0;
1261 iterator __p = before_begin();
1262 iterator __i = begin();
1263 iterator __e = end();
1264 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1265 ;
1266 if (__i != __e)
1267 erase_after(__p, __e);
1268 else
1269 __insert_after(__p, __n - __sz);
1270}
1271
1272template <class _Tp, class _Alloc>
1273_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) {
1274 size_type __sz = 0;
1275 iterator __p = before_begin();
1276 iterator __i = begin();
1277 iterator __e = end();
1278 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1279 ;
1280 if (__i != __e)
1281 erase_after(__p, __e);
1282 else
1283 __insert_after(__p, __n - __sz, __v);
1284}
1285
1286template <class _Tp, class _Alloc>
1287_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& __x) {
1288 if (!__x.empty()) {
1289 if (__p.__ptr_->__next_ != nullptr) {
1290 const_iterator __lm1 = __x.before_begin();
1291 while (__lm1.__ptr_->__next_ != nullptr)
1292 ++__lm1;
1293 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1294 }
1295 __p.__ptr_->__next_ = __x.__before_begin()->__next_;
1296 __x.__before_begin()->__next_ = nullptr;
1297 }
1298}
1299
1300template <class _Tp, class _Alloc>
1301_LIBCPP_CONSTEXPR_SINCE_CXX26 void
1302forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& /*__other*/, const_iterator __i) {
1303 const_iterator __lm1 = std::next(__i);
1304 if (__p != __i && __p != __lm1) {
1305 __i.__ptr_->__next_ = __lm1.__ptr_->__next_;
1306 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1307 __p.__ptr_->__next_ = std::__static_fancy_pointer_cast<__node_pointer>(__lm1.__ptr_);
1308 }
1309}
1310
1311template <class _Tp, class _Alloc>
1312_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::splice_after(
1313 const_iterator __p, forward_list& /*__other*/, const_iterator __f, const_iterator __l) {
1314 if (__f != __l && __p != __f) {
1315 const_iterator __lm1 = __f;
1316 while (__lm1.__ptr_->__next_ != __l.__ptr_)
1317 ++__lm1;
1318 if (__f != __lm1) {
1319 __lm1.__ptr_->__next_ = __p.__ptr_->__next_;
1320 __p.__ptr_->__next_ = __f.__ptr_->__next_;
1321 __f.__ptr_->__next_ = std::__static_fancy_pointer_cast<__node_pointer>(__l.__ptr_);
1322 }
1323 }
1324}
1325
1326template <class _Tp, class _Alloc>
1327_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI void
1328forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x) {
1329 splice_after(__p, __x);
1330}
1331
1332template <class _Tp, class _Alloc>
1333_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI void
1334forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x, const_iterator __i) {
1335 splice_after(__p, __x, __i);
1336}
1337
1338template <class _Tp, class _Alloc>
1339_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(
1340 const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l) {
1341 splice_after(__p, __x, __f, __l);
1342}
1343
1344template <class _Tp, class _Alloc>
1345_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::__remove_return_type
1346forward_list<_Tp, _Alloc>::remove(const value_type& __v) {
1347 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1348 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1349 const iterator __e = end();
1350 for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;) {
1351 if (__i.__ptr_->__next_->__get_value() == __v) {
1352 ++__count_removed;
1353 iterator __j = std::next(__i, 2);
1354 for (; __j != __e && *__j == __v; ++__j)
1355 ++__count_removed;
1356 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1357 if (__j == __e)
1358 break;
1359 __i = __j;
1360 } else
1361 ++__i;
1362 }
1363
1364 return (__remove_return_type)__count_removed;
1365}
1366
1367template <class _Tp, class _Alloc>
1368template <class _Predicate>
1369_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::__remove_return_type
1370forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) {
1371 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1372 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1373 const iterator __e = end();
1374 for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;) {
1375 if (__pred(__i.__ptr_->__next_->__get_value())) {
1376 ++__count_removed;
1377 iterator __j = std::next(__i, 2);
1378 for (; __j != __e && __pred(*__j); ++__j)
1379 ++__count_removed;
1380 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1381 if (__j == __e)
1382 break;
1383 __i = __j;
1384 } else
1385 ++__i;
1386 }
1387
1388 return (__remove_return_type)__count_removed;
1389}
1390
1391template <class _Tp, class _Alloc>
1392template <class _BinaryPredicate>
1393_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::__remove_return_type
1394forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) {
1395 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1396 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1397 for (iterator __i = begin(), __e = end(); __i != __e;) {
1398 iterator __j = std::next(__i);
1399 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1400 ++__count_removed;
1401 if (__i.__ptr_->__next_ != std::__static_fancy_pointer_cast<__node_pointer>(__j.__ptr_))
1402 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1403 __i = __j;
1404 }
1405
1406 return (__remove_return_type)__count_removed;
1407}
1408
1409template <class _Tp, class _Alloc>
1410template <class _Compare>
1411_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) {
1412 if (this != std::addressof(__x)) {
1413 __base::__before_begin()->__next_ =
1414 __merge(__base::__before_begin()->__next_, __x.__before_begin()->__next_, __comp);
1415 __x.__before_begin()->__next_ = nullptr;
1416 }
1417}
1418
1419template <class _Tp, class _Alloc>
1420template <class _Compare>
1421_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::__node_pointer
1422forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp) {
1423 if (__f1 == nullptr)
1424 return __f2;
1425 if (__f2 == nullptr)
1426 return __f1;
1427 __node_pointer __r;
1428 if (__comp(__f2->__get_value(), __f1->__get_value())) {
1429 __node_pointer __t = __f2;
1430 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))
1431 __t = __t->__next_;
1432 __r = __f2;
1433 __f2 = __t->__next_;
1434 __t->__next_ = __f1;
1435 } else
1436 __r = __f1;
1437 __node_pointer __p = __f1;
1438 __f1 = __f1->__next_;
1439 while (__f1 != nullptr && __f2 != nullptr) {
1440 if (__comp(__f2->__get_value(), __f1->__get_value())) {
1441 __node_pointer __t = __f2;
1442 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))
1443 __t = __t->__next_;
1444 __p->__next_ = __f2;
1445 __f2 = __t->__next_;
1446 __t->__next_ = __f1;
1447 }
1448 __p = __f1;
1449 __f1 = __f1->__next_;
1450 }
1451 if (__f2 != nullptr)
1452 __p->__next_ = __f2;
1453 return __r;
1454}
1455
1456template <class _Tp, class _Alloc>
1457template <class _Compare>
1458_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void forward_list<_Tp, _Alloc>::sort(_Compare __comp) {
1459 __base::__before_begin()->__next_ = __sort(__base::__before_begin()->__next_, std::distance(begin(), end()), __comp);
1460}
1461
1462template <class _Tp, class _Alloc>
1463template <class _Compare>
1464_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::__node_pointer
1465forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, _Compare& __comp) {
1466 switch (__sz) {
1467 case 0:
1468 case 1:
1469 return __f1;
1470 case 2:
1471 if (__comp(__f1->__next_->__get_value(), __f1->__get_value())) {
1472 __node_pointer __t = __f1->__next_;
1473 __t->__next_ = __f1;
1474 __f1->__next_ = nullptr;
1475 __f1 = __t;
1476 }
1477 return __f1;
1478 }
1479 difference_type __sz1 = __sz / 2;
1480 difference_type __sz2 = __sz - __sz1;
1481 __node_pointer __t = std::__static_fancy_pointer_cast<__node_pointer>(std::next(iterator(__f1), __sz1 - 1).__ptr_);
1482 __node_pointer __f2 = __t->__next_;
1483 __t->__next_ = nullptr;
1484 return __merge(__sort(__f1, __sz1, __comp), __sort(__f2, __sz2, __comp), __comp);
1485}
1486
1487template <class _Tp, class _Alloc>
1488_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT {
1489 __node_pointer __p = __base::__before_begin()->__next_;
1490 if (__p != nullptr) {
1491 __node_pointer __f = __p->__next_;
1492 __p->__next_ = nullptr;
1493 while (__f != nullptr) {
1494 __node_pointer __t = __f->__next_;
1495 __f->__next_ = __p;
1496 __p = __f;
1497 __f = __t;
1498 }
1499 __base::__before_begin()->__next_ = __p;
1500 }
1501}
1502
1503template <class _Tp, class _Alloc>
1504_LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI bool
1505operator==(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1506 typedef forward_list<_Tp, _Alloc> _Cp;
1507 typedef typename _Cp::const_iterator _Ip;
1508 _Ip __ix = __x.begin();
1509 _Ip __ex = __x.end();
1510 _Ip __iy = __y.begin();
1511 _Ip __ey = __y.end();
1512 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1513 if (!(*__ix == *__iy))
1514 return false;
1515 return (__ix == __ex) == (__iy == __ey);
1516}
1517
1518# if _LIBCPP_STD_VER <= 17
1519
1520template <class _Tp, class _Alloc>
1521_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI bool
1522operator!=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1523 return !(__x == __y);
1524}
1525
1526template <class _Tp, class _Alloc>
1527_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI bool
1528operator<(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1529 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1530}
1531
1532template <class _Tp, class _Alloc>
1533_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI bool
1534operator>(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1535 return __y < __x;
1536}
1537
1538template <class _Tp, class _Alloc>
1539_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI bool
1540operator>=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1541 return !(__x < __y);
1542}
1543
1544template <class _Tp, class _Alloc>
1545_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI bool
1546operator<=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1547 return !(__y < __x);
1548}
1549
1550# else // #if _LIBCPP_STD_VER <= 17
1551
1552template <class _Tp, class _Allocator>
1553_LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp>
1554operator<=>(const forward_list<_Tp, _Allocator>& __x, const forward_list<_Tp, _Allocator>& __y) {
1555 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1556}
1557
1558# endif // #if _LIBCPP_STD_VER <= 17
1559
1560template <class _Tp, class _Alloc>
1561_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI void
1562swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1563 __x.swap(__y);
1564}
1565
1566# if _LIBCPP_STD_VER >= 20
1567template <class _Tp, class _Allocator, class _Predicate>
1568_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Allocator>::size_type
1569erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) {
1570 return __c.remove_if(__pred);
1571}
1572
1573template <class _Tp, class _Allocator, class _Up>
1574_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Allocator>::size_type
1575erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) {
1576 return std::erase_if(__c, [&](const auto& __elem) -> bool { return __elem == __v; });
1577}
1578# endif
1579
1580template <class _Tp, class _Allocator>
1581struct __container_traits<forward_list<_Tp, _Allocator> > {
1582 // http://eel.is/c++draft/container.reqmts
1583 // Unless otherwise specified (see [associative.reqmts.except], [unord.req.except], [deque.modifiers],
1584 // [inplace.vector.modifiers], and [vector.modifiers]) all container types defined in this Clause meet the following
1585 // additional requirements:
1586 // - If an exception is thrown by an insert() or emplace() function while inserting a single element, that
1587 // function has no effects.
1588 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1589
1590 static _LIBCPP_CONSTEXPR const bool __reservable = false;
1591};
1592
1593_LIBCPP_END_NAMESPACE_STD
1594
1595# if _LIBCPP_STD_VER >= 17
1596_LIBCPP_BEGIN_NAMESPACE_STD
1597namespace pmr {
1598template <class _ValueT>
1599using forward_list _LIBCPP_AVAILABILITY_PMR = std::forward_list<_ValueT, polymorphic_allocator<_ValueT>>;
1600} // namespace pmr
1601_LIBCPP_END_NAMESPACE_STD
1602# endif
1603
1604_LIBCPP_POP_MACROS
1605
1606# if defined(_LIBCPP_KEEP_TRANSITIVE_INCLUDES_LLVM23) && _LIBCPP_STD_VER <= 20
1607# include <algorithm>
1608# include <atomic>
1609# include <concepts>
1610# include <cstdint>
1611# include <cstdlib>
1612# include <cstring>
1613# include <functional>
1614# include <iosfwd>
1615# include <iterator>
1616# include <stdexcept>
1617# include <type_traits>
1618# include <typeinfo>
1619# endif
1620#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
1621
1622#endif // _LIBCPP_FORWARD_LIST
1623