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