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