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