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