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