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/forward.h>
238# include <__utility/move.h>
239# include <__utility/swap.h>
240# include <limits>
241# include <version>
242
243// standard-mandated includes
244
245// [iterator.range]
246# include <__iterator/access.h>
247# include <__iterator/data.h>
248# include <__iterator/empty.h>
249# include <__iterator/reverse_access.h>
250# include <__iterator/size.h>
251
252// [forward.list.syn]
253# include <compare>
254# include <initializer_list>
255
256# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
257# pragma GCC system_header
258# endif
259
260_LIBCPP_PUSH_MACROS
261# include <__undef_macros>
262
263_LIBCPP_BEGIN_NAMESPACE_STD
264
265template <class _Tp, class _VoidPtr>
266struct __forward_list_node;
267template <class _NodePtr>
268struct __forward_begin_node;
269
270template <class>
271struct __forward_list_node_value_type;
272
273template <class _Tp, class _VoidPtr>
274struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
275 typedef _Tp type;
276};
277
278template <class _NodePtr>
279struct __forward_node_traits {
280 typedef __remove_cv_t<typename pointer_traits<_NodePtr>::element_type> __node_type;
281 typedef typename __forward_list_node_value_type<__node_type>::type __node_value_type;
282 typedef _NodePtr __node_pointer;
283 typedef __forward_begin_node<_NodePtr> __begin_node;
284 typedef __rebind_pointer_t<_NodePtr, __begin_node> __begin_node_pointer;
285};
286
287template <class _NodePtr>
288struct __forward_begin_node {
289 typedef _NodePtr pointer;
290 typedef __rebind_pointer_t<_NodePtr, __forward_begin_node> __begin_node_pointer;
291
292 pointer __next_;
293
294 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __forward_begin_node() : __next_(nullptr) {}
295 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit __forward_begin_node(pointer __n) : __next_(__n) {}
296};
297
298template <class _Tp, class _VoidPtr>
299using __begin_node_of _LIBCPP_NODEBUG =
300 __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >;
301
302template <class _Tp, class _VoidPtr>
303struct __forward_list_node : public __begin_node_of<_Tp, _VoidPtr> {
304 typedef _Tp value_type;
305 typedef __begin_node_of<_Tp, _VoidPtr> _Base;
306 typedef typename _Base::pointer _NodePtr;
307
308 // We allow starting the lifetime of nodes without initializing the value held by the node,
309 // since that is handled by the list itself in order to be allocator-aware.
310# ifndef _LIBCPP_CXX03_LANG
311
312private:
313 union {
314 _Tp __value_;
315 };
316
317public:
318 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
319# else
320
321private:
322 _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
323
324public:
325 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
326# endif
327
328 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_node(_NodePtr __next) : _Base(__next) {}
329 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI ~__forward_list_node() {}
330};
331
332template <class _Tp, class _Alloc = allocator<_Tp> >
333class forward_list;
334template <class _NodeConstPtr>
335class __forward_list_const_iterator;
336
337template <class _NodePtr>
338class __forward_list_iterator {
339 typedef __forward_node_traits<_NodePtr> __traits;
340 typedef typename __traits::__node_type __node_type;
341 typedef typename __traits::__begin_node __begin_node_type;
342 typedef typename __traits::__node_pointer __node_pointer;
343 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
344
345 __begin_node_pointer __ptr_;
346
347 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(nullptr_t) _NOEXCEPT
348 : __ptr_(nullptr) {}
349
350 _LIBCPP_CONSTEXPR_SINCE_CXX26
351 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
352
353 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
354 : __ptr_(std::__static_fancy_pointer_cast<__begin_node_pointer>(__p)) {}
355
356 template <class, class>
357 friend class forward_list;
358 template <class>
359 friend class __forward_list_const_iterator;
360
361public:
362 typedef forward_iterator_tag iterator_category;
363 typedef typename __traits::__node_value_type value_type;
364 typedef value_type& reference;
365 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
366 typedef __rebind_pointer_t<__node_pointer, value_type> pointer;
367
368 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
369
370 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI reference operator*() const {
371 return std::__static_fancy_pointer_cast<__node_pointer>(__ptr_)->__get_value();
372 }
373 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
374 return pointer_traits<pointer>::pointer_to(std::__static_fancy_pointer_cast<__node_pointer>(__ptr_)->__get_value());
375 }
376
377 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator& operator++() {
378 __ptr_ = std::__static_fancy_pointer_cast<__begin_node_pointer>(__ptr_->__next_);
379 return *this;
380 }
381 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator operator++(int) {
382 __forward_list_iterator __t(*this);
383 ++(*this);
384 return __t;
385 }
386
387 friend _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI bool
388 operator==(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {
389 return __x.__ptr_ == __y.__ptr_;
390 }
391 friend _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI bool
392 operator!=(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {
393 return !(__x == __y);
394 }
395};
396
397template <class _NodeConstPtr>
398class __forward_list_const_iterator {
399 static_assert(!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value, "");
400 typedef _NodeConstPtr _NodePtr;
401
402 typedef __forward_node_traits<_NodePtr> __traits;
403 typedef typename __traits::__node_type __node_type;
404 typedef typename __traits::__begin_node __begin_node_type;
405 typedef typename __traits::__node_pointer __node_pointer;
406 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
407
408 __begin_node_pointer __ptr_;
409
410 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT
411 : __ptr_(nullptr) {}
412
413 _LIBCPP_CONSTEXPR_SINCE_CXX26
414 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
415
416 _LIBCPP_CONSTEXPR_SINCE_CXX26
417 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
418 : __ptr_(std::__static_fancy_pointer_cast<__begin_node_pointer>(__p)) {}
419
420 template <class, class>
421 friend class forward_list;
422
423public:
424 typedef forward_iterator_tag iterator_category;
425 typedef typename __traits::__node_value_type value_type;
426 typedef const value_type& reference;
427 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
428 typedef __rebind_pointer_t<__node_pointer, const value_type> pointer;
429
430 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
431 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
432 __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT : __ptr_(__p.__ptr_) {}
433
434 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI reference operator*() const {
435 return std::__static_fancy_pointer_cast<__node_pointer>(__ptr_)->__get_value();
436 }
437 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
438 return pointer_traits<pointer>::pointer_to(std::__static_fancy_pointer_cast<__node_pointer>(__ptr_)->__get_value());
439 }
440
441 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator& operator++() {
442 __ptr_ = std::__static_fancy_pointer_cast<__begin_node_pointer>(__ptr_->__next_);
443 return *this;
444 }
445 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator operator++(int) {
446 __forward_list_const_iterator __t(*this);
447 ++(*this);
448 return __t;
449 }
450
451 friend _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI bool
452 operator==(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {
453 return __x.__ptr_ == __y.__ptr_;
454 }
455 friend _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI bool
456 operator!=(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {
457 return !(__x == __y);
458 }
459};
460
461template <class _Tp, class _Alloc>
462class __forward_list_base {
463protected:
464 typedef _Tp value_type;
465 typedef _Alloc allocator_type;
466
467 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
468 typedef __forward_list_node<value_type, void_pointer> __node_type;
469 typedef __begin_node_of<value_type, void_pointer> __begin_node;
470 typedef __rebind_alloc<allocator_traits<allocator_type>, __node_type> __node_allocator;
471 typedef allocator_traits<__node_allocator> __node_traits;
472 typedef typename __node_traits::pointer __node_pointer;
473
474 typedef __rebind_alloc<allocator_traits<allocator_type>, __begin_node> __begin_node_allocator;
475 typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer;
476
477 _LIBCPP_COMPRESSED_PAIR(__begin_node, __before_begin_, __node_allocator, __alloc_);
478
479 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() _NOEXCEPT {
480 return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_);
481 }
482
483 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() const _NOEXCEPT {
484 return pointer_traits<__begin_node_pointer>::pointer_to(
485 *const_cast<__begin_node*>(std::addressof(__before_begin_)));
486 }
487
488 typedef __forward_list_iterator<__node_pointer> iterator;
489 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
490
491 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __forward_list_base()
492 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
493 : __before_begin_(__begin_node()) {}
494 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const allocator_type& __a)
495 : __before_begin_(__begin_node()), __alloc_(__node_allocator(__a)) {}
496 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const __node_allocator& __a)
497 : __before_begin_(__begin_node()), __alloc_(__a) {}
498
499public:
500# ifndef _LIBCPP_CXX03_LANG
501 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
502 __forward_list_base(__forward_list_base&& __x) noexcept(is_nothrow_move_constructible<__node_allocator>::value);
503 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
504 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
505# endif // _LIBCPP_CXX03_LANG
506
507 __forward_list_base(const __forward_list_base&) = delete;
508 __forward_list_base& operator=(const __forward_list_base&) = delete;
509
510 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI ~__forward_list_base();
511
512protected:
513 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x) {
514 __copy_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
515 }
516
517 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x)
518 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
519 is_nothrow_move_assignable<__node_allocator>::value) {
520 __move_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
521 }
522
523 template <class... _Args>
524 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __node_pointer
525 __create_node(__node_pointer __next, _Args&&... __args) {
526 __allocation_guard<__node_allocator> __guard(__alloc_, 1);
527 // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
528 // held inside the node, since we need to use the allocator's construct() method for that.
529 //
530 // We don't use the allocator's construct() method to construct the node itself since the
531 // Cpp17FooInsertable named requirements don't require the allocator's construct() method
532 // to work on anything other than the value_type.
533 std::__construct_at(std::addressof(*__guard.__get()), __next);
534
535 // Now construct the value_type using the allocator's construct() method.
536 __node_traits::construct(__alloc_, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
537 return __guard.__release_ptr();
538 }
539
540 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
541 // For the same reason as above, we use the allocator's destroy() method for the value_type,
542 // but not for the node itself.
543 __node_traits::destroy(__alloc_, std::addressof(__node->__get_value()));
544 std::__destroy_at(std::addressof(*__node));
545 __node_traits::deallocate(__alloc_, __node, 1);
546 }
547
548public:
549 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void swap(__forward_list_base& __x)
550# if _LIBCPP_STD_VER >= 14
551 _NOEXCEPT;
552# else
553 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>);
554# endif
555
556protected:
557 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
558
559private:
560 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base&, false_type) {
561 }
562 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
563 __copy_assign_alloc(const __forward_list_base& __x, true_type) {
564 if (__alloc_ != __x.__alloc_)
565 clear();
566 __alloc_ = __x.__alloc_;
567 }
568
569 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
570 __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT {}
571 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x, true_type)
572 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {
573 __alloc_ = std::move(__x.__alloc_);
574 }
575};
576
577# ifndef _LIBCPP_CXX03_LANG
578
579template <class _Tp, class _Alloc>
580_LIBCPP_CONSTEXPR_SINCE_CXX26 inline __forward_list_base<_Tp, _Alloc>::__forward_list_base(
581 __forward_list_base&& __x) noexcept(is_nothrow_move_constructible<__node_allocator>::value)
582 : __before_begin_(std::move(__x.__before_begin_)), __alloc_(std::move(__x.__alloc_)) {
583 __x.__before_begin()->__next_ = nullptr;
584}
585
586template <class _Tp, class _Alloc>
587_LIBCPP_CONSTEXPR_SINCE_CXX26 inline __forward_list_base<_Tp, _Alloc>::__forward_list_base(
588 __forward_list_base&& __x, const allocator_type& __a)
589 : __before_begin_(__begin_node()), __alloc_(__node_allocator(__a)) {
590 if (__alloc_ == __x.__alloc_) {
591 __before_begin()->__next_ = __x.__before_begin()->__next_;
592 __x.__before_begin()->__next_ = nullptr;
593 }
594}
595
596# endif // _LIBCPP_CXX03_LANG
597
598template <class _Tp, class _Alloc>
599_LIBCPP_CONSTEXPR_SINCE_CXX26 __forward_list_base<_Tp, _Alloc>::~__forward_list_base() {
600 clear();
601}
602
603template <class _Tp, class _Alloc>
604_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
605# if _LIBCPP_STD_VER >= 14
606 _NOEXCEPT
607# else
608 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
609# endif
610{
611 std::__swap_allocator(__alloc_, __x.__alloc_);
612 using std::swap;
613 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
614}
615
616template <class _Tp, class _Alloc>
617_LIBCPP_CONSTEXPR_SINCE_CXX26 void __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT {
618 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) {
619 __node_pointer __next = __p->__next_;
620 __delete_node(node: __p);
621 __p = __next;
622 }
623 __before_begin()->__next_ = nullptr;
624}
625
626template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
627class forward_list : private __forward_list_base<_Tp, _Alloc> {
628 typedef __forward_list_base<_Tp, _Alloc> __base;
629 typedef typename __base::__node_allocator __node_allocator;
630 typedef typename __base::__node_type __node_type;
631 typedef typename __base::__node_traits __node_traits;
632 typedef typename __base::__node_pointer __node_pointer;
633 typedef typename __base::__begin_node_pointer __begin_node_pointer;
634
635public:
636 typedef _Tp value_type;
637 typedef _Alloc allocator_type;
638
639 static_assert(__check_valid_allocator<allocator_type>::value, "");
640
641 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
642 "Allocator::value_type must be same type as value_type");
643
644 static_assert(!is_same<allocator_type, __node_allocator>::value,
645 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");
646
647 typedef value_type& reference;
648 typedef const value_type& const_reference;
649 typedef typename allocator_traits<allocator_type>::pointer pointer;
650 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
651 typedef typename allocator_traits<allocator_type>::size_type size_type;
652 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
653
654 typedef typename __base::iterator iterator;
655 typedef typename __base::const_iterator const_iterator;
656# if _LIBCPP_STD_VER >= 20
657 typedef size_type __remove_return_type;
658# else
659 typedef void __remove_return_type;
660# endif
661
662 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list()
663 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) {} // = default;
664 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit forward_list(const allocator_type& __a);
665 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n);
666# if _LIBCPP_STD_VER >= 14
667 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n, const allocator_type& __a);
668# endif
669 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v);
670
671 template <__enable_if_t<__is_allocator_v<_Alloc>, int> = 0>
672 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
673 forward_list(size_type __n, const value_type& __v, const allocator_type& __a)
674 : __base(__a) {
675 insert_after(cbefore_begin(), __n, __v);
676 }
677
678 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
679 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l);
680
681 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
682 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
683 forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a);
684
685# if _LIBCPP_STD_VER >= 23
686 template <_ContainerCompatibleRange<_Tp> _Range>
687 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
688 forward_list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
689 : __base(__a) {
690 prepend_range(std::forward<_Range>(__range));
691 }
692# endif
693
694 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x);
695 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
696 forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);
697
698 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(const forward_list& __x);
699
700# ifndef _LIBCPP_CXX03_LANG
701 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
702 forward_list(forward_list&& __x) noexcept(is_nothrow_move_constructible<__base>::value)
703 : __base(std::move(__x)) {}
704 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
705 forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a);
706
707 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(initializer_list<value_type> __il);
708 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI
709 forward_list(initializer_list<value_type> __il, const allocator_type& __a);
710
711 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(forward_list&& __x) noexcept(
712 (__node_traits::propagate_on_container_move_assignment::value &&
713 is_nothrow_move_assignable<allocator_type>::value) ||
714 allocator_traits<allocator_type>::is_always_equal::value);
715
716 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(initializer_list<value_type> __il);
717
718 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il);
719# endif // _LIBCPP_CXX03_LANG
720
721 // ~forward_list() = default;
722
723 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
724 _LIBCPP_CONSTEXPR_SINCE_CXX26 void _LIBCPP_HIDE_FROM_ABI assign(_InputIterator __f, _InputIterator __l);
725
726# if _LIBCPP_STD_VER >= 23
727 template <_ContainerCompatibleRange<_Tp> _Range>
728 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
729 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
730 }
731# endif
732
733 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);
734
735 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
736 return allocator_type(this->__alloc_);
737 }
738
739 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT {
740 return iterator(__base::__before_begin()->__next_);
741 }
742 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {
743 return const_iterator(__base::__before_begin()->__next_);
744 }
745 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT {
746 return iterator(nullptr);
747 }
748 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT {
749 return const_iterator(nullptr);
750 }
751
752 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT {
753 return const_iterator(__base::__before_begin()->__next_);
754 }
755 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT {
756 return const_iterator(nullptr);
757 }
758
759 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT {
760 return iterator(__base::__before_begin());
761 }
762 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT {
763 return const_iterator(__base::__before_begin());
764 }
765 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT {
766 return const_iterator(__base::__before_begin());
767 }
768
769 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {
770 return __base::__before_begin()->__next_ == nullptr;
771 }
772 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
773 return std::min<size_type>(__node_traits::max_size(this->__alloc_), numeric_limits<difference_type>::max());
774 }
775
776 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI reference front() {
777 _LIBCPP_ASSERT_NON_NULL(!empty(), "forward_list::front called on an empty list");
778 return __base::__before_begin()->__next_->__get_value();
779 }
780 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_reference front() const {
781 _LIBCPP_ASSERT_NON_NULL(!empty(), "forward_list::front called on an empty list");
782 return __base::__before_begin()->__next_->__get_value();
783 }
784
785# ifndef _LIBCPP_CXX03_LANG
786# if _LIBCPP_STD_VER >= 17
787 template <class... _Args>
788 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
789# else
790 template <class... _Args>
791 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
792# endif
793 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v);
794# endif // _LIBCPP_CXX03_LANG
795 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);
796
797# if _LIBCPP_STD_VER >= 23
798 template <_ContainerCompatibleRange<_Tp> _Range>
799 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) {
800 insert_range_after(cbefore_begin(), std::forward<_Range>(__range));
801 }
802# endif
803
804 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void pop_front();
805
806# ifndef _LIBCPP_CXX03_LANG
807 template <class... _Args>
808 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator emplace_after(const_iterator __p, _Args&&... __args);
809
810 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, value_type&& __v);
811 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
812 insert_after(const_iterator __p, initializer_list<value_type> __il) {
813 return insert_after(__p, __il.begin(), __il.end());
814 }
815# endif // _LIBCPP_CXX03_LANG
816 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, const value_type& __v);
817 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
818 insert_after(const_iterator __p, size_type __n, const value_type& __v) {
819 return __insert_after(__p, __n, __v);
820 }
821 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
822 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
823 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
824
825# if _LIBCPP_STD_VER >= 23
826 template <_ContainerCompatibleRange<_Tp> _Range>
827 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
828 insert_range_after(const_iterator __position, _Range&& __range) {
829 return __insert_after_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
830 }
831# endif
832
833 template <class _InputIterator, class _Sentinel>
834 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
835 __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l);
836
837 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p);
838 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l);
839
840 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x)
841# if _LIBCPP_STD_VER >= 14
842 _NOEXCEPT
843# else
844 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
845# endif
846 {
847 __base::swap(__x);
848 }
849
850 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
851 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v);
852 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __base::clear(); }
853
854 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x);
855 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
856 splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
857 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
858 splice_after(const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l);
859 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x);
860 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
861 splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
862 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void
863 splice_after(const_iterator __p, forward_list& __x, const_iterator __f, const_iterator __l);
864 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __v);
865 template <class _Predicate>
866 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Predicate __pred);
867 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }
868 template <class _BinaryPredicate>
869 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred);
870# ifndef _LIBCPP_CXX03_LANG
871 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x) { merge(__x, __less<>()); }
872 template <class _Compare>
873 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x, _Compare __comp) {
874 merge(__x, std::move(__comp));
875 }
876# endif // _LIBCPP_CXX03_LANG
877 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x) { merge(__x, __less<>()); }
878 template <class _Compare>
879 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp);
880 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void sort() { sort(__less<>()); }
881 template <class _Compare>
882 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void sort(_Compare __comp);
883 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
884
885private:
886# ifndef _LIBCPP_CXX03_LANG
887 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, true_type)
888 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
889 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, false_type);
890# endif // _LIBCPP_CXX03_LANG
891
892 template <class _Iter, class _Sent>
893 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iter __f, _Sent __l);
894
895 template <class... _Args>
896 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator
897 __insert_after(const_iterator __p, size_type __n, _Args&&... __args);
898
899 template <class _Compare>
900 _LIBCPP_CONSTEXPR_SINCE_CXX26 static _LIBCPP_HIDE_FROM_ABI __node_pointer
901 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
902
903 // TODO: Make this _LIBCPP_HIDE_FROM_ABI
904 template <class _Compare>
905 _LIBCPP_CONSTEXPR_SINCE_CXX26 static _LIBCPP_HIDDEN __node_pointer
906 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
907};
908
909# if _LIBCPP_STD_VER >= 17
910template <class _InputIterator,
911 class _Alloc = allocator<__iterator_value_type<_InputIterator>>,
912 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
913 class = enable_if_t<__is_allocator_v<_Alloc>>>
914forward_list(_InputIterator, _InputIterator) -> forward_list<__iterator_value_type<_InputIterator>, _Alloc>;
915
916template <class _InputIterator,
917 class _Alloc,
918 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
919 class = enable_if_t<__is_allocator_v<_Alloc>>>
920forward_list(_InputIterator, _InputIterator, _Alloc) -> forward_list<__iterator_value_type<_InputIterator>, _Alloc>;
921# endif
922
923# if _LIBCPP_STD_VER >= 23
924template <ranges::input_range _Range,
925 class _Alloc = allocator<ranges::range_value_t<_Range>>,
926 class = enable_if_t<__is_allocator_v<_Alloc>>>
927forward_list(from_range_t, _Range&&, _Alloc = _Alloc()) -> forward_list<ranges::range_value_t<_Range>, _Alloc>;
928# endif
929
930template <class _Tp, class _Alloc>
931_LIBCPP_CONSTEXPR_SINCE_CXX26 inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : __base(__a) {}
932
933template <class _Tp, class _Alloc>
934_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(size_type __n) {
935 if (__n > 0) {
936 for (__begin_node_pointer __p = __base::__before_begin(); __n > 0;
937 --__n, __p = std::__static_fancy_pointer_cast<__begin_node_pointer>(__p->__next_)) {
938 __p->__next_ = this->__create_node(/* next = */ nullptr);
939 }
940 }
941}
942
943# if _LIBCPP_STD_VER >= 14
944template <class _Tp, class _Alloc>
945_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __base_alloc)
946 : __base(__base_alloc) {
947 if (__n > 0) {
948 for (__begin_node_pointer __p = __base::__before_begin(); __n > 0;
949 --__n, __p = std::__static_fancy_pointer_cast<__begin_node_pointer>(__p->__next_)) {
950 __p->__next_ = this->__create_node(/* next = */ nullptr);
951 }
952 }
953}
954# endif
955
956template <class _Tp, class _Alloc>
957_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) {
958 insert_after(cbefore_begin(), __n, __v);
959}
960
961template <class _Tp, class _Alloc>
962template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
963_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) {
964 insert_after(cbefore_begin(), __f, __l);
965}
966
967template <class _Tp, class _Alloc>
968template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
969_LIBCPP_CONSTEXPR_SINCE_CXX26
970forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
971 : __base(__a) {
972 insert_after(cbefore_begin(), __f, __l);
973}
974
975template <class _Tp, class _Alloc>
976_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
977 : __base(__node_traits::select_on_container_copy_construction(__x.__alloc_)) {
978 insert_after(cbefore_begin(), __x.begin(), __x.end());
979}
980
981template <class _Tp, class _Alloc>
982_LIBCPP_CONSTEXPR_SINCE_CXX26
983forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a)
984 : __base(__a) {
985 insert_after(cbefore_begin(), __x.begin(), __x.end());
986}
987
988template <class _Tp, class _Alloc>
989_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) {
990 if (this != std::addressof(__x)) {
991 __base::__copy_assign_alloc(__x);
992 assign(__x.begin(), __x.end());
993 }
994 return *this;
995}
996
997# ifndef _LIBCPP_CXX03_LANG
998template <class _Tp, class _Alloc>
999_LIBCPP_CONSTEXPR_SINCE_CXX26
1000forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a)
1001 : __base(std::move(__x), __a) {
1002 if (this->__alloc_ != __x.__alloc_) {
1003 typedef move_iterator<iterator> _Ip;
1004 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
1005 }
1006}
1007
1008template <class _Tp, class _Alloc>
1009_LIBCPP_CONSTEXPR_SINCE_CXX26 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) {
1010 insert_after(cbefore_begin(), __il.begin(), __il.end());
1011}
1012
1013template <class _Tp, class _Alloc>
1014_LIBCPP_CONSTEXPR_SINCE_CXX26
1015forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, const allocator_type& __a)
1016 : __base(__a) {
1017 insert_after(cbefore_begin(), __il.begin(), __il.end());
1018}
1019
1020template <class _Tp, class _Alloc>
1021_LIBCPP_CONSTEXPR_SINCE_CXX26 void forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
1022 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
1023 clear();
1024 __base::__move_assign_alloc(__x);
1025 __base::__before_begin()->__next_ = __x.__before_begin()->__next_;
1026 __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_REMOVE_TRANSITIVE_INCLUDES) && _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