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