C++ Logo


Advanced search

[SG12] std::generate order

From: einstap_at <einstap_at_[hidden]>
Date: Fri, 03 Jan 2020 11:42:39 -0000

There were several discussions on other forums about std::generate and
whether or not is guarantees elements to be generated in-order (first
to last). Those discussions didn't lead to a clear result, which brings
me here.
I'm under the assumption that order is not guaranteed for the following

- std::generate has parallel overloads. Parallel algorithms can't
guarantee order without running in sequence.

- There is at least 1 parallel implementation that generates out-of-
order (Tested with clang++9, intel-tbb 2020.0-1, libstdc++ 9.2.0).
Together with [algorithms.parallel.overloads/2] and no exception to
this rule in the std::generate definition, the sequenced overload must
also be allowed to generate out-of-order.

- If std::generate was supposed to generate in-order, but this is an
oversight in the standard, the oversight would have been caught when
ranges::generate was added, which also doesn't differentiate between
the sequenced and parallel overloads.

In other forums it was argued that std::generate can't generate out-of-
order, because it uses a ForwardIterator. However, an implementation is
allowed to copy the iterator, advance the copy, start generating
somewhere in the middle, then generate the beginning at the very last.

I'm asking this question, because std::generate without a guaranteed
order (At least in the overload without an execution policy) is not
very useful, and I still have hope that I'm wrong. In many places
(Including the major references cplusplus.com and cppreference.com),
std::generate is used as if it guaranteed order.

Received on 2020-01-03 05:42:39