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