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