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