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