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