c++ - 生成保证顺序执行吗？

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

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

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

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

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

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

因此标准确实(隐含地和安静地)保证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.