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