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 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>* = nullptr); 707 template <class _InputIterator> 708 forward_list(_InputIterator __f, _InputIterator __l, 709 const allocator_type& __a, 710 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>* = nullptr); 711 forward_list(const forward_list& __x); 712 forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a); 713 714 forward_list& operator=(const forward_list& __x); 715 716#ifndef _LIBCPP_CXX03_LANG 717 _LIBCPP_INLINE_VISIBILITY 718 forward_list(forward_list&& __x) 719 _NOEXCEPT_(is_nothrow_move_constructible<base>::value) 720 : base(_VSTD::move(__x)) {} 721 forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a); 722 723 forward_list(initializer_list<value_type> __il); 724 forward_list(initializer_list<value_type> __il, const allocator_type& __a); 725 726 _LIBCPP_INLINE_VISIBILITY 727 forward_list& operator=(forward_list&& __x) 728 _NOEXCEPT_( 729 __node_traits::propagate_on_container_move_assignment::value && 730 is_nothrow_move_assignable<allocator_type>::value); 731 732 _LIBCPP_INLINE_VISIBILITY 733 forward_list& operator=(initializer_list<value_type> __il); 734 735 _LIBCPP_INLINE_VISIBILITY 736 void assign(initializer_list<value_type> __il); 737#endif // _LIBCPP_CXX03_LANG 738 739 // ~forward_list() = default; 740 741 template <class _InputIterator> 742 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void> 743 assign(_InputIterator __f, _InputIterator __l); 744 void assign(size_type __n, const value_type& __v); 745 746 _LIBCPP_INLINE_VISIBILITY 747 allocator_type get_allocator() const _NOEXCEPT 748 {return allocator_type(base::__alloc());} 749 750 _LIBCPP_INLINE_VISIBILITY 751 iterator begin() _NOEXCEPT 752 {return iterator(base::__before_begin()->__next_);} 753 _LIBCPP_INLINE_VISIBILITY 754 const_iterator begin() const _NOEXCEPT 755 {return const_iterator(base::__before_begin()->__next_);} 756 _LIBCPP_INLINE_VISIBILITY 757 iterator end() _NOEXCEPT 758 {return iterator(nullptr);} 759 _LIBCPP_INLINE_VISIBILITY 760 const_iterator end() const _NOEXCEPT 761 {return const_iterator(nullptr);} 762 763 _LIBCPP_INLINE_VISIBILITY 764 const_iterator cbegin() const _NOEXCEPT 765 {return const_iterator(base::__before_begin()->__next_);} 766 _LIBCPP_INLINE_VISIBILITY 767 const_iterator cend() const _NOEXCEPT 768 {return const_iterator(nullptr);} 769 770 _LIBCPP_INLINE_VISIBILITY 771 iterator before_begin() _NOEXCEPT 772 {return iterator(base::__before_begin());} 773 _LIBCPP_INLINE_VISIBILITY 774 const_iterator before_begin() const _NOEXCEPT 775 {return const_iterator(base::__before_begin());} 776 _LIBCPP_INLINE_VISIBILITY 777 const_iterator cbefore_begin() const _NOEXCEPT 778 {return const_iterator(base::__before_begin());} 779 780 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 781 bool empty() const _NOEXCEPT 782 {return base::__before_begin()->__next_ == nullptr;} 783 _LIBCPP_INLINE_VISIBILITY 784 size_type max_size() const _NOEXCEPT { 785 return _VSTD::min<size_type>( 786 __node_traits::max_size(base::__alloc()), 787 numeric_limits<difference_type>::max()); 788 } 789 790 _LIBCPP_INLINE_VISIBILITY 791 reference front() {return base::__before_begin()->__next_->__value_;} 792 _LIBCPP_INLINE_VISIBILITY 793 const_reference front() const {return base::__before_begin()->__next_->__value_;} 794 795#ifndef _LIBCPP_CXX03_LANG 796#if _LIBCPP_STD_VER > 14 797 template <class... _Args> reference emplace_front(_Args&&... __args); 798#else 799 template <class... _Args> void emplace_front(_Args&&... __args); 800#endif 801 void push_front(value_type&& __v); 802#endif // _LIBCPP_CXX03_LANG 803 void push_front(const value_type& __v); 804 805 void pop_front(); 806 807#ifndef _LIBCPP_CXX03_LANG 808 template <class... _Args> 809 iterator emplace_after(const_iterator __p, _Args&&... __args); 810 811 iterator insert_after(const_iterator __p, value_type&& __v); 812 iterator insert_after(const_iterator __p, initializer_list<value_type> __il) 813 {return insert_after(__p, __il.begin(), __il.end());} 814#endif // _LIBCPP_CXX03_LANG 815 iterator insert_after(const_iterator __p, const value_type& __v); 816 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 817 template <class _InputIterator> 818 _LIBCPP_INLINE_VISIBILITY 819 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, iterator> 820 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 821 822 iterator erase_after(const_iterator __p); 823 iterator erase_after(const_iterator __f, const_iterator __l); 824 825 _LIBCPP_INLINE_VISIBILITY 826 void swap(forward_list& __x) 827#if _LIBCPP_STD_VER >= 14 828 _NOEXCEPT 829#else 830 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 831 __is_nothrow_swappable<__node_allocator>::value) 832#endif 833 {base::swap(__x);} 834 835 void resize(size_type __n); 836 void resize(size_type __n, const value_type& __v); 837 _LIBCPP_INLINE_VISIBILITY 838 void clear() _NOEXCEPT {base::clear();} 839 840 _LIBCPP_INLINE_VISIBILITY 841 void splice_after(const_iterator __p, forward_list&& __x); 842 _LIBCPP_INLINE_VISIBILITY 843 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 844 _LIBCPP_INLINE_VISIBILITY 845 void splice_after(const_iterator __p, forward_list&& __x, 846 const_iterator __f, const_iterator __l); 847 void splice_after(const_iterator __p, forward_list& __x); 848 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 849 void splice_after(const_iterator __p, forward_list& __x, 850 const_iterator __f, const_iterator __l); 851 __remove_return_type remove(const value_type& __v); 852 template <class _Predicate> __remove_return_type remove_if(_Predicate __pred); 853 _LIBCPP_INLINE_VISIBILITY 854 __remove_return_type unique() {return unique(__equal_to<value_type>());} 855 template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred); 856#ifndef _LIBCPP_CXX03_LANG 857 _LIBCPP_INLINE_VISIBILITY 858 void merge(forward_list&& __x) {merge(__x, __less<value_type>());} 859 template <class _Compare> 860 _LIBCPP_INLINE_VISIBILITY 861 void merge(forward_list&& __x, _Compare __comp) 862 {merge(__x, _VSTD::move(__comp));} 863#endif // _LIBCPP_CXX03_LANG 864 _LIBCPP_INLINE_VISIBILITY 865 void merge(forward_list& __x) {merge(__x, __less<value_type>());} 866 template <class _Compare> void merge(forward_list& __x, _Compare __comp); 867 _LIBCPP_INLINE_VISIBILITY 868 void sort() {sort(__less<value_type>());} 869 template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp); 870 void reverse() _NOEXCEPT; 871 872private: 873 874#ifndef _LIBCPP_CXX03_LANG 875 void __move_assign(forward_list& __x, true_type) 876 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 877 void __move_assign(forward_list& __x, false_type); 878#endif // _LIBCPP_CXX03_LANG 879 880 template <class _Compare> 881 static 882 __node_pointer 883 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 884 885 template <class _Compare> 886 static 887 __node_pointer 888 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 889}; 890 891 892#if _LIBCPP_STD_VER >= 17 893template<class _InputIterator, 894 class _Alloc = allocator<__iter_value_type<_InputIterator>>, 895 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 896 class = enable_if_t<__is_allocator<_Alloc>::value> 897 > 898forward_list(_InputIterator, _InputIterator) 899 -> forward_list<__iter_value_type<_InputIterator>, _Alloc>; 900 901template<class _InputIterator, 902 class _Alloc, 903 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 904 class = enable_if_t<__is_allocator<_Alloc>::value> 905 > 906forward_list(_InputIterator, _InputIterator, _Alloc) 907 -> forward_list<__iter_value_type<_InputIterator>, _Alloc>; 908#endif 909 910template <class _Tp, class _Alloc> 911inline 912forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) 913 : base(__a) 914{ 915} 916 917template <class _Tp, class _Alloc> 918forward_list<_Tp, _Alloc>::forward_list(size_type __n) 919{ 920 if (__n > 0) 921 { 922 __node_allocator& __a = base::__alloc(); 923 typedef __allocator_destructor<__node_allocator> _Dp; 924 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 925 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 926 __p = __p->__next_as_begin()) 927 { 928 __h.reset(__node_traits::allocate(__a, 1)); 929 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 930 __h->__next_ = nullptr; 931 __p->__next_ = __h.release(); 932 } 933 } 934} 935 936#if _LIBCPP_STD_VER > 11 937template <class _Tp, class _Alloc> 938forward_list<_Tp, _Alloc>::forward_list(size_type __n, 939 const allocator_type& __base_alloc) 940 : base ( __base_alloc ) 941{ 942 if (__n > 0) 943 { 944 __node_allocator& __a = base::__alloc(); 945 typedef __allocator_destructor<__node_allocator> _Dp; 946 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 947 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 948 __p = __p->__next_as_begin()) 949 { 950 __h.reset(__node_traits::allocate(__a, 1)); 951 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 952 __h->__next_ = nullptr; 953 __p->__next_ = __h.release(); 954 } 955 } 956} 957#endif 958 959template <class _Tp, class _Alloc> 960forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) 961{ 962 insert_after(cbefore_begin(), __n, __v); 963} 964 965template <class _Tp, class _Alloc> 966template <class _InputIterator> 967forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 968 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>*) 969{ 970 insert_after(cbefore_begin(), __f, __l); 971} 972 973template <class _Tp, class _Alloc> 974template <class _InputIterator> 975forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 976 const allocator_type& __a, 977 __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>*) 978 : base(__a) 979{ 980 insert_after(cbefore_begin(), __f, __l); 981} 982 983template <class _Tp, class _Alloc> 984forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) 985 : base( 986 __node_traits::select_on_container_copy_construction(__x.__alloc())) { 987 insert_after(cbefore_begin(), __x.begin(), __x.end()); 988} 989 990template <class _Tp, class _Alloc> 991forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, 992 const __type_identity_t<allocator_type>& __a) 993 : base(__a) 994{ 995 insert_after(cbefore_begin(), __x.begin(), __x.end()); 996} 997 998template <class _Tp, class _Alloc> 999forward_list<_Tp, _Alloc>& 1000forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) 1001{ 1002 if (this != _VSTD::addressof(__x)) 1003 { 1004 base::__copy_assign_alloc(__x); 1005 assign(__x.begin(), __x.end()); 1006 } 1007 return *this; 1008} 1009 1010#ifndef _LIBCPP_CXX03_LANG 1011template <class _Tp, class _Alloc> 1012forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, 1013 const __type_identity_t<allocator_type>& __a) 1014 : base(_VSTD::move(__x), __a) 1015{ 1016 if (base::__alloc() != __x.__alloc()) 1017 { 1018 typedef move_iterator<iterator> _Ip; 1019 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end())); 1020 } 1021} 1022 1023template <class _Tp, class _Alloc> 1024forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) 1025{ 1026 insert_after(cbefore_begin(), __il.begin(), __il.end()); 1027} 1028 1029template <class _Tp, class _Alloc> 1030forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, 1031 const allocator_type& __a) 1032 : base(__a) 1033{ 1034 insert_after(cbefore_begin(), __il.begin(), __il.end()); 1035} 1036 1037template <class _Tp, class _Alloc> 1038void 1039forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type) 1040 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1041{ 1042 clear(); 1043 base::__move_assign_alloc(__x); 1044 base::__before_begin()->__next_ = __x.__before_begin()->__next_; 1045 __x.__before_begin()->__next_ = nullptr; 1046} 1047 1048template <class _Tp, class _Alloc> 1049void 1050forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) 1051{ 1052 if (base::__alloc() == __x.__alloc()) 1053 __move_assign(__x, true_type()); 1054 else 1055 { 1056 typedef move_iterator<iterator> _Ip; 1057 assign(_Ip(__x.begin()), _Ip(__x.end())); 1058 } 1059} 1060 1061template <class _Tp, class _Alloc> 1062inline 1063forward_list<_Tp, _Alloc>& 1064forward_list<_Tp, _Alloc>::operator=(forward_list&& __x) 1065 _NOEXCEPT_( 1066 __node_traits::propagate_on_container_move_assignment::value && 1067 is_nothrow_move_assignable<allocator_type>::value) 1068{ 1069 __move_assign(__x, integral_constant<bool, 1070 __node_traits::propagate_on_container_move_assignment::value>()); 1071 return *this; 1072} 1073 1074template <class _Tp, class _Alloc> 1075inline 1076forward_list<_Tp, _Alloc>& 1077forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) 1078{ 1079 assign(__il.begin(), __il.end()); 1080 return *this; 1081} 1082 1083#endif // _LIBCPP_CXX03_LANG 1084 1085template <class _Tp, class _Alloc> 1086template <class _InputIterator> 1087__enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void> 1088forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) 1089{ 1090 iterator __i = before_begin(); 1091 iterator __j = _VSTD::next(__i); 1092 iterator __e = end(); 1093 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f) 1094 *__j = *__f; 1095 if (__j == __e) 1096 insert_after(__i, __f, __l); 1097 else 1098 erase_after(__i, __e); 1099} 1100 1101template <class _Tp, class _Alloc> 1102void 1103forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) 1104{ 1105 iterator __i = before_begin(); 1106 iterator __j = _VSTD::next(__i); 1107 iterator __e = end(); 1108 for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 1109 *__j = __v; 1110 if (__j == __e) 1111 insert_after(__i, __n, __v); 1112 else 1113 erase_after(__i, __e); 1114} 1115 1116#ifndef _LIBCPP_CXX03_LANG 1117 1118template <class _Tp, class _Alloc> 1119inline 1120void 1121forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) 1122{ 1123 assign(__il.begin(), __il.end()); 1124} 1125 1126template <class _Tp, class _Alloc> 1127template <class... _Args> 1128#if _LIBCPP_STD_VER > 14 1129typename forward_list<_Tp, _Alloc>::reference 1130#else 1131void 1132#endif 1133forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1134{ 1135 __node_allocator& __a = base::__alloc(); 1136 typedef __allocator_destructor<__node_allocator> _Dp; 1137 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1138 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1139 _VSTD::forward<_Args>(__args)...); 1140 __h->__next_ = base::__before_begin()->__next_; 1141 base::__before_begin()->__next_ = __h.release(); 1142#if _LIBCPP_STD_VER > 14 1143 return base::__before_begin()->__next_->__value_; 1144#endif 1145} 1146 1147template <class _Tp, class _Alloc> 1148void 1149forward_list<_Tp, _Alloc>::push_front(value_type&& __v) 1150{ 1151 __node_allocator& __a = base::__alloc(); 1152 typedef __allocator_destructor<__node_allocator> _Dp; 1153 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1154 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1155 __h->__next_ = base::__before_begin()->__next_; 1156 base::__before_begin()->__next_ = __h.release(); 1157} 1158 1159#endif // _LIBCPP_CXX03_LANG 1160 1161template <class _Tp, class _Alloc> 1162void 1163forward_list<_Tp, _Alloc>::push_front(const value_type& __v) 1164{ 1165 __node_allocator& __a = base::__alloc(); 1166 typedef __allocator_destructor<__node_allocator> _Dp; 1167 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1168 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1169 __h->__next_ = base::__before_begin()->__next_; 1170 base::__before_begin()->__next_ = __h.release(); 1171} 1172 1173template <class _Tp, class _Alloc> 1174void 1175forward_list<_Tp, _Alloc>::pop_front() 1176{ 1177 __node_allocator& __a = base::__alloc(); 1178 __node_pointer __p = base::__before_begin()->__next_; 1179 base::__before_begin()->__next_ = __p->__next_; 1180 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 1181 __node_traits::deallocate(__a, __p, 1); 1182} 1183 1184#ifndef _LIBCPP_CXX03_LANG 1185 1186template <class _Tp, class _Alloc> 1187template <class... _Args> 1188typename forward_list<_Tp, _Alloc>::iterator 1189forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) 1190{ 1191 __begin_node_pointer const __r = __p.__get_begin(); 1192 __node_allocator& __a = base::__alloc(); 1193 typedef __allocator_destructor<__node_allocator> _Dp; 1194 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1195 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1196 _VSTD::forward<_Args>(__args)...); 1197 __h->__next_ = __r->__next_; 1198 __r->__next_ = __h.release(); 1199 return iterator(__r->__next_); 1200} 1201 1202template <class _Tp, class _Alloc> 1203typename forward_list<_Tp, _Alloc>::iterator 1204forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) 1205{ 1206 __begin_node_pointer const __r = __p.__get_begin(); 1207 __node_allocator& __a = base::__alloc(); 1208 typedef __allocator_destructor<__node_allocator> _Dp; 1209 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1210 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1211 __h->__next_ = __r->__next_; 1212 __r->__next_ = __h.release(); 1213 return iterator(__r->__next_); 1214} 1215 1216#endif // _LIBCPP_CXX03_LANG 1217 1218template <class _Tp, class _Alloc> 1219typename forward_list<_Tp, _Alloc>::iterator 1220forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) 1221{ 1222 __begin_node_pointer const __r = __p.__get_begin(); 1223 __node_allocator& __a = base::__alloc(); 1224 typedef __allocator_destructor<__node_allocator> _Dp; 1225 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1226 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1227 __h->__next_ = __r->__next_; 1228 __r->__next_ = __h.release(); 1229 return iterator(__r->__next_); 1230} 1231 1232template <class _Tp, class _Alloc> 1233typename forward_list<_Tp, _Alloc>::iterator 1234forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, 1235 const value_type& __v) 1236{ 1237 __begin_node_pointer __r = __p.__get_begin(); 1238 if (__n > 0) 1239 { 1240 __node_allocator& __a = base::__alloc(); 1241 typedef __allocator_destructor<__node_allocator> _Dp; 1242 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1243 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1244 __node_pointer __first = __h.release(); 1245 __node_pointer __last = __first; 1246#ifndef _LIBCPP_NO_EXCEPTIONS 1247 try 1248 { 1249#endif // _LIBCPP_NO_EXCEPTIONS 1250 for (--__n; __n != 0; --__n, __last = __last->__next_) 1251 { 1252 __h.reset(__node_traits::allocate(__a, 1)); 1253 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1254 __last->__next_ = __h.release(); 1255 } 1256#ifndef _LIBCPP_NO_EXCEPTIONS 1257 } 1258 catch (...) 1259 { 1260 while (__first != nullptr) 1261 { 1262 __node_pointer __next = __first->__next_; 1263 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1264 __node_traits::deallocate(__a, __first, 1); 1265 __first = __next; 1266 } 1267 throw; 1268 } 1269#endif // _LIBCPP_NO_EXCEPTIONS 1270 __last->__next_ = __r->__next_; 1271 __r->__next_ = __first; 1272 __r = static_cast<__begin_node_pointer>(__last); 1273 } 1274 return iterator(__r); 1275} 1276 1277template <class _Tp, class _Alloc> 1278template <class _InputIterator> 1279__enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, typename forward_list<_Tp, _Alloc>::iterator> 1280forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, 1281 _InputIterator __f, _InputIterator __l) 1282{ 1283 __begin_node_pointer __r = __p.__get_begin(); 1284 if (__f != __l) 1285 { 1286 __node_allocator& __a = base::__alloc(); 1287 typedef __allocator_destructor<__node_allocator> _Dp; 1288 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1289 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1290 __node_pointer __first = __h.release(); 1291 __node_pointer __last = __first; 1292#ifndef _LIBCPP_NO_EXCEPTIONS 1293 try 1294 { 1295#endif // _LIBCPP_NO_EXCEPTIONS 1296 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) 1297 { 1298 __h.reset(__node_traits::allocate(__a, 1)); 1299 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1300 __last->__next_ = __h.release(); 1301 } 1302#ifndef _LIBCPP_NO_EXCEPTIONS 1303 } 1304 catch (...) 1305 { 1306 while (__first != nullptr) 1307 { 1308 __node_pointer __next = __first->__next_; 1309 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1310 __node_traits::deallocate(__a, __first, 1); 1311 __first = __next; 1312 } 1313 throw; 1314 } 1315#endif // _LIBCPP_NO_EXCEPTIONS 1316 __last->__next_ = __r->__next_; 1317 __r->__next_ = __first; 1318 __r = static_cast<__begin_node_pointer>(__last); 1319 } 1320 return iterator(__r); 1321} 1322 1323template <class _Tp, class _Alloc> 1324typename forward_list<_Tp, _Alloc>::iterator 1325forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) 1326{ 1327 __begin_node_pointer __p = __f.__get_begin(); 1328 __node_pointer __n = __p->__next_; 1329 __p->__next_ = __n->__next_; 1330 __node_allocator& __a = base::__alloc(); 1331 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1332 __node_traits::deallocate(__a, __n, 1); 1333 return iterator(__p->__next_); 1334} 1335 1336template <class _Tp, class _Alloc> 1337typename forward_list<_Tp, _Alloc>::iterator 1338forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) 1339{ 1340 __node_pointer __e = __l.__get_unsafe_node_pointer(); 1341 if (__f != __l) 1342 { 1343 __begin_node_pointer __bp = __f.__get_begin(); 1344 1345 __node_pointer __n = __bp->__next_; 1346 if (__n != __e) 1347 { 1348 __bp->__next_ = __e; 1349 __node_allocator& __a = base::__alloc(); 1350 do 1351 { 1352 __node_pointer __tmp = __n->__next_; 1353 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1354 __node_traits::deallocate(__a, __n, 1); 1355 __n = __tmp; 1356 } while (__n != __e); 1357 } 1358 } 1359 return iterator(__e); 1360} 1361 1362template <class _Tp, class _Alloc> 1363void 1364forward_list<_Tp, _Alloc>::resize(size_type __n) 1365{ 1366 size_type __sz = 0; 1367 iterator __p = before_begin(); 1368 iterator __i = begin(); 1369 iterator __e = end(); 1370 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1371 ; 1372 if (__i != __e) 1373 erase_after(__p, __e); 1374 else 1375 { 1376 __n -= __sz; 1377 if (__n > 0) 1378 { 1379 __node_allocator& __a = base::__alloc(); 1380 typedef __allocator_destructor<__node_allocator> _Dp; 1381 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1382 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, 1383 __ptr = __ptr->__next_as_begin()) 1384 { 1385 __h.reset(__node_traits::allocate(__a, 1)); 1386 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 1387 __h->__next_ = nullptr; 1388 __ptr->__next_ = __h.release(); 1389 } 1390 } 1391 } 1392} 1393 1394template <class _Tp, class _Alloc> 1395void 1396forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) 1397{ 1398 size_type __sz = 0; 1399 iterator __p = before_begin(); 1400 iterator __i = begin(); 1401 iterator __e = end(); 1402 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1403 ; 1404 if (__i != __e) 1405 erase_after(__p, __e); 1406 else 1407 { 1408 __n -= __sz; 1409 if (__n > 0) 1410 { 1411 __node_allocator& __a = base::__alloc(); 1412 typedef __allocator_destructor<__node_allocator> _Dp; 1413 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1414 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, 1415 __ptr = __ptr->__next_as_begin()) 1416 { 1417 __h.reset(__node_traits::allocate(__a, 1)); 1418 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1419 __h->__next_ = nullptr; 1420 __ptr->__next_ = __h.release(); 1421 } 1422 } 1423 } 1424} 1425 1426template <class _Tp, class _Alloc> 1427void 1428forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1429 forward_list& __x) 1430{ 1431 if (!__x.empty()) 1432 { 1433 if (__p.__get_begin()->__next_ != nullptr) 1434 { 1435 const_iterator __lm1 = __x.before_begin(); 1436 while (__lm1.__get_begin()->__next_ != nullptr) 1437 ++__lm1; 1438 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1439 } 1440 __p.__get_begin()->__next_ = __x.__before_begin()->__next_; 1441 __x.__before_begin()->__next_ = nullptr; 1442 } 1443} 1444 1445template <class _Tp, class _Alloc> 1446void 1447forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1448 forward_list& /*__other*/, 1449 const_iterator __i) 1450{ 1451 const_iterator __lm1 = _VSTD::next(__i); 1452 if (__p != __i && __p != __lm1) 1453 { 1454 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_; 1455 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1456 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer(); 1457 } 1458} 1459 1460template <class _Tp, class _Alloc> 1461void 1462forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1463 forward_list& /*__other*/, 1464 const_iterator __f, const_iterator __l) 1465{ 1466 if (__f != __l && __p != __f) 1467 { 1468 const_iterator __lm1 = __f; 1469 while (__lm1.__get_begin()->__next_ != __l.__get_begin()) 1470 ++__lm1; 1471 if (__f != __lm1) 1472 { 1473 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1474 __p.__get_begin()->__next_ = __f.__get_begin()->__next_; 1475 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer(); 1476 } 1477 } 1478} 1479 1480template <class _Tp, class _Alloc> 1481inline _LIBCPP_INLINE_VISIBILITY 1482void 1483forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1484 forward_list&& __x) 1485{ 1486 splice_after(__p, __x); 1487} 1488 1489template <class _Tp, class _Alloc> 1490inline _LIBCPP_INLINE_VISIBILITY 1491void 1492forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1493 forward_list&& __x, 1494 const_iterator __i) 1495{ 1496 splice_after(__p, __x, __i); 1497} 1498 1499template <class _Tp, class _Alloc> 1500inline _LIBCPP_INLINE_VISIBILITY 1501void 1502forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1503 forward_list&& __x, 1504 const_iterator __f, const_iterator __l) 1505{ 1506 splice_after(__p, __x, __f, __l); 1507} 1508 1509template <class _Tp, class _Alloc> 1510typename forward_list<_Tp, _Alloc>::__remove_return_type 1511forward_list<_Tp, _Alloc>::remove(const value_type& __v) 1512{ 1513 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1514 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; 1515 const iterator __e = end(); 1516 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) 1517 { 1518 if (__i.__get_begin()->__next_->__value_ == __v) 1519 { 1520 ++__count_removed; 1521 iterator __j = _VSTD::next(__i, 2); 1522 for (; __j != __e && *__j == __v; ++__j) 1523 ++__count_removed; 1524 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1525 if (__j == __e) 1526 break; 1527 __i = __j; 1528 } 1529 else 1530 ++__i; 1531 } 1532 1533 return (__remove_return_type) __count_removed; 1534} 1535 1536template <class _Tp, class _Alloc> 1537template <class _Predicate> 1538typename forward_list<_Tp, _Alloc>::__remove_return_type 1539forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) 1540{ 1541 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1542 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; 1543 const iterator __e = end(); 1544 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) 1545 { 1546 if (__pred(__i.__get_begin()->__next_->__value_)) 1547 { 1548 ++__count_removed; 1549 iterator __j = _VSTD::next(__i, 2); 1550 for (; __j != __e && __pred(*__j); ++__j) 1551 ++__count_removed; 1552 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1553 if (__j == __e) 1554 break; 1555 __i = __j; 1556 } 1557 else 1558 ++__i; 1559 } 1560 1561 return (__remove_return_type) __count_removed; 1562} 1563 1564template <class _Tp, class _Alloc> 1565template <class _BinaryPredicate> 1566typename forward_list<_Tp, _Alloc>::__remove_return_type 1567forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) 1568{ 1569 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1570 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; 1571 for (iterator __i = begin(), __e = end(); __i != __e;) 1572 { 1573 iterator __j = _VSTD::next(__i); 1574 for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 1575 ++__count_removed; 1576 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer()) 1577 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1578 __i = __j; 1579 } 1580 1581 return (__remove_return_type) __count_removed; 1582} 1583 1584template <class _Tp, class _Alloc> 1585template <class _Compare> 1586void 1587forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) 1588{ 1589 if (this != _VSTD::addressof(__x)) 1590 { 1591 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, 1592 __x.__before_begin()->__next_, 1593 __comp); 1594 __x.__before_begin()->__next_ = nullptr; 1595 } 1596} 1597 1598template <class _Tp, class _Alloc> 1599template <class _Compare> 1600typename forward_list<_Tp, _Alloc>::__node_pointer 1601forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, 1602 _Compare& __comp) 1603{ 1604 if (__f1 == nullptr) 1605 return __f2; 1606 if (__f2 == nullptr) 1607 return __f1; 1608 __node_pointer __r; 1609 if (__comp(__f2->__value_, __f1->__value_)) 1610 { 1611 __node_pointer __t = __f2; 1612 while (__t->__next_ != nullptr && 1613 __comp(__t->__next_->__value_, __f1->__value_)) 1614 __t = __t->__next_; 1615 __r = __f2; 1616 __f2 = __t->__next_; 1617 __t->__next_ = __f1; 1618 } 1619 else 1620 __r = __f1; 1621 __node_pointer __p = __f1; 1622 __f1 = __f1->__next_; 1623 while (__f1 != nullptr && __f2 != nullptr) 1624 { 1625 if (__comp(__f2->__value_, __f1->__value_)) 1626 { 1627 __node_pointer __t = __f2; 1628 while (__t->__next_ != nullptr && 1629 __comp(__t->__next_->__value_, __f1->__value_)) 1630 __t = __t->__next_; 1631 __p->__next_ = __f2; 1632 __f2 = __t->__next_; 1633 __t->__next_ = __f1; 1634 } 1635 __p = __f1; 1636 __f1 = __f1->__next_; 1637 } 1638 if (__f2 != nullptr) 1639 __p->__next_ = __f2; 1640 return __r; 1641} 1642 1643template <class _Tp, class _Alloc> 1644template <class _Compare> 1645inline 1646void 1647forward_list<_Tp, _Alloc>::sort(_Compare __comp) 1648{ 1649 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, 1650 _VSTD::distance(begin(), end()), __comp); 1651} 1652 1653template <class _Tp, class _Alloc> 1654template <class _Compare> 1655typename forward_list<_Tp, _Alloc>::__node_pointer 1656forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, 1657 _Compare& __comp) 1658{ 1659 switch (__sz) 1660 { 1661 case 0: 1662 case 1: 1663 return __f1; 1664 case 2: 1665 if (__comp(__f1->__next_->__value_, __f1->__value_)) 1666 { 1667 __node_pointer __t = __f1->__next_; 1668 __t->__next_ = __f1; 1669 __f1->__next_ = nullptr; 1670 __f1 = __t; 1671 } 1672 return __f1; 1673 } 1674 difference_type __sz1 = __sz / 2; 1675 difference_type __sz2 = __sz - __sz1; 1676 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer(); 1677 __node_pointer __f2 = __t->__next_; 1678 __t->__next_ = nullptr; 1679 return __merge(__sort(__f1, __sz1, __comp), 1680 __sort(__f2, __sz2, __comp), __comp); 1681} 1682 1683template <class _Tp, class _Alloc> 1684void 1685forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT 1686{ 1687 __node_pointer __p = base::__before_begin()->__next_; 1688 if (__p != nullptr) 1689 { 1690 __node_pointer __f = __p->__next_; 1691 __p->__next_ = nullptr; 1692 while (__f != nullptr) 1693 { 1694 __node_pointer __t = __f->__next_; 1695 __f->__next_ = __p; 1696 __p = __f; 1697 __f = __t; 1698 } 1699 base::__before_begin()->__next_ = __p; 1700 } 1701} 1702 1703template <class _Tp, class _Alloc> 1704bool operator==(const forward_list<_Tp, _Alloc>& __x, 1705 const forward_list<_Tp, _Alloc>& __y) 1706{ 1707 typedef forward_list<_Tp, _Alloc> _Cp; 1708 typedef typename _Cp::const_iterator _Ip; 1709 _Ip __ix = __x.begin(); 1710 _Ip __ex = __x.end(); 1711 _Ip __iy = __y.begin(); 1712 _Ip __ey = __y.end(); 1713 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) 1714 if (!(*__ix == *__iy)) 1715 return false; 1716 return (__ix == __ex) == (__iy == __ey); 1717} 1718 1719template <class _Tp, class _Alloc> 1720inline _LIBCPP_INLINE_VISIBILITY 1721bool operator!=(const forward_list<_Tp, _Alloc>& __x, 1722 const forward_list<_Tp, _Alloc>& __y) 1723{ 1724 return !(__x == __y); 1725} 1726 1727template <class _Tp, class _Alloc> 1728inline _LIBCPP_INLINE_VISIBILITY 1729bool operator< (const forward_list<_Tp, _Alloc>& __x, 1730 const forward_list<_Tp, _Alloc>& __y) 1731{ 1732 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), 1733 __y.begin(), __y.end()); 1734} 1735 1736template <class _Tp, class _Alloc> 1737inline _LIBCPP_INLINE_VISIBILITY 1738bool operator> (const forward_list<_Tp, _Alloc>& __x, 1739 const forward_list<_Tp, _Alloc>& __y) 1740{ 1741 return __y < __x; 1742} 1743 1744template <class _Tp, class _Alloc> 1745inline _LIBCPP_INLINE_VISIBILITY 1746bool operator>=(const forward_list<_Tp, _Alloc>& __x, 1747 const forward_list<_Tp, _Alloc>& __y) 1748{ 1749 return !(__x < __y); 1750} 1751 1752template <class _Tp, class _Alloc> 1753inline _LIBCPP_INLINE_VISIBILITY 1754bool operator<=(const forward_list<_Tp, _Alloc>& __x, 1755 const forward_list<_Tp, _Alloc>& __y) 1756{ 1757 return !(__y < __x); 1758} 1759 1760template <class _Tp, class _Alloc> 1761inline _LIBCPP_INLINE_VISIBILITY 1762void 1763swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) 1764 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1765{ 1766 __x.swap(__y); 1767} 1768 1769#if _LIBCPP_STD_VER > 17 1770template <class _Tp, class _Allocator, class _Predicate> 1771inline _LIBCPP_INLINE_VISIBILITY 1772 typename forward_list<_Tp, _Allocator>::size_type 1773 erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) { 1774 return __c.remove_if(__pred); 1775} 1776 1777template <class _Tp, class _Allocator, class _Up> 1778inline _LIBCPP_INLINE_VISIBILITY 1779 typename forward_list<_Tp, _Allocator>::size_type 1780 erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) { 1781 return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; }); 1782} 1783#endif 1784 1785_LIBCPP_END_NAMESPACE_STD 1786 1787_LIBCPP_POP_MACROS 1788 1789#endif // _LIBCPP_FORWARD_LIST 1790