生成保证顺序执行？ [英] Is generate Guaranteed to be Executed Sequentially?

问题描述

我被告知这里：

生成的顺序不能保证=>取决于实现

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

我查过了 gcc的实现生成 ：

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

而Visual Studio也是这样实现的。这是一个救济，因为在生成中使用lambda可以读取和写入捕获可能有不确定的结果：

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;
});

我希望 bar 包含 {1,0,0}

I expect bar to contain {1, 0, 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.

这里注意， experimental :: parallel :: generate 不会是顺序的。我只是询问生成。

推荐答案

这样做了一些研究。

此答案的底部是截至2011年标准的相关章节的副本。

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

您将从 std :: generate<> 的模板声明中看到迭代器参数必须符合 ForwardIterator 和 OutputIterator 。

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 不支持随机存取。它只能依次读或写。 OutputIterator 更受限制 - 其运算符* 隐含地包括运算符++ 。这是概念的明确特征。

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.

因此，标准确实（隐式和安静地）保证 std :: generate 按顺序初始化其元素。这将是不可能写一个良好的实现 std :: generate ，没有。

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生成[alg.generate]

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效果：第一个算法调用函数对象gen和
通过范围
[first，last）中的所有迭代器分配gen的返回值。第二个算法调用函数对象gen，
通过范围
[first，first + n]中的所有迭代器赋值gen的返回值，如果n为正，否则不做任何操作。

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
需要：gen不需要参数，Size可以转换为
整数类型（4.7，12.3）。

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

3返回：generate_n返回第一个+ n，
为非负值，n为负值。

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

4复杂性：
分别是gen和赋值语句的第一，n或0个调用，分别是
。

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

这篇关于生成保证顺序执行？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！