Warning, /include/c++/v1/forward_list is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP_FORWARD_LIST
0011 #define _LIBCPP_FORWARD_LIST
0012
0013 /*
0014 forward_list synopsis
0015
0016 namespace std
0017 {
0018
0019 template <class T, class Allocator = allocator<T>>
0020 class forward_list
0021 {
0022 public:
0023 typedef T value_type;
0024 typedef Allocator allocator_type;
0025
0026 typedef value_type& reference;
0027 typedef const value_type& const_reference;
0028 typedef typename allocator_traits<allocator_type>::pointer pointer;
0029 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0030 typedef typename allocator_traits<allocator_type>::size_type size_type;
0031 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0032
0033 typedef <details> iterator;
0034 typedef <details> const_iterator;
0035
0036 forward_list()
0037 noexcept(is_nothrow_default_constructible<allocator_type>::value);
0038 explicit forward_list(const allocator_type& a);
0039 explicit forward_list(size_type n);
0040 explicit forward_list(size_type n, const allocator_type& a); // C++14
0041 forward_list(size_type n, const value_type& v);
0042 forward_list(size_type n, const value_type& v, const allocator_type& a);
0043 template <class InputIterator>
0044 forward_list(InputIterator first, InputIterator last);
0045 template <class InputIterator>
0046 forward_list(InputIterator first, InputIterator last, const allocator_type& a);
0047 template<container-compatible-range<T> R>
0048 forward_list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
0049 forward_list(const forward_list& x);
0050 forward_list(const forward_list& x, const allocator_type& a);
0051 forward_list(forward_list&& x)
0052 noexcept(is_nothrow_move_constructible<allocator_type>::value);
0053 forward_list(forward_list&& x, const allocator_type& a);
0054 forward_list(initializer_list<value_type> il);
0055 forward_list(initializer_list<value_type> il, const allocator_type& a);
0056
0057 ~forward_list();
0058
0059 forward_list& operator=(const forward_list& x);
0060 forward_list& operator=(forward_list&& x)
0061 noexcept(
0062 allocator_type::propagate_on_container_move_assignment::value &&
0063 is_nothrow_move_assignable<allocator_type>::value);
0064 forward_list& operator=(initializer_list<value_type> il);
0065
0066 template <class InputIterator>
0067 void assign(InputIterator first, InputIterator last);
0068 template<container-compatible-range<T> R>
0069 void assign_range(R&& rg); // C++23
0070 void assign(size_type n, const value_type& v);
0071 void assign(initializer_list<value_type> il);
0072
0073 allocator_type get_allocator() const noexcept;
0074
0075 iterator begin() noexcept;
0076 const_iterator begin() const noexcept;
0077 iterator end() noexcept;
0078 const_iterator end() const noexcept;
0079
0080 const_iterator cbegin() const noexcept;
0081 const_iterator cend() const noexcept;
0082
0083 iterator before_begin() noexcept;
0084 const_iterator before_begin() const noexcept;
0085 const_iterator cbefore_begin() const noexcept;
0086
0087 bool empty() const noexcept;
0088 size_type max_size() const noexcept;
0089
0090 reference front();
0091 const_reference front() const;
0092
0093 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
0094 void push_front(const value_type& v);
0095 void push_front(value_type&& v);
0096 template<container-compatible-range<T> R>
0097 void prepend_range(R&& rg); // C++23
0098
0099 void pop_front();
0100
0101 template <class... Args>
0102 iterator emplace_after(const_iterator p, Args&&... args);
0103 iterator insert_after(const_iterator p, const value_type& v);
0104 iterator insert_after(const_iterator p, value_type&& v);
0105 iterator insert_after(const_iterator p, size_type n, const value_type& v);
0106 template <class InputIterator>
0107 iterator insert_after(const_iterator p,
0108 InputIterator first, InputIterator last);
0109 template<container-compatible-range<T> R>
0110 iterator insert_range_after(const_iterator position, R&& rg); // C++23
0111 iterator insert_after(const_iterator p, initializer_list<value_type> il);
0112
0113 iterator erase_after(const_iterator p);
0114 iterator erase_after(const_iterator first, const_iterator last);
0115
0116 void swap(forward_list& x)
0117 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
0118
0119 void resize(size_type n);
0120 void resize(size_type n, const value_type& v);
0121 void clear() noexcept;
0122
0123 void splice_after(const_iterator p, forward_list& x);
0124 void splice_after(const_iterator p, forward_list&& x);
0125 void splice_after(const_iterator p, forward_list& x, const_iterator i);
0126 void splice_after(const_iterator p, forward_list&& x, const_iterator i);
0127 void splice_after(const_iterator p, forward_list& x,
0128 const_iterator first, const_iterator last);
0129 void splice_after(const_iterator p, forward_list&& x,
0130 const_iterator first, const_iterator last);
0131 size_type remove(const value_type& v); // void before C++20
0132 template <class Predicate>
0133 size_type remove_if(Predicate pred); // void before C++20
0134 size_type unique(); // void before C++20
0135 template <class BinaryPredicate>
0136 size_type unique(BinaryPredicate binary_pred); // void before C++20
0137 void merge(forward_list& x);
0138 void merge(forward_list&& x);
0139 template <class Compare> void merge(forward_list& x, Compare comp);
0140 template <class Compare> void merge(forward_list&& x, Compare comp);
0141 void sort();
0142 template <class Compare> void sort(Compare comp);
0143 void reverse() noexcept;
0144 };
0145
0146
0147 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
0148 forward_list(InputIterator, InputIterator, Allocator = Allocator())
0149 -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
0150
0151 template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
0152 forward_list(from_range_t, R&&, Allocator = Allocator())
0153 -> forward_list<ranges::range_value_t<R>, Allocator>; // C++23
0154
0155 template <class T, class Allocator>
0156 bool operator==(const forward_list<T, Allocator>& x,
0157 const forward_list<T, Allocator>& y);
0158
0159 template <class T, class Allocator>
0160 bool operator< (const forward_list<T, Allocator>& x,
0161 const forward_list<T, Allocator>& y); // removed in C++20
0162
0163 template <class T, class Allocator>
0164 bool operator!=(const forward_list<T, Allocator>& x,
0165 const forward_list<T, Allocator>& y); // removed in C++20
0166
0167 template <class T, class Allocator>
0168 bool operator> (const forward_list<T, Allocator>& x,
0169 const forward_list<T, Allocator>& y); // removed in C++20
0170
0171 template <class T, class Allocator>
0172 bool operator>=(const forward_list<T, Allocator>& x,
0173 const forward_list<T, Allocator>& y); // removed in C++20
0174
0175 template <class T, class Allocator>
0176 bool operator<=(const forward_list<T, Allocator>& x,
0177 const forward_list<T, Allocator>& y); // removed in C++20
0178
0179 template<class T, class Allocator>
0180 synth-three-way-result<T> operator<=>(const forward_list<T, Allocator>& x,
0181 const forward_list<T, Allocator>& y); // since C++20
0182
0183 template <class T, class Allocator>
0184 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
0185 noexcept(noexcept(x.swap(y)));
0186
0187 template <class T, class Allocator, class U>
0188 typename forward_list<T, Allocator>::size_type
0189 erase(forward_list<T, Allocator>& c, const U& value); // C++20
0190 template <class T, class Allocator, class Predicate>
0191 typename forward_list<T, Allocator>::size_type
0192 erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20
0193
0194 } // std
0195
0196 */
0197
0198 #if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0199 # include <__cxx03/forward_list>
0200 #else
0201 # include <__algorithm/comp.h>
0202 # include <__algorithm/lexicographical_compare.h>
0203 # include <__algorithm/lexicographical_compare_three_way.h>
0204 # include <__algorithm/min.h>
0205 # include <__assert>
0206 # include <__config>
0207 # include <__cstddef/nullptr_t.h>
0208 # include <__iterator/distance.h>
0209 # include <__iterator/iterator_traits.h>
0210 # include <__iterator/move_iterator.h>
0211 # include <__iterator/next.h>
0212 # include <__memory/addressof.h>
0213 # include <__memory/allocation_guard.h>
0214 # include <__memory/allocator.h>
0215 # include <__memory/allocator_traits.h>
0216 # include <__memory/compressed_pair.h>
0217 # include <__memory/construct_at.h>
0218 # include <__memory/pointer_traits.h>
0219 # include <__memory/swap_allocator.h>
0220 # include <__memory_resource/polymorphic_allocator.h>
0221 # include <__new/launder.h>
0222 # include <__ranges/access.h>
0223 # include <__ranges/concepts.h>
0224 # include <__ranges/container_compatible_range.h>
0225 # include <__ranges/from_range.h>
0226 # include <__type_traits/conditional.h>
0227 # include <__type_traits/container_traits.h>
0228 # include <__type_traits/enable_if.h>
0229 # include <__type_traits/is_allocator.h>
0230 # include <__type_traits/is_const.h>
0231 # include <__type_traits/is_nothrow_assignable.h>
0232 # include <__type_traits/is_nothrow_constructible.h>
0233 # include <__type_traits/is_pointer.h>
0234 # include <__type_traits/is_same.h>
0235 # include <__type_traits/is_swappable.h>
0236 # include <__type_traits/type_identity.h>
0237 # include <__utility/forward.h>
0238 # include <__utility/move.h>
0239 # include <__utility/swap.h>
0240 # include <limits>
0241 # include <version>
0242
0243 // standard-mandated includes
0244
0245 // [iterator.range]
0246 # include <__iterator/access.h>
0247 # include <__iterator/data.h>
0248 # include <__iterator/empty.h>
0249 # include <__iterator/reverse_access.h>
0250 # include <__iterator/size.h>
0251
0252 // [forward.list.syn]
0253 # include <compare>
0254 # include <initializer_list>
0255
0256 # if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0257 # pragma GCC system_header
0258 # endif
0259
0260 _LIBCPP_PUSH_MACROS
0261 # include <__undef_macros>
0262
0263 _LIBCPP_BEGIN_NAMESPACE_STD
0264
0265 template <class _Tp, class _VoidPtr>
0266 struct __forward_list_node;
0267 template <class _NodePtr>
0268 struct __forward_begin_node;
0269
0270 template <class>
0271 struct __forward_list_node_value_type;
0272
0273 template <class _Tp, class _VoidPtr>
0274 struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
0275 typedef _Tp type;
0276 };
0277
0278 template <class _NodePtr>
0279 struct __forward_node_traits {
0280 typedef __remove_cv_t<typename pointer_traits<_NodePtr>::element_type> __node_type;
0281 typedef typename __forward_list_node_value_type<__node_type>::type __node_value_type;
0282 typedef _NodePtr __node_pointer;
0283 typedef __forward_begin_node<_NodePtr> __begin_node;
0284 typedef __rebind_pointer_t<_NodePtr, __begin_node> __begin_node_pointer;
0285 typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;
0286
0287 // TODO(LLVM 22): Remove this check
0288 # ifndef _LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB
0289 static_assert(sizeof(__begin_node_pointer) == sizeof(__node_pointer) && _LIBCPP_ALIGNOF(__begin_node_pointer) ==
0290 _LIBCPP_ALIGNOF(__node_pointer),
0291 "It looks like you are using std::forward_list with a fancy pointer type that thas a different "
0292 "representation depending on whether it points to a forward_list base pointer or a forward_list node "
0293 "pointer (both of which are implementation details of the standard library). This means that your ABI "
0294 "is being broken between LLVM 19 and LLVM 20. If you don't care about your ABI being broken, define "
0295 "the _LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB macro to silence this diagnostic.");
0296 # endif
0297
0298 _LIBCPP_HIDE_FROM_ABI static __begin_node_pointer __as_iter_node(__begin_node_pointer __p) { return __p; }
0299 _LIBCPP_HIDE_FROM_ABI static __begin_node_pointer __as_iter_node(__node_pointer __p) {
0300 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__p));
0301 }
0302 };
0303
0304 template <class _NodePtr>
0305 struct __forward_begin_node {
0306 typedef _NodePtr pointer;
0307 typedef __rebind_pointer_t<_NodePtr, __forward_begin_node> __begin_node_pointer;
0308
0309 pointer __next_;
0310
0311 _LIBCPP_HIDE_FROM_ABI __forward_begin_node() : __next_(nullptr) {}
0312 _LIBCPP_HIDE_FROM_ABI explicit __forward_begin_node(pointer __n) : __next_(__n) {}
0313
0314 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __next_as_begin() const {
0315 return static_cast<__begin_node_pointer>(__next_);
0316 }
0317 };
0318
0319 template <class _Tp, class _VoidPtr>
0320 using __begin_node_of _LIBCPP_NODEBUG =
0321 __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >;
0322
0323 template <class _Tp, class _VoidPtr>
0324 struct __forward_list_node : public __begin_node_of<_Tp, _VoidPtr> {
0325 typedef _Tp value_type;
0326 typedef __begin_node_of<_Tp, _VoidPtr> _Base;
0327 typedef typename _Base::pointer _NodePtr;
0328
0329 // We allow starting the lifetime of nodes without initializing the value held by the node,
0330 // since that is handled by the list itself in order to be allocator-aware.
0331 # ifndef _LIBCPP_CXX03_LANG
0332
0333 private:
0334 union {
0335 _Tp __value_;
0336 };
0337
0338 public:
0339 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
0340 # else
0341
0342 private:
0343 _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
0344
0345 public:
0346 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
0347 # endif
0348
0349 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_node(_NodePtr __next) : _Base(__next) {}
0350 _LIBCPP_HIDE_FROM_ABI ~__forward_list_node() {}
0351 };
0352
0353 template <class _Tp, class _Alloc = allocator<_Tp> >
0354 class _LIBCPP_TEMPLATE_VIS forward_list;
0355 template <class _NodeConstPtr>
0356 class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
0357
0358 template <class _NodePtr>
0359 class _LIBCPP_TEMPLATE_VIS __forward_list_iterator {
0360 typedef __forward_node_traits<_NodePtr> __traits;
0361 typedef typename __traits::__node_pointer __node_pointer;
0362 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
0363 typedef typename __traits::__void_pointer __void_pointer;
0364
0365 __begin_node_pointer __ptr_;
0366
0367 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {
0368 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_));
0369 }
0370 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const {
0371 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_));
0372 }
0373
0374 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
0375
0376 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
0377 : __ptr_(__traits::__as_iter_node(__p)) {}
0378
0379 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
0380 : __ptr_(__traits::__as_iter_node(__p)) {}
0381
0382 template <class, class>
0383 friend class _LIBCPP_TEMPLATE_VIS forward_list;
0384 template <class>
0385 friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
0386
0387 public:
0388 typedef forward_iterator_tag iterator_category;
0389 typedef typename __traits::__node_value_type value_type;
0390 typedef value_type& reference;
0391 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
0392 typedef __rebind_pointer_t<__node_pointer, value_type> pointer;
0393
0394 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
0395
0396 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); }
0397 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
0398 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value());
0399 }
0400
0401 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator& operator++() {
0402 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
0403 return *this;
0404 }
0405 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator operator++(int) {
0406 __forward_list_iterator __t(*this);
0407 ++(*this);
0408 return __t;
0409 }
0410
0411 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {
0412 return __x.__ptr_ == __y.__ptr_;
0413 }
0414 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {
0415 return !(__x == __y);
0416 }
0417 };
0418
0419 template <class _NodeConstPtr>
0420 class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator {
0421 static_assert(!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value, "");
0422 typedef _NodeConstPtr _NodePtr;
0423
0424 typedef __forward_node_traits<_NodePtr> __traits;
0425 typedef typename __traits::__node_type __node_type;
0426 typedef typename __traits::__node_pointer __node_pointer;
0427 typedef typename __traits::__begin_node_pointer __begin_node_pointer;
0428 typedef typename __traits::__void_pointer __void_pointer;
0429
0430 __begin_node_pointer __ptr_;
0431
0432 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {
0433 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_));
0434 }
0435 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const {
0436 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_));
0437 }
0438
0439 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
0440
0441 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
0442 : __ptr_(__traits::__as_iter_node(__p)) {}
0443
0444 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
0445 : __ptr_(__traits::__as_iter_node(__p)) {}
0446
0447 template <class, class>
0448 friend class forward_list;
0449
0450 public:
0451 typedef forward_iterator_tag iterator_category;
0452 typedef typename __traits::__node_value_type value_type;
0453 typedef const value_type& reference;
0454 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
0455 typedef __rebind_pointer_t<__node_pointer, const value_type> pointer;
0456
0457 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
0458 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
0459 : __ptr_(__p.__ptr_) {}
0460
0461 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); }
0462 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
0463 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value());
0464 }
0465
0466 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator& operator++() {
0467 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
0468 return *this;
0469 }
0470 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator operator++(int) {
0471 __forward_list_const_iterator __t(*this);
0472 ++(*this);
0473 return __t;
0474 }
0475
0476 friend _LIBCPP_HIDE_FROM_ABI bool
0477 operator==(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {
0478 return __x.__ptr_ == __y.__ptr_;
0479 }
0480 friend _LIBCPP_HIDE_FROM_ABI bool
0481 operator!=(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {
0482 return !(__x == __y);
0483 }
0484 };
0485
0486 template <class _Tp, class _Alloc>
0487 class __forward_list_base {
0488 protected:
0489 typedef _Tp value_type;
0490 typedef _Alloc allocator_type;
0491
0492 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
0493 typedef __forward_list_node<value_type, void_pointer> __node_type;
0494 typedef __begin_node_of<value_type, void_pointer> __begin_node;
0495 typedef __rebind_alloc<allocator_traits<allocator_type>, __node_type> __node_allocator;
0496 typedef allocator_traits<__node_allocator> __node_traits;
0497 typedef typename __node_traits::pointer __node_pointer;
0498
0499 typedef __rebind_alloc<allocator_traits<allocator_type>, __begin_node> __begin_node_allocator;
0500 typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer;
0501
0502 _LIBCPP_COMPRESSED_PAIR(__begin_node, __before_begin_, __node_allocator, __alloc_);
0503
0504 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() _NOEXCEPT {
0505 return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_);
0506 }
0507 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() const _NOEXCEPT {
0508 return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_));
0509 }
0510
0511 typedef __forward_list_iterator<__node_pointer> iterator;
0512 typedef __forward_list_const_iterator<__node_pointer> const_iterator;
0513
0514 _LIBCPP_HIDE_FROM_ABI __forward_list_base() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
0515 : __before_begin_(__begin_node()) {}
0516 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const allocator_type& __a)
0517 : __before_begin_(__begin_node()), __alloc_(__node_allocator(__a)) {}
0518 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const __node_allocator& __a)
0519 : __before_begin_(__begin_node()), __alloc_(__a) {}
0520
0521 public:
0522 # ifndef _LIBCPP_CXX03_LANG
0523 _LIBCPP_HIDE_FROM_ABI
0524 __forward_list_base(__forward_list_base&& __x) noexcept(is_nothrow_move_constructible<__node_allocator>::value);
0525 _LIBCPP_HIDE_FROM_ABI __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
0526 # endif // _LIBCPP_CXX03_LANG
0527
0528 __forward_list_base(const __forward_list_base&) = delete;
0529 __forward_list_base& operator=(const __forward_list_base&) = delete;
0530
0531 _LIBCPP_HIDE_FROM_ABI ~__forward_list_base();
0532
0533 protected:
0534 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x) {
0535 __copy_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
0536 }
0537
0538 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x)
0539 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
0540 is_nothrow_move_assignable<__node_allocator>::value) {
0541 __move_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
0542 }
0543
0544 template <class... _Args>
0545 _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__node_pointer __next, _Args&&... __args) {
0546 __allocation_guard<__node_allocator> __guard(__alloc_, 1);
0547 // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
0548 // held inside the node, since we need to use the allocator's construct() method for that.
0549 //
0550 // We don't use the allocator's construct() method to construct the node itself since the
0551 // Cpp17FooInsertable named requirements don't require the allocator's construct() method
0552 // to work on anything other than the value_type.
0553 std::__construct_at(std::addressof(*__guard.__get()), __next);
0554
0555 // Now construct the value_type using the allocator's construct() method.
0556 __node_traits::construct(__alloc_, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);
0557 return __guard.__release_ptr();
0558 }
0559
0560 _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {
0561 // For the same reason as above, we use the allocator's destroy() method for the value_type,
0562 // but not for the node itself.
0563 __node_traits::destroy(__alloc_, std::addressof(__node->__get_value()));
0564 std::__destroy_at(std::addressof(*__node));
0565 __node_traits::deallocate(__alloc_, __node, 1);
0566 }
0567
0568 public:
0569 _LIBCPP_HIDE_FROM_ABI void swap(__forward_list_base& __x)
0570 # if _LIBCPP_STD_VER >= 14
0571 _NOEXCEPT;
0572 # else
0573 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>);
0574 # endif
0575
0576 protected:
0577 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
0578
0579 private:
0580 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base&, false_type) {}
0581 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x, true_type) {
0582 if (__alloc_ != __x.__alloc_)
0583 clear();
0584 __alloc_ = __x.__alloc_;
0585 }
0586
0587 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT {}
0588 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x, true_type)
0589 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {
0590 __alloc_ = std::move(__x.__alloc_);
0591 }
0592 };
0593
0594 # ifndef _LIBCPP_CXX03_LANG
0595
0596 template <class _Tp, class _Alloc>
0597 inline __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x) noexcept(
0598 is_nothrow_move_constructible<__node_allocator>::value)
0599 : __before_begin_(std::move(__x.__before_begin_)), __alloc_(std::move(__x.__alloc_)) {
0600 __x.__before_begin()->__next_ = nullptr;
0601 }
0602
0603 template <class _Tp, class _Alloc>
0604 inline __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x, const allocator_type& __a)
0605 : __before_begin_(__begin_node()), __alloc_(__node_allocator(__a)) {
0606 if (__alloc_ == __x.__alloc_) {
0607 __before_begin()->__next_ = __x.__before_begin()->__next_;
0608 __x.__before_begin()->__next_ = nullptr;
0609 }
0610 }
0611
0612 # endif // _LIBCPP_CXX03_LANG
0613
0614 template <class _Tp, class _Alloc>
0615 __forward_list_base<_Tp, _Alloc>::~__forward_list_base() {
0616 clear();
0617 }
0618
0619 template <class _Tp, class _Alloc>
0620 inline void __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
0621 # if _LIBCPP_STD_VER >= 14
0622 _NOEXCEPT
0623 # else
0624 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
0625 # endif
0626 {
0627 std::__swap_allocator(__alloc_, __x.__alloc_);
0628 using std::swap;
0629 swap(__before_begin()->__next_, __x.__before_begin()->__next_);
0630 }
0631
0632 template <class _Tp, class _Alloc>
0633 void __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT {
0634 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) {
0635 __node_pointer __next = __p->__next_;
0636 __delete_node(__p);
0637 __p = __next;
0638 }
0639 __before_begin()->__next_ = nullptr;
0640 }
0641
0642 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
0643 class _LIBCPP_TEMPLATE_VIS forward_list : private __forward_list_base<_Tp, _Alloc> {
0644 typedef __forward_list_base<_Tp, _Alloc> __base;
0645 typedef typename __base::__node_allocator __node_allocator;
0646 typedef typename __base::__node_type __node_type;
0647 typedef typename __base::__node_traits __node_traits;
0648 typedef typename __base::__node_pointer __node_pointer;
0649 typedef typename __base::__begin_node_pointer __begin_node_pointer;
0650
0651 public:
0652 typedef _Tp value_type;
0653 typedef _Alloc allocator_type;
0654
0655 static_assert(__check_valid_allocator<allocator_type>::value, "");
0656
0657 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
0658 "Allocator::value_type must be same type as value_type");
0659
0660 static_assert(!is_same<allocator_type, __node_allocator>::value,
0661 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");
0662
0663 typedef value_type& reference;
0664 typedef const value_type& const_reference;
0665 typedef typename allocator_traits<allocator_type>::pointer pointer;
0666 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0667 typedef typename allocator_traits<allocator_type>::size_type size_type;
0668 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0669
0670 typedef typename __base::iterator iterator;
0671 typedef typename __base::const_iterator const_iterator;
0672 # if _LIBCPP_STD_VER >= 20
0673 typedef size_type __remove_return_type;
0674 # else
0675 typedef void __remove_return_type;
0676 # endif
0677
0678 _LIBCPP_HIDE_FROM_ABI forward_list() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) {
0679 } // = default;
0680 _LIBCPP_HIDE_FROM_ABI explicit forward_list(const allocator_type& __a);
0681 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n);
0682 # if _LIBCPP_STD_VER >= 14
0683 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n, const allocator_type& __a);
0684 # endif
0685 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v);
0686
0687 template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
0688 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : __base(__a) {
0689 insert_after(cbefore_begin(), __n, __v);
0690 }
0691
0692 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
0693 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l);
0694
0695 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
0696 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a);
0697
0698 # if _LIBCPP_STD_VER >= 23
0699 template <_ContainerCompatibleRange<_Tp> _Range>
0700 _LIBCPP_HIDE_FROM_ABI forward_list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
0701 : __base(__a) {
0702 prepend_range(std::forward<_Range>(__range));
0703 }
0704 # endif
0705
0706 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x);
0707 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);
0708
0709 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(const forward_list& __x);
0710
0711 # ifndef _LIBCPP_CXX03_LANG
0712 _LIBCPP_HIDE_FROM_ABI forward_list(forward_list&& __x) noexcept(is_nothrow_move_constructible<__base>::value)
0713 : __base(std::move(__x)) {}
0714 _LIBCPP_HIDE_FROM_ABI forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a);
0715
0716 _LIBCPP_HIDE_FROM_ABI forward_list(initializer_list<value_type> __il);
0717 _LIBCPP_HIDE_FROM_ABI forward_list(initializer_list<value_type> __il, const allocator_type& __a);
0718
0719 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(forward_list&& __x) noexcept(
0720 __node_traits::propagate_on_container_move_assignment::value &&
0721 is_nothrow_move_assignable<allocator_type>::value);
0722
0723 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(initializer_list<value_type> __il);
0724
0725 _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il);
0726 # endif // _LIBCPP_CXX03_LANG
0727
0728 // ~forward_list() = default;
0729
0730 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
0731 void _LIBCPP_HIDE_FROM_ABI assign(_InputIterator __f, _InputIterator __l);
0732
0733 # if _LIBCPP_STD_VER >= 23
0734 template <_ContainerCompatibleRange<_Tp> _Range>
0735 _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
0736 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
0737 }
0738 # endif
0739
0740 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);
0741
0742 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(this->__alloc_); }
0743
0744 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__base::__before_begin()->__next_); }
0745 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {
0746 return const_iterator(__base::__before_begin()->__next_);
0747 }
0748 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(nullptr); }
0749 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(nullptr); }
0750
0751 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT {
0752 return const_iterator(__base::__before_begin()->__next_);
0753 }
0754 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return const_iterator(nullptr); }
0755
0756 _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT { return iterator(__base::__before_begin()); }
0757 _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT {
0758 return const_iterator(__base::__before_begin());
0759 }
0760 _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT {
0761 return const_iterator(__base::__before_begin());
0762 }
0763
0764 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {
0765 return __base::__before_begin()->__next_ == nullptr;
0766 }
0767 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
0768 return std::min<size_type>(__node_traits::max_size(this->__alloc_), numeric_limits<difference_type>::max());
0769 }
0770
0771 _LIBCPP_HIDE_FROM_ABI reference front() {
0772 _LIBCPP_ASSERT_NON_NULL(!empty(), "forward_list::front called on an empty list");
0773 return __base::__before_begin()->__next_->__get_value();
0774 }
0775 _LIBCPP_HIDE_FROM_ABI const_reference front() const {
0776 _LIBCPP_ASSERT_NON_NULL(!empty(), "forward_list::front called on an empty list");
0777 return __base::__before_begin()->__next_->__get_value();
0778 }
0779
0780 # ifndef _LIBCPP_CXX03_LANG
0781 # if _LIBCPP_STD_VER >= 17
0782 template <class... _Args>
0783 _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args);
0784 # else
0785 template <class... _Args>
0786 _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
0787 # endif
0788 _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v);
0789 # endif // _LIBCPP_CXX03_LANG
0790 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);
0791
0792 # if _LIBCPP_STD_VER >= 23
0793 template <_ContainerCompatibleRange<_Tp> _Range>
0794 _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) {
0795 insert_range_after(cbefore_begin(), std::forward<_Range>(__range));
0796 }
0797 # endif
0798
0799 _LIBCPP_HIDE_FROM_ABI void pop_front();
0800
0801 # ifndef _LIBCPP_CXX03_LANG
0802 template <class... _Args>
0803 _LIBCPP_HIDE_FROM_ABI iterator emplace_after(const_iterator __p, _Args&&... __args);
0804
0805 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, value_type&& __v);
0806 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, initializer_list<value_type> __il) {
0807 return insert_after(__p, __il.begin(), __il.end());
0808 }
0809 # endif // _LIBCPP_CXX03_LANG
0810 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, const value_type& __v);
0811 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
0812 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
0813 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
0814
0815 # if _LIBCPP_STD_VER >= 23
0816 template <_ContainerCompatibleRange<_Tp> _Range>
0817 _LIBCPP_HIDE_FROM_ABI iterator insert_range_after(const_iterator __position, _Range&& __range) {
0818 return __insert_after_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
0819 }
0820 # endif
0821
0822 template <class _InputIterator, class _Sentinel>
0823 _LIBCPP_HIDE_FROM_ABI iterator __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l);
0824
0825 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p);
0826 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l);
0827
0828 _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x)
0829 # if _LIBCPP_STD_VER >= 14
0830 _NOEXCEPT
0831 # else
0832 _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)
0833 # endif
0834 {
0835 __base::swap(__x);
0836 }
0837
0838 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);
0839 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v);
0840 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __base::clear(); }
0841
0842 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x);
0843 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
0844 _LIBCPP_HIDE_FROM_ABI void
0845 splice_after(const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l);
0846 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x);
0847 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
0848 _LIBCPP_HIDE_FROM_ABI void
0849 splice_after(const_iterator __p, forward_list& __x, const_iterator __f, const_iterator __l);
0850 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __v);
0851 template <class _Predicate>
0852 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Predicate __pred);
0853 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }
0854 template <class _BinaryPredicate>
0855 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred);
0856 # ifndef _LIBCPP_CXX03_LANG
0857 _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x) { merge(__x, __less<>()); }
0858 template <class _Compare>
0859 _LIBCPP_HIDE_FROM_ABI void merge(forward_list&& __x, _Compare __comp) {
0860 merge(__x, std::move(__comp));
0861 }
0862 # endif // _LIBCPP_CXX03_LANG
0863 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x) { merge(__x, __less<>()); }
0864 template <class _Compare>
0865 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp);
0866 _LIBCPP_HIDE_FROM_ABI void sort() { sort(__less<>()); }
0867 template <class _Compare>
0868 _LIBCPP_HIDE_FROM_ABI void sort(_Compare __comp);
0869 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;
0870
0871 private:
0872 # ifndef _LIBCPP_CXX03_LANG
0873 _LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, true_type)
0874 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
0875 _LIBCPP_HIDE_FROM_ABI void __move_assign(forward_list& __x, false_type);
0876 # endif // _LIBCPP_CXX03_LANG
0877
0878 template <class _Iter, class _Sent>
0879 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iter __f, _Sent __l);
0880
0881 template <class _Compare>
0882 static _LIBCPP_HIDE_FROM_ABI __node_pointer __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
0883
0884 // TODO: Make this _LIBCPP_HIDE_FROM_ABI
0885 template <class _Compare>
0886 static _LIBCPP_HIDDEN __node_pointer __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
0887 };
0888
0889 # if _LIBCPP_STD_VER >= 17
0890 template <class _InputIterator,
0891 class _Alloc = allocator<__iter_value_type<_InputIterator>>,
0892 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0893 class = enable_if_t<__is_allocator<_Alloc>::value> >
0894 forward_list(_InputIterator, _InputIterator) -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
0895
0896 template <class _InputIterator,
0897 class _Alloc,
0898 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0899 class = enable_if_t<__is_allocator<_Alloc>::value> >
0900 forward_list(_InputIterator, _InputIterator, _Alloc) -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
0901 # endif
0902
0903 # if _LIBCPP_STD_VER >= 23
0904 template <ranges::input_range _Range,
0905 class _Alloc = allocator<ranges::range_value_t<_Range>>,
0906 class = enable_if_t<__is_allocator<_Alloc>::value> >
0907 forward_list(from_range_t, _Range&&, _Alloc = _Alloc()) -> forward_list<ranges::range_value_t<_Range>, _Alloc>;
0908 # endif
0909
0910 template <class _Tp, class _Alloc>
0911 inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : __base(__a) {}
0912
0913 template <class _Tp, class _Alloc>
0914 forward_list<_Tp, _Alloc>::forward_list(size_type __n) {
0915 if (__n > 0) {
0916 for (__begin_node_pointer __p = __base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) {
0917 __p->__next_ = this->__create_node(/* next = */ nullptr);
0918 }
0919 }
0920 }
0921
0922 # if _LIBCPP_STD_VER >= 14
0923 template <class _Tp, class _Alloc>
0924 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const allocator_type& __base_alloc) : __base(__base_alloc) {
0925 if (__n > 0) {
0926 for (__begin_node_pointer __p = __base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) {
0927 __p->__next_ = this->__create_node(/* next = */ nullptr);
0928 }
0929 }
0930 }
0931 # endif
0932
0933 template <class _Tp, class _Alloc>
0934 forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) {
0935 insert_after(cbefore_begin(), __n, __v);
0936 }
0937
0938 template <class _Tp, class _Alloc>
0939 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
0940 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) {
0941 insert_after(cbefore_begin(), __f, __l);
0942 }
0943
0944 template <class _Tp, class _Alloc>
0945 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
0946 forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
0947 : __base(__a) {
0948 insert_after(cbefore_begin(), __f, __l);
0949 }
0950
0951 template <class _Tp, class _Alloc>
0952 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
0953 : __base(__node_traits::select_on_container_copy_construction(__x.__alloc_)) {
0954 insert_after(cbefore_begin(), __x.begin(), __x.end());
0955 }
0956
0957 template <class _Tp, class _Alloc>
0958 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a)
0959 : __base(__a) {
0960 insert_after(cbefore_begin(), __x.begin(), __x.end());
0961 }
0962
0963 template <class _Tp, class _Alloc>
0964 forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) {
0965 if (this != std::addressof(__x)) {
0966 __base::__copy_assign_alloc(__x);
0967 assign(__x.begin(), __x.end());
0968 }
0969 return *this;
0970 }
0971
0972 # ifndef _LIBCPP_CXX03_LANG
0973 template <class _Tp, class _Alloc>
0974 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x, const __type_identity_t<allocator_type>& __a)
0975 : __base(std::move(__x), __a) {
0976 if (this->__alloc_ != __x.__alloc_) {
0977 typedef move_iterator<iterator> _Ip;
0978 insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
0979 }
0980 }
0981
0982 template <class _Tp, class _Alloc>
0983 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il) {
0984 insert_after(cbefore_begin(), __il.begin(), __il.end());
0985 }
0986
0987 template <class _Tp, class _Alloc>
0988 forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il, const allocator_type& __a) : __base(__a) {
0989 insert_after(cbefore_begin(), __il.begin(), __il.end());
0990 }
0991
0992 template <class _Tp, class _Alloc>
0993 void forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
0994 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
0995 clear();
0996 __base::__move_assign_alloc(__x);
0997 __base::__before_begin()->__next_ = __x.__before_begin()->__next_;
0998 __x.__before_begin()->__next_ = nullptr;
0999 }
1000
1001 template <class _Tp, class _Alloc>
1002 void forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type) {
1003 if (this->__alloc_ == __x.__alloc_)
1004 __move_assign(__x, true_type());
1005 else {
1006 typedef move_iterator<iterator> _Ip;
1007 assign(_Ip(__x.begin()), _Ip(__x.end()));
1008 }
1009 }
1010
1011 template <class _Tp, class _Alloc>
1012 inline forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(forward_list&& __x) _NOEXCEPT_(
1013 __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<allocator_type>::value) {
1014 __move_assign(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1015 return *this;
1016 }
1017
1018 template <class _Tp, class _Alloc>
1019 inline forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il) {
1020 assign(__il.begin(), __il.end());
1021 return *this;
1022 }
1023
1024 # endif // _LIBCPP_CXX03_LANG
1025
1026 template <class _Tp, class _Alloc>
1027 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
1028 void forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) {
1029 __assign_with_sentinel(__f, __l);
1030 }
1031
1032 template <class _Tp, class _Alloc>
1033 template <class _Iter, class _Sent>
1034 _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::__assign_with_sentinel(_Iter __f, _Sent __l) {
1035 iterator __i = before_begin();
1036 iterator __j = std::next(__i);
1037 iterator __e = end();
1038 for (; __j != __e && __f != __l; ++__i, (void)++__j, ++__f)
1039 *__j = *__f;
1040 if (__j == __e)
1041 __insert_after_with_sentinel(__i, std::move(__f), std::move(__l));
1042 else
1043 erase_after(__i, __e);
1044 }
1045
1046 template <class _Tp, class _Alloc>
1047 void forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) {
1048 iterator __i = before_begin();
1049 iterator __j = std::next(__i);
1050 iterator __e = end();
1051 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
1052 *__j = __v;
1053 if (__j == __e)
1054 insert_after(__i, __n, __v);
1055 else
1056 erase_after(__i, __e);
1057 }
1058
1059 # ifndef _LIBCPP_CXX03_LANG
1060
1061 template <class _Tp, class _Alloc>
1062 inline void forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il) {
1063 assign(__il.begin(), __il.end());
1064 }
1065
1066 template <class _Tp, class _Alloc>
1067 template <class... _Args>
1068 # if _LIBCPP_STD_VER >= 17
1069 typename forward_list<_Tp, _Alloc>::reference
1070 # else
1071 void
1072 # endif
1073 forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args) {
1074 __base::__before_begin()->__next_ =
1075 this->__create_node(/* next = */ __base::__before_begin()->__next_, std::forward<_Args>(__args)...);
1076 # if _LIBCPP_STD_VER >= 17
1077 return __base::__before_begin()->__next_->__get_value();
1078 # endif
1079 }
1080
1081 template <class _Tp, class _Alloc>
1082 void forward_list<_Tp, _Alloc>::push_front(value_type&& __v) {
1083 __base::__before_begin()->__next_ =
1084 this->__create_node(/* next = */ __base::__before_begin()->__next_, std::move(__v));
1085 }
1086
1087 # endif // _LIBCPP_CXX03_LANG
1088
1089 template <class _Tp, class _Alloc>
1090 void forward_list<_Tp, _Alloc>::push_front(const value_type& __v) {
1091 __base::__before_begin()->__next_ = this->__create_node(/* next = */ __base::__before_begin()->__next_, __v);
1092 }
1093
1094 template <class _Tp, class _Alloc>
1095 void forward_list<_Tp, _Alloc>::pop_front() {
1096 _LIBCPP_ASSERT_NON_NULL(!empty(), "forward_list::pop_front called on an empty list");
1097 __node_pointer __p = __base::__before_begin()->__next_;
1098 __base::__before_begin()->__next_ = __p->__next_;
1099 this->__delete_node(__p);
1100 }
1101
1102 # ifndef _LIBCPP_CXX03_LANG
1103
1104 template <class _Tp, class _Alloc>
1105 template <class... _Args>
1106 typename forward_list<_Tp, _Alloc>::iterator
1107 forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args) {
1108 __begin_node_pointer const __r = __p.__get_begin();
1109 __r->__next_ = this->__create_node(/* next = */ __r->__next_, std::forward<_Args>(__args)...);
1110 return iterator(__r->__next_);
1111 }
1112
1113 template <class _Tp, class _Alloc>
1114 typename forward_list<_Tp, _Alloc>::iterator
1115 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v) {
1116 __begin_node_pointer const __r = __p.__get_begin();
1117 __r->__next_ = this->__create_node(/* next = */ __r->__next_, std::move(__v));
1118 return iterator(__r->__next_);
1119 }
1120
1121 # endif // _LIBCPP_CXX03_LANG
1122
1123 template <class _Tp, class _Alloc>
1124 typename forward_list<_Tp, _Alloc>::iterator
1125 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) {
1126 __begin_node_pointer const __r = __p.__get_begin();
1127 __r->__next_ = this->__create_node(/* next = */ __r->__next_, __v);
1128 return iterator(__r->__next_);
1129 }
1130
1131 template <class _Tp, class _Alloc>
1132 typename forward_list<_Tp, _Alloc>::iterator
1133 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, const value_type& __v) {
1134 __begin_node_pointer __r = __p.__get_begin();
1135 if (__n > 0) {
1136 __node_pointer __first = this->__create_node(/* next = */ nullptr, __v);
1137 __node_pointer __last = __first;
1138 # if _LIBCPP_HAS_EXCEPTIONS
1139 try {
1140 # endif // _LIBCPP_HAS_EXCEPTIONS
1141 for (--__n; __n != 0; --__n, __last = __last->__next_) {
1142 __last->__next_ = this->__create_node(/* next = */ nullptr, __v);
1143 }
1144 # if _LIBCPP_HAS_EXCEPTIONS
1145 } catch (...) {
1146 while (__first != nullptr) {
1147 __node_pointer __next = __first->__next_;
1148 this->__delete_node(__first);
1149 __first = __next;
1150 }
1151 throw;
1152 }
1153 # endif // _LIBCPP_HAS_EXCEPTIONS
1154 __last->__next_ = __r->__next_;
1155 __r->__next_ = __first;
1156 __r = static_cast<__begin_node_pointer>(__last);
1157 }
1158 return iterator(__r);
1159 }
1160
1161 template <class _Tp, class _Alloc>
1162 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >
1163 typename forward_list<_Tp, _Alloc>::iterator
1164 forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l) {
1165 return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l));
1166 }
1167
1168 template <class _Tp, class _Alloc>
1169 template <class _InputIterator, class _Sentinel>
1170 _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Alloc>::iterator
1171 forward_list<_Tp, _Alloc>::__insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) {
1172 __begin_node_pointer __r = __p.__get_begin();
1173
1174 if (__f != __l) {
1175 __node_pointer __first = this->__create_node(/* next = */ nullptr, *__f);
1176 __node_pointer __last = __first;
1177
1178 # if _LIBCPP_HAS_EXCEPTIONS
1179 try {
1180 # endif // _LIBCPP_HAS_EXCEPTIONS
1181 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) {
1182 __last->__next_ = this->__create_node(/* next = */ nullptr, *__f);
1183 }
1184 # if _LIBCPP_HAS_EXCEPTIONS
1185 } catch (...) {
1186 while (__first != nullptr) {
1187 __node_pointer __next = __first->__next_;
1188 this->__delete_node(__first);
1189 __first = __next;
1190 }
1191 throw;
1192 }
1193 # endif // _LIBCPP_HAS_EXCEPTIONS
1194
1195 __last->__next_ = __r->__next_;
1196 __r->__next_ = __first;
1197 __r = static_cast<__begin_node_pointer>(__last);
1198 }
1199
1200 return iterator(__r);
1201 }
1202
1203 template <class _Tp, class _Alloc>
1204 typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) {
1205 __begin_node_pointer __p = __f.__get_begin();
1206 __node_pointer __n = __p->__next_;
1207 __p->__next_ = __n->__next_;
1208 this->__delete_node(__n);
1209 return iterator(__p->__next_);
1210 }
1211
1212 template <class _Tp, class _Alloc>
1213 typename forward_list<_Tp, _Alloc>::iterator
1214 forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) {
1215 __node_pointer __e = __l.__get_unsafe_node_pointer();
1216 if (__f != __l) {
1217 __begin_node_pointer __bp = __f.__get_begin();
1218
1219 __node_pointer __n = __bp->__next_;
1220 if (__n != __e) {
1221 __bp->__next_ = __e;
1222 do {
1223 __node_pointer __tmp = __n->__next_;
1224 this->__delete_node(__n);
1225 __n = __tmp;
1226 } while (__n != __e);
1227 }
1228 }
1229 return iterator(__e);
1230 }
1231
1232 template <class _Tp, class _Alloc>
1233 void forward_list<_Tp, _Alloc>::resize(size_type __n) {
1234 size_type __sz = 0;
1235 iterator __p = before_begin();
1236 iterator __i = begin();
1237 iterator __e = end();
1238 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1239 ;
1240 if (__i != __e)
1241 erase_after(__p, __e);
1242 else {
1243 __n -= __sz;
1244 if (__n > 0) {
1245 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) {
1246 __ptr->__next_ = this->__create_node(/* next = */ nullptr);
1247 }
1248 }
1249 }
1250 }
1251
1252 template <class _Tp, class _Alloc>
1253 void forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) {
1254 size_type __sz = 0;
1255 iterator __p = before_begin();
1256 iterator __i = begin();
1257 iterator __e = end();
1258 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
1259 ;
1260 if (__i != __e)
1261 erase_after(__p, __e);
1262 else {
1263 __n -= __sz;
1264 if (__n > 0) {
1265 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) {
1266 __ptr->__next_ = this->__create_node(/* next = */ nullptr, __v);
1267 }
1268 }
1269 }
1270 }
1271
1272 template <class _Tp, class _Alloc>
1273 void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& __x) {
1274 if (!__x.empty()) {
1275 if (__p.__get_begin()->__next_ != nullptr) {
1276 const_iterator __lm1 = __x.before_begin();
1277 while (__lm1.__get_begin()->__next_ != nullptr)
1278 ++__lm1;
1279 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1280 }
1281 __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
1282 __x.__before_begin()->__next_ = nullptr;
1283 }
1284 }
1285
1286 template <class _Tp, class _Alloc>
1287 void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& /*__other*/, const_iterator __i) {
1288 const_iterator __lm1 = std::next(__i);
1289 if (__p != __i && __p != __lm1) {
1290 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
1291 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1292 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
1293 }
1294 }
1295
1296 template <class _Tp, class _Alloc>
1297 void forward_list<_Tp, _Alloc>::splice_after(
1298 const_iterator __p, forward_list& /*__other*/, const_iterator __f, const_iterator __l) {
1299 if (__f != __l && __p != __f) {
1300 const_iterator __lm1 = __f;
1301 while (__lm1.__get_begin()->__next_ != __l.__get_begin())
1302 ++__lm1;
1303 if (__f != __lm1) {
1304 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
1305 __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
1306 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
1307 }
1308 }
1309 }
1310
1311 template <class _Tp, class _Alloc>
1312 inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x) {
1313 splice_after(__p, __x);
1314 }
1315
1316 template <class _Tp, class _Alloc>
1317 inline _LIBCPP_HIDE_FROM_ABI void
1318 forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x, const_iterator __i) {
1319 splice_after(__p, __x, __i);
1320 }
1321
1322 template <class _Tp, class _Alloc>
1323 inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(
1324 const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l) {
1325 splice_after(__p, __x, __f, __l);
1326 }
1327
1328 template <class _Tp, class _Alloc>
1329 typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove(const value_type& __v) {
1330 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1331 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1332 const iterator __e = end();
1333 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) {
1334 if (__i.__get_begin()->__next_->__get_value() == __v) {
1335 ++__count_removed;
1336 iterator __j = std::next(__i, 2);
1337 for (; __j != __e && *__j == __v; ++__j)
1338 ++__count_removed;
1339 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1340 if (__j == __e)
1341 break;
1342 __i = __j;
1343 } else
1344 ++__i;
1345 }
1346
1347 return (__remove_return_type)__count_removed;
1348 }
1349
1350 template <class _Tp, class _Alloc>
1351 template <class _Predicate>
1352 typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) {
1353 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1354 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1355 const iterator __e = end();
1356 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) {
1357 if (__pred(__i.__get_begin()->__next_->__get_value())) {
1358 ++__count_removed;
1359 iterator __j = std::next(__i, 2);
1360 for (; __j != __e && __pred(*__j); ++__j)
1361 ++__count_removed;
1362 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1363 if (__j == __e)
1364 break;
1365 __i = __j;
1366 } else
1367 ++__i;
1368 }
1369
1370 return (__remove_return_type)__count_removed;
1371 }
1372
1373 template <class _Tp, class _Alloc>
1374 template <class _BinaryPredicate>
1375 typename forward_list<_Tp, _Alloc>::__remove_return_type
1376 forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) {
1377 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
1378 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
1379 for (iterator __i = begin(), __e = end(); __i != __e;) {
1380 iterator __j = std::next(__i);
1381 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1382 ++__count_removed;
1383 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
1384 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
1385 __i = __j;
1386 }
1387
1388 return (__remove_return_type)__count_removed;
1389 }
1390
1391 template <class _Tp, class _Alloc>
1392 template <class _Compare>
1393 void forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) {
1394 if (this != std::addressof(__x)) {
1395 __base::__before_begin()->__next_ =
1396 __merge(__base::__before_begin()->__next_, __x.__before_begin()->__next_, __comp);
1397 __x.__before_begin()->__next_ = nullptr;
1398 }
1399 }
1400
1401 template <class _Tp, class _Alloc>
1402 template <class _Compare>
1403 typename forward_list<_Tp, _Alloc>::__node_pointer
1404 forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp) {
1405 if (__f1 == nullptr)
1406 return __f2;
1407 if (__f2 == nullptr)
1408 return __f1;
1409 __node_pointer __r;
1410 if (__comp(__f2->__get_value(), __f1->__get_value())) {
1411 __node_pointer __t = __f2;
1412 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))
1413 __t = __t->__next_;
1414 __r = __f2;
1415 __f2 = __t->__next_;
1416 __t->__next_ = __f1;
1417 } else
1418 __r = __f1;
1419 __node_pointer __p = __f1;
1420 __f1 = __f1->__next_;
1421 while (__f1 != nullptr && __f2 != nullptr) {
1422 if (__comp(__f2->__get_value(), __f1->__get_value())) {
1423 __node_pointer __t = __f2;
1424 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))
1425 __t = __t->__next_;
1426 __p->__next_ = __f2;
1427 __f2 = __t->__next_;
1428 __t->__next_ = __f1;
1429 }
1430 __p = __f1;
1431 __f1 = __f1->__next_;
1432 }
1433 if (__f2 != nullptr)
1434 __p->__next_ = __f2;
1435 return __r;
1436 }
1437
1438 template <class _Tp, class _Alloc>
1439 template <class _Compare>
1440 inline void forward_list<_Tp, _Alloc>::sort(_Compare __comp) {
1441 __base::__before_begin()->__next_ = __sort(__base::__before_begin()->__next_, std::distance(begin(), end()), __comp);
1442 }
1443
1444 template <class _Tp, class _Alloc>
1445 template <class _Compare>
1446 typename forward_list<_Tp, _Alloc>::__node_pointer
1447 forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, _Compare& __comp) {
1448 switch (__sz) {
1449 case 0:
1450 case 1:
1451 return __f1;
1452 case 2:
1453 if (__comp(__f1->__next_->__get_value(), __f1->__get_value())) {
1454 __node_pointer __t = __f1->__next_;
1455 __t->__next_ = __f1;
1456 __f1->__next_ = nullptr;
1457 __f1 = __t;
1458 }
1459 return __f1;
1460 }
1461 difference_type __sz1 = __sz / 2;
1462 difference_type __sz2 = __sz - __sz1;
1463 __node_pointer __t = std::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
1464 __node_pointer __f2 = __t->__next_;
1465 __t->__next_ = nullptr;
1466 return __merge(__sort(__f1, __sz1, __comp), __sort(__f2, __sz2, __comp), __comp);
1467 }
1468
1469 template <class _Tp, class _Alloc>
1470 void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT {
1471 __node_pointer __p = __base::__before_begin()->__next_;
1472 if (__p != nullptr) {
1473 __node_pointer __f = __p->__next_;
1474 __p->__next_ = nullptr;
1475 while (__f != nullptr) {
1476 __node_pointer __t = __f->__next_;
1477 __f->__next_ = __p;
1478 __p = __f;
1479 __f = __t;
1480 }
1481 __base::__before_begin()->__next_ = __p;
1482 }
1483 }
1484
1485 template <class _Tp, class _Alloc>
1486 _LIBCPP_HIDE_FROM_ABI bool operator==(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1487 typedef forward_list<_Tp, _Alloc> _Cp;
1488 typedef typename _Cp::const_iterator _Ip;
1489 _Ip __ix = __x.begin();
1490 _Ip __ex = __x.end();
1491 _Ip __iy = __y.begin();
1492 _Ip __ey = __y.end();
1493 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
1494 if (!(*__ix == *__iy))
1495 return false;
1496 return (__ix == __ex) == (__iy == __ey);
1497 }
1498
1499 # if _LIBCPP_STD_VER <= 17
1500
1501 template <class _Tp, class _Alloc>
1502 inline _LIBCPP_HIDE_FROM_ABI bool
1503 operator!=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1504 return !(__x == __y);
1505 }
1506
1507 template <class _Tp, class _Alloc>
1508 inline _LIBCPP_HIDE_FROM_ABI bool
1509 operator<(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1510 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1511 }
1512
1513 template <class _Tp, class _Alloc>
1514 inline _LIBCPP_HIDE_FROM_ABI bool
1515 operator>(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1516 return __y < __x;
1517 }
1518
1519 template <class _Tp, class _Alloc>
1520 inline _LIBCPP_HIDE_FROM_ABI bool
1521 operator>=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1522 return !(__x < __y);
1523 }
1524
1525 template <class _Tp, class _Alloc>
1526 inline _LIBCPP_HIDE_FROM_ABI bool
1527 operator<=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {
1528 return !(__y < __x);
1529 }
1530
1531 # else // #if _LIBCPP_STD_VER <= 17
1532
1533 template <class _Tp, class _Allocator>
1534 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Tp>
1535 operator<=>(const forward_list<_Tp, _Allocator>& __x, const forward_list<_Tp, _Allocator>& __y) {
1536 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1537 }
1538
1539 # endif // #if _LIBCPP_STD_VER <= 17
1540
1541 template <class _Tp, class _Alloc>
1542 inline _LIBCPP_HIDE_FROM_ABI void swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
1543 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1544 __x.swap(__y);
1545 }
1546
1547 # if _LIBCPP_STD_VER >= 20
1548 template <class _Tp, class _Allocator, class _Predicate>
1549 inline _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Allocator>::size_type
1550 erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) {
1551 return __c.remove_if(__pred);
1552 }
1553
1554 template <class _Tp, class _Allocator, class _Up>
1555 inline _LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Allocator>::size_type
1556 erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) {
1557 return std::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
1558 }
1559 # endif
1560
1561 template <class _Tp, class _Allocator>
1562 struct __container_traits<forward_list<_Tp, _Allocator> > {
1563 // http://eel.is/c++draft/container.reqmts
1564 // Unless otherwise specified (see [associative.reqmts.except], [unord.req.except], [deque.modifiers],
1565 // [inplace.vector.modifiers], and [vector.modifiers]) all container types defined in this Clause meet the following
1566 // additional requirements:
1567 // - If an exception is thrown by an insert() or emplace() function while inserting a single element, that
1568 // function has no effects.
1569 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1570 };
1571
1572 _LIBCPP_END_NAMESPACE_STD
1573
1574 # if _LIBCPP_STD_VER >= 17
1575 _LIBCPP_BEGIN_NAMESPACE_STD
1576 namespace pmr {
1577 template <class _ValueT>
1578 using forward_list _LIBCPP_AVAILABILITY_PMR = std::forward_list<_ValueT, polymorphic_allocator<_ValueT>>;
1579 } // namespace pmr
1580 _LIBCPP_END_NAMESPACE_STD
1581 # endif
1582
1583 _LIBCPP_POP_MACROS
1584
1585 # if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1586 # include <algorithm>
1587 # include <atomic>
1588 # include <concepts>
1589 # include <cstdint>
1590 # include <cstdlib>
1591 # include <cstring>
1592 # include <functional>
1593 # include <iosfwd>
1594 # include <iterator>
1595 # include <stdexcept>
1596 # include <type_traits>
1597 # include <typeinfo>
1598 # endif
1599 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
1600
1601 #endif // _LIBCPP_FORWARD_LIST
