Issue 3058: Parallel adjacent_difference shouldn't require creating temporaries

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

Section: 26.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.
Modify 26.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) — 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 (24.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.

(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 ForwardIterator2result of the expressions binary_op(*first, *first) and *first shall be writable to result.

(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.

Modify 26.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 (24.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 ForwardIterator2result 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))).

3058. Parallel adjacent_difference shouldn't require creating temporaries

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