Is it valid to use std::transform with std::back_inserter?

Question

Cppreference has this example code for std::transform:

std::vector<std::size_t> ordinals; std::transform(s.begin(), s.end(), std::back_inserter(ordinals),                [](unsigned char c) -> std::size_t { return c; }); 

But it also says:

std::transform does not guarantee in-order application of unary_op or binary_op. To apply a function to a sequence in-order or to apply a function that modifies the elements of a sequence, use std::for_each.

This is presumably to allow parallel implementations. However the third parameter of std::transform is a LegacyOutputIterator which has the following postcondition for ++r:

After this operation r is not required to be incrementable and any copies of the previous value of r are no longer required to be dereferenceable or incrementable.

So it seems to me that the assignment of the output must happen in order. Do they simply mean that the application of unary_op may be out of order, and stored to a temporary location, but copied to the output in order? That doesn't sound like something you'd ever want to do.

Most C++ libraries haven't actually implemented parallel executors yet, but Microsoft has. I'm pretty sure this is the relevant code, and I think it calls this populate() function to record iterators to chunks of the output, which surely isn't a valid thing to do because LegacyOutputIterator can be invalidated by incrementing copies of it.

What am I missing?

Answer 1

1) The output iterator requirements in the standard are completely broken. See LWG2035.

2) If you use a purely output iterator and a purely input source range, then there's little else the algorithm can do in practice; it has no choice but to write in order. (However, a hypothetical implementation can choose to special-case its own types, like std::back_insert_iterator<std::vector<size_t>>; I don't see why any implementation would want to do it here, but it is permitted to do so.)

3) Nothing in the standard guarantees that transform applies the transformations in-order. We are looking at an implementation detail.

That std::transform requires only output iterators does not mean it cannot detect higher iterator strengths and reorder the operations in such cases. Indeed, algorithms dispatch on iterator strength all the time, and they have special handling for special iterator types (like pointers or vector iterators) all the time.

When the standard wants to guarantee a particular order, it knows how to say it (see std::copy's "starting from first and proceeding to last").

Answer 2

From n4385:

§25.6.4 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); 

§23.5.2.1.2 back_inserter

template<class Container> constexpr back_insert_iterator<Container> back_inserter(Container& x); 

Returns: back_insert_iterator(x).

§23.5.2.1 Class template back_insert_iterator

using iterator_category = output_iterator_tag; 

So std::back_inserter can't be used with parallel versions of std::transform. The versions that support output iterators read from their source with input iterators. Since input iterators can only be pre- and post-incremented (§23.3.5.2 Input iterators) and there is only sequential (i.e. non-parallel) execution, order must be preserved between them and the output iterator.