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