1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___PSTL_BACKENDS_DEFAULT_H
10#define _LIBCPP___PSTL_BACKENDS_DEFAULT_H
11
12#include <__algorithm/copy_n.h>
13#include <__algorithm/equal.h>
14#include <__algorithm/fill_n.h>
15#include <__algorithm/for_each_n.h>
16#include <__algorithm/is_sorted.h>
17#include <__config>
18#include <__functional/identity.h>
19#include <__functional/not_fn.h>
20#include <__functional/operations.h>
21#include <__iterator/concepts.h>
22#include <__iterator/iterator_traits.h>
23#include <__iterator/next.h>
24#include <__pstl/backend_fwd.h>
25#include <__pstl/dispatch.h>
26#include <__utility/empty.h>
27#include <__utility/forward.h>
28#include <__utility/move.h>
29#include <optional>
30
31#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
32# pragma GCC system_header
33#endif
34
35_LIBCPP_PUSH_MACROS
36#include <__undef_macros>
37
38#if _LIBCPP_STD_VER >= 17
39
40_LIBCPP_BEGIN_NAMESPACE_STD
41namespace __pstl {
42
43//
44// This file provides an incomplete PSTL backend that implements all of the PSTL algorithms
45// based on a smaller set of basis operations.
46//
47// It is intended as a building block for other PSTL backends that implement some operations more
48// efficiently but may not want to define the full set of PSTL algorithms.
49//
50// This backend implements all the PSTL algorithms based on the following basis operations:
51//
52// find_if family
53// --------------
54// - find
55// - find_if_not
56// - any_of
57// - all_of
58// - none_of
59// - is_partitioned
60//
61// for_each family
62// ---------------
63// - for_each_n
64// - fill
65// - fill_n
66// - replace
67// - replace_if
68// - generate
69// - generate_n
70//
71// merge family
72// ------------
73// No other algorithms based on merge
74//
75// stable_sort family
76// ------------------
77// - sort
78//
79// transform_reduce and transform_reduce_binary family
80// ---------------------------------------------------
81// - count_if
82// - count
83// - equal(3 legs)
84// - equal
85// - is_sorted
86// - reduce
87//
88// transform and transform_binary family
89// -------------------------------------
90// - replace_copy_if
91// - replace_copy
92// - move
93// - copy
94// - copy_n
95// - rotate_copy
96//
97
98//////////////////////////////////////////////////////////////
99// find_if family
100//////////////////////////////////////////////////////////////
101template <class _ExecutionPolicy>
102struct __find<__default_backend_tag, _ExecutionPolicy> {
103 template <class _Policy, class _ForwardIterator, class _Tp>
104 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
105 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {
106 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
107 return _FindIf()(
108 __policy, std::move(__first), std::move(__last), [&](__iterator_reference<_ForwardIterator> __element) {
109 return __element == __value;
110 });
111 }
112};
113
114template <class _ExecutionPolicy>
115struct __find_if_not<__default_backend_tag, _ExecutionPolicy> {
116 template <class _Policy, class _ForwardIterator, class _Pred>
117 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
118 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
119 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
120 return _FindIf()(__policy, __first, __last, std::not_fn(std::forward<_Pred>(__pred)));
121 }
122};
123
124template <class _ExecutionPolicy>
125struct __any_of<__default_backend_tag, _ExecutionPolicy> {
126 template <class _Policy, class _ForwardIterator, class _Pred>
127 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
128 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
129 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
130 auto __res = _FindIf()(__policy, __first, __last, std::forward<_Pred>(__pred));
131 if (!__res)
132 return nullopt;
133 return *__res != __last;
134 }
135};
136
137template <class _ExecutionPolicy>
138struct __all_of<__default_backend_tag, _ExecutionPolicy> {
139 template <class _Policy, class _ForwardIterator, class _Pred>
140 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
141 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
142 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
143 auto __res = _AnyOf()(__policy, __first, __last, [&](__iterator_reference<_ForwardIterator> __value) {
144 return !__pred(__value);
145 });
146 if (!__res)
147 return nullopt;
148 return !*__res;
149 }
150};
151
152template <class _ExecutionPolicy>
153struct __none_of<__default_backend_tag, _ExecutionPolicy> {
154 template <class _Policy, class _ForwardIterator, class _Pred>
155 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
156 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
157 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
158 auto __res = _AnyOf()(__policy, __first, __last, std::forward<_Pred>(__pred));
159 if (!__res)
160 return nullopt;
161 return !*__res;
162 }
163};
164
165template <class _ExecutionPolicy>
166struct __is_partitioned<__default_backend_tag, _ExecutionPolicy> {
167 template <class _Policy, class _ForwardIterator, class _Pred>
168 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
169 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
170 using _FindIfNot = __dispatch<__find_if_not, __current_configuration, _ExecutionPolicy>;
171 auto __maybe_first = _FindIfNot()(__policy, std::move(__first), __last, __pred);
172 if (__maybe_first == nullopt)
173 return nullopt;
174
175 __first = *__maybe_first;
176 if (__first == __last)
177 return true;
178 ++__first;
179 using _NoneOf = __dispatch<__none_of, __current_configuration, _ExecutionPolicy>;
180 return _NoneOf()(__policy, std::move(__first), std::move(__last), __pred);
181 }
182};
183
184//////////////////////////////////////////////////////////////
185// for_each family
186//////////////////////////////////////////////////////////////
187template <class _ExecutionPolicy>
188struct __for_each_n<__default_backend_tag, _ExecutionPolicy> {
189 template <class _Policy, class _ForwardIterator, class _Size, class _Function>
190 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
191 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) const noexcept {
192 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
193 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
194 _ForwardIterator __last = __first + __size;
195 return _ForEach()(__policy, std::move(__first), std::move(__last), std::move(__func));
196 } else {
197 // Otherwise, use the serial algorithm to avoid doing two passes over the input
198 std::for_each_n(std::move(__first), __size, std::move(__func));
199 return __empty{};
200 }
201 }
202};
203
204template <class _ExecutionPolicy>
205struct __fill<__default_backend_tag, _ExecutionPolicy> {
206 template <class _Policy, class _ForwardIterator, class _Tp>
207 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
208 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
209 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
210 using _Ref = __iterator_reference<_ForwardIterator>;
211 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; });
212 }
213};
214
215template <class _ExecutionPolicy>
216struct __fill_n<__default_backend_tag, _ExecutionPolicy> {
217 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
218 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
219 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept {
220 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
221 using _Fill = __dispatch<__fill, __current_configuration, _ExecutionPolicy>;
222 _ForwardIterator __last = __first + __n;
223 return _Fill()(__policy, std::move(__first), std::move(__last), __value);
224 } else {
225 // Otherwise, use the serial algorithm to avoid doing two passes over the input
226 std::fill_n(std::move(__first), __n, __value);
227 return optional<__empty>{__empty{}};
228 }
229 }
230};
231
232template <class _ExecutionPolicy>
233struct __replace<__default_backend_tag, _ExecutionPolicy> {
234 template <class _Policy, class _ForwardIterator, class _Tp>
235 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
236 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new)
237 const noexcept {
238 using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>;
239 using _Ref = __iterator_reference<_ForwardIterator>;
240 return _ReplaceIf()(
241 __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new);
242 }
243};
244
245template <class _ExecutionPolicy>
246struct __replace_if<__default_backend_tag, _ExecutionPolicy> {
247 template <class _Policy, class _ForwardIterator, class _Pred, class _Tp>
248 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
249 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value)
250 const noexcept {
251 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
252 using _Ref = __iterator_reference<_ForwardIterator>;
253 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {
254 if (__pred(__element))
255 __element = __new_value;
256 });
257 }
258};
259
260template <class _ExecutionPolicy>
261struct __generate<__default_backend_tag, _ExecutionPolicy> {
262 template <class _Policy, class _ForwardIterator, class _Generator>
263 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
264 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept {
265 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
266 using _Ref = __iterator_reference<_ForwardIterator>;
267 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); });
268 }
269};
270
271template <class _ExecutionPolicy>
272struct __generate_n<__default_backend_tag, _ExecutionPolicy> {
273 template <class _Policy, class _ForwardIterator, class _Size, class _Generator>
274 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
275 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept {
276 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
277 using _Ref = __iterator_reference<_ForwardIterator>;
278 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); });
279 }
280};
281
282//////////////////////////////////////////////////////////////
283// stable_sort family
284//////////////////////////////////////////////////////////////
285template <class _ExecutionPolicy>
286struct __sort<__default_backend_tag, _ExecutionPolicy> {
287 template <class _Policy, class _RandomAccessIterator, class _Comp>
288 _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
289 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
290 using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>;
291 return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
292 }
293};
294
295//////////////////////////////////////////////////////////////
296// transform_reduce family
297//////////////////////////////////////////////////////////////
298template <class _ExecutionPolicy>
299struct __count_if<__default_backend_tag, _ExecutionPolicy> {
300 template <class _Policy, class _ForwardIterator, class _Predicate>
301 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>> operator()(
302 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept {
303 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
304 using _DiffT = __iterator_difference_type<_ForwardIterator>;
305 using _Ref = __iterator_reference<_ForwardIterator>;
306 return _TransformReduce()(
307 __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT {
308 return __pred(__element) ? _DiffT(1) : _DiffT(0);
309 });
310 }
311};
312
313template <class _ExecutionPolicy>
314struct __count<__default_backend_tag, _ExecutionPolicy> {
315 template <class _Policy, class _ForwardIterator, class _Tp>
316 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>>
317 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
318 using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>;
319 using _Ref = __iterator_reference<_ForwardIterator>;
320 return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool {
321 return __element == __value;
322 });
323 }
324};
325
326template <class _ExecutionPolicy>
327struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> {
328 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
329 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
330 operator()(_Policy&& __policy,
331 _ForwardIterator1 __first1,
332 _ForwardIterator1 __last1,
333 _ForwardIterator2 __first2,
334 _Predicate&& __pred) const noexcept {
335 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;
336 return _TransformReduce()(
337 __policy,
338 std::move(__first1),
339 std::move(__last1),
340 std::move(__first2),
341 true,
342 std::logical_and{},
343 std::forward<_Predicate>(__pred));
344 }
345};
346
347template <class _ExecutionPolicy>
348struct __equal<__default_backend_tag, _ExecutionPolicy> {
349 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
350 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
351 operator()(_Policy&& __policy,
352 _ForwardIterator1 __first1,
353 _ForwardIterator1 __last1,
354 _ForwardIterator2 __first2,
355 _ForwardIterator2 __last2,
356 _Predicate&& __pred) const noexcept {
357 if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value &&
358 __has_random_access_iterator_category<_ForwardIterator2>::value) {
359 if (__last1 - __first1 != __last2 - __first2)
360 return false;
361 // Fall back to the 3 legged algorithm
362 using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>;
363 return _Equal3Leg()(
364 __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred));
365 } else {
366 // If we don't have random access, fall back to the serial algorithm cause we can't do much
367 return std::equal(
368 std::move(__first1),
369 std::move(__last1),
370 std::move(__first2),
371 std::move(__last2),
372 std::forward<_Predicate>(__pred));
373 }
374 }
375};
376
377template <class _ExecutionPolicy>
378struct __reduce<__default_backend_tag, _ExecutionPolicy> {
379 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation>
380 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp>
381 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op)
382 const noexcept {
383 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
384 return _TransformReduce()(
385 __policy,
386 std::move(__first),
387 std::move(__last),
388 std::move(__init),
389 std::forward<_BinaryOperation>(__op),
390 __identity{});
391 }
392};
393
394template <class _ExecutionPolicy>
395struct __is_sorted<__default_backend_tag, _ExecutionPolicy> {
396 template <class _Policy, class _ForwardIterator, class _Comp>
397 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
398 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept {
399 if constexpr (__has_bidirectional_iterator_category<_ForwardIterator>::value) {
400 if (__first == __last)
401 return true; // Empty, sorted by definition
402 _ForwardIterator __first2 = std::next(__first);
403 if (__first2 == __last)
404 return true; // Only one element, sorted by definition
405 --__last; // Make two iterator ranges: [__first, __first + n - 1) and [__first + 1, __first + n)
406 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;
407 using _Ref = __iterator_reference<_ForwardIterator>;
408 return _TransformReduce()(
409 __policy,
410 std::move(__first),
411 std::move(__last),
412 std::move(__first2),
413 true,
414 std::logical_and{},
415 [&](_Ref __left, _Ref __right) -> bool { return !__comp(__right, __left); });
416 } else {
417 // Currently anything outside bidirectional iterators has to be processed serially
418 return std::is_sorted(std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
419 }
420 }
421};
422
423//////////////////////////////////////////////////////////////
424// transform family
425//////////////////////////////////////////////////////////////
426template <class _ExecutionPolicy>
427struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> {
428 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp>
429 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
430 operator()(_Policy&& __policy,
431 _ForwardIterator __first,
432 _ForwardIterator __last,
433 _ForwardOutIterator __out_it,
434 _Pred&& __pred,
435 _Tp const& __new_value) const noexcept {
436 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
437 using _Ref = __iterator_reference<_ForwardIterator>;
438 auto __res =
439 _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) {
440 return __pred(__element) ? __new_value : __element;
441 });
442 if (__res == nullopt)
443 return nullopt;
444 return __empty{};
445 }
446};
447
448template <class _ExecutionPolicy>
449struct __replace_copy<__default_backend_tag, _ExecutionPolicy> {
450 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp>
451 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
452 operator()(_Policy&& __policy,
453 _ForwardIterator __first,
454 _ForwardIterator __last,
455 _ForwardOutIterator __out_it,
456 _Tp const& __old_value,
457 _Tp const& __new_value) const noexcept {
458 using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>;
459 using _Ref = __iterator_reference<_ForwardIterator>;
460 return _ReplaceCopyIf()(
461 __policy,
462 std::move(__first),
463 std::move(__last),
464 std::move(__out_it),
465 [&](_Ref __element) { return __element == __old_value; },
466 __new_value);
467 }
468};
469
470// TODO: Use the std::copy/move shenanigans to forward to std::memmove
471// Investigate whether we want to still forward to std::transform(policy)
472// in that case for the execution::par part, or whether we actually want
473// to run everything serially in that case.
474template <class _ExecutionPolicy>
475struct __move<__default_backend_tag, _ExecutionPolicy> {
476 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
477 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
478 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
479 const noexcept {
480 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
481 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) {
482 return std::move(__element);
483 });
484 }
485};
486
487// TODO: Use the std::copy/move shenanigans to forward to std::memmove
488template <class _ExecutionPolicy>
489struct __copy<__default_backend_tag, _ExecutionPolicy> {
490 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
491 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
492 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
493 const noexcept {
494 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
495 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity());
496 }
497};
498
499template <class _ExecutionPolicy>
500struct __copy_n<__default_backend_tag, _ExecutionPolicy> {
501 template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator>
502 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
503 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept {
504 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
505 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
506 _ForwardIterator __last = __first + __n;
507 return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it));
508 } else {
509 // Otherwise, use the serial algorithm to avoid doing two passes over the input
510 return std::copy_n(std::move(__first), __n, std::move(__out_it));
511 }
512 }
513};
514
515template <class _ExecutionPolicy>
516struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> {
517 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
518 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
519 operator()(_Policy&& __policy,
520 _ForwardIterator __first,
521 _ForwardIterator __middle,
522 _ForwardIterator __last,
523 _ForwardOutIterator __out_it) const noexcept {
524 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
525 auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it));
526 if (__result_mid == nullopt)
527 return nullopt;
528 return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid));
529 }
530};
531
532} // namespace __pstl
533_LIBCPP_END_NAMESPACE_STD
534
535#endif // _LIBCPP_STD_VER >= 17
536
537_LIBCPP_POP_MACROS
538
539#endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H
540