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