1623 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP_FORWARD_LIST11#define _LIBCPP_FORWARD_LIST12 13/*14 forward_list synopsis15 16namespace std17{18 19template <class T, class Allocator = allocator<T>>20class forward_list21{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++1441 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++2349 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++2370 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++1794 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++2398 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++23111 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++17118 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++20132 template <class Predicate>133 size_type remove_if(Predicate pred); // void before C++20134 size_type unique(); // void before C++20135 template <class BinaryPredicate>136 size_type unique(BinaryPredicate binary_pred); // void before C++20137 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++17150 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++23154 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++20162 163template <class T, class Allocator>164 bool operator!=(const forward_list<T, Allocator>& x,165 const forward_list<T, Allocator>& y); // removed in C++20166 167template <class T, class Allocator>168 bool operator> (const forward_list<T, Allocator>& x,169 const forward_list<T, Allocator>& y); // removed in C++20170 171template <class T, class Allocator>172 bool operator>=(const forward_list<T, Allocator>& x,173 const forward_list<T, Allocator>& y); // removed in C++20174 175template <class T, class Allocator>176 bool operator<=(const forward_list<T, Allocator>& x,177 const forward_list<T, Allocator>& y); // removed in C++20178 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++20182 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_type189 erase(forward_list<T, Allocator>& c, const U& value); // C++20190template <class T, class Allocator, class Predicate>191 typename forward_list<T, Allocator>::size_type192 erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20193 194} // std195 196*/197 198#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)199# include <__cxx03/forward_list>200#else201# 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 includes244 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_header258# endif259 260_LIBCPP_PUSH_MACROS261# include <__undef_macros>262 263_LIBCPP_BEGIN_NAMESPACE_STD264 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_LANG311 312private:313 union {314 _Tp __value_;315 };316 317public:318 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }319# else320 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# endif327 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) _NOEXCEPT348 : __ptr_(nullptr) {}349 350 _LIBCPP_CONSTEXPR_SINCE_CXX26351 _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) _NOEXCEPT354 : __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 bool388 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 bool392 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) _NOEXCEPT411 : __ptr_(nullptr) {}412 413 _LIBCPP_CONSTEXPR_SINCE_CXX26414 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}415 416 _LIBCPP_CONSTEXPR_SINCE_CXX26417 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT418 : __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_ABI432 __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 bool452 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 bool456 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_LANG501 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI502 __forward_list_base(__forward_list_base&& __x) noexcept(is_nothrow_move_constructible<__node_allocator>::value);503 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI504 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);505# endif // _LIBCPP_CXX03_LANG506 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_pointer525 __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 value528 // 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 the531 // Cpp17FooInsertable named requirements don't require the allocator's construct() method532 // 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 >= 14551 _NOEXCEPT;552# else553 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>);554# endif555 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 void563 __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 void570 __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_LANG578 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_LANG597 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 >= 14606 _NOEXCEPT607# else608 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)609# endif610{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(__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 >= 20657 typedef size_type __remove_return_type;658# else659 typedef void __remove_return_type;660# endif661 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 >= 14667 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n, const allocator_type& __a);668# endif669 _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_ABI673 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_ABI683 forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a);684 685# if _LIBCPP_STD_VER >= 23686 template <_ContainerCompatibleRange<_Tp> _Range>687 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI688 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# endif693 694 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x);695 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI696 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_LANG701 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI702 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_ABI705 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_ABI709 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_LANG720 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 >= 23727 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# endif732 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_LANG786# if _LIBCPP_STD_VER >= 17787 template <class... _Args>788 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);789# else790 template <class... _Args>791 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);792# endif793 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v);794# endif // _LIBCPP_CXX03_LANG795 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);796 797# if _LIBCPP_STD_VER >= 23798 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# endif803 804 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void pop_front();805 806# ifndef _LIBCPP_CXX03_LANG807 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 iterator812 insert_after(const_iterator __p, initializer_list<value_type> __il) {813 return insert_after(__p, __il.begin(), __il.end());814 }815# endif // _LIBCPP_CXX03_LANG816 _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 iterator818 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 iterator823 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);824 825# if _LIBCPP_STD_VER >= 23826 template <_ContainerCompatibleRange<_Tp> _Range>827 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator828 insert_range_after(const_iterator __position, _Range&& __range) {829 return __insert_after_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));830 }831# endif832 833 template <class _InputIterator, class _Sentinel>834 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI iterator835 __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 >= 14842 _NOEXCEPT843# else844 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)845# endif846 {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 void856 splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);857 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void858 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 void861 splice_after(const_iterator __p, forward_list& __x, const_iterator __i);862 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void863 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_LANG871 _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_LANG877 _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_LANG887 _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_LANG891 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 iterator897 __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_pointer901 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);902 903 // TODO: Make this _LIBCPP_HIDE_FROM_ABI904 template <class _Compare>905 _LIBCPP_CONSTEXPR_SINCE_CXX26 static _LIBCPP_HIDDEN __node_pointer906 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);907};908 909# if _LIBCPP_STD_VER >= 17910template <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# endif922 923# if _LIBCPP_STD_VER >= 23924template <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# endif929 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 >= 14944template <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# endif955 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_CXX26970forward_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_CXX26983forward_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_LANG998template <class _Tp, class _Alloc>999_LIBCPP_CONSTEXPR_SINCE_CXX261000forward_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_CXX261015forward_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_LANG1057 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 void1067forward_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 else1076 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 else1089 erase_after(__i, __e);1090}1091 1092# ifndef _LIBCPP_CXX03_LANG1093 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_CXX261102# if _LIBCPP_STD_VER >= 171103 typename forward_list<_Tp, _Alloc>::reference1104# else1105 void1106# endif1107 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 >= 171111 return __base::__before_begin()->__next_->__get_value();1112# endif1113}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_LANG1122 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_LANG1137 1138template <class _Tp, class _Alloc>1139template <class... _Args>1140_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator1141forward_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>::iterator1149forward_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_LANG1156 1157template <class _Tp, class _Alloc>1158_LIBCPP_CONSTEXPR_SINCE_CXX26 typename forward_list<_Tp, _Alloc>::iterator1159forward_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>::iterator1168forward_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>::iterator1194forward_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>::iterator1201forward_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>::iterator1230forward_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>::iterator1240forward_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 else1269 __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 else1283 __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 void1302forward_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 void1328forward_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 void1334forward_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_type1346forward_list<_Tp, _Alloc>::remove(const value_type& __v) {1347 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1348 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 } else1361 ++__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_type1370forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) {1371 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1372 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 } else1385 ++__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_type1394forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) {1395 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1396 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_pointer1422forward_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 } else1436 __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_pointer1465forward_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 bool1505operator==(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 <= 171519 1520template <class _Tp, class _Alloc>1521_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI bool1522operator!=(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 bool1528operator<(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 bool1534operator>(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 bool1540operator>=(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 bool1546operator<=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {1547 return !(__y < __x);1548}1549 1550# else // #if _LIBCPP_STD_VER <= 171551 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 <= 171559 1560template <class _Tp, class _Alloc>1561_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI void1562swap(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 >= 201567template <class _Tp, class _Allocator, class _Predicate>1568_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Allocator>::size_type1569erase_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_type1575erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) {1576 return std::erase_if(__c, [&](const auto& __elem) -> bool { return __elem == __v; });1577}1578# endif1579 1580template <class _Tp, class _Allocator>1581struct __container_traits<forward_list<_Tp, _Allocator> > {1582 // http://eel.is/c++draft/container.reqmts1583 // 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 following1585 // additional requirements:1586 // - If an exception is thrown by an insert() or emplace() function while inserting a single element, that1587 // 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_STD1594 1595# if _LIBCPP_STD_VER >= 171596_LIBCPP_BEGIN_NAMESPACE_STD1597namespace pmr {1598template <class _ValueT>1599using forward_list _LIBCPP_AVAILABILITY_PMR = std::forward_list<_ValueT, polymorphic_allocator<_ValueT>>;1600} // namespace pmr1601_LIBCPP_END_NAMESPACE_STD1602# endif1603 1604_LIBCPP_POP_MACROS1605 1606# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 201607# 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# endif1620#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)1621 1622#endif // _LIBCPP_FORWARD_LIST1623