codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===----------------------- forward_list ---------------------------------===//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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX_FORWARD_LIST11#define _LIBCUDACXX_FORWARD_LIST12 13/*14 forward_list synopsis15 16namespace std17{18 19template <class T, class Allocator = allocator<T>>20class forward_list21{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++1441 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 forward_list(const forward_list& x);48 forward_list(const forward_list& x, const allocator_type& a);49 forward_list(forward_list&& x)50 noexcept(is_nothrow_move_constructible<allocator_type>::value);51 forward_list(forward_list&& x, const allocator_type& a);52 forward_list(initializer_list<value_type> il);53 forward_list(initializer_list<value_type> il, const allocator_type& a);54 55 ~forward_list();56 57 forward_list& operator=(const forward_list& x);58 forward_list& operator=(forward_list&& x)59 noexcept(60 allocator_type::propagate_on_container_move_assignment::value &&61 is_nothrow_move_assignable<allocator_type>::value);62 forward_list& operator=(initializer_list<value_type> il);63 64 template <class InputIterator>65 void assign(InputIterator first, InputIterator last);66 void assign(size_type n, const value_type& v);67 void assign(initializer_list<value_type> il);68 69 allocator_type get_allocator() const noexcept;70 71 iterator begin() noexcept;72 const_iterator begin() const noexcept;73 iterator end() noexcept;74 const_iterator end() const noexcept;75 76 const_iterator cbegin() const noexcept;77 const_iterator cend() const noexcept;78 79 iterator before_begin() noexcept;80 const_iterator before_begin() const noexcept;81 const_iterator cbefore_begin() const noexcept;82 83 bool empty() const noexcept;84 size_type max_size() const noexcept;85 86 reference front();87 const_reference front() const;88 89 template <class... Args> reference emplace_front(Args&&... args); // reference in C++1790 void push_front(const value_type& v);91 void push_front(value_type&& v);92 93 void pop_front();94 95 template <class... Args>96 iterator emplace_after(const_iterator p, Args&&... args);97 iterator insert_after(const_iterator p, const value_type& v);98 iterator insert_after(const_iterator p, value_type&& v);99 iterator insert_after(const_iterator p, size_type n, const value_type& v);100 template <class InputIterator>101 iterator insert_after(const_iterator p,102 InputIterator first, InputIterator last);103 iterator insert_after(const_iterator p, initializer_list<value_type> il);104 105 iterator erase_after(const_iterator p);106 iterator erase_after(const_iterator first, const_iterator last);107 108 void swap(forward_list& x)109 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17110 111 void resize(size_type n);112 void resize(size_type n, const value_type& v);113 void clear() noexcept;114 115 void splice_after(const_iterator p, forward_list& x);116 void splice_after(const_iterator p, forward_list&& x);117 void splice_after(const_iterator p, forward_list& x, const_iterator i);118 void splice_after(const_iterator p, forward_list&& x, const_iterator i);119 void splice_after(const_iterator p, forward_list& x,120 const_iterator first, const_iterator last);121 void splice_after(const_iterator p, forward_list&& x,122 const_iterator first, const_iterator last);123 size_type remove(const value_type& v); // void before C++20124 template <class Predicate>125 size_type remove_if(Predicate pred); // void before C++20126 size_type unique(); // void before C++20127 template <class BinaryPredicate>128 size_type unique(BinaryPredicate binary_pred); // void before C++20129 void merge(forward_list& x);130 void merge(forward_list&& x);131 template <class Compare> void merge(forward_list& x, Compare comp);132 template <class Compare> void merge(forward_list&& x, Compare comp);133 void sort();134 template <class Compare> void sort(Compare comp);135 void reverse() noexcept;136};137 138 139template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>140 forward_list(InputIterator, InputIterator, Allocator = Allocator())141 -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17142 143template <class T, class Allocator>144 bool operator==(const forward_list<T, Allocator>& x,145 const forward_list<T, Allocator>& y);146 147template <class T, class Allocator>148 bool operator< (const forward_list<T, Allocator>& x,149 const forward_list<T, Allocator>& y);150 151template <class T, class Allocator>152 bool operator!=(const forward_list<T, Allocator>& x,153 const forward_list<T, Allocator>& y);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);162 163template <class T, class Allocator>164 bool operator<=(const forward_list<T, Allocator>& x,165 const forward_list<T, Allocator>& y);166 167template <class T, class Allocator>168 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)169 noexcept(noexcept(x.swap(y)));170 171template <class T, class Allocator, class U>172 void erase(forward_list<T, Allocator>& c, const U& value); // C++20173template <class T, class Allocator, class Predicate>174 void erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20175 176} // std177 178*/179 180#include <__config>181#include <initializer_list>182#include <memory>183#include <limits>184#include <iterator>185#include <algorithm>186#include <version>187 188#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)189# pragma GCC system_header190#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)191# pragma clang system_header192#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)193# pragma system_header194#endif // no system header195 196_LIBCUDACXX_PUSH_MACROS197#include <__undef_macros>198 199 200_LIBCUDACXX_BEGIN_NAMESPACE_STD201 202template <class _Tp, class _VoidPtr> struct __forward_list_node;203template <class _NodePtr> struct __forward_begin_node;204 205 206template <class>207struct __forward_list_node_value_type;208 209template <class _Tp, class _VoidPtr>210struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {211 typedef _Tp type;212};213 214template <class _NodePtr>215struct __forward_node_traits {216 217 typedef typename remove_cv<218 typename pointer_traits<_NodePtr>::element_type>::type __node;219 typedef typename __forward_list_node_value_type<__node>::type __node_value_type;220 typedef _NodePtr __node_pointer;221 typedef __forward_begin_node<_NodePtr> __begin_node;222 typedef typename __rebind_pointer<_NodePtr, __begin_node>::type223 __begin_node_pointer;224 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;225 226#if defined(_LIBCUDACXX_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)227 typedef __begin_node_pointer __iter_node_pointer;228#else229 typedef typename conditional<230 is_pointer<__void_pointer>::value,231 __begin_node_pointer,232 __node_pointer233 >::type __iter_node_pointer;234#endif235 236 typedef typename conditional<237 is_same<__iter_node_pointer, __node_pointer>::value,238 __begin_node_pointer,239 __node_pointer240 >::type __non_iter_node_pointer;241 242 _LIBCUDACXX_INLINE_VISIBILITY243 static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) {244 return __p;245 }246 _LIBCUDACXX_INLINE_VISIBILITY247 static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {248 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));249 }250};251 252template <class _NodePtr>253struct __forward_begin_node254{255 typedef _NodePtr pointer;256 typedef typename __rebind_pointer<_NodePtr, __forward_begin_node>::type __begin_node_pointer;257 258 pointer __next_;259 260 _LIBCUDACXX_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}261 262 _LIBCUDACXX_INLINE_VISIBILITY263 __begin_node_pointer __next_as_begin() const {264 return static_cast<__begin_node_pointer>(__next_);265 }266};267 268template <class _Tp, class _VoidPtr>269struct _LIBCUDACXX_HIDDEN __begin_node_of270{271 typedef __forward_begin_node<272 typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type273 > type;274};275 276template <class _Tp, class _VoidPtr>277struct __forward_list_node278 : public __begin_node_of<_Tp, _VoidPtr>::type279{280 typedef _Tp value_type;281 282 value_type __value_;283};284 285 286template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCUDACXX_TEMPLATE_VIS forward_list;287template<class _NodeConstPtr> class _LIBCUDACXX_TEMPLATE_VIS __forward_list_const_iterator;288 289template <class _NodePtr>290class _LIBCUDACXX_TEMPLATE_VIS __forward_list_iterator291{292 typedef __forward_node_traits<_NodePtr> __traits;293 typedef typename __traits::__node_pointer __node_pointer;294 typedef typename __traits::__begin_node_pointer __begin_node_pointer;295 typedef typename __traits::__iter_node_pointer __iter_node_pointer;296 typedef typename __traits::__void_pointer __void_pointer;297 298 __iter_node_pointer __ptr_;299 300 _LIBCUDACXX_INLINE_VISIBILITY301 __begin_node_pointer __get_begin() const {302 return static_cast<__begin_node_pointer>(303 static_cast<__void_pointer>(__ptr_));304 }305 _LIBCUDACXX_INLINE_VISIBILITY306 __node_pointer __get_unsafe_node_pointer() const {307 return static_cast<__node_pointer>(308 static_cast<__void_pointer>(__ptr_));309 }310 311 _LIBCUDACXX_INLINE_VISIBILITY312 explicit __forward_list_iterator(nullptr_t) noexcept : __ptr_(nullptr) {}313 314 _LIBCUDACXX_INLINE_VISIBILITY315 explicit __forward_list_iterator(__begin_node_pointer __p) noexcept316 : __ptr_(__traits::__as_iter_node(__p)) {}317 318 _LIBCUDACXX_INLINE_VISIBILITY319 explicit __forward_list_iterator(__node_pointer __p) noexcept320 : __ptr_(__traits::__as_iter_node(__p)) {}321 322 template<class, class> friend class _LIBCUDACXX_TEMPLATE_VIS forward_list;323 template<class> friend class _LIBCUDACXX_TEMPLATE_VIS __forward_list_const_iterator;324 325public:326 typedef forward_iterator_tag iterator_category;327 typedef typename __traits::__node_value_type value_type;328 typedef value_type& reference;329 typedef typename pointer_traits<__node_pointer>::difference_type330 difference_type;331 typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;332 333 _LIBCUDACXX_INLINE_VISIBILITY334 __forward_list_iterator() noexcept : __ptr_(nullptr) {}335 336 _LIBCUDACXX_INLINE_VISIBILITY337 reference operator*() const {return __get_unsafe_node_pointer()->__value_;}338 _LIBCUDACXX_INLINE_VISIBILITY339 pointer operator->() const {340 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_);341 }342 343 _LIBCUDACXX_INLINE_VISIBILITY344 __forward_list_iterator& operator++()345 {346 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);347 return *this;348 }349 _LIBCUDACXX_INLINE_VISIBILITY350 __forward_list_iterator operator++(int)351 {352 __forward_list_iterator __t(*this);353 ++(*this);354 return __t;355 }356 357 friend _LIBCUDACXX_INLINE_VISIBILITY358 bool operator==(const __forward_list_iterator& __x,359 const __forward_list_iterator& __y)360 {return __x.__ptr_ == __y.__ptr_;}361 friend _LIBCUDACXX_INLINE_VISIBILITY362 bool operator!=(const __forward_list_iterator& __x,363 const __forward_list_iterator& __y)364 {return !(__x == __y);}365};366 367template <class _NodeConstPtr>368class _LIBCUDACXX_TEMPLATE_VIS __forward_list_const_iterator369{370 static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), "");371 typedef _NodeConstPtr _NodePtr;372 373 typedef __forward_node_traits<_NodePtr> __traits;374 typedef typename __traits::__node __node;375 typedef typename __traits::__node_pointer __node_pointer;376 typedef typename __traits::__begin_node_pointer __begin_node_pointer;377 typedef typename __traits::__iter_node_pointer __iter_node_pointer;378 typedef typename __traits::__void_pointer __void_pointer;379 380 __iter_node_pointer __ptr_;381 382 __begin_node_pointer __get_begin() const {383 return static_cast<__begin_node_pointer>(384 static_cast<__void_pointer>(__ptr_));385 }386 __node_pointer __get_unsafe_node_pointer() const {387 return static_cast<__node_pointer>(388 static_cast<__void_pointer>(__ptr_));389 }390 391 _LIBCUDACXX_INLINE_VISIBILITY392 explicit __forward_list_const_iterator(nullptr_t) noexcept393 : __ptr_(nullptr) {}394 395 _LIBCUDACXX_INLINE_VISIBILITY396 explicit __forward_list_const_iterator(__begin_node_pointer __p) noexcept397 : __ptr_(__traits::__as_iter_node(__p)) {}398 399 _LIBCUDACXX_INLINE_VISIBILITY400 explicit __forward_list_const_iterator(__node_pointer __p) noexcept401 : __ptr_(__traits::__as_iter_node(__p)) {}402 403 404 template<class, class> friend class forward_list;405 406public:407 typedef forward_iterator_tag iterator_category;408 typedef typename __traits::__node_value_type value_type;409 typedef const value_type& reference;410 typedef typename pointer_traits<__node_pointer>::difference_type411 difference_type;412 typedef typename __rebind_pointer<__node_pointer, const value_type>::type413 pointer;414 415 _LIBCUDACXX_INLINE_VISIBILITY416 __forward_list_const_iterator() noexcept : __ptr_(nullptr) {}417 _LIBCUDACXX_INLINE_VISIBILITY418 __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) noexcept419 : __ptr_(__p.__ptr_) {}420 421 _LIBCUDACXX_INLINE_VISIBILITY422 reference operator*() const {return __get_unsafe_node_pointer()->__value_;}423 _LIBCUDACXX_INLINE_VISIBILITY424 pointer operator->() const {return pointer_traits<pointer>::pointer_to(425 __get_unsafe_node_pointer()->__value_);}426 427 _LIBCUDACXX_INLINE_VISIBILITY428 __forward_list_const_iterator& operator++()429 {430 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);431 return *this;432 }433 _LIBCUDACXX_INLINE_VISIBILITY434 __forward_list_const_iterator operator++(int)435 {436 __forward_list_const_iterator __t(*this);437 ++(*this);438 return __t;439 }440 441 friend _LIBCUDACXX_INLINE_VISIBILITY442 bool operator==(const __forward_list_const_iterator& __x,443 const __forward_list_const_iterator& __y)444 {return __x.__ptr_ == __y.__ptr_;}445 friend _LIBCUDACXX_INLINE_VISIBILITY446 bool operator!=(const __forward_list_const_iterator& __x,447 const __forward_list_const_iterator& __y)448 {return !(__x == __y);}449};450 451template <class _Tp, class _Alloc>452class __forward_list_base453{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;460 typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node;461 typedef typename __rebind_alloc_helper<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 typename __rebind_alloc_helper<466 allocator_traits<allocator_type>, __begin_node467 >::type __begin_node_allocator;468 typedef typename allocator_traits<__begin_node_allocator>::pointer469 __begin_node_pointer;470 471 static_assert((!is_same<allocator_type, __node_allocator>::value),472 "internal allocator type must differ from user-specified "473 "type; otherwise overload resolution breaks");474 475 __compressed_pair<__begin_node, __node_allocator> __before_begin_;476 477 _LIBCUDACXX_INLINE_VISIBILITY478 __begin_node_pointer __before_begin() noexcept479 {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());}480 _LIBCUDACXX_INLINE_VISIBILITY481 __begin_node_pointer __before_begin() const noexcept482 {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));}483 484 _LIBCUDACXX_INLINE_VISIBILITY485 __node_allocator& __alloc() noexcept486 {return __before_begin_.second();}487 _LIBCUDACXX_INLINE_VISIBILITY488 const __node_allocator& __alloc() const noexcept489 {return __before_begin_.second();}490 491 typedef __forward_list_iterator<__node_pointer> iterator;492 typedef __forward_list_const_iterator<__node_pointer> const_iterator;493 494 _LIBCUDACXX_INLINE_VISIBILITY495 __forward_list_base()496 noexcept(is_nothrow_default_constructible<__node_allocator>::value)497 : __before_begin_(__begin_node()) {}498 _LIBCUDACXX_INLINE_VISIBILITY499 explicit __forward_list_base(const allocator_type& __a)500 : __before_begin_(__begin_node(), __node_allocator(__a)) {}501 _LIBCUDACXX_INLINE_VISIBILITY502 explicit __forward_list_base(const __node_allocator& __a)503 : __before_begin_(__begin_node(), __a) {}504public:505 _LIBCUDACXX_INLINE_VISIBILITY506 __forward_list_base(__forward_list_base&& __x)507 noexcept(is_nothrow_move_constructible<__node_allocator>::value);508 _LIBCUDACXX_INLINE_VISIBILITY509 __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);510 511private:512 __forward_list_base(const __forward_list_base&);513 __forward_list_base& operator=(const __forward_list_base&);514 515public:516 ~__forward_list_base();517 518protected:519 _LIBCUDACXX_INLINE_VISIBILITY520 void __copy_assign_alloc(const __forward_list_base& __x)521 {__copy_assign_alloc(__x, integral_constant<bool,522 __node_traits::propagate_on_container_copy_assignment::value>());}523 524 _LIBCUDACXX_INLINE_VISIBILITY525 void __move_assign_alloc(__forward_list_base& __x)526 noexcept(!__node_traits::propagate_on_container_move_assignment::value ||527 is_nothrow_move_assignable<__node_allocator>::value)528 {__move_assign_alloc(__x, integral_constant<bool,529 __node_traits::propagate_on_container_move_assignment::value>());}530 531public:532 _LIBCUDACXX_INLINE_VISIBILITY533 void swap(__forward_list_base& __x)534#if _LIBCUDACXX_STD_VER >= 14535 noexcept;536#else537 noexcept(!__node_traits::propagate_on_container_move_assignment::value ||538 __is_nothrow_swappable<__node_allocator>::value);539#endif540protected:541 void clear() noexcept;542 543private:544 _LIBCUDACXX_INLINE_VISIBILITY545 void __copy_assign_alloc(const __forward_list_base&, false_type) {}546 _LIBCUDACXX_INLINE_VISIBILITY547 void __copy_assign_alloc(const __forward_list_base& __x, true_type)548 {549 if (__alloc() != __x.__alloc())550 clear();551 __alloc() = __x.__alloc();552 }553 554 _LIBCUDACXX_INLINE_VISIBILITY555 void __move_assign_alloc(__forward_list_base&, false_type) noexcept556 {}557 _LIBCUDACXX_INLINE_VISIBILITY558 void __move_assign_alloc(__forward_list_base& __x, true_type)559 noexcept(is_nothrow_move_assignable<__node_allocator>::value)560 {__alloc() = _CUDA_VSTD::move(__x.__alloc());}561};562 563template <class _Tp, class _Alloc>564inline565__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)566 noexcept(is_nothrow_move_constructible<__node_allocator>::value)567 : __before_begin_(_CUDA_VSTD::move(__x.__before_begin_))568{569 __x.__before_begin()->__next_ = nullptr;570}571 572template <class _Tp, class _Alloc>573inline574__forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,575 const allocator_type& __a)576 : __before_begin_(__begin_node(), __node_allocator(__a))577{578 if (__alloc() == __x.__alloc())579 {580 __before_begin()->__next_ = __x.__before_begin()->__next_;581 __x.__before_begin()->__next_ = nullptr;582 }583}584 585template <class _Tp, class _Alloc>586__forward_list_base<_Tp, _Alloc>::~__forward_list_base()587{588 clear();589}590 591template <class _Tp, class _Alloc>592inline593void594__forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)595#if _LIBCUDACXX_STD_VER >= 14596 noexcept597#else598 noexcept(!__node_traits::propagate_on_container_move_assignment::value ||599 __is_nothrow_swappable<__node_allocator>::value)600#endif601{602 __swap_allocator(__alloc(), __x.__alloc(),603 integral_constant<bool, __node_traits::propagate_on_container_swap::value>());604 using _CUDA_VSTD::swap;605 swap(__before_begin()->__next_, __x.__before_begin()->__next_);606}607 608template <class _Tp, class _Alloc>609void610__forward_list_base<_Tp, _Alloc>::clear() noexcept611{612 __node_allocator& __a = __alloc();613 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)614 {615 __node_pointer __next = __p->__next_;616 __node_traits::destroy(__a, _CUDA_VSTD::addressof(__p->__value_));617 __node_traits::deallocate(__a, __p, 1);618 __p = __next;619 }620 __before_begin()->__next_ = nullptr;621}622 623template <class _Tp, class _Alloc /*= allocator<_Tp>*/>624class _LIBCUDACXX_TEMPLATE_VIS forward_list625 : private __forward_list_base<_Tp, _Alloc>626{627 typedef __forward_list_base<_Tp, _Alloc> base;628 typedef typename base::__node_allocator __node_allocator;629 typedef typename base::__node __node;630 typedef typename base::__node_traits __node_traits;631 typedef typename base::__node_pointer __node_pointer;632 typedef typename base::__begin_node_pointer __begin_node_pointer;633 634public:635 typedef _Tp value_type;636 typedef _Alloc allocator_type;637 638 static_assert((is_same<typename allocator_type::value_type, value_type>::value),639 "Allocator::value_type must be same type as value_type");640 641 typedef value_type& reference;642 typedef const value_type& const_reference;643 typedef typename allocator_traits<allocator_type>::pointer pointer;644 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;645 typedef typename allocator_traits<allocator_type>::size_type size_type;646 typedef typename allocator_traits<allocator_type>::difference_type difference_type;647 648 typedef typename base::iterator iterator;649 typedef typename base::const_iterator const_iterator;650#if _LIBCUDACXX_STD_VER > 17651 typedef size_type __remove_return_type;652#else653 typedef void __remove_return_type;654#endif655 656 _LIBCUDACXX_INLINE_VISIBILITY657 forward_list()658 noexcept(is_nothrow_default_constructible<__node_allocator>::value)659 {} // = default;660 _LIBCUDACXX_INLINE_VISIBILITY661 explicit forward_list(const allocator_type& __a);662 explicit forward_list(size_type __n);663#if _LIBCUDACXX_STD_VER > 11664 explicit forward_list(size_type __n, const allocator_type& __a);665#endif666 forward_list(size_type __n, const value_type& __v);667 forward_list(size_type __n, const value_type& __v, const allocator_type& __a);668 template <class _InputIterator>669 forward_list(_InputIterator __f, _InputIterator __l,670 typename enable_if<671 __is_cpp17_input_iterator<_InputIterator>::value672 >::type* = nullptr);673 template <class _InputIterator>674 forward_list(_InputIterator __f, _InputIterator __l,675 const allocator_type& __a,676 typename enable_if<677 __is_cpp17_input_iterator<_InputIterator>::value678 >::type* = nullptr);679 forward_list(const forward_list& __x);680 forward_list(const forward_list& __x, const allocator_type& __a);681 682 forward_list& operator=(const forward_list& __x);683 684 _LIBCUDACXX_INLINE_VISIBILITY685 forward_list(forward_list&& __x)686 noexcept(is_nothrow_move_constructible<base>::value)687 : base(_CUDA_VSTD::move(__x)) {}688 forward_list(forward_list&& __x, const allocator_type& __a);689 690 forward_list(initializer_list<value_type> __il);691 forward_list(initializer_list<value_type> __il, const allocator_type& __a);692 693 _LIBCUDACXX_INLINE_VISIBILITY694 forward_list& operator=(forward_list&& __x)695 noexcept(696 __node_traits::propagate_on_container_move_assignment::value &&697 is_nothrow_move_assignable<allocator_type>::value);698 699 _LIBCUDACXX_INLINE_VISIBILITY700 forward_list& operator=(initializer_list<value_type> __il);701 702 _LIBCUDACXX_INLINE_VISIBILITY703 void assign(initializer_list<value_type> __il);704 705 // ~forward_list() = default;706 707 template <class _InputIterator>708 typename enable_if709 <710 __is_cpp17_input_iterator<_InputIterator>::value,711 void712 >::type713 assign(_InputIterator __f, _InputIterator __l);714 void assign(size_type __n, const value_type& __v);715 716 _LIBCUDACXX_INLINE_VISIBILITY717 allocator_type get_allocator() const noexcept718 {return allocator_type(base::__alloc());}719 720 _LIBCUDACXX_INLINE_VISIBILITY721 iterator begin() noexcept722 {return iterator(base::__before_begin()->__next_);}723 _LIBCUDACXX_INLINE_VISIBILITY724 const_iterator begin() const noexcept725 {return const_iterator(base::__before_begin()->__next_);}726 _LIBCUDACXX_INLINE_VISIBILITY727 iterator end() noexcept728 {return iterator(nullptr);}729 _LIBCUDACXX_INLINE_VISIBILITY730 const_iterator end() const noexcept731 {return const_iterator(nullptr);}732 733 _LIBCUDACXX_INLINE_VISIBILITY734 const_iterator cbegin() const noexcept735 {return const_iterator(base::__before_begin()->__next_);}736 _LIBCUDACXX_INLINE_VISIBILITY737 const_iterator cend() const noexcept738 {return const_iterator(nullptr);}739 740 _LIBCUDACXX_INLINE_VISIBILITY741 iterator before_begin() noexcept742 {return iterator(base::__before_begin());}743 _LIBCUDACXX_INLINE_VISIBILITY744 const_iterator before_begin() const noexcept745 {return const_iterator(base::__before_begin());}746 _LIBCUDACXX_INLINE_VISIBILITY747 const_iterator cbefore_begin() const noexcept748 {return const_iterator(base::__before_begin());}749 750 _LIBCUDACXX_NODISCARD_AFTER_CXX17 _LIBCUDACXX_INLINE_VISIBILITY751 bool empty() const noexcept752 {return base::__before_begin()->__next_ == nullptr;}753 _LIBCUDACXX_INLINE_VISIBILITY754 size_type max_size() const noexcept {755 return std::min<size_type>(756 __node_traits::max_size(base::__alloc()),757 numeric_limits<difference_type>::max());758 }759 760 _LIBCUDACXX_INLINE_VISIBILITY761 reference front() {return base::__before_begin()->__next_->__value_;}762 _LIBCUDACXX_INLINE_VISIBILITY763 const_reference front() const {return base::__before_begin()->__next_->__value_;}764 765#if _LIBCUDACXX_STD_VER > 14766 template <class... _Args> reference emplace_front(_Args&&... __args);767#else768 template <class... _Args> void emplace_front(_Args&&... __args);769#endif770 void push_front(value_type&& __v);771 void push_front(const value_type& __v);772 773 void pop_front();774 775 template <class... _Args>776 iterator emplace_after(const_iterator __p, _Args&&... __args);777 778 iterator insert_after(const_iterator __p, value_type&& __v);779 iterator insert_after(const_iterator __p, initializer_list<value_type> __il)780 {return insert_after(__p, __il.begin(), __il.end());}781 iterator insert_after(const_iterator __p, const value_type& __v);782 iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);783 template <class _InputIterator>784 _LIBCUDACXX_INLINE_VISIBILITY785 typename enable_if786 <787 __is_cpp17_input_iterator<_InputIterator>::value,788 iterator789 >::type790 insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);791 792 iterator erase_after(const_iterator __p);793 iterator erase_after(const_iterator __f, const_iterator __l);794 795 _LIBCUDACXX_INLINE_VISIBILITY796 void swap(forward_list& __x)797#if _LIBCUDACXX_STD_VER >= 14798 noexcept799#else800 noexcept(!__node_traits::propagate_on_container_swap::value ||801 __is_nothrow_swappable<__node_allocator>::value)802#endif803 {base::swap(__x);}804 805 void resize(size_type __n);806 void resize(size_type __n, const value_type& __v);807 _LIBCUDACXX_INLINE_VISIBILITY808 void clear() noexcept {base::clear();}809 810 _LIBCUDACXX_INLINE_VISIBILITY811 void splice_after(const_iterator __p, forward_list&& __x);812 _LIBCUDACXX_INLINE_VISIBILITY813 void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);814 _LIBCUDACXX_INLINE_VISIBILITY815 void splice_after(const_iterator __p, forward_list&& __x,816 const_iterator __f, const_iterator __l);817 void splice_after(const_iterator __p, forward_list& __x);818 void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);819 void splice_after(const_iterator __p, forward_list& __x,820 const_iterator __f, const_iterator __l);821 __remove_return_type remove(const value_type& __v);822 template <class _Predicate> __remove_return_type remove_if(_Predicate __pred);823 _LIBCUDACXX_INLINE_VISIBILITY824 __remove_return_type unique() {return unique(__equal_to<value_type>());}825 template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred);826 _LIBCUDACXX_INLINE_VISIBILITY827 void merge(forward_list&& __x) {merge(__x, __less<value_type>());}828 template <class _Compare>829 _LIBCUDACXX_INLINE_VISIBILITY830 void merge(forward_list&& __x, _Compare __comp)831 {merge(__x, _CUDA_VSTD::move(__comp));}832 _LIBCUDACXX_INLINE_VISIBILITY833 void merge(forward_list& __x) {merge(__x, __less<value_type>());}834 template <class _Compare> void merge(forward_list& __x, _Compare __comp);835 _LIBCUDACXX_INLINE_VISIBILITY836 void sort() {sort(__less<value_type>());}837 template <class _Compare> _LIBCUDACXX_INLINE_VISIBILITY void sort(_Compare __comp);838 void reverse() noexcept;839 840private:841 842 void __move_assign(forward_list& __x, true_type)843 noexcept(is_nothrow_move_assignable<allocator_type>::value);844 void __move_assign(forward_list& __x, false_type);845 846 template <class _Compare>847 static848 __node_pointer849 __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);850 851 template <class _Compare>852 static853 __node_pointer854 __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);855};856 857 858#ifndef _LIBCUDACXX_HAS_NO_DEDUCTION_GUIDES859template<class _InputIterator,860 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,861 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type862 >863forward_list(_InputIterator, _InputIterator)864 -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;865 866template<class _InputIterator,867 class _Alloc,868 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type869 >870forward_list(_InputIterator, _InputIterator, _Alloc)871 -> forward_list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;872#endif873 874template <class _Tp, class _Alloc>875inline876forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)877 : base(__a)878{879}880 881template <class _Tp, class _Alloc>882forward_list<_Tp, _Alloc>::forward_list(size_type __n)883{884 if (__n > 0)885 {886 __node_allocator& __a = base::__alloc();887 typedef __allocator_destructor<__node_allocator> _Dp;888 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));889 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,890 __p = __p->__next_as_begin())891 {892 __h.reset(__node_traits::allocate(__a, 1));893 __node_traits::construct(__a, _CUDA_VSTD::addressof(__h->__value_));894 __h->__next_ = nullptr;895 __p->__next_ = __h.release();896 }897 }898}899 900#if _LIBCUDACXX_STD_VER > 11901template <class _Tp, class _Alloc>902forward_list<_Tp, _Alloc>::forward_list(size_type __n,903 const allocator_type& __base_alloc)904 : base ( __base_alloc )905{906 if (__n > 0)907 {908 __node_allocator& __a = base::__alloc();909 typedef __allocator_destructor<__node_allocator> _Dp;910 unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));911 for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,912 __p = __p->__next_as_begin())913 {914 __h.reset(__node_traits::allocate(__a, 1));915 __node_traits::construct(__a, _CUDA_VSTD::addressof(__h->__value_));916 __h->__next_ = nullptr;917 __p->__next_ = __h.release();918 }919 }920}921#endif922 923template <class _Tp, class _Alloc>924forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)925{926 insert_after(cbefore_begin(), __n, __v);927}928 929template <class _Tp, class _Alloc>930forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v,931 const allocator_type& __a)932 : base(__a)933{934 insert_after(cbefore_begin(), __n, __v);935}936 937template <class _Tp, class _Alloc>938template <class _InputIterator>939forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,940 typename enable_if<941 __is_cpp17_input_iterator<_InputIterator>::value942 >::type*)943{944 insert_after(cbefore_begin(), __f, __l);945}946 947template <class _Tp, class _Alloc>948template <class _InputIterator>949forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,950 const allocator_type& __a,951 typename enable_if<952 __is_cpp17_input_iterator<_InputIterator>::value953 >::type*)954 : base(__a)955{956 insert_after(cbefore_begin(), __f, __l);957}958 959template <class _Tp, class _Alloc>960forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)961 : base(962 __node_traits::select_on_container_copy_construction(__x.__alloc())) {963 insert_after(cbefore_begin(), __x.begin(), __x.end());964}965 966template <class _Tp, class _Alloc>967forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,968 const allocator_type& __a)969 : base(__a)970{971 insert_after(cbefore_begin(), __x.begin(), __x.end());972}973 974template <class _Tp, class _Alloc>975forward_list<_Tp, _Alloc>&976forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)977{978 if (this != &__x)979 {980 base::__copy_assign_alloc(__x);981 assign(__x.begin(), __x.end());982 }983 return *this;984}985 986template <class _Tp, class _Alloc>987forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,988 const allocator_type& __a)989 : base(_CUDA_VSTD::move(__x), __a)990{991 if (base::__alloc() != __x.__alloc())992 {993 typedef move_iterator<iterator> _Ip;994 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));995 }996}997 998template <class _Tp, class _Alloc>999forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)1000{1001 insert_after(cbefore_begin(), __il.begin(), __il.end());1002}1003 1004template <class _Tp, class _Alloc>1005forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,1006 const allocator_type& __a)1007 : base(__a)1008{1009 insert_after(cbefore_begin(), __il.begin(), __il.end());1010}1011 1012template <class _Tp, class _Alloc>1013void1014forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)1015 noexcept(is_nothrow_move_assignable<allocator_type>::value)1016{1017 clear();1018 base::__move_assign_alloc(__x);1019 base::__before_begin()->__next_ = __x.__before_begin()->__next_;1020 __x.__before_begin()->__next_ = nullptr;1021}1022 1023template <class _Tp, class _Alloc>1024void1025forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)1026{1027 if (base::__alloc() == __x.__alloc())1028 __move_assign(__x, true_type());1029 else1030 {1031 typedef move_iterator<iterator> _Ip;1032 assign(_Ip(__x.begin()), _Ip(__x.end()));1033 }1034}1035 1036template <class _Tp, class _Alloc>1037inline1038forward_list<_Tp, _Alloc>&1039forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)1040 noexcept(1041 __node_traits::propagate_on_container_move_assignment::value &&1042 is_nothrow_move_assignable<allocator_type>::value)1043{1044 __move_assign(__x, integral_constant<bool,1045 __node_traits::propagate_on_container_move_assignment::value>());1046 return *this;1047}1048 1049template <class _Tp, class _Alloc>1050inline1051forward_list<_Tp, _Alloc>&1052forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)1053{1054 assign(__il.begin(), __il.end());1055 return *this;1056}1057 1058template <class _Tp, class _Alloc>1059template <class _InputIterator>1060typename enable_if1061<1062 __is_cpp17_input_iterator<_InputIterator>::value,1063 void1064>::type1065forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)1066{1067 iterator __i = before_begin();1068 iterator __j = _CUDA_VSTD::next(__i);1069 iterator __e = end();1070 for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)1071 *__j = *__f;1072 if (__j == __e)1073 insert_after(__i, __f, __l);1074 else1075 erase_after(__i, __e);1076}1077 1078template <class _Tp, class _Alloc>1079void1080forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)1081{1082 iterator __i = before_begin();1083 iterator __j = _CUDA_VSTD::next(__i);1084 iterator __e = end();1085 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)1086 *__j = __v;1087 if (__j == __e)1088 insert_after(__i, __n, __v);1089 else1090 erase_after(__i, __e);1091}1092 1093template <class _Tp, class _Alloc>1094inline1095void1096forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)1097{1098 assign(__il.begin(), __il.end());1099}1100 1101template <class _Tp, class _Alloc>1102template <class... _Args>1103#if _LIBCUDACXX_STD_VER > 141104typename forward_list<_Tp, _Alloc>::reference1105#else1106void1107#endif1108forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)1109{1110 __node_allocator& __a = base::__alloc();1111 typedef __allocator_destructor<__node_allocator> _Dp;1112 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));1113 __node_traits::construct(__a, _CUDA_VSTD::addressof(__h->__value_),1114 _CUDA_VSTD::forward<_Args>(__args)...);1115 __h->__next_ = base::__before_begin()->__next_;1116 base::__before_begin()->__next_ = __h.release();1117#if _LIBCUDACXX_STD_VER > 141118 return base::__before_begin()->__next_->__value_;1119#endif1120}1121 1122template <class _Tp, class _Alloc>1123void1124forward_list<_Tp, _Alloc>::push_front(value_type&& __v)1125{1126 __node_allocator& __a = base::__alloc();1127 typedef __allocator_destructor<__node_allocator> _Dp;1128 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));1129 __node_traits::construct(__a, _CUDA_VSTD::addressof(__h->__value_), _CUDA_VSTD::move(__v));1130 __h->__next_ = base::__before_begin()->__next_;1131 base::__before_begin()->__next_ = __h.release();1132}1133 1134template <class _Tp, class _Alloc>1135void1136forward_list<_Tp, _Alloc>::push_front(const value_type& __v)1137{1138 __node_allocator& __a = base::__alloc();1139 typedef __allocator_destructor<__node_allocator> _Dp;1140 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));1141 __node_traits::construct(__a, _CUDA_VSTD::addressof(__h->__value_), __v);1142 __h->__next_ = base::__before_begin()->__next_;1143 base::__before_begin()->__next_ = __h.release();1144}1145 1146template <class _Tp, class _Alloc>1147void1148forward_list<_Tp, _Alloc>::pop_front()1149{1150 __node_allocator& __a = base::__alloc();1151 __node_pointer __p = base::__before_begin()->__next_;1152 base::__before_begin()->__next_ = __p->__next_;1153 __node_traits::destroy(__a, _CUDA_VSTD::addressof(__p->__value_));1154 __node_traits::deallocate(__a, __p, 1);1155}1156 1157template <class _Tp, class _Alloc>1158template <class... _Args>1159typename forward_list<_Tp, _Alloc>::iterator1160forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)1161{1162 __begin_node_pointer const __r = __p.__get_begin();1163 __node_allocator& __a = base::__alloc();1164 typedef __allocator_destructor<__node_allocator> _Dp;1165 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));1166 __node_traits::construct(__a, _CUDA_VSTD::addressof(__h->__value_),1167 _CUDA_VSTD::forward<_Args>(__args)...);1168 __h->__next_ = __r->__next_;1169 __r->__next_ = __h.release();1170 return iterator(__r->__next_);1171}1172 1173template <class _Tp, class _Alloc>1174typename forward_list<_Tp, _Alloc>::iterator1175forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)1176{1177 __begin_node_pointer const __r = __p.__get_begin();1178 __node_allocator& __a = base::__alloc();1179 typedef __allocator_destructor<__node_allocator> _Dp;1180 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));1181 __node_traits::construct(__a, _CUDA_VSTD::addressof(__h->__value_), _CUDA_VSTD::move(__v));1182 __h->__next_ = __r->__next_;1183 __r->__next_ = __h.release();1184 return iterator(__r->__next_);1185}1186 1187template <class _Tp, class _Alloc>1188typename forward_list<_Tp, _Alloc>::iterator1189forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)1190{1191 __begin_node_pointer const __r = __p.__get_begin();1192 __node_allocator& __a = base::__alloc();1193 typedef __allocator_destructor<__node_allocator> _Dp;1194 unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));1195 __node_traits::construct(__a, _CUDA_VSTD::addressof(__h->__value_), __v);1196 __h->__next_ = __r->__next_;1197 __r->__next_ = __h.release();1198 return iterator(__r->__next_);1199}1200