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