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