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