[alg.replace]

# 26 Algorithms library [[algorithms]](./#algorithms)

## 26.7 Mutating sequence operations [[alg.modifying.operations]](alg.modifying.operations#alg.replace)

### 26.7.5 Replace [alg.replace]

[ð](#lib:replace)

`template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
  constexpr void replace(ForwardIterator first, ForwardIterator last,
                         const T& old_value, const T& new_value);
template<class ExecutionPolicy, class ForwardIterator,
         class T = iterator_traits<ForwardIterator>::value_type>
  void replace(ExecutionPolicy&& exec,
               ForwardIterator first, ForwardIterator last,
               const T& old_value, const T& new_value);

template<class ForwardIterator, class Predicate,
         class T = iterator_traits<ForwardIterator>::value_type>
  constexpr void replace_if(ForwardIterator first, ForwardIterator last,
                            Predicate pred, const T& new_value);
template<class ExecutionPolicy, class ForwardIterator, class Predicate,
         class T = iterator_traits<ForwardIterator>::value_type>
  void replace_if(ExecutionPolicy&& exec,
                  ForwardIterator first, ForwardIterator last,
                  Predicate pred, const T& new_value);

template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S, class Proj = identity,
         class T1 = projected_value_t<I, Proj>, class T2 = T1>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<I, const T2&> &&
           [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<I, Proj>, const T1*>
  constexpr I
    ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});
template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity,
         class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = T1>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<iterator_t<R>, const T2&> &&
           [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
  constexpr borrowed_iterator_t<R>
    ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {});

template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I> S,
         class Proj = identity, class T1 = projected_value_t<I, Proj>, class T2 = T1>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<I, const T2&> &&
           [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<I, Proj>, const T1*>
  I ranges::replace(Ep&& exec, I first, S last,
                    const T1& old_value, const T2& new_value, Proj proj = {});
template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity,
         class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = T1>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<iterator_t<R>, const T2&> &&
            [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to,
                                      projected<iterator_t<R>, Proj>, const T1*>
  borrowed_iterator_t<R>
    ranges::replace(Ep&& exec, R&& r, const T1& old_value, const T2& new_value,
                    Proj proj = {});

template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S, class Proj = identity,
         class T = projected_value_t<I, Proj>,
         [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> Pred>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<I, const T&>
  constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {});
template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>,
         [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> Pred>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<iterator_t<R>, const T&>
  constexpr borrowed_iterator_t<R>
    ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {});

template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I> S,
         class Proj = identity, class T = projected_value_t<I, Proj>,
         [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> Pred>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<I, const T&>
  I ranges::replace_if(Ep&& exec, I first, S last, Pred pred,
                       const T& new_value, Proj proj = {});
template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity,
         class T = projected_value_t<iterator_t<R>, Proj>,
         [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> Pred>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<iterator_t<R>, const T&>
  borrowed_iterator_t<R>
    ranges::replace_if(Ep&& exec, R&& r, Pred pred, const T& new_value, Proj proj = {});
`

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7203)

Let E(i) be

