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