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