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