生成保证顺序执行吗？

Question

有人告诉我 here：

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

我已经查过了gcc's implementation of generate:

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

并且 Visual Studio 的实现方式与此相同。这让我松了一口气，因为在 generate 中使用 lambda 读取和写入捕获可能会产生不确定的结果：

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 包含 {1, 0, 0}.

如果允许我乱序执行，这甚至可能导致除以 0 错误。

所以如果这个问题可以通过证明 generate 需要按顺序执行来回答，我会睡得更安心。

这里需要注意的是，我知道 experimental::parallel::generate 不会是连续的。我只是问 generate.

Answer 1

以下是关于它的所有标准 (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.

如您所见，没有明确说明迭代器赋值必须按顺序进行。

Answer 2

我对此很感兴趣，所以做了一些研究。

此答案底部是 2011 年标准中相关部分的副本。

从std::generate<>的模板声明中可以看出，迭代器参数必须分别符合ForwardIterator和OutputIterator的概念。

ForwardIterator 不支持随机访问。它只能顺序读取或写入。 OutputIterator 甚至更具限制性 - 它的 operator* 隐含地包含 operator++ 的效果。这是该概念的显式特征。

因此，暗示此函数的实现必须按顺序访问元素（并因此按顺序生成值），因为 不这样做会破坏契约隐含在接口中.

因此标准确实（隐含地和安静地）保证std::generate按顺序初始化它的元素。编写一个格式正确的 std::generate 实现是不可能的。

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.

生成保证顺序执行吗？

Is generate Guaranteed to be Executed Sequentially?

c++

algorithm

lambda

language-lawyer

sequential