This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++20 status.

### 3058. Parallel `adjacent_difference` shouldn't require creating temporaries

Section: 25.10.12 [adjacent.difference] Status: C++20 Submitter: Billy O'Neal III Opened: 2018-02-02 Last modified: 2021-02-25

Priority: 3

View all other issues in [adjacent.difference].

View all issues with C++20 status.

Discussion:

Parallel `adjacent_difference` is presently specified to "create a temporary object whose type is `ForwardIterator1`'s value type". Serial `adjacent_difference` does that because it needs to work with input iterators, and needs to work when the destination range exactly overlaps the input range. The parallel version requires forward iterators and doesn't allow overlap, so it can avoid making these temporaries.

[2018-02-13, Priority set to 3 after mailing list discussion]

[2018-3-14 Wednesday evening issues processing; remove 'const' before `minus` and move to Ready.]

Previous resolution [SUPERSEDED]:

> This wording is relative to N4713.

> 1. Modify 25.10.12 [adjacent.difference] as indicated:

>    >     template<class InputIterator, class OutputIterator>
>    >       OutputIterator
>    >         adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);
>    >     template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
>    >       ForwardIterator2
>    >         adjacent_difference(ExecutionPolicy&& exec,
>    >                             ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);

>    >     template<class InputIterator, class OutputIterator, class BinaryOperation>
>    >       OutputIterator
>    >         adjacent_difference(InputIterator first, InputIterator last,
>    >                             OutputIterator result, BinaryOperation binary_op);
>    >     template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
>    >              class BinaryOperation>
>    >       ForwardIterator2
>    >         adjacent_difference(ExecutionPolicy&& exec,
>    >                             ForwardIterator1 first, ForwardIterator1 last,
>    >                             ForwardIterator2 result, BinaryOperation binary_op);

>    > > -?- Let `T` be the value type of `decltype(first)`. For the overloads that do not take an argument `binary_op`, let `binary_op` be an lvalue that denotes an object of type `const minus<>`.

>    > > -1- Requires:

>    > > 1. (1.1) — For the overloads with no `ExecutionPolicy`, `InputIterator`’s value type `T` shall be `MoveAssignable` (Table 25) and shall be constructible from the type of `*first`. `acc` (defined below) shall be writable (23.3.1 [iterator.requirements.general]) to the `result` output iterator. The result of the expression `val - std::move(acc)` or `binary_op(val, std::move(acc))` shall be writable to the `result` output iterator.

>    > > 2. (1.2) — For the overloads with an `ExecutionPolicy`, the value type of `ForwardIterator1` shall be `CopyConstructible` (Table 24), constructible from the expression `*first - *first` or `binary_op(*first, *first)`, and assignable to the value type of `ForwardIterator2` result of the expressions `binary_op(*first, *first)` and `*first` shall be writable to `result`.

>    > > 3. (1.3) — […]

>    > > -2- Effects: For the overloads with no `ExecutionPolicy` and a non-empty range, the function creates an accumulator `acc` whose type is `InputIterator`’s value type of type `T`, initializes it with `*first`, and assigns the result to `*result`. For every iterator `i` in `[first + 1, last)` in order, creates an object `val` whose type is `InputIterator`’s value type `T`, initializes it with `*i`, computes `val - std::move(acc)` or `binary_op(val, std::move(acc))`, assigns the result to `*(result + (i - first))`, and move assigns from `val` to `acc`.

>    > > -3- For the overloads with an `ExecutionPolicy` and a non-empty range, first the function creates an object whose type is `ForwardIterator1`'s value type, initializes it with `*first`, and assigns the result to `*result`. Then for every `d` in `[1, last - first - 1]`, creates an object `val` whose type is `ForwardIterator1`'s value type, initializes it with `*(first + d) - *(first + d - 1)` or `binary_op(*(first + d), *(first + d - 1))`, and assigns the result to `*(result + d)`performs `*result = *first`. Then, for every `d` in `[1, last - first - 1]`, performs `*(result + d) = binary_op(*(first + d), *(first + (d - 1)))`.

[2018-06 Rapperswil: Adopted]

Proposed resolution:

This wording is relative to N4713.

1. Modify 25.10.12 [adjacent.difference] as indicated:

   >     template<class InputIterator, class OutputIterator>
   >       OutputIterator
   >         adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);
   >     template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
   >       ForwardIterator2
   >         adjacent_difference(ExecutionPolicy&& exec,
   >                             ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);

   >     template<class InputIterator, class OutputIterator, class BinaryOperation>
   >       OutputIterator
   >         adjacent_difference(InputIterator first, InputIterator last,
   >                             OutputIterator result, BinaryOperation binary_op);
   >     template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
   >              class BinaryOperation>
   >       ForwardIterator2
   >         adjacent_difference(ExecutionPolicy&& exec,
   >                             ForwardIterator1 first, ForwardIterator1 last,
   >                             ForwardIterator2 result, BinaryOperation binary_op);

   > > -?- Let `T` be the value type of `decltype(first)`. For the overloads that do not take an argument `binary_op`, let `binary_op` be an lvalue that denotes an object of type `minus<>`.

   > > -1- Requires:

   > > 1. (1.1) — For the overloads with no `ExecutionPolicy`, `InputIterator`’s value type `T` shall be `MoveAssignable` (Table 25) and shall be constructible from the type of `*first`. `acc` (defined below) shall be writable (23.3.1 [iterator.requirements.general]) to the `result` output iterator. The result of the expression `val - std::move(acc)` or `binary_op(val, std::move(acc))` shall be writable to the `result` output iterator.

   > > 2. (1.2) — For the overloads with an `ExecutionPolicy`, the value type of `ForwardIterator1` shall be `CopyConstructible` (Table 24), constructible from the expression `*first - *first` or `binary_op(*first, *first)`, and assignable to the value type of `ForwardIterator2` result of the expressions `binary_op(*first, *first)` and `*first` shall be writable to `result`.

   > > 3. (1.3) — […]

   > > -2- Effects: For the overloads with no `ExecutionPolicy` and a non-empty range, the function creates an accumulator `acc` whose type is `InputIterator`’s value type of type `T`, initializes it with `*first`, and assigns the result to `*result`. For every iterator `i` in `[first + 1, last)` in order, creates an object `val` whose type is `InputIterator`’s value type `T`, initializes it with `*i`, computes `val - std::move(acc)` or `binary_op(val, std::move(acc))`, assigns the result to `*(result + (i - first))`, and move assigns from `val` to `acc`.

   > > -3- For the overloads with an `ExecutionPolicy` and a non-empty range, first the function creates an object whose type is `ForwardIterator1`'s value type, initializes it with `*first`, and assigns the result to `*result`. Then for every `d` in `[1, last - first - 1]`, creates an object `val` whose type is `ForwardIterator1`'s value type, initializes it with `*(first + d) - *(first + d - 1)` or `binary_op(*(first + d), *(first + d - 1))`, and assigns the result to `*(result + d)`performs `*result = *first`. Then, for every `d` in `[1, last - first - 1]`, performs `*(result + d) = binary_op(*(first + d), *(first + (d - 1)))`.