Title
Incorrect requirements for transform_inclusive_scan without initial value
Status
new
Section
[transform.inclusive.scan]
Submitter
Agustín K-ballo Bergé

Created on 2020-07-07.00:00:00 last changed 45 months ago

Messages

Date: 2020-07-17.22:37:26

Proposed resolution:

This wording is relative to N4861.

[Drafting note: Current implementations that accept the code, do some form of auto acc = unary_op(*first);, therefore the following proposed wording uses decay_t instead of e.g. remove_cvref_t.]

  1. Modify [transform.inclusive.scan] as indicated:

    template<class InputIterator, class OutputIterator,
             class BinaryOperation, class UnaryOperation>
      constexpr OutputIterator
        transform_inclusive_scan(InputIterator first, InputIterator last,
                                 OutputIterator result,
                                 BinaryOperation binary_op, UnaryOperation unary_op);
    template<class ExecutionPolicy,
             class ForwardIterator1, class ForwardIterator2,
             class BinaryOperation, class UnaryOperation>
      ForwardIterator2
        transform_inclusive_scan(ExecutionPolicy&& exec,
                                 ForwardIterator1 first, ForwardIterator1 last,
                                 ForwardIterator2 result,
                                 BinaryOperation binary_op, UnaryOperation unary_op);
    template<class InputIterator, class OutputIterator,
             class BinaryOperation, class UnaryOperation, class T>
      constexpr OutputIterator
        transform_inclusive_scan(InputIterator first, InputIterator last,
                                 OutputIterator result,
                                 BinaryOperation binary_op, UnaryOperation unary_op,
                                 T init);
    template<class ExecutionPolicy,
             class ForwardIterator1, class ForwardIterator2,
             class BinaryOperation, class UnaryOperation, class T>
      ForwardIterator2
        transform_inclusive_scan(ExecutionPolicy&& exec,
                                 ForwardIterator1 first, ForwardIterator1 last,
                                 ForwardIterator2 result,
                                 BinaryOperation binary_op, UnaryOperation unary_op,
                                 T init);
    

    -1- Let U be the value type of decltype(first)decay_t<decltype(unary_op(*first))>.

    -2- […]

Date: 2020-07-15.00:00:00

[ 2020-07-17; Priority set to 3 in telecon ]

Date: 2020-07-07.00:00:00

The requirements for the overloads of std::transform_inclusive_scan without an initial value incorrectly assume that the internal accumulator uses the iterator's value type, as it does for std::inclusive_scan, rather than the transformed type of the iterator's value type, as it was intended.

According to the standard, the following program is ill-formed as it requires std::string to be convertible to int:

auto vs = {0, 1, 2};
std::transform_inclusive_scan(
   vs.begin(), vs.end(),
   std::ostream_iterator<std::string>(std::cout, ";"),
   [](std::string x, std::string y) { return x + y; },
   [](int x) { return std::to_string(x); });

libstdc++ and Microsoft's STL accept the snippet, producing 0;01;012; as expected, libc++ strictly conforms to the standard and rejects it.

These constrains were introduced by P0574R1.

History
Date User Action Args
2020-07-17 22:37:26adminsetmessages: + msg11389
2020-07-12 17:01:28adminsetmessages: + msg11366
2020-07-07 00:00:00admincreate