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