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