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