Movatterモバイル変換

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

3058. Paralleladjacent_difference shouldn't require creating temporaries

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

Priority:3

View all otherissues in [adjacent.difference].

View all issues withC++20 status.

Discussion:

Paralleladjacent_difference is presently specified to "create a temporary object whosetype isForwardIterator1's value type". Serialadjacent_difference does thatbecause it needs to work with input iterators, and needs to work when the destination rangeexactly overlaps the input range. The parallel version requires forward iterators and doesn'tallow 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' beforeminus and move to Ready.]

Previous resolution [SUPERSEDED]:

This wording is relative toN4713.

1. 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);

   -?- LetT be the value type ofdecltype(first). For the overloads that do nottake an argumentbinary_op, letbinary_op be an lvalue that denotes an object oftypeconst minus<>.

   -1-Requires:

   1. (1.1) — For the overloads with noExecutionPolicy,InputIterator’s value typeT shall beMoveAssignable (Table 25) and shall be constructible from the type of*first.acc (defined below) shall be writable (24.3.1[iterator.requirements.general]) totheresult output iterator. The result of the expressionval - std::move(acc)orbinary_op(val, std::move(acc)) shall be writable to theresult outputiterator.

   2. (1.2) — For the overloads with anExecutionPolicy, thevalue type ofForwardIterator1 shall beCopyConstructible (Table 24), constructible from theexpression*first - *first orbinary_op(*first, *first), and assignable to thevalue type ofForwardIterator2result of the expressionsbinary_op(*first, *first) and*first shall be writable toresult.

   3. (1.3) — […]

   -2-Effects: For the overloads with noExecutionPolicy and a non-empty range, thefunction creates an accumulatoraccwhose type isInputIterator’s valuetypeof typeT, initializes it with*first, and assigns theresult to*result. For every iteratori in[first + 1, last) in order,creates an objectval whose type isInputIterator’s value typeT, initializes it with*i, computesval - std::move(acc)orbinary_op(val, std::move(acc)), assigns the result to*(result + (i - first)), and move assigns fromval toacc.

   -3- For the overloads with anExecutionPolicy and a non-empty range,first the functioncreates an object whose type isForwardIterator1's value type, initializes it with*first, and assigns the result to*result. Then for everyd in[1, last - first - 1], creates an objectval whose type isForwardIterator1's value type, initializes it with*(first + d) - *(first + d - 1)orbinary_op(*(first + d), *(first + d - 1)), and assigns the result to*(result + d)performs*result = *first. Then, for everyd 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 toN4713.

1. 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);

   -?- LetT be the value type ofdecltype(first). For the overloads that do nottake an argumentbinary_op, letbinary_op be an lvalue that denotes an object oftypeminus<>.

   -1-Requires:

   1. (1.1) — For the overloads with noExecutionPolicy,InputIterator’s value typeT shall beMoveAssignable (Table 25) and shall be constructible from the type of*first.acc (defined below) shall be writable (24.3.1[iterator.requirements.general]) totheresult output iterator. The result of the expressionval - std::move(acc)orbinary_op(val, std::move(acc)) shall be writable to theresult outputiterator.

   2. (1.2) — For the overloads with anExecutionPolicy, thevalue type ofForwardIterator1 shall beCopyConstructible (Table 24), constructible from theexpression*first - *first orbinary_op(*first, *first), and assignable to thevalue type ofForwardIterator2result of the expressionsbinary_op(*first, *first) and*first shall be writable toresult.

   3. (1.3) — […]

   -2-Effects: For the overloads with noExecutionPolicy and a non-empty range, thefunction creates an accumulatoraccwhose type isInputIterator’s valuetypeof typeT, initializes it with*first, and assigns theresult to*result. For every iteratori in[first + 1, last) in order,creates an objectval whose type isInputIterator’s value typeT, initializes it with*i, computesval - std::move(acc)orbinary_op(val, std::move(acc)), assigns the result to*(result + (i - first)), and move assigns fromval toacc.

   -3- For the overloads with anExecutionPolicy and a non-empty range,first the functioncreates an object whose type isForwardIterator1's value type, initializes it with*first, and assigns the result to*result. Then for everyd in[1, last - first - 1], creates an objectval whose type isForwardIterator1's value type, initializes it with*(first + d) - *(first + d - 1)orbinary_op(*(first + d), *(first + d - 1)), and assigns the result to*(result + d)performs*result = *first. Then, for everyd in[1, last - first - 1], performs*(result + d) = binary_op(*(first + d), *(first + (d - 1))).