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