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