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