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_CXX03_LANG 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_CXX03_LANG 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_CXX03_LANG 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_CXX03_LANG 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 660 forward_list& operator=(const forward_list& __x); 661 662#ifndef _LIBCPP_CXX03_LANG 663 _LIBCPP_INLINE_VISIBILITY 664 forward_list(forward_list&& __x) 665 _NOEXCEPT_(is_nothrow_move_constructible<base>::value) 666 : base(_VSTD::move(__x)) {} 667 forward_list(forward_list&& __x, const allocator_type& __a); 668 669 forward_list(initializer_list<value_type> __il); 670 forward_list(initializer_list<value_type> __il, const allocator_type& __a); 671 672 _LIBCPP_INLINE_VISIBILITY 673 forward_list& operator=(forward_list&& __x) 674 _NOEXCEPT_( 675 __node_traits::propagate_on_container_move_assignment::value && 676 is_nothrow_move_assignable<allocator_type>::value); 677 678 _LIBCPP_INLINE_VISIBILITY 679 forward_list& operator=(initializer_list<value_type> __il); 680 681 _LIBCPP_INLINE_VISIBILITY 682 void assign(initializer_list<value_type> __il); 683#endif // _LIBCPP_CXX03_LANG 684 685 // ~forward_list() = default; 686 687 template <class _InputIterator> 688 typename enable_if 689 < 690 __is_input_iterator<_InputIterator>::value, 691 void 692 >::type 693 assign(_InputIterator __f, _InputIterator __l); 694 void assign(size_type __n, const value_type& __v); 695 696 _LIBCPP_INLINE_VISIBILITY 697 allocator_type get_allocator() const _NOEXCEPT 698 {return allocator_type(base::__alloc());} 699 700 _LIBCPP_INLINE_VISIBILITY 701 iterator begin() _NOEXCEPT 702 {return iterator(base::__before_begin()->__next_);} 703 _LIBCPP_INLINE_VISIBILITY 704 const_iterator begin() const _NOEXCEPT 705 {return const_iterator(base::__before_begin()->__next_);} 706 _LIBCPP_INLINE_VISIBILITY 707 iterator end() _NOEXCEPT 708 {return iterator(nullptr);} 709 _LIBCPP_INLINE_VISIBILITY 710 const_iterator end() const _NOEXCEPT 711 {return const_iterator(nullptr);} 712 713 _LIBCPP_INLINE_VISIBILITY 714 const_iterator cbegin() const _NOEXCEPT 715 {return const_iterator(base::__before_begin()->__next_);} 716 _LIBCPP_INLINE_VISIBILITY 717 const_iterator cend() const _NOEXCEPT 718 {return const_iterator(nullptr);} 719 720 _LIBCPP_INLINE_VISIBILITY 721 iterator before_begin() _NOEXCEPT 722 {return iterator(base::__before_begin());} 723 _LIBCPP_INLINE_VISIBILITY 724 const_iterator before_begin() const _NOEXCEPT 725 {return const_iterator(base::__before_begin());} 726 _LIBCPP_INLINE_VISIBILITY 727 const_iterator cbefore_begin() const _NOEXCEPT 728 {return const_iterator(base::__before_begin());} 729 730 _LIBCPP_INLINE_VISIBILITY 731 bool empty() const _NOEXCEPT 732 {return base::__before_begin()->__next_ == nullptr;} 733 _LIBCPP_INLINE_VISIBILITY 734 size_type max_size() const _NOEXCEPT { 735 return std::min<size_type>( 736 __node_traits::max_size(base::__alloc()), 737 numeric_limits<difference_type>::max()); 738 } 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_CXX03_LANG 746#if _LIBCPP_STD_VER > 14 747 template <class... _Args> reference emplace_front(_Args&&... __args); 748#else 749 template <class... _Args> void emplace_front(_Args&&... __args); 750#endif 751 void push_front(value_type&& __v); 752#endif // _LIBCPP_CXX03_LANG 753 void push_front(const value_type& __v); 754 755 void pop_front(); 756 757#ifndef _LIBCPP_CXX03_LANG 758 template <class... _Args> 759 iterator emplace_after(const_iterator __p, _Args&&... __args); 760 761 iterator insert_after(const_iterator __p, value_type&& __v); 762 iterator insert_after(const_iterator __p, initializer_list<value_type> __il) 763 {return insert_after(__p, __il.begin(), __il.end());} 764#endif // _LIBCPP_CXX03_LANG 765 iterator insert_after(const_iterator __p, const value_type& __v); 766 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 767 template <class _InputIterator> 768 _LIBCPP_INLINE_VISIBILITY 769 typename enable_if 770 < 771 __is_input_iterator<_InputIterator>::value, 772 iterator 773 >::type 774 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 775 776 iterator erase_after(const_iterator __p); 777 iterator erase_after(const_iterator __f, const_iterator __l); 778 779 _LIBCPP_INLINE_VISIBILITY 780 void swap(forward_list& __x) 781#if _LIBCPP_STD_VER >= 14 782 _NOEXCEPT 783#else 784 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || 785 __is_nothrow_swappable<__node_allocator>::value) 786#endif 787 {base::swap(__x);} 788 789 void resize(size_type __n); 790 void resize(size_type __n, const value_type& __v); 791 _LIBCPP_INLINE_VISIBILITY 792 void clear() _NOEXCEPT {base::clear();} 793 794#ifndef _LIBCPP_CXX03_LANG 795 _LIBCPP_INLINE_VISIBILITY 796 void splice_after(const_iterator __p, forward_list&& __x); 797 _LIBCPP_INLINE_VISIBILITY 798 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 799 _LIBCPP_INLINE_VISIBILITY 800 void splice_after(const_iterator __p, forward_list&& __x, 801 const_iterator __f, const_iterator __l); 802#endif // _LIBCPP_CXX03_LANG 803 void splice_after(const_iterator __p, forward_list& __x); 804 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 805 void splice_after(const_iterator __p, forward_list& __x, 806 const_iterator __f, const_iterator __l); 807 void remove(const value_type& __v); 808 template <class _Predicate> void remove_if(_Predicate __pred); 809 _LIBCPP_INLINE_VISIBILITY 810 void unique() {unique(__equal_to<value_type>());} 811 template <class _BinaryPredicate> void unique(_BinaryPredicate __binary_pred); 812#ifndef _LIBCPP_CXX03_LANG 813 _LIBCPP_INLINE_VISIBILITY 814 void merge(forward_list&& __x) {merge(__x, __less<value_type>());} 815 template <class _Compare> 816 _LIBCPP_INLINE_VISIBILITY 817 void merge(forward_list&& __x, _Compare __comp) 818 {merge(__x, _VSTD::move(__comp));} 819#endif // _LIBCPP_CXX03_LANG 820 _LIBCPP_INLINE_VISIBILITY 821 void merge(forward_list& __x) {merge(__x, __less<value_type>());} 822 template <class _Compare> void merge(forward_list& __x, _Compare __comp); 823 _LIBCPP_INLINE_VISIBILITY 824 void sort() {sort(__less<value_type>());} 825 template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp); 826 void reverse() _NOEXCEPT; 827 828private: 829 830#ifndef _LIBCPP_CXX03_LANG 831 void __move_assign(forward_list& __x, true_type) 832 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 833 void __move_assign(forward_list& __x, false_type); 834#endif // _LIBCPP_CXX03_LANG 835 836 template <class _Compare> 837 static 838 __node_pointer 839 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 840 841 template <class _Compare> 842 static 843 __node_pointer 844 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 845}; 846 847template <class _Tp, class _Alloc> 848inline 849forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) 850 : base(__a) 851{ 852} 853 854template <class _Tp, class _Alloc> 855forward_list<_Tp, _Alloc>::forward_list(size_type __n) 856{ 857 if (__n > 0) 858 { 859 __node_allocator& __a = base::__alloc(); 860 typedef __allocator_destructor<__node_allocator> _Dp; 861 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 862 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, 863 __p = __p->__next_as_begin()) 864 { 865 __h.reset(__node_traits::allocate(__a, 1)); 866 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 867 __h->__next_ = nullptr; 868 __p->__next_ = __h.release(); 869 } 870 } 871} 872 873#if _LIBCPP_STD_VER > 11 874template <class _Tp, class _Alloc> 875forward_list<_Tp, _Alloc>::forward_list(size_type __n, 876 const allocator_type& __base_alloc) 877 : base ( __base_alloc ) 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 950template <class _Tp, class _Alloc> 951forward_list<_Tp, _Alloc>& 952forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) 953{ 954 if (this != &__x) 955 { 956 base::__copy_assign_alloc(__x); 957 assign(__x.begin(), __x.end()); 958 } 959 return *this; 960} 961 962#ifndef _LIBCPP_CXX03_LANG 963template <class _Tp, class _Alloc> 964forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, 965 const allocator_type& __a) 966 : base(_VSTD::move(__x), __a) 967{ 968 if (base::__alloc() != __x.__alloc()) 969 { 970 typedef move_iterator<iterator> _Ip; 971 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end())); 972 } 973} 974 975template <class _Tp, class _Alloc> 976forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) 977{ 978 insert_after(cbefore_begin(), __il.begin(), __il.end()); 979} 980 981template <class _Tp, class _Alloc> 982forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, 983 const allocator_type& __a) 984 : base(__a) 985{ 986 insert_after(cbefore_begin(), __il.begin(), __il.end()); 987} 988 989template <class _Tp, class _Alloc> 990void 991forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type) 992 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 993{ 994 clear(); 995 base::__move_assign_alloc(__x); 996 base::__before_begin()->__next_ = __x.__before_begin()->__next_; 997 __x.__before_begin()->__next_ = nullptr; 998} 999 1000template <class _Tp, class _Alloc> 1001void 1002forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) 1003{ 1004 if (base::__alloc() == __x.__alloc()) 1005 __move_assign(__x, true_type()); 1006 else 1007 { 1008 typedef move_iterator<iterator> _Ip; 1009 assign(_Ip(__x.begin()), _Ip(__x.end())); 1010 } 1011} 1012 1013template <class _Tp, class _Alloc> 1014inline 1015forward_list<_Tp, _Alloc>& 1016forward_list<_Tp, _Alloc>::operator=(forward_list&& __x) 1017 _NOEXCEPT_( 1018 __node_traits::propagate_on_container_move_assignment::value && 1019 is_nothrow_move_assignable<allocator_type>::value) 1020{ 1021 __move_assign(__x, integral_constant<bool, 1022 __node_traits::propagate_on_container_move_assignment::value>()); 1023 return *this; 1024} 1025 1026template <class _Tp, class _Alloc> 1027inline 1028forward_list<_Tp, _Alloc>& 1029forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) 1030{ 1031 assign(__il.begin(), __il.end()); 1032 return *this; 1033} 1034 1035#endif // _LIBCPP_CXX03_LANG 1036 1037template <class _Tp, class _Alloc> 1038template <class _InputIterator> 1039typename enable_if 1040< 1041 __is_input_iterator<_InputIterator>::value, 1042 void 1043>::type 1044forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) 1045{ 1046 iterator __i = before_begin(); 1047 iterator __j = _VSTD::next(__i); 1048 iterator __e = end(); 1049 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f) 1050 *__j = *__f; 1051 if (__j == __e) 1052 insert_after(__i, __f, __l); 1053 else 1054 erase_after(__i, __e); 1055} 1056 1057template <class _Tp, class _Alloc> 1058void 1059forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) 1060{ 1061 iterator __i = before_begin(); 1062 iterator __j = _VSTD::next(__i); 1063 iterator __e = end(); 1064 for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 1065 *__j = __v; 1066 if (__j == __e) 1067 insert_after(__i, __n, __v); 1068 else 1069 erase_after(__i, __e); 1070} 1071 1072#ifndef _LIBCPP_CXX03_LANG 1073 1074template <class _Tp, class _Alloc> 1075inline 1076void 1077forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) 1078{ 1079 assign(__il.begin(), __il.end()); 1080} 1081 1082template <class _Tp, class _Alloc> 1083template <class... _Args> 1084#if _LIBCPP_STD_VER > 14 1085typename forward_list<_Tp, _Alloc>::reference 1086#else 1087void 1088#endif 1089forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1090{ 1091 __node_allocator& __a = base::__alloc(); 1092 typedef __allocator_destructor<__node_allocator> _Dp; 1093 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1094 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1095 _VSTD::forward<_Args>(__args)...); 1096 __h->__next_ = base::__before_begin()->__next_; 1097 base::__before_begin()->__next_ = __h.release(); 1098#if _LIBCPP_STD_VER > 14 1099 return base::__before_begin()->__next_->__value_; 1100#endif 1101} 1102 1103template <class _Tp, class _Alloc> 1104void 1105forward_list<_Tp, _Alloc>::push_front(value_type&& __v) 1106{ 1107 __node_allocator& __a = base::__alloc(); 1108 typedef __allocator_destructor<__node_allocator> _Dp; 1109 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1110 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1111 __h->__next_ = base::__before_begin()->__next_; 1112 base::__before_begin()->__next_ = __h.release(); 1113} 1114 1115#endif // _LIBCPP_CXX03_LANG 1116 1117template <class _Tp, class _Alloc> 1118void 1119forward_list<_Tp, _Alloc>::push_front(const value_type& __v) 1120{ 1121 __node_allocator& __a = base::__alloc(); 1122 typedef __allocator_destructor<__node_allocator> _Dp; 1123 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1124 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1125 __h->__next_ = base::__before_begin()->__next_; 1126 base::__before_begin()->__next_ = __h.release(); 1127} 1128 1129template <class _Tp, class _Alloc> 1130void 1131forward_list<_Tp, _Alloc>::pop_front() 1132{ 1133 __node_allocator& __a = base::__alloc(); 1134 __node_pointer __p = base::__before_begin()->__next_; 1135 base::__before_begin()->__next_ = __p->__next_; 1136 __node_traits::destroy(__a, _VSTD::addressof(__p->__value_)); 1137 __node_traits::deallocate(__a, __p, 1); 1138} 1139 1140#ifndef _LIBCPP_CXX03_LANG 1141 1142template <class _Tp, class _Alloc> 1143template <class... _Args> 1144typename forward_list<_Tp, _Alloc>::iterator 1145forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) 1146{ 1147 __begin_node_pointer const __r = __p.__get_begin(); 1148 __node_allocator& __a = base::__alloc(); 1149 typedef __allocator_destructor<__node_allocator> _Dp; 1150 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1151 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), 1152 _VSTD::forward<_Args>(__args)...); 1153 __h->__next_ = __r->__next_; 1154 __r->__next_ = __h.release(); 1155 return iterator(__r->__next_); 1156} 1157 1158template <class _Tp, class _Alloc> 1159typename forward_list<_Tp, _Alloc>::iterator 1160forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) 1161{ 1162 __begin_node_pointer const __r = __p.__get_begin(); 1163 __node_allocator& __a = base::__alloc(); 1164 typedef __allocator_destructor<__node_allocator> _Dp; 1165 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1166 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1167 __h->__next_ = __r->__next_; 1168 __r->__next_ = __h.release(); 1169 return iterator(__r->__next_); 1170} 1171 1172#endif // _LIBCPP_CXX03_LANG 1173 1174template <class _Tp, class _Alloc> 1175typename forward_list<_Tp, _Alloc>::iterator 1176forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const 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_), __v); 1183 __h->__next_ = __r->__next_; 1184 __r->__next_ = __h.release(); 1185 return iterator(__r->__next_); 1186} 1187 1188template <class _Tp, class _Alloc> 1189typename forward_list<_Tp, _Alloc>::iterator 1190forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, 1191 const value_type& __v) 1192{ 1193 __begin_node_pointer __r = __p.__get_begin(); 1194 if (__n > 0) 1195 { 1196 __node_allocator& __a = base::__alloc(); 1197 typedef __allocator_destructor<__node_allocator> _Dp; 1198 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1199 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1200 __node_pointer __first = __h.release(); 1201 __node_pointer __last = __first; 1202#ifndef _LIBCPP_NO_EXCEPTIONS 1203 try 1204 { 1205#endif // _LIBCPP_NO_EXCEPTIONS 1206 for (--__n; __n != 0; --__n, __last = __last->__next_) 1207 { 1208 __h.reset(__node_traits::allocate(__a, 1)); 1209 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1210 __last->__next_ = __h.release(); 1211 } 1212#ifndef _LIBCPP_NO_EXCEPTIONS 1213 } 1214 catch (...) 1215 { 1216 while (__first != nullptr) 1217 { 1218 __node_pointer __next = __first->__next_; 1219 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1220 __node_traits::deallocate(__a, __first, 1); 1221 __first = __next; 1222 } 1223 throw; 1224 } 1225#endif // _LIBCPP_NO_EXCEPTIONS 1226 __last->__next_ = __r->__next_; 1227 __r->__next_ = __first; 1228 __r = static_cast<__begin_node_pointer>(__last); 1229 } 1230 return iterator(__r); 1231} 1232 1233template <class _Tp, class _Alloc> 1234template <class _InputIterator> 1235typename enable_if 1236< 1237 __is_input_iterator<_InputIterator>::value, 1238 typename forward_list<_Tp, _Alloc>::iterator 1239>::type 1240forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, 1241 _InputIterator __f, _InputIterator __l) 1242{ 1243 __begin_node_pointer __r = __p.__get_begin(); 1244 if (__f != __l) 1245 { 1246 __node_allocator& __a = base::__alloc(); 1247 typedef __allocator_destructor<__node_allocator> _Dp; 1248 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1)); 1249 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1250 __node_pointer __first = __h.release(); 1251 __node_pointer __last = __first; 1252#ifndef _LIBCPP_NO_EXCEPTIONS 1253 try 1254 { 1255#endif // _LIBCPP_NO_EXCEPTIONS 1256 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) 1257 { 1258 __h.reset(__node_traits::allocate(__a, 1)); 1259 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f); 1260 __last->__next_ = __h.release(); 1261 } 1262#ifndef _LIBCPP_NO_EXCEPTIONS 1263 } 1264 catch (...) 1265 { 1266 while (__first != nullptr) 1267 { 1268 __node_pointer __next = __first->__next_; 1269 __node_traits::destroy(__a, _VSTD::addressof(__first->__value_)); 1270 __node_traits::deallocate(__a, __first, 1); 1271 __first = __next; 1272 } 1273 throw; 1274 } 1275#endif // _LIBCPP_NO_EXCEPTIONS 1276 __last->__next_ = __r->__next_; 1277 __r->__next_ = __first; 1278 __r = static_cast<__begin_node_pointer>(__last); 1279 } 1280 return iterator(__r); 1281} 1282 1283template <class _Tp, class _Alloc> 1284typename forward_list<_Tp, _Alloc>::iterator 1285forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) 1286{ 1287 __begin_node_pointer __p = __f.__get_begin(); 1288 __node_pointer __n = __p->__next_; 1289 __p->__next_ = __n->__next_; 1290 __node_allocator& __a = base::__alloc(); 1291 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1292 __node_traits::deallocate(__a, __n, 1); 1293 return iterator(__p->__next_); 1294} 1295 1296template <class _Tp, class _Alloc> 1297typename forward_list<_Tp, _Alloc>::iterator 1298forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) 1299{ 1300 __node_pointer __e = __l.__get_unsafe_node_pointer(); 1301 if (__f != __l) 1302 { 1303 __begin_node_pointer __bp = __f.__get_begin(); 1304 1305 __node_pointer __n = __bp->__next_; 1306 if (__n != __e) 1307 { 1308 __bp->__next_ = __e; 1309 __node_allocator& __a = base::__alloc(); 1310 do 1311 { 1312 __node_pointer __tmp = __n->__next_; 1313 __node_traits::destroy(__a, _VSTD::addressof(__n->__value_)); 1314 __node_traits::deallocate(__a, __n, 1); 1315 __n = __tmp; 1316 } while (__n != __e); 1317 } 1318 } 1319 return iterator(__e); 1320} 1321 1322template <class _Tp, class _Alloc> 1323void 1324forward_list<_Tp, _Alloc>::resize(size_type __n) 1325{ 1326 size_type __sz = 0; 1327 iterator __p = before_begin(); 1328 iterator __i = begin(); 1329 iterator __e = end(); 1330 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1331 ; 1332 if (__i != __e) 1333 erase_after(__p, __e); 1334 else 1335 { 1336 __n -= __sz; 1337 if (__n > 0) 1338 { 1339 __node_allocator& __a = base::__alloc(); 1340 typedef __allocator_destructor<__node_allocator> _Dp; 1341 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1342 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, 1343 __ptr = __ptr->__next_as_begin()) 1344 { 1345 __h.reset(__node_traits::allocate(__a, 1)); 1346 __node_traits::construct(__a, _VSTD::addressof(__h->__value_)); 1347 __h->__next_ = nullptr; 1348 __ptr->__next_ = __h.release(); 1349 } 1350 } 1351 } 1352} 1353 1354template <class _Tp, class _Alloc> 1355void 1356forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) 1357{ 1358 size_type __sz = 0; 1359 iterator __p = before_begin(); 1360 iterator __i = begin(); 1361 iterator __e = end(); 1362 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 1363 ; 1364 if (__i != __e) 1365 erase_after(__p, __e); 1366 else 1367 { 1368 __n -= __sz; 1369 if (__n > 0) 1370 { 1371 __node_allocator& __a = base::__alloc(); 1372 typedef __allocator_destructor<__node_allocator> _Dp; 1373 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1)); 1374 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, 1375 __ptr = __ptr->__next_as_begin()) 1376 { 1377 __h.reset(__node_traits::allocate(__a, 1)); 1378 __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v); 1379 __h->__next_ = nullptr; 1380 __ptr->__next_ = __h.release(); 1381 } 1382 } 1383 } 1384} 1385 1386template <class _Tp, class _Alloc> 1387void 1388forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1389 forward_list& __x) 1390{ 1391 if (!__x.empty()) 1392 { 1393 if (__p.__get_begin()->__next_ != nullptr) 1394 { 1395 const_iterator __lm1 = __x.before_begin(); 1396 while (__lm1.__get_begin()->__next_ != nullptr) 1397 ++__lm1; 1398 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1399 } 1400 __p.__get_begin()->__next_ = __x.__before_begin()->__next_; 1401 __x.__before_begin()->__next_ = nullptr; 1402 } 1403} 1404 1405template <class _Tp, class _Alloc> 1406void 1407forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1408 forward_list& /*__other*/, 1409 const_iterator __i) 1410{ 1411 const_iterator __lm1 = _VSTD::next(__i); 1412 if (__p != __i && __p != __lm1) 1413 { 1414 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_; 1415 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1416 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer(); 1417 } 1418} 1419 1420template <class _Tp, class _Alloc> 1421void 1422forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1423 forward_list& /*__other*/, 1424 const_iterator __f, const_iterator __l) 1425{ 1426 if (__f != __l && __p != __f) 1427 { 1428 const_iterator __lm1 = __f; 1429 while (__lm1.__get_begin()->__next_ != __l.__get_begin()) 1430 ++__lm1; 1431 if (__f != __lm1) 1432 { 1433 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 1434 __p.__get_begin()->__next_ = __f.__get_begin()->__next_; 1435 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer(); 1436 } 1437 } 1438} 1439 1440#ifndef _LIBCPP_CXX03_LANG 1441 1442template <class _Tp, class _Alloc> 1443inline _LIBCPP_INLINE_VISIBILITY 1444void 1445forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1446 forward_list&& __x) 1447{ 1448 splice_after(__p, __x); 1449} 1450 1451template <class _Tp, class _Alloc> 1452inline _LIBCPP_INLINE_VISIBILITY 1453void 1454forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1455 forward_list&& __x, 1456 const_iterator __i) 1457{ 1458 splice_after(__p, __x, __i); 1459} 1460 1461template <class _Tp, class _Alloc> 1462inline _LIBCPP_INLINE_VISIBILITY 1463void 1464forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, 1465 forward_list&& __x, 1466 const_iterator __f, const_iterator __l) 1467{ 1468 splice_after(__p, __x, __f, __l); 1469} 1470 1471#endif // _LIBCPP_CXX03_LANG 1472 1473template <class _Tp, class _Alloc> 1474void 1475forward_list<_Tp, _Alloc>::remove(const value_type& __v) 1476{ 1477 forward_list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing 1478 iterator __e = end(); 1479 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) 1480 { 1481 if (__i.__get_begin()->__next_->__value_ == __v) 1482 { 1483 iterator __j = _VSTD::next(__i, 2); 1484 for (; __j != __e && *__j == __v; ++__j) 1485 ; 1486 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1487 if (__j == __e) 1488 break; 1489 __i = __j; 1490 } 1491 else 1492 ++__i; 1493 } 1494} 1495 1496template <class _Tp, class _Alloc> 1497template <class _Predicate> 1498void 1499forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) 1500{ 1501 iterator __e = end(); 1502 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) 1503 { 1504 if (__pred(__i.__get_begin()->__next_->__value_)) 1505 { 1506 iterator __j = _VSTD::next(__i, 2); 1507 for (; __j != __e && __pred(*__j); ++__j) 1508 ; 1509 erase_after(__i, __j); 1510 if (__j == __e) 1511 break; 1512 __i = __j; 1513 } 1514 else 1515 ++__i; 1516 } 1517} 1518 1519template <class _Tp, class _Alloc> 1520template <class _BinaryPredicate> 1521void 1522forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) 1523{ 1524 for (iterator __i = begin(), __e = end(); __i != __e;) 1525 { 1526 iterator __j = _VSTD::next(__i); 1527 for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 1528 ; 1529 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer()) 1530 erase_after(__i, __j); 1531 __i = __j; 1532 } 1533} 1534 1535template <class _Tp, class _Alloc> 1536template <class _Compare> 1537void 1538forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) 1539{ 1540 if (this != &__x) 1541 { 1542 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, 1543 __x.__before_begin()->__next_, 1544 __comp); 1545 __x.__before_begin()->__next_ = nullptr; 1546 } 1547} 1548 1549template <class _Tp, class _Alloc> 1550template <class _Compare> 1551typename forward_list<_Tp, _Alloc>::__node_pointer 1552forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, 1553 _Compare& __comp) 1554{ 1555 if (__f1 == nullptr) 1556 return __f2; 1557 if (__f2 == nullptr) 1558 return __f1; 1559 __node_pointer __r; 1560 if (__comp(__f2->__value_, __f1->__value_)) 1561 { 1562 __node_pointer __t = __f2; 1563 while (__t->__next_ != nullptr && 1564 __comp(__t->__next_->__value_, __f1->__value_)) 1565 __t = __t->__next_; 1566 __r = __f2; 1567 __f2 = __t->__next_; 1568 __t->__next_ = __f1; 1569 } 1570 else 1571 __r = __f1; 1572 __node_pointer __p = __f1; 1573 __f1 = __f1->__next_; 1574 while (__f1 != nullptr && __f2 != nullptr) 1575 { 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 __p->__next_ = __f2; 1583 __f2 = __t->__next_; 1584 __t->__next_ = __f1; 1585 } 1586 __p = __f1; 1587 __f1 = __f1->__next_; 1588 } 1589 if (__f2 != nullptr) 1590 __p->__next_ = __f2; 1591 return __r; 1592} 1593 1594template <class _Tp, class _Alloc> 1595template <class _Compare> 1596inline 1597void 1598forward_list<_Tp, _Alloc>::sort(_Compare __comp) 1599{ 1600 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, 1601 _VSTD::distance(begin(), end()), __comp); 1602} 1603 1604template <class _Tp, class _Alloc> 1605template <class _Compare> 1606typename forward_list<_Tp, _Alloc>::__node_pointer 1607forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, 1608 _Compare& __comp) 1609{ 1610 switch (__sz) 1611 { 1612 case 0: 1613 case 1: 1614 return __f1; 1615 case 2: 1616 if (__comp(__f1->__next_->__value_, __f1->__value_)) 1617 { 1618 __node_pointer __t = __f1->__next_; 1619 __t->__next_ = __f1; 1620 __f1->__next_ = nullptr; 1621 __f1 = __t; 1622 } 1623 return __f1; 1624 } 1625 difference_type __sz1 = __sz / 2; 1626 difference_type __sz2 = __sz - __sz1; 1627 __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer(); 1628 __node_pointer __f2 = __t->__next_; 1629 __t->__next_ = nullptr; 1630 return __merge(__sort(__f1, __sz1, __comp), 1631 __sort(__f2, __sz2, __comp), __comp); 1632} 1633 1634template <class _Tp, class _Alloc> 1635void 1636forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT 1637{ 1638 __node_pointer __p = base::__before_begin()->__next_; 1639 if (__p != nullptr) 1640 { 1641 __node_pointer __f = __p->__next_; 1642 __p->__next_ = nullptr; 1643 while (__f != nullptr) 1644 { 1645 __node_pointer __t = __f->__next_; 1646 __f->__next_ = __p; 1647 __p = __f; 1648 __f = __t; 1649 } 1650 base::__before_begin()->__next_ = __p; 1651 } 1652} 1653 1654template <class _Tp, class _Alloc> 1655bool operator==(const forward_list<_Tp, _Alloc>& __x, 1656 const forward_list<_Tp, _Alloc>& __y) 1657{ 1658 typedef forward_list<_Tp, _Alloc> _Cp; 1659 typedef typename _Cp::const_iterator _Ip; 1660 _Ip __ix = __x.begin(); 1661 _Ip __ex = __x.end(); 1662 _Ip __iy = __y.begin(); 1663 _Ip __ey = __y.end(); 1664 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) 1665 if (!(*__ix == *__iy)) 1666 return false; 1667 return (__ix == __ex) == (__iy == __ey); 1668} 1669 1670template <class _Tp, class _Alloc> 1671inline _LIBCPP_INLINE_VISIBILITY 1672bool operator!=(const forward_list<_Tp, _Alloc>& __x, 1673 const forward_list<_Tp, _Alloc>& __y) 1674{ 1675 return !(__x == __y); 1676} 1677 1678template <class _Tp, class _Alloc> 1679inline _LIBCPP_INLINE_VISIBILITY 1680bool operator< (const forward_list<_Tp, _Alloc>& __x, 1681 const forward_list<_Tp, _Alloc>& __y) 1682{ 1683 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), 1684 __y.begin(), __y.end()); 1685} 1686 1687template <class _Tp, class _Alloc> 1688inline _LIBCPP_INLINE_VISIBILITY 1689bool operator> (const forward_list<_Tp, _Alloc>& __x, 1690 const forward_list<_Tp, _Alloc>& __y) 1691{ 1692 return __y < __x; 1693} 1694 1695template <class _Tp, class _Alloc> 1696inline _LIBCPP_INLINE_VISIBILITY 1697bool operator>=(const forward_list<_Tp, _Alloc>& __x, 1698 const forward_list<_Tp, _Alloc>& __y) 1699{ 1700 return !(__x < __y); 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 1713void 1714swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) 1715 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1716{ 1717 __x.swap(__y); 1718} 1719 1720_LIBCPP_END_NAMESPACE_STD 1721 1722#endif // _LIBCPP_FORWARD_LIST 1723