Is generate Guaranteed to be Executed Sequentially?

Question

I was told here that:

The order of generate is not guaranteed => depending on the implementation

I have looked up gcc's implementation of generate:

  for (; __first != __last; ++__first)
*__first = __gen();

And Visual Studio implements it identically to that. This is a relief to me as using a lambda in generate that reads and writes to a capture could have undeterministic results:

int foo[] = {1, 0, 13};
vector<int> bar(3);

generate(bar.begin(), bar.end(), [&]() {
    static auto i = 0;
    static auto total = 0;

    total += foo[i];
    return foo[i] / total;
});

I expect bar to contain {1, 0, 0}.

If I am allowed to execute out of order this could even cause a divide by 0 error.

So I'd sleep easier if this question could be answered with proof that generate is required to execute sequentially.

As a note here, I know that experimental::parallel::generate will not be sequential. I'm just asking about generate.

Possible duplicate of [Why std::transform doesn't guarantee the order (but for\_each guarantee the order)? Doesn't this allow trick implementation for performance?](http://stackoverflow.com/questions/17356719/why-stdtransform-doesnt-guarantee-the-order-but-for-each-guarantee-the-order) — 101010, Oct 22 '15 at 14:22
after doing a little research (and some lateral thought) I can confirm that std::generate is guaranteed to be sequential. answer below. — Richard Hodges, Oct 23 '15 at 15:10

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

3

I was intrigued by this so have done some research.

At the bottom of this answer is a copy of the relevant section from the standard as of 2011.

You will see from the template declaration of std::generate<> that the iterator parameters must conform to the concept of a ForwardIterator and OutputIterator respectively.

A ForwardIterator does not support random access. it can only read or write sequentially. An OutputIterator is even more restrictive - its operator* implicitly includes the effect of an operator++. This is an explicit feature of the concept.

Therefore, by implication, the implementation of this function must access elements sequentially (and therefore generate values sequentially) since to not do so would break the contract implicit in the interface.

Therefore the standard does (implicitly and quietly) guarantee that std::generate initialise its elements sequentially. It would be impossible to write a well-formed implementation of std::generate that did not.

QED

25.3.7 Generate [alg.generate]

template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
Generator gen);

template<class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

1 Effects: The first algorithm invokes the function object gen and assigns the return value of gen through all the iterators in the range [first,last). The second algorithm invokes the function object gen and assigns the return value of gen through all the iterators in the range [first,first + n) if n is positive, otherwise it does nothing.

2 Requires: gen takes no arguments, Size shall be convertible to an integral type (4.7, 12.3).

3 Returns: generate_n returns first + n for non-negative values of n and first for negative values.

4 Complexity: Exactly last - first, n, or 0 invocations of gen and assignments, respectively.

edited Jun 20 '20 at 09:12

Community

1
1

answered Oct 23 '15 at 15:05

Richard Hodges

68,278
7
90
142

Whew I can sleep again at night. I knew that about `ForwardIterator`s but I never put much thought into it, that's actually really important in this situation isn't it. The linked [std::transform doesn't guarantee the order (but for_each guarantee the order)? Doesn't this allow trick implementation for performance?](http://stackoverflow.com/questions/17356719/why-stdtransform-doesnt-guarantee-the-order-but-for-each-guarantee-the-order) also makes the same mistake. It'd be worthwhile to go post an answer there, or at least a comment with a link to this answer. – Jonathan Mee Oct 23 '15 at 15:24
1

@RichardHodges +1 Overlooked that too ... well, generate got just usable again :D – deviantfan Oct 23 '15 at 16:09
Algorithms can be optimised to different iterator categories. – curiousguy Oct 28 '15 at 12:48
@curiousguy optimise yes, but change observable behaviour no. The algorithm's interface mandates ForwardIterator. Therefore to detect that it really is a random access iterator and use it (illogically) as such would change the observable behaviour of the function template. – Richard Hodges Oct 28 '15 at 13:43
@RichardHodges What is observable behaviour? – curiousguy Oct 28 '15 at 13:47
for example "this function fills the range between one **forward iterator** and another". There is an unequivocal implicit implication that the function will iterate forwards, since its interface is presented in terms of forward iterators and the documentation must be read in that light. If there was an intention that it could optionally iterate backwards (or randomly) this would be explicitly made clear by the function being declared in terms of random access iterators. This would give rise to the possibility of different observable behaviour (generated values landing in different positions). – Richard Hodges Oct 28 '15 at 14:47

score 1 · Answer 2 · answered Oct 22 '15 at 14:27

Here is all the standard says about it (25.7.3/1):

template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen);

template<class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

The first algorithm invokes the function object gen and assigns the return value of gen through all the iterators in the range [first,last) . The second algorithm invokes the function object gen and assigns the return value of gen through all the iterators in the range [first,first + n) if n is positive, otherwise it does nothing.

As you can see, it is not explicitly stated that the iterator assignments must be done sequentially.

Just wanted to make sure that you saw [Richard Hodges answer](http://stackoverflow.com/a/33305627/2642059), it is in conflict with your, but I believe his answer is correct. — Jonathan Mee, Oct 23 '15 at 15:26

Is generate Guaranteed to be Executed Sequentially?

2 Answers2

Linked