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 <__memory/swap_allocator.h> 192#include <__utility/forward.h> 193#include <limits> 194#include <memory> 195#include <type_traits> 196#include <version> 197 198#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES 199# include <algorithm> 200# include <functional> 201# include <iterator> 202#endif 203 204// standard-mandated includes 205 206// [iterator.range] 207#include <__iterator/access.h> 208#include <__iterator/data.h> 209#include <__iterator/empty.h> 210#include <__iterator/reverse_access.h> 211#include <__iterator/size.h> 212 213// [forward.list.syn] 214#include <compare> 215#include <initializer_list> 216 217#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 218# pragma GCC system_header 219#endif 220 221_LIBCPP_PUSH_MACROS 222#include <__undef_macros> 223 224 225_LIBCPP_BEGIN_NAMESPACE_STD 226 227template <class _Tp, class _VoidPtr> struct __forward_list_node; 228template <class _NodePtr> struct __forward_begin_node; 229 230 231template <class> 232struct __forward_list_node_value_type; 233 234template <class _Tp, class _VoidPtr> 235struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > { 236 typedef _Tp type; 237}; 238 239template <class _NodePtr> 240struct __forward_node_traits { 241 242 typedef typename remove_cv< 243 typename pointer_traits<_NodePtr>::element_type>::type __node; 244 typedef typename __forward_list_node_value_type<__node>::type __node_value_type; 245 typedef _NodePtr __node_pointer; 246 typedef __forward_begin_node<_NodePtr> __begin_node; 247 typedef typename __rebind_pointer<_NodePtr, __begin_node>::type 248 __begin_node_pointer; 249 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer; 250 251#if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB) 252 typedef __begin_node_pointer __iter_node_pointer; 253#else 254 typedef typename conditional< 255 is_pointer<__void_pointer>::value, 256 __begin_node_pointer, 257 __node_pointer 258 >::type __iter_node_pointer; 259#endif 260 261 typedef typename conditional< 262 is_same<__iter_node_pointer, __node_pointer>::value, 263 __begin_node_pointer, 264 __node_pointer 265 >::type __non_iter_node_pointer; 266 267 _LIBCPP_INLINE_VISIBILITY 268 static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) { 269 return __p; 270 } 271 _LIBCPP_INLINE_VISIBILITY 272 static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) { 273 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p)); 274 } 275}; 276 277template <class _NodePtr> 278struct __forward_begin_node 279{ 280 typedef _NodePtr pointer; 281 typedef typename __rebind_pointer<_NodePtr, __forward_begin_node>::type __begin_node_pointer; 282 283 pointer __next_; 284 285 _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {} 286 287 _LIBCPP_INLINE_VISIBILITY 288 __begin_node_pointer __next_as_begin() const { 289 return static_cast<__begin_node_pointer>(__next_); 290 } 291}; 292 293template <class _Tp, class _VoidPtr> 294struct _LIBCPP_HIDDEN __begin_node_of 295{ 296 typedef __forward_begin_node< 297 typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type 298 > type; 299}; 300 301template <class _Tp, class _VoidPtr> 302struct _LIBCPP_STANDALONE_DEBUG __forward_list_node 303 : public __begin_node_of<_Tp, _VoidPtr>::type 304{ 305 typedef _Tp value_type; 306 307 value_type __value_; 308}; 309 310 311template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list; 312template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator; 313 314template <class _NodePtr> 315class _LIBCPP_TEMPLATE_VIS __forward_list_iterator 316{ 317 typedef __forward_node_traits<_NodePtr> __traits; 318 typedef typename __traits::__node_pointer __node_pointer; 319 typedef typename __traits::__begin_node_pointer __begin_node_pointer; 320 typedef typename __traits::__iter_node_pointer __iter_node_pointer; 321 typedef typename __traits::__void_pointer __void_pointer; 322 323 __iter_node_pointer __ptr_; 324 325 _LIBCPP_INLINE_VISIBILITY 326 __begin_node_pointer __get_begin() const { 327 return static_cast<__begin_node_pointer>( 328 static_cast<__void_pointer>(__ptr_)); 329 } 330 _LIBCPP_INLINE_VISIBILITY 331 __node_pointer __get_unsafe_node_pointer() const { 332 return static_cast<__node_pointer>( 333 static_cast<__void_pointer>(__ptr_)); 334 } 335 336 _LIBCPP_INLINE_VISIBILITY 337 explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {} 338 339 _LIBCPP_INLINE_VISIBILITY 340 explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT 341 : __ptr_(__traits::__as_iter_node(__p)) {} 342 343 _LIBCPP_INLINE_VISIBILITY 344 explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT 345 : __ptr_(__traits::__as_iter_node(__p)) {} 346 347 template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list; 348 template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator; 349 350public: 351 typedef forward_iterator_tag iterator_category; 352 typedef typename __traits::__node_value_type value_type; 353 typedef value_type& reference; 354 typedef typename pointer_traits<__node_pointer>::difference_type 355 difference_type; 356 typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer; 357 358 _LIBCPP_INLINE_VISIBILITY 359 __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {} 360 361 _LIBCPP_INLINE_VISIBILITY 362 reference operator*() const {return __get_unsafe_node_pointer()->__value_;} 363 _LIBCPP_INLINE_VISIBILITY 364 pointer operator->() const { 365 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_); 366 } 367 368 _LIBCPP_INLINE_VISIBILITY 369 __forward_list_iterator& operator++() 370 { 371 __ptr_ = __traits::__as_iter_node(__ptr_->__next_); 372 return *this; 373 } 374 _LIBCPP_INLINE_VISIBILITY 375 __forward_list_iterator operator++(int) 376 { 377 __forward_list_iterator __t(*this); 378 ++(*this); 379 return __t; 380 } 381 382 friend _LIBCPP_INLINE_VISIBILITY 383 bool operator==(const __forward_list_iterator& __x, 384 const __forward_list_iterator& __y) 385 {return __x.__ptr_ == __y.__ptr_;} 386 friend _LIBCPP_INLINE_VISIBILITY 387 bool operator!=(const __forward_list_iterator& __x, 388 const __forward_list_iterator& __y) 389 {return !(__x == __y);} 390}; 391 392template <class _NodeConstPtr> 393class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator 394{ 395 static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), ""); 396 typedef _NodeConstPtr _NodePtr; 397 398 typedef __forward_node_traits<_NodePtr> __traits; 399 typedef typename __traits::__node __node; 400 typedef typename __traits::__node_pointer __node_pointer; 401 typedef typename __traits::__begin_node_pointer __begin_node_pointer; 402 typedef typename __traits::__iter_node_pointer __iter_node_pointer; 403 typedef typename __traits::__void_pointer __void_pointer; 404 405 __iter_node_pointer __ptr_; 406 407 __begin_node_pointer __get_begin() const { 408 return static_cast<__begin_node_pointer>( 409 static_cast<__void_pointer>(__ptr_)); 410 } 411 __node_pointer __get_unsafe_node_pointer() const { 412 return static_cast<__node_pointer>( 413 static_cast<__void_pointer>(__ptr_)); 414 } 415 416 _LIBCPP_INLINE_VISIBILITY 417 explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT 418 : __ptr_(nullptr) {} 419 420 _LIBCPP_INLINE_VISIBILITY 421 explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT 422 : __ptr_(__traits::__as_iter_node(__p)) {} 423 424 _LIBCPP_INLINE_VISIBILITY 425 explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT 426 : __ptr_(__traits::__as_iter_node(__p)) {} 427 428 429 template<class, class> friend class forward_list; 430 431public: 432 typedef forward_iterator_tag iterator_category; 433 typedef typename __traits::__node_value_type value_type; 434 typedef const value_type& reference; 435 typedef typename pointer_traits<__node_pointer>::difference_type 436 difference_type; 437 typedef typename __rebind_pointer<__node_pointer, const value_type>::type 438 pointer; 439 440 _LIBCPP_INLINE_VISIBILITY 441 __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {} 442 _LIBCPP_INLINE_VISIBILITY 443 __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT 444 : __ptr_(__p.__ptr_) {} 445 446 _LIBCPP_INLINE_VISIBILITY 447 reference operator*() const {return __get_unsafe_node_pointer()->__value_;} 448 _LIBCPP_INLINE_VISIBILITY 449 pointer operator->() const {return pointer_traits<pointer>::pointer_to( 450 __get_unsafe_node_pointer()->__value_);} 451 452 _LIBCPP_INLINE_VISIBILITY 453 __forward_list_const_iterator& operator++() 454 { 455 __ptr_ = __traits::__as_iter_node(__ptr_->__next_); 456 return *this; 457 } 458 _LIBCPP_INLINE_VISIBILITY 459 __forward_list_const_iterator operator++(int) 460 { 461 __forward_list_const_iterator __t(*this); 462 ++(*this); 463 return __t; 464 } 465 466 friend _LIBCPP_INLINE_VISIBILITY 467 bool operator==(const __forward_list_const_iterator& __x, 468 const __forward_list_const_iterator& __y) 469 {return __x.__ptr_ == __y.__ptr_;} 470 friend _LIBCPP_INLINE_VISIBILITY 471 bool operator!=(const __forward_list_const_iterator& __x, 472 const __forward_list_const_iterator& __y) 473 {return !(__x == __y);} 474}; 475 476template <class _Tp, class _Alloc> 477class __forward_list_base 478{ 479protected: 480 typedef _Tp value_type; 481 typedef _Alloc allocator_type; 482 483 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer; 484 typedef __forward_list_node<value_type, void_pointer> __node; 485 typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node; 486 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __node>::type __node_allocator; 487 typedef allocator_traits<__node_allocator> __node_traits; 488 typedef typename __node_traits::pointer __node_pointer; 489 490 typedef typename __rebind_alloc_helper< 491 allocator_traits<allocator_type>, __begin_node 492 >::type __begin_node_allocator; 493 typedef typename allocator_traits<__begin_node_allocator>::pointer 494 __begin_node_pointer; 495 496 static_assert((!is_same<allocator_type, __node_allocator>::value), 497 "internal allocator type must differ from user-specified " 498 "type; otherwise overload resolution breaks"); 499 500 __compressed_pair<__begin_node, __node_allocator> __before_begin_; 501 502 _LIBCPP_INLINE_VISIBILITY 503 __begin_node_pointer __before_begin() _NOEXCEPT 504 {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());} 505 _LIBCPP_INLINE_VISIBILITY 506 __begin_node_pointer __before_begin() const _NOEXCEPT 507 {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));} 508 509 _LIBCPP_INLINE_VISIBILITY 510 __node_allocator& __alloc() _NOEXCEPT 511 {return __before_begin_.second();} 512 _LIBCPP_INLINE_VISIBILITY 513 const __node_allocator& __alloc() const _NOEXCEPT 514 {return __before_begin_.second();} 515 516 typedef __forward_list_iterator<__node_pointer> iterator; 517 typedef __forward_list_const_iterator<__node_pointer> const_iterator; 518 519 _LIBCPP_INLINE_VISIBILITY 520 __forward_list_base() 521 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 522 : __before_begin_(__begin_node(), __default_init_tag()) {} 523 _LIBCPP_INLINE_VISIBILITY 524 explicit __forward_list_base(const allocator_type& __a) 525 : __before_begin_(__begin_node(), __node_allocator(__a)) {} 526 _LIBCPP_INLINE_VISIBILITY 527 explicit __forward_list_base(const __node_allocator& __a) 528 : __before_begin_(__begin_node(), __a) {} 529#ifndef _LIBCPP_CXX03_LANG 530public: 531 _LIBCPP_INLINE_VISIBILITY 532 __forward_list_base(__forward_list_base&& __x) 533 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 534 _LIBCPP_INLINE_VISIBILITY 535 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a); 536#endif // _LIBCPP_CXX03_LANG 537 538private: 539 __forward_list_base(const __forward_list_base&); 540 __forward_list_base& operator=(const __forward_list_base&); 541 542public: 543 ~__forward_list_base(); 544 545protected: 546 _LIBCPP_INLINE_VISIBILITY 547 void __copy_assign_alloc(const __forward_list_base& __x) 548 {__copy_assign_alloc(__x, integral_constant<bool, 549 __node_traits::propagate_on_container_copy_assignment::value>());} 550 551 _LIBCPP_INLINE_VISIBILITY 552 void __move_assign_alloc(__forward_list_base& __x) 553 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || 554 is_nothrow_move_assignable<__node_allocator>::value) 555 {__move_assign_alloc(__x, integral_constant<bool, 556 __node_traits::propagate_on_container_move_assignment::value>());} 557 558public: 559 _LIBCPP_INLINE_VISIBILITY 560 void swap(__forward_list_base& __x) 561#if _LIBCPP_STD_VER >= 14 562 _NOEXCEPT; 563#else 564 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 565 __is_nothrow_swappable<__node_allocator>::value); 566#endif 567protected: 568 void clear() _NOEXCEPT; 569 570private: 571 _LIBCPP_INLINE_VISIBILITY 572 void __copy_assign_alloc(const __forward_list_base&, false_type) {} 573 _LIBCPP_INLINE_VISIBILITY 574 void __copy_assign_alloc(const __forward_list_base& __x, true_type) 575 { 576 if (__alloc() != __x.__alloc()) 577 clear(); 578 __alloc() = __x.__alloc(); 579 } 580 581 _LIBCPP_INLINE_VISIBILITY 582 void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT 583 {} 584 _LIBCPP_INLINE_VISIBILITY 585 void __move_assign_alloc(__forward_list_base& __x, true_type) 586 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 587 {__alloc() = _VSTD::move(__x.__alloc());} 588}; 589 590#ifndef _LIBCPP_CXX03_LANG 591 592template <class _Tp, class _Alloc> 593inline 594__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x) 595 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 596 : __before_begin_(_VSTD::move(__x.__before_begin_)) 597{ 598 __x.__before_begin()->__next_ = nullptr; 599} 600 601template <class _Tp, class _Alloc> 602inline 603__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x, 604 const allocator_type& __a) 605 : __before_begin_(__begin_node(), __node_allocator(__a)) 606{ 607 if (__alloc() == __x.__alloc()) 608 { 609 __before_begin()->__next_ = __x.__before_begin()->__next_; 610 __x.__before_begin()->__next_ = nullptr; 611 } 612} 613 614#endif // _LIBCPP_CXX03_LANG 615 616template <class _Tp, class _Alloc> 617__forward_list_base<_Tp, _Alloc>::~__forward_list_base() 618{ 619 clear(); 620} 621 622template <class _Tp, class _Alloc> 623inline 624void 625__forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x) 626#if _LIBCPP_STD_VER >= 14 627 _NOEXCEPT 628#else 629 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 630 __is_nothrow_swappable<__node_allocator>::value) 631#endif 632{ 633 _VSTD::__swap_allocator(__alloc(), __x.__alloc(), 634 integral_constant<bool, __node_traits::propagate_on_container_swap::value>()); 635 using _VSTD::swap; 636 swap(__before_begin()->__next_, __x.__before_begin()->__next_); 637} 638 639template <class _Tp, class _Alloc> 640void 641__forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT 642{ 643 __node_allocator& __a = __alloc(); 644 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) 645 { 646 __node_pointer __next = __p->__next_; 647 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 648 __node_traits::deallocate(__a, __p, 1); 649 __p = __next; 650 } 651 __before_begin()->__next_ = nullptr; 652} 653 654template <class _Tp, class _Alloc /*= allocator<_Tp>*/> 655class _LIBCPP_TEMPLATE_VIS forward_list 656 : private __forward_list_base<_Tp, _Alloc> 657{ 658 typedef __forward_list_base<_Tp, _Alloc> base; 659 typedef typename base::__node_allocator __node_allocator; 660 typedef typename base::__node __node; 661 typedef typename base::__node_traits __node_traits; 662 typedef typename base::__node_pointer __node_pointer; 663 typedef typename base::__begin_node_pointer __begin_node_pointer; 664 665public: 666 typedef _Tp value_type; 667 typedef _Alloc allocator_type; 668 669 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 670 "Allocator::value_type must be same type as value_type"); 671 672 typedef value_type& reference; 673 typedef const value_type& const_reference; 674 typedef typename allocator_traits<allocator_type>::pointer pointer; 675 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 676 typedef typename allocator_traits<allocator_type>::size_type size_type; 677 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 678 679 typedef typename base::iterator iterator; 680 typedef typename base::const_iterator const_iterator; 681#if _LIBCPP_STD_VER > 17 682 typedef size_type __remove_return_type; 683#else 684 typedef void __remove_return_type; 685#endif 686 687 _LIBCPP_INLINE_VISIBILITY 688 forward_list() 689 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 690 {} // = default; 691 _LIBCPP_INLINE_VISIBILITY 692 explicit forward_list(const allocator_type& __a); 693 explicit forward_list(size_type __n); 694#if _LIBCPP_STD_VER > 11 695 explicit forward_list(size_type __n, const allocator_type& __a); 696#endif 697 forward_list(size_type __n, const value_type& __v); 698 699 template <class = __enable_if_t<__is_allocator<_Alloc>::value> > 700 forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : base(__a) 701 { 702 insert_after(cbefore_begin(), __n, __v); 703 } 704 705 template <class _InputIterator> 706 forward_list(_InputIterator __f, _InputIterator __l, 707 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>* = nullptr); 708 template <class _InputIterator> 709 forward_list(_InputIterator __f, _InputIterator __l, 710 const allocator_type& __a, 711 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>* = nullptr); 712 forward_list(const forward_list& __x); 713 forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a); 714 715 forward_list& operator=(const forward_list& __x); 716 717#ifndef _LIBCPP_CXX03_LANG 718 _LIBCPP_INLINE_VISIBILITY 719 forward_list(forward_list&& __x) 720 _NOEXCEPT_(is_nothrow_move_constructible<base>::value) 721 : base(_VSTD::move(__x)) {} 722 forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a); 723 724 forward_list(initializer_list<value_type> __il); 725 forward_list(initializer_list<value_type> __il, const allocator_type& __a); 726 727 _LIBCPP_INLINE_VISIBILITY 728 forward_list& operator=(forward_list&& __x) 729 _NOEXCEPT_( 730 __node_traits::propagate_on_container_move_assignment::value && 731 is_nothrow_move_assignable<allocator_type>::value); 732 733 _LIBCPP_INLINE_VISIBILITY 734 forward_list& operator=(initializer_list<value_type> __il); 735 736 _LIBCPP_INLINE_VISIBILITY 737 void assign(initializer_list<value_type> __il); 738#endif // _LIBCPP_CXX03_LANG 739 740 // ~forward_list() = default; 741 742 template <class _InputIterator> 743 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void> 744 assign(_InputIterator __f, _InputIterator __l); 745 void assign(size_type __n, const value_type& __v); 746 747 _LIBCPP_INLINE_VISIBILITY 748 allocator_type get_allocator() const _NOEXCEPT 749 {return allocator_type(base::__alloc());} 750 751 _LIBCPP_INLINE_VISIBILITY 752 iterator begin() _NOEXCEPT 753 {return iterator(base::__before_begin()->__next_);} 754 _LIBCPP_INLINE_VISIBILITY 755 const_iterator begin() const _NOEXCEPT 756 {return const_iterator(base::__before_begin()->__next_);} 757 _LIBCPP_INLINE_VISIBILITY 758 iterator end() _NOEXCEPT 759 {return iterator(nullptr);} 760 _LIBCPP_INLINE_VISIBILITY 761 const_iterator end() const _NOEXCEPT 762 {return const_iterator(nullptr);} 763 764 _LIBCPP_INLINE_VISIBILITY 765 const_iterator cbegin() const _NOEXCEPT 766 {return const_iterator(base::__before_begin()->__next_);} 767 _LIBCPP_INLINE_VISIBILITY 768 const_iterator cend() const _NOEXCEPT 769 {return const_iterator(nullptr);} 770 771 _LIBCPP_INLINE_VISIBILITY 772 iterator before_begin() _NOEXCEPT 773 {return iterator(base::__before_begin());} 774 _LIBCPP_INLINE_VISIBILITY 775 const_iterator before_begin() const _NOEXCEPT 776 {return const_iterator(base::__before_begin());} 777 _LIBCPP_INLINE_VISIBILITY 778 const_iterator cbefore_begin() const _NOEXCEPT 779 {return const_iterator(base::__before_begin());} 780 781 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 782 bool empty() const _NOEXCEPT 783 {return base::__before_begin()->__next_ == nullptr;} 784 _LIBCPP_INLINE_VISIBILITY 785 size_type max_size() const _NOEXCEPT { 786 return _VSTD::min<size_type>( 787 __node_traits::max_size(base::__alloc()), 788 numeric_limits<difference_type>::max()); 789 } 790 791 _LIBCPP_INLINE_VISIBILITY 792 reference front() {return base::__before_begin()->__next_->__value_;} 793 _LIBCPP_INLINE_VISIBILITY 794 const_reference front() const {return base::__before_begin()->__next_->__value_;} 795 796#ifndef _LIBCPP_CXX03_LANG 797#if _LIBCPP_STD_VER > 14 798 template <class... _Args> reference emplace_front(_Args&&... __args); 799#else 800 template <class... _Args> void emplace_front(_Args&&... __args); 801#endif 802 void push_front(value_type&& __v); 803#endif // _LIBCPP_CXX03_LANG 804 void push_front(const value_type& __v); 805 806 void pop_front(); 807 808#ifndef _LIBCPP_CXX03_LANG 809 template <class... _Args> 810 iterator emplace_after(const_iterator __p, _Args&&... __args); 811 812 iterator insert_after(const_iterator __p, value_type&& __v); 813 iterator insert_after(const_iterator __p, initializer_list<value_type> __il) 814 {return insert_after(__p, __il.begin(), __il.end());} 815#endif // _LIBCPP_CXX03_LANG 816 iterator insert_after(const_iterator __p, const value_type& __v); 817 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 818 template <class _InputIterator> 819 _LIBCPP_INLINE_VISIBILITY 820 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, iterator> 821 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 822 823 iterator erase_after(const_iterator __p); 824 iterator erase_after(const_iterator __f, const_iterator __l); 825 826 _LIBCPP_INLINE_VISIBILITY 827 void swap(forward_list& __x) 828#if _LIBCPP_STD_VER >= 14 829 _NOEXCEPT 830#else 831 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 832 __is_nothrow_swappable<__node_allocator>::value) 833#endif 834 {base::swap(__x);} 835 836 void resize(size_type __n); 837 void resize(size_type __n, const value_type& __v); 838 _LIBCPP_INLINE_VISIBILITY 839 void clear() _NOEXCEPT {base::clear();} 840 841 _LIBCPP_INLINE_VISIBILITY 842 void splice_after(const_iterator __p, forward_list&& __x); 843 _LIBCPP_INLINE_VISIBILITY 844 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 845 _LIBCPP_INLINE_VISIBILITY 846 void splice_after(const_iterator __p, forward_list&& __x, 847 const_iterator __f, const_iterator __l); 848 void splice_after(const_iterator __p, forward_list& __x); 849 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 850 void splice_after(const_iterator __p, forward_list& __x, 851 const_iterator __f, const_iterator __l); 852 __remove_return_type remove(const value_type& __v); 853 template <class _Predicate> __remove_return_type remove_if(_Predicate __pred); 854 _LIBCPP_INLINE_VISIBILITY 855 __remove_return_type unique() {return unique(__equal_to<value_type>());} 856 template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred); 857#ifndef _LIBCPP_CXX03_LANG 858 _LIBCPP_INLINE_VISIBILITY 859 void merge(forward_list&& __x) {merge(__x, __less<value_type>());} 860 template <class _Compare> 861 _LIBCPP_INLINE_VISIBILITY 862 void merge(forward_list&& __x, _Compare __comp) 863 {merge(__x, _VSTD::move(__comp));} 864#endif // _LIBCPP_CXX03_LANG 865 _LIBCPP_INLINE_VISIBILITY 866 void merge(forward_list& __x) {merge(__x, __less<value_type>());} 867 template <class _Compare> void merge(forward_list& __x, _Compare __comp); 868 _LIBCPP_INLINE_VISIBILITY 869 void sort() {sort(__less<value_type>());} 870 template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp); 871 void reverse() _NOEXCEPT; 872 873private: 874 875#ifndef _LIBCPP_CXX03_LANG 876 void __move_assign(forward_list& __x, true_type) 877 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 878 void __move_assign(forward_list& __x, false_type); 879#endif // _LIBCPP_CXX03_LANG 880 881 template <class _Compare> 882 static 883 __node_pointer 884 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 885 886 template <class _Compare> 887 static 888 __node_pointer 889 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 890}; 891 892 893#if _LIBCPP_STD_VER >= 17 894template<class _InputIterator, 895 class _Alloc = allocator<__iter_value_type<_InputIterator>>, 896 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 897 class = enable_if_t<__is_allocator<_Alloc>::value> 898 > 899forward_list(_InputIterator, _InputIterator) 900 -> forward_list<__iter_value_type<_InputIterator>, _Alloc>; 901 902template<class _InputIterator, 903 class _Alloc, 904 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 905 class = enable_if_t<__is_allocator<_Alloc>::value> 906 > 907forward_list(_InputIterator, _InputIterator, _Alloc) 908 -> forward_list<__iter_value_type<_InputIterator>, _Alloc>; 909#endif 910 911template <class _Tp, class _Alloc> 912inline 913forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) 914 : base(__a) 915{ 916} 917 918template <class _Tp, class _Alloc> 919forward_list<_Tp, _Alloc>::forward_list(size_type __n) 920{ 921 if (__n > 0) 922 { 923 __node_allocator& __a = base::__alloc(); 924 typedef __allocator_destructor<__node_allocator> _Dp; 925 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 926 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 927 __p = __p->__next_as_begin()) 928 { 929 __h.reset(__node_traits::allocate(__a, 1)); 930 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 931 __h->__next_ = nullptr; 932 __p->__next_ = __h.release(); 933 } 934 } 935} 936 937#if _LIBCPP_STD_VER > 11 938template <class _Tp, class _Alloc> 939forward_list<_Tp, _Alloc>::forward_list(size_type __n, 940 const allocator_type& __base_alloc) 941 : base ( __base_alloc ) 942{ 943 if (__n > 0) 944 { 945 __node_allocator& __a = base::__alloc(); 946 typedef __allocator_destructor<__node_allocator> _Dp; 947 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 948 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 949 __p = __p->__next_as_begin()) 950 { 951 __h.reset(__node_traits::allocate(__a, 1)); 952 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 953 __h->__next_ = nullptr; 954 __p->__next_ = __h.release(); 955 } 956 } 957} 958#endif 959 960template <class _Tp, class _Alloc> 961forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) 962{ 963 insert_after(cbefore_begin(), __n, __v); 964} 965 966template <class _Tp, class _Alloc> 967template <class _InputIterator> 968forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 969 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>*) 970{ 971 insert_after(cbefore_begin(), __f, __l); 972} 973 974template <class _Tp, class _Alloc> 975template <class _InputIterator> 976forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 977 const allocator_type& __a, 978 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>*) 979 : base(__a) 980{ 981 insert_after(cbefore_begin(), __f, __l); 982} 983 984template <class _Tp, class _Alloc> 985forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) 986 : base( 987 __node_traits::select_on_container_copy_construction(__x.__alloc())) { 988 insert_after(cbefore_begin(), __x.begin(), __x.end()); 989} 990 991template <class _Tp, class _Alloc> 992forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, 993 const __type_identity_t<allocator_type>& __a) 994 : base(__a) 995{ 996 insert_after(cbefore_begin(), __x.begin(), __x.end()); 997} 998 999template <class _Tp, class _Alloc> 1000forward_list<_Tp, _Alloc>& 1001forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) 1002{ 1003 if (this != _VSTD::addressof(__x)) 1004 { 1005 base::__copy_assign_alloc(__x); 1006 assign(__x.begin(), __x.end()); 1007 } 1008 return *this; 1009} 1010 1011#ifndef _LIBCPP_CXX03_LANG 1012template <class _Tp, class _Alloc> 1013forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, 1014 const __type_identity_t<allocator_type>& __a) 1015 : base(_VSTD::move(__x), __a) 1016{ 1017 if (base::__alloc() != __x.__alloc()) 1018 { 1019 typedef move_iterator<iterator> _Ip; 1020 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end())); 1021 } 1022} 1023 1024template <class _Tp, class _Alloc> 1025forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) 1026{ 1027 insert_after(cbefore_begin(), __il.begin(), __il.end()); 1028} 1029 1030template <class _Tp, class _Alloc> 1031forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, 1032 const allocator_type& __a) 1033 : base(__a) 1034{ 1035 insert_after(cbefore_begin(), __il.begin(), __il.end()); 1036} 1037 1038template <class _Tp, class _Alloc> 1039void 1040forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type) 1041 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1042{ 1043 clear(); 1044 base::__move_assign_alloc(__x); 1045 base::__before_begin()->__next_ = __x.__before_begin()->__next_; 1046 __x.__before_begin()->__next_ = nullptr; 1047} 1048 1049template <class _Tp, class _Alloc> 1050void 1051forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) 1052{ 1053 if (base::__alloc() == __x.__alloc()) 1054 __move_assign(__x, true_type()); 1055 else 1056 { 1057 typedef move_iterator<iterator> _Ip; 1058 assign(_Ip(__x.begin()), _Ip(__x.end())); 1059 } 1060} 1061 1062template <class _Tp, class _Alloc> 1063inline 1064forward_list<_Tp, _Alloc>& 1065forward_list<_Tp, _Alloc>::operator=(forward_list&& __x) 1066 _NOEXCEPT_( 1067 __node_traits::propagate_on_container_move_assignment::value && 1068 is_nothrow_move_assignable<allocator_type>::value) 1069{ 1070 __move_assign(__x, integral_constant<bool, 1071 __node_traits::propagate_on_container_move_assignment::value>()); 1072 return *this; 1073} 1074 1075template <class _Tp, class _Alloc> 1076inline 1077forward_list<_Tp, _Alloc>& 1078forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) 1079{ 1080 assign(__il.begin(), __il.end()); 1081 return *this; 1082} 1083 1084#endif // _LIBCPP_CXX03_LANG 1085 1086template <class _Tp, class _Alloc> 1087template <class _InputIterator> 1088__enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void> 1089forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) 1090{ 1091 iterator __i = before_begin(); 1092 iterator __j = _VSTD::next(__i); 1093 iterator __e = end(); 1094 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f) 1095 *__j = *__f; 1096 if (__j == __e) 1097 insert_after(__i, __f, __l); 1098 else 1099 erase_after(__i, __e); 1100} 1101 1102template <class _Tp, class _Alloc> 1103void 1104forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) 1105{ 1106 iterator __i = before_begin(); 1107 iterator __j = _VSTD::next(__i); 1108 iterator __e = end(); 1109 for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 1110 *__j = __v; 1111 if (__j == __e) 1112 insert_after(__i, __n, __v); 1113 else 1114 erase_after(__i, __e); 1115} 1116 1117#ifndef _LIBCPP_CXX03_LANG 1118 1119template <class _Tp, class _Alloc> 1120inline 1121void 1122forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) 1123{ 1124 assign(__il.begin(), __il.end()); 1125} 1126 1127template <class _Tp, class _Alloc> 1128template <class... _Args> 1129#if _LIBCPP_STD_VER > 14 1130typename forward_list<_Tp, _Alloc>::reference 1131#else 1132void 1133#endif 1134forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1135{ 1136 __node_allocator& __a = base::__alloc(); 1137 typedef __allocator_destructor<__node_allocator> _Dp; 1138 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1139 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1140 _VSTD::forward<_Args>(__args)...); 1141 __h->__next_ = base::__before_begin()->__next_; 1142 base::__before_begin()->__next_ = __h.release(); 1143#if _LIBCPP_STD_VER > 14 1144 return base::__before_begin()->__next_->__value_; 1145#endif 1146} 1147 1148template <class _Tp, class _Alloc> 1149void 1150forward_list<_Tp, _Alloc>::push_front(value_type&& __v) 1151{ 1152 __node_allocator& __a = base::__alloc(); 1153 typedef __allocator_destructor<__node_allocator> _Dp; 1154 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1155 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1156 __h->__next_ = base::__before_begin()->__next_; 1157 base::__before_begin()->__next_ = __h.release(); 1158} 1159 1160#endif // _LIBCPP_CXX03_LANG 1161 1162template <class _Tp, class _Alloc> 1163void 1164forward_list<_Tp, _Alloc>::push_front(const value_type& __v) 1165{ 1166 __node_allocator& __a = base::__alloc(); 1167 typedef __allocator_destructor<__node_allocator> _Dp; 1168 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1169 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1170 __h->__next_ = base::__before_begin()->__next_; 1171 base::__before_begin()->__next_ = __h.release(); 1172} 1173 1174template <class _Tp, class _Alloc> 1175void 1176forward_list<_Tp, _Alloc>::pop_front() 1177{ 1178 __node_allocator& __a = base::__alloc(); 1179 __node_pointer __p = base::__before_begin()->__next_; 1180 base::__before_begin()->__next_ = __p->__next_; 1181 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 1182 __node_traits::deallocate(__a, __p, 1); 1183} 1184 1185#ifndef _LIBCPP_CXX03_LANG 1186 1187template <class _Tp, class _Alloc> 1188template <class... _Args> 1189typename forward_list<_Tp, _Alloc>::iterator 1190forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) 1191{ 1192 __begin_node_pointer const __r = __p.__get_begin(); 1193 __node_allocator& __a = base::__alloc(); 1194 typedef __allocator_destructor<__node_allocator> _Dp; 1195 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1196 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1197 _VSTD::forward<_Args>(__args)...); 1198 __h->__next_ = __r->__next_; 1199 __r->__next_ = __h.release(); 1200 return iterator(__r->__next_); 1201} 1202 1203template <class _Tp, class _Alloc> 1204typename forward_list<_Tp, _Alloc>::iterator 1205forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) 1206{ 1207 __begin_node_pointer const __r = __p.__get_begin(); 1208 __node_allocator& __a = base::__alloc(); 1209 typedef __allocator_destructor<__node_allocator> _Dp; 1210 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1211 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1212 __h->__next_ = __r->__next_; 1213 __r->__next_ = __h.release(); 1214 return iterator(__r->__next_); 1215} 1216 1217#endif // _LIBCPP_CXX03_LANG 1218 1219template <class _Tp, class _Alloc> 1220typename forward_list<_Tp, _Alloc>::iterator 1221forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) 1222{ 1223 __begin_node_pointer const __r = __p.__get_begin(); 1224 __node_allocator& __a = base::__alloc(); 1225 typedef __allocator_destructor<__node_allocator> _Dp; 1226 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1227 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1228 __h->__next_ = __r->__next_; 1229 __r->__next_ = __h.release(); 1230 return iterator(__r->__next_); 1231} 1232 1233template <class _Tp, class _Alloc> 1234typename forward_list<_Tp, _Alloc>::iterator 1235forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, 1236 const value_type& __v) 1237{ 1238 __begin_node_pointer __r = __p.__get_begin(); 1239 if (__n > 0) 1240 { 1241 __node_allocator& __a = base::__alloc(); 1242 typedef __allocator_destructor<__node_allocator> _Dp; 1243 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1244 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1245 __node_pointer __first = __h.release(); 1246 __node_pointer __last = __first; 1247#ifndef _LIBCPP_NO_EXCEPTIONS 1248 try 1249 { 1250#endif // _LIBCPP_NO_EXCEPTIONS 1251 for (--__n; __n != 0; --__n, __last = __last->__next_) 1252 { 1253 __h.reset(__node_traits::allocate(__a, 1)); 1254 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1255 __last->__next_ = __h.release(); 1256 } 1257#ifndef _LIBCPP_NO_EXCEPTIONS 1258 } 1259 catch (...) 1260 { 1261 while (__first != nullptr) 1262 { 1263 __node_pointer __next = __first->__next_; 1264 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1265 __node_traits::deallocate(__a, __first, 1); 1266 __first = __next; 1267 } 1268 throw; 1269 } 1270#endif // _LIBCPP_NO_EXCEPTIONS 1271 __last->__next_ = __r->__next_; 1272 __r->__next_ = __first; 1273 __r = static_cast<__begin_node_pointer>(__last); 1274 } 1275 return iterator(__r); 1276} 1277 1278template <class _Tp, class _Alloc> 1279template <class _InputIterator> 1280__enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, typename forward_list<_Tp, _Alloc>::iterator> 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