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

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").

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.