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> void emplace_front(Args&&... args); 91 void push_front(const value_type& v); 92 void push_front(value_type&& v); 93 94 void pop_front(); 95 96 template <class... Args> 97 iterator emplace_after(const_iterator p, Args&&... args); 98 iterator insert_after(const_iterator p, const value_type& v); 99 iterator insert_after(const_iterator p, value_type&& v); 100 iterator insert_after(const_iterator p, size_type n, const value_type& v); 101 template <class InputIterator> 102 iterator insert_after(const_iterator p, 103 InputIterator first, InputIterator last); 104 iterator insert_after(const_iterator p, initializer_list<value_type> il); 105 106 iterator erase_after(const_iterator p); 107 iterator erase_after(const_iterator first, const_iterator last); 108 109 void swap(forward_list& x) 110 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 111 112 void resize(size_type n); 113 void resize(size_type n, const value_type& v); 114 void clear() noexcept; 115 116 void splice_after(const_iterator p, forward_list& x); 117 void splice_after(const_iterator p, forward_list&& x); 118 void splice_after(const_iterator p, forward_list& x, const_iterator i); 119 void splice_after(const_iterator p, forward_list&& x, const_iterator i); 120 void splice_after(const_iterator p, forward_list& x, 121 const_iterator first, const_iterator last); 122 void splice_after(const_iterator p, forward_list&& x, 123 const_iterator first, const_iterator last); 124 void remove(const value_type& v); 125 template <class Predicate> void remove_if(Predicate pred); 126 void unique(); 127 template <class BinaryPredicate> void unique(BinaryPredicate binary_pred); 128 void merge(forward_list& x); 129 void merge(forward_list&& x); 130 template <class Compare> void merge(forward_list& x, Compare comp); 131 template <class Compare> void merge(forward_list&& x, Compare comp); 132 void sort(); 133 template <class Compare> void sort(Compare comp); 134 void reverse() noexcept; 135}; 136 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_TYPE_VIS_ONLY forward_list; 270template<class _NodeConstPtr> class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator; 271 272template <class _NodePtr> 273class _LIBCPP_TYPE_VIS_ONLY __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_TYPE_VIS_ONLY forward_list; 306 template<class> friend class _LIBCPP_TYPE_VIS_ONLY __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_TYPE_VIS_ONLY __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& __x, 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_TYPE_VIS_ONLY 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 numeric_limits<size_type>::max();} 739 740 _LIBCPP_INLINE_VISIBILITY 741 reference front() {return base::__before_begin()->__next_->__value_;} 742 _LIBCPP_INLINE_VISIBILITY 743 const_reference front() const {return base::__before_begin()->__next_->__value_;} 744 745#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 746#ifndef _LIBCPP_HAS_NO_VARIADICS 747 template <class... _Args> void emplace_front(_Args&&... __args); 748#endif 749 void push_front(value_type&& __v); 750#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 751 void push_front(const value_type& __v); 752 753 void pop_front(); 754 755#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 756#ifndef _LIBCPP_HAS_NO_VARIADICS 757 template <class... _Args> 758 iterator emplace_after(const_iterator __p, _Args&&... __args); 759#endif // _LIBCPP_HAS_NO_VARIADICS 760 iterator insert_after(const_iterator __p, value_type&& __v); 761#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 762 iterator insert_after(const_iterator __p, const value_type& __v); 763 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 764 template <class _InputIterator> 765 _LIBCPP_INLINE_VISIBILITY 766 typename enable_if 767 < 768 __is_input_iterator<_InputIterator>::value, 769 iterator 770 >::type 771 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 772#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 773 iterator insert_after(const_iterator __p, initializer_list<value_type> __il) 774 {return insert_after(__p, __il.begin(), __il.end());} 775#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 776 777 iterator erase_after(const_iterator __p); 778 iterator erase_after(const_iterator __f, const_iterator __l); 779 780 _LIBCPP_INLINE_VISIBILITY 781 void swap(forward_list& __x) 782#if _LIBCPP_STD_VER >= 14 783 _NOEXCEPT 784#else 785 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 786 __is_nothrow_swappable<__node_allocator>::value) 787#endif 788 {base::swap(__x);} 789 790 void resize(size_type __n); 791 void resize(size_type __n, const value_type& __v); 792 _LIBCPP_INLINE_VISIBILITY 793 void clear() _NOEXCEPT {base::clear();} 794 795#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 796 _LIBCPP_INLINE_VISIBILITY 797 void splice_after(const_iterator __p, forward_list&& __x); 798 _LIBCPP_INLINE_VISIBILITY 799 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 800 _LIBCPP_INLINE_VISIBILITY 801 void splice_after(const_iterator __p, forward_list&& __x, 802 const_iterator __f, const_iterator __l); 803#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 804 void splice_after(const_iterator __p, forward_list& __x); 805 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 806 void splice_after(const_iterator __p, forward_list& __x, 807 const_iterator __f, const_iterator __l); 808 void remove(const value_type& __v); 809 template <class _Predicate> void remove_if(_Predicate __pred); 810 _LIBCPP_INLINE_VISIBILITY 811 void unique() {unique(__equal_to<value_type>());} 812 template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred); 813#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 814 _LIBCPP_INLINE_VISIBILITY 815 void merge(forward_list&& __x) {merge(__x, __less<value_type>());} 816 template <class _Compare> 817 _LIBCPP_INLINE_VISIBILITY 818 void merge(forward_list&& __x, _Compare __comp) 819 {merge(__x, _VSTD::move(__comp));} 820#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 821 _LIBCPP_INLINE_VISIBILITY 822 void merge(forward_list& __x) {merge(__x, __less<value_type>());} 823 template <class _Compare> void merge(forward_list& __x, _Compare __comp); 824 _LIBCPP_INLINE_VISIBILITY 825 void sort() {sort(__less<value_type>());} 826 template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp); 827 void reverse() _NOEXCEPT; 828 829private: 830 831#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 832 void __move_assign(forward_list& __x, true_type) 833 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 834 void __move_assign(forward_list& __x, false_type); 835#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 836 837 template <class _Compare> 838 static 839 __node_pointer 840 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 841 842 template <class _Compare> 843 static 844 __node_pointer 845 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 846}; 847 848template <class _Tp, class _Alloc> 849inline 850forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) 851 : base(__a) 852{ 853} 854 855template <class _Tp, class _Alloc> 856forward_list<_Tp, _Alloc>::forward_list(size_type __n) 857{ 858 if (__n > 0) 859 { 860 __node_allocator& __a = base::__alloc(); 861 typedef __allocator_destructor<__node_allocator> _Dp; 862 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 863 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 864 __p = __p->__next_as_begin()) 865 { 866 __h.reset(__node_traits::allocate(__a, 1)); 867 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 868 __h->__next_ = nullptr; 869 __p->__next_ = __h.release(); 870 } 871 } 872} 873 874#if _LIBCPP_STD_VER > 11 875template <class _Tp, class _Alloc> 876forward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __a) 877 : base ( __a ) 878{ 879 if (__n > 0) 880 { 881 __node_allocator& __a = base::__alloc(); 882 typedef __allocator_destructor<__node_allocator> _Dp; 883 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 884 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 885 __p = __p->__next_as_begin()) 886 { 887 __h.reset(__node_traits::allocate(__a, 1)); 888 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 889 __h->__next_ = nullptr; 890 __p->__next_ = __h.release(); 891 } 892 } 893} 894#endif 895 896template <class _Tp, class _Alloc> 897forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) 898{ 899 insert_after(cbefore_begin(), __n, __v); 900} 901 902template <class _Tp, class _Alloc> 903forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v, 904 const allocator_type& __a) 905 : base(__a) 906{ 907 insert_after(cbefore_begin(), __n, __v); 908} 909 910template <class _Tp, class _Alloc> 911template <class _InputIterator> 912forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 913 typename enable_if< 914 __is_input_iterator<_InputIterator>::value 915 >::type*) 916{ 917 insert_after(cbefore_begin(), __f, __l); 918} 919 920template <class _Tp, class _Alloc> 921template <class _InputIterator> 922forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, 923 const allocator_type& __a, 924 typename enable_if< 925 __is_input_iterator<_InputIterator>::value 926 >::type*) 927 : base(__a) 928{ 929 insert_after(cbefore_begin(), __f, __l); 930} 931 932template <class _Tp, class _Alloc> 933forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) 934 : base(allocator_type( 935 __node_traits::select_on_container_copy_construction(__x.__alloc()) 936 ) 937 ) 938{ 939 insert_after(cbefore_begin(), __x.begin(), __x.end()); 940} 941 942template <class _Tp, class _Alloc> 943forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, 944 const allocator_type& __a) 945 : base(__a) 946{ 947 insert_after(cbefore_begin(), __x.begin(), __x.end()); 948} 949 950#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 951 952template <class _Tp, class _Alloc> 953forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, 954 const allocator_type& __a) 955 : base(_VSTD::move(__x), __a) 956{ 957 if (base::__alloc() != __x.__alloc()) 958 { 959 typedef move_iterator<iterator> _Ip; 960 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end())); 961 } 962} 963 964#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 965 966#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 967 968template <class _Tp, class _Alloc> 969forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) 970{ 971 insert_after(cbefore_begin(), __il.begin(), __il.end()); 972} 973 974template <class _Tp, class _Alloc> 975forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, 976 const allocator_type& __a) 977 : base(__a) 978{ 979 insert_after(cbefore_begin(), __il.begin(), __il.end()); 980} 981 982#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 983 984template <class _Tp, class _Alloc> 985forward_list<_Tp, _Alloc>& 986forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) 987{ 988 if (this != &__x) 989 { 990 base::__copy_assign_alloc(__x); 991 assign(__x.begin(), __x.end()); 992 } 993 return *this; 994} 995 996#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 997 998template <class _Tp, class _Alloc> 999void 1000forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type) 1001 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1002{ 1003 clear(); 1004 base::__move_assign_alloc(__x); 1005 base::__before_begin()->__next_ = __x.__before_begin()->__next_; 1006 __x.__before_begin()->__next_ = nullptr; 1007} 1008 1009template <class _Tp, class _Alloc> 1010void 1011forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) 1012{ 1013 if (base::__alloc() == __x.__alloc()) 1014 __move_assign(__x, true_type()); 1015 else 1016 { 1017 typedef move_iterator<iterator> _Ip; 1018 assign(_Ip(__x.begin()), _Ip(__x.end())); 1019 } 1020} 1021 1022template <class _Tp, class _Alloc> 1023inline 1024forward_list<_Tp, _Alloc>& 1025forward_list<_Tp, _Alloc>::operator=(forward_list&& __x) 1026 _NOEXCEPT_( 1027 __node_traits::propagate_on_container_move_assignment::value && 1028 is_nothrow_move_assignable<allocator_type>::value) 1029{ 1030 __move_assign(__x, integral_constant<bool, 1031 __node_traits::propagate_on_container_move_assignment::value>()); 1032 return *this; 1033} 1034 1035#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1036 1037#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1038 1039template <class _Tp, class _Alloc> 1040inline 1041forward_list<_Tp, _Alloc>& 1042forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) 1043{ 1044 assign(__il.begin(), __il.end()); 1045 return *this; 1046} 1047 1048#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1049 1050template <class _Tp, class _Alloc> 1051template <class _InputIterator> 1052typename enable_if 1053< 1054 __is_input_iterator<_InputIterator>::value, 1055 void 1056>::type 1057forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) 1058{ 1059 iterator __i = before_begin(); 1060 iterator __j = _VSTD::next(__i); 1061 iterator __e = end(); 1062 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f) 1063 *__j = *__f; 1064 if (__j == __e) 1065 insert_after(__i, __f, __l); 1066 else 1067 erase_after(__i, __e); 1068} 1069 1070template <class _Tp, class _Alloc> 1071void 1072forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) 1073{ 1074 iterator __i = before_begin(); 1075 iterator __j = _VSTD::next(__i); 1076 iterator __e = end(); 1077 for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 1078 *__j = __v; 1079 if (__j == __e) 1080 insert_after(__i, __n, __v); 1081 else 1082 erase_after(__i, __e); 1083} 1084 1085#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1086 1087template <class _Tp, class _Alloc> 1088inline 1089void 1090forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) 1091{ 1092 assign(__il.begin(), __il.end()); 1093} 1094 1095#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1096 1097#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1098#ifndef _LIBCPP_HAS_NO_VARIADICS 1099 1100template <class _Tp, class _Alloc> 1101template <class... _Args> 1102void 1103forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1104{ 1105 __node_allocator& __a = base::__alloc(); 1106 typedef __allocator_destructor<__node_allocator> _Dp; 1107 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1108 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1109 _VSTD::forward<_Args>(__args)...); 1110 __h->__next_ = base::__before_begin()->__next_; 1111 base::__before_begin()->__next_ = __h.release(); 1112} 1113 1114#endif // _LIBCPP_HAS_NO_VARIADICS 1115 1116template <class _Tp, class _Alloc> 1117void 1118forward_list<_Tp, _Alloc>::push_front(value_type&& __v) 1119{ 1120 __node_allocator& __a = base::__alloc(); 1121 typedef __allocator_destructor<__node_allocator> _Dp; 1122 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1123 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1124 __h->__next_ = base::__before_begin()->__next_; 1125 base::__before_begin()->__next_ = __h.release(); 1126} 1127 1128#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1129 1130template <class _Tp, class _Alloc> 1131void 1132forward_list<_Tp, _Alloc>::push_front(const value_type& __v) 1133{ 1134 __node_allocator& __a = base::__alloc(); 1135 typedef __allocator_destructor<__node_allocator> _Dp; 1136 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1137 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1138 __h->__next_ = base::__before_begin()->__next_; 1139 base::__before_begin()->__next_ = __h.release(); 1140} 1141 1142template <class _Tp, class _Alloc> 1143void 1144forward_list<_Tp, _Alloc>::pop_front() 1145{ 1146 __node_allocator& __a = base::__alloc(); 1147 __node_pointer __p = base::__before_begin()->__next_; 1148 base::__before_begin()->__next_ = __p->__next_; 1149 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 1150 __node_traits::deallocate(__a, __p, 1); 1151} 1152 1153#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1154#ifndef _LIBCPP_HAS_NO_VARIADICS 1155 1156template <class _Tp, class _Alloc> 1157template <class... _Args> 1158typename forward_list<_Tp, _Alloc>::iterator 1159forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) 1160{ 1161 __begin_node_pointer const __r = __p.__get_begin(); 1162 __node_allocator& __a = base::__alloc(); 1163 typedef __allocator_destructor<__node_allocator> _Dp; 1164 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1165 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1166 _VSTD::forward<_Args>(__args)...); 1167 __h->__next_ = __r->__next_; 1168 __r->__next_ = __h.release(); 1169 return iterator(__r->__next_); 1170} 1171 1172#endif // _LIBCPP_HAS_NO_VARIADICS 1173 1174template <class _Tp, class _Alloc> 1175typename forward_list<_Tp, _Alloc>::iterator 1176forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) 1177{ 1178 __begin_node_pointer const __r = __p.__get_begin(); 1179 __node_allocator& __a = base::__alloc(); 1180 typedef __allocator_destructor<__node_allocator> _Dp; 1181 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1182 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1183 __h->__next_ = __r->__next_; 1184 __r->__next_ = __h.release(); 1185 return iterator(__r->__next_); 1186} 1187 1188#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1189 1190template <class _Tp, class _Alloc> 1191typename forward_list<_Tp, _Alloc>::iterator 1192forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) 1193{ 1194 __begin_node_pointer const __r = __p.__get_begin(); 1195 __node_allocator& __a = base::__alloc(); 1196 typedef __allocator_destructor<__node_allocator> _Dp; 1197 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1198 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1199 __h->__next_ = __r->__next_; 1200 __r->__next_ = __h.release(); 1201 return iterator(__r->__next_); 1202} 1203 1204template <class _Tp, class _Alloc> 1205typename forward_list<_Tp, _Alloc>::iterator 1206forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, 1207 const value_type& __v) 1208{ 1209 __begin_node_pointer __r = __p.__get_begin(); 1210 if (__n > 0) 1211 { 1212 __node_allocator& __a = base::__alloc(); 1213 typedef __allocator_destructor<__node_allocator> _Dp; 1214 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1215 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1216 __node_pointer __first = __h.release(); 1217 __node_pointer __last = __first; 1218#ifndef _LIBCPP_NO_EXCEPTIONS 1219 try 1220 { 1221#endif // _LIBCPP_NO_EXCEPTIONS 1222 for (--__n; __n != 0; --__n, __last = __last->__next_) 1223 { 1224 __h.reset(__node_traits::allocate(__a, 1)); 1225 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1226 __last->__next_ = __h.release(); 1227 } 1228#ifndef _LIBCPP_NO_EXCEPTIONS 1229 } 1230 catch (...) 1231 { 1232 while (__first != nullptr) 1233 { 1234 __node_pointer __next = __first->__next_; 1235 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1236 __node_traits::deallocate(__a, __first, 1); 1237 __first = __next; 1238 } 1239 throw; 1240 } 1241#endif // _LIBCPP_NO_EXCEPTIONS 1242 __last->__next_ = __r->__next_; 1243 __r->__next_ = __first; 1244 __r = static_cast<__begin_node_pointer>(__last); 1245 } 1246 return iterator(__r); 1247} 1248 1249template <class _Tp, class _Alloc> 1250template <class _InputIterator> 1251typename enable_if 1252< 1253 __is_input_iterator<_InputIterator>::value, 1254 typename forward_list<_Tp, _Alloc>::iterator 1255>::type 1256forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, 1257 _InputIterator __f, _InputIterator __l) 1258{ 1259 __begin_node_pointer __r = __p.__get_begin(); 1260 if (__f != __l) 1261 { 1262 __node_allocator& __a = base::__alloc(); 1263 typedef __allocator_destructor<__node_allocator> _Dp; 1264 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1265 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1266 __node_pointer __first = __h.release(); 1267 __node_pointer __last = __first; 1268#ifndef _LIBCPP_NO_EXCEPTIONS 1269 try 1270 { 1271#endif // _LIBCPP_NO_EXCEPTIONS 1272 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) 1273 { 1274 __h.reset(__node_traits::allocate(__a, 1)); 1275 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1276 __last->__next_ = __h.release(); 1277 } 1278#ifndef _LIBCPP_NO_EXCEPTIONS 1279 } 1280 catch (...) 1281 { 1282 while (__first != nullptr) 1283 { 1284 __node_pointer __next = __first->__next_; 1285 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1286 __node_traits::deallocate(__a, __first, 1); 1287 __first = __next; 1288 } 1289 throw; 1290 } 1291#endif // _LIBCPP_NO_EXCEPTIONS 1292 __last->__next_ = __r->__next_; 1293 __r->__next_ = __first; 1294 __r = static_cast<__begin_node_pointer>(__last); 1295 } 1296 return iterator(__r); 1297} 1298 1299template <class _Tp, class _Alloc> 1300typename forward_list<_Tp, _Alloc>::iterator 1301forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) 1302{ 1303 __begin_node_pointer __p = __f.__get_begin(); 1304 __node_pointer __n = __p->__next_; 1305 __p->__next_ = __n->__next_; 1306 __node_allocator& __a = base::__alloc(); 1307 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1308 __node_traits::deallocate(__a, __n, 1); 1309 return iterator(__p->__next_); 1310} 1311 1312template <class _Tp, class _Alloc> 1313typename forward_list<_Tp, _Alloc>::iterator 1314forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) 1315{ 1316 __node_pointer __e = __l.__get_unsafe_node_pointer(); 1317 if (__f != __l) 1318 { 1319 __begin_node_pointer __bp = __f.__get_begin(); 1320 1321 __node_pointer __n = __bp->__next_; 1322 if (__n != __e) 1323 { 1324 __bp->__next_ = __e; 1325 __node_allocator& __a = base::__alloc(); 1326 do 1327 { 1328 __node_pointer __tmp = __n->__next_; 1329 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1330 __node_traits::deallocate(__a, __n, 1); 1331 __n = __tmp; 1332 } while (__n != __e); 1333 } 1334 } 1335 return iterator(__e); 1336} 1337 1338template <class _Tp, class _Alloc> 1339void 1340forward_list<_Tp, _Alloc>::resize(size_type __n) 1341{ 1342 size_type __sz = 0; 1343 iterator __p = before_begin(); 1344 iterator __i = begin(); 1345 iterator __e = end(); 1346 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1347 ; 1348 if (__i != __e) 1349 erase_after(__p, __e); 1350 else 1351 { 1352 __n -= __sz; 1353 if (__n > 0) 1354 { 1355 __node_allocator& __a = base::__alloc(); 1356 typedef __allocator_destructor<__node_allocator> _Dp; 1357 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1358 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, 1359 __ptr = __ptr->__next_as_begin()) 1360 { 1361 __h.reset(__node_traits::allocate(__a, 1)); 1362 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 1363 __h->__next_ = nullptr; 1364 __ptr->__next_ = __h.release(); 1365 } 1366 } 1367 } 1368} 1369 1370template <class _Tp, class _Alloc> 1371void 1372forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) 1373{ 1374 size_type __sz = 0; 1375 iterator __p = before_begin(); 1376 iterator __i = begin(); 1377 iterator __e = end(); 1378 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1379 ; 1380 if (__i != __e) 1381 erase_after(__p, __e); 1382 else 1383 { 1384 __n -= __sz; 1385 if (__n > 0) 1386 { 1387 __node_allocator& __a = base::__alloc(); 1388 typedef __allocator_destructor<__node_allocator> _Dp; 1389 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1390 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, 1391 __ptr = __ptr->__next_as_begin()) 1392 { 1393 __h.reset(__node_traits::allocate(__a, 1)); 1394 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1395 __h->__next_ = nullptr; 1396 __ptr->__next_ = __h.release(); 1397 } 1398 } 1399 } 1400} 1401 1402template <class _Tp, class _Alloc> 1403void 1404forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1405 forward_list& __x) 1406{ 1407 if (!__x.empty()) 1408 { 1409 if (__p.__get_begin()->__next_ != nullptr) 1410 { 1411 const_iterator __lm1 = __x.before_begin(); 1412 while (__lm1.__get_begin()->__next_ != nullptr) 1413 ++__lm1; 1414 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1415 } 1416 __p.__get_begin()->__next_ = __x.__before_begin()->__next_; 1417 __x.__before_begin()->__next_ = nullptr; 1418 } 1419} 1420 1421template <class _Tp, class _Alloc> 1422void 1423forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1424 forward_list& __x, 1425 const_iterator __i) 1426{ 1427 const_iterator __lm1 = _VSTD::next(__i); 1428 if (__p != __i && __p != __lm1) 1429 { 1430 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_; 1431 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1432 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer(); 1433 } 1434} 1435 1436template <class _Tp, class _Alloc> 1437void 1438forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1439 forward_list& __x, 1440 const_iterator __f, const_iterator __l) 1441{ 1442 if (__f != __l && __p != __f) 1443 { 1444 const_iterator __lm1 = __f; 1445 while (__lm1.__get_begin()->__next_ != __l.__get_begin()) 1446 ++__lm1; 1447 if (__f != __lm1) 1448 { 1449 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1450 __p.__get_begin()->__next_ = __f.__get_begin()->__next_; 1451 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer(); 1452 } 1453 } 1454} 1455 1456#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1457 1458template <class _Tp, class _Alloc> 1459inline _LIBCPP_INLINE_VISIBILITY 1460void 1461forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1462 forward_list&& __x) 1463{ 1464 splice_after(__p, __x); 1465} 1466 1467template <class _Tp, class _Alloc> 1468inline _LIBCPP_INLINE_VISIBILITY 1469void 1470forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1471 forward_list&& __x, 1472 const_iterator __i) 1473{ 1474 splice_after(__p, __x, __i); 1475} 1476 1477template <class _Tp, class _Alloc> 1478inline _LIBCPP_INLINE_VISIBILITY 1479void 1480forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1481 forward_list&& __x, 1482 const_iterator __f, const_iterator __l) 1483{ 1484 splice_after(__p, __x, __f, __l); 1485} 1486 1487#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1488 1489template <class _Tp, class _Alloc> 1490void 1491forward_list<_Tp, _Alloc>::remove(const value_type& __v) 1492{ 1493 forward_list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing 1494 iterator __e = end(); 1495 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) 1496 { 1497 if (__i.__get_begin()->__next_->__value_ == __v) 1498 { 1499 iterator __j = _VSTD::next(__i, 2); 1500 for (; __j != __e && *__j == __v; ++__j) 1501 ; 1502 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1503 if (__j == __e) 1504 break; 1505 __i = __j; 1506 } 1507 else 1508 ++__i; 1509 } 1510} 1511 1512template <class _Tp, class _Alloc> 1513template <class _Predicate> 1514void 1515forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) 1516{ 1517 iterator __e = end(); 1518 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) 1519 { 1520 if (__pred(__i.__get_begin()->__next_->__value_)) 1521 { 1522 iterator __j = _VSTD::next(__i, 2); 1523 for (; __j != __e && __pred(*__j); ++__j) 1524 ; 1525 erase_after(__i, __j); 1526 if (__j == __e) 1527 break; 1528 __i = __j; 1529 } 1530 else 1531 ++__i; 1532 } 1533} 1534 1535template <class _Tp, class _Alloc> 1536template <class _BinaryPredicate> 1537void 1538forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) 1539{ 1540 for (iterator __i = begin(), __e = end(); __i != __e;) 1541 { 1542 iterator __j = _VSTD::next(__i); 1543 for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 1544 ; 1545 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer()) 1546 erase_after(__i, __j); 1547 __i = __j; 1548 } 1549} 1550 1551template <class _Tp, class _Alloc> 1552template <class _Compare> 1553void 1554forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) 1555{ 1556 if (this != &__x) 1557 { 1558 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, 1559 __x.__before_begin()->__next_, 1560 __comp); 1561 __x.__before_begin()->__next_ = nullptr; 1562 } 1563} 1564 1565template <class _Tp, class _Alloc> 1566template <class _Compare> 1567typename forward_list<_Tp, _Alloc>::__node_pointer 1568forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, 1569 _Compare& __comp) 1570{ 1571 if (__f1 == nullptr) 1572 return __f2; 1573 if (__f2 == nullptr) 1574 return __f1; 1575 __node_pointer __r; 1576 if (__comp(__f2->__value_, __f1->__value_)) 1577 { 1578 __node_pointer __t = __f2; 1579 while (__t->__next_ != nullptr && 1580 __comp(__t->__next_->__value_, __f1->__value_)) 1581 __t = __t->__next_; 1582 __r = __f2; 1583 __f2 = __t->__next_; 1584 __t->__next_ = __f1; 1585 } 1586 else 1587 __r = __f1; 1588 __node_pointer __p = __f1; 1589 __f1 = __f1->__next_; 1590 while (__f1 != nullptr && __f2 != nullptr) 1591 { 1592 if (__comp(__f2->__value_, __f1->__value_)) 1593 { 1594 __node_pointer __t = __f2; 1595 while (__t->__next_ != nullptr && 1596 __comp(__t->__next_->__value_, __f1->__value_)) 1597 __t = __t->__next_; 1598 __p->__next_ = __f2; 1599 __f2 = __t->__next_; 1600 __t->__next_ = __f1; 1601 } 1602 __p = __f1; 1603 __f1 = __f1->__next_; 1604 } 1605 if (__f2 != nullptr) 1606 __p->__next_ = __f2; 1607 return __r; 1608} 1609 1610template <class _Tp, class _Alloc> 1611template <class _Compare> 1612inline 1613void 1614forward_list<_Tp, _Alloc>::sort(_Compare __comp) 1615{ 1616 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, 1617 _VSTD::distance(begin(), end()), __comp); 1618} 1619 1620template <class _Tp, class _Alloc> 1621template <class _Compare> 1622typename forward_list<_Tp, _Alloc>::__node_pointer 1623forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, 1624 _Compare& __comp) 1625{ 1626 switch (__sz) 1627 { 1628 case 0: 1629 case 1: 1630 return __f1; 1631 case 2: 1632 if (__comp(__f1->__next_->__value_, __f1->__value_)) 1633 { 1634 __node_pointer __t = __f1->__next_; 1635 __t->__next_ = __f1; 1636 __f1->__next_ = nullptr; 1637 __f1 = __t; 1638 } 1639 return __f1; 1640 } 1641 difference_type __sz1 = __sz / 2; 1642 difference_type __sz2 = __sz - __sz1; 1643 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer(); 1644 __node_pointer __f2 = __t->__next_; 1645 __t->__next_ = nullptr; 1646 return __merge(__sort(__f1, __sz1, __comp), 1647 __sort(__f2, __sz2, __comp), __comp); 1648} 1649 1650template <class _Tp, class _Alloc> 1651void 1652forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT 1653{ 1654 __node_pointer __p = base::__before_begin()->__next_; 1655 if (__p != nullptr) 1656 { 1657 __node_pointer __f = __p->__next_; 1658 __p->__next_ = nullptr; 1659 while (__f != nullptr) 1660 { 1661 __node_pointer __t = __f->__next_; 1662 __f->__next_ = __p; 1663 __p = __f; 1664 __f = __t; 1665 } 1666 base::__before_begin()->__next_ = __p; 1667 } 1668} 1669 1670template <class _Tp, class _Alloc> 1671bool operator==(const forward_list<_Tp, _Alloc>& __x, 1672 const forward_list<_Tp, _Alloc>& __y) 1673{ 1674 typedef forward_list<_Tp, _Alloc> _Cp; 1675 typedef typename _Cp::const_iterator _Ip; 1676 _Ip __ix = __x.begin(); 1677 _Ip __ex = __x.end(); 1678 _Ip __iy = __y.begin(); 1679 _Ip __ey = __y.end(); 1680 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) 1681 if (!(*__ix == *__iy)) 1682 return false; 1683 return (__ix == __ex) == (__iy == __ey); 1684} 1685 1686template <class _Tp, class _Alloc> 1687inline _LIBCPP_INLINE_VISIBILITY 1688bool operator!=(const forward_list<_Tp, _Alloc>& __x, 1689 const forward_list<_Tp, _Alloc>& __y) 1690{ 1691 return !(__x == __y); 1692} 1693 1694template <class _Tp, class _Alloc> 1695inline _LIBCPP_INLINE_VISIBILITY 1696bool operator< (const forward_list<_Tp, _Alloc>& __x, 1697 const forward_list<_Tp, _Alloc>& __y) 1698{ 1699 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), 1700 __y.begin(), __y.end()); 1701} 1702 1703template <class _Tp, class _Alloc> 1704inline _LIBCPP_INLINE_VISIBILITY 1705bool operator> (const forward_list<_Tp, _Alloc>& __x, 1706 const forward_list<_Tp, _Alloc>& __y) 1707{ 1708 return __y < __x; 1709} 1710 1711template <class _Tp, class _Alloc> 1712inline _LIBCPP_INLINE_VISIBILITY 1713bool operator>=(const forward_list<_Tp, _Alloc>& __x, 1714 const forward_list<_Tp, _Alloc>& __y) 1715{ 1716 return !(__x < __y); 1717} 1718 1719template <class _Tp, class _Alloc> 1720inline _LIBCPP_INLINE_VISIBILITY 1721bool operator<=(const forward_list<_Tp, _Alloc>& __x, 1722 const forward_list<_Tp, _Alloc>& __y) 1723{ 1724 return !(__y < __x); 1725} 1726 1727template <class _Tp, class _Alloc> 1728inline _LIBCPP_INLINE_VISIBILITY 1729void 1730swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) 1731 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1732{ 1733 __x.swap(__y); 1734} 1735 1736_LIBCPP_END_NAMESPACE_STD 1737 1738#endif // _LIBCPP_FORWARD_LIST 1739