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