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