[alg.transform]

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

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

### 26.7.4 Transform [alg.transform]

[ð](#lib:transform)

`template<class InputIterator, class OutputIterator,
         class UnaryOperation>
  constexpr OutputIterator
    transform(InputIterator first1, InputIterator last1,
              OutputIterator result, UnaryOperation op);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
         class UnaryOperation>
  ForwardIterator2
    transform(ExecutionPolicy&& exec,
              ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 result, UnaryOperation op);

template<class InputIterator1, class InputIterator2,
         class OutputIterator, class BinaryOperation>
  constexpr OutputIterator
    transform(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, OutputIterator result,
              BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
         class ForwardIterator, class BinaryOperation>
  ForwardIterator
    transform(ExecutionPolicy&& exec,
              ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 first2, ForwardIterator result,
              BinaryOperation binary_op);

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, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O,
         [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]") F, class Proj = identity>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, indirect_result_t<F&, projected<I, Proj>>>
  constexpr ranges::unary_transform_result<I, O>
    ranges::transform(I first1, S last1, O result, F op, Proj proj = {});
template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]") F,
         class Proj = identity>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
  constexpr ranges::unary_transform_result<borrowed_iterator_t<R>, O>
    ranges::transform(R&& r, O result, F op, 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,
         [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]") F, class Proj = identity>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, indirect_result_t<F&, projected<I, Proj>>>
  ranges::unary_transform_result<I, O>
    ranges::transform(Ep&& exec, I first1, S last1, O result, OutS result_last,
                      F op, 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,
          [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]") F, class Proj = identity>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<iterator_t<OutR>,
                                indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
  ranges::unary_transform_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
    ranges::transform(Ep&& exec, R&& r, OutR&& result_r, F op, Proj proj = {});

template<[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I1, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I1> S1, [input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") I2, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I2> S2,
         [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O, [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]") F, class Proj1 = identity,
         class Proj2 = identity>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, indirect_result_t<F&, projected<I1, Proj1>,
                               projected<I2, Proj2>>>
  constexpr ranges::binary_transform_result<I1, I2, O>
    ranges::transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                      F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
template<[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R1, [input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R2, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O,
         [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]") F, class Proj1 = identity, class Proj2 = identity>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>,
                               projected<iterator_t<R2>, Proj2>>>
  constexpr ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
    ranges::transform(R1&& r1, R2&& r2, O result,
                      F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});

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]") I1, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I1> S1,
         [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I2, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I2> S2,
         [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,
         [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]") F, class Proj1 = identity, class Proj2 = identity>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, indirect_result_t<F&, projected<I1, Proj1>,
                                projected<I2, Proj2>>>
  ranges::binary_transform_result<I1, I2, O>
    ranges::transform(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
                      O result, OutS result_last,
                      F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
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]") R1, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R2,
         [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR, [copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]") F,
          class Proj1 = identity, class Proj2 = identity>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<iterator_t<OutR>,
                                indirect_result_t<F&, projected<iterator_t<R1>, Proj1>,
                                projected<iterator_t<R2>, Proj2>>>
  ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>,
                                  borrowed_iterator_t<OutR>>
    ranges::transform(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
                      F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
`

[1](#1)

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

Let:

- [(1.1)](#1.1)

last2 be first2 + (last1 - first1) for the overloads in namespace std with parameter first2 but no parameter last2;

- [(1.2)](#1.2)

M be last1 - first1 for unary transforms, or min(last1 - first1, last2 - first2) for binary transforms;

- [(1.3)](#1.3)

result_last be result + M for the overloads with no parameter result_last or result_r;

- [(1.4)](#1.4)

N be min(M, result_last - result);

- [(1.5)](#1.5)

E(i) be
  * [(1.5.1)](#1.5.1)

op(*(first1 + (i - result))) for unary transforms defined in namespace std;

  * [(1.5.2)](#1.5.2)

binary_op(*(first1 + (i - result)), *(first2 + (i - result))) for binary transforms defined in namespace std;

  * [(1.5.3)](#1.5.3)

invoke(op, invoke(proj, *(first1 + (i - result)))) for unary transforms defined in namespace ranges;

  * [(1.5.4)](#1.5.4)

invoke(binary_op, invoke(proj1, *(first1 + (i - result))), invoke(proj2, *(first2 + (i - result)))) for binary transforms defined in namespace ranges[.](#1.sentence-1)

[2](#2)

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

*Preconditions*: For parallel algorithm overloadsop and binary_op satisfy the requirements
specified in [[algorithms.parallel.user]](algorithms.parallel.user "26.3.2 Requirements on user-provided function objects")[.](#2.sentence-1)

op and binary_op do not invalidate iterators or subranges, nor
modify elements in the ranges

- [(2.1)](#2.1)

[first1, first1 + N],

- [(2.2)](#2.2)

[first2, first2 + N], and

- [(2.3)](#2.3)

[result, result + N][.](#2.sentence-2)[203](#footnote-203 "The use of fully closed ranges is intentional.")

[3](#3)

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

*Effects*: Assigns through every iterator i in the range [result, result + N)
a new corresponding value equal to E(i)[.](#3.sentence-1)

[4](#4)

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

*Returns*: 

- [(4.1)](#4.1)

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

- [(4.2)](#4.2)

  {first1 + N, result + N} for unary transforms defined in namespace ranges[.](#4.2.sentence-1)

- [(4.3)](#4.3)

  {first1 + N, first2 + N, result + N} for binary transforms defined in namespace ranges[.](#4.3.sentence-1)

[5](#5)

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

*Complexity*: Exactly N applications of op or binary_op, and
any projections[.](#5.sentence-1)

This requirement also applies to the parallel algorithm overloads[.](#5.sentence-2)

[6](#6)

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

*Remarks*: result may be equal to first1 or first2[.](#6.sentence-1)

[203)](#footnote-203)[203)](#footnoteref-203)

The use of fully closed ranges is intentional[.](#footnote-203.sentence-1)
