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 17 namespace std 18 { 19 20 template <class T, class Allocator = allocator<T>> 21 class forward_list 22 { 23 public: 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); // reference in C++17 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 137 template <class T, class Allocator> 138 bool operator==(const forward_list<T, Allocator>& x, 139 const forward_list<T, Allocator>& y); 140 141 template <class T, class Allocator> 142 bool operator< (const forward_list<T, Allocator>& x, 143 const forward_list<T, Allocator>& y); 144 145 template <class T, class Allocator> 146 bool operator!=(const forward_list<T, Allocator>& x, 147 const forward_list<T, Allocator>& y); 148 149 template <class T, class Allocator> 150 bool operator> (const forward_list<T, Allocator>& x, 151 const forward_list<T, Allocator>& y); 152 153 template <class T, class Allocator> 154 bool operator>=(const forward_list<T, Allocator>& x, 155 const forward_list<T, Allocator>& y); 156 157 template <class T, class Allocator> 158 bool operator<=(const forward_list<T, Allocator>& x, 159 const forward_list<T, Allocator>& y); 160 161 template <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 185 template <class _Tp, class _VoidPtr> struct __forward_list_node; 186 template <class _NodePtr> struct __forward_begin_node; 187 188 189 template <class> 190 struct __forward_list_node_value_type; 191 192 template <class _Tp, class _VoidPtr> 193 struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > { 194 typedef _Tp type; 195 }; 196 197 template <class _NodePtr> 198 struct __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 235 template <class _NodePtr> 236 struct __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 251 template <class _Tp, class _VoidPtr> 252 struct _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 259 template <class _Tp, class _VoidPtr> 260 struct __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 269 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list; 270 template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator; 271 272 template <class _NodePtr> 273 class _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 308 public: 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 350 template <class _NodeConstPtr> 351 class _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 389 public: 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 434 template <class _Tp, class _Alloc> 435 class __forward_list_base 436 { 437 protected: 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 482 public: 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 490 private: 491 __forward_list_base(const __forward_list_base&); 492 __forward_list_base& operator=(const __forward_list_base&); 493 494 public: 495 ~__forward_list_base(); 496 497 protected: 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 510 public: 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 519 protected: 520 void clear() _NOEXCEPT; 521 522 private: 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 544 template <class _Tp, class _Alloc> 545 inline 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 553 template <class _Tp, class _Alloc> 554 inline 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 568 template <class _Tp, class _Alloc> 569 __forward_list_base<_Tp, _Alloc>::~__forward_list_base() 570 { 571 clear(); 572 } 573 574 template <class _Tp, class _Alloc> 575 inline 576 void 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 591 template <class _Tp, class _Alloc> 592 void 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 606 template <class _Tp, class _Alloc /*= allocator<_Tp>*/> 607 class _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 617 public: 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 #if _LIBCPP_STD_VER > 14 751 template <class... _Args> reference emplace_front(_Args&&... __args); 752 #else 753 template <class... _Args> void emplace_front(_Args&&... __args); 754 #endif 755 #endif 756 void push_front(value_type&& __v); 757 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 758 void push_front(const value_type& __v); 759 760 void pop_front(); 761 762 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 763 #ifndef _LIBCPP_HAS_NO_VARIADICS 764 template <class... _Args> 765 iterator emplace_after(const_iterator __p, _Args&&... __args); 766 #endif // _LIBCPP_HAS_NO_VARIADICS 767 iterator insert_after(const_iterator __p, value_type&& __v); 768 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 769 iterator insert_after(const_iterator __p, const value_type& __v); 770 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 771 template <class _InputIterator> 772 _LIBCPP_INLINE_VISIBILITY 773 typename enable_if 774 < 775 __is_input_iterator<_InputIterator>::value, 776 iterator 777 >::type 778 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 779 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 780 iterator insert_after(const_iterator __p, initializer_list<value_type> __il) 781 {return insert_after(__p, __il.begin(), __il.end());} 782 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 783 784 iterator erase_after(const_iterator __p); 785 iterator erase_after(const_iterator __f, const_iterator __l); 786 787 _LIBCPP_INLINE_VISIBILITY 788 void swap(forward_list& __x) 789 #if _LIBCPP_STD_VER >= 14 790 _NOEXCEPT 791 #else 792 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 793 __is_nothrow_swappable<__node_allocator>::value) 794 #endif 795 {base::swap(__x);} 796 797 void resize(size_type __n); 798 void resize(size_type __n, const value_type& __v); 799 _LIBCPP_INLINE_VISIBILITY 800 void clear() _NOEXCEPT {base::clear();} 801 802 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 803 _LIBCPP_INLINE_VISIBILITY 804 void splice_after(const_iterator __p, forward_list&& __x); 805 _LIBCPP_INLINE_VISIBILITY 806 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 807 _LIBCPP_INLINE_VISIBILITY 808 void splice_after(const_iterator __p, forward_list&& __x, 809 const_iterator __f, const_iterator __l); 810 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 811 void splice_after(const_iterator __p, forward_list& __x); 812 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 813 void splice_after(const_iterator __p, forward_list& __x, 814 const_iterator __f, const_iterator __l); 815 void remove(const value_type& __v); 816 template <class _Predicate> void remove_if(_Predicate __pred); 817 _LIBCPP_INLINE_VISIBILITY 818 void unique() {unique(__equal_to<value_type>());} 819 template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred); 820 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 821 _LIBCPP_INLINE_VISIBILITY 822 void merge(forward_list&& __x) {merge(__x, __less<value_type>());} 823 template <class _Compare> 824 _LIBCPP_INLINE_VISIBILITY 825 void merge(forward_list&& __x, _Compare __comp) 826 {merge(__x, _VSTD::move(__comp));} 827 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 828 _LIBCPP_INLINE_VISIBILITY 829 void merge(forward_list& __x) {merge(__x, __less<value_type>());} 830 template <class _Compare> void merge(forward_list& __x, _Compare __comp); 831 _LIBCPP_INLINE_VISIBILITY 832 void sort() {sort(__less<value_type>());} 833 template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp); 834 void reverse() _NOEXCEPT; 835 836 private: 837 838 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 839 void __move_assign(forward_list& __x, true_type) 840 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 841 void __move_assign(forward_list& __x, false_type); 842 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 843 844 template <class _Compare> 845 static 846 __node_pointer 847 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 848 849 template <class _Compare> 850 static 851 __node_pointer 852 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 853 }; 854 855 template <class _Tp, class _Alloc> 856 inline 857 forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) 858 : base(__a) 859 { 860 } 861 862 template <class _Tp, class _Alloc> 863 forward_list<_Tp, _Alloc>::forward_list(size_type __n) 864 { 865 if (__n > 0) 866 { 867 __node_allocator& __a = base::__alloc(); 868 typedef __allocator_destructor<__node_allocator> _Dp; 869 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 870 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 871 __p = __p->__next_as_begin()) 872 { 873 __h.reset(__node_traits::allocate(__a, 1)); 874 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 875 __h->__next_ = nullptr; 876 __p->__next_ = __h.release(); 877 } 878 } 879 } 880 881 #if _LIBCPP_STD_VER > 11 882 template <class _Tp, class _Alloc> 883 forward_list<_Tp, _Alloc>::forward_list(size_type __n, 884 const allocator_type& __base_alloc) 885 : base ( __base_alloc ) 886 { 887 if (__n > 0) 888 { 889 __node_allocator& __a = base::__alloc(); 890 typedef __allocator_destructor<__node_allocator> _Dp; 891 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 892 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 893 __p = __p->__next_as_begin()) 894 { 895 __h.reset(__node_traits::allocate(__a, 1)); 896 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 897 __h->__next_ = nullptr; 898 __p->__next_ = __h.release(); 899 } 900 } 901 } 902 #endif 903 904 template <class _Tp, class _Alloc> 905 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) 906 { 907 insert_after(cbefore_begin(), __n, __v); 908 } 909 910 template <class _Tp, class _Alloc> 911 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v, 912 const allocator_type& __a) 913 : base(__a) 914 { 915 insert_after(cbefore_begin(), __n, __v); 916 } 917 918 template <class _Tp, class _Alloc> 919 template <class _InputIterator> 920 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 921 typename enable_if< 922 __is_input_iterator<_InputIterator>::value 923 >::type*) 924 { 925 insert_after(cbefore_begin(), __f, __l); 926 } 927 928 template <class _Tp, class _Alloc> 929 template <class _InputIterator> 930 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 931 const allocator_type& __a, 932 typename enable_if< 933 __is_input_iterator<_InputIterator>::value 934 >::type*) 935 : base(__a) 936 { 937 insert_after(cbefore_begin(), __f, __l); 938 } 939 940 template <class _Tp, class _Alloc> 941 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) 942 : base(allocator_type( 943 __node_traits::select_on_container_copy_construction(__x.__alloc()) 944 ) 945 ) 946 { 947 insert_after(cbefore_begin(), __x.begin(), __x.end()); 948 } 949 950 template <class _Tp, class _Alloc> 951 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, 952 const allocator_type& __a) 953 : base(__a) 954 { 955 insert_after(cbefore_begin(), __x.begin(), __x.end()); 956 } 957 958 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 959 960 template <class _Tp, class _Alloc> 961 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, 962 const allocator_type& __a) 963 : base(_VSTD::move(__x), __a) 964 { 965 if (base::__alloc() != __x.__alloc()) 966 { 967 typedef move_iterator<iterator> _Ip; 968 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end())); 969 } 970 } 971 972 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 973 974 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 975 976 template <class _Tp, class _Alloc> 977 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) 978 { 979 insert_after(cbefore_begin(), __il.begin(), __il.end()); 980 } 981 982 template <class _Tp, class _Alloc> 983 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, 984 const allocator_type& __a) 985 : base(__a) 986 { 987 insert_after(cbefore_begin(), __il.begin(), __il.end()); 988 } 989 990 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 991 992 template <class _Tp, class _Alloc> 993 forward_list<_Tp, _Alloc>& 994 forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) 995 { 996 if (this != &__x) 997 { 998 base::__copy_assign_alloc(__x); 999 assign(__x.begin(), __x.end()); 1000 } 1001 return *this; 1002 } 1003 1004 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1005 1006 template <class _Tp, class _Alloc> 1007 void 1008 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type) 1009 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1010 { 1011 clear(); 1012 base::__move_assign_alloc(__x); 1013 base::__before_begin()->__next_ = __x.__before_begin()->__next_; 1014 __x.__before_begin()->__next_ = nullptr; 1015 } 1016 1017 template <class _Tp, class _Alloc> 1018 void 1019 forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) 1020 { 1021 if (base::__alloc() == __x.__alloc()) 1022 __move_assign(__x, true_type()); 1023 else 1024 { 1025 typedef move_iterator<iterator> _Ip; 1026 assign(_Ip(__x.begin()), _Ip(__x.end())); 1027 } 1028 } 1029 1030 template <class _Tp, class _Alloc> 1031 inline 1032 forward_list<_Tp, _Alloc>& 1033 forward_list<_Tp, _Alloc>::operator=(forward_list&& __x) 1034 _NOEXCEPT_( 1035 __node_traits::propagate_on_container_move_assignment::value && 1036 is_nothrow_move_assignable<allocator_type>::value) 1037 { 1038 __move_assign(__x, integral_constant<bool, 1039 __node_traits::propagate_on_container_move_assignment::value>()); 1040 return *this; 1041 } 1042 1043 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1044 1045 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1046 1047 template <class _Tp, class _Alloc> 1048 inline 1049 forward_list<_Tp, _Alloc>& 1050 forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) 1051 { 1052 assign(__il.begin(), __il.end()); 1053 return *this; 1054 } 1055 1056 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1057 1058 template <class _Tp, class _Alloc> 1059 template <class _InputIterator> 1060 typename enable_if 1061 < 1062 __is_input_iterator<_InputIterator>::value, 1063 void 1064 >::type 1065 forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) 1066 { 1067 iterator __i = before_begin(); 1068 iterator __j = _VSTD::next(__i); 1069 iterator __e = end(); 1070 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f) 1071 *__j = *__f; 1072 if (__j == __e) 1073 insert_after(__i, __f, __l); 1074 else 1075 erase_after(__i, __e); 1076 } 1077 1078 template <class _Tp, class _Alloc> 1079 void 1080 forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) 1081 { 1082 iterator __i = before_begin(); 1083 iterator __j = _VSTD::next(__i); 1084 iterator __e = end(); 1085 for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 1086 *__j = __v; 1087 if (__j == __e) 1088 insert_after(__i, __n, __v); 1089 else 1090 erase_after(__i, __e); 1091 } 1092 1093 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1094 1095 template <class _Tp, class _Alloc> 1096 inline 1097 void 1098 forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) 1099 { 1100 assign(__il.begin(), __il.end()); 1101 } 1102 1103 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1104 1105 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1106 #ifndef _LIBCPP_HAS_NO_VARIADICS 1107 1108 template <class _Tp, class _Alloc> 1109 template <class... _Args> 1110 #if _LIBCPP_STD_VER > 14 1111 typename forward_list<_Tp, _Alloc>::reference 1112 #else 1113 void 1114 #endif 1115 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1116 { 1117 __node_allocator& __a = base::__alloc(); 1118 typedef __allocator_destructor<__node_allocator> _Dp; 1119 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1120 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1121 _VSTD::forward<_Args>(__args)...); 1122 __h->__next_ = base::__before_begin()->__next_; 1123 base::__before_begin()->__next_ = __h.release(); 1124 #if _LIBCPP_STD_VER > 14 1125 return base::__before_begin()->__next_->__value_; 1126 #endif 1127 } 1128 1129 #endif // _LIBCPP_HAS_NO_VARIADICS 1130 1131 template <class _Tp, class _Alloc> 1132 void 1133 forward_list<_Tp, _Alloc>::push_front(value_type&& __v) 1134 { 1135 __node_allocator& __a = base::__alloc(); 1136 typedef __allocator_destructor<__node_allocator> _Dp; 1137 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1138 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1139 __h->__next_ = base::__before_begin()->__next_; 1140 base::__before_begin()->__next_ = __h.release(); 1141 } 1142 1143 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1144 1145 template <class _Tp, class _Alloc> 1146 void 1147 forward_list<_Tp, _Alloc>::push_front(const value_type& __v) 1148 { 1149 __node_allocator& __a = base::__alloc(); 1150 typedef __allocator_destructor<__node_allocator> _Dp; 1151 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1152 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1153 __h->__next_ = base::__before_begin()->__next_; 1154 base::__before_begin()->__next_ = __h.release(); 1155 } 1156 1157 template <class _Tp, class _Alloc> 1158 void 1159 forward_list<_Tp, _Alloc>::pop_front() 1160 { 1161 __node_allocator& __a = base::__alloc(); 1162 __node_pointer __p = base::__before_begin()->__next_; 1163 base::__before_begin()->__next_ = __p->__next_; 1164 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 1165 __node_traits::deallocate(__a, __p, 1); 1166 } 1167 1168 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1169 #ifndef _LIBCPP_HAS_NO_VARIADICS 1170 1171 template <class _Tp, class _Alloc> 1172 template <class... _Args> 1173 typename forward_list<_Tp, _Alloc>::iterator 1174 forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) 1175 { 1176 __begin_node_pointer const __r = __p.__get_begin(); 1177 __node_allocator& __a = base::__alloc(); 1178 typedef __allocator_destructor<__node_allocator> _Dp; 1179 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1180 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1181 _VSTD::forward<_Args>(__args)...); 1182 __h->__next_ = __r->__next_; 1183 __r->__next_ = __h.release(); 1184 return iterator(__r->__next_); 1185 } 1186 1187 #endif // _LIBCPP_HAS_NO_VARIADICS 1188 1189 template <class _Tp, class _Alloc> 1190 typename forward_list<_Tp, _Alloc>::iterator 1191 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) 1192 { 1193 __begin_node_pointer const __r = __p.__get_begin(); 1194 __node_allocator& __a = base::__alloc(); 1195 typedef __allocator_destructor<__node_allocator> _Dp; 1196 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1197 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1198 __h->__next_ = __r->__next_; 1199 __r->__next_ = __h.release(); 1200 return iterator(__r->__next_); 1201 } 1202 1203 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1204 1205 template <class _Tp, class _Alloc> 1206 typename forward_list<_Tp, _Alloc>::iterator 1207 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) 1208 { 1209 __begin_node_pointer const __r = __p.__get_begin(); 1210 __node_allocator& __a = base::__alloc(); 1211 typedef __allocator_destructor<__node_allocator> _Dp; 1212 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1213 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1214 __h->__next_ = __r->__next_; 1215 __r->__next_ = __h.release(); 1216 return iterator(__r->__next_); 1217 } 1218 1219 template <class _Tp, class _Alloc> 1220 typename forward_list<_Tp, _Alloc>::iterator 1221 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, 1222 const value_type& __v) 1223 { 1224 __begin_node_pointer __r = __p.__get_begin(); 1225 if (__n > 0) 1226 { 1227 __node_allocator& __a = base::__alloc(); 1228 typedef __allocator_destructor<__node_allocator> _Dp; 1229 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1230 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1231 __node_pointer __first = __h.release(); 1232 __node_pointer __last = __first; 1233 #ifndef _LIBCPP_NO_EXCEPTIONS 1234 try 1235 { 1236 #endif // _LIBCPP_NO_EXCEPTIONS 1237 for (--__n; __n != 0; --__n, __last = __last->__next_) 1238 { 1239 __h.reset(__node_traits::allocate(__a, 1)); 1240 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1241 __last->__next_ = __h.release(); 1242 } 1243 #ifndef _LIBCPP_NO_EXCEPTIONS 1244 } 1245 catch (...) 1246 { 1247 while (__first != nullptr) 1248 { 1249 __node_pointer __next = __first->__next_; 1250 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1251 __node_traits::deallocate(__a, __first, 1); 1252 __first = __next; 1253 } 1254 throw; 1255 } 1256 #endif // _LIBCPP_NO_EXCEPTIONS 1257 __last->__next_ = __r->__next_; 1258 __r->__next_ = __first; 1259 __r = static_cast<__begin_node_pointer>(__last); 1260 } 1261 return iterator(__r); 1262 } 1263 1264 template <class _Tp, class _Alloc> 1265 template <class _InputIterator> 1266 typename enable_if 1267 < 1268 __is_input_iterator<_InputIterator>::value, 1269 typename forward_list<_Tp, _Alloc>::iterator 1270 >::type 1271 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, 1272 _InputIterator __f, _InputIterator __l) 1273 { 1274 __begin_node_pointer __r = __p.__get_begin(); 1275 if (__f != __l) 1276 { 1277 __node_allocator& __a = base::__alloc(); 1278 typedef __allocator_destructor<__node_allocator> _Dp; 1279 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1280 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1281 __node_pointer __first = __h.release(); 1282 __node_pointer __last = __first; 1283 #ifndef _LIBCPP_NO_EXCEPTIONS 1284 try 1285 { 1286 #endif // _LIBCPP_NO_EXCEPTIONS 1287 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) 1288 { 1289 __h.reset(__node_traits::allocate(__a, 1)); 1290 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1291 __last->__next_ = __h.release(); 1292 } 1293 #ifndef _LIBCPP_NO_EXCEPTIONS 1294 } 1295 catch (...) 1296 { 1297 while (__first != nullptr) 1298 { 1299 __node_pointer __next = __first->__next_; 1300 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1301 __node_traits::deallocate(__a, __first, 1); 1302 __first = __next; 1303 } 1304 throw; 1305 } 1306 #endif // _LIBCPP_NO_EXCEPTIONS 1307 __last->__next_ = __r->__next_; 1308 __r->__next_ = __first; 1309 __r = static_cast<__begin_node_pointer>(__last); 1310 } 1311 return iterator(__r); 1312 } 1313 1314 template <class _Tp, class _Alloc> 1315 typename forward_list<_Tp, _Alloc>::iterator 1316 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) 1317 { 1318 __begin_node_pointer __p = __f.__get_begin(); 1319 __node_pointer __n = __p->__next_; 1320 __p->__next_ = __n->__next_; 1321 __node_allocator& __a = base::__alloc(); 1322 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1323 __node_traits::deallocate(__a, __n, 1); 1324 return iterator(__p->__next_); 1325 } 1326 1327 template <class _Tp, class _Alloc> 1328 typename forward_list<_Tp, _Alloc>::iterator 1329 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) 1330 { 1331 __node_pointer __e = __l.__get_unsafe_node_pointer(); 1332 if (__f != __l) 1333 { 1334 __begin_node_pointer __bp = __f.__get_begin(); 1335 1336 __node_pointer __n = __bp->__next_; 1337 if (__n != __e) 1338 { 1339 __bp->__next_ = __e; 1340 __node_allocator& __a = base::__alloc(); 1341 do 1342 { 1343 __node_pointer __tmp = __n->__next_; 1344 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1345 __node_traits::deallocate(__a, __n, 1); 1346 __n = __tmp; 1347 } while (__n != __e); 1348 } 1349 } 1350 return iterator(__e); 1351 } 1352 1353 template <class _Tp, class _Alloc> 1354 void 1355 forward_list<_Tp, _Alloc>::resize(size_type __n) 1356 { 1357 size_type __sz = 0; 1358 iterator __p = before_begin(); 1359 iterator __i = begin(); 1360 iterator __e = end(); 1361 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1362 ; 1363 if (__i != __e) 1364 erase_after(__p, __e); 1365 else 1366 { 1367 __n -= __sz; 1368 if (__n > 0) 1369 { 1370 __node_allocator& __a = base::__alloc(); 1371 typedef __allocator_destructor<__node_allocator> _Dp; 1372 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1373 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, 1374 __ptr = __ptr->__next_as_begin()) 1375 { 1376 __h.reset(__node_traits::allocate(__a, 1)); 1377 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 1378 __h->__next_ = nullptr; 1379 __ptr->__next_ = __h.release(); 1380 } 1381 } 1382 } 1383 } 1384 1385 template <class _Tp, class _Alloc> 1386 void 1387 forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) 1388 { 1389 size_type __sz = 0; 1390 iterator __p = before_begin(); 1391 iterator __i = begin(); 1392 iterator __e = end(); 1393 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1394 ; 1395 if (__i != __e) 1396 erase_after(__p, __e); 1397 else 1398 { 1399 __n -= __sz; 1400 if (__n > 0) 1401 { 1402 __node_allocator& __a = base::__alloc(); 1403 typedef __allocator_destructor<__node_allocator> _Dp; 1404 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1405 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, 1406 __ptr = __ptr->__next_as_begin()) 1407 { 1408 __h.reset(__node_traits::allocate(__a, 1)); 1409 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1410 __h->__next_ = nullptr; 1411 __ptr->__next_ = __h.release(); 1412 } 1413 } 1414 } 1415 } 1416 1417 template <class _Tp, class _Alloc> 1418 void 1419 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1420 forward_list& __x) 1421 { 1422 if (!__x.empty()) 1423 { 1424 if (__p.__get_begin()->__next_ != nullptr) 1425 { 1426 const_iterator __lm1 = __x.before_begin(); 1427 while (__lm1.__get_begin()->__next_ != nullptr) 1428 ++__lm1; 1429 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1430 } 1431 __p.__get_begin()->__next_ = __x.__before_begin()->__next_; 1432 __x.__before_begin()->__next_ = nullptr; 1433 } 1434 } 1435 1436 template <class _Tp, class _Alloc> 1437 void 1438 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1439 forward_list& /*__other*/, 1440 const_iterator __i) 1441 { 1442 const_iterator __lm1 = _VSTD::next(__i); 1443 if (__p != __i && __p != __lm1) 1444 { 1445 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_; 1446 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1447 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer(); 1448 } 1449 } 1450 1451 template <class _Tp, class _Alloc> 1452 void 1453 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1454 forward_list& /*__other*/, 1455 const_iterator __f, const_iterator __l) 1456 { 1457 if (__f != __l && __p != __f) 1458 { 1459 const_iterator __lm1 = __f; 1460 while (__lm1.__get_begin()->__next_ != __l.__get_begin()) 1461 ++__lm1; 1462 if (__f != __lm1) 1463 { 1464 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1465 __p.__get_begin()->__next_ = __f.__get_begin()->__next_; 1466 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer(); 1467 } 1468 } 1469 } 1470 1471 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1472 1473 template <class _Tp, class _Alloc> 1474 inline _LIBCPP_INLINE_VISIBILITY 1475 void 1476 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1477 forward_list&& __x) 1478 { 1479 splice_after(__p, __x); 1480 } 1481 1482 template <class _Tp, class _Alloc> 1483 inline _LIBCPP_INLINE_VISIBILITY 1484 void 1485 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1486 forward_list&& __x, 1487 const_iterator __i) 1488 { 1489 splice_after(__p, __x, __i); 1490 } 1491 1492 template <class _Tp, class _Alloc> 1493 inline _LIBCPP_INLINE_VISIBILITY 1494 void 1495 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1496 forward_list&& __x, 1497 const_iterator __f, const_iterator __l) 1498 { 1499 splice_after(__p, __x, __f, __l); 1500 } 1501 1502 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1503 1504 template <class _Tp, class _Alloc> 1505 void 1506 forward_list<_Tp, _Alloc>::remove(const value_type& __v) 1507 { 1508 forward_list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing 1509 iterator __e = end(); 1510 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) 1511 { 1512 if (__i.__get_begin()->__next_->__value_ == __v) 1513 { 1514 iterator __j = _VSTD::next(__i, 2); 1515 for (; __j != __e && *__j == __v; ++__j) 1516 ; 1517 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1518 if (__j == __e) 1519 break; 1520 __i = __j; 1521 } 1522 else 1523 ++__i; 1524 } 1525 } 1526 1527 template <class _Tp, class _Alloc> 1528 template <class _Predicate> 1529 void 1530 forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) 1531 { 1532 iterator __e = end(); 1533 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) 1534 { 1535 if (__pred(__i.__get_begin()->__next_->__value_)) 1536 { 1537 iterator __j = _VSTD::next(__i, 2); 1538 for (; __j != __e && __pred(*__j); ++__j) 1539 ; 1540 erase_after(__i, __j); 1541 if (__j == __e) 1542 break; 1543 __i = __j; 1544 } 1545 else 1546 ++__i; 1547 } 1548 } 1549 1550 template <class _Tp, class _Alloc> 1551 template <class _BinaryPredicate> 1552 void 1553 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) 1554 { 1555 for (iterator __i = begin(), __e = end(); __i != __e;) 1556 { 1557 iterator __j = _VSTD::next(__i); 1558 for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 1559 ; 1560 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer()) 1561 erase_after(__i, __j); 1562 __i = __j; 1563 } 1564 } 1565 1566 template <class _Tp, class _Alloc> 1567 template <class _Compare> 1568 void 1569 forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) 1570 { 1571 if (this != &__x) 1572 { 1573 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, 1574 __x.__before_begin()->__next_, 1575 __comp); 1576 __x.__before_begin()->__next_ = nullptr; 1577 } 1578 } 1579 1580 template <class _Tp, class _Alloc> 1581 template <class _Compare> 1582 typename forward_list<_Tp, _Alloc>::__node_pointer 1583 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, 1584 _Compare& __comp) 1585 { 1586 if (__f1 == nullptr) 1587 return __f2; 1588 if (__f2 == nullptr) 1589 return __f1; 1590 __node_pointer __r; 1591 if (__comp(__f2->__value_, __f1->__value_)) 1592 { 1593 __node_pointer __t = __f2; 1594 while (__t->__next_ != nullptr && 1595 __comp(__t->__next_->__value_, __f1->__value_)) 1596 __t = __t->__next_; 1597 __r = __f2; 1598 __f2 = __t->__next_; 1599 __t->__next_ = __f1; 1600 } 1601 else 1602 __r = __f1; 1603 __node_pointer __p = __f1; 1604 __f1 = __f1->__next_; 1605 while (__f1 != nullptr && __f2 != nullptr) 1606 { 1607 if (__comp(__f2->__value_, __f1->__value_)) 1608 { 1609 __node_pointer __t = __f2; 1610 while (__t->__next_ != nullptr && 1611 __comp(__t->__next_->__value_, __f1->__value_)) 1612 __t = __t->__next_; 1613 __p->__next_ = __f2; 1614 __f2 = __t->__next_; 1615 __t->__next_ = __f1; 1616 } 1617 __p = __f1; 1618 __f1 = __f1->__next_; 1619 } 1620 if (__f2 != nullptr) 1621 __p->__next_ = __f2; 1622 return __r; 1623 } 1624 1625 template <class _Tp, class _Alloc> 1626 template <class _Compare> 1627 inline 1628 void 1629 forward_list<_Tp, _Alloc>::sort(_Compare __comp) 1630 { 1631 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, 1632 _VSTD::distance(begin(), end()), __comp); 1633 } 1634 1635 template <class _Tp, class _Alloc> 1636 template <class _Compare> 1637 typename forward_list<_Tp, _Alloc>::__node_pointer 1638 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, 1639 _Compare& __comp) 1640 { 1641 switch (__sz) 1642 { 1643 case 0: 1644 case 1: 1645 return __f1; 1646 case 2: 1647 if (__comp(__f1->__next_->__value_, __f1->__value_)) 1648 { 1649 __node_pointer __t = __f1->__next_; 1650 __t->__next_ = __f1; 1651 __f1->__next_ = nullptr; 1652 __f1 = __t; 1653 } 1654 return __f1; 1655 } 1656 difference_type __sz1 = __sz / 2; 1657 difference_type __sz2 = __sz - __sz1; 1658 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer(); 1659 __node_pointer __f2 = __t->__next_; 1660 __t->__next_ = nullptr; 1661 return __merge(__sort(__f1, __sz1, __comp), 1662 __sort(__f2, __sz2, __comp), __comp); 1663 } 1664 1665 template <class _Tp, class _Alloc> 1666 void 1667 forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT 1668 { 1669 __node_pointer __p = base::__before_begin()->__next_; 1670 if (__p != nullptr) 1671 { 1672 __node_pointer __f = __p->__next_; 1673 __p->__next_ = nullptr; 1674 while (__f != nullptr) 1675 { 1676 __node_pointer __t = __f->__next_; 1677 __f->__next_ = __p; 1678 __p = __f; 1679 __f = __t; 1680 } 1681 base::__before_begin()->__next_ = __p; 1682 } 1683 } 1684 1685 template <class _Tp, class _Alloc> 1686 bool operator==(const forward_list<_Tp, _Alloc>& __x, 1687 const forward_list<_Tp, _Alloc>& __y) 1688 { 1689 typedef forward_list<_Tp, _Alloc> _Cp; 1690 typedef typename _Cp::const_iterator _Ip; 1691 _Ip __ix = __x.begin(); 1692 _Ip __ex = __x.end(); 1693 _Ip __iy = __y.begin(); 1694 _Ip __ey = __y.end(); 1695 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) 1696 if (!(*__ix == *__iy)) 1697 return false; 1698 return (__ix == __ex) == (__iy == __ey); 1699 } 1700 1701 template <class _Tp, class _Alloc> 1702 inline _LIBCPP_INLINE_VISIBILITY 1703 bool operator!=(const forward_list<_Tp, _Alloc>& __x, 1704 const forward_list<_Tp, _Alloc>& __y) 1705 { 1706 return !(__x == __y); 1707 } 1708 1709 template <class _Tp, class _Alloc> 1710 inline _LIBCPP_INLINE_VISIBILITY 1711 bool operator< (const forward_list<_Tp, _Alloc>& __x, 1712 const forward_list<_Tp, _Alloc>& __y) 1713 { 1714 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), 1715 __y.begin(), __y.end()); 1716 } 1717 1718 template <class _Tp, class _Alloc> 1719 inline _LIBCPP_INLINE_VISIBILITY 1720 bool operator> (const forward_list<_Tp, _Alloc>& __x, 1721 const forward_list<_Tp, _Alloc>& __y) 1722 { 1723 return __y < __x; 1724 } 1725 1726 template <class _Tp, class _Alloc> 1727 inline _LIBCPP_INLINE_VISIBILITY 1728 bool operator>=(const forward_list<_Tp, _Alloc>& __x, 1729 const forward_list<_Tp, _Alloc>& __y) 1730 { 1731 return !(__x < __y); 1732 } 1733 1734 template <class _Tp, class _Alloc> 1735 inline _LIBCPP_INLINE_VISIBILITY 1736 bool operator<=(const forward_list<_Tp, _Alloc>& __x, 1737 const forward_list<_Tp, _Alloc>& __y) 1738 { 1739 return !(__y < __x); 1740 } 1741 1742 template <class _Tp, class _Alloc> 1743 inline _LIBCPP_INLINE_VISIBILITY 1744 void 1745 swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) 1746 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1747 { 1748 __x.swap(__y); 1749 } 1750 1751 _LIBCPP_END_NAMESPACE_STD 1752 1753 #endif // _LIBCPP_FORWARD_LIST 1754
