[libc++][PSTL] Implement std::replace{,_if,_copy,_copy_if}
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits
Differential Revision: https://reviews.llvm.org/D151841
GitOrigin-RevId: 51131edf83e4d560f19474b8147efc5fc1118295
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index 62d6ea5..89b7995 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -91,6 +91,7 @@
__algorithm/pstl_for_each.h
__algorithm/pstl_frontend_dispatch.h
__algorithm/pstl_merge.h
+ __algorithm/pstl_replace.h
__algorithm/pstl_stable_sort.h
__algorithm/pstl_transform.h
__algorithm/push_heap.h
diff --git a/include/__algorithm/pstl_backend.h b/include/__algorithm/pstl_backend.h
index 73e2c48..7b2edb6 100644
--- a/include/__algorithm/pstl_backend.h
+++ b/include/__algorithm/pstl_backend.h
@@ -119,6 +119,28 @@
template <class _ExecutionPolicy, class _Iterator, class _Predicate>
__iter_diff_t<_Iterator> __pstl_count_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
+ template <class _ExecutionPolicy, class _Iterator, class _Tp>
+ void __pstl_replace(_Backend, _Iterator __first, _Iterator __last, const _Tp& __old_value, const _Tp& __new_value);
+
+ template <class _ExecutionPolicy, class _Iterator, class _Pred, class _Tp>
+ void __pstl_replace_if(_Backend, _Iterator __first, _Iterator __last, _Pred __pred, const _Tp& __new_value);
+
+ template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Tp>
+ void __pstl_replace_copy(_Backend,
+ _Iterator __first,
+ _Iterator __last,
+ _OutIterator __result,
+ const _Tp& __old_value,
+ const _Tp& __new_value);
+
+ template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Pred, class _Tp>
+ void __pstl_replace_copy_if(_Backend,
+ _Iterator __first,
+ _Iterator __last,
+ _OutIterator __result,
+ _Pred __pred,
+ const _Tp& __new_value);
+
// TODO: Complete this list
*/
diff --git a/include/__algorithm/pstl_replace.h b/include/__algorithm/pstl_replace.h
new file mode 100644
index 0000000..9f8a44b
--- /dev/null
+++ b/include/__algorithm/pstl_replace.h
@@ -0,0 +1,162 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_PSTL_REPLACE_H
+#define _LIBCPP___ALGORITHM_PSTL_REPLACE_H
+
+#include <__algorithm/pstl_backend.h>
+#include <__algorithm/pstl_for_each.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class>
+void __pstl_replace_if();
+
+template <class _ExecutionPolicy,
+ class _ForwardIterator,
+ class _Pred,
+ class _Tp,
+ class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>,
+ enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+replace_if(_ExecutionPolicy&& __policy,
+ _ForwardIterator __first,
+ _ForwardIterator __last,
+ _Pred __pred,
+ const _Tp& __new_value) {
+ std::__pstl_frontend_dispatch(
+ _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_if),
+ [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred, const _Tp& __g_new_value) {
+ std::for_each(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __element) {
+ if (__g_pred(__element))
+ __element = __g_new_value;
+ });
+ },
+ std::move(__first),
+ std::move(__last),
+ std::move(__pred),
+ __new_value);
+}
+
+template <class>
+void __pstl_replace();
+
+template <class _ExecutionPolicy,
+ class _ForwardIterator,
+ class _Tp,
+ class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>,
+ enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+replace(_ExecutionPolicy&& __policy,
+ _ForwardIterator __first,
+ _ForwardIterator __last,
+ const _Tp& __old_value,
+ const _Tp& __new_value) {
+ std::__pstl_frontend_dispatch(
+ _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace),
+ [&__policy](
+ _ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_old_value, const _Tp& __g_new_value) {
+ std::replace_if(
+ __policy,
+ std::move(__g_first),
+ std::move(__g_last),
+ [&](__iter_reference<_ForwardIterator> __element) { return __element == __g_old_value; },
+ __g_new_value);
+ },
+ std::move(__first),
+ std::move(__last),
+ __old_value,
+ __new_value);
+}
+
+template <class>
+void __pstl_replace_copy_if();
+
+template <class _ExecutionPolicy,
+ class _ForwardIterator,
+ class _ForwardOutIterator,
+ class _Pred,
+ class _Tp,
+ class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>,
+ enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void replace_copy_if(
+ _ExecutionPolicy&& __policy,
+ _ForwardIterator __first,
+ _ForwardIterator __last,
+ _ForwardOutIterator __result,
+ _Pred __pred,
+ const _Tp& __new_value) {
+ std::__pstl_frontend_dispatch(
+ _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_copy_if),
+ [&__policy](_ForwardIterator __g_first,
+ _ForwardIterator __g_last,
+ _ForwardOutIterator __g_result,
+ _Pred __g_pred,
+ const _Tp& __g_new_value) {
+ std::transform(__policy, __g_first, __g_last, __g_result, [&](__iter_reference<_ForwardIterator> __element) {
+ return __g_pred(__element) ? __g_new_value : __element;
+ });
+ },
+ std::move(__first),
+ std::move(__last),
+ std::move(__result),
+ std::move(__pred),
+ __new_value);
+}
+
+template <class>
+void __pstl_replace_copy();
+
+template <class _ExecutionPolicy,
+ class _ForwardIterator,
+ class _ForwardOutIterator,
+ class _Tp,
+ class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>,
+ enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void replace_copy(
+ _ExecutionPolicy&& __policy,
+ _ForwardIterator __first,
+ _ForwardIterator __last,
+ _ForwardOutIterator __result,
+ const _Tp& __old_value,
+ const _Tp& __new_value) {
+ std::__pstl_frontend_dispatch(
+ _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_copy),
+ [&__policy](_ForwardIterator __g_first,
+ _ForwardIterator __g_last,
+ _ForwardOutIterator __g_result,
+ const _Tp& __g_old_value,
+ const _Tp& __g_new_value) {
+ return std::replace_copy_if(
+ __policy,
+ std::move(__g_first),
+ std::move(__g_last),
+ std::move(__g_result),
+ [&](__iter_reference<_ForwardIterator> __element) { return __element == __g_old_value; },
+ __g_new_value);
+ },
+ std::move(__first),
+ std::move(__last),
+ std::move(__result),
+ __old_value,
+ __new_value);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_REPLACE_H
diff --git a/include/__pstl/internal/glue_algorithm_impl.h b/include/__pstl/internal/glue_algorithm_impl.h
index 4b17133..8e8f253 100644
--- a/include/__pstl/internal/glue_algorithm_impl.h
+++ b/include/__pstl/internal/glue_algorithm_impl.h
@@ -213,115 +213,6 @@
});
}
-// [alg.transform]
-
-template <class _ExecutionPolicy,
- class _ForwardIterator1,
- class _ForwardIterator2,
- class _ForwardIterator,
- class _BinaryOperation>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
-transform(_ExecutionPolicy&& __exec,
- _ForwardIterator1 __first1,
- _ForwardIterator1 __last1,
- _ForwardIterator2 __first2,
- _ForwardIterator __result,
- _BinaryOperation __op) {
- typedef typename iterator_traits<_ForwardIterator1>::reference _Input1Type;
- typedef typename iterator_traits<_ForwardIterator2>::reference _Input2Type;
- typedef typename iterator_traits<_ForwardIterator>::reference _OutputType;
-
- auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __result);
-
- return __pstl::__internal::__pattern_walk3(
- __dispatch_tag,
- std::forward<_ExecutionPolicy>(__exec),
- __first1,
- __last1,
- __first2,
- __result,
- [__op](_Input1Type x, _Input2Type y, _OutputType z) mutable { z = __op(x, y); });
-}
-
-// [alg.replace]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
-replace_if(_ExecutionPolicy&& __exec,
- _ForwardIterator __first,
- _ForwardIterator __last,
- _UnaryPredicate __pred,
- const _Tp& __new_value) {
- typedef typename iterator_traits<_ForwardIterator>::reference _ElementType;
-
- auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
-
- __pstl::__internal::__pattern_walk1(
- __dispatch_tag,
- std::forward<_ExecutionPolicy>(__exec),
- __first,
- __last,
- [&__pred, &__new_value](_ElementType __elem) {
- if (__pred(__elem)) {
- __elem = __new_value;
- }
- });
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
-replace(_ExecutionPolicy&& __exec,
- _ForwardIterator __first,
- _ForwardIterator __last,
- const _Tp& __old_value,
- const _Tp& __new_value) {
- std::replace_if(
- std::forward<_ExecutionPolicy>(__exec),
- __first,
- __last,
- __pstl::__internal::__equal_value<_Tp>(__old_value),
- __new_value);
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryPredicate, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> replace_copy_if(
- _ExecutionPolicy&& __exec,
- _ForwardIterator1 __first,
- _ForwardIterator1 __last,
- _ForwardIterator2 __result,
- _UnaryPredicate __pred,
- const _Tp& __new_value) {
- typedef typename iterator_traits<_ForwardIterator1>::reference _InputType;
- typedef typename iterator_traits<_ForwardIterator2>::reference _OutputType;
-
- auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
-
- return __pstl::__internal::__pattern_walk2(
- __dispatch_tag,
- std::forward<_ExecutionPolicy>(__exec),
- __first,
- __last,
- __result,
- [__pred, &__new_value](_InputType __x, _OutputType __y) mutable { __y = __pred(__x) ? __new_value : __x; });
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> replace_copy(
- _ExecutionPolicy&& __exec,
- _ForwardIterator1 __first,
- _ForwardIterator1 __last,
- _ForwardIterator2 __result,
- const _Tp& __old_value,
- const _Tp& __new_value) {
- return std::replace_copy_if(
- std::forward<_ExecutionPolicy>(__exec),
- __first,
- __last,
- __result,
- __pstl::__internal::__equal_value<_Tp>(__old_value),
- __new_value);
-}
-
// [alg.generate]
template <class _ExecutionPolicy, class _ForwardIterator, class _Generator>
__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
diff --git a/include/algorithm b/include/algorithm
index 04a21c0..2ceedc9 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -1807,6 +1807,7 @@
#include <__algorithm/pstl_find.h>
#include <__algorithm/pstl_for_each.h>
#include <__algorithm/pstl_merge.h>
+#include <__algorithm/pstl_replace.h>
#include <__algorithm/pstl_stable_sort.h>
#include <__algorithm/pstl_transform.h>
#include <__algorithm/push_heap.h>
diff --git a/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp b/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp
index 2a634c3..4291521 100644
--- a/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp
+++ b/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp
@@ -130,6 +130,38 @@
pstl_fill_n_called = true;
}
+bool pstl_replace_called = false;
+
+template <class, class ForwardIterator, class T>
+void __pstl_replace(TestBackend, ForwardIterator, ForwardIterator, const T&, const T&) {
+ assert(!pstl_replace_called);
+ pstl_replace_called = true;
+}
+
+bool pstl_replace_if_called = false;
+
+template <class, class ForwardIterator, class T, class Func>
+void __pstl_replace_if(TestBackend, ForwardIterator, ForwardIterator, Func, const T&) {
+ assert(!pstl_replace_if_called);
+ pstl_replace_if_called = true;
+}
+
+bool pstl_replace_copy_called = false;
+
+template <class, class ForwardIterator, class ForwardOutIterator, class T>
+void __pstl_replace_copy(TestBackend, ForwardIterator, ForwardIterator, ForwardOutIterator, const T&, const T&) {
+ assert(!pstl_replace_copy_called);
+ pstl_replace_copy_called = true;
+}
+
+bool pstl_replace_copy_if_called = false;
+
+template <class, class ForwardIterator, class ForwardOutIterator, class T, class Func>
+void __pstl_replace_copy_if(TestBackend, ForwardIterator, ForwardIterator, ForwardOutIterator, Func, const T&) {
+ assert(!pstl_replace_copy_if_called);
+ pstl_replace_copy_if_called = true;
+}
+
bool pstl_unary_transform_called = false;
template <class, class ForwardIterator, class ForwardOutIterator, class UnaryOperation>
@@ -235,6 +267,14 @@
assert(std::pstl_for_each_called);
(void)std::for_each_n(TestPolicy{}, std::begin(a), std::size(a), pred);
assert(std::pstl_for_each_n_called);
+ (void)std::replace(TestPolicy{}, std::begin(a), std::end(a), 0, 0);
+ assert(std::pstl_replace_called);
+ (void)std::replace_if(TestPolicy{}, std::begin(a), std::end(a), pred, 0);
+ assert(std::pstl_replace_if_called);
+ (void)std::replace_copy(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), 0, 0);
+ assert(std::pstl_replace_copy_called);
+ (void)std::replace_copy_if(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), pred, 0);
+ assert(std::pstl_replace_copy_if_called);
(void)std::transform(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), pred);
assert(std::pstl_unary_transform_called);
(void)std::transform(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), std::begin(a), pred);
diff --git a/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace.pass.cpp b/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace.pass.cpp
new file mode 100644
index 0000000..0b51d35
--- /dev/null
+++ b/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace.pass.cpp
@@ -0,0 +1,96 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator, class T>
+// void replace(ExecutionPolicy&& exec,
+// ForwardIterator first, ForwardIterator last,
+// const T& old_value, const T& new_value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter>
+struct Test {
+ template <class ExecutionPolicy>
+ void operator()(ExecutionPolicy&& policy) {
+ { // simple test
+ std::array a = {1, 2, 3, 4, 5, 6, 7, 8};
+ std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+ assert((a == std::array{1, 2, 6, 4, 5, 6, 7, 8}));
+ }
+
+ { // empty range works
+ std::array<int, 0> a = {};
+ std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+ }
+
+ { // non-empty range without a match works
+ std::array a = {1, 2};
+ std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+ }
+
+ { // single element range works
+ std::array a = {3};
+ std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+ assert((a == std::array{6}));
+ }
+
+ { // two element range works
+ std::array a = {3, 4};
+ std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+ assert((a == std::array{6, 4}));
+ }
+
+ { // multiple matching elements work
+ std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
+ std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 9);
+ assert((a == std::array{1, 2, 9, 4, 9, 9, 5, 6, 9}));
+ }
+
+ { // large range works
+ std::vector<int> a(150, 3);
+ a[45] = 5;
+ std::replace(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), 3, 6);
+
+ std::vector<int> comp(150, 6);
+ comp[45] = 5;
+ assert(std::equal(a.begin(), a.end(), comp.begin()));
+ }
+ }
+};
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+ types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ std::set_terminate(terminate_successful);
+ ThrowOnCompare a[2];
+ try {
+ (void)std::replace(std::execution::par, std::begin(a), std::end(a), ThrowOnCompare{}, ThrowOnCompare{});
+ } catch (int) {
+ assert(false);
+ }
+#endif
+
+ return 0;
+}
diff --git a/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy.pass.cpp b/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy.pass.cpp
new file mode 100644
index 0000000..29c9692
--- /dev/null
+++ b/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy.pass.cpp
@@ -0,0 +1,106 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
+// ForwardIterator2
+// replace_copy(ExecutionPolicy&& exec,
+// ForwardIterator1 first, ForwardIterator1 last,
+// ForwardIterator2 result,
+// const T& old_value, const T& new_value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter>
+struct Test {
+ template <class ExecutionPolicy>
+ void operator()(ExecutionPolicy&& policy) {
+ { // simple test
+ std::array a = {1, 2, 3, 4, 5, 6, 7, 8};
+ std::array<int, a.size()> out;
+ std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), 3, 6);
+ assert((out == std::array{1, 2, 6, 4, 5, 6, 7, 8}));
+ }
+
+ { // empty range works
+ std::array<int, 0> a = {};
+ std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(a)), 3, 6);
+ }
+
+ { // non-empty range without a match works
+ std::array a = {1, 2};
+ std::array<int, a.size()> out;
+ std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(out.data()), 3, 6);
+ assert((out == std::array{1, 2}));
+ }
+
+ { // single element range works
+ std::array a = {3};
+ std::array<int, a.size()> out;
+ std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), 3, 6);
+ assert((out == std::array{6}));
+ }
+
+ { // two element range works
+ std::array a = {3, 4};
+ std::array<int, a.size()> out;
+ std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), 3, 6);
+ assert((out == std::array{6, 4}));
+ }
+
+ { // multiple matching elements work
+ std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
+ std::array<int, a.size()> out;
+ std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), 3, 9);
+ assert((out == std::array{1, 2, 9, 4, 9, 9, 5, 6, 9}));
+ }
+
+ { // large range works
+ std::vector<int> a(150, 3);
+ std::vector<int> out(a.size());
+ a[45] = 5;
+ std::replace_copy(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), Iter(out.data()), 3, 6);
+
+ std::vector<int> comp(150, 6);
+ comp[45] = 5;
+ assert(std::equal(out.begin(), out.end(), comp.begin()));
+ }
+ }
+};
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+ types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ std::set_terminate(terminate_successful);
+ ThrowOnCompare a[2];
+ try {
+ (void)std::replace_copy(
+ std::execution::par, std::begin(a), std::end(a), std::begin(a), ThrowOnCompare{}, ThrowOnCompare{});
+ } catch (int) {
+ assert(false);
+ }
+#endif
+
+ return 0;
+}
diff --git a/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy_if.pass.cpp b/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy_if.pass.cpp
new file mode 100644
index 0000000..965cedb
--- /dev/null
+++ b/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy_if.pass.cpp
@@ -0,0 +1,124 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+// class Predicate, class T>
+// ForwardIterator2
+// replace_copy_if(ExecutionPolicy&& exec,
+// ForwardIterator1 first, ForwardIterator1 last,
+// ForwardIterator2 result,
+// Predicate pred, const T& new_value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter>
+struct Test {
+ template <class ExecutionPolicy>
+ void operator()(ExecutionPolicy&& policy) {
+ { // simple test
+ std::array a = {1, 2, 3, 4, 5, 6, 7, 8};
+ std::array<int, a.size()> out;
+ std::replace_copy_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), [](int i) { return i == 3; }, 6);
+ assert((out == std::array{1, 2, 6, 4, 5, 6, 7, 8}));
+ }
+
+ { // empty range works
+ std::array<int, 0> a = {};
+ std::replace_copy_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(a)), [](int i) { return i == 3; }, 6);
+ }
+
+ { // non-empty range without a match works
+ std::array a = {1, 2};
+ std::array<int, a.size()> out;
+ std::replace_copy_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(out.data()), [](int i) { return i == 3; }, 6);
+ assert((out == std::array{1, 2}));
+ }
+
+ { // single element range works
+ std::array a = {3};
+ std::array<int, a.size()> out;
+ std::replace_copy_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), [](int i) { return i == 3; }, 6);
+ assert((out == std::array{6}));
+ }
+
+ { // two element range works
+ std::array a = {3, 4};
+ std::array<int, a.size()> out;
+ std::replace_copy_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), [](int i) { return i == 3; }, 6);
+ assert((out == std::array{6, 4}));
+ }
+
+ { // multiple matching elements work
+ std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
+ std::array<int, a.size()> out;
+ std::replace_copy_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), [](int i) { return i == 3; }, 9);
+ assert((out == std::array{1, 2, 9, 4, 9, 9, 5, 6, 9}));
+ }
+
+ { // large range works
+ std::vector<int> a(150, 3);
+ std::vector<int> out(a.size());
+ a[45] = 5;
+ std::replace_copy_if(
+ policy,
+ Iter(std::data(a)),
+ Iter(std::data(a) + std::size(a)),
+ Iter(out.data()),
+ [](int i) { return i == 3; },
+ 6);
+
+ std::vector<int> comp(150, 6);
+ comp[45] = 5;
+ assert(std::equal(out.begin(), out.end(), comp.begin()));
+ }
+ }
+};
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+ types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ std::set_terminate(terminate_successful);
+ ThrowOnCompare a[2];
+ try {
+ (void)std::replace_copy_if(
+ std::execution::par,
+ std::begin(a),
+ std::end(a),
+ std::begin(a),
+ [](ThrowOnCompare& i) { return i == i; },
+ ThrowOnCompare{});
+ } catch (int) {
+ assert(false);
+ }
+#endif
+
+ return 0;
+}
diff --git a/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_if.pass.cpp b/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_if.pass.cpp
new file mode 100644
index 0000000..2f81955
--- /dev/null
+++ b/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_if.pass.cpp
@@ -0,0 +1,102 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator, class Predicate, class T>
+// void replace_if(ExecutionPolicy&& exec,
+// ForwardIterator first, ForwardIterator last,
+// Predicate pred, const T& new_value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter>
+struct Test {
+ template <class ExecutionPolicy>
+ void operator()(ExecutionPolicy&& policy) {
+ { // simple test
+ std::array a = {1, 2, 3, 4, 5, 6, 7, 8};
+ std::replace_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 3 || i == 7; }, 6);
+ assert((a == std::array{1, 2, 6, 4, 5, 6, 6, 8}));
+ }
+
+ { // empty range works
+ std::array<int, 0> a = {};
+ std::replace_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), [](int) { return false; }, 6);
+ }
+
+ { // non-empty range without a match works
+ std::array a = {1, 2};
+ std::replace_if(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int) { return false; }, 6);
+ }
+
+ { // single element range works
+ std::array a = {3};
+ std::replace_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 3; }, 6);
+ assert((a == std::array{6}));
+ }
+
+ { // two element range works
+ std::array a = {3, 4};
+ std::replace_if(
+ policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 3; }, 6);
+ assert((a == std::array{6, 4}));
+ }
+
+ { // multiple matching elements work
+ std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
+ std::replace_if(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 3; }, 9);
+ assert((a == std::array{1, 2, 9, 4, 9, 9, 5, 6, 9}));
+ }
+
+ { // large range works
+ std::vector<int> a(150, 3);
+ a[45] = 5;
+ std::replace_if(
+ policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), [](int i) { return i == 3; }, 6);
+
+ std::vector<int> comp(150, 6);
+ comp[45] = 5;
+ assert(std::equal(a.begin(), a.end(), comp.begin()));
+ }
+ }
+};
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+ types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ std::set_terminate(terminate_successful);
+ ThrowOnCompare a[2];
+ try {
+ (void)std::replace_if(
+ std::execution::par, std::begin(a), std::end(a), [](ThrowOnCompare&) { return false; }, ThrowOnCompare{});
+ } catch (int) {
+ assert(false);
+ }
+#endif
+
+ return 0;
+}
