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