1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP___CXX03_FORWARD_LIST 11#define _LIBCPP___CXX03_FORWARD_LIST 12 13/* 14 forward_list synopsis 15 16namespace std 17{ 18 19template <class T, class Allocator = allocator<T>> 20class forward_list 21{ 22public: 23 typedef T value_type; 24 typedef Allocator allocator_type; 25 26 typedef value_type& reference; 27 typedef const value_type& const_reference; 28 typedef typename allocator_traits<allocator_type>::pointer pointer; 29 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 30 typedef typename allocator_traits<allocator_type>::size_type size_type; 31 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 32 33 typedef <details> iterator; 34 typedef <details> const_iterator; 35 36 forward_list() 37 noexcept(is_nothrow_default_constructible<allocator_type>::value); 38 explicit forward_list(const allocator_type& a); 39 explicit forward_list(size_type n); 40 explicit forward_list(size_type n, const allocator_type& a); // C++14 41 forward_list(size_type n, const value_type& v); 42 forward_list(size_type n, const value_type& v, const allocator_type& a); 43 template <class InputIterator> 44 forward_list(InputIterator first, InputIterator last); 45 template <class InputIterator> 46 forward_list(InputIterator first, InputIterator last, const allocator_type& a); 47 template<container-compatible-range<T> R> 48 forward_list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 49 forward_list(const forward_list& x); 50 forward_list(const forward_list& x, const allocator_type& a); 51 forward_list(forward_list&& x) 52 noexcept(is_nothrow_move_constructible<allocator_type>::value); 53 forward_list(forward_list&& x, const allocator_type& a); 54 forward_list(initializer_list<value_type> il); 55 forward_list(initializer_list<value_type> il, const allocator_type& a); 56 57 ~forward_list(); 58 59 forward_list& operator=(const forward_list& x); 60 forward_list& operator=(forward_list&& x) 61 noexcept( 62 allocator_type::propagate_on_container_move_assignment::value && 63 is_nothrow_move_assignable<allocator_type>::value); 64 forward_list& operator=(initializer_list<value_type> il); 65 66 template <class InputIterator> 67 void assign(InputIterator first, InputIterator last); 68 template<container-compatible-range<T> R> 69 void assign_range(R&& rg); // C++23 70 void assign(size_type n, const value_type& v); 71 void assign(initializer_list<value_type> il); 72 73 allocator_type get_allocator() const noexcept; 74 75 iterator begin() noexcept; 76 const_iterator begin() const noexcept; 77 iterator end() noexcept; 78 const_iterator end() const noexcept; 79 80 const_iterator cbegin() const noexcept; 81 const_iterator cend() const noexcept; 82 83 iterator before_begin() noexcept; 84 const_iterator before_begin() const noexcept; 85 const_iterator cbefore_begin() const noexcept; 86 87 bool empty() const noexcept; 88 size_type max_size() const noexcept; 89 90 reference front(); 91 const_reference front() const; 92 93 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17 94 void push_front(const value_type& v); 95 void push_front(value_type&& v); 96 template<container-compatible-range<T> R> 97 void prepend_range(R&& rg); // C++23 98 99 void pop_front(); 100 101 template <class... Args> 102 iterator emplace_after(const_iterator p, Args&&... args); 103 iterator insert_after(const_iterator p, const value_type& v); 104 iterator insert_after(const_iterator p, value_type&& v); 105 iterator insert_after(const_iterator p, size_type n, const value_type& v); 106 template <class InputIterator> 107 iterator insert_after(const_iterator p, 108 InputIterator first, InputIterator last); 109 template<container-compatible-range<T> R> 110 iterator insert_range_after(const_iterator position, R&& rg); // C++23 111 iterator insert_after(const_iterator p, initializer_list<value_type> il); 112 113 iterator erase_after(const_iterator p); 114 iterator erase_after(const_iterator first, const_iterator last); 115 116 void swap(forward_list& x) 117 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 118 119 void resize(size_type n); 120 void resize(size_type n, const value_type& v); 121 void clear() noexcept; 122 123 void splice_after(const_iterator p, forward_list& x); 124 void splice_after(const_iterator p, forward_list&& x); 125 void splice_after(const_iterator p, forward_list& x, const_iterator i); 126 void splice_after(const_iterator p, forward_list&& x, const_iterator i); 127 void splice_after(const_iterator p, forward_list& x, 128 const_iterator first, const_iterator last); 129 void splice_after(const_iterator p, forward_list&& x, 130 const_iterator first, const_iterator last); 131 size_type remove(const value_type& v); // void before C++20 132 template <class Predicate> 133 size_type remove_if(Predicate pred); // void before C++20 134 size_type unique(); // void before C++20 135 template <class BinaryPredicate> 136 size_type unique(BinaryPredicate binary_pred); // void before C++20 137 void merge(forward_list& x); 138 void merge(forward_list&& x); 139 template <class Compare> void merge(forward_list& x, Compare comp); 140 template <class Compare> void merge(forward_list&& x, Compare comp); 141 void sort(); 142 template <class Compare> void sort(Compare comp); 143 void reverse() noexcept; 144}; 145 146 147template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 148 forward_list(InputIterator, InputIterator, Allocator = Allocator()) 149 -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17 150 151template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> 152 forward_list(from_range_t, R&&, Allocator = Allocator()) 153 -> forward_list<ranges::range_value_t<R>, Allocator>; // C++23 154 155template <class T, class Allocator> 156 bool operator==(const forward_list<T, Allocator>& x, 157 const forward_list<T, Allocator>& y); 158 159template <class T, class Allocator> 160 bool operator< (const forward_list<T, Allocator>& x, 161 const forward_list<T, Allocator>& y); // removed in C++20 162 163template <class T, class Allocator> 164 bool operator!=(const forward_list<T, Allocator>& x, 165 const forward_list<T, Allocator>& y); // removed in C++20 166 167template <class T, class Allocator> 168 bool operator> (const forward_list<T, Allocator>& x, 169 const forward_list<T, Allocator>& y); // removed in C++20 170 171template <class T, class Allocator> 172 bool operator>=(const forward_list<T, Allocator>& x, 173 const forward_list<T, Allocator>& y); // removed in C++20 174 175template <class T, class Allocator> 176 bool operator<=(const forward_list<T, Allocator>& x, 177 const forward_list<T, Allocator>& y); // removed in C++20 178 179template<class T, class Allocator> 180 synth-three-way-result<T> operator<=>(const forward_list<T, Allocator>& x, 181 const forward_list<T, Allocator>& y); // since C++20 182 183template <class T, class Allocator> 184 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y) 185 noexcept(noexcept(x.swap(y))); 186 187template <class T, class Allocator, class U> 188 typename forward_list<T, Allocator>::size_type 189 erase(forward_list<T, Allocator>& c, const U& value); // C++20 190template <class T, class Allocator, class Predicate> 191 typename forward_list<T, Allocator>::size_type 192 erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20 193 194} // std 195 196*/ 197 198#include <__cxx03/__algorithm/comp.h> 199#include <__cxx03/__algorithm/lexicographical_compare.h> 200#include <__cxx03/__algorithm/min.h> 201#include <__cxx03/__config> 202#include <__cxx03/__iterator/distance.h> 203#include <__cxx03/__iterator/iterator_traits.h> 204#include <__cxx03/__iterator/move_iterator.h> 205#include <__cxx03/__iterator/next.h> 206#include <__cxx03/__memory/addressof.h> 207#include <__cxx03/__memory/allocation_guard.h> 208#include <__cxx03/__memory/allocator.h> 209#include <__cxx03/__memory/allocator_traits.h> 210#include <__cxx03/__memory/compressed_pair.h> 211#include <__cxx03/__memory/construct_at.h> 212#include <__cxx03/__memory/pointer_traits.h> 213#include <__cxx03/__memory/swap_allocator.h> 214#include <__cxx03/__type_traits/conditional.h> 215#include <__cxx03/__type_traits/is_allocator.h> 216#include <__cxx03/__type_traits/is_const.h> 217#include <__cxx03/__type_traits/is_nothrow_assignable.h> 218#include <__cxx03/__type_traits/is_nothrow_constructible.h> 219#include <__cxx03/__type_traits/is_pointer.h> 220#include <__cxx03/__type_traits/is_same.h> 221#include <__cxx03/__type_traits/is_swappable.h> 222#include <__cxx03/__type_traits/type_identity.h> 223#include <__cxx03/__utility/forward.h> 224#include <__cxx03/__utility/move.h> 225#include <__cxx03/limits> 226#include <__cxx03/new> // __launder 227#include <__cxx03/version> 228 229// standard-mandated includes 230 231// [iterator.range] 232#include <__cxx03/__iterator/access.h> 233 234#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 235# pragma GCC system_header 236#endif 237 238_LIBCPP_PUSH_MACROS 239#include <__cxx03/__undef_macros> 240 241_LIBCPP_BEGIN_NAMESPACE_STD 242 243template <class _Tp, class _VoidPtr> 244struct __forward_list_node; 245template <class _NodePtr> 246struct __forward_begin_node; 247 248template <class> 249struct __forward_list_node_value_type; 250 251template <class _Tp, class _VoidPtr> 252struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > { 253 typedef _Tp type; 254}; 255 256template <class _NodePtr> 257struct __forward_node_traits { 258 typedef __remove_cv_t<typename pointer_traits<_NodePtr>::element_type> __node_type; 259 typedef typename __forward_list_node_value_type<__node_type>::type __node_value_type; 260 typedef _NodePtr __node_pointer; 261 typedef __forward_begin_node<_NodePtr> __begin_node; 262 typedef __rebind_pointer_t<_NodePtr, __begin_node> __begin_node_pointer; 263 typedef __rebind_pointer_t<_NodePtr, void> __void_pointer; 264 265#if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB) 266 typedef __begin_node_pointer __iter_node_pointer; 267#else 268 typedef __conditional_t<is_pointer<__void_pointer>::value, __begin_node_pointer, __node_pointer> __iter_node_pointer; 269#endif 270 271 typedef __conditional_t<is_same<__iter_node_pointer, __node_pointer>::value, __begin_node_pointer, __node_pointer> 272 __non_iter_node_pointer; 273 274 _LIBCPP_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) { return __p; } 275 _LIBCPP_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) { 276 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p)); 277 } 278}; 279 280template <class _NodePtr> 281struct __forward_begin_node { 282 typedef _NodePtr pointer; 283 typedef __rebind_pointer_t<_NodePtr, __forward_begin_node> __begin_node_pointer; 284 285 pointer __next_; 286 287 _LIBCPP_HIDE_FROM_ABI __forward_begin_node() : __next_(nullptr) {} 288 _LIBCPP_HIDE_FROM_ABI explicit __forward_begin_node(pointer __n) : __next_(__n) {} 289 290 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __next_as_begin() const { 291 return static_cast<__begin_node_pointer>(__next_); 292 } 293}; 294 295template <class _Tp, class _VoidPtr> 296using __begin_node_of = __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >; 297 298template <class _Tp, class _VoidPtr> 299struct __forward_list_node : public __begin_node_of<_Tp, _VoidPtr> { 300 typedef _Tp value_type; 301 typedef __begin_node_of<_Tp, _VoidPtr> _Base; 302 typedef typename _Base::pointer _NodePtr; 303 304 // We allow starting the lifetime of nodes without initializing the value held by the node, 305 // since that is handled by the list itself in order to be allocator-aware. 306 307private: 308 _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)]; 309 310public: 311 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); } 312 313 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_node(_NodePtr __next) : _Base(__next) {} 314 _LIBCPP_HIDE_FROM_ABI ~__forward_list_node() {} 315}; 316 317template <class _Tp, class _Alloc = allocator<_Tp> > 318class _LIBCPP_TEMPLATE_VIS forward_list; 319template <class _NodeConstPtr> 320class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator; 321 322template <class _NodePtr> 323class _LIBCPP_TEMPLATE_VIS __forward_list_iterator { 324 typedef __forward_node_traits<_NodePtr> __traits; 325 typedef typename __traits::__node_pointer __node_pointer; 326 typedef typename __traits::__begin_node_pointer __begin_node_pointer; 327 typedef typename __traits::__iter_node_pointer __iter_node_pointer; 328 typedef typename __traits::__void_pointer __void_pointer; 329 330 __iter_node_pointer __ptr_; 331 332 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const { 333 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_)); 334 } 335 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const { 336 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_)); 337 } 338 339 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {} 340 341 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT 342 : __ptr_(__traits::__as_iter_node(__p)) {} 343 344 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT 345 : __ptr_(__traits::__as_iter_node(__p)) {} 346 347 template <class, class> 348 friend class _LIBCPP_TEMPLATE_VIS forward_list; 349 template <class> 350 friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator; 351 352public: 353 typedef forward_iterator_tag iterator_category; 354 typedef typename __traits::__node_value_type value_type; 355 typedef value_type& reference; 356 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 357 typedef __rebind_pointer_t<__node_pointer, value_type> pointer; 358 359 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {} 360 361 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); } 362 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { 363 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value()); 364 } 365 366 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator& operator++() { 367 __ptr_ = __traits::__as_iter_node(__ptr_->__next_); 368 return *this; 369 } 370 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator operator++(int) { 371 __forward_list_iterator __t(*this); 372 ++(*this); 373 return __t; 374 } 375 376 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __forward_list_iterator& __x, const __forward_list_iterator& __y) { 377 return __x.__ptr_ == __y.__ptr_; 378 } 379 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __forward_list_iterator& __x, const __forward_list_iterator& __y) { 380 return !(__x == __y); 381 } 382}; 383 384template <class _NodeConstPtr> 385class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator { 386 static_assert(!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value, ""); 387 typedef _NodeConstPtr _NodePtr; 388 389 typedef __forward_node_traits<_NodePtr> __traits; 390 typedef typename __traits::__node_type __node_type; 391 typedef typename __traits::__node_pointer __node_pointer; 392 typedef typename __traits::__begin_node_pointer __begin_node_pointer; 393 typedef typename __traits::__iter_node_pointer __iter_node_pointer; 394 typedef typename __traits::__void_pointer __void_pointer; 395 396 __iter_node_pointer __ptr_; 397 398 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const { 399 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_)); 400 } 401 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const { 402 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_)); 403 } 404 405 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {} 406 407 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT 408 : __ptr_(__traits::__as_iter_node(__p)) {} 409 410 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT 411 : __ptr_(__traits::__as_iter_node(__p)) {} 412 413 template <class, class> 414 friend class forward_list; 415 416public: 417 typedef forward_iterator_tag iterator_category; 418 typedef typename __traits::__node_value_type value_type; 419 typedef const value_type& reference; 420 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 421 typedef __rebind_pointer_t<__node_pointer, const value_type> pointer; 422 423 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {} 424 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT 425 : __ptr_(__p.__ptr_) {} 426 427 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); } 428 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { 429 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value()); 430 } 431 432 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator& operator++() { 433 __ptr_ = __traits::__as_iter_node(__ptr_->__next_); 434 return *this; 435 } 436 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator operator++(int) { 437 __forward_list_const_iterator __t(*this); 438 ++(*this); 439 return __t; 440 } 441 442 friend _LIBCPP_HIDE_FROM_ABI bool 443 operator==(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) { 444 return __x.__ptr_ == __y.__ptr_; 445 } 446 friend _LIBCPP_HIDE_FROM_ABI bool 447 operator!=(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) { 448 return !(__x == __y); 449 } 450}; 451 452template <class _Tp, class _Alloc> 453class __forward_list_base { 454protected: 455 typedef _Tp value_type; 456 typedef _Alloc allocator_type; 457 458 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer; 459 typedef __forward_list_node<value_type, void_pointer> __node_type; 460 typedef __begin_node_of<value_type, void_pointer> __begin_node; 461 typedef __rebind_alloc<allocator_traits<allocator_type>, __node_type> __node_allocator; 462 typedef allocator_traits<__node_allocator> __node_traits; 463 typedef typename __node_traits::pointer __node_pointer; 464 465 typedef __rebind_alloc<allocator_traits<allocator_type>, __begin_node> __begin_node_allocator; 466 typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer; 467 468 __compressed_pair<__begin_node, __node_allocator> __before_begin_; 469 470 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() _NOEXCEPT { 471 return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first()); 472 } 473 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() const _NOEXCEPT { 474 return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first())); 475 } 476 477 _LIBCPP_HIDE_FROM_ABI __node_allocator& __alloc() _NOEXCEPT { return __before_begin_.second(); } 478 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __alloc() const _NOEXCEPT { return __before_begin_.second(); } 479 480 typedef __forward_list_iterator<__node_pointer> iterator; 481 typedef __forward_list_const_iterator<__node_pointer> const_iterator; 482 483 _LIBCPP_HIDE_FROM_ABI __forward_list_base() : __before_begin_(__begin_node(), __default_init_tag()) {} 484 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const allocator_type& __a) 485 : __before_begin_(__begin_node(), __node_allocator(__a)) {} 486 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const __node_allocator& __a) 487 : __before_begin_(__begin_node(), __a) {} 488 489public: 490 __forward_list_base(const __forward_list_base&) = delete; 491 __forward_list_base& operator=(const __forward_list_base&) = delete; 492 493 _LIBCPP_HIDE_FROM_ABI ~__forward_list_base(); 494 495protected: 496 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x) { 497 __copy_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>()); 498 } 499 500 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x) { 501 __move_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); 502 } 503 504 template <class... _Args> 505 _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__node_pointer __next, _Args&&... __args) { 506 __node_allocator& __a = __alloc(); 507 __allocation_guard<__node_allocator> __guard(__a, 1); 508 // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value 509 // held inside the node, since we need to use the allocator's construct() method for that. 510 // 511 // We don't use the allocator's construct() method to construct the node itself since the 512 // Cpp17FooInsertable named requirements don't require the allocator's construct() method 513 // to work on anything other than the value_type. 514 std::__construct_at(std::addressof(*__guard.__get()), __next); 515 516 // Now construct the value_type using the allocator's construct() method. 517 __node_traits::construct(__a, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...); 518 return __guard.__release_ptr(); 519 } 520 521 _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) { 522 // For the same reason as above, we use the allocator's destroy() method for the value_type, 523 // but not for the node itself. 524 __node_allocator& __a = __alloc(); 525 __node_traits::destroy(__a, std::addressof(__node->__get_value())); 526 std::__destroy_at(std::addressof(*__node)); 527 __node_traits::deallocate(__a, __node, 1); 528 } 529 530public: 531 _LIBCPP_HIDE_FROM_ABI void swap(__forward_list_base& __x); 532 533protected: 534 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT; 535 536private: 537 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base&, false_type) {} 538 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x, true_type) { 539 if (__alloc() != __x.__alloc()) 540 clear(); 541 __alloc() = __x.__alloc(); 542 } 543 544 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT {} 545 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x, true_type) { 546 __alloc() = std::move(__x.__alloc()); 547 } 548}; 549 550template <class _Tp, class _Alloc> 551__forward_list_base<_Tp, _Alloc>::~__forward_list_base() { 552 clear(); 553} 554 555template <class _Tp, class _Alloc> 556inline void __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x) { 557 std::__swap_allocator( 558 __alloc(), __x.__alloc(), integral_constant<bool, __node_traits::propagate_on_container_swap::value>()); 559 using std::swap; 560 swap(__before_begin()->__next_, __x.__before_begin()->__next_); 561} 562 563template <class _Tp, class _Alloc> 564void __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT { 565 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) { 566 __node_pointer __next = __p->__next_; 567 __delete_node(__p); 568 __p = __next; 569 } 570 __before_begin()->__next_ = nullptr; 571} 572 573template <class _Tp, class _Alloc /*= allocator<_Tp>*/> 574class _LIBCPP_TEMPLATE_VIS forward_list : private __forward_list_base<_Tp, _Alloc> { 575 typedef __forward_list_base<_Tp, _Alloc> base; 576 typedef typename base::__node_allocator __node_allocator; 577 typedef typename base::__node_type __node_type; 578 typedef typename base::__node_traits __node_traits; 579 typedef typename base::__node_pointer __node_pointer; 580 typedef typename base::__begin_node_pointer __begin_node_pointer; 581 582public: 583 typedef _Tp value_type; 584 typedef _Alloc allocator_type; 585 586 static_assert(__check_valid_allocator<allocator_type>::value, ""); 587 588 static_assert(is_same<value_type, typename allocator_type::value_type>::value, 589 "Allocator::value_type must be same type as value_type"); 590 591 static_assert(!is_same<allocator_type, __node_allocator>::value, 592 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks"); 593 594 typedef value_type& reference; 595 typedef const value_type& const_reference; 596 typedef typename allocator_traits<allocator_type>::pointer pointer; 597 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 598 typedef typename allocator_traits<allocator_type>::size_type size_type; 599 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 600 601 typedef typename base::iterator iterator; 602 typedef typename base::const_iterator const_iterator; 603 typedef void __remove_return_type; 604 605 _LIBCPP_HIDE_FROM_ABI forward_list() {} // = default; 606 _LIBCPP_HIDE_FROM_ABI explicit forward_list(const allocator_type& __a); 607 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n); 608 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v); 609 610 template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0> 611 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : base(__a) { 612 insert_after(cbefore_begin(), __n, __v); 613 } 614 615 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0> 616 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l); 617 618 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0> 619 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a); 620 621 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x); 622 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a); 623 624 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(const forward_list& __x); 625 626 // ~forward_list() = default; 627 628 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0> 629 void _LIBCPP_HIDE_FROM_ABI assign(_InputIterator __f, _InputIterator __l); 630 631 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v); 632 633 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(base::__alloc()); } 634 635 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(base::__before_begin()->__next_); } 636 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { 637 return const_iterator(base::__before_begin()->__next_); 638 } 639 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(nullptr); } 640 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(nullptr); } 641 642 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { 643 return const_iterator(base::__before_begin()->__next_); 644 } 645 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return const_iterator(nullptr); } 646 647 _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT { return iterator(base::__before_begin()); } 648 _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT { return const_iterator(base::__before_begin()); } 649 _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT { 650 return const_iterator(base::__before_begin()); 651 } 652 653 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { 654 return base::__before_begin()->__next_ == nullptr; 655 } 656 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { 657 return std::min<size_type>(__node_traits::max_size(base::__alloc()), numeric_limits<difference_type>::max()); 658 } 659 660 _LIBCPP_HIDE_FROM_ABI reference front() { return base::__before_begin()->__next_->__get_value(); } 661 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return base::__before_begin()->__next_->__get_value(); } 662 663 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v); 664 665 _LIBCPP_HIDE_FROM_ABI void pop_front(); 666 667 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, const value_type& __v); 668 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, size_type __n, const value_type& __v); 669 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0> 670 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); 671 672 template <class _InputIterator, class _Sentinel> 673 _LIBCPP_HIDE_FROM_ABI iterator __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l); 674 675 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p); 676 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l); 677 678 _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x) { base::swap(__x); } 679 680 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n); 681 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v); 682 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); } 683 684 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x); 685 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); 686 _LIBCPP_HIDE_FROM_ABI void 687 splice_after(const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l); 688 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x); 689 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); 690 _LIBCPP_HIDE_FROM_ABI void 691 splice_after(const_iterator __p, forward_list& __x, const_iterator __f, const_iterator __l); 692 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __v); 693 template <class _Predicate> 694 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Predicate __pred); 695 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); } 696 template <class _BinaryPredicate> 697 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred); 698 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x) { merge(__x, __less<>()); } 699 template <class _Compare> 700 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp); 701 _LIBCPP_HIDE_FROM_ABI void sort() { sort(__less<>()); } 702 template <class _Compare> 703 _LIBCPP_HIDE_FROM_ABI void sort(_Compare __comp); 704 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT; 705 706private: 707 template <class _Iter, class _Sent> 708 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iter __f, _Sent __l); 709 710 template <class _Compare> 711 static _LIBCPP_HIDE_FROM_ABI __node_pointer __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp); 712 713 // TODO: Make this _LIBCPP_HIDE_FROM_ABI 714 template <class _Compare> 715 static _LIBCPP_HIDDEN __node_pointer __sort(__node_pointer __f, difference_type __sz, _Compare& __comp); 716}; 717 718template <class _Tp, class _Alloc> 719inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : base(__a) {} 720 721template <class _Tp, class _Alloc> 722forward_list<_Tp, _Alloc>::forward_list(size_type __n) { 723 if (__n > 0) { 724 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) { 725 __p->__next_ = this->__create_node(/* next = */ nullptr); 726 } 727 } 728} 729 730template <class _Tp, class _Alloc> 731forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) { 732 insert_after(cbefore_begin(), __n, __v); 733} 734 735template <class _Tp, class _Alloc> 736template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> > 737forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) { 738 insert_after(cbefore_begin(), __f, __l); 739} 740 741template <class _Tp, class _Alloc> 742template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> > 743forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a) : base(__a) { 744 insert_after(cbefore_begin(), __f, __l); 745} 746 747template <class _Tp, class _Alloc> 748forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) 749 : base(__node_traits::select_on_container_copy_construction(__x.__alloc())) { 750 insert_after(cbefore_begin(), __x.begin(), __x.end()); 751} 752 753template <class _Tp, class _Alloc> 754forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a) 755 : base(__a) { 756 insert_after(cbefore_begin(), __x.begin(), __x.end()); 757} 758 759template <class _Tp, class _Alloc> 760forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) { 761 if (this != std::addressof(__x)) { 762 base::__copy_assign_alloc(__x); 763 assign(__x.begin(), __x.end()); 764 } 765 return *this; 766} 767 768template <class _Tp, class _Alloc> 769template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> > 770void forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) { 771 __assign_with_sentinel(__f, __l); 772} 773 774template <class _Tp, class _Alloc> 775template <class _Iter, class _Sent> 776_LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::__assign_with_sentinel(_Iter __f, _Sent __l) { 777 iterator __i = before_begin(); 778 iterator __j = std::next(__i); 779 iterator __e = end(); 780 for (; __j != __e && __f != __l; ++__i, (void)++__j, ++__f) 781 *__j = *__f; 782 if (__j == __e) 783 __insert_after_with_sentinel(__i, std::move(__f), std::move(__l)); 784 else 785 erase_after(__i, __e); 786} 787 788template <class _Tp, class _Alloc> 789void forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) { 790 iterator __i = before_begin(); 791 iterator __j = std::next(__i); 792 iterator __e = end(); 793 for (; __j != __e && __n > 0; --__n, ++__i, ++__j) 794 *__j = __v; 795 if (__j == __e) 796 insert_after(__i, __n, __v); 797 else 798 erase_after(__i, __e); 799} 800 801template <class _Tp, class _Alloc> 802void forward_list<_Tp, _Alloc>::push_front(const value_type& __v) { 803 base::__before_begin()->__next_ = this->__create_node(/* next = */ base::__before_begin()->__next_, __v); 804} 805 806template <class _Tp, class _Alloc> 807void forward_list<_Tp, _Alloc>::pop_front() { 808 __node_pointer __p = base::__before_begin()->__next_; 809 base::__before_begin()->__next_ = __p->__next_; 810 this->__delete_node(__p); 811} 812 813template <class _Tp, class _Alloc> 814typename forward_list<_Tp, _Alloc>::iterator 815forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) { 816 __begin_node_pointer const __r = __p.__get_begin(); 817 __r->__next_ = this->__create_node(/* next = */ __r->__next_, __v); 818 return iterator(__r->__next_); 819} 820 821template <class _Tp, class _Alloc> 822typename forward_list<_Tp, _Alloc>::iterator 823forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, const value_type& __v) { 824 __begin_node_pointer __r = __p.__get_begin(); 825 if (__n > 0) { 826 __node_pointer __first = this->__create_node(/* next = */ nullptr, __v); 827 __node_pointer __last = __first; 828#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 829 try { 830#endif // _LIBCPP_HAS_NO_EXCEPTIONS 831 for (--__n; __n != 0; --__n, __last = __last->__next_) { 832 __last->__next_ = this->__create_node(/* next = */ nullptr, __v); 833 } 834#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 835 } catch (...) { 836 while (__first != nullptr) { 837 __node_pointer __next = __first->__next_; 838 this->__delete_node(__first); 839 __first = __next; 840 } 841 throw; 842 } 843#endif // _LIBCPP_HAS_NO_EXCEPTIONS 844 __last->__next_ = __r->__next_; 845 __r->__next_ = __first; 846 __r = static_cast<__begin_node_pointer>(__last); 847 } 848 return iterator(__r); 849} 850 851template <class _Tp, class _Alloc> 852template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> > 853typename forward_list<_Tp, _Alloc>::iterator 854forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l) { 855 return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l)); 856} 857 858template <class _Tp, class _Alloc> 859template <class _InputIterator, class _Sentinel> 860_LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Alloc>::iterator 861forward_list<_Tp, _Alloc>::__insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) { 862 __begin_node_pointer __r = __p.__get_begin(); 863 864 if (__f != __l) { 865 __node_pointer __first = this->__create_node(/* next = */ nullptr, *__f); 866 __node_pointer __last = __first; 867 868#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 869 try { 870#endif // _LIBCPP_HAS_NO_EXCEPTIONS 871 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) { 872 __last->__next_ = this->__create_node(/* next = */ nullptr, *__f); 873 } 874#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 875 } catch (...) { 876 while (__first != nullptr) { 877 __node_pointer __next = __first->__next_; 878 this->__delete_node(__first); 879 __first = __next; 880 } 881 throw; 882 } 883#endif // _LIBCPP_HAS_NO_EXCEPTIONS 884 885 __last->__next_ = __r->__next_; 886 __r->__next_ = __first; 887 __r = static_cast<__begin_node_pointer>(__last); 888 } 889 890 return iterator(__r); 891} 892 893template <class _Tp, class _Alloc> 894typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) { 895 __begin_node_pointer __p = __f.__get_begin(); 896 __node_pointer __n = __p->__next_; 897 __p->__next_ = __n->__next_; 898 this->__delete_node(__n); 899 return iterator(__p->__next_); 900} 901 902template <class _Tp, class _Alloc> 903typename forward_list<_Tp, _Alloc>::iterator 904forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) { 905 __node_pointer __e = __l.__get_unsafe_node_pointer(); 906 if (__f != __l) { 907 __begin_node_pointer __bp = __f.__get_begin(); 908 909 __node_pointer __n = __bp->__next_; 910 if (__n != __e) { 911 __bp->__next_ = __e; 912 do { 913 __node_pointer __tmp = __n->__next_; 914 this->__delete_node(__n); 915 __n = __tmp; 916 } while (__n != __e); 917 } 918 } 919 return iterator(__e); 920} 921 922template <class _Tp, class _Alloc> 923void forward_list<_Tp, _Alloc>::resize(size_type __n) { 924 size_type __sz = 0; 925 iterator __p = before_begin(); 926 iterator __i = begin(); 927 iterator __e = end(); 928 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 929 ; 930 if (__i != __e) 931 erase_after(__p, __e); 932 else { 933 __n -= __sz; 934 if (__n > 0) { 935 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) { 936 __ptr->__next_ = this->__create_node(/* next = */ nullptr); 937 } 938 } 939 } 940} 941 942template <class _Tp, class _Alloc> 943void forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) { 944 size_type __sz = 0; 945 iterator __p = before_begin(); 946 iterator __i = begin(); 947 iterator __e = end(); 948 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz) 949 ; 950 if (__i != __e) 951 erase_after(__p, __e); 952 else { 953 __n -= __sz; 954 if (__n > 0) { 955 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) { 956 __ptr->__next_ = this->__create_node(/* next = */ nullptr, __v); 957 } 958 } 959 } 960} 961 962template <class _Tp, class _Alloc> 963void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& __x) { 964 if (!__x.empty()) { 965 if (__p.__get_begin()->__next_ != nullptr) { 966 const_iterator __lm1 = __x.before_begin(); 967 while (__lm1.__get_begin()->__next_ != nullptr) 968 ++__lm1; 969 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 970 } 971 __p.__get_begin()->__next_ = __x.__before_begin()->__next_; 972 __x.__before_begin()->__next_ = nullptr; 973 } 974} 975 976template <class _Tp, class _Alloc> 977void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& /*__other*/, const_iterator __i) { 978 const_iterator __lm1 = std::next(__i); 979 if (__p != __i && __p != __lm1) { 980 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_; 981 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 982 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer(); 983 } 984} 985 986template <class _Tp, class _Alloc> 987void forward_list<_Tp, _Alloc>::splice_after( 988 const_iterator __p, forward_list& /*__other*/, const_iterator __f, const_iterator __l) { 989 if (__f != __l && __p != __f) { 990 const_iterator __lm1 = __f; 991 while (__lm1.__get_begin()->__next_ != __l.__get_begin()) 992 ++__lm1; 993 if (__f != __lm1) { 994 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_; 995 __p.__get_begin()->__next_ = __f.__get_begin()->__next_; 996 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer(); 997 } 998 } 999} 1000 1001template <class _Tp, class _Alloc> 1002inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x) { 1003 splice_after(__p, __x); 1004} 1005 1006template <class _Tp, class _Alloc> 1007inline _LIBCPP_HIDE_FROM_ABI void 1008forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x, const_iterator __i) { 1009 splice_after(__p, __x, __i); 1010} 1011 1012template <class _Tp, class _Alloc> 1013inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after( 1014 const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l) { 1015 splice_after(__p, __x, __f, __l); 1016} 1017 1018template <class _Tp, class _Alloc> 1019typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove(const value_type& __v) { 1020 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1021 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; 1022 const iterator __e = end(); 1023 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) { 1024 if (__i.__get_begin()->__next_->__get_value() == __v) { 1025 ++__count_removed; 1026 iterator __j = std::next(__i, 2); 1027 for (; __j != __e && *__j == __v; ++__j) 1028 ++__count_removed; 1029 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1030 if (__j == __e) 1031 break; 1032 __i = __j; 1033 } else 1034 ++__i; 1035 } 1036 1037 return (__remove_return_type)__count_removed; 1038} 1039 1040template <class _Tp, class _Alloc> 1041template <class _Predicate> 1042typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) { 1043 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1044 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; 1045 const iterator __e = end(); 1046 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) { 1047 if (__pred(__i.__get_begin()->__next_->__get_value())) { 1048 ++__count_removed; 1049 iterator __j = std::next(__i, 2); 1050 for (; __j != __e && __pred(*__j); ++__j) 1051 ++__count_removed; 1052 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1053 if (__j == __e) 1054 break; 1055 __i = __j; 1056 } else 1057 ++__i; 1058 } 1059 1060 return (__remove_return_type)__count_removed; 1061} 1062 1063template <class _Tp, class _Alloc> 1064template <class _BinaryPredicate> 1065typename forward_list<_Tp, _Alloc>::__remove_return_type 1066forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) { 1067 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing 1068 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; 1069 for (iterator __i = begin(), __e = end(); __i != __e;) { 1070 iterator __j = std::next(__i); 1071 for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 1072 ++__count_removed; 1073 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer()) 1074 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); 1075 __i = __j; 1076 } 1077 1078 return (__remove_return_type)__count_removed; 1079} 1080 1081template <class _Tp, class _Alloc> 1082template <class _Compare> 1083void forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) { 1084 if (this != std::addressof(__x)) { 1085 base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, __x.__before_begin()->__next_, __comp); 1086 __x.__before_begin()->__next_ = nullptr; 1087 } 1088} 1089 1090template <class _Tp, class _Alloc> 1091template <class _Compare> 1092typename forward_list<_Tp, _Alloc>::__node_pointer 1093forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp) { 1094 if (__f1 == nullptr) 1095 return __f2; 1096 if (__f2 == nullptr) 1097 return __f1; 1098 __node_pointer __r; 1099 if (__comp(__f2->__get_value(), __f1->__get_value())) { 1100 __node_pointer __t = __f2; 1101 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value())) 1102 __t = __t->__next_; 1103 __r = __f2; 1104 __f2 = __t->__next_; 1105 __t->__next_ = __f1; 1106 } else 1107 __r = __f1; 1108 __node_pointer __p = __f1; 1109 __f1 = __f1->__next_; 1110 while (__f1 != nullptr && __f2 != nullptr) { 1111 if (__comp(__f2->__get_value(), __f1->__get_value())) { 1112 __node_pointer __t = __f2; 1113 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value())) 1114 __t = __t->__next_; 1115 __p->__next_ = __f2; 1116 __f2 = __t->__next_; 1117 __t->__next_ = __f1; 1118 } 1119 __p = __f1; 1120 __f1 = __f1->__next_; 1121 } 1122 if (__f2 != nullptr) 1123 __p->__next_ = __f2; 1124 return __r; 1125} 1126 1127template <class _Tp, class _Alloc> 1128template <class _Compare> 1129inline void forward_list<_Tp, _Alloc>::sort(_Compare __comp) { 1130 base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, std::distance(begin(), end()), __comp); 1131} 1132 1133template <class _Tp, class _Alloc> 1134template <class _Compare> 1135typename forward_list<_Tp, _Alloc>::__node_pointer 1136forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, _Compare& __comp) { 1137 switch (__sz) { 1138 case 0: 1139 case 1: 1140 return __f1; 1141 case 2: 1142 if (__comp(__f1->__next_->__get_value(), __f1->__get_value())) { 1143 __node_pointer __t = __f1->__next_; 1144 __t->__next_ = __f1; 1145 __f1->__next_ = nullptr; 1146 __f1 = __t; 1147 } 1148 return __f1; 1149 } 1150 difference_type __sz1 = __sz / 2; 1151 difference_type __sz2 = __sz - __sz1; 1152 __node_pointer __t = std::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer(); 1153 __node_pointer __f2 = __t->__next_; 1154 __t->__next_ = nullptr; 1155 return __merge(__sort(__f1, __sz1, __comp), __sort(__f2, __sz2, __comp), __comp); 1156} 1157 1158template <class _Tp, class _Alloc> 1159void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT { 1160 __node_pointer __p = base::__before_begin()->__next_; 1161 if (__p != nullptr) { 1162 __node_pointer __f = __p->__next_; 1163 __p->__next_ = nullptr; 1164 while (__f != nullptr) { 1165 __node_pointer __t = __f->__next_; 1166 __f->__next_ = __p; 1167 __p = __f; 1168 __f = __t; 1169 } 1170 base::__before_begin()->__next_ = __p; 1171 } 1172} 1173 1174template <class _Tp, class _Alloc> 1175_LIBCPP_HIDE_FROM_ABI bool operator==(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { 1176 typedef forward_list<_Tp, _Alloc> _Cp; 1177 typedef typename _Cp::const_iterator _Ip; 1178 _Ip __ix = __x.begin(); 1179 _Ip __ex = __x.end(); 1180 _Ip __iy = __y.begin(); 1181 _Ip __ey = __y.end(); 1182 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy) 1183 if (!(*__ix == *__iy)) 1184 return false; 1185 return (__ix == __ex) == (__iy == __ey); 1186} 1187 1188template <class _Tp, class _Alloc> 1189inline _LIBCPP_HIDE_FROM_ABI bool 1190operator!=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { 1191 return !(__x == __y); 1192} 1193 1194template <class _Tp, class _Alloc> 1195inline _LIBCPP_HIDE_FROM_ABI bool 1196operator<(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { 1197 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1198} 1199 1200template <class _Tp, class _Alloc> 1201inline _LIBCPP_HIDE_FROM_ABI bool 1202operator>(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { 1203 return __y < __x; 1204} 1205 1206template <class _Tp, class _Alloc> 1207inline _LIBCPP_HIDE_FROM_ABI bool 1208operator>=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { 1209 return !(__x < __y); 1210} 1211 1212template <class _Tp, class _Alloc> 1213inline _LIBCPP_HIDE_FROM_ABI bool 1214operator<=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) { 1215 return !(__y < __x); 1216} 1217 1218template <class _Tp, class _Alloc> 1219inline _LIBCPP_HIDE_FROM_ABI void swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) { 1220 __x.swap(__y); 1221} 1222 1223_LIBCPP_END_NAMESPACE_STD 1224 1225_LIBCPP_POP_MACROS 1226 1227#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) 1228# include <__cxx03/algorithm> 1229# include <__cxx03/atomic> 1230# include <__cxx03/cstdint> 1231# include <__cxx03/cstdlib> 1232# include <__cxx03/cstring> 1233# include <__cxx03/functional> 1234# include <__cxx03/iosfwd> 1235# include <__cxx03/iterator> 1236# include <__cxx03/stdexcept> 1237# include <__cxx03/type_traits> 1238# include <__cxx03/typeinfo> 1239#endif 1240 1241#endif // _LIBCPP___CXX03_FORWARD_LIST 1242