- [(1.1)](#1.1)

bool(*i == old_value) for replace;

- [(1.2)](#1.2)

bool(pred(*i)) for replace_if;

- [(1.3)](#1.3)

bool(invoke(proj, *i) == old_value) for ranges​::​replace;

- [(1.4)](#1.4)

bool(invoke(pred, invoke(proj, *i))) for ranges​::​replace_if[.](#1.sentence-1)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7212)

*Mandates*: new_value is writable ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General")) to first[.](#2.sentence-1)

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7216)

*Effects*: Substitutes elements referred by the iterator i in the range [first, last) with new_value,
when E(i) is true[.](#3.sentence-1)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7222)

*Returns*: last for the overloads in namespace ranges[.](#4.sentence-1)

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7226)

*Complexity*: Exactly last - first applications
of the corresponding predicate and any projection[.](#5.sentence-1)

[ð](#lib:replace_copy)

`template<class InputIterator, class OutputIterator, class T>
  constexpr OutputIterator
    replace_copy(InputIterator first, InputIterator last,
                 OutputIterator result,
                 const T& old_value, const T& new_value);
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);

template<class InputIterator, class OutputIterator, class Predicate, class T>
  constexpr OutputIterator
    replace_copy_if(InputIterator first, InputIterator last,
                    OutputIterator result,
                    Predicate pred, const T& new_value);
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);

template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S, class O,
         class Proj = identity, class T1 = projected_value_t<I, Proj>, class T2 = iter_value_t<O>>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O> &&
           [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<I, Proj>, const T1*> &&
           [output_iterator](iterator.concept.output#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]")<O, const T2&>
  constexpr ranges::replace_copy_result<I, O>
    ranges::replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
                         Proj proj = {});
template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class O, class Proj = identity,
         class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = iter_value_t<O>>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<iterator_t<R>, O> &&
           [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
           && [output_iterator](iterator.concept.output#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]")<O, const T2&>
  constexpr ranges::replace_copy_result<borrowed_iterator_t<R>, O>
    ranges::replace_copy(R&& r, O result, const T1& old_value, const T2& new_value,
                         Proj proj = {});

template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I> S,
         [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<O> OutS,
         class Proj = identity,
         class T1 = projected_value_t<I, Proj>, class T2 = iter_value_t<O>>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O> &&
           [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<I, Proj>, const T1*> &&
           [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, const T2&>
  ranges::replace_copy_result<I, O>
    ranges::replace_copy(Ep&& exec, I first, S last, O result, OutS result_last,
                         const T1& old_value, const T2& new_value, Proj proj = {});
template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR,
         class Proj = identity, class T1 = projected_value_t<iterator_t<R>, Proj>,
         class T2 = range_value_t<OutR>>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<iterator_t<R>, iterator_t<OutR>> &&
           [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to,
                                      projected<iterator_t<R>, Proj>, const T1*> &&
           [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<iterator_t<OutR>, const T2&>
  ranges::replace_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
    ranges::replace_copy(Ep&& exec, R&& r, OutR&& result_r, const T1& old_value,
                         const T2& new_value, Proj proj = {});

template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S,class O, class T = iter_value_t<O>,
         class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> Pred>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O> && [output_iterator](iterator.concept.output#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]")<O, const T&>
  constexpr ranges::replace_copy_if_result<I, O>
    ranges::replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
                            Proj proj = {});
template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class O, class T = iter_value_t<O>, class Proj = identity,
         [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> Pred>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<iterator_t<R>, O> && [output_iterator](iterator.concept.output#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]")<O, const T&>
  constexpr ranges::replace_copy_if_result<borrowed_iterator_t<R>, O>
    ranges::replace_copy_if(R&& r, O result, Pred pred, const T& new_value,
                            Proj proj = {});

template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I> S,
         [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<O> OutS, class T = iter_value_t<O>,
         class Proj = identity, [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> Pred>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O> && [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, const T&>
  ranges::replace_copy_if_result<I, O>
    ranges::replace_copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
                            Pred pred, const T& new_value, Proj proj = {});
template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR,
         class T = range_value_t<OutR>, class Proj = identity,
         [indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> Pred>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<iterator_t<R>, iterator_t<OutR>> &&
           [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<OutR, const T&>
  ranges::replace_copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
    ranges::replace_copy_if(Ep&& exec, R&& r, OutR&& result_r, Pred pred, const T& new_value,
                            Proj proj = {});
`

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7330)

Let E(i) be

- [(6.1)](#6.1)

bool(*(first + (i - result)) == old_value) for replace_copy;

- [(6.2)](#6.2)

bool(pred(*(first + (i - result)))) for replace_copy_if;

- [(6.3)](#6.3)

bool(invoke(proj, *(first + (i - result))) == old_value) for ranges​::​replace_copy;

- [(6.4)](#6.4)

bool(invoke(pred, invoke(proj, *(first + (i - result))))) for ranges​::​replace_copy_if[.](#6.sentence-1)

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7343)

Let:

- [(7.1)](#7.1)

result_last be result + (last - first) for the overloads with no parameter result_last or result_r;

- [(7.2)](#7.2)

N be min(last - first, result_last - result)[.](#7.sentence-1)

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7353)

*Mandates*: The results of the expressions *first and new_value are writable ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General")) to result[.](#8.sentence-1)

[9](#9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7358)

*Preconditions*: The ranges [first, last) and [result, result + N)
do not overlap[.](#9.sentence-1)

[10](#10)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7363)

*Effects*: Assigns through every iterator i in the range [result, result + N)
a new corresponding value

- [(10.1)](#10.1)

new_value if E(i) is true or

- [(10.2)](#10.2)

*(first + (i - result)) otherwise[.](#10.sentence-1)

[11](#11)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7373)

*Returns*: 

- [(11.1)](#11.1)

  result + N for the overloads in namespace std[.](#11.1.sentence-1)

- [(11.2)](#11.2)

  {first + N, result + N} for the overloads in namespace ranges[.](#11.2.sentence-1)

[12](#12)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7384)

*Complexity*: Exactly N applications
of the corresponding predicate and any projection[.](#12.sentence-1)
