diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -87,6 +87,7 @@
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/pstl_merge.h
+  __algorithm/pstl_replace.h
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
diff --git a/libcxx/include/__algorithm/pstl_backend.h b/libcxx/include/__algorithm/pstl_backend.h
--- a/libcxx/include/__algorithm/pstl_backend.h
+++ b/libcxx/include/__algorithm/pstl_backend.h
@@ -81,6 +81,28 @@
                             _OutIterator __result,
                             _Comp __comp);
 
+  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/libcxx/include/__algorithm/pstl_replace.h b/libcxx/include/__algorithm/pstl_replace.h
new file mode 100644
--- /dev/null
+++ b/libcxx/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/libcxx/include/algorithm b/libcxx/include/algorithm
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -1806,6 +1806,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_transform.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
diff --git a/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp b/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp
--- a/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp
@@ -108,6 +108,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>
@@ -165,6 +197,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/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace.pass.cpp
@@ -0,0 +1,85 @@
+//===----------------------------------------------------------------------===//
+//
+// 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);
+    }
+
+    { // 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}));
+    }
+
+    { // large range works
+      std::vector<int> a(3, 150);
+      a[45] = 5;
+      std::replace(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), 3, 6);
+
+      std::vector<int> comp(6, 150);
+      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/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy.pass.cpp
@@ -0,0 +1,92 @@
+//===----------------------------------------------------------------------===//
+//
+// 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);
+    }
+
+    { // 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}));
+    }
+
+    { // large range works
+      std::vector<int> a(3, 150);
+      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(6, 150);
+      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_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/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy_if.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy_if.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy_if.pass.cpp
@@ -0,0 +1,108 @@
+//===----------------------------------------------------------------------===//
+//
+// 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);
+    }
+
+    { // 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}));
+    }
+
+    { // large range works
+      std::vector<int> a(3, 150);
+      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(6, 150);
+      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_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/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_if.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_if.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_if.pass.cpp
@@ -0,0 +1,91 @@
+//===----------------------------------------------------------------------===//
+//
+// 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);
+    }
+
+    { // 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}));
+    }
+
+    { // large range works
+      std::vector<int> a(3, 150);
+      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(6, 150);
+      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;
+}